// Copyright 2000 Jonathan White 
// Use/modify this however you want, just keep this and the previous line

package mt.util;
import java.util.*;
/** This class is a four-way trie for strings. The trie is built
    as strings are added to the object. Searched can be done on
    the struture to determine a full or partial match on a specified
    String. Searching is 4N (~N); Inserting is 4N as well. N is the
    length of the key. 
 */
public class FourWayTrie extends Object{
    protected TrieNode root = new TrieNode(4);

    /** Adds a string to the trie.
	@param key String to be add to the trie
	@return None
     */
    public void put(String key){
	int depth = 0;
	byte[] k = key.getBytes();
	TrieNode current = root;
	for(int i = 0; i < k.length; i++){
	    //buffer the first four 2bits
	    byte b = k[i];
	    for(int j=6; j >=0; j-=2){
		//get the location
		int loc = (b >>> j) & 0x3;
		//check the child to see if it is null;
		if(current.children[loc] == null)
		    current.children[loc] = new TrieNode(4);
		current = current.children[loc];
		depth++;
	    }
	}
	current.marker = true;
    }

    /** Find the longest String in the trie that will match from the begining
	of the key
	@param key String that will be searched on.
	@return Length of the match. If the key is SERVERROOT
	and only SERVER matches then 6 will be returned <p>
	-1 if no match
      */
    public int match(String key){
	byte[] k = key.getBytes();
	TrieNode current = root;
	int last = -1;
	int depth = 0;

    MATCH:
	while((current != null) && (depth < k.length)){
	    byte b = k[depth];
	    for(int j =6; j >=0; j-=2){
		int loc = (b >>> j) & 0x3;
		if(current.children[loc] == null){
		    break MATCH;
		}
		current = current.children[loc];
	    }
	    depth++;
	    if(current.marker)
		last = depth;
	    
	}
	return last;
    }
}

class TrieNode{
    TrieNode[] children = null;
    boolean marker = false;
    TrieNode(int nChildren){
	children = new TrieNode[nChildren];
    }   
}