i am trying to make basic object oriented suffix tree console program and i dont know how to make boolean suffix(String s) method. My actual suffix method doesn't work properly. Finally it should looks like :
Node is for object, SuffixTree create tree and have methods for that tree, TestTree have main method for testing
Node
package trie3;
import java.util.HashMap;
import java.util.Map;
class Node{
private final char currentValue;
Map<Character,Node> children;
Node(){
this.currentValue = '#';
this.children = new HashMap<Character,Node>();
}
Node(char currentValue){
this.currentValue = currentValue;
this.children = new HashMap<Character,Node>();
}
char getValue(){
return this.currentValue;
}
void addChild(Node c){
this.children.put(c.getValue(),c);
}
boolean hasChild(Node c){
return this.children.containsKey(c.getValue());
}
Node getChild(Node c){
return this.children.get(c.getValue());
}
public String toString(){
char currentValue = this.getValue();
StringBuffer keys = new StringBuffer();
for(char key:this.children.keySet()){
keys.append("Current key:"+key+"\n");
}
return "Current value:"+currentValue+"\n"+
"Keys:"+keys.toString();
}
}
SuffixTree
package trie3;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import trie3.Node;
public class SuffixTree{
private Node root;
private void log(Object l){
System.out.println(l);
}
/*
* Helper method that initializes the suffix tree
*/
private Node createSuffixTree(String source,Node root){
for(int i=1;i<source.length();i++){
Node parent = new Node(source.charAt(i));
if(root.hasChild(parent)){
parent = root.getChild(parent);
}
Node current = parent;
for(int j=i+1;j<source.length();j++){
Node temp = new Node(source.charAt(j));
if(current.hasChild(temp)){
temp = current.getChild(temp);
}else{
current.addChild(temp);
}
current = temp;
}
root.addChild(parent);
}
return root;
}
/*
Creates the suffix tree from the given string
*/
public SuffixTree(String source){
this.root = createSuffixTree(source,new Node()); // jj to je vychozi s # jj jo
}
void printMap(Map<Character,Node> map){ // vytiskne vsechny znaky potomku daneho suffixu takze hahaa -- pokud budes od n tak to bude a h a a # tusim teda
for(char c:map.keySet()){
System.out.println("Current node has child: " +c);
}
}
boolean infix(String target){ // infix method
Map<Character,Node> rootChildren = this.root.children;
for(char c:target.toCharArray()){
if(rootChildren.containsKey(c)){
rootChildren = rootChildren.get(c).children;
}else{
return false;
}
}
return true;
}
boolean suffix(String target){ // like infix but last char must be leaf
Map<Character,Node> rootChildren = this.root.children;
for(int i=0;i<target.length()-1;i++){
printMap(rootChildren);
char c = target.charAt(i);
if(rootChildren.containsKey(c)){
rootChildren = rootChildren.get(c).children;
}else if(rootChildren == null){
System.out.println("hash");
return true;
}else{
return false;
}
}
return false;
}
testTree
public class testTree {
public static void main(String[] args){
SuffixTree sTree = new SuffixTree("hahaa");
//test suffix
if(sTree.infix("ha")){
System.out.println(":)");
}
else{
System.out.println(":(");
}
if(sTree.suffix("ha")){ // true only for a,ha,haa,ahaa
System.out.println(":)");
}
else{
System.out.println(":(");
}
//test substring
// sTree.printMap();
}
}