bookmark_index.h revision 5821806d5e7f356e8fa4b058a389a808ea183019 
1// Copyright (c) 2010 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#ifndef CHROME_BROWSER_BOOKMARKS_BOOKMARK_INDEX_H_
6#define CHROME_BROWSER_BOOKMARKS_BOOKMARK_INDEX_H_
7
8#include <map>
9#include <set>
10#include <vector>
11
12#include "base/basictypes.h"
13#include "base/string16.h"
14
15class BookmarkNode;
16class Profile;
17class QueryNode;
18class QueryParser;
19
20namespace bookmark_utils {
21struct TitleMatch;
22}
23
24namespace history {
25class URLDatabase;
26}
27
28// BookmarkIndex maintains an index of the titles of bookmarks for quick
29// look up. BookmarkIndex is owned and maintained by BookmarkModel, you
30// shouldn't need to interact directly with BookmarkIndex.
31//
32// BookmarkIndex maintains the index (index_) as a map of sets. The map (type
33// Index) maps from a lower case string to the set (type NodeSet) of
34// BookmarkNodes that contain that string in their title.
35
36class BookmarkIndex {
37 public:
38  explicit BookmarkIndex(Profile* profile);
39  ~BookmarkIndex();
40
41  // Invoked when a bookmark has been added to the model.
42  void Add(const BookmarkNode* node);
43
44  // Invoked when a bookmark has been removed from the model.
45  void Remove(const BookmarkNode* node);
46
47  // Returns up to |max_count| of bookmarks containing the text |query|.
48  void GetBookmarksWithTitlesMatching(
49      const string16& query,
50      size_t max_count,
51      std::vector<bookmark_utils::TitleMatch>* results);
52
53 private:
54  typedef std::set<const BookmarkNode*> NodeSet;
55  typedef std::map<string16, NodeSet> Index;
56
57  struct Match;
58  typedef std::vector<Match> Matches;
59
60  // Pairs BookmarkNodes and the number of times the nodes' URLs were typed.
61  // Used to sort Matches in decreasing order of typed count.
62  typedef std::pair<const BookmarkNode*, int> NodeTypedCountPair;
63  typedef std::vector<NodeTypedCountPair> NodeTypedCountPairs;
64
65  // Extracts |matches.nodes| into NodeTypedCountPairs, sorts the pairs in
66  // decreasing order of typed count, and then de-dupes the matches.
67  void SortMatches(const Matches& matches,
68                   NodeTypedCountPairs* node_typed_counts) const;
69
70  // Extracts BookmarkNodes from |match| and retrieves typed counts for each
71  // node from the in-memory database. Inserts pairs containing the node and
72  // typed count into the vector |node_typed_counts|. |node_typed_counts| is
73  // sorted in decreasing order of typed count.
74  void ExtractBookmarkNodePairs(history::URLDatabase* url_db,
75                                const Match& match,
76                                NodeTypedCountPairs* node_typed_counts) const;
77
78  // Sort function for NodeTypedCountPairs. We sort in decreasing order of typed
79  // count so that the best matches will always be added to the results.
80  static bool NodeTypedCountPairSortFunc(const NodeTypedCountPair& a,
81                                         const NodeTypedCountPair& b) {
82      return a.second > b.second;
83  }
84
85  // Add |node| to |results| if the node matches the query.
86  void AddMatchToResults(const BookmarkNode* node,
87                         QueryParser* parser,
88                         const std::vector<QueryNode*>& query_nodes,
89                         std::vector<bookmark_utils::TitleMatch>* results);
90
91  // Populates |matches| for the specified term. If |first_term| is true, this
92  // is the first term in the query. Returns true if there is at least one node
93  // matching the term.
94  bool GetBookmarksWithTitleMatchingTerm(const string16& term,
95                                         bool first_term,
96                                         Matches* matches);
97
98  // Iterates over |matches| updating each Match's nodes to contain the
99  // intersection of the Match's current nodes and the nodes at |index_i|.
100  // If the intersection is empty, the Match is removed.
101  //
102  // This is invoked from GetBookmarksWithTitleMatchingTerm.
103  void CombineMatchesInPlace(const Index::const_iterator& index_i,
104                             Matches* matches);
105
106  // Iterates over |current_matches| calculating the intersection between the
107  // Match's nodes and the nodes at |index_i|. If the intersection between the
108  // two is non-empty, a new match is added to |result|.
109  //
110  // This differs from CombineMatchesInPlace in that if the intersection is
111  // non-empty the result is added to result, not combined in place. This
112  // variant is used for prefix matching.
113  //
114  // This is invoked from GetBookmarksWithTitleMatchingTerm.
115  void CombineMatches(const Index::const_iterator& index_i,
116                      const Matches& current_matches,
117                      Matches* result);
118
119  // Returns the set of query words from |query|.
120  std::vector<string16> ExtractQueryWords(const string16& query);
121
122  // Adds |node| to |index_|.
123  void RegisterNode(const string16& term, const BookmarkNode* node);
124
125  // Removes |node| from |index_|.
126  void UnregisterNode(const string16& term, const BookmarkNode* node);
127
128  Index index_;
129
130  Profile* profile_;
131
132  DISALLOW_COPY_AND_ASSIGN(BookmarkIndex);
133};
134
135#endif  // CHROME_BROWSER_BOOKMARKS_BOOKMARK_INDEX_H_
136