Binary Search Tree in Java with Generics

This post is more about generics than the actual implementation of the binary search tree. I tried to implement some of the suggestions in the developerworks articles titled "Java theory and practice: Going wild with generics". The Binary Search Tree of this example uses the first two suggestions. The rest are equally helpful though.

1. A generic factory method that allows you to avoid redundantly specifying type parameters

   public static<T extends Comparable<? super T>> BinarySearchTree<T> createTestTree() 

   Can be used as shown below.

   BinarySearchTree<Test> tree = BinarySearchTree.createTestTree();

2. By using bounded wildcards, we can now construct a tree with both the super and sub-class type objects.

   public class BinarySearchTree<T extends Comparable<? super T>> 

3. The get-put principle

   Use an extends wildcard when you only get values out of a structure, use a super wildcard when you only put values into a structure, and don't use a wildcard when you do both.

4. Wildcard capture: Use a generic method as a capture helper to workaround compiler's limitations dealing with wildcards. (refer to the article "Java theory and practice: Going wild with generics, Part 1")

Following is the complete source code

package trees;

import java.util.NoSuchElementException;

public class BinarySearchTree<T extends Comparable<? super T>> {

  private Entry<T> root;

  public BinarySearchTree() {
    root = null;
  }
  
  public static<T extends Comparable<? super T>> BinarySearchTree<T> createTestTree() {
    return new BinarySearchTree<T>();
  }

  public void insert(T value) {
    root = insert(value, root);
  }
  

  public void remove(T value) {
    root = remove(value, root);
  }

  public boolean contains(T value) {
    return valueOf(find(value, root)) != null;
  }

  private T valueOf(Entry<T> entry) {
    return entry == null ? null : entry.element;
  }

  private Entry<T> insert(T value, Entry<T> entry) {
    if (entry == null)
      entry = new Entry<T>(value);
    else if (value.compareTo(entry.element) < 0)
      entry.left = insert(value, entry.left);
    else if (value.compareTo(entry.element) > 0)
      entry.right = insert(value, entry.right);
    else
      throw new RuntimeException("Duplicate Entry : " + value.toString());
    return entry;
  }

  private Entry<T> remove(T value, Entry<T> entry) {
    if (entry == null)
      throw new NoSuchElementException("Entry not found : " + value.toString());
    if (value.compareTo(entry.element) < 0)
      entry.left = remove(value, entry.left);
    else if (value.compareTo(entry.element) > 0)
      entry.right = remove(value, entry.right);
    else {
      // Entry found.
      if (entry.left != null && entry.right != null) {

        // Replace with in-order successor (the left-most child of the right subtree)
        entry.element = findMin(entry.right).element;
        entry.right = removeInorderSuccessor(entry.right);

        // Replace with in-order predecessor (the right-most child of the left subtree)
        // entry.element = findMax(entry.left).element;
        // entry.left = removeInorderPredecessor(entry.left);
      } else
        entry = (entry.left != null) ? entry.left : entry.right;
    }
    return entry;
  }

  private Entry<T> removeInorderSuccessor(Entry<T> entry) {
    if (entry == null)
      throw new NoSuchElementException();
    else if (entry.left != null) {
      entry.left = removeInorderSuccessor(entry.left);
      return entry;
    } else
      return entry.right;
  }

  private Entry<T> removeInorderPredecessor(Entry<T> entry) {
    if (entry == null)
      throw new NoSuchElementException();
    else if (entry.right != null) {
      entry.right = removeInorderPredecessor(entry.right);
      return entry;
    } else
      return entry.left;
  }

  private Entry<T> findMin(Entry<T> entry) {
    if (entry != null)
      while (entry.left != null)
        entry = entry.left;

    return entry;
  }

  private Entry<T> findMax(Entry<T> entry) {
    if (entry != null)
      while (entry.right != null)
        entry = entry.right;

    return entry;
  }

  private Entry<T> find(T value, Entry<T> entry) {
    while (entry != null) {
      if (value.compareTo(entry.element) < 0)
        entry = entry.left;
      else if (value.compareTo(entry.element) > 0)
        entry = entry.right;
      else
        return entry;
    }

    return null;
  }

  private void printInOrder(Entry<T> entry) {
    if (entry != null) {
      printInOrder(entry.left);
      System.out.println(entry.element);
      printInOrder(entry.right);
    }
  }

  public void printInOrder() {
    printInOrder(root);
  }

  private static class Entry<T extends Comparable<? super T>> {
    T element;
    Entry<T> left;
    Entry<T> right;

    Entry(T theElement) {
      element = theElement;
      left = right = null;
    }
  }

  private static class Test implements Comparable<Test> {
    private String value;

    public Test(String value) {
      this.value = value;
    }

    public String toString() {
      return value;
    }

    @Override
    public int compareTo(Test o) {
      return this.value.compareTo(o.toString());
    }
  }

  private static class Test1 extends Test {
    public Test1(String value) {
      super(value);
    }
  }

  public static void main(String[] args) {
    BinarySearchTree<Test> tree = BinarySearchTree.createTestTree();
    int size = 20;

    for (int i = 0; i <= size; i++) {
      tree.insert(new Test1(String.valueOf(i)));
    }

    tree.insert(new Test1("100"));
    tree.remove(new Test1("10"));
    tree.remove(new Test1(String.valueOf(15)));
    tree.remove(new Test1(String.valueOf(20)));
    tree.printInOrder();
    System.out.println("Contains (10) : " + tree.contains(new Test1("10")));
    System.out.println("Contains (11) : " + tree.contains(new Test1(String.valueOf(11))));
  }

}

References

• Java theory and practice: Going wild with generics, Part 1
  
• Java theory and practice: Going wild with generics, Part 2
• Java theory and practice: Generics gotchas

Cricular Linked List in Java

Had to implement a circular linked list recently. Here's my take, suggestions are welcome. The list can be parameterized for any type which has a meaningful equals method defined. The main method shows a sample usage of the Circular linked list with the String type. Only add, remove and size method are implemented.

There's more ...

package algo;

import java.util.NoSuchElementException;

public class CircularLinkedList<E> {
 private Entry<E> head;

 // Last element of the list. tail.next = head
 private Entry<E> tail;

 private int size = 0;

 /**
  * Class to hold the individual elements.
  * @param <E>
  */
 private static class Entry<E> {
  E element;

  Entry<E> next;

  Entry(E element, Entry<E> next) {
   this.element = element;
   this.next = next;
  }

  Entry(E element) {
   this.element = element;
  }
 }

 public CircularLinkedList() {
  head = null;
 }

 /**
  * Remove obj from the circular linked list and return the removed object
  * @param obj
  * @return
  */
 public E remove(E obj) {
  if (head == null || tail == null)
   throw new NoSuchElementException();
  Entry<E> current = head, temp = head, found = null;
  if (obj.equals(head.element)) {
   if (head.next == head) {
    found = head;
    head = null;
    tail = null;
    size--;
    return found.element;
   } else {
    found = head;
    temp = tail;
   }
  } else {
   current = head.next;
   while (current != head) {
    if (current.element.equals(obj)) {
     found = current;
     break;
    }
    temp = current;
    current = current.next;
   }
  }
  if (found == null) {
   throw new NoSuchElementException(obj.toString());
  }
  E result = found.element;
  temp.next = found.next;
  found.next = null;
  found.element = null;
  size--;
  return result;
 }

 /**
  * Add obj to the circular linked list.
  * @param obj
  */
 public void add(E obj) {
  Entry e = new Entry(obj);
  if (head == null) {
   size++;
   head = e;
   head.next = head;
   tail = head;
   return;
  }
  size++;
  e.next = head;
  head = e;
  tail.next = head;
 }

 /**
  * Size of the list.
  * @return
  */
 public int size() {
  return size;
 }

 public static void main(String[] args) {
  CircularLinkedList<String> list = new CircularLinkedList<String>();
  list.add("One");
  list.add("Two");
  list.add("Three");
  list.add("Four");

  System.out.println(list.remove("Three"));
  System.out.println(list.remove("Two"));
  System.out.println(list.remove("One"));
  System.out.println(list.remove("Four"));
  System.out.println(list.remove("Four"));

 }
}

Detecting Code Smells With Eclipse and CheckStyle

In a new article "Automation for the people: Continual refactoring" as a part of the "Automation for the people" series, Paul Duvall discusses the use of static code analysis tools to identify code smells and suggested refactorings. The article shows how to

• Reduce conditional complexity code smells by measuring cyclomatic complexity using CheckStyle and providing refactorings such as Replace Conditional with Polymorphism
• Remove duplicated code code smells by assessing code duplication using CheckStyle and providing refactorings such as Pull Up Method
• Thin large class code smells by counting source lines of code using PMD (or JavaNCSS) and providing refactorings such as Extract Method
• Wipe out too many imports code smells by determining a class's efferent coupling using CheckStyle (or JDepend) and providing refactorings such as Move Method

There's MoreThe following is a short list of static code analysis tools available for Java

• CheckStyle
• PMD
• FindBugs
• JavaNCSS
• JDepend

This post describes how to identify common code smells using CheckStyle and Eclipse. Checkstyle has a useful eclipse plugin. Installing the plugin is simple. In Eclipse Ganymede,

1. Go to Help->Software Updates->Software Updates->Available Software
2. Click on Add Site, and add http://eclipse-cs.sourceforge.net/update to the sites list
3. Select the new site and click Install

Once CheckStyle plugin is install, running the tool is quite simple. Usage is well documented in the plugin site. The following are some Code smells which can be detected using Checkstyle, along with the suggested refactorings (from the "Smells to Refactorings Quick Reference Guide"). The description of the refactorings can be found at refactoring.com and refactoring to patterns catalog. The center column shows the CheckStyle configuration option in the plugin GUI.

Conditional complexity	Metrics->Cyclomatic Complexity	Introduce Null Object Move Embellishment to Decorator Replace Condidtional Logic with Strategy Replace State-Altering Conditionals with State
Duplicated code	Duplicates->Strict Duplicate Code	Chain Constructors Extract Composite Extract Method Extract Class Form Template Method Introduce Null Object Introduce Polymorphic Creation with Factory Method Pull Up Method Pull Up Field Replace One/Many Distinctions with Composite Substitue Algorithm Unify Interfaces with Adapter
Long method	Size Violations->Maximum Method Length	Extract Method Compose Method Introduce Parameter Object Move Accumulation to Collecting Parameter Move Accumulation to Visitor Decompose Conditional Preserve Whole Object Replace Conditional Dispatcher with Command Replace Conditional Logic with Strategy Replace Method with Method Object Replace Temp with Query

Web Service Best Practices

Bobby Woolf at IBM has a list of articles with best practices for working with Web Services. Most of these links are IBM resources.

• "Best practices for Web services" series: Part 1 through Part 12 (developerWorks)
• "Web Services Architectures and Best Practices" (developerWorks)
• "Best practices for Web services versioning" (developerWorks)
• "Best Practices and Web services Profiles" (developerWorks)
• "Web services performance best practices" (WAS InfoCenter)
• "Web services migration best practices" (WAS InfoCenter)
• WebSphere Version 6 Web Services Handbook Development and Deployment (Redbook)
• Web Services Handbook for WebSphere Application Server 6.1 (Redbook)
• IBM WebSphere DataPower SOA Appliances Part III: XML Security Guide (Redbook)
• "Web services with SOAP over JMS in IBM WebSphere Process Server or IBM WebSphere Enterprise Service Bus" (developerWorks)
• "Web services SOAP/JMS protocol" (WAS InfoCenter)
• "HTTP and JMS transport methods" (RAD InfoCenter)

To these I'd just like to add Implementing REST Web Services: Best Practices and Guidelines, which I find useful for implementing REST based web services.