OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2011 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/ui/title_prefix_matcher.h" |
| 6 |
| 7 #include "base/hash_tables.h" |
| 8 #include "base/i18n/break_iterator.h" |
| 9 #include "base/logging.h" |
| 10 |
| 11 namespace { |
| 12 const size_t kPreviouslySeenIndex = 0xFFFFFFFF; |
| 13 } |
| 14 |
| 15 namespace browser { |
| 16 |
| 17 // static |
| 18 void TitlePrefixMatcher::CalculatePrefixLengths( |
| 19 std::vector<TitleInfo>* title_infos) { |
| 20 DCHECK(title_infos != NULL); |
| 21 // This set will contain the indexes of the TitleInfo objects in the vector |
| 22 // that have a duplicate. |
| 23 base::hash_set<size_t> duplicate_titles; |
| 24 // This map is used to identify duplicates by remembering the vector indexes |
| 25 // we have seen with a given title string. The vector index is set to |
| 26 // kPreviouslySeenIndex once we identified duplicates and placed their |
| 27 // indices in duplicate_titles. |
| 28 base::hash_map<string16, size_t> existing_title; |
| 29 // We identify if there are identical titles upfront, |
| 30 // because we don't want to remove prefixes for those at all. |
| 31 // We do it as a separate pass so that we don't need to remove |
| 32 // previously parsed titles when we find a duplicate title later on. |
| 33 for (size_t i = 0; i < title_infos->size(); ++i) { |
| 34 // We use pairs to test existence and insert in one shot. |
| 35 std::pair<base::hash_map<string16, size_t>::iterator, bool> insert_result = |
| 36 existing_title.insert(std::make_pair(*title_infos->at(i).title, i)); |
| 37 if (!insert_result.second) { |
| 38 // insert_result.second is false when we insert a duplicate in the set. |
| 39 // insert_result.first is a map iterator and thus |
| 40 // insert_result.first->first is the string title key of the map. |
| 41 DCHECK(*title_infos->at(i).title == insert_result.first->first); |
| 42 duplicate_titles.insert(i); |
| 43 // insert_result.first->second is the value of the title index and if it's |
| 44 // not kPreviouslySeenIndex yet, we must remember it as a duplicate too. |
| 45 if (insert_result.first->second != kPreviouslySeenIndex) { |
| 46 duplicate_titles.insert(insert_result.first->second); |
| 47 insert_result.first->second = kPreviouslySeenIndex; |
| 48 } |
| 49 } |
| 50 } |
| 51 |
| 52 // This next loop accumulates all the potential prefixes, |
| 53 // and remember on which titles we saw them. |
| 54 base::hash_map<string16, std::vector<size_t> > prefixes; |
| 55 for (size_t i = 0; i < title_infos->size(); ++i) { |
| 56 // Duplicate titles are not to be included in this process. |
| 57 if (duplicate_titles.find(i) != duplicate_titles.end()) |
| 58 continue; |
| 59 const string16* title = title_infos->at(i).title; |
| 60 // We only create prefixes at word boundaries. |
| 61 base::BreakIterator iter(title, base::BreakIterator::BREAK_WORD); |
| 62 // We ignore this title if we can't break it into words, or if it only |
| 63 // contains a single word. |
| 64 if (!iter.Init() || !iter.Advance()) |
| 65 continue; |
| 66 // We continue advancing even though we already advanced to the first |
| 67 // word above, so that we can use iter.prev() to identify the end of the |
| 68 // previous word and more easily ignore the last word while iterating. |
| 69 while (iter.Advance()) { |
| 70 if (iter.IsWord()) |
| 71 prefixes[title->substr(0, iter.prev())].push_back(i); |
| 72 } |
| 73 } |
| 74 |
| 75 // Now we parse the map to find common prefixes |
| 76 // and keep the largest per title. |
| 77 for (base::hash_map<string16, std::vector<size_t> >::iterator iter = |
| 78 prefixes.begin(); iter != prefixes.end(); ++iter) { |
| 79 // iter->first is the prefix string, iter->second is a vector of indices. |
| 80 if (iter->second.size() > 1) { |
| 81 size_t prefix_length = iter->first.size(); |
| 82 for (size_t i = 0; i < iter->second.size(); ++i){ |
| 83 if (title_infos->at(iter->second[i]).prefix_length < prefix_length) |
| 84 title_infos->at(iter->second[i]).prefix_length = prefix_length; |
| 85 } |
| 86 } |
| 87 } |
| 88 } |
| 89 |
| 90 } // namespace browser |
OLD | NEW |