/*
 * 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;
  }
}