Saturday, February 21, 2009

Java Inheritance gotchas

Here are a few gotchas about inheritance in java. It is followed by an example which highlights some of these.
- private instance methods and variables are not inherited. Similarly, final instance methods and variables are not inherited. If you try it, you will get compile time error.
- Static methods and static variables cannot be inherited. If static methods are defined again in the sub class, it amounts to redefinition and has nothing to do with overriding. It is also called static method hiding. Similarly if static variables are defined again in the sub class it hides the static variables with same name in the super class.
-Similar to static variables , if instance variables are defined again in subclass, it hides the variables with same name in the super class.
- For redefinition/hiding it is the same name that matters, the type and access modifiers can be different.
- Since static members(variables and methods) belong to a class and not an instance, it is always a good practice to access static members with class name. If they are called using reference type, the reference type and not the object type determines which static method will be called.
- Object type determines which overloaded method is called at runtime but reference type determines whether a method can be called i.e. if the method isn't defined in reference type definition, you will get a compile time error.
- Reference type and not the object type determines which instance variable is called at runtime.
- When you override a method, you can still get the original method by using super.thatMethod() .

Example:

//Super class
public class StringInstruments {

  public static String types = "Over 50 types of String Instruments are available today";
  protected String wholesaleManufacturer = "Thumbelina & Co";
  
  public static void superDefinition() {
    System.out.println("StringInstruments: Vibrating strings produce sound.");
  }
  
  public void playIt() {
    System.out.println("Pluck it or use the bow or strike it");
  }

}

//Sub class
class ClassicalViolin extends StringInstruments {
  
//Redefinition
  public static String types = "Only 1 type of Classical Violin exists today, though it comes in many sizes";

//Instance variable redefinition.
// If you want inheritance, have get and set for
//this member variable in the base class.
  int  wholesaleManufacturer = 8;
  
  //Static method hiding
  public static void superDefinition() {
    System.out.println("Violin: A String Instrument");
  }
  
//Overridden method
  @Override public void playIt() {
    System.out.println("Use the bow to play a Violin");
  }
}

//Test the above code
public class TestInstruments {
  public static void main(String[] args) {
    StringInstruments si = new ClassicalViolin();
    //Calls the static method of the reference type 
    si.superDefinition();
    
    //Calls the overridden method of the reference object
    si.playIt();
    
    //Accesses the static variable of the reference type 
    System.out.println(si.types);
    
    //Accesses the instance variable of the reference type
    System.out.println(si.wholesaleManufacturer);
    
    //Calls to static methods and static variables 
    //should be made using the classname to avoid confusion
    StringInstruments.superDefinition();
    ClassicalViolin.superDefinition();
    System.out.println(StringInstruments.types);
    System.out.println(ClassicalViolin.types);
    
    //Prints the instance variable defined in ClassicalViolin
    System.out.println(new ClassicalViolin().wholesaleManufacturer);
    
  }
}

Thursday, February 5, 2009

Binary search tree implementation in Java using generics

Binary tree is a data structure in which each node has atmost 2 child subtree's, each of which is a binary tree. The child subtree's are called left and right.

A Binary search tree(BST) is a binary tree in which each node has a value, the node values of the left subtree contains only values less than the node value and the node values of the right subtree contains only values greater than the node value. The search tree could allow duplicate values, depending on the implementation.

Following is my implementation of binary search tree in Java with generics.

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

/**
* Implements an unbalanced binary search tree.
*/
public class MyTree<T extends Comparable<T>> {
Node<T> root;

/**
* Construct the tree.
*/
public MyTree(T elem) {
root = new Node<T>(elem,null,null);
}

/**
* Insert into the tree.
* @param elem is the item to insert.
* @throws IllegalArgumentException if elem is already present.
*/
public void add(T elem) {
Node<T> node = new Node<T>(elem,null,null);
insertNode(root,node);
}

/**
* Internal method to insert into a subtree.
* @param subTree is the subtree.
* @param newNode is the new node to be inserted.
* @return the new subtree.
* @throws IllegalArgumentException if newNode is already present.
*/
private Node<T> insertNode(Node<T> subTree, Node<T> newNode) {

if (subTree == null) {
subTree = newNode;
} else if ((subTree.elem).compareTo(newNode.elem) < 0){
subTree.rightChild = insertNode(subTree.rightChild, newNode);
} else if ((subTree.elem).compareTo(newNode.elem) > 0){
subTree.leftChild = insertNode(subTree.leftChild, newNode);
} else {
throw
new IllegalArgumentException("Duplicate Element " + newNode.elem);
}
return subTree;
}

/**
* Remove from the tree.
* @param item is the item to remove.
* @throws IllegalArgumentException if item is not found.
*/
public void delete(T item) {
this.deleteNode(root,item);
}

/**
* Internal method to delete a node.
* @param subTree is the subtree.
* @param item is the item to be deleted.
* @return the new subtree.
* @throws IllegalArgumentException if the item is not present.
*/
private Node<T> deleteNode(Node<T> subtree, T item) {
//Search for the node first
if (subtree != null) {
if ((subtree.elem).compareTo(item) < 0) {
subtree.rightChild = deleteNode(subtree.rightChild, item);
} else if ((subtree.elem).compareTo(item) > 0) {
subtree.leftChild = deleteNode(subtree.leftChild, item);
} else {
/* Found a match.
* There are 3 possibilities:
* Node is leaf:
* Easy, Just delete the node but this is implicitly
* handled as part of node has 1 child (see below)
* Node has 1 child:
* Delete the node and put the child node in its place
* Node has 2 children:
* Find the leftmost child in the right subtree,
* replace the node to be deleted with this child.
* Then delete that child node.
*/
if ((subtree.leftChild != null) && (subtree.rightChild != null)) {
//Node has 2 children
//Find the leftmost child of the right subtree and
//make it the current node, then delete the
//leftmost child of the right subtree
Node<T> node = findLeftmostChild(subtree.rightChild);
subtree.elem = node.elem;
subtree.rightChild = deleteNode(subtree.rightChild,node.elem);
} else if (subtree.leftChild != null) {
//Node has only 1 child i.e. left child
subtree = subtree.leftChild;
} else {
//Node can either have no children or just have 1 right child
subtree = subtree.rightChild;
}
}

} else{
//No match
throw new IllegalArgumentException("No such element");
}
return subtree;
}

/**
* Internal method to find the leftmost child.
* @param subtree is the subtree.
* @return the leftmost child.
*/
private Node<T> findLeftmostChild(Node<T> subtree){
assert (subtree != null);
while (subtree.leftChild != null) {
subtree = subtree.leftChild;
}
return subtree;
}

/**
* Method to traverse the tree in depth first order.
* @return the List of elements in the tree in depth first order.
*/
public List<T> depthFirstTraversal() {
List<T> l = new ArrayList<T>();
Stack<Node<T>> s = new Stack<Node<T>>();
s.push(root);
while (!s.isEmpty()){
Node<T> node = s.pop();
l.add(node.elem);
if (node.rightChild != null) {
s.push(node.rightChild);
}
if (node.leftChild != null) {
s.push(node.leftChild);
}
}
return l;
}

/**
* Method to traverse the tree in breadth first order
* @return the List of elements in the tree in breadth first order.
*/
public List<T> breadthFirstTraversal() {
List<T> l = new ArrayList<T>();
Queue<Node<T>> q = new LinkedList<Node<T>>();
q.add(root);
while (!q.isEmpty()) {
Node<T> node = q.poll();
l.add(node.elem);
if (node.leftChild != null) {
q.add(node.leftChild);
}
if (node.rightChild != null) {
q.add(node.rightChild);
}
}
return l;
}

/**
* Method to find an item in a subtree.
* @param item is item to search for.
* @return node containing the matched item.
*/
public Node<T> findNode(T item) {
if (item == null) return null;
Node<T> current = root;
while ((current.elem).compareTo(item) != 0) {
if ((current.elem).compareTo(item) > 0) {
current = current.leftChild;
} else if ((current.elem).compareTo(item) < 0) {
current = current.rightChild;
}
if (current == null) return null;
}
return current;

}

//Test it
public static void main(String[] args) {
MyTree<Integer> tree = new MyTree<Integer>(20);
tree.add(30);
tree.add(10);
tree.add(15);
tree.add(24);
tree.add(36);
//tree.add(30);

List<Integer> l = tree.depthFirstTraversal();
System.out.println("Depth First Order");
printTree(l);
l = tree.breadthFirstTraversal();
System.out.println("Breadth First Order");
printTree(l);

tree.delete(30);
System.out.println("Tree after deleting a node");
l = tree.depthFirstTraversal();
printTree(l);
}

//Method to print tree
public static <T> void printTree(List<T> l) {
for(T i: l) {
System.out.println(i);
}
}

}

/**
* Basic node stored in binary search trees
*/
class Node<T extends Comparable<T>>{
T elem;
Node<T> leftChild;
Node<T> rightChild;

Node(T elem, Node<T> left, Node<T> right){
this.elem = elem;
leftChild = left;
rightChild = right;
}
}




Note:
I did not use google-code-prettify to highlight my code as it eats up types (generic and actual) in the angle braces.
More information about BST can be found here.