2.1/user/src/com/google/gwt/user/client/ui/MultiWordSuggestOracle.java - gwt - Git at Google

 /*
  * Copyright 2007 Google Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
  * use this file except in compliance with the License. You may obtain a copy of
  * the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  * License for the specific language governing permissions and limitations under
  * the License.
  */
 package com.google.gwt.user.client.ui;

 import com.google.gwt.safehtml.shared.SafeHtmlBuilder;
 import com.google.gwt.user.client.rpc.IsSerializable;

 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Set;

 /**
  * The default {@link com.google.gwt.user.client.ui.SuggestOracle}. The default
  * oracle returns potential suggestions based on breaking the query into
  * separate words and looking for matches. It also modifies the returned text to
  * show which prefix matched the query term. The matching is case insensitive.
  * All suggestions are sorted before being passed into a response.
  * <p>
  * Example Table
  * </p>
  * <p>
  * <table width = "100%" border = "1">
  * <tr>
  * <td><b> All Suggestions </b></td>
  * <td><b>Query string</b></td>
  * <td><b>Matching Suggestions</b></td>
  * </tr>
  * <tr>
  * <td>John Smith, Joe Brown, Jane Doe, Jane Smith, Bob Jones</td>
  * <td>Jo</td>
  * <td>John Smith, Joe Brown, Bob Jones</td>
  * </tr>
  * <tr>
  * <td>John Smith, Joe Brown, Jane Doe, Jane Smith, Bob Jones</td>
  * <td>Smith</td>
  * <td>John Smith, Jane Smith</td>
  * </tr>
  * <tr>
  * <td>Georgia, New York, California</td>
  * <td>g</td>
  * <td>Georgia</td>
  * </tr>
  * </table>
  * </p>
  */
 public class MultiWordSuggestOracle extends SuggestOracle {

   /**
    * Suggestion class for {@link MultiWordSuggestOracle}.
    */
   public static class MultiWordSuggestion implements Suggestion, IsSerializable {
     private String displayString;
     private String replacementString;

     /**
      * Constructor used by RPC.
      */
     public MultiWordSuggestion() {
     }

     /**
      * Constructor for <code>MultiWordSuggestion</code>.
      *
      * @param replacementString the string to enter into the SuggestBox's text
      *          box if the suggestion is chosen
      * @param displayString the display string
      */
     public MultiWordSuggestion(String replacementString, String displayString) {
       this.replacementString = replacementString;
       this.displayString = displayString;
     }

     public String getDisplayString() {
       return displayString;
     }

     public String getReplacementString() {
       return replacementString;
     }
   }

   /**
    * A class reresenting the bounds of a word within a string.
    *
    * The bounds are represented by a {@code startIndex} (inclusive) and
    * an {@code endIndex} (exclusive).
    */
   private static class WordBounds implements Comparable<WordBounds> {

     final int startIndex;
     final int endIndex;

     public WordBounds(int startIndex, int length) {
       this.startIndex = startIndex;
       this.endIndex = startIndex + length;
     }

     public int compareTo(WordBounds that) {
       int comparison = this.startIndex - that.startIndex;
       if (comparison == 0) {
         comparison = that.endIndex - this.endIndex;
       }
       return comparison;
     }
   }

   private static final char WHITESPACE_CHAR = ' ';
   private static final String WHITESPACE_STRING = " ";

   /**
    * Regular expression used to collapse all whitespace in a query string.
    */
   private static final String NORMALIZE_TO_SINGLE_WHITE_SPACE = "\\s+";

   /**
    * Associates substrings with words.
    */
   private final PrefixTree tree = new PrefixTree();

   /**
    * Associates individual words with candidates.
    */
   private HashMap<String, Set<String>> toCandidates = new HashMap<String, Set<String>>();

   /**
    * Associates candidates with their formatted suggestions.
    */
   private HashMap<String, String> toRealSuggestions = new HashMap<String, String>();

   /**
    * The whitespace masks used to prevent matching and replacing of the given
    * substrings.
    */
   private char[] whitespaceChars;

   private Response defaultResponse;

   /**
    * Constructor for <code>MultiWordSuggestOracle</code>. This uses a space as
    * the whitespace character.
    *
    * @see #MultiWordSuggestOracle(String)
    */
   public MultiWordSuggestOracle() {
     this(" ");
   }

   /**
    * Constructor for <code>MultiWordSuggestOracle</code> which takes in a set of
    * whitespace chars that filter its input.
    * <p>
    * Example: If <code>".,"</code> is passed in as whitespace, then the string
    * "foo.bar" would match the queries "foo", "bar", "foo.bar", "foo...bar", and
    * "foo, bar". If the empty string is used, then all characters are used in
    * matching. For example, the query "bar" would match "bar", but not "foo
    * bar".
    * </p>
    *
    * @param whitespaceChars the characters to treat as word separators
    */
   public MultiWordSuggestOracle(String whitespaceChars) {
     this.whitespaceChars = new char[whitespaceChars.length()];
     for (int i = 0; i < whitespaceChars.length(); i++) {
       this.whitespaceChars[i] = whitespaceChars.charAt(i);
     }
   }

   /**
    * Adds a suggestion to the oracle. Each suggestion must be plain text.
    *
    * @param suggestion the suggestion
    */
   public void add(String suggestion) {
     String candidate = normalizeSuggestion(suggestion);
     // candidates --> real suggestions.
     toRealSuggestions.put(candidate, suggestion);

     // word fragments --> candidates.
     String[] words = candidate.split(WHITESPACE_STRING);
     for (int i = 0; i < words.length; i++) {
       String word = words[i];
       tree.add(word);
       Set<String> l = toCandidates.get(word);
       if (l == null) {
         l = new HashSet<String>();
         toCandidates.put(word, l);
       }
       l.add(candidate);
     }
   }

   /**
    * Adds all suggestions specified. Each suggestion must be plain text.
    *
    * @param collection the collection
    */
   public final void addAll(Collection<String> collection) {
     for (String suggestion : collection) {
       add(suggestion);
     }
   }

   /**
    * Removes all of the suggestions from the oracle.
    */
   public void clear() {
     tree.clear();
     toCandidates.clear();
     toRealSuggestions.clear();
   }

   @Override
   public boolean isDisplayStringHTML() {
     return true;
   }

   @Override
   public void requestDefaultSuggestions(Request request, Callback callback) {
     if (defaultResponse != null) {
       callback.onSuggestionsReady(request, defaultResponse);
     } else {
       super.requestDefaultSuggestions(request, callback);
     }
   }

   @Override
   public void requestSuggestions(Request request, Callback callback) {
     String query = normalizeSearch(request.getQuery());
     int limit = request.getLimit();

     // Get candidates from search words.
     List<String> candidates = createCandidatesFromSearch(query);

     // Respect limit for number of choices.
     int numberTruncated = Math.max(0, candidates.size() - limit);
     for (int i = candidates.size() - 1; i > limit; i--) {
       candidates.remove(i);
     }

     // Convert candidates to suggestions.
     List<MultiWordSuggestion> suggestions =
         convertToFormattedSuggestions(query, candidates);

     Response response = new Response(suggestions);
     response.setMoreSuggestionsCount(numberTruncated);

     callback.onSuggestionsReady(request, response);
   }

   /**
    * Sets the default suggestion collection.
    *
    * @param suggestionList the default list of suggestions
    */
   public void setDefaultSuggestions(Collection<Suggestion> suggestionList) {
     this.defaultResponse = new Response(suggestionList);
   }

   /**
    * A convenience method to set default suggestions using plain text strings.
    *
    * Note to use this method each default suggestion must be plain text.
    *
    * @param suggestionList the default list of suggestions
    */
   public final void setDefaultSuggestionsFromText(
       Collection<String> suggestionList) {
     Collection<Suggestion> accum = new ArrayList<Suggestion>();
     for (String candidate : suggestionList) {
       accum.add(createSuggestion(candidate, candidate));
     }
     setDefaultSuggestions(accum);
   }

   /**
    * Creates the suggestion based on the given replacement and display strings.
    *
    * @param replacementString the string to enter into the SuggestBox's text box
    *          if the suggestion is chosen
    * @param displayString the display string
    *
    * @return the suggestion created
    */
   protected MultiWordSuggestion createSuggestion(String replacementString,
       String displayString) {
     return new MultiWordSuggestion(replacementString, displayString);
   }

   /**
    * Returns real suggestions with the given query in <code>strong</code> html
    * font.
    *
    * @param query query string
    * @param candidates candidates
    * @return real suggestions
    */
   private List<MultiWordSuggestion> convertToFormattedSuggestions(String query,
       List<String> candidates) {
     List<MultiWordSuggestion> suggestions = new ArrayList<MultiWordSuggestion>();

     for (int i = 0; i < candidates.size(); i++) {
       String candidate = candidates.get(i);
       int cursor = 0;
       int index = 0;
       // Use real suggestion for assembly.
       String formattedSuggestion = toRealSuggestions.get(candidate);

       // Create strong search string.
       SafeHtmlBuilder accum = new SafeHtmlBuilder();

       String[] searchWords = query.split(WHITESPACE_STRING);
       while (true) {
         WordBounds wordBounds = findNextWord(candidate, searchWords, index);
         if (wordBounds == null) {
           break;
         }
         if (wordBounds.startIndex == 0 ||
             WHITESPACE_CHAR == candidate.charAt(wordBounds.startIndex - 1)) {
           String part1 = formattedSuggestion.substring(cursor, wordBounds.startIndex);
           String part2 = formattedSuggestion.substring(wordBounds.startIndex,
               wordBounds.endIndex);
           cursor = wordBounds.endIndex;
           accum.appendEscaped(part1);
           accum.appendHtmlConstant("<strong>");
           accum.appendEscaped(part2);
           accum.appendHtmlConstant("</strong>");
         }
         index = wordBounds.endIndex;
       }

       // Check to make sure the search was found in the string.
       if (cursor == 0) {
         continue;
       }

       accum.appendEscaped(formattedSuggestion.substring(cursor));
       MultiWordSuggestion suggestion = createSuggestion(formattedSuggestion,
           accum.toSafeHtml().asString());
       suggestions.add(suggestion);
     }
     return suggestions;
   }

   /**
    * Find the sorted list of candidates that are matches for the given query.
    */
   private List<String> createCandidatesFromSearch(String query) {
     ArrayList<String> candidates = new ArrayList<String>();

     if (query.length() == 0) {
       return candidates;
     }

     // Find all words to search for.
     String[] searchWords = query.split(WHITESPACE_STRING);
     HashSet<String> candidateSet = null;
     for (int i = 0; i < searchWords.length; i++) {
       String word = searchWords[i];

       // Eliminate bogus word choices.
       if (word.length() == 0 || word.matches(WHITESPACE_STRING)) {
         continue;
       }

       // Find the set of candidates that are associated with all the
       // searchWords.
       HashSet<String> thisWordChoices = createCandidatesFromWord(word);
       if (candidateSet == null) {
         candidateSet = thisWordChoices;
       } else {
         candidateSet.retainAll(thisWordChoices);

         if (candidateSet.size() < 2) {
           // If there is only one candidate, on average it is cheaper to
           // check if that candidate contains our search string than to
           // continue intersecting suggestion sets.
           break;
         }
       }
     }
     if (candidateSet != null) {
       candidates.addAll(candidateSet);
       Collections.sort(candidates);
     }
     return candidates;
   }

   /**
    * Creates a set of potential candidates that match the given query.
    *
    * @param query query string
    * @return possible candidates
    */
   private HashSet<String> createCandidatesFromWord(String query) {
     HashSet<String> candidateSet = new HashSet<String>();
     List<String> words = tree.getSuggestions(query, Integer.MAX_VALUE);
     if (words != null) {
       // Find all candidates that contain the given word the search is a
       // subset of.
       for (int i = 0; i < words.size(); i++) {
         Collection<String> belongsTo = toCandidates.get(words.get(i));
         if (belongsTo != null) {
           candidateSet.addAll(belongsTo);
         }
       }
     }
     return candidateSet;
   }

   /**
    * @return a {@link WordBounds} representing the first word in
    *     {@code searchWords} that is found in candidate starting at
    *     {@code indexToStartAt} or {@code null} if no words could be found.
    */
   private WordBounds findNextWord(String candidate, String[] searchWords, int indexToStartAt) {
     WordBounds firstWord = null;
     for (String word : searchWords) {
       int index = candidate.indexOf(word, indexToStartAt);
       if (index != -1) {
         WordBounds newWord = new WordBounds(index, word.length());
         if (firstWord == null || newWord.compareTo(firstWord) < 0) {
           firstWord = newWord;
         }
       }
     }
     return firstWord;
   }

   /**
    * Normalize the search key by making it lower case, removing multiple spaces,
    * apply whitespace masks, and make it lower case.
    */
   private String normalizeSearch(String search) {
     // Use the same whitespace masks and case normalization for the search
     // string as was used with the candidate values.
     search = normalizeSuggestion(search);

     // Remove all excess whitespace from the search string.
     search = search.replaceAll(NORMALIZE_TO_SINGLE_WHITE_SPACE,
         WHITESPACE_STRING);

     return search.trim();
   }

   /**
    * Takes the formatted suggestion, makes it lower case and blanks out any
    * existing whitespace for searching.
    */
   private String normalizeSuggestion(String formattedSuggestion) {
     // Formatted suggestions should already have normalized whitespace. So we
     // can skip that step.

     // Lower case suggestion.
     formattedSuggestion = formattedSuggestion.toLowerCase();

     // Apply whitespace.
     if (whitespaceChars != null) {
       for (int i = 0; i < whitespaceChars.length; i++) {
         char ignore = whitespaceChars[i];
         formattedSuggestion = formattedSuggestion.replace(ignore,
             WHITESPACE_CHAR);
       }
     }
     return formattedSuggestion;
   }
 }
	/*
	* Copyright 2007 Google Inc.
	*
	* Licensed under the Apache License, Version 2.0 (the "License"); you may not
	* use this file except in compliance with the License. You may obtain a copy of
	* the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
	* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
	* License for the specific language governing permissions and limitations under
	* the License.
	*/
	package com.google.gwt.user.client.ui;

	import com.google.gwt.safehtml.shared.SafeHtmlBuilder;
	import com.google.gwt.user.client.rpc.IsSerializable;

	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Collections;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Set;

	/**
	* The default {@link com.google.gwt.user.client.ui.SuggestOracle}. The default
	* oracle returns potential suggestions based on breaking the query into
	* separate words and looking for matches. It also modifies the returned text to
	* show which prefix matched the query term. The matching is case insensitive.
	* All suggestions are sorted before being passed into a response.
	* <p>
	* Example Table
	* </p>
	* <p>
	* <table width = "100%" border = "1">
	* <tr>
	* <td><b> All Suggestions </b></td>
	* <td><b>Query string</b></td>
	* <td><b>Matching Suggestions</b></td>
	* </tr>
	* <tr>
	* <td>John Smith, Joe Brown, Jane Doe, Jane Smith, Bob Jones</td>
	* <td>Jo</td>
	* <td>John Smith, Joe Brown, Bob Jones</td>
	* </tr>
	* <tr>
	* <td>John Smith, Joe Brown, Jane Doe, Jane Smith, Bob Jones</td>
	* <td>Smith</td>
	* <td>John Smith, Jane Smith</td>
	* </tr>
	* <tr>
	* <td>Georgia, New York, California</td>
	* <td>g</td>
	* <td>Georgia</td>
	* </tr>
	* </table>
	* </p>
	*/
	public class MultiWordSuggestOracle extends SuggestOracle {

	/**
	* Suggestion class for {@link MultiWordSuggestOracle}.
	*/
	public static class MultiWordSuggestion implements Suggestion, IsSerializable {
	private String displayString;
	private String replacementString;

	/**
	* Constructor used by RPC.
	*/
	public MultiWordSuggestion() {
	}

	/**
	* Constructor for <code>MultiWordSuggestion</code>.
	*
	* @param replacementString the string to enter into the SuggestBox's text
	* box if the suggestion is chosen
	* @param displayString the display string
	*/
	public MultiWordSuggestion(String replacementString, String displayString) {
	this.replacementString = replacementString;
	this.displayString = displayString;
	}

	public String getDisplayString() {
	return displayString;
	}

	public String getReplacementString() {
	return replacementString;
	}
	}

	/**
	* A class reresenting the bounds of a word within a string.
	*
	* The bounds are represented by a {@code startIndex} (inclusive) and
	* an {@code endIndex} (exclusive).
	*/
	private static class WordBounds implements Comparable<WordBounds> {

	final int startIndex;
	final int endIndex;

	public WordBounds(int startIndex, int length) {
	this.startIndex = startIndex;
	this.endIndex = startIndex + length;
	}

	public int compareTo(WordBounds that) {
	int comparison = this.startIndex - that.startIndex;
	if (comparison == 0) {
	comparison = that.endIndex - this.endIndex;
	}
	return comparison;
	}
	}

	private static final char WHITESPACE_CHAR = ' ';
	private static final String WHITESPACE_STRING = " ";

	/**
	* Regular expression used to collapse all whitespace in a query string.
	*/
	private static final String NORMALIZE_TO_SINGLE_WHITE_SPACE = "\\s+";

	/**
	* Associates substrings with words.
	*/
	private final PrefixTree tree = new PrefixTree();

	/**
	* Associates individual words with candidates.
	*/
	private HashMap<String, Set<String>> toCandidates = new HashMap<String, Set<String>>();

	/**
	* Associates candidates with their formatted suggestions.
	*/
	private HashMap<String, String> toRealSuggestions = new HashMap<String, String>();

	/**
	* The whitespace masks used to prevent matching and replacing of the given
	* substrings.
	*/
	private char[] whitespaceChars;

	private Response defaultResponse;

	/**
	* Constructor for <code>MultiWordSuggestOracle</code>. This uses a space as
	* the whitespace character.
	*
	* @see #MultiWordSuggestOracle(String)
	*/
	public MultiWordSuggestOracle() {
	this(" ");
	}

	/**
	* Constructor for <code>MultiWordSuggestOracle</code> which takes in a set of
	* whitespace chars that filter its input.
	* <p>
	* Example: If <code>".,"</code> is passed in as whitespace, then the string
	* "foo.bar" would match the queries "foo", "bar", "foo.bar", "foo...bar", and
	* "foo, bar". If the empty string is used, then all characters are used in
	* matching. For example, the query "bar" would match "bar", but not "foo
	* bar".
	* </p>
	*
	* @param whitespaceChars the characters to treat as word separators
	*/
	public MultiWordSuggestOracle(String whitespaceChars) {
	this.whitespaceChars = new char[whitespaceChars.length()];
	for (int i = 0; i < whitespaceChars.length(); i++) {
	this.whitespaceChars[i] = whitespaceChars.charAt(i);
	}
	}

	/**
	* Adds a suggestion to the oracle. Each suggestion must be plain text.
	*
	* @param suggestion the suggestion
	*/
	public void add(String suggestion) {
	String candidate = normalizeSuggestion(suggestion);
	// candidates --> real suggestions.
	toRealSuggestions.put(candidate, suggestion);

	// word fragments --> candidates.
	String[] words = candidate.split(WHITESPACE_STRING);
	for (int i = 0; i < words.length; i++) {
	String word = words[i];
	tree.add(word);
	Set<String> l = toCandidates.get(word);
	if (l == null) {
	l = new HashSet<String>();
	toCandidates.put(word, l);
	}
	l.add(candidate);
	}
	}

	/**
	* Adds all suggestions specified. Each suggestion must be plain text.
	*
	* @param collection the collection
	*/
	public final void addAll(Collection<String> collection) {
	for (String suggestion : collection) {
	add(suggestion);
	}
	}

	/**
	* Removes all of the suggestions from the oracle.
	*/
	public void clear() {
	tree.clear();
	toCandidates.clear();
	toRealSuggestions.clear();
	}

	@Override
	public boolean isDisplayStringHTML() {
	return true;
	}

	@Override
	public void requestDefaultSuggestions(Request request, Callback callback) {
	if (defaultResponse != null) {
	callback.onSuggestionsReady(request, defaultResponse);
	} else {
	super.requestDefaultSuggestions(request, callback);
	}
	}

	@Override
	public void requestSuggestions(Request request, Callback callback) {
	String query = normalizeSearch(request.getQuery());
	int limit = request.getLimit();

	// Get candidates from search words.
	List<String> candidates = createCandidatesFromSearch(query);

	// Respect limit for number of choices.
	int numberTruncated = Math.max(0, candidates.size() - limit);
	for (int i = candidates.size() - 1; i > limit; i--) {
	candidates.remove(i);
	}

	// Convert candidates to suggestions.
	List<MultiWordSuggestion> suggestions =
	convertToFormattedSuggestions(query, candidates);

	Response response = new Response(suggestions);
	response.setMoreSuggestionsCount(numberTruncated);

	callback.onSuggestionsReady(request, response);
	}

	/**
	* Sets the default suggestion collection.
	*
	* @param suggestionList the default list of suggestions
	*/
	public void setDefaultSuggestions(Collection<Suggestion> suggestionList) {
	this.defaultResponse = new Response(suggestionList);
	}

	/**
	* A convenience method to set default suggestions using plain text strings.
	*
	* Note to use this method each default suggestion must be plain text.
	*
	* @param suggestionList the default list of suggestions
	*/
	public final void setDefaultSuggestionsFromText(
	Collection<String> suggestionList) {
	Collection<Suggestion> accum = new ArrayList<Suggestion>();
	for (String candidate : suggestionList) {
	accum.add(createSuggestion(candidate, candidate));
	}
	setDefaultSuggestions(accum);
	}

	/**
	* Creates the suggestion based on the given replacement and display strings.
	*
	* @param replacementString the string to enter into the SuggestBox's text box
	* if the suggestion is chosen
	* @param displayString the display string
	*
	* @return the suggestion created
	*/
	protected MultiWordSuggestion createSuggestion(String replacementString,
	String displayString) {
	return new MultiWordSuggestion(replacementString, displayString);
	}

	/**
	* Returns real suggestions with the given query in <code>strong</code> html
	* font.
	*
	* @param query query string
	* @param candidates candidates
	* @return real suggestions
	*/
	private List<MultiWordSuggestion> convertToFormattedSuggestions(String query,
	List<String> candidates) {
	List<MultiWordSuggestion> suggestions = new ArrayList<MultiWordSuggestion>();

	for (int i = 0; i < candidates.size(); i++) {
	String candidate = candidates.get(i);
	int cursor = 0;
	int index = 0;
	// Use real suggestion for assembly.
	String formattedSuggestion = toRealSuggestions.get(candidate);

	// Create strong search string.
	SafeHtmlBuilder accum = new SafeHtmlBuilder();

	String[] searchWords = query.split(WHITESPACE_STRING);
	while (true) {
	WordBounds wordBounds = findNextWord(candidate, searchWords, index);
	if (wordBounds == null) {
	break;
	}
	if (wordBounds.startIndex == 0 \|\|
	WHITESPACE_CHAR == candidate.charAt(wordBounds.startIndex - 1)) {
	String part1 = formattedSuggestion.substring(cursor, wordBounds.startIndex);
	String part2 = formattedSuggestion.substring(wordBounds.startIndex,
	wordBounds.endIndex);
	cursor = wordBounds.endIndex;
	accum.appendEscaped(part1);
	accum.appendHtmlConstant("<strong>");
	accum.appendEscaped(part2);
	accum.appendHtmlConstant("</strong>");
	}
	index = wordBounds.endIndex;
	}

	// Check to make sure the search was found in the string.
	if (cursor == 0) {
	continue;
	}

	accum.appendEscaped(formattedSuggestion.substring(cursor));
	MultiWordSuggestion suggestion = createSuggestion(formattedSuggestion,
	accum.toSafeHtml().asString());
	suggestions.add(suggestion);
	}
	return suggestions;
	}

	/**
	* Find the sorted list of candidates that are matches for the given query.
	*/
	private List<String> createCandidatesFromSearch(String query) {
	ArrayList<String> candidates = new ArrayList<String>();

	if (query.length() == 0) {
	return candidates;
	}

	// Find all words to search for.
	String[] searchWords = query.split(WHITESPACE_STRING);
	HashSet<String> candidateSet = null;
	for (int i = 0; i < searchWords.length; i++) {
	String word = searchWords[i];

	// Eliminate bogus word choices.
	if (word.length() == 0 \|\| word.matches(WHITESPACE_STRING)) {
	continue;
	}

	// Find the set of candidates that are associated with all the
	// searchWords.
	HashSet<String> thisWordChoices = createCandidatesFromWord(word);
	if (candidateSet == null) {
	candidateSet = thisWordChoices;
	} else {
	candidateSet.retainAll(thisWordChoices);

	if (candidateSet.size() < 2) {
	// If there is only one candidate, on average it is cheaper to
	// check if that candidate contains our search string than to
	// continue intersecting suggestion sets.
	break;
	}
	}
	}
	if (candidateSet != null) {
	candidates.addAll(candidateSet);
	Collections.sort(candidates);
	}
	return candidates;
	}

	/**
	* Creates a set of potential candidates that match the given query.
	*
	* @param query query string
	* @return possible candidates
	*/
	private HashSet<String> createCandidatesFromWord(String query) {
	HashSet<String> candidateSet = new HashSet<String>();
	List<String> words = tree.getSuggestions(query, Integer.MAX_VALUE);
	if (words != null) {
	// Find all candidates that contain the given word the search is a
	// subset of.
	for (int i = 0; i < words.size(); i++) {
	Collection<String> belongsTo = toCandidates.get(words.get(i));
	if (belongsTo != null) {
	candidateSet.addAll(belongsTo);
	}
	}
	}
	return candidateSet;
	}

	/**
	* @return a {@link WordBounds} representing the first word in
	* {@code searchWords} that is found in candidate starting at
	* {@code indexToStartAt} or {@code null} if no words could be found.
	*/
	private WordBounds findNextWord(String candidate, String[] searchWords, int indexToStartAt) {
	WordBounds firstWord = null;
	for (String word : searchWords) {
	int index = candidate.indexOf(word, indexToStartAt);
	if (index != -1) {
	WordBounds newWord = new WordBounds(index, word.length());
	if (firstWord == null \|\| newWord.compareTo(firstWord) < 0) {
	firstWord = newWord;
	}
	}
	}
	return firstWord;
	}

	/**
	* Normalize the search key by making it lower case, removing multiple spaces,
	* apply whitespace masks, and make it lower case.
	*/
	private String normalizeSearch(String search) {
	// Use the same whitespace masks and case normalization for the search
	// string as was used with the candidate values.
	search = normalizeSuggestion(search);

	// Remove all excess whitespace from the search string.
	search = search.replaceAll(NORMALIZE_TO_SINGLE_WHITE_SPACE,
	WHITESPACE_STRING);

	return search.trim();
	}

	/**
	* Takes the formatted suggestion, makes it lower case and blanks out any
	* existing whitespace for searching.
	*/
	private String normalizeSuggestion(String formattedSuggestion) {
	// Formatted suggestions should already have normalized whitespace. So we
	// can skip that step.

	// Lower case suggestion.
	formattedSuggestion = formattedSuggestion.toLowerCase();

	// Apply whitespace.
	if (whitespaceChars != null) {
	for (int i = 0; i < whitespaceChars.length; i++) {
	char ignore = whitespaceChars[i];
	formattedSuggestion = formattedSuggestion.replace(ignore,
	WHITESPACE_CHAR);
	}
	}
	return formattedSuggestion;
	}
	}