KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*
2  * Copyright 2007 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 package com.google.gwt.user.client.ui;
17
18 import com.google.gwt.user.client.rpc.IsSerializable;
19
20 import java.util.ArrayList JavaDoc;
21 import java.util.Collection JavaDoc;
22 import java.util.Collections JavaDoc;
23 import java.util.HashMap JavaDoc;
24 import java.util.HashSet JavaDoc;
25 import java.util.Iterator JavaDoc;
26 import java.util.List JavaDoc;
27
28 /**
29  * The default {@link com.google.gwt.user.client.ui.SuggestOracle}. The default
30  * oracle returns potential suggestions based on breaking the query into
31  * separate words and looking for matches. It also modifies the returned text to
32  * show which prefix matched the query term. The matching is case insensitive.
33  * All suggestions are sorted before being passed into a response.
34  * <p>
35  * Example Table
36  * </p>
37  * <p>
38  * <table width = "100%" border = "1">
39  * <tr>
40  * <td><b> All Suggestions </b> </td>
41  * <td><b>Query string</b> </td>
42  * <td><b>Matching Suggestions</b></td>
43  * </tr>
44  * <tr>
45  * <td> John Smith, Joe Brown, Jane Doe, Jane Smith, Bob Jones</td>
46  * <td> Jo</td>
47  * <td> John Smith, Joe Brown, Bob Jones</td>
48  * </tr>
49  * <tr>
50  * <td> John Smith, Joe Brown, Jane Doe, Jane Smith, Bob Jones</td>
51  * <td> Smith</td>
52  * <td> John Smith, Jane Smith</td>
53  * </tr>
54  * <tr>
55  * <td> Georgia, New York, California</td>
56  * <td> g</td>
57  * <td> Georgia</td>
58  * </tr>
59  * </table>
60  * </p>
61  */

62 public final class MultiWordSuggestOracle extends SuggestOracle {
63
64   /**
65    * Suggestion class for {@link MultiWordSuggestOracle}.
66    */

67   public static class MultiWordSuggestion implements Suggestion, IsSerializable {
68     private String JavaDoc value;
69     private String JavaDoc displayString;
70
71     /**
72      * Constructor used by RPC.
73      */

74     public MultiWordSuggestion() {
75     }
76     
77     /**
78      * Constructor for <code>MultiWordSuggestion</code>.
79      *
80      * @param value the value
81      * @param displayString the display string
82      */

83     public MultiWordSuggestion(String JavaDoc value, String JavaDoc displayString) {
84       this.value = value;
85       this.displayString = displayString;
86     }
87
88     public String JavaDoc getDisplayString() {
89       return displayString;
90     }
91
92     public Object JavaDoc getValue() {
93       return value;
94     }
95   }
96
97   private static final char WHITESPACE_CHAR = ' ';
98   private static final String JavaDoc WHITESPACE_STRING = " ";
99
100   /**
101    * Regular expression used to collapse all whitespace in a query string.
102    */

103   private static final String JavaDoc NORMALIZE_TO_SINGLE_WHITE_SPACE = "\\s+";
104
105   private static HTML convertMe = new HTML();
106
107   /**
108    * Associates substrings with words.
109    */

110   private final PrefixTree tree = new PrefixTree();
111
112   /**
113    * Associates individual words with candidates.
114    */

115   private HashMap JavaDoc toCandidates = new HashMap JavaDoc();
116
117   /**
118    * Associates candidates with their formatted suggestions.
119    */

120   private HashMap JavaDoc toRealSuggestions = new HashMap JavaDoc();
121
122   /**
123    * The whitespace masks used to prevent matching and replacing of the given
124    * substrings.
125    */

126   private char[] whitespaceChars;
127
128   /**
129    * Constructor for <code>MultiWordSuggestOracle</code>. This uses a space as
130    * the whitespace character.
131    *
132    * @see #MultiWordSuggestOracle(String)
133    */

134   public MultiWordSuggestOracle() {
135     this(" ");
136   }
137
138   /**
139    * Constructor for <code>MultiWordSuggestOracle</code> which takes in a set
140    * of whitespace chars that filter its input.
141    * <p>
142    * Example: If <code>".,"</code> is passed in as whitespace, then the string
143    * "foo.bar" would match the queries "foo", "bar", "foo.bar", "foo...bar", and
144    * "foo, bar". If the empty string is used, then all characters are used in
145    * matching. For example, the query "bar" would match "bar", but not "foo
146    * bar".
147    * </p>
148    *
149    * @param whitespaceChars the characters to treat as word separators
150    */

151   public MultiWordSuggestOracle(String JavaDoc whitespaceChars) {
152     this.whitespaceChars = new char[whitespaceChars.length()];
153     for (int i = 0; i < whitespaceChars.length(); i++) {
154       this.whitespaceChars[i] = whitespaceChars.charAt(i);
155     }
156   }
157
158   /**
159    * Adds a suggestion to the oracle. Each suggestion must be plain text.
160    *
161    * @param suggestion the suggestion
162    */

163   public void add(String JavaDoc suggestion) {
164     String JavaDoc candidate = normalizeSuggestion(suggestion);
165     // candidates --> real suggestions.
166
toRealSuggestions.put(candidate, suggestion);
167
168     // word fragments --> candidates.
169
String JavaDoc[] words = candidate.split(WHITESPACE_STRING);
170     for (int i = 0; i < words.length; i++) {
171       String JavaDoc word = words[i];
172       tree.add(word);
173       HashSet JavaDoc l = (HashSet JavaDoc) toCandidates.get(word);
174       if (l == null) {
175         l = new HashSet JavaDoc();
176         toCandidates.put(word, l);
177       }
178       l.add(candidate);
179     }
180   }
181
182   /**
183    * Adds all suggestions specified. Each suggestion must be plain text.
184    *
185    * @param collection the collection
186    */

187   public void addAll(Collection JavaDoc collection) {
188     Iterator JavaDoc suggestions = collection.iterator();
189     while (suggestions.hasNext()) {
190       add((String JavaDoc) suggestions.next());
191     }
192   }
193
194   public boolean isDisplayStringHTML() {
195     return true;
196   }
197
198   public void requestSuggestions(Request request, Callback callback) {
199     final List JavaDoc suggestions = computeItemsFor(request.getQuery(), request
200       .getLimit());
201     Response response = new Response(suggestions);
202     callback.onSuggestionsReady(request, response);
203   }
204
205   String JavaDoc escapeText(String JavaDoc escapeMe) {
206     convertMe.setText(escapeMe);
207     String JavaDoc escaped = convertMe.getHTML();
208     return escaped;
209   }
210
211   /**
212    * Compute the suggestions that are matches for a given query.
213    *
214    * @param query search string
215    * @param limit limit
216    * @return matching suggestions
217    */

218   private List JavaDoc computeItemsFor(String JavaDoc query, int limit) {
219     query = normalizeSearch(query);
220
221     // Get candidates from search words.
222
List JavaDoc candidates = createCandidatesFromSearch(query, limit);
223
224     // Convert candidates to suggestions.
225
return convertToFormattedSuggestions(query, candidates);
226   }
227
228   /**
229    * Returns real suggestions with the given query in <code>strong</code> html
230    * font.
231    *
232    * @param query query string
233    * @param candidates candidates
234    * @return real suggestions
235    */

236   private List JavaDoc convertToFormattedSuggestions(String JavaDoc query, List JavaDoc candidates) {
237     List JavaDoc suggestions = new ArrayList JavaDoc();
238
239     for (int i = 0; i < candidates.size(); i++) {
240       String JavaDoc candidate = (String JavaDoc) candidates.get(i);
241       int index = 0;
242       int cursor = 0;
243       // Use real suggestion for assembly.
244
String JavaDoc formattedSuggestion = (String JavaDoc) toRealSuggestions.get(candidate);
245
246       // Create strong search string.
247
StringBuffer JavaDoc accum = new StringBuffer JavaDoc();
248
249       while (true) {
250         index = candidate.indexOf(query, index);
251         if (index == -1) {
252           break;
253         }
254         int endIndex = index + query.length();
255         if (index == 0 || (WHITESPACE_CHAR == candidate.charAt(index - 1))) {
256           String JavaDoc part1 = escapeText(formattedSuggestion
257             .substring(cursor, index));
258           String JavaDoc part2 = escapeText(formattedSuggestion.substring(index,
259             endIndex));
260           cursor = endIndex;
261           accum.append(part1).append("<strong>").append(part2).append(
262             "</strong>");
263         }
264         index = endIndex;
265       }
266
267       // Check to make sure the search was found in the string.
268
if (cursor == 0) {
269         continue;
270       }
271
272       // Finish creating the formatted string.
273
String JavaDoc end = escapeText(formattedSuggestion.substring(cursor));
274       accum.append(end);
275       MultiWordSuggestion suggestion = new MultiWordSuggestion(
276         formattedSuggestion, accum.toString());
277       suggestions.add(suggestion);
278     }
279     return suggestions;
280   }
281
282   /**
283    * Find the sorted list of candidates that are matches for the given query.
284    */

285   private List JavaDoc createCandidatesFromSearch(String JavaDoc query, int limit) {
286     ArrayList JavaDoc candidates = new ArrayList JavaDoc();
287
288     if (query.length() == 0) {
289       return candidates;
290     }
291
292     // Find all words to search for.
293
String JavaDoc[] searchWords = query.split(WHITESPACE_STRING);
294     HashSet JavaDoc candidateSet = null;
295     for (int i = 0; i < searchWords.length; i++) {
296       String JavaDoc word = searchWords[i];
297
298       // Eliminate bogus word choices.
299
if (word.length() == 0 || word.matches(WHITESPACE_STRING)) {
300         continue;
301       }
302
303       // Find the set of candidates that are associated with all the
304
// searchWords.
305
HashSet JavaDoc thisWordChoices = createCandidatesFromWord(word);
306       if (candidateSet == null) {
307         candidateSet = thisWordChoices;
308       } else {
309         candidateSet.retainAll(thisWordChoices);
310
311         if (candidateSet.size() < 2) {
312           // If there is only one candidate, on average it is cheaper to
313
// check if that candidate contains our search string than to
314
// continue intersecting suggestion sets.
315
break;
316         }
317       }
318     }
319     if (candidateSet != null) {
320       candidates.addAll(candidateSet);
321       Collections.sort(candidates);
322       // Respect limit for number of choices.
323
for (int i = candidates.size() - 1; i > limit; i--) {
324         candidates.remove(i);
325       }
326     }
327     return candidates;
328   }
329
330   /**
331    * Creates a set of potential candidates that match the given query.
332    *
333    * @param limit number of candidates to return
334    * @param query query string
335    * @return possible candidates
336    */

337   private HashSet JavaDoc createCandidatesFromWord(String JavaDoc query) {
338     HashSet JavaDoc candidateSet = new HashSet JavaDoc();
339     List JavaDoc words = tree.getSuggestions(query, Integer.MAX_VALUE);
340     if (words != null) {
341       // Find all candidates that contain the given word the search is a
342
// subset of.
343
for (int i = 0; i < words.size(); i++) {
344         Collection JavaDoc belongsTo = (Collection JavaDoc) toCandidates.get(words.get(i));
345         if (belongsTo != null) {
346           candidateSet.addAll(belongsTo);
347         }
348       }
349     }
350     return candidateSet;
351   }
352
353   /**
354    * Normalize the search key by making it lower case, removing multiple spaces,
355    * apply whitespace masks, and make it lower case.
356    */

357   private String JavaDoc normalizeSearch(String JavaDoc search) {
358     // Use the same whitespace masks and case normalization for the search
359
// string as was used with the candidate values.
360
search = normalizeSuggestion(search);
361
362     // Remove all excess whitespace from the search string.
363
search = search.replaceAll(NORMALIZE_TO_SINGLE_WHITE_SPACE,
364       WHITESPACE_STRING);
365
366     return search.trim();
367   }
368
369   /**
370    * Takes the formatted suggestion, makes it lower case and blanks out any
371    * existing whitespace for searching.
372    */

373   private String JavaDoc normalizeSuggestion(String JavaDoc formattedSuggestion) {
374     // Formatted suggestions should already have normalized whitespace. So we
375
// can skip that step.
376

377     // Lower case suggestion.
378
formattedSuggestion = formattedSuggestion.toLowerCase();
379
380     // Apply whitespace.
381
if (whitespaceChars != null) {
382       for (int i = 0; i < whitespaceChars.length; i++) {
383         char ignore = whitespaceChars[i];
384         formattedSuggestion = formattedSuggestion.replace(ignore,
385           WHITESPACE_CHAR);
386       }
387     }
388     return formattedSuggestion;
389   }
390 }
391
Popular Tags