Saturday, January 2, 2016

Summary of Interesting Posts

Here is the summary of some of the interesting posts:

Data Structure Implementations
Stack Implementation in Java (here)
Binary Search Tree implementation in Java (here)
AVL BST Implementation in Java (here)

Java Interesting Posts
A very interesting problem related to Java Concurrency (here)
Computing execution time using CountDownLatch and CyclicBarrier (here)
Is multithreading really worth it (here)
How CAS (Compare And Swap) in Java 8 works? (here)
Lock, ReentrantLock, ReentrantReadWriteLock and StampedLock in Java (here)
ExecutorService vs ExecutorCompletionService in Java (here)
Writing custom spliterator in Java 8 (here)

Java Interview Questions
Core Java Interview Questions (Part OnePart TwoTough Ones)

Java Basics
Abstract class vs Interface in Java 8 (here)
What are nested classes and why do we need them in Java 8 (here)
Default methods in Java 8 (here)
Volatile: Atomicity, Visibility and Ordering (here)
CyclicBarrier and its internal implementation in Java (here)
Why and how to use Phaser in Java? (here)
Overview of Enum in Java (here)

Flex Interesting Posts
Designing and developing Stock Ticker application in Flex (Part OneTwo and Three)
Understanding Spark Button Source Code
How can we remove binding in Flex?
How dictionary works in Flex?
Array, ArrayList, ListCollectionView and ArrayCollection
Problem with ObjectUtil's copy() method
How can we remove Binding on Object in Flex?
BlazeDS, LCDS and Flex-Java Integration
BlazeDS Scaling Issues
How to get time taken by the application to load in Flex?
Digital Clock: Custom Component
How dictionary works in Flex
Why to avoid binding if possible?

Flex Interview Questions
Flex Interview Questions (Good, Tough Ones)
Binding (Part One, Two and Three)
Events (Part One and Two)
Investment Bank Flex Interview Questions
Parsley Framework (Part One and Two)

Puzzles
Tough Logical Puzzles

Algorithms
Partition of a Number
Intersection of two linked lists in Y shape

Books
Good Java and Flex Books

Sunday, June 14, 2015

Stack Implementation in Java

Stack is a LIFO (Last In First Out) data structure and supports various operations as specified by the interface below:
public interface IStack<T> {
    public boolean push(T value);
    public T pop();
    public void clear();
    public boolean contains(T value);
    public int size();
}

The Stack can be implemented using an Array or a LinkedList. The Array implementation will be having an underlying array which will be re-sized accordingly. The source code is pretty straight forward and does not need much explanation.
public class ArrayStack<T> implements IStack<T> {
 private static final int MINIMUM_SIZE = 10;
 private T[] array = (T[]) new Object[MINIMUM_SIZE];
 private int size = 0;

 @Override
 public boolean push(T value) {
  int stackSize = this.size;
  if (stackSize >= array.length) {
   array = Arrays.copyOf(array, (stackSize + (stackSize>>1)));
  }
  array[size++] = value;
  return true;
 }

 @Override
 public T pop() {
  if (size <= 0) return null;
  T t = array[--size];
  array[size] = null;
  int stackShrinkSIze = size;
  if (size >= MINIMUM_SIZE && size < (stackShrinkSIze + (stackShrinkSIze<<1))) {
   System.arraycopy(array, 0, array, 0, size);
  }
  return t;
 }
 @Override
 public void clear() {
  size = 0;
 }
 
 @Override
 public boolean contains(T value) {
  for (int i = 0; i < size; i++) {
     T item = array[i];
     if (item.equals(value))
    return true;
  }
  return false;
 }
 @Override
 public int size() {
  return size;
 }
}

Similarly we can make use of LinkedList to implement Stack in Java.
public class LinkedStack<T> implements IStack<T> {
 private Node<T> top = null;
 private int size = 0;

 public LinkedStack() {
  top = null;
  size = 0;
 }
 @Override
 public boolean push(T value) {
  return push(new Node<T>(value));
 }
 private boolean push(Node<T> node) {
  if (top == null) { 
   top = node;
  } else {
   Node<T> oldTop = top;
   top = node;
   top.below = oldTop;
   oldTop.above = top;
  }
  size++;
  return true;
 }
 @Override
 public T pop() {
  if (top==null) return null;

  Node<T> nodeToRemove = top;
  top = nodeToRemove.below;
  if (top != null) top.above = null;

  T value = nodeToRemove.value;
  size--;
  return value;
 }
 @Override
 public void clear() {
  top = null;
  size = 0;
 }
 @Override
 public boolean contains(T value) {
  if (top == null) return false;
  Node<T> node = top;
  while (node != null) {
   if (node.value.equals(value)) return true;
   node = node.below;
  }
  return false;
 }

 @Override
 public int size() {
  return size;
 }
}

On a side note we have a class named Stack in Java as well but it usage is deprecated. That's all. I hope you liked the post!

Saturday, June 13, 2015

AVL Binary Search Tree Implementation in Java

AVL (Adelson-Velsky and Landis) is an example of self-balanced Binary Search Tree. It has the same basic operations as that of a regular BST but modifications are followed by zero or more tree rotation operations. Every node also stores balance factor which is corrected after insertion or deletion. If the recomputed balance factor remains in the range from -1 to +1 then only corrections of the balance factor is required and no rotations are necessary. But if the recomputed balance factor becomes less than -1 or greater than +1 the subtree rooted at this node is unbalanced, and a rotation is needed. The AVLNode class (extends Node from BinarySearchTree class) can be declared like:
public static class AVLNode<T extends Comparable<T>> extends Node<T> {
    protected int height = 1;
    protected AVLNode(Node<T> parent, T value) {
        super(parent, value);
    }

    protected boolean isLeaf() {
        return ((getLeft() == null) && (getRight() == null));
    }

    protected void updateHeight() {
        int lesserHeight = 0;
        int greaterHeight = 0;
        if (getLeft() != null) {
            AVLNode<T> lesserAVLNode = (AVLNode<T>) getLeft();
            lesserHeight = lesserAVLNode.height;
        }
        if (getRight() != null) {
            AVLNode<T> greaterAVLNode = (AVLNode<T>) getRight();
            greaterHeight = greaterAVLNode.height;
        }
        if (lesserHeight > greaterHeight) {
            height = lesserHeight + 1;
        } else {
            height = greaterHeight + 1;
        }
    }

    protected int getBalanceFactor() {
        int lesserHeight = 0;
        int greaterHeight = 0;
        if (getLeft() != null) {
            AVLNode<T> lesserAVLNode = (AVLNode<T>) getLeft();
            lesserHeight = lesserAVLNode.height;
        }
        if (getRight() != null) {
            AVLNode<T> greaterAVLNode = (AVLNode<T>) getRight();
            greaterHeight = greaterAVLNode.height;
        }
        return greaterHeight - lesserHeight;
    }

    @Override
    public String toString() {
        return "value=" + getData() + " height=" + height + " parent=" + ((getParent() != null) ? getParent().getData() : "NULL")
                    + " left=" + ((getLeft() != null) ? getLeft().getData() : "NULL") + " right="
                    + ((getRight() != null) ? getRight().getData() : "NULL");
    }
}

The AVLTree class can be declared like:
public class AVLTree<T extends Comparable<T>> extends RotatableBinarySearchTree<T> {
   public AVLTree() { }
}

We need to re-balance after insertion and deletion. Consider the insertion method first
@Override
protected Node<T> insertValue(T id) {
        Node<T> returnedNode = super.insertValue(id);
 AVLNode<T> insertedNode = (AVLNode<T>) returnedNode;
 while (insertedNode != null) {
  insertedNode.updateHeight();
  balanceAfterInsert(insertedNode);
  insertedNode = (AVLNode<T>) insertedNode.getParent();
 }
 return returnedNode;
}
private enum RotationSequence {
        LEFT_LEFT, LEFT_RIGHT, RIGHT_LEFT, RIGHT_RIGHT
};
private void balanceAfterInsert(AVLNode<T> node) {
 int balanceFactor = node.getBalanceFactor();
 
 if (balanceFactor > 1 || balanceFactor < -1) {
  AVLNode<T> parent = null;
  AVLNode<T> child = null;
  RotationSequence rotation = null;
  
  if (balanceFactor < 0) {
   parent = (AVLNode<T>) node.getLeft();
   balanceFactor = parent.getBalanceFactor();
   if (balanceFactor < 0) {
    child = (AVLNode<T>) parent.getLeft();
    rotation = RotationSequence.LEFT_LEFT;
   } else {
    child = (AVLNode<T>) parent.getRight();
    rotation = RotationSequence.LEFT_RIGHT;
   }
  } else {
   parent = (AVLNode<T>) node.getRight();
   balanceFactor = parent.getBalanceFactor();
   if (balanceFactor < 0) {
    child = (AVLNode<T>) parent.getLeft();
    rotation = RotationSequence.RIGHT_LEFT;
   } else {
    child = (AVLNode<T>) parent.getRight();
    rotation = RotationSequence.RIGHT_RIGHT;
   }
  }

  if (rotation == RotationSequence.LEFT_RIGHT) {
   // Left-Right (Left rotation, right rotation)
   rotateLeft(parent);
   rotateRight(node);
  } else if (rotation == RotationSequence.RIGHT_LEFT) {
   // Right-Left (Right rotation, left rotation)
   rotateRight(parent);
   rotateLeft(node);
  } else if (rotation == RotationSequence.LEFT_LEFT) {
   // Left-Left (Right rotation)
   rotateRight(node);
  } else {
   // Right-Right (Left rotation)
   rotateLeft(node);
  }

  node.updateHeight(); // New child node
  child.updateHeight(); // New child node
  parent.updateHeight(); // New Parent node
 }
}

The deletion will be similar and the process is: find the node in tree, find its replacement and replace the node and balance it accordingly.
@Override
protected Node<T> deleteValue(T value) {
 // Find node to remove
 Node<T> nodeToRemoved = this.searchAndGetNode(value);
 if (nodeToRemoved != null) {
  // Find the replacement node
  Node<T> replacementNode = this.getReplacementNode(nodeToRemoved);

  // Find the parent of the replacement node to re-factor the
  // height/balance of the tree
  AVLNode<T> nodeToRefactor = null;
  if (replacementNode != null)
   nodeToRefactor = (AVLNode<T>) replacementNode.getParent();
  if (nodeToRefactor == null)
   nodeToRefactor = (AVLNode<T>) nodeToRemoved.getParent();
  if (nodeToRefactor != null && nodeToRefactor.equals(nodeToRemoved))
   nodeToRefactor = (AVLNode<T>) replacementNode;

  // Replace the node
  deleteAndReplaceNode(nodeToRemoved, replacementNode);

  // Re-balance the tree all the way up the tree
  if (nodeToRefactor != null) {
   while (nodeToRefactor != null) {
    nodeToRefactor.updateHeight();
    balanceAfterDelete(nodeToRefactor);
    nodeToRefactor = (AVLNode<T>) nodeToRefactor.getParent();
   }
  }
 }
 return nodeToRemoved;
}

private void balanceAfterDelete(AVLNode<T> node) {
 int balanceFactor = node.getBalanceFactor();
 if (balanceFactor == -2 || balanceFactor == 2) {
  if (balanceFactor == -2) {
   AVLNode<T> ll = (AVLNode<T>) node.getLeft().getLeft();
   int lesser = (ll != null) ? ll.height : 0;
   AVLNode<T> lr = (AVLNode<T>) node.getLeft().getRight();
   int greater = (lr != null) ? lr.height : 0;
   if (lesser >= greater) {
    rotateRight(node);
    node.updateHeight();
    if (node.getParent() != null)
     ((AVLNode<T>) node.getParent()).updateHeight();
   } else {
    rotateLeft(node.getLeft());
    rotateRight(node);

    AVLNode<T> p = (AVLNode<T>) node.getParent();
    if (p.getLeft() != null)
     ((AVLNode<T>) p.getLeft()).updateHeight();
    if (p.getRight() != null)
     ((AVLNode<T>) p.getRight()).updateHeight();
    p.updateHeight();
   }
  } else if (balanceFactor == 2) {
   AVLNode<T> rr = (AVLNode<T>) node.getRight().getRight();
   int greater = (rr != null) ? rr.height : 0;
   AVLNode<T> rl = (AVLNode<T>) node.getRight().getLeft();
   int lesser = (rl != null) ? rl.height : 0;
   if (greater >= lesser) {
    rotateLeft(node);
    node.updateHeight();
    if (node.getParent() != null)
     ((AVLNode<T>) node.getParent()).updateHeight();
   } else {
    rotateRight(node.getRight());
    rotateLeft(node);

    AVLNode<T> p = (AVLNode<T>) node.getParent();
    if (p.getLeft() != null)
     ((AVLNode<T>) p.getLeft()).updateHeight();
    if (p.getRight() != null)
     ((AVLNode<T>) p.getRight()).updateHeight();
    p.updateHeight();
   }
  }
 }
}

Remaining methods are inherited from BinarySearchTree class. So the major changes are in insertion/deletion along with re-balancing efforts. But considering the benefits it provide it is worth it.

Friday, June 12, 2015

Self-balancing Binary Search Tree

Before we go any further lets see what will happen  if we insert sorted numbers into a regular Binary Search Tree (BST). Suppose we enter 10,20,30,40 and 50 in the same order. Then what we will get is a highly unbalanced BST:

Actually it has become a linked list now. You can read more about skewed BSTs here. As it hurts the performance badly there is always a need for balance Binary Search Tree.

A self balanced binary search tree is the one that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. An example is AVL (Adelson-Velsky and Landis) Binary Search Tree which makes use of rotations to keep itself balanced.

As per wikipedia: "In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations."

The wi-ki page also demonstrates how rotation works:


AVL tree is generally compared with Red-Black tree as both have certain common properties and both support the concept of rotation. They also support same operations and take O(log n) time for basic operations (For purists they actually take O(lg n) time but base does not matter much in this case as they will show same pattern). For look up intensive applications AVL trees are supposed to be faster than Red-Black trees but both are height balanced.

We have already covered implementation of Binary Search Tree in previous article. Here I will create an abstract class that will have methods for rotation as well.
abstract public class RotatableBinarySearchTree<T extends Comparable<T>> extends BinarySearchTree<T> {
    protected enum Position {
       LEFT, RIGHT
    };
    public RotatableBinarySearchTree() { }
}

The methods that will perform rotation are: rotateLeft and rotateRight. These are shown below:
protected void rotateLeft(Node<T> node) {
 Position parentPosition = null;
 Node<T> parent = node.getParent();
 if (parent != null) {
  if (node.equals(parent.getLeft())) {
   // Lesser
   parentPosition = Position.LEFT;
  } else {
   // Greater
   parentPosition = Position.RIGHT;
  }
 }

 Node<T> greater = node.getRight();
 node.setRight(null);
 Node<T> lesser = greater.getLeft();

 greater.setLeft(node);
 node.setParent(greater);

 node.setRight(lesser);
 if (lesser != null)
  lesser.setParent(node);

 if (parentPosition != null) {
  if (parentPosition == Position.LEFT) {
   parent.setLeft(greater);
  } else {
   parent.setRight(greater);
  }
  greater.setParent(parent);
 } else {
  root = greater;
  greater.setParent(null);
 }
}

protected void rotateRight(Node<T> node) {
 Position parentPosition = null;
 Node<T> parent = node.getParent();
 if (parent != null) {
  if (node.equals(parent.getLeft())) {
   // Lesser
   parentPosition = Position.LEFT;
  } else {
   // Greater
   parentPosition = Position.RIGHT;
  }
 }

 Node<T> lesser = node.getLeft();
 node.setLeft(null);
 Node<T> greater = lesser.getRight();

 lesser.setRight(node);
 node.setParent(lesser);

 node.setLeft(greater);
 if (greater != null)
  greater.setParent(node);

 if (parentPosition != null) {
  if (parentPosition == Position.LEFT) {
   parent.setLeft(lesser);
  } else {
   parent.setRight(lesser);
  }
  lesser.setParent(parent);
 } else {
  root = lesser;
  lesser.setParent(null);
 }
}

This abstract class provides method for rotation and will be extended by the implementation of AVL and Red-Black Trees when we will discuss them.

Binary Search Tree implementation in Java

Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. This post is not about the basics of BST, in case you are interested please check this pdf.

I will first declare an interface ITree which we assume all our tree implementations to implement:
public interface Tree<T> {
    public boolean insert(T value);
    public T delete(T value);
    public void clear();
    public boolean contains(T value);
    public int size();
}

This interface can be implemented by the class as follows:
public class BinarySearchTree<T extends Comparable<T>> implements Tree<T> {
    protected Node<T> root = null;
    protected int size = 0;
    public BinarySearchTree() { }
}

We have used generics and we also want elements to be mutually comparable. We will first provide implementation of insert method as:
@Override
public boolean insert(T value) {
     Node<T> nodeAdded = this.insertValue(value);
     return (nodeAdded != null);
}
protected Node<T> insertValue(T value) {
     Node<T> newNode = getNewNode(value);

     // If root is null, assign
     if (root == null) {
       root = newNode;
       size++;
       return newNode;
     }

     Node<T> currentNode = root;
     while (currentNode != null) {
        if (newNode.getData().compareTo(currentNode.getData()) <= 0) { // Less than or equal to goes left
           if(currentNode.getLeft() == null) {
              insertNodeToLeft(currentNode, newNode);
              break;
           }
           currentNode = currentNode.getLeft();
        } else { // Greater than goes right
           if (currentNode.getRight() == null) {
              insertNodeToRight(currentNode, newNode);
              break;
           }
          currentNode = currentNode.getRight();
        }
     }
     return newNode;
}

The insert method will insert the node in left or right branch based on its value. The deletion part is slightly tricky. The process of deletion is as follows:
  1. First locate the node that needs to be deleted.
  2. Then find the replacement node for this node. We can select from left or right subtree and we do not want to select from one subtree all the time as it can lead to skewed tree.
  3. Then we need to delete this node and replace it with its replacement found in step 2.
This is performed by the following code:
        @Override
 public T delete(T value) {
    Node<T> nodeToRemove = this.deleteValue(value);
    return ((nodeToRemove!=null)?nodeToRemove.getData():null);
 }
 
 protected Node<T> deleteValue(T value) {
    Node<T> nodeToRemoved = this.searchAndGetNode(value);
    if (nodeToRemoved != null) nodeToRemoved = deleteNode(nodeToRemoved);
    return nodeToRemoved;
 }

 protected Node<T> searchAndGetNode(T value) {
    Node<T> currentNode = root;
    while (currentNode != null && currentNode.getData() != null) {
       int valueComparison = value.compareTo(currentNode.getData());
       if (valueComparison == 0) {
         return currentNode;
       } else if (valueComparison < 0) {
         currentNode = currentNode.getLeft();
       } else {
         currentNode = currentNode.getRight();
       }
    }
  return null;
 }

 protected Node<T> deleteNode(Node<T> nodeToRemoved) {
    if (nodeToRemoved != null) {
      Node<T> replacementNode = this.getReplacementNode(nodeToRemoved);
      deleteAndReplaceNode(nodeToRemoved, replacementNode);
    }
  return nodeToRemoved;
 }

 protected Node<T> getReplacementNode(Node<T> nodeToRemoved) {
    Node<T> replacement = null;
    if (nodeToRemoved.getLeft() != null && nodeToRemoved.getRight() == null) { // Using the less subtree
      replacement = nodeToRemoved.getLeft();
    } else if (nodeToRemoved.getRight() != null && nodeToRemoved.getLeft() == null) {
      // Using the greater subtree (there is no lesser subtree)
      replacement = nodeToRemoved.getRight();
    } else if (nodeToRemoved.getRight() != null && nodeToRemoved.getLeft() != null) {
      // Two children add some randomness to deletions, so we don't always use the greatest/least on deletion
      if (toggleReplacementNodeSelection) {
         replacement = this.getLargestNodeInSubTree(nodeToRemoved.getLeft());
         if (replacement == null)
           replacement = nodeToRemoved.getLeft();
         } else {
           replacement = this.getSmallestNodeInSubTree(nodeToRemoved.getRight());
           if (replacement == null)
             replacement = nodeToRemoved.getRight();
         }
         toggleReplacementNodeSelection = !toggleReplacementNodeSelection;
   }
   return replacement;
 }

 protected void deleteAndReplaceNode(Node<T> nodeToDelete, Node<T> replacementNode) {
    if (replacementNode != null) {
      // Record left and right child of replacementNode for later use
      Node<T> leftChildOfReplacementNode = replacementNode.getLeft();
      Node<T> rightChildOfReplacementNode = replacementNode.getRight();

      // For left and right children of nodeToDelete, new parent is replacementNode
      Node<T> leftChildOfNodeToDelete = nodeToDelete.getLeft();
      if (leftChildOfNodeToDelete != null && !leftChildOfNodeToDelete.equals(replacementNode)) {
         replacementNode.setLeft(leftChildOfNodeToDelete);
         leftChildOfNodeToDelete.setParent(replacementNode);
      }
   
      Node<T> rightChildOfNodeToDelete = nodeToDelete.getRight();
      if (rightChildOfNodeToDelete != null && !rightChildOfNodeToDelete.equals(replacementNode)) {
         replacementNode.setRight(rightChildOfNodeToDelete);
         rightChildOfNodeToDelete.setParent(replacementNode);
      }

      // Update the link of parent of replacementNode as well. For the parent of replacementNode kids of replacementNode are its new kids. In short grand-kids are kids now.
      Node<T> parentOfReplacementNode = replacementNode.parent;
      if (parentOfReplacementNode != null && !parentOfReplacementNode.equals(nodeToDelete)) {
         Node<T> leftChildOfParentOfReplacementNode = parentOfReplacementNode.getLeft();
         Node<T> rightChildOfParentOfReplacementNode = parentOfReplacementNode.getRight();

         // Check whether the replacementNode is left or right child of its parent.
         if (leftChildOfParentOfReplacementNode != null && leftChildOfParentOfReplacementNode.equals(replacementNode)) {
            parentOfReplacementNode.setLeft(rightChildOfReplacementNode);
            if (rightChildOfReplacementNode != null)
               rightChildOfReplacementNode.setParent(parentOfReplacementNode);
         } else if (rightChildOfParentOfReplacementNode != null && rightChildOfParentOfReplacementNode.equals(replacementNode)) {
            parentOfReplacementNode.setRight(leftChildOfReplacementNode);
            if (leftChildOfReplacementNode != null)
               leftChildOfReplacementNode.setParent(parentOfReplacementNode);
         }
       }
     } 

     // Update the link in the tree from the nodeToRemoved to the replacementNode
     Node<T> parentOfNodeToDelete = nodeToDelete.getParent();

     if (parentOfNodeToDelete == null) {
        // We are deleting root node. So replacing the root node.
        root = replacementNode;
        if (root != null) root.parent = null;
     } else if (parentOfNodeToDelete.getLeft() != null && (parentOfNodeToDelete.getLeft().getData().compareTo(nodeToDelete.getData()) == 0)) {
        parentOfNodeToDelete.setLeft(replacementNode);
        if (replacementNode != null) replacementNode.parent = parentOfNodeToDelete;
     } else if (parentOfNodeToDelete.getRight() != null && (parentOfNodeToDelete.getRight().getData().compareTo(nodeToDelete.getData()) == 0)) {
        parentOfNodeToDelete.setRight(replacementNode);
        if (replacementNode != null) replacementNode.parent = parentOfNodeToDelete;
     }
     size--;
 }

Now the remaining methods are relatively easy ones.
@Override
 public void clear() {
  root = null;
  size = 0;
 }
 @Override
 public boolean contains(T value) {
  Node<T> node = searchAndGetNode(value);
  return (node != null);
 }
 @Override
 public int size() {
  return size;
 }

This completes the implementation of BST in Java.

Friday, May 1, 2015

Implementing Binary Search Tree in Java

I believe we all know what is a Binary Search Tree (also called ordered tree). I will explain the step-by-step implementation of BST in Java. First of all we will need a node class which will store data/info to be stored in node, parent of node, left and right child. We can also create a static nested class for that as well because this class will not be used by any other class. I will go with a separate class as it will keep the code clean and will also be easy to explain.
public class Node<T extends Comparable<T>> {
    private T data = null;
    private Node<T> left;
    private Node<T> right;
    private Node<T> parent;

    public Node(Node<T> parent, T data) {
        this.parent = parent;
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getLeft() {
        return left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
    }

    public Node<T> getRight() {
        return right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
    }

    public Node<T> getParent() {
        return parent;
    }

    public void setParent(Node<T> parent) {
        this.parent = parent;
    }

    @Override
    public String toString() {
        String nodeInformation = "Data: " + data + " Parent: " + ( (parent != null) ? parent.data : "NULL") + " Left: " + ((left != null) ? left.data : "NULL") + " Right: " + ((right != null) ? right.data : "NULL");
        return super.toString();
    }
}

We want to be able to store any thing inside node (String, Integer and even our own class objects) and for that I would have used generics, also we want data stored in Node class comparable so we have used:
Node<T extends Comparable<T>&gt;

Next we will declare an interface ITree which will define the methods to be implemented by BST later on:
public interface ITree<T> {
    public boolean insert(T value);
    public T delete(T value);
    public void clear();
    public boolean contains(T value);
    public int size();
    public boolean validate();
    public java.util.Collection<T> toCollection();
}

Now we will move ahead with a class named BinarySearchTree which will implement this interface and body will look like:
public class BinarySearchTree<T extends Comparable<T>> implements ITree{
    protected Node<T> root;
    protected int size = 0;

    @Override
    public boolean insert(T value) {
        return false;
    }

    @Override
    public T delete(T value) {
        return null;
    }

    @Override
    public void clear() {

    }

    @Override
    public boolean contains(T value) {
        return false;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public boolean validate() {
        return false;
    }

    @Override
    public Collection toCollection() {
        return null;
    }
}

We have also declared two protected fields (as we want them available in derived classes as well) root and size of the tree. Next task is to provide the method implementations. We will consider insert first and will write two methods to insert a node to left or right of a parent.
private void insertNodeToRight(Node<T> parent, Node<T> child) {
    parent.setRight(child);
    child.setParent(parent);
    size++;
}

private void insertNodeToLeft(Node<T> parent, Node<T> child) {
    parent.setLeft(child);
    child.setParent(parent);
    size++;
}

Now we will write a method which will do the actual insertion of node to the tree. It will traverse through the tree to figure out place where a node can be inserted.
private Node<T> createNewNode(T value) {
 return (creator != null) ? (creator.createNewNode(null, value)) : (new Node<T>(null, value));
}
protected Node<T> insertValue(T value) {
 Node<T> newNode = createNewNode(value);

 // If root is null, assign
 if (root == null) {
  root = newNode;
  size++;
  return newNode;
 }

 Node<T> currentNode = root;
 while (currentNode != null) {
  if (newNode.getData().compareTo(currentNode.getData()) <= 0) { // Less than or equal to goes left
   if(currentNode.getLeft() == null) {
    insertNodeToLeft(currentNode, newNode);
    break;
   }
   currentNode = currentNode.getLeft();
  } else {          // Greater than goes right
   if (currentNode.getRight() == null) {
    insertNodeToRight(currentNode, newNode);
    break;
   }
   currentNode = currentNode.getRight();
  }
 }

 return newNode;
}

Now this method will be actually called by our public insertion method as:
public boolean insert(T value) {
 Node<T> nodeAdded = this.insertValue(value);
 return (nodeAdded != null);
}

This completes the insertion functionality. Next we will work upon search functionality where it will search for a value in the tree. If the value is less than the value at current node it will go left else it will go right (assumption is we don't have duplicate).
public boolean contains(T value) {
 Node<T> node = searchAndGetNode(value);
 return (node != null);
}
protected Node<T> searchAndGetNode(T value) {
 Node<T> currentNode = root;
 while (currentNode != null && currentNode.getData() != null) {
  int valueComparison = value.compareTo(currentNode.getData());
  if (valueComparison == 0) {
   return currentNode;
  } else if (valueComparison < 0) {
   currentNode = currentNode.getLeft();
  } else {
   currentNode = currentNode.getRight();
  }
 }
 return null;
}

Next we can work on deletion of a node but before that we need to figure out which node will replace it. We don't have any concern if the node to be deleted has zero or one children, but in case it has both left and right children then we need to design our code carefully. In case node has both children we can delete the node and replace it with either rightmost (largest) child from left sub tree or leftmost (smallest) child from right sub tree. If we keep on using only one of these strategy then it can lead to skewed tree quickly.
private boolean toggleReplacementNodeSelection = true;
protected Node<T> getReplacementNode(Node<T> nodeToRemoved) {
 Node<T> replacement = null;
 if (nodeToRemoved.getLeft() != null && nodeToRemoved.getRight() == null) {
  // Using the less subtree
  replacement = nodeToRemoved.getLeft();
 } else if (nodeToRemoved.getRight() != null && nodeToRemoved.getLeft() == null) {
  // Using the greater subtree (there is no lesser subtree, no
  // refactoring)
  replacement = nodeToRemoved.getRight();
 } else if (nodeToRemoved.getRight() != null && nodeToRemoved.getLeft() != null) {
  // Two children
  // Add some randomness to deletions, so we don't always use the
  // greatest/least on deletion
  if (toggleReplacementNodeSelection) {
   replacement = this.getLargestNodeInSubTree(nodeToRemoved.getLeft());
   if (replacement == null)
    replacement = nodeToRemoved.getLeft();
  } else {
   replacement = this.getSmallestNodeInSubTree(nodeToRemoved.getRight());
   if (replacement == null)
    replacement = nodeToRemoved.getRight();
  }
  toggleReplacementNodeSelection = !toggleReplacementNodeSelection;
 }
 return replacement;
}

Now after getting the replacement node we need to perform deletion. We need to update children of node to be deleted with new parent, update left and right child of replacement node and also update its parent. The method below does that:
protected void deleteAndReplaceNode(Node<T> nodeToDelete, Node<T> replacementNode) {
 if (replacementNode != null) {

  // Record left and right child of replacementNode for later use
  Node<T> leftChildOfReplacementNode = replacementNode.getLeft();
  Node<T> rightChildOfReplacementNode = replacementNode.getRight();

  // For left and right children of nodeToDelete, new parent is replacementNode
  Node<T> leftChildOfNodeToDelete = nodeToDelete.getLeft();
  if (leftChildOfNodeToDelete != null && !leftChildOfNodeToDelete.equals(replacementNode)) {
   replacementNode.setLeft(leftChildOfNodeToDelete);
   leftChildOfNodeToDelete.setParent(replacementNode);
  }
  Node<T> rightChildOfNodeToDelete = nodeToDelete.getRight();
  if (rightChildOfNodeToDelete != null && !rightChildOfNodeToDelete.equals(replacementNode)) {
   replacementNode.setRight(rightChildOfNodeToDelete);
   rightChildOfNodeToDelete.setParent(replacementNode);
  }

  // Update the link of parent of replacementNode as well. For the parent of replacementNode kids of replacementNode are its new kids.
  // In short grand-kids are kids now.
  Node<T> parentOfReplacementNode = replacementNode.parent;
  if (parentOfReplacementNode != null && !parentOfReplacementNode.equals(nodeToDelete)) {
   Node<T> leftChildOfParentOfReplacementNode = parentOfReplacementNode.getLeft();
   Node<T> rightChildOfParentOfReplacementNode = parentOfReplacementNode.getRight();

   // Check whether the replacementNode is left or right child of its parent.
   if (leftChildOfParentOfReplacementNode != null && leftChildOfParentOfReplacementNode.equals(replacementNode)) {
    parentOfReplacementNode.setLeft(rightChildOfReplacementNode);
    if (rightChildOfReplacementNode != null)
     rightChildOfReplacementNode.setParent(parentOfReplacementNode);
   } else if (rightChildOfParentOfReplacementNode != null && rightChildOfParentOfReplacementNode.equals(replacementNode)) {
    parentOfReplacementNode.setRight(leftChildOfReplacementNode);
    if (leftChildOfReplacementNode != null)
     leftChildOfReplacementNode.setParent(parentOfReplacementNode);
   }
  }
 }

 // Update the link in the tree from the nodeToRemoved to the replacementNode
 Node<T> parentOfNodeToDelete = nodeToDelete.getParent();

 if (parentOfNodeToDelete == null) {
  // We are deleting root node. So replacing the root node.
  root = replacementNode;
  if (root != null) root.parent = null;
 } else if (parentOfNodeToDelete.getLeft() != null && (parentOfNodeToDelete.getLeft().getData().compareTo(nodeToDelete.getData()) == 0)) {
  parentOfNodeToDelete.setLeft(replacementNode);
  if (replacementNode != null) replacementNode.parent = parentOfNodeToDelete;
 } else if (parentOfNodeToDelete.getRight() != null && (parentOfNodeToDelete.getRight().getData().compareTo(nodeToDelete.getData()) == 0)) {
  parentOfNodeToDelete.setRight(replacementNode);
  if (replacementNode != null) replacementNode.parent = parentOfNodeToDelete;
 }
 size--;
}

Now this can be called by the public method as:
public T delete(T value) {
 Node<T> nodeToRemove = this.deleteValue(value);
 return ((nodeToRemove!=null)?nodeToRemove.getData():null);
}
protected Node<T> deleteValue(T value) {
 Node<T> nodeToRemoved = this.searchAndGetNode(value);
 if (nodeToRemoved != null) nodeToRemoved = deleteNode(nodeToRemoved);
 return nodeToRemoved;
}

Now similarly other methods can also be written.




Saturday, April 18, 2015

Java Concurrency Problem: A Producer which produces N work items and waits for them to be over.

“With great power often comes great confusion.” ― Dan Allen, Seam in Action

Many times we encounter concurrency problems in Java where existing constructs need to be tweaked. Recently I wrote about one such problem where we wanted to accumulate results of multiple threads and these threads could write or update values randomly.

This time I am going to write about a problem where we will have one producer which will produce an N number of items (of course N is not known in advance) and then producer needs to wait for all those N items to be over. Before we move further I would like to stress again that what I am going to present here is oversimplified version of actual problem. I am not going to write complete code rather only those pieces that would make sense in context of this post.

Using ExecutorCompletionService
If you are not familiar then you need to have a look on this post which explains how ExecutorCompletionService differentiates from ExecutorService. My worker will doing some work and that's all.
public class WorkerThread implements Runnable {
    @Override
    public void run() {
        try {
            Thread.currentThread().sleep(1000);  // do some work
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

At first it seems that we can use this to submit jobs and get list of futures, and then later we can get results out of it. When we will be retrieving the results using take() producer will obviously block.
public class WorkProducerUsingECS implements Runnable{
    private final CompletionService service;
    private final List<Future<Integer>> listOfFutures;

    public WorkProducerUsingECS() {
        this.listOfFutures = new ArrayList<>();
        service = new ExecutorCompletionService(Executors.newFixedThreadPool(5));
    }

    @Override
    public void run() {
        produceRandomWorkers();
    }

    private void produceRandomWorkers() {
        Random random = new Random();
        int numberOfWorkers = random.nextInt(20) + 1;
        System.out.println("Workers count: " + numberOfWorkers);
        for (int i=0; i<numberOfWorkers; i++){
             listOfFutures.add(service.submit(new WorkerThread(),1));
        }
    }

    private void getResultAfterWorkIsOver() throws InterruptedException, ExecutionException {
        for(int i=0; i<listOfFutures.size(); i++) {
            Integer result = (Integer) service.take().get();
            System.out.println("Result: "  + result);
        }
    }
}

This can be called using the following code:
public static void main(String[] args) {
   WorkProducerUsingECS producer =  new WorkProducerUsingECS();
   Thread thread = new Thread(producer);
   thread.start();
}

Now the problem is once all the workers are done how can we signal the producer so that it can call getResultAfterWorkIsOver method.

Using CountDownLatch (CDL)
Using latch seems a good option but the problem is we don't know the actual number of worker threads in advance. If it were available we could have simply created a CDL and have producer thread wait (using await method) until all work was complete.

Lets give it a try. We will create a wrapper class WorkerTask on top of class which will take Runnable (to be executed) and an atomic reference to CDL as constructor parameter. An AtomicReference can be updated atomically.
public class WorkerTask implements Runnable {
    private final Runnable runnable;
    private AtomicReference<CountDownLatch> latchAtomicReference;

    public WorkerTask(Runnable runnable, AtomicReference<CountDownLatch> latchAtomicReference) {
        this.runnable = runnable;
        this.latchAtomicReference = latchAtomicReference;
    }

    @Override
    public void run(){
        runnable.run();
        while (latchAtomicReference.get() == null) {
            try {
                Thread.currentThread().sleep(1000L);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        latchAtomicReference.get().countDown();
    }
}

In case any worker-thread is over by the time CDL is not set, it will sleep for some time and again check whether it is set or not. If it is set then it will invoke countdown on it. The AtomicReference is used because this can be updated atomically and will not create unintended problems in multi-threaded code.

Another thing to note is I have called run() and not start() on the Runnable passed in constructor as I do not want to spawn a new thread. You can read more here and here. This can be used with producer as:
public class WorkProducerUsingCDL implements Runnable{
    private final AtomicReference<CountDownLatch> latchAtomicReference;

    public WorkProducerUsingCDL() {
        latchAtomicReference = new AtomicReference<>();
    }

    @Override
    public void run() {
        produceRandomWorkers();
    }

    private void produceRandomWorkers() {
        Random random = new Random();
        int numberOfWorkers = random.nextInt(20) + 1;
        System.out.println("Workers count: " + numberOfWorkers);
        for (int i=0; i<numberOfWorkers; i++){
            try {
                createWorkerTask().start();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        // Add some delay to simulate some processing
        try {
            Thread.currentThread().sleep(5000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        //By now all workers have been added. Some of them may be over and some may be processing.
        latchAtomicReference.set(new CountDownLatch(numberOfWorkers));

        // Now producer will wait for latch to be over.
        try {
            latchAtomicReference.get().await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        // Now all workers are definitely over.
        try {
            processAfterWorkIsOver();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }

    private Thread createWorkerTask() {
        WorkerTask workerTask = new WorkerTask(new WorkerThread(), latchAtomicReference);
        Thread thread = new Thread(workerTask);
        return  thread;
    }

    private void processAfterWorkIsOver() throws InterruptedException, ExecutionException {
        System.out.println("Work is over by all workers.");
    }

}

And we can verify this code as:
public static void main(String[] args) {
    WorkProducerUsingCDL producerUsingCDL = new WorkProducerUsingCDL();
    Thread thread = new Thread(producerUsingCDL);
    thread.start();
}

One thing to observe in this code is that the number of threads is unknown to us and it is possible that some of the threads have already near to completion by the time we create a CDL and set it in the AtomicReference of CDL. I have not used ExecutorService here knowingly in this example because that would have returned Future and when we invoke get on it, it will block the producer. Here also producer will be blocked but by the await method which is called on CDL in the AtomicReference.

This code should work and in my opinion not a neat version. One more point which is still not discussed is: the process is cyclic. It means every time a cycle starts producer will produce unknown number of threads and will wait for them to be completed. It seems we can also make use of CyclicBarrier to solve this problem. Think for a moment before going further. Can we solve it using CyclicBarrier?

Using Phaser
As we do not have Flexible CDL, there is one construct that will fit the problem and that is Phaser. To know about why and how to use Phaser check this post. We need to pass the phaser reference to worker as:
public class WorkerThread implements Runnable {
    private final Phaser phaser;

    public WorkerThread(Phaser phaser) {
        this.phaser = phaser;
    }

    @Override
    public void run() {
        try {
            Thread.currentThread().sleep(5000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("Work is over.");
        phaser.arrive();
    }
}

Once the work of worker is over it will call arrive method on phaser to notify that this particular worker is done with the work and has arrived on that particular phase. The phaser is a mix of CyclicBarrier and CountDownLatch and when one phase is over, it starts a new phase and the limit is Integer.MAX_VALUE. Once it reaches max value it rounds off to zero and starts again. The producer can be written as:
public class WorkProducerUsingPhaser implements Runnable{
    private final Phaser phaser;
    private final ExecutorService executorService;

    public WorkProducerUsingPhaser() {
        phaser = new Phaser();
        executorService = Executors.newFixedThreadPool(5);
    }

    @Override
    public void run() {
        produceRandomWorkers();
    }

    private void produceRandomWorkers() {
        Random random = new Random();
        int numberOfWorkers = random.nextInt(20) + 1;
        System.out.println("Workers count: " + numberOfWorkers);

        phaser.register();

        for (int i=0; i<numberOfWorkers; i++){
            phaser.register();
            executorService.submit(getWorker());
        }

        phaser.arriveAndAwaitAdvance();

        // Now all workers are definitely over.
        try {
            processAfterWorkIsOver();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }

    private Thread getWorker() {
        WorkerThread workerTask = new WorkerThread(phaser);
        Thread thread = new Thread(workerTask);
        return  thread;
    }

    private void processAfterWorkIsOver() throws InterruptedException, ExecutionException {
        System.out.println("Work is over by all workers.");
    }
}

Here I have used a thread pool of 5 (you can take any suitable number) and submit all worker threads to ExecutorService. The producer along with all workers is registered to Phaser and then it waits by calling arriveAndAwaitAdvance method. Once every worker is done it calls method arrive and when the last worker calls this method producer is notified and then producer can move ahead. A new phase will also start. This solution seems more clean and suits better.

That is all and I hope you liked it. Please drop your feedback in comments.