Priority Queue implemented by heap

import java.util.Comparator;


public class PriQueue <T> {
 int defaultsize = 2000;
 int size;
 T[] elements;
 int length;
 Comparator<? super T> comparator; 
 
 @SuppressWarnings("unchecked")
 public PriQueue(int size){
  this.size = size;
  if( size <= 0 ){
   this.size = this.defaultsize;
  }
  this.elements = (T[]) new Object[size+1];
  this.length = 0;
 }
 
 @SuppressWarnings("unchecked")
 public PriQueue(){
  this.size = this.defaultsize;
  this.elements = (T[]) new Object[size+1];
  this.length = 0;
 }
 
 public int size(){
  return this.size;
 }
 
 public int length(){
  return this.length;
 }
 
 public void setComparator(Comparator<? super T> comparator){
  this.comparator = comparator;
 }
 
 void swap(int i, int j){
  T t = elements[i];
  elements[i] = elements[j];
  elements[j] = t;
 }
 
 public void insert(T t){
  int cur, parent;
  if( this.length == this.size ){
   throw new UnsupportedOperationException("queue is full");
  }
  if( comparator == null ){
   throw new UnsupportedOperationException("Comparator is not defined.");
  }
  elements[++this.length] = t;
  for( cur = this.length; cur > 1 && 
   comparator.compare(elements[parent = cur/2], elements[cur])>0; cur=parent){
   swap(parent,cur);
  }
 }
 
 public T extractmin(){
  int cur, child;
  if( this.length < 1 ) {
   return null;
  }
  if( comparator == null ){
   throw new UnsupportedOperationException("Comparator is not defined.");
  }
  T t = elements[1];
  elements[1] = elements[this.length--];
  for( cur = 1; (child=2*cur)<=this.length; cur = child ){
   if( (child+1) <= this.length && 
     comparator.compare(elements[child+1], elements[child])< 0 ){
    child++;
   }
   if( comparator.compare(elements[cur], elements[child])<=0 ){
    break;
   }
   swap(cur, child);
  }
  return t;
 }
}

Test:

public class TestMain {

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub

  Comparator<Integer> comp = new Comparator<Integer>() {  
            @Override  
            public int compare(Integer o1, Integer o2) {  
                return o1 - o2;  
            }  
        };  
  PriQueue<Integer> queue = new PriQueue<Integer>();
  queue.setComparator(comp);
  queue.insert(5);
  queue.insert(3);
  queue.insert(6);
  queue.insert(2);
  Integer val = null;
  while( (val = queue.extractmin()) != null ){
   System.out.print(val + " ");
  }
 }

}

Output: 2 3 5 6

Binary Tree

Breadth First Scan

Define Binary Tree:

public class BTree {
 BTree left;
 BTree right;
 String id;
 
 public BTree(String id){
  this.id = id;
 }
 
 public BTree Left(){
  return this.left;
 }
 
 public BTree Right(){
  return this.right;
 }
 
 public void setLeaves(BTree left, BTree right){
  this.left = left;
  this.right = right;
 }
 
 public String toString(){
  return this.id;
 }
}

Tree mothods

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class TreeMethod {

 /**
  * Breadth First Traversal
  */
 public static void BFT(BTree root){
  Queue<BTree> queue = new LinkedList<BTree>();
  if(root != null ){   
   queue.offer(root);
  }
  
  BTree node = null;
  while( (node = queue.poll()) != null ){   
   System.out.print(node + " ");
   
   if( node.Left() != null )
    queue.offer(node.Left());
   if( node.Right() != null )
    queue.offer(node.Right());
  }
 }
 
 
 /**
  * Pre Order Traversal
  */
 public static void PreOrder(BTree root){
  if( root == null ){
   return;
  } 
  
  System.out.print(root + " ");
  // traverse left node
  PreOrder(root.Left());
  //traverse right node
  PreOrder(root.Right());
 }
 
 /**
  * Pre Order Traversal without recursion
  */
 public static void PreOrder_NoRecursion(BTree root){
  Stack<BTree> stack = new Stack<BTree>();
  stack.push(root);
  BTree node = null;
  while( !stack.isEmpty() && (node=stack.pop()) != null ){
   System.out.print(node + " ");
   if( node.Right() != null )
    stack.push(node.Right());
   if( node.Left() != null )
    stack.push(node.Left());
  }
 }
 
 /**
  * In Order Traversal
  */
 public static void InOrder(BTree root){
  if( root == null ){
   return;
  }
  // traverse left node
  InOrder(root.Left());

  System.out.print(root + " ");

  //traverse right node
  InOrder(root.Right());
 }
 
 /**
  * In Order Traversal without recursion
  */
 public static void InOrder_NoRecursion(BTree root){
  Stack<BTree> stack = new Stack<BTree>();
  while( root!=null || !stack.isEmpty() ){
   // traverse along the left child till meet the end
   while( root != null ){
    stack.push(root);
    root = root.Left();
   }
   
   root = stack.pop();   
   System.out.print(root + " ");
   
   // start traversal from the right child
   root = root.Right();
  }
 }
 
 /**
  * Post Order Traversal
  */
 public static void PostOrder(BTree root){
  if( root == null ){
   return;
  }
  // traverse left node
  PostOrder(root.Left());

  //traverse right node
  PostOrder(root.Right()); 
  
  System.out.print(root + " ");
 }
 
 /**
  * Post Order Traversal without recursion
  */
 public static void PostOrder_NoRecursion(BTree root){
  Stack<BTree> stack = new Stack<BTree>();
  BTree pre = null;
  while( root!=null || !stack.isEmpty() ){
   // traverse along the left child till meet the end
   while( root != null ){
    stack.push(root);
    root = root.Left();
   }
    
   root = stack.pop();
   while( root.Right() == null || root.Right() == pre ){
    System.out.print(root + " ");    
    pre = root;
    if( stack.isEmpty() ) {
     return;
    }
    root = stack.pop();
   }
   
   stack.push(root);
   root = root.Right();
  }
 }
}

turn a binary tree into a double linked list

public static  void Tree2DLinkedList(BTree root) { 
  if( root == null) {
   return;
  }
  Tree2DLinkedList(root.left);
  if( tail != null ){
   tail.right = root;   
  }
  
  if( head == null ){
   head = root;
  }
  root.left = tail;
  tail = root;
  
  Tree2DLinkedList(root.right);  
 }
 
 static BTree head;
 static BTree tail;

Test method:

public class TestTree {

 /**
  * @param args
  */
 public static void main(String[] args) {
  /**
   *            A
   *          /   \
   *         B     C
   *        / \      \
   *       D   E      F
   *          / \
   *         G   H
   */
  BTree A = new BTree("A");
  BTree B = new BTree("B");
  BTree C = new BTree("C");
  BTree D = new BTree("D");
  BTree E = new BTree("E");
  BTree F = new BTree("F");
  BTree G = new BTree("G");
  BTree H = new BTree("H");

  A.setLeaves(B, C);
  B.setLeaves(D, E);
  E.setLeaves(G, H);
  C.setLeaves(null, F);
  
  System.out.print("Breadth First Traversal: ");
  TreeMethod.BFT(A);
  System.out.println();
  
  System.out.print("Preorder Traversal: ");
  TreeMethod.PreOrder(A);
  System.out.println(); 
  
  System.out.print("Preorder Traversal with no recursion: ");
  TreeMethod.PreOrder_NoRecursion(A);
  System.out.println();
  
  System.out.print("Inorder Traversal: ");
  TreeMethod.InOrder(A);
  System.out.println(); 
  
  System.out.print("Inorder Traversal with no recursion: ");
  TreeMethod.InOrder_NoRecursion(A);
  System.out.println();
  
  System.out.print("Postorder Traversal: ");
  TreeMethod.PostOrder(A);
  System.out.println(); 
  
  System.out.print("Postorder Traversal with no recursion: ");
  TreeMethod.PostOrder_NoRecursion(A);
  System.out.println();

  System.out.println("Building double linked list:"）；
  TreeMethod.Tree2DLinkedList(A);
  tail = TreeMethod.tail;
  while( tail != null ){
   System.out.print(tail + " ");
   tail = tail.left;
  }
  System.out.println();
  head = TreeMethod.head;
  while (head != null ){
   System.out.print(head + " ");
   head = head.right;
  }
 }
}

Result:

Breadth First Traversal: A B C D E F G H
Preorder Traversal: A B D E G H C F
Preorder Traversal with no recursion: A B D E G H C F
Inorder Traversal: D B G E H A C F
Inorder Traversal with no recursion: D B G E H A C F
Postorder Traversal: D G H E B F C A
Postorder Traversal with no recursion: D G H E B F C A
Building double linked list F C A H E G B D
D B G E H A C F

Big Endian or Little Endian

Write a function to test a system is using Big Endian or Little Endian. For a hex A45C Big Endian, MSB (Most Important Byte) is stored in the lowest address: 1st byte - A4, 2nd byte - 5C Little Endian, LSB (Least Important Byte) is stored in the lowest address: 1st byte - 5C, 2nd byte - A4 Windows, Linux use Little Endian, Mac OS uses Big Endian. Network protocol uses Big Endian, so Big Endian is also called Network Byte.

 
/*
 * check the binary value of first byte of 1,
 * value = 0 -> Big Endian
 * value = 1 -> Little Endian
 */
void endianness(){
    int testNum;
    char* ptr;

    testNum = 1;
    ptr = (char*) &testNum;
    if(*ptr) {
        printf("Little Endian.");
    } else {
        printf("Big Endian.");
    }
}

/*
 * use union, theInteger & singleByte will share the same lowest address
 */
void endiannessV2(){
    union{
        int theInteger;
        char singleByte;
    } endianTest;

    endianTest.theInteger = 1;
    if(endianTest.singleByte) {
        printf("Little Endian.\n");
    } else {
        printf("Big Endian.\n");
    }
}

/*
 * convert from a network byte
 */
int getIntBE(int networkbyte){
    char* ptr = (char*)&networkbyte;
    return (int)(ptr[0]<<24) + (int)(ptr[1] << 16) + (int)(ptr[2] << 8) + (int)(ptr[3]);
}

/*
 * convert to a network byte
 */
int getIntLE(int value){
    char* ptr = (char*)&value;
    return (int)(ptr[3]<<24) + (int)(ptr[2] << 16) + (int)(ptr[1] << 8) + (int)(ptr[0]);
}