001: /*
002: * Copyright 2007 Google Inc.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License"); you may not
005: * use this file except in compliance with the License. You may obtain a copy of
006: * the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
012: * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
013: * License for the specific language governing permissions and limitations under
014: * the License.
015: */
016:
017: package com.google.gwt.user.client.ui;
018:
019: import com.google.gwt.core.client.JavaScriptObject;
020:
021: import java.util.AbstractCollection;
022: import java.util.ArrayList;
023: import java.util.Collection;
024: import java.util.Iterator;
025: import java.util.List;
026: import java.util.NoSuchElementException;
027:
028: /**
029: * A prefix tree (aka trie).
030: *
031: */
032: class PrefixTree extends AbstractCollection<String> {
033:
034: /**
035: * Iterates over the structure of a PrefixTree. No concurrency checks are
036: * made. This Iterator will output anything new added to the tree if the new
037: * entry is after the current position of the Iterator.
038: *
039: * This Iterator implementation is iterative and uses an internal stack object
040: * to avoid call-stack limitations and invocation overhead.
041: */
042: private static class PrefixTreeIterator implements Iterator<String> {
043:
044: private JavaScriptObject stack;
045:
046: /**
047: * Constructor.
048: *
049: * @param tree The base of the PrefixTree to iterate over
050: */
051: public PrefixTreeIterator(PrefixTree tree) {
052: init();
053: addTree(tree, "");
054: }
055:
056: public boolean hasNext() {
057: // Have nextImpl peek at the next value that would be returned.
058: return nextImpl(true) != null;
059: }
060:
061: /**
062: * {@inheritDoc} Wraps the native implementation with some sanity checking.
063: */
064: public String next() {
065: final String toReturn = nextImpl(false);
066:
067: // A null response indicates that there was no data to be had.
068: if (toReturn == null) {
069: // Sanity check.
070: if (!hasNext()) {
071: throw new NoSuchElementException(
072: "No more elements in the iterator");
073: } else {
074: throw new RuntimeException(
075: "nextImpl() returned null, but hasNext says otherwise");
076: }
077: }
078:
079: return toReturn;
080: }
081:
082: public void remove() {
083: throw new UnsupportedOperationException(
084: "PrefixTree does not support "
085: + "removal. Use clear()");
086: }
087:
088: /**
089: * Add a frame to the work stack.
090: *
091: * <pre>
092: * frame := {suffixNames, subtrees, prefix, index}
093: * suffixNames := All suffixes in the target PrefixTree
094: * subtrees := All subtrees in the target PrefixTree
095: * prefix := A string that next() will prepend to output from the frame
096: * index := Stores which suffix was last output
097: * </pre>
098: *
099: * @param tree The tree to add
100: * @param prefix The prefix to prepend to values in tree
101: */
102: private native void addTree(PrefixTree tree, String prefix) /*-{
103: var suffixes = [];
104: for (suffix in tree.@com.google.gwt.user.client.ui.PrefixTree::suffixes) {
105: suffixes.push(suffix);
106: }
107:
108: var frame = {
109: suffixNames: suffixes,
110: subtrees: tree.@com.google.gwt.user.client.ui.PrefixTree::subtrees,
111: prefix: prefix,
112: index: 0
113: };
114:
115: var stack = this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::stack;
116: stack.push(frame);
117: }-*/;
118:
119: /**
120: * Initialize JSNI objects.
121: */
122: private native void init() /*-{
123: this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::stack = [];
124: }-*/;
125:
126: /**
127: * Access JSNI structures.
128: *
129: * @param peek If this is true, don't advance the iteration, just return the
130: * value that next() would return if it were called
131: * @return The next object, or null if there is an error
132: */
133: private native String nextImpl(boolean peek) /*-{
134: var stack = this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::stack;
135: var safe = @com.google.gwt.user.client.ui.PrefixTree::safe(Ljava/lang/String;)
136: var unsafe = @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)
137:
138: // Put this in a while loop to handle descent into subtrees without recursion.
139: while (stack.length > 0) {
140: var frame = stack.pop();
141:
142: // Check to see if there are any remaining suffixes to output.
143: if (frame.index < frame.suffixNames.length) {
144: var toReturn = frame.prefix + unsafe(frame.suffixNames[frame.index]);
145:
146: if (!peek) {
147: frame.index++;
148: }
149:
150: // If the current frame has more suffixes, retain it on the stack.
151: if (frame.index < frame.suffixNames.length) {
152: stack.push(frame);
153:
154: // Otherwise, put all of the subtrees on the stack.
155: } else {
156: for (key in frame.subtrees) {
157: var target = frame.prefix + unsafe(key);
158: var subtree = frame.subtrees[key];
159: this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::addTree(Lcom/google/gwt/user/client/ui/PrefixTree;Ljava/lang/String;)(subtree, target);
160: }
161: }
162:
163: return toReturn;
164:
165: // Put all subframes on the stack, and return to top of loop.
166: } else {
167: for (key in frame.subtrees) {
168: var target = frame.prefix + unsafe(key);
169: var subtree = frame.subtrees[key];
170:
171: this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::addTree(Lcom/google/gwt/user/client/ui/PrefixTree;Ljava/lang/String;)(subtree, target);
172: }
173: }
174: }
175:
176: // This would indicate that next() was called on an empty iterator.
177: // Will throw an exception from next().
178: return null;
179: }-*/;
180: }
181:
182: /**
183: * Used by native methods to create an appropriately blessed PrefixTree.
184: *
185: * @param prefixLength Smaller prefix length equals faster, more direct
186: * searches, at a cost of setup time
187: * @return a newly constructed prefix tree
188: */
189: protected static PrefixTree createPrefixTree(int prefixLength) {
190: return new PrefixTree(prefixLength);
191: }
192:
193: /**
194: * Ensure that a String can be safely used as a key to an associative-array
195: * JavaScript object by prepending a prefix.
196: *
197: * @param s The String to make safe
198: * @return A safe version of <code>s</code>
199: */
200: private static String safe(String s) {
201: return ':' + s;
202: }
203:
204: /**
205: * Undo the operation performed by safe().
206: *
207: * @param s A String returned from safe()
208: * @return The original String passed into safe()
209: */
210: private static String unsafe(String s) {
211: return s.substring(1);
212: }
213:
214: /**
215: * Stores the requested prefix length.
216: */
217: protected final int prefixLength;
218:
219: /**
220: * Field to store terminal nodes in.
221: */
222: protected JavaScriptObject suffixes;
223:
224: /**
225: * Field to store subtrees in.
226: */
227: protected JavaScriptObject subtrees;
228:
229: /**
230: * Store the number of elements contained by this PrefixTree and its
231: * sub-trees.
232: */
233: protected int size = 0;
234:
235: /**
236: * Constructor.
237: */
238: public PrefixTree() {
239: this (2, null);
240: }
241:
242: /**
243: * Constructor.
244: *
245: * @param source Initialize from another collection
246: */
247: public PrefixTree(Collection<String> source) {
248: this (2, source);
249: }
250:
251: /**
252: * Constructor.
253: *
254: * @param prefixLength Smaller prefix length equals faster, more direct
255: * searches, at a cost of setup time.
256: */
257: public PrefixTree(final int prefixLength) {
258: this (prefixLength, null);
259: }
260:
261: /**
262: * Constructor.
263: *
264: * @param prefixLength Smaller prefix length equals faster, more direct
265: * searches, at a cost of setup time.
266: * @param source Initialize from another collection
267: */
268: public PrefixTree(final int prefixLength,
269: final Collection<String> source) {
270: this .prefixLength = prefixLength;
271: clear();
272:
273: if (source != null) {
274: addAll(source);
275: }
276: }
277:
278: /**
279: * Add a String to the PrefixTree.
280: *
281: * @param s The data to add
282: * @return <code>true</code> if the string was added, <code>false</code>
283: * otherwise
284: */
285: @Override
286: public native boolean add(String s) /*-{
287: var suffixes =
288: this.@com.google.gwt.user.client.ui.PrefixTree::suffixes;
289: var subtrees =
290: this.@com.google.gwt.user.client.ui.PrefixTree::subtrees;
291: var prefixLength =
292: this.@com.google.gwt.user.client.ui.PrefixTree::prefixLength;
293:
294: // This would indicate a mis-use of the code.
295: if ((s == null) || (s.length == 0)) {
296: return false;
297: }
298:
299: // Use <= so that strings that are exactly prefixLength long don't
300: // require some kind of null token.
301: if (s.length <= prefixLength) {
302: var safeKey = @com.google.gwt.user.client.ui.PrefixTree::safe(Ljava/lang/String;)(s);
303: if (suffixes.hasOwnProperty(safeKey)) {
304: return false;
305: } else {
306: // Each tree keeps a count of how large it and its children are.
307: this.@com.google.gwt.user.client.ui.PrefixTree::size++;
308:
309: suffixes[safeKey] = true;
310: return true;
311: }
312:
313: // Add the string to the appropriate PrefixTree.
314: } else {
315: var prefix = @com.google.gwt.user.client.ui.PrefixTree::safe(Ljava/lang/String;)(s.slice(0, prefixLength));
316: var theTree;
317:
318: if (subtrees.hasOwnProperty(prefix)) {
319: theTree = subtrees[prefix];
320: } else {
321: theTree = @com.google.gwt.user.client.ui.PrefixTree::createPrefixTree(I)(prefixLength * 2);
322: subtrees[prefix] = theTree;
323: }
324:
325: var slice = s.slice(prefixLength);
326: if (theTree.@com.google.gwt.user.client.ui.PrefixTree::add(Ljava/lang/String;)(slice)) {
327: // The size of the subtree increased, so we need to update the local count.
328: this.@com.google.gwt.user.client.ui.PrefixTree::size++;
329: return true;
330: } else {
331: return false;
332: }
333: }
334: }-*/;
335:
336: /**
337: * Initialize native state.
338: */
339: @Override
340: public native void clear() /*-{
341: this.@com.google.gwt.user.client.ui.PrefixTree::size = 0;
342: this.@com.google.gwt.user.client.ui.PrefixTree::subtrees = {};
343: this.@com.google.gwt.user.client.ui.PrefixTree::suffixes = {};
344: }-*/;
345:
346: @Override
347: public boolean contains(Object o) {
348: if (o instanceof String) {
349: return contains((String) o);
350: } else {
351: return false;
352: }
353: }
354:
355: public boolean contains(String s) {
356: return (getSuggestions(s, 1)).contains(s);
357: }
358:
359: /**
360: * Retrieve suggestions from the PrefixTree. The number of items returned from
361: * getSuggesstions may slightly exceed <code>limit</code> so that all
362: * suffixes and partial stems will be returned. This prevents the search space
363: * from changing size if the PrefixTree is used in an interactive manner.
364: * <br/> The returned List is guaranteed to be safe; changing its contents
365: * will not affect the PrefixTree.
366: *
367: * @param search The prefix to search for
368: * @param limit The desired number of results to retrieve
369: * @return A List of suggestions
370: */
371: public List<String> getSuggestions(String search, int limit) {
372: final List<String> toReturn = new ArrayList<String>();
373: if ((search != null) && (limit > 0)) {
374: suggestImpl(search, "", toReturn, limit);
375: }
376: return toReturn;
377: }
378:
379: @Override
380: public Iterator<String> iterator() {
381: return new PrefixTreeIterator(this );
382: }
383:
384: /**
385: * Get the number of all elements contained within the PrefixTree.
386: *
387: * @return the size of the prefix tree
388: */
389: @Override
390: public int size() {
391: return size;
392: }
393:
394: protected native void suggestImpl(String search, String prefix,
395: Collection<String> output, int limit) /*-{
396: var suffixes =
397: this.@com.google.gwt.user.client.ui.PrefixTree::suffixes;
398: var subtrees =
399: this.@com.google.gwt.user.client.ui.PrefixTree::subtrees;
400: var prefixLength =
401: this.@com.google.gwt.user.client.ui.PrefixTree::prefixLength;
402:
403: // Search is too big to be found in current tree, just recurse.
404: if (search.length > prefix.length + prefixLength) {
405: var key = @com.google.gwt.user.client.ui.PrefixTree::safe(Ljava/lang/String;)(search.slice(prefix.length, prefix.length + prefixLength));
406:
407: // Just pick the correct subtree, if it exists, and call suggestImpl.
408: if (subtrees.hasOwnProperty(key)) {
409: var subtree = subtrees[key];
410: var target = prefix + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(key);
411: subtree.@com.google.gwt.user.client.ui.PrefixTree::suggestImpl(Ljava/lang/String;Ljava/lang/String;Ljava/util/Collection;I)(search, target, output, limit);
412: }
413:
414: // The answer can only exist in this tree's suffixes or subtree keys.
415: } else {
416: // Check local suffixes.
417: for (suffix in suffixes) {
418: var target = prefix + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(suffix);
419: if (target.indexOf(search) == 0) {
420: output.@java.util.Collection::add(Ljava/lang/Object;)(target);
421: }
422:
423: if (output.@java.util.Collection::size()() >= limit) {
424: return;
425: }
426: }
427:
428: // Check the subtree keys. If the key matches, that implies that all
429: // elements of the subtree would match.
430: for (var key in subtrees) {
431: var target = prefix + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(key);
432: var subtree = subtrees[key];
433:
434: // See if the prefix gives us a match.
435: if (target.indexOf(search) == 0) {
436:
437: // Provide as many suggestions as will fit into the remaining limit.
438: // If there is only one suggestion, include it.
439: if ((subtree.@com.google.gwt.user.client.ui.PrefixTree::size <= limit - output.@java.util.Collection::size()()) ||
440: (subtree.@com.google.gwt.user.client.ui.PrefixTree::size == 1)) {
441: subtree.@com.google.gwt.user.client.ui.PrefixTree::dump(Ljava/util/Collection;Ljava/lang/String;)(output, target);
442:
443: // Otherwise, include as many answers as we can by truncating the suffix
444: } else {
445:
446: // Always fully-specify suffixes.
447: for (var suffix in subtree.@com.google.gwt.user.client.ui.PrefixTree::suffixes) {
448: output.@java.util.Collection::add(Ljava/lang/Object;)(target + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(suffix));
449: }
450:
451: // Give the keys of the subtree.
452: for (var subkey in subtree.@com.google.gwt.user.client.ui.PrefixTree::subtrees) {
453: output.@java.util.Collection::add(Ljava/lang/Object;)(target + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(subkey) + "...");
454: }
455: }
456: }
457: }
458: }
459: }-*/;
460:
461: /**
462: * Put all contents of the PrefixTree into a Collection.
463: *
464: * @param output the collection into which the prefixes will be dumped
465: * @param prefix the prefix to filter with
466: */
467: private void dump(Collection<String> output, String prefix) {
468: for (String s : this) {
469: output.add(prefix + s);
470: }
471: }
472: }
|