Interface default methods

I am coding feverishly to complete a web interface to the JVM internals like memory, threads etc. This is my first set of default methods in an interface.

I have not read the JLS comparison between this and other inheritance mechanisms but this serves a purpose.

package com.memory.probe;

import java.io.IOException;
import java.io.PrintWriter;
import java.io.StringWriter;
import java.util.AbstractQueue;
import java.util.concurrent.ArrayBlockingQueue;

import javax.management.remote.JMXConnector;
import javax.management.remote.JMXConnectorFactory;
import javax.management.remote.JMXServiceURL;

import org.apache.log4j.Logger;

public interface Probe {
	
	Logger l = Logger.getLogger("generation.gc");
	
	AbstractQueue<Long> abq = new ArrayBlockingQueue<Long>(100);

	default void connectJMXRemote(int port){
	      JMXServiceURL url;
	  	try {
	  		url = new JMXServiceURL(
	  		            "service:jmx:rmi:///jndi/rmi://localhost:" + port + "/jmxrmi");
	  		JMXConnector jmxc = JMXConnectorFactory.connect(url, null);
	  		l.debug("Remote JMX connection is successful");
	  	} catch (IOException e) {
	  		l.debug(getStackTrace(e));
	  	}

	}
	
	default String getTrace(Throwable t){
		return getStackTrace(t);
	}
	
    static String getStackTrace(Throwable t){
    	StringWriter sw = new StringWriter();
    	PrintWriter pw = new PrintWriter(sw);
    	t.printStackTrace(pw);
    	return sw.toString();
    	
    }


}

Real-time graph showing heap generations

I am able to dynamically update a graph in real-time with test data using the code shown in the previous post. The graph is refreshed without refreshing the entire browser. Even though the particular JavaScript graph library will be replaced with another better one, at this time the tests are successful.
Now I will be able to use JMX to get the YoungGen data from the heap and show actual data as the GC collects the garbage.

All the code will be pushed to Github.

Screen Shot 2014-06-23 at 11.10.36 AM

R Shiny

I have recently started to code a web dashboard to show information like heap usage in HotSpot. So initially I setup a Shiny server. The part that connects to HotSpot is not ready but this is my first Shiny UI. This is a Twitter BootStrap UI.

Part of the shiny server code is this. Now the data is generated by R code and later the data will be extracted from the JVM using JMX and other serviceability API’s.

output$metaspace <- renderChart({
  metacapacity <- data.frame(lapply(as.Date('2014-08-06') + 0:0, seq, as.Date('2014/10/08'), '1 weeks'));
  metacapacity['init'] <- 300
  metacapacity['committed'] <- 700
  colnames(metacapacity) <- c("date","init","committed")
  metacapacity  <- transform(metacapacity,date=as.character(date))
  ms <- mPlot(x = "date", y = c("init", "committed"), type = "Area", data = metacapacity)
  ms$addParams(height = 300, dom = 'metaspace')
  ms$set(title="MetaSpace")
  return(ms)
  })

CompletableFuture

The short definition of java.util.concurrent.CompletableFuture<T> is

A Future that may be explicitly completed (setting its value and status), and may be used as a CompletionStage, supporting dependent functions and actions that trigger upon its completion.

Code that conforms to the Reactive manifesto is all the rage now. The Play framework embodies it.

This example uses CompletableFuture and Apache HTTP Components to download data and react to its completion. I will update this as I learn more about the API and explain the asynchronous nature of this type of code.

public class ReactiveCompletion {

    ExecutorService executor = Executors.newFixedThreadPool(4);

    private void fetch() throws IOException{

        CountDownLatch latch = new CountDownLatch(1);
        CompletableFuture future =
        CompletableFuture.anyOf(CompletableFuture.supplyAsync(() -> streamData())
        .thenAccept(content -> {
            System.out.println("Completed");
            latch.countDown();
        })
        );
        try {
            latch.await();
        } catch (InterruptedException e) {
            System.out.println("Interrupted");
        }
    }

    private Content streamData(){
        Content content = null;
        try{
            CloseableHttpClient httpclient = HttpClients.createDefault();
            HttpGet httpget = new HttpGet("http://data.gov.in/node/104089/datastore/export/json");
            CloseableHttpResponse response = httpclient.execute(httpget);
            try {
                HttpEntity entity = response.getEntity();
                if (entity != null) {
                    Scanner in = new Scanner(new BufferedReader(new InputStreamReader(entity.getContent())));
                    while(in.hasNextLine() ){
                        System.out.println(in.nextLine());
                    }
                }
            } finally {
                response.close();
            }
        }catch (  IOException io){
            io.printStackTrace();
        }
        return content;
    }

    public static void main(String... argv) throws IOException {
        new ReactiveCompletion().fetch();
    }
}

Left-leaning Red-Black Trees

I think this is the easiest algorithm to learn and code. Robert Sedgewick’s Java code is always succinct. I have learnt how to code Tries based on his code. Now his Red-black tree code is easy to remember.

http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf

Though the properties of this type of tree are different from the original Red-black tree I think it is sufficient to remember this condensed code.

These are the three lines and some small methods that we should remember mainly.

        if ( isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
        if ( isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
        if ( isRed(h.left) && isRed(h.right)) colorFlip(h);

Original binary tree before rotation

Screen Shot 2014-06-02 at 9.43.10 AM

Final tree

Screen Shot 2014-06-02 at 9.50.41 AM

I think the fundamental rules are these apart from the other Red-black tree rules.

  1. Disallow right-leaning red nodes.
  2. Disallow more than two consecutive red nodes.

Red-Black Tree

I will refine this post as I code more methods. This is an attempt to learn this data structure and explain what I think I understand using pictures drawn using TEX. I use the tikz editor.

The algorithm code is based on pseudo-code from “Introduction to Algorithms” by Thomas H. Cormen et al. I use Java language features like enums etc. wherever possible.

Sample TEX code

[->,>=stealth',level/.style={sibling distance = 5cm/#1,
  level distance = 1.5cm}] 
\node [arn_n] {3}
    child{ node [arn_r] {2} 
 				child{ node [arn_nil] {NIL}}
    }
    child{ node [arn_r] {4}
							child{ node [arn_nil] {NIL}}
	}
;

Insert

public class RedBlack {

    private final Node SENTINEL= new Node();
    private Node root= new Node();

    public RedBlack() {
        root = SENTINEL;
    }

    enum Color {
        BLACK,
        RED};

    class Node{

        public void setColor(Color color) {
            this.color = color;
        }

        private Color color = Color.BLACK;

        Node left,right,p;
        int key;
    }

    public void insert( RedBlack tree,
                        Node z){
        
        Node y =  SENTINEL;
        Node x =  tree.root;
        
        while( x != SENTINEL){
            y = x;
            if ( z.key < x.key){
                x = x.left;
            }else
                x = x.right;
        }
        
        z.p = y;
        
        if( y == SENTINEL){
            tree.root = z;
        }else if ( z.key < y.key){
                z = y.left;
        }else{
                z = y.right;
        }
        z.left = z.right = SENTINEL;
        z.setColor(Color.RED);
    }
}

I check the colors like this.

    public void inOrder(Node x){

        if( x != SENTINEL){
            inOrder(x.left);
            System.out.println(x.key + "[" + x.color + "]");
            inOrder(x.right);
        }
    }

Now this tree has to be fixed so that it conforms to the rules that govern a Red-Black tree. So I code a method to fix it. This method is based on the pseudo-code from the same book. But I think there is a bug which I haven’t found. This tree after it is fixed looks like this.

Screen Shot 2014-06-01 at 1.17.01 PM

The black height property is 2.

The black height property for the left branch is 2 but it is 3 for one of the paths on the right.

I may have to read some other book because finding this bug is going to be hard.

Actually the tree should be like this.

Hackerrank’s Service Lane

I am again posting code without asymtotic analysis. There is no standard algorithm used here. I believe this problem pertains to Range Minimum Query algorithm which I hope to explore.

It is ridiculous that the code to parse the input values is more complex than the actual brute-force algorithm. Should Hackerrank parse it for us ?

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Solution {

    private int noOfTestCases;

    private ArrayList<Integer> widths = new ArrayList<>();
    private ArrayList<Segment> tests = new ArrayList<>();

    OutputStream outputStream = System.out;
    PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));


    public void  getInput(BufferedReader br) throws IOException {
        Scanner s = null;
        int lengthHighway = 0;
        try {
            s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));

            if (s.hasNextLine()) {
                String[] s1 = s.nextLine().split("\\s+");
                lengthHighway = Integer.parseInt(s1[0]);
                noOfTestCases = Integer.parseInt(s1[1]);
            }
            if (s.hasNextLine()) {
                String[] s1 = s.nextLine().split("\\s+");
                for( int i = 0 ; i < s1.length ; i ++){
                    widths.add( Integer.parseInt(s1[i]) );
                }
            }
            while (s.hasNextLine()) {
                String[] s1 = s.nextLine().split("\\s+");
                tests.add( new Segment(Integer.parseInt(s1[0]), Integer.parseInt(s1[1]) ));
            }
        } finally {
            s.close();
        }
    }

    class Segment{

        public final int entry,exit;

        public Segment(int entry, int exit) {
            this.entry = entry;
            this.exit = exit;
        }
    }

    public static void main( String... argv ) throws IOException {
        Solution rm = new Solution();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        rm.getInput(br);
        rm.fit();

    }

   private void fit() {
        int[] vehicle = new int[]{1,2,3};

        try {
            for( Segment test : tests){
                Integer[] a  = Arrays.copyOfRange(widths.toArray(new Integer[widths.size()]), test.entry, test.exit+1);
                Arrays.sort(a);
                pw.println(vehicle[a[0]-1]);
                pw.flush();
            }
        }finally{
            pw.close();
        }
    }

}

A randomized divide-and-conquer algorithm

There is nothing new here. My Java code to find the k^{th} smallest element in an array(Algorithms book by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani). The code is written based on the pseudo-code.

I am using Google guava here.

Ints.toArray( less )

This is the algorithm definition.

selection(S,k) = \begin{cases} selection(S_L,k), & \mbox{if } k\le |S_L|\\ v, & \mbox{if } |S_L| < k \le |S_L| + |S_v|\\ selection(S_R,k-|S_L|-|S_v|, & \mbox{if } k\ge |S_L|+|S_v| \end{cases}

import com.google.common.primitives.Ints;

import java.util.ArrayList;
import java.util.Random;

import static java.util.Arrays.sort;

public class KThLargestSelection {

    private Random r = new Random();

    static int[] a1 = new int[]{ 0,2,7,3,4,9};

        public int findKThLargest(  int[] a, int k ){

                int pivot = getPivot(a);

                ArrayList<Integer> less = new ArrayList<>();
                ArrayList<Integer> equal = new ArrayList<>();
                ArrayList<Integer> great = new ArrayList<>();

                for( int value : a ){
                        if ( value < pivot){
                            less.add( value );
                        } else if ( value == pivot){
                            equal.add( value );
                        }else if ( value > pivot){
                            great.add( value );
                        }
                }
                        if (k <= less.size()) {
                            return findKThLargest (Ints.toArray( less ), k);
                        }else if (k <= less.size() + equal.size()){
                            return  pivot;
                        }else
                            return   findKThLargest (Ints.toArray( great  ), k - less.size() - equal.size());

        }

    private int getPivot( int[] data ){
        int[] highLow = new int[0];

            System.out.println("getPivot [" + data.length + "] " + toStringArray(data));
            highLow = new int[] { data[0],data[data.length - 1] };

        if( data.length >= 3){
            sort(new int[]{data[r.nextInt(2)],
                           data[r.nextInt(2)],
                           data[r.nextInt(2)]});
        }
        return highLow[ 1 ];
    }

    private String toStringArray(int[] data){
        StringBuilder sb = new StringBuilder();
        for( int i = 0 ; i < data.length ; i ++ ){
            sb.append( data[i] + " ");
        }
        return sb.toString();
    }
    
    public static void main( String... s){
        KThLargestSelection l = new KThLargestSelection();
        System.out.println( l.findKThLargest(a1, 1));
    }
}

Hackerrank

I know it is embarassing to post code like this without asymptotic analysis. After taking a strenuous 10 week Machine learning course I am again coding java. This is the Utopia problem which can be solved in one line.

package com.hackerrank;

import java.io.*;
import java.util.ArrayList;


public class Solution {

    private int noOfTestCases;

    private ArrayList<Integer> tests = new ArrayList<>();

    OutputStream outputStream = System.out;
    PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));

    protected void parseStdin(String[] data){

        int test = Integer.parseInt( data[0] );
        assert( test >= 1 && test <= 10);
        noOfTestCases = test;
            for( int i = 1 ; i < data.length ; i ++ ){
                int d = Integer.parseInt( data[i] );
                assert( d >= 0 && d <= 60);
                tests.add( d );
            }
        assert( tests.size() == noOfTestCases );
    }


    public ArrayList<String>  getInput(BufferedReader br) throws IOException {
        String line = null;
        ArrayList<String> arguments = new ArrayList<>();
        while( (line = br.readLine()) != null ){
            arguments.add(line);
        }
        br.close();
        return arguments;
    }

    public static void main( String... argv ) throws IOException {

        Solution utopia = new Solution();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<String> arguments = utopia.getInput( br );
        utopia.parseStdin( arguments.toArray(new String[arguments.size()]));
        utopia.test();


    }

    protected void test() {
        assert( 0 != noOfTestCases );
        assert( tests.size() == noOfTestCases );
        for( Integer test : tests)   {
            if( test != 0 ){
               if(test % 2  == 0){
                   growEvenly(test);
               }else{
                   growOddly(test);

               }
            }else{
                pw.println(1);
            }
        }
        pw.close();
    }

    private void growOddly(int test) {
        int odd = 1;
        if(test == 1 ){
            pw.println(test + 1);
        }else{
            for(int j = 0,k = test - 1 ; j < k; j = j + 2 ){
                odd = odd + odd + 1;
            }
            pw.println(odd * 2); pw.flush();
        }

    }

    private void growEvenly(int test) {
        int even = 1;
        for(int j = 0,k = test / 2 ; j < k ; j ++){
            even = even * 2 + 1;

        }
        pw.println(even);  pw.flush();
    }
}

Easymock

I have to expect 4 calls to readLine to accomodate null.

package com.hackerrank;

import org.junit.Assert;
import org.junit.*;

import java.io.BufferedReader;
import java.io.IOException;

import static org.easymock.EasyMock.createMock;
import static org.easymock.EasyMock.expect;
import static org.easymock.EasyMock.replay;

public class UtopiaTest {

    String[] argv;

    Solution solution;

    @Before
    public void sendInput() throws IOException {
        BufferedReader mockInputStream = createMock(BufferedReader.class);
        expect(mockInputStream.readLine()).andReturn(String.valueOf(2));
        expect(mockInputStream.readLine()).andReturn(String.valueOf(0));
        expect(mockInputStream.readLine()).andReturn(String.valueOf(1));
        expect(mockInputStream.readLine()).andReturn(null);
        replay(mockInputStream);
        solution = new Solution();
        argv = solution.getInput(mockInputStream).toArray(new String[3]);
        Assert.assertTrue(argv.length == 3);
    }

    @Test
    public void parse(){
        solution = new Solution();
        solution.parseStdin( argv );
    }

    @Test
    public void test(){
        solution = new Solution();
        solution.parseStdin( argv );
        solution.test();
    }
}

Reactive application

I really cannot believe that the firms in Chennai do not have any need for newer technology. On the one hand requirements are clear about scalability, resilience etc. On the other hand the developers do not show interest in new ideas. We had a requirement to notify users when reports are generated in the background thread.

Why don’t we read books and learn to use newer ideas ?

Play has an event handling mechanism that publishes events that refresh the browser with new data.

When I submit new data in the browser on the right, it shows up immediately in the other browser.

Events