View Javadoc

1   /*
2    * Copyright (C) 2007 University of Cambridge
3    *
4    * This file is part of Fosstrak (www.fosstrak.org).
5    *
6    * Fosstrak is free software; you can redistribute it and/or
7    * modify it under the terms of the GNU Lesser General Public
8    * License version 2.1, as published by the Free Software Foundation.
9    *
10   * Fosstrak is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13   * Lesser General Public License for more details.
14   *
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with Fosstrak; if not, write to the Free
17   * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18   * Boston, MA  02110-1301  USA
19   */
20  
21  package org.fosstrak.tdt;
22  
23  import java.lang.reflect.Array;
24  import java.util.ArrayList;
25  import java.util.List;
26  
27  /**
28   * Simple version of a Trie structure.
29   * 
30   * See Wikipedia for information about Tries.
31   * 
32   * Note that this version assumes chars contain values between 0 and 255 (i.e.
33   * UTF-8 or similar).
34   * 
35   * @author Mark Harrison [University of Cambridge] - mark.harrison@cantab.net
36   * @author James Brusey
37   */
38  public class PrefixTree<T> {
39  
40  	private class PrefixNode {
41  		private PrefixNode[] node;
42  
43  		// list is null if non-leaf
44  		private List<T> list;
45  
46  		public PrefixNode() {
47  			node = (PrefixNode[]) Array.newInstance(PrefixNode.class, 256);
48  		}
49  
50  		public PrefixNode[] getNode() {
51  			return node;
52  		}
53  
54  		public PrefixNode getNode(char c) {
55  			return node[c];
56  		}
57  
58  		public void setNode(char c, PrefixNode n) {
59  			node[c] = n;
60  		}
61  
62  		public List<T> getList() {
63  			return list;
64  		}
65  
66  		public boolean isMarked() {
67  			return list != null;
68  		}
69  
70  		public void add(T obj) {
71  			if (list == null)
72  				list = new ArrayList<T>();
73  			list.add(obj);
74  		}
75  
76  	}
77  
78  	PrefixNode root = new PrefixNode();
79  
80  	public void insert1(String s, T obj) {
81  		// add a prefix to the tree
82  		PrefixNode n = root;
83  		for (int i = 0; i < s.length(); i++) {
84  			char c = s.charAt(i);
85  
86  			PrefixNode next = n.getNode(c);
87  			if (next == null) {
88  				next = new PrefixNode();
89  				n.setNode(c, next);
90  			}
91  			n = next;
92  		}
93  		assert n != null;
94  		n.add(obj);
95  	}
96  
97  	// recursive version
98  	public void insert(String s, T obj) {
99  		assert s != null : "Attempt to insert a null string into prefix tree";
100 		myInsert(root, s, obj);
101 	}
102 
103 	private void myInsert(PrefixNode n, String s, T obj) {
104 		if (s.equals(""))
105 			n.add(obj);
106 		else {
107 			char c = s.charAt(0);
108 			PrefixNode next = n.getNode(c);
109 			if (next == null) {
110 				next = new PrefixNode();
111 				n.setNode(c, next);
112 			}
113 			myInsert(next, s.substring(1), obj);
114 		}
115 	}
116 
117 	public List<T> search(String s) {
118 		return mySearch(root, s);
119 	}
120 
121 	private List<T> mySearch(PrefixNode n, String s) {
122 		if (s.equals(""))
123 			return n.getList();
124 		else {
125 			char c = s.charAt(0);
126 			PrefixNode next = n.getNode(c);
127 			if (next == null) {
128 				if (n.isMarked())
129 					return n.getList();
130 				else
131 					return new ArrayList<T>();
132 			} else
133 				return mySearch(next, s.substring(1));
134 		}
135 	}
136 }