Friday, October 24, 2014

Ordered Symbol Table : Fixed Capacity Implementation [Java]

The symbol table supports the following functions:

void put(Key key, Value val)                      put key-value pair into the table
                                                                     (remove key from table if value is null)

Value get(Key key)                                    value paired with key
                                                                     (null if key is absent)

void delete(Key key)                                  remove key (and its value) from table

boolean contains(Key key)                          is there a value paired with key?

boolean isEmpty()                                      is the table empty?

int size()                                                     number of key-value pairs

Key min()                                                   smallest key

Key max()                                                  largest key

Key floor(Key key)                                    largest key less than or equal to key

Key ceiling(Key key)                                 smallest key greater than or equal to key

int rank(Key key)                                      number of keys less than key

Key select(int k)                                       key of rank k

void deleteMin()                                      delete smallest key

void deleteMax()                                     delete largest key

int size(Key lo, Key hi)                              number of keys in [lo..hi]

Iterable<Key> keys(Key lo, Key hi)          keys in [lo..hi], in sorted order

Iterable<Key> keys()                               all keys in the table, in sorted order

Source:

import java.util.Arrays;

public class SymbolTable<Key extends Comparable<Key>, Value> {

    final private Key[] keys;
    final private Value[] values;
    private int size;

    public SymbolTable(int size) {
        this.keys = (Key[]) new Comparable[size];
        this.values = (Value[]) new Object[size];
    }

    private void swap(Object[] a, int b, int c) {
        Object temp = a[b];
        a[b] = a[c];
        a[c] = temp;
    }

    public void put(Key key, Value val) {
        int pos = 0;
        while (pos < size && keys[pos] != null){
            if(key.compareTo(keys[pos]) > 0) pos++; 
            else if(key.compareTo(keys[pos])==0){
                values[pos] = val; 
                return;
            }else break;
        }
        
        if (pos >= keys.length) return;
        
        if(size==keys.length)size--;
        for (int i = size; i > 0 && i > pos; --i) { 
            keys[i] = keys[i - 1];
            values[i] = values[i - 1]; 
        }
        
        keys[pos] = key;
        values[pos] = val; 
        
        size++; 
    }

    private int findIndex(Key key) {
        int lo = 0, hi = size-1;
        int mid = hi / 2;

        while (lo <= hi) {
            if (key.compareTo(keys[mid]) == 0) {
                return mid;
            } else if (key.compareTo(keys[mid]) < 0) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
            mid = (hi + lo) / 2;
        }
        return mid;
    }

    public Value get(Key key) {
        int index = findIndex(key);
        if(key.compareTo(keys[index])==0)return values[index];
        else return null;
    }

    public void delete(Key key) {
        int index = findIndex(key);
        if(key.compareTo(keys[index])!=0){
            System.out.println("Unable to delete - Key not present");
            return;
        } 
       
        for (int i = index; i+1 < size; ++i) { 
            keys[i] = keys[i+1];
            values[i] = values[i+1]; 
        } 
        keys[size-1] = null;
        values[size-1] = null;
        size--;
    }

    public Key min(){ 
        if(size>=1) return keys[0]; 
        return null;
    }
    
    public Key max(){
        if(size>=1) return keys[size-1];
        return null;
    }
    
    public boolean contains(Key key) {
        return get(key) != null;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public Iterable<Key> keys() {
        return Arrays.asList(keys);
    }
    
    void deleteMin(){
        if(size>=1) delete(keys[0]);
    }
    
    void deleteMax(){
        if(size>=1) delete(keys[size-1]);
    }
    
    public void printTable(String s){
        System.out.print("\n\n"+s+"\n"+Arrays.asList(keys));
        System.out.print("\n"+Arrays.asList(values));
    }
    
    //Find a key less than or equal to the key supplied
    public Key floor(Key key){
        int index = findIndex(key); 
        if(index>0) {
            if(key.compareTo(keys[index])<0) return keys[index-1];
            else return keys[index];
        }
        else if(index==0)return keys[0];
        else return null;
    }
    
    //Find a key greater than or equal to the key supplied
    public Key ceiling(Key key){
        int index = findIndex(key);
        if(index<size-1) {
            if(key.compareTo(keys[index])>0) return keys[index+1];
            else return keys[index];
        }
        else if(index==0) return keys[0];
        else return null;
    }
    
    /*
        The location where the key should have been - Key
        may or may not be present
    */
    public int rank(Key key){
        
        int index = findIndex(key); 
        if(keys[index].compareTo(key)==0)
            return index;
        return -1; //Not present
    }
    
    public Key select(int k){
        if(k<0 || k>=size) return null;   
        return keys[k-1]; 
    } 
    
    //If key isn't present, take floor for lo, ceiling for hi
    int size(Key lo, Key hi){
        //hi>lo doesn't make sense
        if(lo.compareTo(hi)>0){System.out.println("lo must be less than hi");return -1;}
        
        int loIndex = findIndex(lo); 
        if(loIndex>0) 
            if(lo.compareTo(keys[loIndex])<0) loIndex--; 
        
        int hiIndex = findIndex(hi);
        if(hiIndex<size-1) 
            if(hi.compareTo(keys[hiIndex])>0) hiIndex++; 
          
        return hiIndex-loIndex+1;
    }
    
    Iterable<Key> keys(Key lo, Key hi){
        //hi>lo doesn't make sense
        if(lo.compareTo(hi)>0){System.out.println("lo must be less than hi");return null;}
       
        int loIndex = findIndex(lo); 
        if(loIndex>0) 
            if(lo.compareTo(keys[loIndex])<0) loIndex--; 
        
        int hiIndex = findIndex(hi);
        if(hiIndex<size-1) 
            if(hi.compareTo(keys[hiIndex])>0) hiIndex++; 
        
        Key[] subKeys = Arrays.copyOfRange(keys, loIndex, hiIndex+1);
        return Arrays.asList(subKeys);
    }
      
    public static void main(String[] args) {
        
        //Test code
        SymbolTable<Integer, String> table = new SymbolTable<>(3);

        System.out.println("isEmpty()? = "+table.isEmpty());
        table.put(3, "Hi"); 
        System.out.println("isEmpty()? = "+table.isEmpty());
        table.put(1, "There");
        table.put(2, "Hello");
        table.printTable("Full list");
        table.put(0, "Hey");
        table.printTable("Inserting index 0");
        table.delete(0);
        table.printTable("After deleting zeroth");
        table.put(0, "Hi there");
        table.printTable("Inserting new zero");
         
        System.out.println("\n\nTesting the get operation");
        for(int i=0;i<3;++i)System.out.println(table.get(i)+" ");
        System.out.println(table.get(4));
        
        System.out.println(table.size());
        
        System.out.println(table.keys());
        
        System.out.println(table.contains(0));
        System.out.println(table.contains(5));
        
        System.out.println("Min key = "+table.min());
        System.out.println("Max key = "+table.max());
        
        table.deleteMin();
        table.printTable("After deleting min key");
        table.deleteMax();
        table.printTable("After deleting max key");
        
        System.out.println("Min key = "+table.min());
        System.out.println("Max key = "+table.max());
        
        System.out.println("Min key = "+table.min());
        System.out.println("Max key = "+table.max());
         
        System.out.println("Floor of 2 "+table.floor(2));
        System.out.println("Ceiling of 0 "+table.ceiling(0));
        
        table.put(1, "There");
        table.put(2, "Someone"); 
        table.printTable("Considering floor and ceiling ops on this table");
        System.out.println("Floor of 2 "+table.floor(2));
        System.out.println("Ceiling of 0 "+table.ceiling(0));
        
        System.out.println("Rank of 2 = "+table.rank(2));
        System.out.println("Rank of 5 = "+table.rank(5));
        
        table.put(5, "Points");
        table.printTable("Testing the table for size function");
        System.out.println("size(0, 1) = "+table.size(1, 1));
        
        System.out.println("key range "+table.keys(1, 1));
        System.out.println("key range "+table.keys(1, 5)); 
        
        System.out.println("key range "+table.keys(5, 1)); 
    }
}

Output:

isEmpty()? = true
isEmpty()? = false


Full list
[1, 2, 3]
[There, Hello, Hi]

Inserting index 0
[0, 1, 2]
[Hey, There, Hello]

After deleting zeroth
[1, 2, null]
[There, Hello, null]

Inserting new zero
[0, 1, 2]
[Hi there, There, Hello]

Testing the get operation
Hi there
There
Hello
null
3
[0, 1, 2]
true
false
Min key = 0
Max key = 2


After deleting min key
[1, 2, null]
[There, Hello, null]

After deleting max key
[1, null, null]
[There, null, null]Min key = 1
Max key = 1
Min key = 1
Max key = 1
Floor of 2 1
Ceiling of 0 1


Considering floor and ceiling ops on this table
[1, 2, null]
[There, Someone, null]Floor of 2 2
Ceiling of 0 1
Rank of 2 = 1
Rank of 5 = -1


Testing the table for size function
[1, 2, 5]
[There, Someone, Points]size(0, 1) = 1
key range [1]
key range [1, 2, 5]
lo must be less than hi
key range null 

No comments:

Post a Comment