Symbol Table

ST Implementation

1. Un-Ordered List
    Search Complexity: N (average N/2)
    Insert Complexity: N

2. Ordered List
    Search: N Log N
    Insert: N (average N/2)

3. BST
    Search: N (average 1.4 log N)
    insert: N (average 1.4 log N)

/*
 *  Symbol table implementation using Linked list
 */

import java.util.Iterator;

public class LinkedListST<Key, Value> implements Iterable<Key> {

 private Node root;

 public LinkedListST() {
 }

 @Override
 public Iterator<Key> iterator() {
  return new STIterator();
 }

 private class STIterator implements Iterator<Key> {

  Node current = root;

  @Override
  public boolean hasNext() {
   return current != null;
  }

  @Override
  public Key next() {
   Key key = current.key;
   current = current.next;

   return key;
  }

  @Override
  public void remove() throws UnsupportedOperationException {
   throw new UnsupportedOperationException();
  }
 }

 public class Node {
  private Key key;
  private Value value;
  private Node next;
 }

 public void put(Key key, Value value) {
  Node current = root;

  while (current != null) {
   if (current.key.equals(key)) {
    current.value = value;
    return;
   }
   current = current.next;
  }
  Node temp = new Node();
  temp.key = key;
  temp.value = value;
  temp.next = root;

  root = temp;
 }

 public Value get(Key key) {
  Node current = root;

  while (current != null) {
   if (current.key.equals(key))
    return current.value;

   current = current.next;
  }
  return null;
 }

 public boolean contains(Key key) {
  return get(key) != null;
 }
}


import java.util.Iterator;

/**
 * Liked List Symbol table test
 */

public class LinkedListSTTest {

 /**
  * @param args
  */
 public static void main(String[] args) {
  System.out.println("BinarySearchBTTest::main");

  LinkedListST<String, Integer> bsst = new LinkedListST<String, Integer>();

  bsst.put("Ramesh", 90);
  bsst.put("Suguna", 80);
  bsst.put("Haasini", 99);
  bsst.put("Saravanan", 80);
  bsst.put("Mahisa", 75);
  bsst.put("Reethu", 60);

  bsst.put("Ramesh", 50);

  Iterator<String> iterator = bsst.iterator();

  while (iterator.hasNext()) {

   String name = iterator.next();
   Integer marks = bsst.get(name);

   System.out.println("name = " + name + ", marks = " + marks);
  }

 }

}

/****
 * 
 *  Sorted symbol table implementation using array & BST
 * 
 */

import java.util.Iterator;
import java.util.NoSuchElementException;

public class BinarySearchST<Key extends Comparable<Key>, Value> implements
  Iterable<Key> {

 private static final int ST_SIZE = 10;
 
 private Key[] keys;
 private Value[] values;
 
 private int N;
 
 public BinarySearchST(){
  this(ST_SIZE);
 }
 
 private BinarySearchST(final int capacity){
  keys = (Key[]) new Object[capacity];
  values = (Value[]) new Comparable[capacity];
 }
 
 private void resize(int capacity){
  Key[] tempKeys = (Key[]) new Object[capacity];
  Value[] tempValues = (Value[]) new Comparable[capacity];
  
  for (int i = 0; i < keys.length; i++) {
   tempKeys[i] = keys[i];
   tempValues[i] = values[i];
  }
  
  keys = tempKeys;
  values = tempValues;
 }
 
 public void put(Key key, Value value){
  
  if(N == keys.length) resize(keys.length * 2);
  
  int index = search(key);
  if(index >= 0){
   values[index] = value;
   return;
  }
  
  int i = N;
  
  while(i>0 && key.compareTo(keys[i-1]) < 0){
   keys[i] = keys[i-1];
   values[i] = values[i-1];
   i--;
  }
  
  keys[i] = key;
  values[i] = value;
  N++;
  
 }
 
 public Value get(Key key){
  int index = search(key);
  if(index>=0){
   return values[index];
  }
  
  return null;
 }
 
 private int search(Key key){
  int lo = 0, hi = N-1;
  
  int mid = lo+(hi-lo)/2;
  
  while(lo<=hi){
   int val = key.compareTo(keys[mid]);
   
   if(val < 0){
    hi = mid-1;
   }else if(val > 0){
    lo = mid+1;
   }else{
    return mid;
   }
  }
  return -1;
 }
 
 @Override
 public Iterator<Key> iterator() {
  return new BSSTIterator();
 }
 
 private class BSSTIterator implements Iterator<Key>{

  private int index = 0;
  
  @Override
  public boolean hasNext() {
   return index < N;
  }

  @Override
  public Key next() {
   if(!hasNext()) throw new NoSuchElementException();
   return keys[index++];
  }

  @Override
  public void remove() throws UnsupportedOperationException{
   throw new UnsupportedOperationException();
  }
  
 }
}



/*
 *  Binary Search Symbol Table Test
 * 
 */


import java.util.Iterator;


public class BinarySearchSTTest {

 /**
  * @param args
  */
 public static void main(String[] args) {
  System.out.println("BinarySearchBTTest::main");

  LinkedListST<String, Integer> bsst = new LinkedListST<String, Integer>();

  bsst.put("Ramesh", 90);
  bsst.put("Suguna", 80);
  bsst.put("Haasini", 99);
  bsst.put("Saravanan", 80);
  bsst.put("Mahisa", 75);
  bsst.put("Reethu", 60);

  bsst.put("Ramesh", 50);

  Iterator<String> iterator = bsst.iterator();

  while (iterator.hasNext()) {

   String name = iterator.next();
   Integer marks = bsst.get(name);

   System.out.println("name = " + name + ", marks = " + marks);
  }
 }

}

/*
 * Symbol table implementation using BST
 * 
 */

import java.util.Iterator;

public class BSTSymbolTable<Key extends Comparable<Key>, Value> implements
  Iterable<Key> {

 private Node root;

 public class Node {
  private Key key;
  private Value value;
  private Node left;
  private Node right;

  public Node(Key key, Value value) {
   this.key = key;
   this.value = value;
  }
 }

 public Value get(Key key) {

  Node current = root;

  while (current != null) {
   int val = key.compareTo(current.key);
   if (val < 0) {
    current = current.left;
   } else if (val > 0) {
    current = current.right;
   } else
    return current.value;
  }

  return null;
 }

 public void put(Key key, Value value) {
  root = put(root, key, value);
 }

 private Node put(Node node, Key key, Value value) {
  if (node == null)
   return new Node(key, value);

  int index = key.compareTo(node.key);
  if (index < 0) {
   node.left = put(node.left, key, value);
  } else if (index > 0) {
   node.right = put(node.right, key, value);
  } else {
   node.value = value;
  }

  return node;
 }

 public Iterator<Key> iterator() {
  return null;
 }
}


/*
 *  BSTSymbolTableTest
 * 
 */

public class BSTSymbolTableTest {

 /**
  * @param args
  */
 public static void main(String[] args) {
  System.out.println("BSTSymbolTableTest::main");

  BSTSymbolTable<String, Integer> table = new BSTSymbolTable<String, Integer>();

  table.put("Ramesh", 90);

  table.put("Anandhan", 80);

  System.out.println(table.get("Ramesh"));

 }

}