Java > Open Source Codes > com > google > gwt > user > client > ui > PrefixTree


1 /*
2  * Copyright 2006 Google Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
5  * use this file except in compliance with the License. You may obtain a copy of
6  * the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13  * License for the specific language governing permissions and limitations under
14  * the License.
15  */
16
17 package com.google.gwt.user.client.ui;
18
19 import com.google.gwt.core.client.JavaScriptObject;
20
21 import java.util.AbstractCollection ;
22 import java.util.ArrayList ;
23 import java.util.Collection ;
24 import java.util.Iterator ;
25 import java.util.List ;
26 import java.util.NoSuchElementException ;
27
28 /**
29  * A prefix tree (aka trie).
30  *
31  */
32 class PrefixTree extends AbstractCollection {
33
34   /**
35    * Iterates over the structure of a PrefixTree. No concurrency checks are
36    * made. This Iterator will output anything new added to the tree if the new
37    * entry is after the current position of the Iterator.
38    *
39    * This Iterator implementation is iterative and uses an internal stack object
40    * to avoid call-stack limitations and invocation overhead.
41    */
42   private static class PrefixTreeIterator implements Iterator {
43
44     private JavaScriptObject stack;
45
46     /**
47      * Constructor.
48      *
49      * @param tree The base of the PrefixTree to iterate over
50      */
51     public PrefixTreeIterator(PrefixTree tree) {
52       init();
53       addTree(tree, "");
54     }
55
56     public boolean hasNext() {
57       // Have nextImpl peek at the next value that would be returned.
58 return nextImpl(true) != null;
59     }
60
61     /**
62      * {@inheritDoc} Wraps the native implementation with some sanity checking.
63      */
64     public Object next() {
65       final Object toReturn = nextImpl(false);
66
67       // A null response indicates that there was no data to be had.
68 if (toReturn == null) {
69         // Sanity check.
70 if (!hasNext()) {
71           throw new NoSuchElementException ("No more elements in the iterator");
72         } else {
73           throw new RuntimeException (
74               "nextImpl() returned null, but hasNext says otherwise");
75         }
76       }
77
78       return toReturn;
79     }
80
81     public void remove() {
82       throw new UnsupportedOperationException ("PrefixTree does not support "
83           + "removal. Use clear()");
84     }
85
86     /**
87      * Add a frame to the work stack.
88      *
89      * <pre>
90      * frame := {suffixNames, subtrees, prefix, index}
91      * suffixNames := All suffixes in the target PrefixTree
92      * subtrees := All subtrees in the target PrefixTree
93      * prefix := A string that next() will prepend to output from the frame
94      * index := Stores which suffix was last output
95      * </pre>
96      *
97      * @param tree The tree to add
98      * @param prefix The prefix to prepend to values in tree
99      */
100     private native void addTree(PrefixTree tree, String prefix) /*-{
101       var suffixes = [];
102       for (suffix in tree.@com.google.gwt.user.client.ui.PrefixTree::suffixes) {
103         suffixes.push(suffix);
104       }
105
106       var frame = {
107         suffixNames: suffixes,
108         subtrees: tree.@com.google.gwt.user.client.ui.PrefixTree::subtrees,
109         prefix: prefix,
110         index: 0
111       };
112
113       var stack = this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::stack;
114       stack.push(frame);
115     }-*/;
116
117     /**
118      * Initialize JSNI objects.
119      */
120     private native void init() /*-{
121       this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::stack = [];
122     }-*/;
123
124     /**
125      * Access JSNI structures.
126      *
127      * @param peek If this is true, don't advance the iteration, just return the
128      * value that next() would return if it were called
129      * @return The next object, or null if there is an error
130      */
131     private native Object nextImpl(boolean peek) /*-{
132       var stack = this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::stack;
133       var safe = @com.google.gwt.user.client.ui.PrefixTree::safe(Ljava/lang/String;)
134       var unsafe = @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)
135
136       // Put this in a while loop to handle descent into subtrees without recursion.
137       while (stack.length > 0) {
138         var frame = stack.pop();
139
140         // Check to see if there are any remaining suffixes to output.
141         if (frame.index < frame.suffixNames.length) {
142           var toReturn = frame.prefix + unsafe(frame.suffixNames[frame.index]);
143
144           if (!peek) {
145             frame.index++;
146           }
147
148           // If the current frame has more suffixes, retain it on the stack.
149           if (frame.index < frame.suffixNames.length) {
150             stack.push(frame);
151
152             // Otherwise, put all of the subtrees on the stack.
153           } else {
154             for (key in frame.subtrees) {
155               var target = frame.prefix + unsafe(key);
156               var subtree = frame.subtrees[key];
157               this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::addTree(Lcom/google/gwt/user/client/ui/PrefixTree;Ljava/lang/String;)(subtree, target);
158             }
159           }
160
161           return toReturn;
162
163        // Put all subframes on the stack, and return to top of loop.
164        } else {
165          for (key in frame.subtrees) {
166            var target = frame.prefix + unsafe(key);
167            var subtree = frame.subtrees[key];
168
169            this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::addTree(Lcom/google/gwt/user/client/ui/PrefixTree;Ljava/lang/String;)(subtree, target);
170          }
171        }
172      }
173
174      // This would indicate that next() was called on an empty iterator.
175      // Will throw an exception from next().
176      return null;
177     }-*/;
178   }
179
180   /**
181    * Used by native methods to create an appropriately blessed PrefixTree.
182    *
183    * @param prefixLength Smaller prefix length equals faster, more direct
184    * searches, at a cost of setup time
185    * @return a newly constructed prefix tree
186    */
187   protected static PrefixTree createPrefixTree(int prefixLength) {
188     return new PrefixTree(prefixLength);
189   }
190
191   /**
192    * Ensure that a String can be safely used as a key to an associative-array
193    * JavaScript object by prepending a prefix.
194    *
195    * @param s The String to make safe
196    * @return A safe version of <code>s</code>
197    */
198   private static String safe(String s) {
199     return ':' + s;
200   }
201
202   /**
203    * Undo the operation performed by safe().
204    *
205    * @param s A String returned from safe()
206    * @return The original String passed into safe()
207    */
208   private static String unsafe(String s) {
209     return s.substring(1);
210   }
211
212   /**
213    * Stores the requested prefix length.
214    */
215   protected final int prefixLength;
216
217   /**
218    * Field to store terminal nodes in.
219    */
220   protected JavaScriptObject suffixes;
221
222   /**
223    * Field to store subtrees in.
224    */
225   protected JavaScriptObject subtrees;
226
227   /**
228    * Store the number of elements contained by this PrefixTree and its
229    * sub-trees.
230    */
231   protected int size = 0;
232
233   /**
234    * Constructor.
235    */
236   public PrefixTree() {
237     this(2, null);
238   }
239
240   /**
241    * Constructor.
242    *
243    * @param source Initialize from another collection
244    */
245   public PrefixTree(Collection source) {
246     this(2, source);
247   }
248
249   /**
250    * Constructor.
251    *
252    * @param prefixLength Smaller prefix length equals faster, more direct
253    * searches, at a cost of setup time.
254    */
255   public PrefixTree(final int prefixLength) {
256     this(prefixLength, null);
257   }
258
259   /**
260    * Constructor.
261    *
262    * @param prefixLength Smaller prefix length equals faster, more direct
263    * searches, at a cost of setup time.
264    * @param source Initialize from another collection
265    */
266   public PrefixTree(final int prefixLength, final Collection source) {
267     this.prefixLength = prefixLength;
268     clear();
269
270     if (source != null) {
271       addAll(source);
272     }
273   }
274
275   /**
276    * Adds an object to the PrefixTree.
277    *
278    * @param o The object to add
279    * @throws UnsupportedOperationException if the object is not a String
280    * @return <code>true</code> if the string was added, <code>false</code>
281    * otherwise
282    */
283   public boolean add(Object o) throws UnsupportedOperationException {
284     if (o instanceof String ) {
285       return add((String ) o);
286     } else {
287       throw new UnsupportedOperationException (
288           "Cannot add non-Strings to PrefixTree");
289     }
290   }
291
292   /**
293    * Add a String to the PrefixTree.
294    *
295    * @param s The data to add
296    * @return <code>true</code> if the string was added, <code>false</code>
297    * otherwise
298    */
299   public native boolean add(String s) /*-{
300     var suffixes =
301         this.@com.google.gwt.user.client.ui.PrefixTree::suffixes;
302     var subtrees =
303         this.@com.google.gwt.user.client.ui.PrefixTree::subtrees;
304     var prefixLength =
305         this.@com.google.gwt.user.client.ui.PrefixTree::prefixLength;
306
307     // This would indicate a mis-use of the code.
308     if ((s == null) || (s.length == 0)) {
309       return false;
310     }
311
312     // Use <= so that strings that are exactly prefixLength long don't
313     // require some kind of null token.
314     if (s.length <= prefixLength) {
315       var safeKey = @com.google.gwt.user.client.ui.PrefixTree::safe(Ljava/lang/String;)(s);
316       if (suffixes.hasOwnProperty(safeKey)) {
317         return false;
318       } else {
319         // Each tree keeps a count of how large it and its children are.
320         this.@com.google.gwt.user.client.ui.PrefixTree::size++;
321
322         suffixes[safeKey] = true;
323         return true;
324       }
325
326     // Add the string to the appropriate PrefixTree.
327     } else {
328       var prefix = @com.google.gwt.user.client.ui.PrefixTree::safe(Ljava/lang/String;)(s.slice(0, prefixLength));
329       var theTree;
330
331       if (subtrees.hasOwnProperty(prefix)) {
332         theTree = subtrees[prefix];
333       } else {
334         theTree = @com.google.gwt.user.client.ui.PrefixTree::createPrefixTree(I)(prefixLength * 2);
335         subtrees[prefix] = theTree;
336       }
337
338       var slice = s.slice(prefixLength);
339       if (theTree.@com.google.gwt.user.client.ui.PrefixTree::add(Ljava/lang/String;)(slice)) {
340         // The size of the subtree increased, so we need to update the local count.
341         this.@com.google.gwt.user.client.ui.PrefixTree::size++;
342         return true;
343       } else {
344         return false;
345       }
346     }
347   }-*/;
348
349   /**
350    * Initialize native state.
351    */
352   public native void clear() /*-{
353     this.@com.google.gwt.user.client.ui.PrefixTree::size = 0;
354     this.@com.google.gwt.user.client.ui.PrefixTree::subtrees = {};
355     this.@com.google.gwt.user.client.ui.PrefixTree::suffixes = {};
356   }-*/;
357
358   public boolean contains(Object o) {
359     if (o instanceof String ) {
360       return contains((String ) o);
361     } else {
362       return false;
363     }
364   }
365
366   public boolean contains(String s) {
367     return (getSuggestions(s, 1)).contains(s);
368   }
369
370   /**
371    * Retrieve suggestions from the PrefixTree. The number of items returned from
372    * getSuggesstions may slightly exceed <code>limit</code> so that all
373    * suffixes and partial stems will be returned. This prevents the search space
374    * from changing size if the PrefixTree is used in an interactive manner.
375    * <br/> The returned List is guaranteed to be safe; changing its contents
376    * will not affect the PrefixTree.
377    *
378    * @param search The prefix to search for
379    * @param limit The desired number of results to retrieve
380    * @return A List of suggestions
381    */
382   public List /* <String> */getSuggestions(String search, int limit) {
383     final List toReturn = new ArrayList ();
384     if ((search != null) && (limit > 0)) {
385       suggestImpl(search, "", toReturn, limit);
386     }
387     return toReturn;
388   }
389
390   public Iterator iterator() {
391     return new PrefixTreeIterator(this);
392   }
393
394   /**
395    * Get the number of all elements contained within the PrefixTree.
396    *
397    * @return the size of the prefix tree
398    */
399   public int size() {
400     return size;
401   }
402
403   protected native void suggestImpl(String search, String prefix,
404       Collection output, int limit) /*-{
405     var suffixes =
406         this.@com.google.gwt.user.client.ui.PrefixTree::suffixes;
407     var subtrees =
408         this.@com.google.gwt.user.client.ui.PrefixTree::subtrees;
409     var prefixLength =
410         this.@com.google.gwt.user.client.ui.PrefixTree::prefixLength;
411
412     // Search is too big to be found in current tree, just recurse.
413     if (search.length > prefix.length + prefixLength) {
414       var key = @com.google.gwt.user.client.ui.PrefixTree::safe(Ljava/lang/String;)(search.slice(prefix.length, prefix.length + prefixLength));
415
416       // Just pick the correct subtree, if it exists, and call suggestImpl.
417       if (subtrees.hasOwnProperty(key)) {
418         var subtree = subtrees[key];
419         var target = prefix + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(key);
420         subtree.@com.google.gwt.user.client.ui.PrefixTree::suggestImpl(Ljava/lang/String;Ljava/lang/String;Ljava/util/Collection;I)(search, target, output, limit);
421       }
422
423     // The answer can only exist in this tree's suffixes or subtree keys.
424     } else {
425      // Check local suffixes.
426      for (suffix in suffixes) {
427        var target = prefix + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(suffix);
428        if (target.indexOf(search) == 0) {
429          output.@java.util.Collection::add(Ljava/lang/Object;)(target);
430        }
431
432        if (output.@java.util.Collection::size()() >= limit) {
433          return;
434        }
435      }
436
437      // Check the subtree keys. If the key matches, that implies that all
438      // elements of the subtree would match.
439      for (var key in subtrees) {
440        var target = prefix + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(key);
441        var subtree = subtrees[key];
442
443        // See if the prefix gives us a match.
444        if (target.indexOf(search) == 0) {
445
446          // Provide as many suggestions as will fit into the remaining limit.
447          // If there is only one suggestion, include it.
448          if ((subtree.@com.google.gwt.user.client.ui.PrefixTree::size <= limit - output.@java.util.Collection::size()()) ||
449              (subtree.@com.google.gwt.user.client.ui.PrefixTree::size == 1)) {
450            subtree.@com.google.gwt.user.client.ui.PrefixTree::dump(Ljava/util/Collection;Ljava/lang/String;)(output, target);
451
452          // Otherwise, include as many answers as we can by truncating the suffix
453          } else {
454
455            // Always fully-specify suffixes.
456            for (var suffix in subtree.@com.google.gwt.user.client.ui.PrefixTree::suffixes) {
457              output.@java.util.Collection::add(Ljava/lang/Object;)(target + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(suffix));
458            }
459
460            // Give the keys of the subtree.
461            for (var subkey in subtree.@com.google.gwt.user.client.ui.PrefixTree::subtrees) {
462              output.@java.util.Collection::add(Ljava/lang/Object;)(target + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(subkey) + "...");
463            }
464          }
465        }
466      }
467    }
468   }-*/;
469
470   /**
471    * Put all contents of the PrefixTree into a Collection.
472    *
473    * @param output the collection into which the prefixes will be dumped
474    * @param prefix the prefix to filter with
475    */
476   private void dump(Collection output, String prefix) {
477     for (final Iterator i = iterator(); i.hasNext();) {
478       output.add(prefix + (String ) i.next());
479     }
480   }
481 }
482

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags