text: // Copyright 2013 The Chromium Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  
  #include "chrome/browser/ui/app_list/search/tokenized_string_match.h"
  
  #include "chrome/browser/ui/app_list/search/tokenized_string_char_iterator.h"
  
  namespace app_list {
  
  namespace {
  
  // The factors below are applied when the current char of query matches
  // the current char of the text to be matched. Different factors are chosen
  // based on where the match happens. kIsPrefixMultiplier is used when the
  // matched portion is a prefix of both the query and the text, which implies
  // that the matched chars are at the same position in query and text. This is
  // the most preferred case thus it has the highest score. When the current char
  // of the query and the text does not match, the algorithm moves to the next
  // token in the text and try to match from there. kIsFrontOfWordMultipler will
  // be used if the first char of the token matches the current char of the query.
  // Otherwise, the match is considered as weak and kIsWeakHitMultiplier is
  // used.
  // Examples:
  //   Suppose the text to be matched is 'Google Chrome'.
  //   Query 'go' would yield kIsPrefixMultiplier for each char.
  //   Query 'gc' would use kIsPrefixMultiplier for 'g' and
  //       kIsFrontOfWordMultipler for 'c'.
  //   Query 'ch' would use kIsFrontOfWordMultipler for 'c' and
  //       kIsWeakHitMultiplier for 'h'.
  const double kIsPrefixMultiplier = 1.0;
  const double kIsFrontOfWordMultipler = 0.8;
  const double kIsWeakHitMultiplier = 0.6;
  
  // A relevance score that represents no match.
  const double kNoMatchScore = 0.0;
  
  }  // namespace
  
  TokenizedStringMatch::TokenizedStringMatch()
      : relevance_(kNoMatchScore) {}
  
  TokenizedStringMatch::~TokenizedStringMatch() {}
  
  bool TokenizedStringMatch::Calculate(const TokenizedString& query,
                                       const TokenizedString& text) {
    relevance_ = kNoMatchScore;
    hits_.clear();
  
    ui::Range hit = ui::Range::InvalidRange();
  
    TokenizedStringCharIterator query_iter(query);
    TokenizedStringCharIterator text_iter(text);
  
    while (!query_iter.end() && !text_iter.end()) {
      if (query_iter.Get() == text_iter.Get()) {
        if (query_iter.GetArrayPos() == text_iter.GetArrayPos())
          relevance_ += kIsPrefixMultiplier;
        else if (text_iter.IsFirstCharOfToken())
          relevance_ += kIsFrontOfWordMultipler;
        else
          relevance_ += kIsWeakHitMultiplier;
  
        if (!hit.IsValid())
          hit.set_start(text_iter.GetArrayPos());
        hit.set_end(text_iter.GetArrayPos() + text_iter.GetCharSize());
  
        query_iter.NextChar();
        text_iter.NextChar();
      } else {
        if (hit.IsValid()) {
          hits_.push_back(hit);
          hit = ui::Range::InvalidRange();
        }
  
        text_iter.NextToken();
      }
    }
  
    // No match if query is not fully consumed.
    if (!query_iter.end()) {
      relevance_ = kNoMatchScore;
      hits_.clear();
      return false;
    }
  
    if (hit.IsValid())
      hits_.push_back(hit);
  
    // Using length() for normalizing is not 100% correct but should be good
    // enough compared with using real char count of the text.
    if (text.text().length())
      relevance_ /= text.text().length();
  
    return relevance_ > kNoMatchScore;
  }
  
  bool TokenizedStringMatch::Calculate(const string16& query,
                                       const string16& text) {
    const TokenizedString tokenized_query(query);
    const TokenizedString tokenized_text(text);
    return Calculate(tokenized_query, tokenized_text);
  }
  
  }  // namespace app_list
  