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: package com.google.gwt.user.client.ui;
017:
018: import com.google.gwt.junit.client.GWTTestCase;
019:
020: import java.util.ArrayList;
021: import java.util.Iterator;
022: import java.util.List;
023:
024: /**
025: * TODO(bobv): comment me.
026: */
027: public class PrefixTreeTest extends GWTTestCase {
028: public String getModuleName() {
029: return "com.google.gwt.user.User";
030: }
031:
032: /**
033: * Ensure that names of functions declared on the Object prototype are valid
034: * data to insert into the PrefixTree (<a
035: * href="http://code.google.com/p/google-web-toolkit/issues/detail?id=631">issue
036: * #631)</a>.
037: */
038: public void testBug631Prefixes() {
039: // Set the prefix length large enough so that we ensure prefixes are
040: // appropriately tested
041: final String[] prototypeNames = { "__proto__", "constructor",
042: "eval", "prototype", "toString", "toSource", "unwatch",
043: "valueOf", };
044:
045: for (int i = 0; i < prototypeNames.length; i++) {
046: final String name = prototypeNames[i]
047: + "AAAAAAAAAAAAAAAAAAAA";
048: final PrefixTree tree = new PrefixTree(prototypeNames[i]
049: .length());
050:
051: assertFalse("Incorrectly found " + name, tree
052: .contains(name));
053:
054: assertTrue("First add() didn't return true: " + name, tree
055: .add(name));
056: assertFalse(
057: "Second add() of duplicate entry didn't return false: "
058: + name, tree.add(name));
059:
060: assertTrue("contains() didn't find added word: " + name,
061: tree.contains(name));
062:
063: testSizeByIterator(tree);
064: assertTrue("PrefixTree doesn't contain the desired word",
065: 1 == tree.size());
066: }
067: }
068:
069: /**
070: * Ensure that names of functions declared on the Object prototype are valid
071: * data to insert into the PrefixTree(<a
072: * href="http://code.google.com/p/google-web-toolkit/issues/detail?id=631">issue
073: * #631)</a>.
074: */
075: public void testBug631Suffixes() {
076: // Set the prefix length large enough so that we ensure suffixes are
077: // appropriately tested
078: final PrefixTree tree = new PrefixTree(100);
079: final String[] prototypeNames = { "__proto__", "constructor",
080: "eval", "prototype", "toString", "toSource", "unwatch",
081: "valueOf", };
082:
083: for (int i = 0; i < prototypeNames.length; i++) {
084: final String name = prototypeNames[i];
085:
086: assertFalse("Incorrectly found " + name, tree
087: .contains(name));
088:
089: assertTrue("First add() didn't return true: " + name, tree
090: .add(name));
091: assertFalse(
092: "Second add() of duplicate entry didn't return false: "
093: + name, tree.add(name));
094:
095: assertTrue("contains() didn't find added word: " + name,
096: tree.contains(name));
097: }
098:
099: testSizeByIterator(tree);
100: assertTrue(
101: "PrefixTree doesn't contain all of the desired words",
102: prototypeNames.length == tree.size());
103: }
104:
105: /**
106: * Tests adding multiple prefixes and clearing the contents.
107: */
108: public void testMultipleAddsAndClear() {
109: final PrefixTree tree = new PrefixTree();
110:
111: assertTrue(tree.add("foo"));
112: assertFalse(tree.add("foo"));
113: assertTrue(tree.add("bar"));
114:
115: assertTrue("Expecting iterator to have next", tree.iterator()
116: .hasNext());
117: assertTrue("Tree did not have expected size", tree.size() == 2);
118: testSizeByIterator(tree);
119:
120: tree.clear();
121: assertFalse("Expecting cleared tree to not hasNext()", tree
122: .iterator().hasNext());
123: assertTrue("Clear did not set size to 0", tree.size() == 0);
124: }
125:
126: public void testNewTree() {
127: final PrefixTree tree = new PrefixTree();
128: assertTrue("Newly-created tree had non-zero size",
129: tree.size() == 0);
130: testSizeByIterator(tree);
131:
132: assertFalse(
133: "Newly-created tree had iterator with a next element",
134: tree.iterator().hasNext());
135: }
136:
137: /**
138: * Tests newly constructed prefix tree assumptions.
139: */
140: public void testPlaysWellWithOthers() {
141: final List l = new ArrayList();
142: for (int i = 0; i < 100; i++) {
143: l.add(String.valueOf(i));
144: }
145:
146: final PrefixTree tree = new PrefixTree();
147: tree.addAll(l);
148:
149: assertTrue("Not all elements copied", tree.size() == l.size());
150: testSizeByIterator(tree);
151:
152: assertTrue("Original list does not contain all of the tree", l
153: .containsAll(tree));
154:
155: assertTrue("The tree does not contain the original list", tree
156: .containsAll(l));
157: }
158:
159: /**
160: * Test whether the prefix tree works appropriately with collections.
161: */
162: public void testSuggestions() {
163: final PrefixTree tree = new PrefixTree();
164:
165: assertTrue(tree.add("onetwothree"));
166: assertTrue(tree.add("onetwothree1"));
167: assertTrue(tree.add("onetwothree2"));
168: assertTrue(tree.add("onetwothree3"));
169: assertTrue(tree.add("fourfivesix"));
170: assertTrue(tree.add("fourfivesix1"));
171: assertTrue(tree.add("fourfivesix2"));
172: assertTrue(tree.add("fourfivesix3"));
173: assertTrue(tree.add("seveneightnine"));
174: assertTrue(tree.add("seveneightnine1"));
175: assertTrue(tree.add("seveneightnine2"));
176: assertTrue(tree.add("seveneightnine3"));
177: assertTrue(tree.add("somethingdifferent"));
178:
179: assertTrue(tree.size() == 13);
180: testSizeByIterator(tree);
181: assertTrue(tree.iterator().hasNext());
182:
183: List l;
184:
185: l = tree.getSuggestions("", 13);
186: assertTrue("Expected size of 13, got " + l.size(),
187: l.size() == 13);
188: assertAllStartWith(l, "");
189:
190: l = tree.getSuggestions("one", 10);
191: assertTrue("Expected size of 4, got " + l.size(), l.size() == 4);
192: assertAllStartWith(l, "one");
193:
194: l = tree.getSuggestions("onetwothree", 10);
195: assertTrue("Expected size of 4, got " + l.size(), l.size() == 4);
196: assertAllStartWith(l, "onetwothree");
197:
198: l = tree.getSuggestions("onetwothree1", 10);
199: assertTrue("Expected size of 1, got " + l.size(), l.size() == 1);
200: assertAllStartWith(l, "onetwothree1");
201:
202: l = tree.getSuggestions("o", 1);
203: assertTrue("Expected size of 1, got " + l.size(), l.size() == 1);
204: assertTrue(((String) l.get(0)).endsWith("..."));
205: assertAllStartWith(l, "o");
206:
207: l = tree.getSuggestions("something", 1);
208: assertTrue("Expected size of 1, got " + l.size(), l.size() == 1);
209: assertEquals("somethingdifferent", l.get(0));
210: assertAllStartWith(l, "somethingdifferent");
211: }
212:
213: protected void assertAllStartWith(List l, String prefix) {
214: for (final Iterator i = l.iterator(); i.hasNext();) {
215: final String test = (String) i.next();
216: assertTrue(test + " does not start with " + prefix, test
217: .startsWith(prefix));
218: }
219: }
220:
221: /**
222: * Ensure that size() reports the same number of items that the iterator
223: * produces.
224: *
225: * @param tree the tree to test
226: */
227: protected void testSizeByIterator(PrefixTree tree) {
228: int count = 0;
229: for (final Iterator i = tree.iterator(); i.hasNext();) {
230: i.next();
231: count++;
232: }
233:
234: assertTrue("Iteration count " + count + " did not match size "
235: + tree.size(), count == tree.size());
236: }
237: }
|