1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "chrome/browser/history/in_memory_url_index_types.h" 6 7 #include <algorithm> 8 #include <functional> 9 #include <iterator> 10 #include <numeric> 11 #include <set> 12 13 #include "base/i18n/break_iterator.h" 14 #include "base/i18n/case_conversion.h" 15 #include "base/strings/string_util.h" 16 #include "net/base/escape.h" 17 #include "net/base/net_util.h" 18 19 namespace history { 20 21 // Matches within URL and Title Strings ---------------------------------------- 22 23 TermMatches MatchTermInString(const base::string16& term, 24 const base::string16& cleaned_string, 25 int term_num) { 26 const size_t kMaxCompareLength = 2048; 27 const base::string16& short_string = 28 (cleaned_string.length() > kMaxCompareLength) ? 29 cleaned_string.substr(0, kMaxCompareLength) : cleaned_string; 30 TermMatches matches; 31 for (size_t location = short_string.find(term); 32 location != base::string16::npos; 33 location = short_string.find(term, location + 1)) 34 matches.push_back(TermMatch(term_num, location, term.length())); 35 return matches; 36 } 37 38 // Comparison function for sorting TermMatches by their offsets. 39 bool MatchOffsetLess(const TermMatch& m1, const TermMatch& m2) { 40 return m1.offset < m2.offset; 41 } 42 43 TermMatches SortAndDeoverlapMatches(const TermMatches& matches) { 44 if (matches.empty()) 45 return matches; 46 TermMatches sorted_matches = matches; 47 std::sort(sorted_matches.begin(), sorted_matches.end(), MatchOffsetLess); 48 TermMatches clean_matches; 49 TermMatch last_match; 50 for (TermMatches::const_iterator iter = sorted_matches.begin(); 51 iter != sorted_matches.end(); ++iter) { 52 if (iter->offset >= last_match.offset + last_match.length) { 53 last_match = *iter; 54 clean_matches.push_back(last_match); 55 } 56 } 57 return clean_matches; 58 } 59 60 std::vector<size_t> OffsetsFromTermMatches(const TermMatches& matches) { 61 std::vector<size_t> offsets; 62 for (TermMatches::const_iterator i = matches.begin(); i != matches.end(); 63 ++i) { 64 offsets.push_back(i->offset); 65 offsets.push_back(i->offset + i->length); 66 } 67 return offsets; 68 } 69 70 TermMatches ReplaceOffsetsInTermMatches(const TermMatches& matches, 71 const std::vector<size_t>& offsets) { 72 DCHECK_EQ(2 * matches.size(), offsets.size()); 73 TermMatches new_matches; 74 std::vector<size_t>::const_iterator offset_iter = offsets.begin(); 75 for (TermMatches::const_iterator term_iter = matches.begin(); 76 term_iter != matches.end(); ++term_iter, ++offset_iter) { 77 const size_t starting_offset = *offset_iter; 78 ++offset_iter; 79 const size_t ending_offset = *offset_iter; 80 if ((starting_offset != base::string16::npos) && 81 (ending_offset != base::string16::npos) && 82 (starting_offset != ending_offset)) { 83 TermMatch new_match(*term_iter); 84 new_match.offset = starting_offset; 85 new_match.length = ending_offset - starting_offset; 86 new_matches.push_back(new_match); 87 } 88 } 89 return new_matches; 90 } 91 92 // Utility Functions ----------------------------------------------------------- 93 94 String16Set String16SetFromString16(const base::string16& cleaned_uni_string, 95 WordStarts* word_starts) { 96 String16Vector words = 97 String16VectorFromString16(cleaned_uni_string, false, word_starts); 98 String16Set word_set; 99 for (String16Vector::const_iterator iter = words.begin(); iter != words.end(); 100 ++iter) 101 word_set.insert(base::i18n::ToLower(*iter).substr(0, kMaxSignificantChars)); 102 return word_set; 103 } 104 105 String16Vector String16VectorFromString16( 106 const base::string16& cleaned_uni_string, 107 bool break_on_space, 108 WordStarts* word_starts) { 109 if (word_starts) 110 word_starts->clear(); 111 base::i18n::BreakIterator iter(cleaned_uni_string, 112 break_on_space ? base::i18n::BreakIterator::BREAK_SPACE : 113 base::i18n::BreakIterator::BREAK_WORD); 114 String16Vector words; 115 if (!iter.Init()) 116 return words; 117 while (iter.Advance()) { 118 if (break_on_space || iter.IsWord()) { 119 base::string16 word(iter.GetString()); 120 size_t initial_whitespace = 0; 121 if (break_on_space) { 122 base::string16 trimmed_word; 123 base::TrimWhitespace(word, base::TRIM_LEADING, &trimmed_word); 124 initial_whitespace = word.length() - trimmed_word.length(); 125 base::TrimWhitespace(trimmed_word, base::TRIM_TRAILING, &word); 126 } 127 if (word.empty()) 128 continue; 129 words.push_back(word); 130 if (!word_starts) 131 continue; 132 size_t word_start = iter.prev() + initial_whitespace; 133 if (word_start < kMaxSignificantChars) 134 word_starts->push_back(word_start); 135 } 136 } 137 return words; 138 } 139 140 Char16Set Char16SetFromString16(const base::string16& term) { 141 Char16Set characters; 142 for (base::string16::const_iterator iter = term.begin(); iter != term.end(); 143 ++iter) 144 characters.insert(*iter); 145 return characters; 146 } 147 148 // HistoryInfoMapValue --------------------------------------------------------- 149 150 HistoryInfoMapValue::HistoryInfoMapValue() {} 151 HistoryInfoMapValue::~HistoryInfoMapValue() {} 152 153 // RowWordStarts --------------------------------------------------------------- 154 155 RowWordStarts::RowWordStarts() {} 156 RowWordStarts::~RowWordStarts() {} 157 158 void RowWordStarts::Clear() { 159 url_word_starts_.clear(); 160 title_word_starts_.clear(); 161 } 162 163 } // namespace history 164
