t9/trie/TrieBuilder.java

Go to the documentation of this file.

package t9.trie;

import java.util.Collection;
import java.util.TreeSet;

public class TrieBuilder {

    private TrieNode listInsert(TrieNode sibling, char letter) {
        TrieNode head = sibling;
        TrieNode trail = head;
        while (head != null) {
            if (letter == head.getLetter()) {
                break;
            }
            else if (letter < head.getLetter()) {
                TrieNode newSib = new TrieNode(letter);
                trail.setSib(newSib);
                newSib.setSib(head);
                head = newSib;
                break;
            }
            trail = head;
            head = head.getSib();
            if (head == null) {
                TrieNode newSib = new TrieNode(letter );
                trail.setSib(newSib);
                head = newSib;
            }
        }
        return head;
    }
 

    private TrieNode insertSibling(TrieNode head, char letter) {
        TrieNode sibling = head.getSib();
        if (sibling == null) {
            TrieNode newSib = new TrieNode(letter);
            head.setSib(newSib);
            head = newSib;
        }
        else {
            head = listInsert(sibling, letter );
        }
        return head;
    }



    public TrieNode addWord(TrieNode root, Pair word) {
        if (word != null) {
            TrieNode head = root;
            TrieNode trail = head;
            char letters[] = word.word.toCharArray();
            for (char letter : letters) {
                if (root == null) {
                    root = new TrieNode( letter );
                    trail = root;
                }
                else if (head == null) {
                    TrieNode newChild = new TrieNode(letter);
                    trail.setChild(newChild);
                    trail = newChild;
                }
                else if (head.getLetter() != letter){
                    head = insertSibling( head, letter );
                    trail = head;
                    head = head.getChild();
                }
                else {
                    trail = head;
                    head = head.getChild();
                }
            }
            if (head == null) {
                head = trail;
            }
            head.setEOW();
            head.setFrequency(word.frequency);
        }

        return root;
    }  

    public TrieNode buildTrie( Collection<Pair> words ) {
        TrieNode root = null;
        for (Pair word : words) {
            root = addWord(root, word);
        }
        return root;
    }

    protected void listTrie( TrieNode root, String prefix, Collection<Pair> words ) {
        String newPrefix = prefix;
        for (TrieNode curRoot = root; curRoot != null; curRoot = curRoot.getChild()) {
            // traverse down the sibling list
            TrieNode sib = curRoot.getSib();
            listTrie(sib, newPrefix, words );
            newPrefix = newPrefix + curRoot.getLetter();
            if (curRoot.isEOW()) {
                Pair pair = new Pair(newPrefix, curRoot.getFrequency());
                words.add(pair);
            }
        }
    }
    
    public TreeSet<Pair> listTrie(TrieNode root)
    {
        TreeSet<Pair> words = new TreeSet<Pair>();
        listTrie(root, "", words);
        return words;
    }

}