字符串处理算法之TrieTree

package com.yan.algorithm.string;

import java.util.LinkedList;
import java.util.Queue;

public class TrieTree {

	private static int R = 256;

	private Node root = new Node();

	private class Node {

		private Node[] next = new Node[R];
		private Object value;
	}
	
	/**
	 * add value to trie tree
	 * @param key
	 * @param value
	 */
	public void put(String key, Object value) {

		root = put(root, key, value, 0);
	}

	private Node put(Node x, String key, Object value, int d) {
		if (x == null)
			return null;
		if (key.length() == d)
			return x;
		char c = key.charAt(d);
		x.next[c] = put(x.next[c], key, value, d + 1);
		return x;
	}
	
	/**
	 * search value by key
	 * @param key
	 * @return
	 */
	public Node get(String key) {
		return get(root, key, 0);
	}

	private Node get(Node x, String key, int d) {
		if (x == null)
			return null;

		if (key.length() == d)
			return x;

		char c = key.charAt(d);
		return get(x.next[c], key, d + 1);
	}
	
	/**
	 * remove value from trie tree by key
	 * @param key
	 */
	public void remove(String key) {
		root = remove(root,key,0);
	}

	/**
	 * delete one element from trie tree
	 * @param x
	 * @param key
	 * @param d
	 * @return
	 */
	private Node remove(Node x, String key, int d) {

		if(x == null) return null;
		if(key.length()==d) {
			
			x.value = null;
		} else {
			char c = key.charAt(d);
			x.next[c] = remove(x.next[c],key,d+1);
		}
		
		if(x.value != null) return x;
		for(char e = 0;d<R;d++) {
			if(x.next[e] != null)
				return x;
		}
		return null;
	}
	
	
	private void collect(Node x, String pre,Queue<String> q) {
		if(x == null) return;
		
		if(x.value != null) q.add(pre);
		for(char c=0;c<R;c++) {
			collect(x.next[c],pre+c,q);
		}
		
	}
	
	/**
	 * get all keys which start with pre 
	 */
	public Iterable<String> keysWithPrefix(String pre) {
		Queue<String> q = new LinkedList<String>();
		collect(root,pre,q);
		return q;
	}
	
	/**
	 * get all keys
	 */
	public Iterable<String> keys() {
		return keysWithPrefix("");
	}
	
	/**
	 * return a key which is the longest prefix of a string
	 * @param str
	 * @return
	 */
	public String longPrefixOf(String str) {
		return str.substring(0,search(root,0,0,str));
	}
	
	
	private int search(Node x,int d,int length,String str) {
		
		if(x == null) return length;
		if(x.value != null) length = d;
		if(d == str.length()) return length;
		char c = str.charAt(d);
		
		return search(x.next[c],d+1,length,str);
	}

}