1 package prefuse.data.search; 2 3 import java.util.Iterator ; 4 import java.util.LinkedList ; 5 import java.util.NoSuchElementException ; 6 7 import prefuse.data.Tuple; 8 9 10 21 public class Trie { 22 23 26 public class TrieNode { 27 boolean isLeaf; 28 int leafCount = 0; 29 } 30 31 36 public class TrieBranch extends TrieNode { 37 char[] chars = new char[] {0}; 38 TrieNode[] children = new TrieNode[1]; 39 } 40 41 46 public class TrieLeaf extends TrieNode { 47 public TrieLeaf(String word, Tuple t) { 48 this.word = word; 49 tuple = t; 50 next = null; 51 leafCount = 1; 52 } 53 String word; 54 Tuple tuple; 55 TrieLeaf next; 56 } 57 58 61 public class TrieIterator implements Iterator { 62 private LinkedList queue; 63 public TrieIterator(TrieNode node) { 64 queue = new LinkedList (); 65 queue.add(node); 66 } 67 public boolean hasNext() { 68 return !queue.isEmpty(); 69 } 70 public Object next() { 71 if ( queue.isEmpty() ) 72 throw new NoSuchElementException (); 73 74 TrieNode n = (TrieNode)queue.removeFirst(); 75 Object o; 76 if ( n instanceof TrieLeaf ) { 77 TrieLeaf l = (TrieLeaf)n; 78 o = l.tuple; 79 if ( l.next != null ) 80 queue.addFirst(l.next); 81 return o; 82 } else { 83 TrieBranch b = (TrieBranch)n; 84 for ( int i = b.chars.length-1; i > 0; i-- ) { 85 queue.addFirst(b.children[i]); 86 } 87 if ( b.children[0] != null ) 88 queue.addFirst(b.children[0]); 89 return next(); 90 } 91 } 92 public void remove() { 93 throw new UnsupportedOperationException (); 94 } 95 } 97 private TrieBranch root = new TrieBranch(); 98 private boolean caseSensitive = false; 99 100 105 public Trie(boolean caseSensitive) { 106 this.caseSensitive = caseSensitive; 107 } 108 109 114 public boolean isCaseSensitive() { 115 return caseSensitive; 116 } 117 118 123 public void addString(String word, Tuple t) { 124 TrieLeaf leaf = new TrieLeaf(word,t); 125 addLeaf(root, leaf, 0); 126 } 127 128 133 public void removeString(String word, Tuple t) { 134 removeLeaf(root, word, t, 0); 135 } 136 137 private final int getIndex(char[] chars, char c) { 138 for ( int i=0; i<chars.length; i++ ) 139 if ( chars[i] == c ) return i; 140 return -1; 141 } 142 143 private final char getChar(String s, int i) { 144 char c = ( i < 0 || i >= s.length() ? 0 : s.charAt(i) ); 145 return ( caseSensitive ? c : Character.toLowerCase(c) ); 146 } 147 148 private final TrieNode equalityCheck(String word, TrieLeaf l) { 149 if ( caseSensitive ) { 150 return l.word.startsWith(word) ? l : null; 151 } else { 152 int len = word.length(); 154 if ( len > l.word.length() ) return null; 155 for ( int i=0; i<len; ++i ) { 156 char c1 = Character.toLowerCase(word.charAt(i)); 157 char c2 = Character.toLowerCase(l.word.charAt(i)); 158 if ( c1 != c2 ) return null; 159 } 160 return l; 161 } 162 } 163 164 private boolean removeLeaf(TrieBranch b, String word, Tuple t, int depth) { 165 char c = getChar(word, depth); 166 int i = getIndex(b.chars, c); 167 168 if ( i == -1 ) { 169 return false; 171 } else { 172 TrieNode n = b.children[i]; 173 if ( n instanceof TrieBranch ) { 174 TrieBranch tb = (TrieBranch)n; 175 boolean rem = removeLeaf(tb, word, t, depth+1); 176 if ( rem ) { 177 b.leafCount--; 178 if ( tb.leafCount == 1 ) 179 b.children[i] = tb.children[tb.children[0]!=null?0:1]; 180 } 181 return rem; 182 } else { 183 TrieLeaf nl = (TrieLeaf)n; 184 if ( nl.tuple == t ) { 185 b.children[i] = nl.next; 186 if ( nl.next == null ) 187 repairBranch(b,i); 188 b.leafCount--; 189 return true; 190 } else { 191 TrieLeaf nnl = nl.next; 192 while ( nnl != null && nnl.tuple != t ) { 193 nl = nnl; nnl = nnl.next; 194 } 195 if ( nnl == null ) 196 return false; 198 for ( TrieLeaf tl = (TrieLeaf)n; tl.tuple != t; tl = tl.next ) 200 tl.leafCount--; 201 202 nl.next = nnl.next; 203 b.leafCount--; 204 return true; 205 } 206 } 207 } 208 } 209 210 private void repairBranch(TrieBranch b, int i) { 211 if ( i == 0 ) { 212 b.children[0] = null; 213 } else { 214 int len = b.chars.length; 215 char[] nchars = new char[len-1]; 216 TrieNode[] nkids = new TrieNode[len-1]; 217 System.arraycopy(b.chars,0,nchars,0,i); 218 System.arraycopy(b.children,0,nkids,0,i); 219 System.arraycopy(b.chars,i+1,nchars,i,len-i-1); 220 System.arraycopy(b.children,i+1,nkids,i,len-i-1); 221 b.chars = nchars; 222 b.children = nkids; 223 } 224 } 225 226 private void addLeaf(TrieBranch b, TrieLeaf l, int depth) { 227 b.leafCount += l.leafCount; 228 229 char c = getChar(l.word, depth); 230 int i = getIndex(b.chars, c); 231 232 if ( i == -1 ) { 233 addChild(b,l,c); 234 } else { 235 TrieNode n = b.children[i]; 236 if ( n == null ) { 237 b.children[i] = l; 239 } else if ( n instanceof TrieBranch ) { 240 addLeaf((TrieBranch)n,l,depth+1); 242 } else { 243 TrieLeaf nl = (TrieLeaf)n; 245 if ( i==0 || (caseSensitive ? nl.word.equals(l.word) 246 : nl.word.equalsIgnoreCase(l.word)) ) 247 { 248 for ( ; nl.next != null; nl = nl.next ) 250 nl.leafCount++; 251 nl.leafCount++; 252 nl.next = l; 253 } else { 254 TrieBranch nb = new TrieBranch(); 256 b.children[i] = nb; 257 addLeaf(nb,nl,depth+1); 258 addLeaf(nb,l,depth+1); 259 } 260 } 261 } 262 } 263 264 private void addChild(TrieBranch b, TrieNode n, char c) { 265 int len = b.chars.length; 266 char[] nchars = new char[len+1]; 267 TrieNode[] nkids = new TrieNode[len+1]; 268 System.arraycopy(b.chars,0,nchars,0,len); 269 System.arraycopy(b.children,0,nkids,0,len); 270 nchars[len] = c; 271 nkids[len] = n; 272 b.chars = nchars; 273 b.children = nkids; 274 } 275 276 284 public TrieNode find(String word) { 285 return (word.length() < 1 ? null : find(word, root, 0)); 286 } 287 288 private TrieNode find(String word, TrieBranch b, int depth) { 289 char c = getChar(word, depth); 290 int i = getIndex(b.chars, c); 291 if ( i == -1 ) { 292 return null; } else if ( word.length()-1 == depth ) { 294 return b.children[i]; } else if ( b.children[i] instanceof TrieLeaf ) { 296 return equalityCheck(word, (TrieLeaf)b.children[i]); 297 } else { 298 return find(word, (TrieBranch)b.children[i], depth+1); } 300 } 301 302 } | Popular Tags |