Binary Tree Traversal

Standard

I thought long before of writing this post after discussing the binary tree generation in reverse lexicographic order but unfortunately it got delayed. So lets not make any more delay in discussing binary tree traversal.

Following are the general way of traversing binary tree, which you can find in any data structure book:-

1) Preorder :-

sample recursive code:

preorder(node)
{
           if(node!=null)
           {
                visit(node);
                preorder(left(node));
                preorder(right(node));
           }
}

Non-recursive traversal:-

preorder(root)
{
            p=root;
            stack S;
            while(p is not null or S is not empty) 
            {
              if(p is not null)
              {
                    visit(p);
                    push(p,S);
                    if(left(p) is not null)
                            p=left(p);
                   else
                            p=right(p);
             }
             else
             {
                      do
                     {
                           q=S.pop();
                           if( S is not empty)
                                rtptr=right(item(S));
                           else
                                 rtptr=null
                     }while(S is not empty and q is rtptr);
                     p=rtptr;
           }

}

2) Inorder :-

inorder(node)
{
         if(node!=null)
         {
             inorder(left(node));
              visit(node);
             inorder(right(node));
        }
}

3) Postorder :-

postorder(node)
{
       if(node!=null)
       {
             postorder(left(node))
             postorder(right(node));
             visit(node);
        }
}

4) Level-wise binary tree traversal.

We can have some more traversal based on the way we traverse left and right child. But here all the traversal require some extra data structure like stack. Hence we will discuss some more tree traversal which are space effective.

Link Inversion Traversal

This is very space effective and beautiful algorithm. In which we assign 1 bit extra information which store  0 or 1.  Initially, all the node have 0. As we descend to the right, we tag that node as 1 and make the right pointer of the node point to parent, whose right subtree is to be traversed. And as we descend to the left, we tag that node as 0 and make the left pointer point to parent, whose left subtree is to be traversed. Once we finish the traversing the subtree, can look at the tag of the node and decide whether it was the left or right subtree of the parent whose traversal has just been finished, this way we traverse back up to root. While traversing, we should restore the tag and its pointers also.

This tree traversal does not require any additional data structure and it just need n extra bit to tag each node. Lets improve this also.

Robson Traversal

This is even more space effective than the “Link Inversion Traversal”, since it does not require even  n bits extra information. It uses the leave node to store the information, basically it connects all the leave node and use them as stack and hence we need an extra pointer to point to start or end of this stack and we call that pointer as stack and one more extra pointer we will call that top,which will point to the last (recent) traversed node whose right tree we are traversing and which have non null left subtree and stack pointer’s right will point to the next most recent and its left pointer will point to the next leave node who will store the similar information.

Here is the algorithm:-


If the node's left subtree is being traversed, then
        its left pointer is pointing to its predecessor, and its right pointer is undisturbed.

If the node's right subtree is being traversed, then
        if the node has a null left subtree, then
                its right pointer is pointing to its predecessor
        else
                its left pointer is pointing to its predecessor, and its right pointer is pointing   to the root of the node's left subtree.


Here is the java implementation of above discussed tree traversal:-

package edu.temple.pt.assignment;
/**
 * 
 * @author aakash
 *
 * @param  <  T  &rt;   
 */
public class Node <  T  &rt;    {

	/*
	 * taking one extra tag data for link inversion traversal, not needed in any other traversal.
	 */
	private int tag=0;
	public int getTag() {
		return tag;
	}
	public void setTag(int tag) {
		this.tag = tag;
	}


	private T data;
	private Node <  T  &rt;    lt=null;
	private Node <  T  &rt;    rt=null;
	public T getData() {
		return data;
	}
	public void setData(T data) {
		this.data = data;
	}
	public Node <  T  &rt;    getLt() {
		return lt;
	}
	public void setLt(Node <  T  &rt;    lt) {
		this.lt = lt;
	}
	public Node <  T  &rt;    getRt() {
		return rt;
	}
	public void setRt(Node <  T  &rt;    rt) {
		this.rt = rt;
	}
	
	public Node(T data) {
		this.data=data;
		this.tag=0;
		// TODO Auto-generated constructor stub
	}
	/**
	 * @param data
	 * @param lt
	 * @param rt
	 */
	public Node(T data, Node <  T  &rt;    lt, Node <  T  &rt;    rt) {
		super();
		this.data = data;
		this.lt = lt;
		this.rt = rt;
		this.tag=0;
	}
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((data == null) ? 0 : data.hashCode());
		result = prime * result + ((lt == null) ? 0 : lt.hashCode());
		result = prime * result + ((rt == null) ? 0 : rt.hashCode());
		return result;
	}
	@SuppressWarnings("unchecked")
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Node <  T  &rt;    other = (Node <  T  &rt;   ) obj;
		if (data == null) {
			if (other.data != null)
				return false;
		} else if (!data.equals(other.data))
			return false;
		if (lt == null) {
			if (other.lt != null)
				return false;
		} else if (!lt.equals(other.lt))
			return false;
		if (rt == null) {
			if (other.rt != null)
				return false;
		} else if (!rt.equals(other.rt))
			return false;
		return true;
	}
	@Override
	public String toString()
	{
		StringBuilder sbr=new StringBuilder();
		sbr.append("[");
		sbr.append("{data:").append(data.toString());
//		sbr.append(" tag:").append(tag);
		sbr.append("}");
		if(lt!=null)
			sbr.append(",{left:").append(lt.getData()).append("}");
		else
			sbr.append(",{left:").append(lt).append("}");
		if(rt!=null)
			sbr.append(",{right:").append(rt.getData()).append("}");
		else
			sbr.append(",{right:").append(rt).append("}");
		/*
		if(lt!=null)
			sbr.append(",{left:").append(lt.toString()).append("}");
		else
			sbr.append(",{left:").append(lt).append("}");
		if(rt!=null)
			sbr.append(",{right:").append(rt.toString()).append("}");
		else
			sbr.append(",{right:").append(rt).append("}");
		*/
		sbr.append("]");
		return sbr.toString();
	}

	
	public static void main(String args[])
	{
		System.out.println(new Node <  Integer  &rt;   (new Integer(10)).toString());
	}	
}

package edu.temple.pt.assignment;


import java.util.Stack;
/**
 * 
 * @author aakash
 *
 * @param  <  T  &rt;   
 */
public abstract class BinaryTree <  T  &rt;    {

	protected Node <  T  &rt;    root=null;
	public Node <  T  &rt;    getRoot() {
		return root;
	}

	public void setRoot(Node <  T  &rt;    root) {
		this.root = root;
	}

	protected abstract Node <  T  &rt;    createTree();
	
	public void postOrderTraversal()
	{
		
	}
	public void inOrderTraversal()
	{
		
	}
	public void preOrderTraversal()
	{
		System.out.println("\n=============================");
		System.out.println("Preorder traversal::");
		System.out.println("===============================");
		Node <  T  &rt;    p=root;
		Stack <  Node <  T  &rt;     &rt;    stack=new Stack <  Node <  T  &rt;     &rt;   ();
		while(p!=null||!stack.isEmpty())
		{
			Node <  T  &rt;    rtptr=null;
			if(p!=null)
			{
				visit(p);
				stack.push(p);
				if(p.getLt()!=null)
					p=p.getLt();
				else
					p=p.getRt();
			}
			else
			{
				Node <  T  &rt;   q=null;
				do
				{
					q=stack.pop();				
					if(!stack.isEmpty())
						rtptr=stack.peek().getRt();
					else
						rtptr=null;
				}
				while(!stack.isEmpty()&&q==rtptr);
				p=rtptr;
			}
		}
	}
	public void visit(Node <  T  &rt;    data)
	{
		System.out.println(data.toString());
	}
	
	public void visit(Node <  T  &rt;    data,Node <  T  &rt;    stack,Node <  T  &rt;    top)
	{
		System.out.println("node visiting currently::"+data.toString());
		if(stack!=null)
		{
			Node <  T  &rt;    p=stack;
			System.out.println("Stack::");
			while(p!=null)
			{
				System.out.print("\tdata:"+p.getData());
				if(p.getLt()!=null)
					System.out.print("\t left:"+p.getLt().getData());
				else
					System.out.print("\t left:"+p.getLt());
				if(p.getRt()!=null)
					System.out.println("\t right:"+p.getRt().getData());
				else
					System.out.println("\t right:"+p.getRt());
				
				p=p.getLt();
			}
		}
		else
			System.out.println("stack::"+stack);
		
		
		if(top!=null)
			System.out.println("top::"+top.getData());
		else
			System.out.println("top::"+top);
	}
	public void linkInvrsionTraversal()
	{
		Node <  T  &rt;    cur=root;
		Node <  T  &rt;    		empty=root;
		Node <  T  &rt;    		prev=null;
		Node <  T  &rt;    		next=null;
		System.out.println("link inversal traversal::");
		do
		{
			while(cur!=null)
			{
				visit(cur);
				cur.setTag(0);
				next= cur.getLt();
//						cur-  &rt;   left=prev;
				cur.setLt(prev);
				prev=cur;
				cur=next;
			}
			next=cur;
			cur=prev;
			if(prev.getTag()==0)
				prev=prev.getLt();
			else
				prev=prev.getRt();
			cur.setLt(next);
			boolean up=true;
			do
			{
				if(cur.getRt()!=null && cur.getTag()==0)
				{
					cur.setTag(1);
					next=cur.getRt();
					cur.setRt(prev);
					prev=cur;
					cur=next;

					up=false;
				}
				if(cur.equals(empty))
				{
					cur.setTag(0);
					return;
				}
				if(up==true&&prev!=null)
				{
					Node <  T  &rt;    next_prev=null;
					
					
					if(prev.getTag()==0)
						next_prev=prev.getLt();
					else 
						next_prev=prev.getRt();
					
					if(prev!=null&&prev.getTag()==0)
					{
						cur.setTag(0);
						prev.setLt(cur);
						cur=prev;
						prev=next_prev;
					}
					else
					{
						
						cur.setTag(0);
						prev.setRt(cur);
						cur=prev;
						prev=next_prev;
					}

				}
				
			}while(cur!=null&&up);
			
		}while(cur!=null);
	}
	
	
	
	/**
	Write and test a "modified" Robson Traversal program that uses the linked representation of the trees. This modified version differs from the Robson only in that        the pointers to a node's predecessor should now be as in the Linked Inversion Traversal. That is, when a node's left(right) subtree is being traversed, its left(	  right) pointer will point to its predecessor. During the traversal, when a node is visited, output for each "stack' entry, its info value and the info value of i	   ts left and right successors. This means, first, output the number of the node Top points to, and then the number that that node's left and right pointers point 	    to. Then, output the number of the node that Stack points to,and then the numbers that that node's left and right pointers point to. Do this for each node on the	      "stack". Also, output similar information for each node along the path from the predecessor of the node being visited to the root. That is, for each of these no	      des output its info value and the numbers that the nodes left left and right pointers point to.
	*/
	public void modifiedRobsonTreeTraversal()
	{
		Node <  T  &rt;    cur=root;
		boolean rootHasOnlyRightChild=false;
		if(root!=null)
			rootHasOnlyRightChild=(root.getLt()==null)?(root.getRt()!=null?true:false):false;
		Node <  T  &rt;    		empty=root;
		Node <  T  &rt;    		prev=null;
		Node <  T  &rt;    		next=null;
		Node <  T  &rt;   			avail=null;
		Node <  T  &rt;            stack=null;
		Node <  T  &rt;            top=null;
		boolean done=false;
		System.out.println("\n===============================");
		System.out.println("Modified Robson traversal::");
		System.out.println("===============================");
		if(cur==null)
		{
			System.out.println("Sorry! it is a null tree");
			return;
		}
		do
		{
			while(cur!=null)
			{
				visit(cur,stack,top);
				next= cur.getLt();
				
				if(cur.getLt()==null&&cur.getRt()==null)
				{
					if(avail==null)
						avail=cur;
					else
					{
						cur.setRt(avail);
						avail=cur;
					}
				}
				cur.setLt(prev);
				prev=cur;
				cur=next;
			}
			next=cur;
			cur=prev;
			prev=prev.getLt();
			cur.setLt(next);
			boolean up=true;
			boolean leftTraversingFinished=true;
			do
			{
				if(cur.getRt()!=null&&cur!=avail&&leftTraversingFinished)
				{
					next=cur.getRt();
					cur.setRt(prev);
					if(cur.getLt()!=null)
					{

						if(top!=null)
						{
							Node <  T  &rt;    temp=avail;
							avail=avail.getRt();
							temp.setLt(null);
							temp.setRt(null);
							temp.setRt(top);
							if(stack==null)
								stack=temp;
							else
							{
								temp.setLt(stack);
								stack=temp;
							}
							
						}
						top=cur;
						
					}
					prev=cur;
					cur=next;
					up=false;
				}
				if(cur.equals(empty))
				{
					done=true;
				}
				if(up==true&&prev!=null)
				{
					Node <  T  &rt;    next_prev=null;
					boolean curIsPrevLeftChild=true;
					if(prev==empty)
					{
						next_prev=null;
						if(rootHasOnlyRightChild)
							curIsPrevLeftChild=false;
					}
					else if(prev.getLt()!=null&&top!=prev)
						next_prev=prev.getLt();
						
					else
					{
						next_prev=prev.getRt();
						curIsPrevLeftChild=false;
					}

					
					if(top==prev)
					{
						prev.setRt(cur);
						leftTraversingFinished=false;
						if(top!=null)
						{
							
							if(stack!=null)
							{
								top=stack.getRt();
								Node <  T  &rt;    currentStack=stack;
								stack=stack.getLt();
								currentStack.setLt(null);
								currentStack.setRt(null);
							}
							else 
								top=null;
						
						}
					
					}
						
					else if(curIsPrevLeftChild)
					{
						prev.setLt(cur);
						leftTraversingFinished=true;
					}
					else 
					{
						prev.setRt(cur);
						prev.setLt(null);
						leftTraversingFinished=false;
						
						
					}
					cur=prev;
					prev=next_prev;
				}
				
			}while(cur!=null&&up&&!done);
			
		}while(cur!=null&&!done);
		while(avail!=null)
		{
			Node <  T  &rt;    temp=avail;
			avail=avail.getRt();
			temp.setLt(null);
			temp.setRt(null);
		}
	}
}


Advertisements

Discussion for Integer Overflow in Java

Standard

Today, I was reading an article for overflow and cannot stop myself from sharing the gist of it.

Let us discuss this solution of binary search tree.

public int binarySearchTree(int a[],int item)
{
  int start=0;
  int end=a.length-1;
  while(start<=end)
  {
      int mid=(start+end)/2;
      if(a[mid]==item)
               return mid;
      else if(a[mid]<item)
               start=mid+1;
      else
                end=mid-1;
}
return -1;
}

 

if we carefully check these lines of code, we will realize that the line mid=(start+end)/2 may result in overflow, what if start+end > Integer.MAX_VALUE then mid will have a -ve value.  To overcome this sort of potential programming bug (this bug is still existing in Java’s Arrays Binary search and it has been earlier reported by Joshua Bloch) , it will be better to write this line of code as this,

1)  mid= start + (end-start)/2;
or
2) mid = (start+high) >>>1; //since in java “>>>” is unsigned right shift operator.
 
Now let us try to write a utility class to check whether different arithmetic operation is overflow safe or not.

For this let us start to discuss which all arithmetic operation can result in overflow, here I will like to point out that any logical operation like &, | and ^ cannot result in overflow thats why we are only discussing arithmetic operation.

1) Addition:  a+ b can result in overflow as we have seen in above discussion. So, we need to have a utility method for this.

2)  Subtraction: same like for addition it can also result in overflow.

3)  Multiplication: a*b, can easily result in overflow.

4) Division: consider this case Integer.MIN_VALUE/-1,  this will result in overflow.

5) Negation: – (Integer.MIN_VALUE) can result in overflow again.

 

Here is the Utility class has methods to check the safety for each of the above discussed arithemetic operations:-

package org.aakash.pratice;

public class OverflowCheckUtility {

public static boolean isSafeToSubtract(int i,int j)
{
    if(!isSafeToNegate(j))
          return (i&Integer.MIN_VALUE)<0;
    return isSafeToAdd(i, -j);
}
public static boolean isSafeToNegate(int i)
{
    return i!=Integer.MIN_VALUE;
}
public static boolean isSafeToAdd(int i,int j)
{
    int k=i+j;
    if(((i^k)&(j^k))<0)
         return false;
    return true;
}
public static boolean isSafeToDivide(int i,int j)
{
   if(i<=Integer.MAX_VALUE&j==-1)
      return false;
   return true;
}
public static boolean isSafeToMultiply(int i,int j)
{
   int k=i*j;
   boolean expectedSign=((i&Integer.MIN_VALUE)^(j&Integer.MIN_VALUE))>=0?true:false;
   boolean actualsign=(k&Integer.MIN_VALUE)>=0?true:false;
   return expectedSign==actualsign;
}
/**
   Testing utility class for different boundry values
* @param args
*/

public static void main(String[] args) {
// TODO Auto-generated method stub
     int count=0;
     int n=Integer.MIN_VALUE;
//        int n=-1;
    while(n!=0)
    {
        n=(n-1)&n;
        count++;
     }
     System.out.println(count);
     System.out.println(Integer.MAX_VALUE*2);
     System.out.println(Integer.MAX_VALUE*-2);
     System.out.println(Integer.MIN_VALUE*2);
     System.out.println(Integer.MIN_VALUE*-1);
     System.out.println("::checking for multiply");
     int i=-1;
     System.out.println(isSafeToMultiply(i, Integer.MIN_VALUE));
     System.out.println(isSafeToMultiply(i, Integer.MAX_VALUE));
     System.out.println(isSafeToMultiply(2, Integer.MAX_VALUE/3));
     System.out.println(isSafeToMultiply(2, Integer.MAX_VALUE/2));
     System.out.println(isSafeToMultiply(2, Integer.MAX_VALUE));
     System.out.println(isSafeToMultiply(-2, Integer.MIN_VALUE/2));


     System.out.println("checking subtraction");
     System.out.println(isSafeToSubtract(-1, Integer.MAX_VALUE));
     System.out.println(isSafeToSubtract(-2, Integer.MAX_VALUE));
     System.out.println(isSafeToSubtract(-5, Integer.MAX_VALUE));
     System.out.println(isSafeToSubtract(1, Integer.MIN_VALUE));
     System.out.println(isSafeToSubtract(-12, Integer.MIN_VALUE));
     System.out.println(isSafeToSubtract(-1, Integer.MIN_VALUE));

     System.out.println("checking addition");
     System.out.println(isSafeToAdd(-1, Integer.MIN_VALUE));
//        System.out.println(isSafeToSubtract(-2, Integer.MAX_VALUE));
//        System.out.println(isSafeToSubtract(-5, Integer.MAX_VALUE));
//        System.out.println(isSafeToSubtract(1, Integer.MAX_VALUE));

}

How to generate all possible binary tree in reverse lexicographic order

Standard

Suppose we are representing binary as L and R array, for example
The tree would be represented then
1            L[1]=2, R[1]=4
/  \           L[2]=0, R[2]=3
2   4        L[3]=0, R[3]=0
\             L[4]=0, R[4]=0
3

Now, if we read tree in preorder, in such a way that if node present it print 1 otherwise 0 then this tree will also be represented as 110100100. Now the problem we are going to solve here is: “ if we have to generate all possible binary tree for a give number of node in such a way that if we traverse the tree in preorder just described then it should be in reverse lexicographic order.

Now, first we will develop the algo then will code it.

Our first step will be to observe the pattern and see what will be the next generated tree for a given tree. Suppose we have this tree

                       1

                  /

             2

           /

        3

tree in 1,0 format : 1110000

then the next generated tree in the reverse lexicographic order will be this

                         1

                     /

                  2

                     \

                       3

tree in 1,0 format : 1101000

After looking at then newly generated tree, we can find that node 3 has moved and its moved from left of 2 to right of 3.  Let us generate one more tree from the last generated tree and the new tree will look like this:

                1

            /       \

          2            3

tree in 1,0 format : 1100100 (Note: observe this no for all the generated tree, you will find its decreasing)

and next  tree generated from this tree is:

               1

             /   \

        null      2

                   /      \

              3          null

tree in 1,0 format : 1011000 (Note: observe this no for all the generated tree, you will find its decreasing)

If we compare with the last generated one then we will find that this time node 2 has moved and now node 3 is left child of node 2.  If we generate  some more trees then we will find that this algo:

1. take the nth node and try to find the best position for it i.e. the next possible position for it in preorder.

2. if we are not able to find any position for nth node then try to find for n-1 th node and moved the node there

and then we make all node greater then this left child of its parent.

For example :-

1 we take the first generated tree as an example here:

1. let us take the nth node , 3 in this case, now try to find the next possible position for it in the tree after traversing it in preorder then we will find that it it is the right of 2nd node.

2. move the 3 rd node to right of 2nd node and since it has no child node, hence this is the answer.

2. Now try, the last generated tree:

1. let us take the nth node first here i.e. 3rd node in this case, now if we try to next possible position. We see there is no possible next position for so

2. try the node higher then it i.e. 2nd node. We find that next possible position for it is right of 1. Now shift 2nd to this new position and move 3 rd as its left child, if we have 4 th node then we would have made it left of 3rd.

The most important this, we have to do now, is to find the way to find the next possible position for the given node. After,  we do pre-order traversal of the tree then we will find that the 3 rd node traversed after traversing the selected node is the possible position for it. For example,

take the example of first generated tree:-

                            1

                       /       \

                      2           null 4

                  /    \

              3         null 3

             /    \

     null  1   null 2

now if we try to find , the possible position for 3 we see that after traversing node 3 in pre-order, we traverse null 1 first then null 2 and then null3 which is the possible position and which is exactly third node traversed after traversing node 3. Hence our logic is correct in this example.

Now, we consider the last generated tree, the parent tree is

                                      1

                                  /      \

                              2             3

                         /     \             /   \

                 null1  null2     null3  null4

Now, we try to find,  best  position for nth node, i.e. 3 rd node, now if we do pre-order traversal, then we find that after traversing node 3rd we can only 2 nodes which are its child and hence there is no possible shift for node 3 rd hence we will do the same for node 2 nd and we will find that 3 rd node traversed after traversing node 2 is the node where currently node 3 is, hence we shift 2 to this new position and make node 3 its left child and if we would has 4 th node then it would have been the left child of node 3rd and so on.

Before we start coding, one more point left to discuss is: from where to start, what actually I mean is what will be the first base tree?

For, generating the reverse lexicographic order  tree, the firs tree should be the left linear tree i.e.

                                                   1

                                            /

                                    2

                                 /

                            3

                        .

                      .

                  n

and the final tree will be right linear tree i.e.

1

   \

      2

        \

           3

               .

                  .

                   n


package edu.temple.pt.assignment;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* This program is written as part of the assignment 5 question 1. It provides APIs to generate the next binary tree for a given binary tree in
* reverse lexicographic order.
*
* Assignment:
* Assume the nodes of any n node binary tree are numbered from 1 to n in preorder. Arrays L and R will be used to represent the tree in memory as in the following example.
* Consider the tree with nodes 1, 2, 3 and 4 with 2 and 4 as 1’s left and right successors and 3 as 2’s right successor. Then L and R would be
* L[1]=2, R[1]=4
L[2]=0, R[2]=3
L[3]=0, R[3]=0
L[4]=0, R[4]=0

Write a program to generate all the binary trees with n nodes so that their representations, using n 0’s and n 1’s (i.e. n right and n left parentheses)
as discussed in class, would appear in reverse lexicographic order. The tree is represented in memory only by the L and R arrays. To do this, you should determine
what transformation is required on a tree that corresponds to the transformation on its parentheses representation to produce the successor tree in lexicographic
order, and then carry out this transformation on the tree in memory. Your program should output the L and R arrays for each tree and its corresponding n 0’s and n 1’s
representation. You should provide a number of samples for small n that are actual outputs of the program. In addition you should output the #of binary trees with n nodes.

<code>

* @author aakash
*
*/
public class ReversedLexicoGraphic {
/**
*
*/
public ReversedLexicoGraphic() {
super();
}
private int preOrderElementVisited[]=null;
private int elementVisitedPosition[]=null;

/**
* this method will do preorder traversal to the tree represented in LR array and will decide what is the next best position for
* the given element.
* @param binaryTreeInLRArray binary tree represented in LR array
* @param element element for which the best next position to be found
* @return -1 if it there is no suitable next position for it otherwise it will return positive number( if is is less than n(number of nodes in tree)
* then it means the index in left array otherwise return_value-n is the index for right array)
*/
private int findNextPositionForGivenElement(BinaryTreeInLRArray binaryTreeInLRArray,int element)
{
preOrderElementVisited=new int[binaryTreeInLRArray.getLeftArray().length*2+1];
elementVisitedPosition=new int[binaryTreeInLRArray.getLeftArray().length-1];
for(int i=0;i<elementVisitedPosition.length;i++)
elementVisitedPosition[i]=-1;
for(int i=0;i<preOrderElementVisited.length;i++)
preOrderElementVisited[i]=-1;
//int freeEntry=0;
int p=1;
Stack stack=new Stack();
int i=0;
int lastFreeEntry=-1;
int j=0;
boolean foundLastNode=false;
int countOfLeaveNodeAfterLastNode=0;
while(p!=0||!stack.isEmpty())
{

if(p!=0)
{
stack.push(p);

preOrderElementVisited[i++]=p-1;
if(binaryTreeInLRArray.getLeftArray()[p-1]==0&&foundLastNode)
{
//System.out.println(“calculating prev=”+lastFreeEntry+” when p=”+(p-1));
countOfLeaveNodeAfterLastNode++;
if(countOfLeaveNodeAfterLastNode>=3)
{
lastFreeEntry=p-1;
break;
}
}
if(binaryTreeInLRArray.getLeftArray()[p-1]!=0)
{
if(j=3)
{
lastFreeEntry=p-1+binaryTreeInLRArray.getLeftArray().length;
break;
}

}
else if(binaryTreeInLRArray.getRightArray()[p-1]!=0&&j<elementVisitedPosition.length-1)
elementVisitedPosition[j++]=p-1+binaryTreeInLRArray.getLeftArray().length;
p=binaryTreeInLRArray.getRightArray()[p-1];

}

}
else
{
int q=0;
int r=0;
do
{
q=stack.pop();
if(!stack.isEmpty())
{
preOrderElementVisited[i]=stack.peek()-1+binaryTreeInLRArray.getLeftArray().length;
r=binaryTreeInLRArray.getRightArray()[stack.peek()-1];
if(r==0&&foundLastNode)
{
//System.out.println(“calculating prev=”+lastFreeEntry+” when p=”+(p-1));
countOfLeaveNodeAfterLastNode++;
if(countOfLeaveNodeAfterLastNode==3)
{
lastFreeEntry=stack.peek()-1+binaryTreeInLRArray.getRightArray().length;
stack.removeAllElements();
return lastFreeEntry;
}

}
else if(r!=0&&j=2;element–)
{
BinaryTreeInLRArray tempBinaryTreeInLRArray=new BinaryTreeInLRArray(baseBinaryTreeInLRArray.getLeftArray().length);
for(int i=2;i<=element;i++)
{
int tempPosition=elementVisitedPosition[i-2];
modifyArrayAtPosition(tempBinaryTreeInLRArray, tempPosition, i);
}
position=findNextPositionForGivenElement(tempBinaryTreeInLRArray, element);
tempBinaryTreeInLRArray=null;
if(position!=-1)
break;
}

if(element==1||element==-1)
{
binaryTreeInLRArray=null;
return binaryTreeInLRArray;
}
// findNextPositionForGivenElement(baseBinaryTreeInLRArray, baseBinaryTreeInLRArray.getLeftArray().length);
// System.out.println(“position:”+position+” for element:”+element);
for(int i=2;i<element;i++)
{
int tempPosition=elementVisitedPosition[i-2];
modifyArrayAtPosition(binaryTreeInLRArray, tempPosition, i);
}

modifyArrayAtPosition(binaryTreeInLRArray, position, element);
for(int i=element+1;i<=binaryTreeInLRArray.getLeftArray().length;i++)
{
int tempPosition=i-2;
modifyArrayAtPosition(binaryTreeInLRArray, tempPosition, i);
}

}
else
{
for(int i=2;i=binaryTreeInLRArray.getLeftArray().length)
{
position-=binaryTreeInLRArray.getLeftArray().length;
binaryTreeInLRArray.getRightArray()[position]=element;
}
else
binaryTreeInLRArray.getLeftArray()[position]=element;
}
/**
* This method can be used to get the next binary tree in reverse lexicographic order.
*
* @param base the base tree from which the next binary tree will be generated
* @return null if there is no possible binary tree otherwise the new generated binary tree.
*/
public BinaryTreeInLRArray getNextBinaryTree(BinaryTreeInLRArray base)
{
if(base.getLeftArray().length<=1)
return null;
// BinaryTreeInLRArray nextLRBinaryTree=new BinaryTreeInLRArray(base.getLeftArray().length);

int prev=findNextPositionForGivenElement(base,base.getLeftArray().length);
// for(int i=0;i<preOrderElementVisited.length;i++)
// System.out.println(“\npreorder visit::”+preOrderElementVisited[i]);
// for(int i=0;i<elementVisitedPosition.length;i++)
// System.out.println(“element visited position::”+elementVisitedPosition[i]);
// System.out.println(“prev=”+prev);
// if(prev==-1)
// return null;

BinaryTreeInLRArray nextLRBinaryTree=modifiedPosition(base, prev);
return nextLRBinaryTree;
}
public List getAllReveresedLexicoGraphicBinaryTree(int n)
{
ArrayList binaryTreeInLRArrayList=new ArrayList();
if(n0″);
int L[]=new int[n];
int R[]=new int[n];
int j=2;
for(int i=0;i<n;i++)
{
R[i]=0;
if(j<=n)
L[i]=j++;
else
L[i]=0;
}
BinaryTreeInLRArray baseBinaryTreeInLRArray=new BinaryTreeInLRArray(L, R);
binaryTreeInLRArrayList.add(baseBinaryTreeInLRArray);
while((baseBinaryTreeInLRArray=getNextBinaryTree(baseBinaryTreeInLRArray))!=null)
binaryTreeInLRArrayList.add(baseBinaryTreeInLRArray);
return binaryTreeInLRArrayList;
}
public static void main(String args[])
{
// int R[]={5,0,4,0,0};
// int L[]={2,3,0,0,0};

int R[]={0,0,0,0};
int L[]={2,3,4,0};
BinaryTreeInLRArray binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.preOrderTraversal();

//binaryTree=new ReversedLexicoGraphic().getNextBinaryTree(binaryTree);
int i=1;
while((binaryTree=new ReversedLexicoGraphic().getNextBinaryTree(binaryTree))!=null)
{
binaryTree.preOrderTraversal();
i++;
System.out.println(“total generated count::”+i);
}
System.out.println(“total generated count::”+i);

/*
binaryTree=new ReversedLexicoGraphic().getNextBinaryTree(binaryTree);
//int i=1;
//while((binaryTree=new ReversedLexicoGraphic().getNextBinaryTree(binaryTree))!=null)
{
binaryTree.preOrderTraversal();
i++;
System.out.println(“total generated count::”+i);
}
System.out.println(“total generated count::”+i);

*/

}
}


package edu.temple.pt.assignment;

import java.util.Stack;

public class BinaryTreeInLRArray {

int L[]=null;
int R[]=null;

public void setLeftArray(int L[])
{
this.L=L;
return;
}
public void setRightArray(int R[])
{
this.R=R;
return;
}
public int[] getLeftArray()
{
return L;
}
public int[] getRightArray()
{
return R;
}

int visitedArray[]={-1};
public BinaryTreeInLRArray(int numberOfNodes) {
// TODO Auto-generated constructor stub
L=new int[numberOfNodes];
R=new int[numberOfNodes];
}
public BinaryTreeInLRArray(int L[],int R[]) {
// TODO Auto-generated constructor stub
if(L.length!=R.length)
throw new IllegalArgumentException(“Sorry! L and R array should be of equal length”);
this.L=L;
this.R=R;
}
private void visit(int i)
{
if(visitedArray[0]!=-1)
System.out.print(visitedArray[0]!=0?1:0);
visitedArray[0]=i;
}
private void cleanUpVisit(){
visitedArray[0]=-1;
}
private void printLRArray()
{
System.out.println(“\t[L]\t[R]”);
System.out.println(“\t—\t—“);
for(int i=0;i<L.length;i++)
System.out.println(“\t|”+L[i]+”|\t|”+R[i]+”|”);
}
public void preOrderTraversal()
{
printLRArray();
int p=1;
Stack stack=new Stack();
while(p!=0||!stack.isEmpty())
{

if(p!=0)
{
visit(p);
stack.push(p);
if(L[p-1]!=0)
p=L[p-1];
else
{
visit(L[p-1]);
p=R[p-1];
if(p==0)
visit(p);
}
}
else
{
int q=0;
int r=0;
do
{
q=stack.pop();
if(!stack.isEmpty())
{

r=R[stack.peek()-1];
if(r==0)
visit(r);
}
else
r=0;

}while(!stack.isEmpty()&& q==r);
p=r;

}

}
cleanUpVisit();
}

public void reversePreOrderTraversal()
{
printLRArray();
int p=1;
Stack stack=new Stack();
while(p!=0||!stack.isEmpty())
{

if(p!=0)
{
visit(p);
stack.push(p);
if(R[p-1]!=0)
p=R[p-1];
else
{
visit(R[p-1]);
p=L[p-1];
if(p==0)
visit(p);
}
}
else
{
int q=0;
int r=0;
do
{
q=stack.pop();
if(!stack.isEmpty())
{

r=L[stack.peek()-1];
if(r==0)
visit(r);
}
else
r=0;

}while(!stack.isEmpty()&& q==r);
p=r;

}

}
cleanUpVisit();
}
private Integer getIntegerFromBinaryString(String str,int i)
{
if(str.charAt(i)==’0’||str.charAt(i)==’)’)
return new Integer(0);
return new Integer(1);
}
/**
* Extra Credit
Write and test a program “create”, that reads the sequence of n 0’s and n 1’s (i.e. the n right and n left parentheses) representing an n node
binary tree as we discussed in class and creates a linked representation of the tree in memory using L and R. This program should echo the
input. After the tree is created, preorder traverse the tree, and as each node is visited, output its number and that of its left and right
successors.
Provide the actual output for a number of sample trees.
* @param binaryString
*/
public void createTree(String binaryString)
{
L=new int[binaryString.length()/2];
R=new int[binaryString.length()/2];
for(int i=0;i<L.length;i++)
{
L[i]=R[i]=-1;
}
int p=1;
Stack stack=new Stack();
int i=0;
if(getIntegerFromBinaryString(binaryString, i).equals(new Integer(0)))
{
p=0;
for(int j=0;j<L.length;j++)
{
L[j]=R[j]=0;
}
}
int elementCount=2;
while(p!=0||!stack.isEmpty())
{

if(p!=0)
{
//visit(p);
i++;
stack.push(p);
if(getIntegerFromBinaryString(binaryString, i).equals(new Integer(1)))
L[p-1]=elementCount++;
else
L[p-1]=0;

if(L[p-1]!=0)
p=L[p-1];
else
{
i++;
if(getIntegerFromBinaryString(binaryString, i).equals(new Integer(1)))
R[p-1]=elementCount++;
else
R[p-1]=0;
// visit(L[p-1]);
p=R[p-1];
// if(p==0)
// visit(p);
}
}
else
{
int q=0;
int r=0;
do
{
q=stack.pop();
if(!stack.isEmpty())
{
r=R[stack.peek()-1];
if(r==-1)
{
i++;
if(getIntegerFromBinaryString(binaryString, i).equals(new Integer(1)))
R[stack.peek()-1]=elementCount++;
else
R[stack.peek()-1]=0;
r=R[stack.peek()-1];
}

}
else
r=0;
}while(!stack.isEmpty()&& q==r);
p=r;

}

}
}

public static void main(String args[])
{
int L[]={2,0,0,0};
int R[]={4,3,0,0};

BinaryTreeInLRArray binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“110100100”);
System.out.println();
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“111000100”);
System.out.println();
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“101100100”);
System.out.println();
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“101010100”);
System.out.println();
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“101010100”);
System.out.println();
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“111100000”);
System.out.println();
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“011100000”);
System.out.println();
binaryTree.preOrderTraversal();
}
}

Linux CPU Scheduling

Standard

Today we will discuss about the CPU scheduling in Linux. What do we mean by CPU scheduling, it is sharing the CPU among different processes. Earlier most of the system were uniprocessor and for them CPU scheduling algorithm used were:-

  1. FCFS (First come first scheduled)
  2. SJFS (Shortest Job First)
  3. RR (Round Robin)
  4. Priority Based Scheduling

Nowadays systems are multiprocessor and we need to schedule the CPU in such a way that all the processor execute jobs in balanced way and for this we have new scheduling algorithms. Besides this most of the new scheduling algorithm are priority based.

Now, when we consider the priority based algorithm, then first question arise is: who will assign the priority? we cannot leave this to user; since it may possible that the user processes will have higher priority then the system related processes which is not correct since the interrupt and kernal thread should have higher priority and we also cannot leave the priority decision totally on the system since then it will be impossible for user to specify to the system about importance of tasks. In Linux there are two types of priorities:-

  • Static Priority- assigned by the user using nice() system call.
  • Dynamic Priority – priority assigned earlier is recalculated by the scheduler.

In, Linux processes are classified as:-

  • CPU bound processes (Real Time (RT) processes)
  • IO bound processes (Interactive processes)

Scheduler in Linux system is known as O(1) scheduler, since it takes constant time in all the operations e.g. selecting the process with highest priority, recalculating the priorities and adding the process to queue.It is multi-level priority based, fairer and preemptive(once the time quantum is over it will be switched with the process higher or equal in priority and time quantum assigned to processes is nearly ~100 ms) in nature. There are 140 levels of priority and at each level there is queue for processes.For deciding, the processes with highest priority it uses bitmap mechanism and scan this bitmap array from left and so which ever bit is found to be set first, process will be selected from that particular priority level.
In Linux, typically there are two priority arrays (as discussed earlier the array of 140 priority queue) are maintained, which are known as active and expired. For, processes for whom time quantum is over, is moved to expired array and once the processes are exhausted in active array, pointers are exchanged that is expired array become active and active become expired and all processes are assigned new time quantum (a.k.a epoch).

While recalculating the priority, scheduler gives bonus to processes which varies from 0 to 10, one thing
to be remembered is that higher the value of the priority less is its priority in scheduler term, hence to increase the priority, bonus added which actually means decrementing that many bonus from the current priority and opposite way while decreasing the priority in scheduler context. To make the system fairer, IO bound processes get more bonus then the CPU bound and this bonus calculation is depend on the amount processes have slept and priorities for RT processes remains same. Algorithm for recalculation of priority of process is:

(For detail, data structure and methods of Linux check kernel/sched.c and kernel/sched.h file and man sched_setscheduler.)


bonus = CURRENT_BONUS(p) – MAX_BONUS / 2;
prio = p->static_prio – bonus;
CURRENT_BONUS is defined as follows:
#define CURRENT_BONUS(p) NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / MAX_SLEEP_AVG)


Essentially, CURRENT_BONUS maps a task’s sleep average onto the range 0-MAX_BONUS, which is 0-10. If a task has a high sleep_avg, the value returned by CUR-RENT_BONUS will be high, and vice-versa. Since MAX_BONUS is twice as large as a task’s priority is allowed to rise or fall (MAX_BONUS of 10 means that the priority adjustment can be from +5 to -5), it is divided by two and that value is subtracted from CURRENT_BONUS(p).

Here, p-> static_prio is the static priority defined by the user to a process using nice() system call and by default it is 0.

Till now we have discussed about the priority assignment and its recalculation and data structure and algo for processes priority, but for a scheduler to be fairer to all processor it must need to balance the jobs load among the processors. For this load balancing for SMP system, Linux scheduler invokes the rebalance_tick() function, which is called by scheduler_tick(). rebalance_tick() first updates the current CPU’s load variable, then goes up the CPU’s scheduler domain hierarchy attempting to rebalance.

We can also specify different types of scheduling policies and details for this can be found, if we do “man sched_setscheduler”.
In summary, Linux CPU scheduler is one of the best multi-processor and fairer scheduler available today.

Synchronization using Monitor

Standard

Monitor

It is an advance mechanism for synchronization, it is more sophisticated and advance than “Semaphore”. It can be considered as an object or module where the variables and synchronization mechanism is abstracted from the user hence unlike semaphore where user is suppose to handle the mutual exclusion and counting based logic, hence less error-prone.

It has been invented by C. A. R. Hoare, a british computer scientist who is profoundly known for inventing Quick Sort.

At a time only one thread can execute monitor’s procedure and only one of the procedure of monitor can be executed. From implementation point of view we can use binary semaphore to implement this feature of monitor .i.e. to provide the mutual exclusion among the monitor’s procedures.

Now, since only one of thread can execute the monitor hence other thread should wait for it and for waiting we need to first have the queue and then method call to make them wait () and release them from the waiting queue and having this in mind a new concept of Condition Variables is introduced. The POSIX thread implementation has library for this pthread_cond_wait() and pthread_cond_signal().

Though Condition variables’s wait() and signal() and Semaphore’s P() and V() seems similar but there are some differences:-

  • Wait Queue is FIFO (hence it is considered as fair also), unlike the semaphore queue, hence process will be awake in order
  • Unlike V() of semaphore, if there is no process waiting then signal() call will be nop (no operation)
  • Condition variable can only be used for block and wake up, it cannot be used for counting
  • Executing wait(), release mutual exclusion on the monitor i.e. allow other thread to execute it

Some caveats while implementing monitor:-

  • We should call signal() as the last instruction otherwise two threads will be executing the monitor at the same time which is not what we are expecting, those two threads will be: the thread which called signal() and the one which is waked up.
  • If we are calling signal in the middle then use the concept of urgent queue which is again like wait queue. The thread which is calling signal() will be inserted in urgent queue and if there is no process waiting for that signal then threads waiting in the urgent queue will be waked up and it has given priority over threads on the entrance queue (There is supposed to be an entry queue for the thread willing to get in monitor)

In the Java language, each object may be used as a monitor. (However, methods that require mutual exclusion must be explicitly marked as synchronized.) Rather than having explicit condition variables, each monitor (i.e. object) is equipped with a single wait queue, in addition to its entrance queue. All waiting is done on this single wait queue and all notify and notify all operations apply to this queue.

This approach has also been adopted in other languages such as C#.

References

Hello world!

Standard

Hi Guys,

I am Aakash, currently a graduate student at Temple University, Philadelphia before joining Temple I worked as Senior Quality Eng. in Yahoo! R&D for 3 and half years. I am also an alumni of Vellore Institute of Technology, Vellore, India.
I believe in working hard and doing something new in my style. I am fond of computers and love solving problems, optimizing it and my area of interests are: Programming Technique. Algos, Operating System and Distributed Systems.
As far as my hobbies and interests are concerned I like coding, reading books, listening songs and watching Cricket and Football.

I will welcome readers to be my friend at FB (https://www.facebook.com/profile.php?id=750863707) and will appreciate their comments.

Thanks for ur precious time!