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.user.client.rpc.IsSerializable;
019:
020: import java.util.ArrayList;
021: import java.util.Collection;
022: import java.util.Collections;
023: import java.util.HashMap;
024: import java.util.HashSet;
025: import java.util.List;
026: import java.util.Set;
027:
028: /**
029: * The default {@link com.google.gwt.user.client.ui.SuggestOracle}. The default
030: * oracle returns potential suggestions based on breaking the query into
031: * separate words and looking for matches. It also modifies the returned text to
032: * show which prefix matched the query term. The matching is case insensitive.
033: * All suggestions are sorted before being passed into a response.
034: * <p>
035: * Example Table
036: * </p>
037: * <p>
038: * <table width = "100%" border = "1">
039: * <tr>
040: * <td><b> All Suggestions </b> </td>
041: * <td><b>Query string</b> </td>
042: * <td><b>Matching Suggestions</b></td>
043: * </tr>
044: * <tr>
045: * <td> John Smith, Joe Brown, Jane Doe, Jane Smith, Bob Jones</td>
046: * <td> Jo</td>
047: * <td> John Smith, Joe Brown, Bob Jones</td>
048: * </tr>
049: * <tr>
050: * <td> John Smith, Joe Brown, Jane Doe, Jane Smith, Bob Jones</td>
051: * <td> Smith</td>
052: * <td> John Smith, Jane Smith</td>
053: * </tr>
054: * <tr>
055: * <td> Georgia, New York, California</td>
056: * <td> g</td>
057: * <td> Georgia</td>
058: * </tr>
059: * </table>
060: * </p>
061: */
062: public final class MultiWordSuggestOracle extends SuggestOracle {
063:
064: /**
065: * Suggestion class for {@link MultiWordSuggestOracle}.
066: */
067: public static class MultiWordSuggestion implements Suggestion,
068: IsSerializable {
069: private String displayString;
070: private String replacementString;
071:
072: /**
073: * Constructor used by RPC.
074: */
075: public MultiWordSuggestion() {
076: }
077:
078: /**
079: * Constructor for <code>MultiWordSuggestion</code>.
080: *
081: * @param replacementString the string to enter into the SuggestBox's text
082: * box if the suggestion is chosen
083: * @param displayString the display string
084: */
085: public MultiWordSuggestion(String replacementString,
086: String displayString) {
087: this .replacementString = replacementString;
088: this .displayString = displayString;
089: }
090:
091: public String getDisplayString() {
092: return displayString;
093: }
094:
095: public String getReplacementString() {
096: return replacementString;
097: }
098: }
099:
100: private static final char WHITESPACE_CHAR = ' ';
101: private static final String WHITESPACE_STRING = " ";
102:
103: /**
104: * Regular expression used to collapse all whitespace in a query string.
105: */
106: private static final String NORMALIZE_TO_SINGLE_WHITE_SPACE = "\\s+";
107:
108: private static HTML convertMe = new HTML();
109:
110: /**
111: * Associates substrings with words.
112: */
113: private final PrefixTree tree = new PrefixTree();
114:
115: /**
116: * Associates individual words with candidates.
117: */
118: private HashMap<String, Set<String>> toCandidates = new HashMap<String, Set<String>>();
119:
120: /**
121: * Associates candidates with their formatted suggestions.
122: */
123: private HashMap<String, String> toRealSuggestions = new HashMap<String, String>();
124:
125: /**
126: * The whitespace masks used to prevent matching and replacing of the given
127: * substrings.
128: */
129: private char[] whitespaceChars;
130:
131: /**
132: * Constructor for <code>MultiWordSuggestOracle</code>. This uses a space
133: * as the whitespace character.
134: *
135: * @see #MultiWordSuggestOracle(String)
136: */
137: public MultiWordSuggestOracle() {
138: this (" ");
139: }
140:
141: /**
142: * Constructor for <code>MultiWordSuggestOracle</code> which takes in a set
143: * of whitespace chars that filter its input.
144: * <p>
145: * Example: If <code>".,"</code> is passed in as whitespace, then the string
146: * "foo.bar" would match the queries "foo", "bar", "foo.bar", "foo...bar", and
147: * "foo, bar". If the empty string is used, then all characters are used in
148: * matching. For example, the query "bar" would match "bar", but not "foo
149: * bar".
150: * </p>
151: *
152: * @param whitespaceChars the characters to treat as word separators
153: */
154: public MultiWordSuggestOracle(String whitespaceChars) {
155: this .whitespaceChars = new char[whitespaceChars.length()];
156: for (int i = 0; i < whitespaceChars.length(); i++) {
157: this .whitespaceChars[i] = whitespaceChars.charAt(i);
158: }
159: }
160:
161: /**
162: * Adds a suggestion to the oracle. Each suggestion must be plain text.
163: *
164: * @param suggestion the suggestion
165: */
166: public void add(String suggestion) {
167: String candidate = normalizeSuggestion(suggestion);
168: // candidates --> real suggestions.
169: toRealSuggestions.put(candidate, suggestion);
170:
171: // word fragments --> candidates.
172: String[] words = candidate.split(WHITESPACE_STRING);
173: for (int i = 0; i < words.length; i++) {
174: String word = words[i];
175: tree.add(word);
176: Set<String> l = toCandidates.get(word);
177: if (l == null) {
178: l = new HashSet<String>();
179: toCandidates.put(word, l);
180: }
181: l.add(candidate);
182: }
183: }
184:
185: /**
186: * Adds all suggestions specified. Each suggestion must be plain text.
187: *
188: * @param collection the collection
189: */
190: public void addAll(Collection<String> collection) {
191: for (String suggestion : collection) {
192: add(suggestion);
193: }
194: }
195:
196: /**
197: * Removes all of the suggestions from the oracle.
198: */
199: public void clear() {
200: tree.clear();
201: toCandidates.clear();
202: toRealSuggestions.clear();
203: }
204:
205: @Override
206: public boolean isDisplayStringHTML() {
207: return true;
208: }
209:
210: @Override
211: public void requestSuggestions(Request request, Callback callback) {
212: final List<MultiWordSuggestion> suggestions = computeItemsFor(
213: request.getQuery(), request.getLimit());
214: Response response = new Response(suggestions);
215: callback.onSuggestionsReady(request, response);
216: }
217:
218: String escapeText(String escapeMe) {
219: convertMe.setText(escapeMe);
220: String escaped = convertMe.getHTML();
221: return escaped;
222: }
223:
224: /**
225: * Compute the suggestions that are matches for a given query.
226: *
227: * @param query search string
228: * @param limit limit
229: * @return matching suggestions
230: */
231: private List<MultiWordSuggestion> computeItemsFor(String query,
232: int limit) {
233: query = normalizeSearch(query);
234:
235: // Get candidates from search words.
236: List<String> candidates = createCandidatesFromSearch(query,
237: limit);
238:
239: // Convert candidates to suggestions.
240: return convertToFormattedSuggestions(query, candidates);
241: }
242:
243: /**
244: * Returns real suggestions with the given query in <code>strong</code> html
245: * font.
246: *
247: * @param query query string
248: * @param candidates candidates
249: * @return real suggestions
250: */
251: private List<MultiWordSuggestion> convertToFormattedSuggestions(
252: String query, List<String> candidates) {
253: List<MultiWordSuggestion> suggestions = new ArrayList<MultiWordSuggestion>();
254:
255: for (int i = 0; i < candidates.size(); i++) {
256: String candidate = candidates.get(i);
257: int index = 0;
258: int cursor = 0;
259: // Use real suggestion for assembly.
260: String formattedSuggestion = toRealSuggestions
261: .get(candidate);
262:
263: // Create strong search string.
264: StringBuffer accum = new StringBuffer();
265:
266: while (true) {
267: index = candidate.indexOf(query, index);
268: if (index == -1) {
269: break;
270: }
271: int endIndex = index + query.length();
272: if (index == 0
273: || (WHITESPACE_CHAR == candidate
274: .charAt(index - 1))) {
275: String part1 = escapeText(formattedSuggestion
276: .substring(cursor, index));
277: String part2 = escapeText(formattedSuggestion
278: .substring(index, endIndex));
279: cursor = endIndex;
280: accum.append(part1).append("<strong>")
281: .append(part2).append("</strong>");
282: }
283: index = endIndex;
284: }
285:
286: // Check to make sure the search was found in the string.
287: if (cursor == 0) {
288: continue;
289: }
290:
291: // Finish creating the formatted string.
292: String end = escapeText(formattedSuggestion
293: .substring(cursor));
294: accum.append(end);
295: MultiWordSuggestion suggestion = new MultiWordSuggestion(
296: formattedSuggestion, accum.toString());
297: suggestions.add(suggestion);
298: }
299: return suggestions;
300: }
301:
302: /**
303: * Find the sorted list of candidates that are matches for the given query.
304: */
305: private List<String> createCandidatesFromSearch(String query,
306: int limit) {
307: ArrayList<String> candidates = new ArrayList<String>();
308:
309: if (query.length() == 0) {
310: return candidates;
311: }
312:
313: // Find all words to search for.
314: String[] searchWords = query.split(WHITESPACE_STRING);
315: HashSet<String> candidateSet = null;
316: for (int i = 0; i < searchWords.length; i++) {
317: String word = searchWords[i];
318:
319: // Eliminate bogus word choices.
320: if (word.length() == 0 || word.matches(WHITESPACE_STRING)) {
321: continue;
322: }
323:
324: // Find the set of candidates that are associated with all the
325: // searchWords.
326: HashSet<String> this WordChoices = createCandidatesFromWord(word);
327: if (candidateSet == null) {
328: candidateSet = this WordChoices;
329: } else {
330: candidateSet.retainAll(this WordChoices);
331:
332: if (candidateSet.size() < 2) {
333: // If there is only one candidate, on average it is cheaper to
334: // check if that candidate contains our search string than to
335: // continue intersecting suggestion sets.
336: break;
337: }
338: }
339: }
340: if (candidateSet != null) {
341: candidates.addAll(candidateSet);
342: Collections.sort(candidates);
343: // Respect limit for number of choices.
344: for (int i = candidates.size() - 1; i > limit; i--) {
345: candidates.remove(i);
346: }
347: }
348: return candidates;
349: }
350:
351: /**
352: * Creates a set of potential candidates that match the given query.
353: *
354: * @param query query string
355: * @return possible candidates
356: */
357: private HashSet<String> createCandidatesFromWord(String query) {
358: HashSet<String> candidateSet = new HashSet<String>();
359: List<String> words = tree.getSuggestions(query,
360: Integer.MAX_VALUE);
361: if (words != null) {
362: // Find all candidates that contain the given word the search is a
363: // subset of.
364: for (int i = 0; i < words.size(); i++) {
365: Collection<String> belongsTo = toCandidates.get(words
366: .get(i));
367: if (belongsTo != null) {
368: candidateSet.addAll(belongsTo);
369: }
370: }
371: }
372: return candidateSet;
373: }
374:
375: /**
376: * Normalize the search key by making it lower case, removing multiple spaces,
377: * apply whitespace masks, and make it lower case.
378: */
379: private String normalizeSearch(String search) {
380: // Use the same whitespace masks and case normalization for the search
381: // string as was used with the candidate values.
382: search = normalizeSuggestion(search);
383:
384: // Remove all excess whitespace from the search string.
385: search = search.replaceAll(NORMALIZE_TO_SINGLE_WHITE_SPACE,
386: WHITESPACE_STRING);
387:
388: return search.trim();
389: }
390:
391: /**
392: * Takes the formatted suggestion, makes it lower case and blanks out any
393: * existing whitespace for searching.
394: */
395: private String normalizeSuggestion(String formattedSuggestion) {
396: // Formatted suggestions should already have normalized whitespace. So we
397: // can skip that step.
398:
399: // Lower case suggestion.
400: formattedSuggestion = formattedSuggestion.toLowerCase();
401:
402: // Apply whitespace.
403: if (whitespaceChars != null) {
404: for (int i = 0; i < whitespaceChars.length; i++) {
405: char ignore = whitespaceChars[i];
406: formattedSuggestion = formattedSuggestion.replace(
407: ignore, WHITESPACE_CHAR);
408: }
409: }
410: return formattedSuggestion;
411: }
412: }
|