Friday, December 11, 2015

Ternary Search Tries TSTs Character based Operations - Java

Additional functions added -

1. Iterable<String> keys()                   - all keys

2. Iterable<String> keysWithPrefix(String s) - keys having s as a prefix 

3. String longestPrefixOf(String s)          - longest key that is a prefix of s

Source:


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


public class TSTFunctions<T> {
    class Node{
        char c;
        T v;
        Node left, mid, right;
        
        Node(){}
        Node(char c){this.c = c;}
        Node(T v){this.v = v;}
        Node(char c, T v){this.c = c;this.v = v;}
    }
    
    Node root; 
    
    public void add(String s, T value){ 
       root = add(root, s, 0, value);
    }
    
    private Node add(Node n, String s, int i, T value){  
        if(n==null){ 
            n = new Node(s.charAt(i));
            if(i==s.length()-1){n.v = value; return n;}
        }
        if(s.charAt(i)==n.c){
            if(i==s.length()-1){n.v = value; return n;}
            n.mid = add(n.mid, s, i+1, value);
        }
        else if(s.charAt(i)<n.c){
            n.left = add(n.left, s, i, value);
        }
        else{
            n.right = add(n.right, s, i, value);
        }
        return n;
    }
    
    public boolean findKey(String s){ 
        return findKey(root, s, 0); 
    }
    
    private boolean findKey(Node n, String s, int i){  
        if(n==null) return false;
        if(i==s.length()-1){
            if(n.c==s.charAt(i)){
                if(n.v!=null){System.out.println(n.v); return true;} 
                else {
                    return false;
                }
            }
        }else if(i>s.length())return false; 
        if(s.charAt(i)==n.c){
            return findKey(n.mid, s, i+1);
        }
        else if(s.charAt(i)<n.c){
            return findKey(n.left, s, i);
        }
        else {
            return findKey(n.right, s, i);
        }        
    }
    
    public void delete(String s){
        delete(root, s, 0);
    }
    
    private boolean delete(Node n, String s, int i){
        if(n==null) return false;
        if(i==s.length()-1){
            if(n.c==s.charAt(i)){
                if(n.v!=null){n.v = null;return true;}
                else return false;
            }
        }else if(i>s.length())return false; 
        
        boolean r;
        if(s.charAt(i)==n.c){
            if((r=delete(n.mid, s, i+1))){ 
                if(n.mid.v == null && n.mid.left == null 
                   && n.mid.mid == null && n.mid.right == null)n.mid = null;
            }
        }else if(s.charAt(i)<n.c){
            if((r=delete(n.left, s, i))){ 
                if(n.left.v == null && n.left.left==null 
                   && n.left.mid == null && n.left.right == null)n.left = null;
            }
        }else{
            if((r=delete(n.right, s, i))){ 
                if(n.right.v == null && n.right.left == null 
                   && n.right.mid == null && n.right.right == null)n.right = null; 
            } 
        }
        return r;
    }
    
    public Iterable<String> keys(){
        Queue<String> al = new LinkedList<>();
        String string = "";
        findKeys(root, al, string);  
        return al;
    }
    
    private void findKeys(Node n, Queue<String> al, String s){
        if(n==null)return;
        if(n.v!=null){al.add(s+n.c);}
        findKeys(n.left, al, s);
        
        String s2 = s+n.c;
        findKeys(n.mid, al, s2);
        
        findKeys(n.right,al, s);
    }
    
    public Iterable<String> keysWithPrefix(String prefix){
        Queue<String> al = new LinkedList<>();
        String string = "";
        System.out.println("\n\nFinding keys with prefix \""+prefix+"\"\n\n");
        findKeysP(root, al, string, prefix);  
        return al;
    }
    
    private void findKeysP(Node n, Queue<String> al, String s, String p){
        if(n==null)return;
        System.out.println("Working with string \""+s+"\" with prefix \""+p+"\"");
        if(s.length()<=p.length() && s.length()!=0 && s.charAt(s.length()-1)!=p.charAt(s.length()-1)){
            System.out.println("Above string rejected");
            return;
        }
        System.out.println("Above string accepted");
        if(n.v!=null){
            if(s.length()<p.length()&&n.c==p.charAt(s.length()))al.add(s+n.c);
            else if(s.length()>p.length())al.add(s+n.c);
        }
        findKeysP(n.left, al, s, p);
        
        String s2 = s+n.c;
        findKeysP(n.mid, al, s2, p);
        
        findKeysP(n.right,al, s, p);
    }
    
    public String longestPrefixOf(String s){
        String string = "";
        System.out.println("\n\nFinding the longest prefix of \""+s+"\"\n\n"); 
        int l = longestPrefixOf(root, l=0, s);  
        return s.substring(0, l+1);
    }
    
    private int longestPrefixOf(Node n, int i, String p){ 
        if(n==null)return i-1;
        if(i>=p.length()){System.out.println("Node "+n.c+" rejected");return i-1; }
         
        int l,m=Integer.MIN_VALUE,r;
        l = longestPrefixOf(n.left, i, p);
        if(n.c==p.charAt(i)){System.out.println("Node "+n.c+" accepted"); m = longestPrefixOf(n.mid, i+1, p);}
        r = longestPrefixOf(n.right, i, p);
        return Math.max(l, Math.max(m, r));
    }
    
    public static void main(String[] args){
        TSTFunctions<Integer> tst = new TSTFunctions<>();
        String s = "she sells seashells by the sea the shells she sells are surely seashells";
        String a[] = s.split(" ");
        
        int i = 0;
        for(String ss:a)tst.add(ss, i++); 
        
        //All keys
        for(String ss:tst.keys())System.out.println(ss);
        
        //Keys with prefix
        for(String ss:tst.keysWithPrefix("sea")) System.out.println(ss); 
        for(String ss:tst.keysWithPrefix("sh")) System.out.println(ss);
        
        //Longest Prefix Of
        System.out.println(tst.longestPrefixOf("are"));
        System.out.println(tst.longestPrefixOf("seashel"));
        System.out.println(tst.longestPrefixOf("seaXshell"));
        System.out.println(tst.longestPrefixOf("seashells"));
        System.out.println(tst.longestPrefixOf("seashellsxx"));
    }
}

Output:

are
by
sea
seashells
sells
she
shells
surely
the


Finding keys with prefix "sea"


Working with string "" with prefix "sea"
Above string accepted
Working with string "" with prefix "sea"
Above string accepted
Working with string "" with prefix "sea"
Above string accepted
Working with string "a" with prefix "sea"
Above string rejected
Working with string "b" with prefix "sea"
Above string rejected
Working with string "s" with prefix "sea"
Above string accepted
Working with string "s" with prefix "sea"
Above string accepted
Working with string "se" with prefix "sea"
Above string accepted
Working with string "se" with prefix "sea"
Above string accepted
Working with string "sea" with prefix "sea"
Above string accepted
Working with string "seas" with prefix "sea"
Above string accepted
Working with string "seash" with prefix "sea"
Above string accepted
Working with string "seashe" with prefix "sea"
Above string accepted
Working with string "seashel" with prefix "sea"
Above string accepted
Working with string "seashell" with prefix "sea"
Above string accepted
Working with string "sel" with prefix "sea"
Above string rejected
Working with string "sh" with prefix "sea"
Above string rejected
Working with string "s" with prefix "sea"
Above string accepted
Working with string "su" with prefix "sea"
Above string rejected
Working with string "" with prefix "sea"
Above string accepted
Working with string "t" with prefix "sea"
Above string rejected
sea
seashells


Finding keys with prefix "sh"


Working with string "" with prefix "sh"
Above string accepted
Working with string "" with prefix "sh"
Above string accepted
Working with string "" with prefix "sh"
Above string accepted
Working with string "a" with prefix "sh"
Above string rejected
Working with string "b" with prefix "sh"
Above string rejected
Working with string "s" with prefix "sh"
Above string accepted
Working with string "s" with prefix "sh"
Above string accepted
Working with string "se" with prefix "sh"
Above string rejected
Working with string "sh" with prefix "sh"
Above string accepted
Working with string "she" with prefix "sh"
Above string accepted
Working with string "shel" with prefix "sh"
Above string accepted
Working with string "shell" with prefix "sh"
Above string accepted
Working with string "s" with prefix "sh"
Above string accepted
Working with string "su" with prefix "sh"
Above string rejected
Working with string "" with prefix "sh"
Above string accepted
Working with string "t" with prefix "sh"
Above string rejected
shells


Finding the longest prefix of "are"


Node a accepted
Node r accepted
Node e accepted
are


Finding the longest prefix of "seashel"


Node s accepted
Node e accepted
Node a accepted
Node s accepted
Node h accepted
Node e accepted
Node l accepted
Node l rejected
seashel


Finding the longest prefix of "seaXshell"


Node s accepted
Node e accepted
Node a accepted
sea


Finding the longest prefix of "seashells"


Node s accepted
Node e accepted
Node a accepted
Node s accepted
Node h accepted
Node e accepted
Node l accepted
Node l accepted
Node s accepted
seashells


Finding the longest prefix of "seashellsxx"


Node s accepted
Node e accepted
Node a accepted
Node s accepted
Node h accepted
Node e accepted
Node l accepted
Node l accepted
Node s accepted

seashells

No comments:

Post a Comment