gistfile1.java

package com.raj.strings;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;

/**
 * Trie implementation: 
 * Names taken from: http://stavi.sh/downloads/names.txt
 * 
 * @author raju rama krishna
 *
 */
public class Trie {

	LinkList rootList;


	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {
		Trie trie = new Trie();
		BufferedReader br = null;
		try {
			long t1 = new Date().getTime();
			br = new BufferedReader(new FileReader(new File("C:\\Apps\\names.txt")));
			String line = br.readLine();
			int i=0;
			while( line != null ) {
				trie.createTree(line, i++);
				line = br.readLine();
			}
			long t2 = new Date().getTime();
			System.out.println("Loaded " +i+ " names into Trie. Time taken = " + (t2-t1) + "ms.");
			String p = "JAMES";
			List<Integer> indexes = trie.search(p);
			t1 = new Date().getTime();
			System.out.println("Searched for : " +p+ " . Time taken = " +(t1-t2) + "ms.");
			if(indexes != null) {
				System.out.println("RESULTS: Found " +indexes.size()+ " matches");
				br = new BufferedReader(new FileReader(new File("C:\\Apps\\names.txt")));
				line = br.readLine();
				i=0;
				while( line != null ) {
					if( indexes.contains(i)) {
						System.out.println(line);
					}
					line = br.readLine();
					i++;
				}
			} else {
				System.out.println("ERROR: Not Found!!");
			}

		}catch(Exception e) {
			e.printStackTrace();
		} finally {
			br.close();
		}
	}

	public void createTree( String s, int i ) {
		String[] sArr = s.split(" ");
		for( int j=0; j<sArr.length; j++ ) {
			insert( sArr[j], i );
		}
	}

	public void insert( String x, int index ) {
		char[] cArr = x.toCharArray();		
		LinkList list = rootList;
		for(int i=0; i<cArr.length; i++) {			
			if( list == null ) {
				rootList = new LinkList();
				LinkNode node = new LinkNode(cArr[i]);
				rootList.head = node;
				node.children = new LinkList();
				list = node.children;
			} else {
				if( i == cArr.length-1 ) {
					list = list.add(cArr[i], true, index);
				} else {
					list = list.add(cArr[i], false, index);
				}
			}
		}
	}

	public List<Integer> search( String p ) {
		List<Integer> indexes = null;
		LinkList list = rootList;
		int i = 0;
		char c = p.charAt(i);
		LinkNode node = list.head;
		while( node != null ) {
			if( c == node.c ) {
				i++;
				if( i == p.length()) {
					if(node.isEnd) {
						indexes = node.indexes;
					}
					break;
				}
				c = p.charAt(i);
				list = node.children; 
				node = list.head;
			} else {
				node = node.next;
			}
		}
		return indexes;
	}
}


class LinkList {
	LinkNode head;

	public LinkList add( char c, boolean isEnd, int index ) {
		LinkNode res = null;
		if( head == null ) {
			LinkNode linkNode = new LinkNode( c );
			head = linkNode;
			res = linkNode;
		} else {
			if( c < head.c ) {
				LinkNode linkNode = new LinkNode( c );
				linkNode.next = head;
				head = linkNode;
				res = linkNode;
			} else {
				LinkNode prev = null;
				LinkNode cur = head;
				while( cur != null && cur.c < c ) {				
					prev = cur;
					cur = cur.next;
				}	

				if( cur != null && cur.c == c ) {
					res = cur;
				} else {
					LinkNode linkNode = new LinkNode( c );
					prev.next = linkNode;
					linkNode.next = cur;
					res = linkNode;
				}
			}
		}
		if( !isEnd ) {
			if(res.children == null ) {
				res.children = new LinkList();
			}
		} else {
			res.isEnd = true;
			if(res.indexes == null) {
				res.indexes = new ArrayList<Integer>();
			}
			res.indexes.add(index);
		}
		return res.children;
	}
}

class LinkNode {
	boolean isEnd;
	char c;
	LinkNode next;
	LinkList children;
	List<Integer> indexes;

	public LinkNode( char c ) {
		this.c = c;
	}

	public String toString() {
		return String.valueOf(c);
//		StringBuffer sb = new StringBuffer();
//		LinkNode node = this;
//		while( node != null ) {
//			sb.append("->").append(node.c);
//			node = node.next;
//		}
//		return sb.toString();
	}
}