## Friday, December 11, 2015

### Ternary Search Tries TSTs Character based Operations - Java

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(){
String string = "";
findKeys(root, al, string);
return al;
}

private void findKeys(Node n, Queue<String> al, String s){
if(n==null)return;
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){
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);
```        }
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;

//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