/*
 * WordTreeBag.java
 * Created on Feb 24, 2005
 */
package word;

/**
 * A tree-based implementation of WordBag.
 */
public final class WordTreeBag implements WordBag {

    private WordNode root;
    
    public WordTreeBag() {}
    
    public WordCount add(String str) {
        WordNode current = root, prev = null;
        int compare = 0;
        
        while (current != null) {
            compare = str.compareToIgnoreCase(current.word());
            
            if (compare == 0) {
                current.incrementCount();
                return current;
            } else {
                prev = current;
                if (compare <  0) current = current.left;
                else              current = current.right;
            }                  
        }
        
        // if we reached this point, it means the string
        // is not in the tree, so let's add it
        WordNode node = new WordNode(str);
        if      (prev == null) root = node;
        else if (compare < 0)  prev.left = node;
        else                   prev.right = node;
        return node;
    }
    
    private static class WordNode extends WordCount {
        private WordNode left = null, right = null;
        
        private WordNode(String word) {
            super(word);
        }  
    }

}