bookmark_index.h revision c407dc5cd9bdc5668497f21b26b09d988ab439de 
1// Copyright (c) 2009 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 <list>
9#include <map>
10#include <set>
11#include <string>
12#include <vector>
13
14#include "base/basictypes.h"
15
16class BookmarkNode;
17class Profile;
18class QueryNode;
19class QueryParser;
20
21namespace bookmark_utils {
22struct TitleMatch;
23}
24
25namespace history {
26class URLDatabase;
27}
28
29// BookmarkIndex maintains an index of the titles of bookmarks for quick
30// look up. BookmarkIndex is owned and maintained by BookmarkModel, you
31// shouldn't need to interact directly with BookmarkIndex.
32//
33// BookmarkIndex maintains the index (index_) as a map of sets. The map (type
34// Index) maps from a lower case string to the set (type NodeSet) of
35// BookmarkNodes that contain that string in their title.
36
37class BookmarkIndex {
38 public:
39  explicit BookmarkIndex(Profile* profile) : profile_(profile) {}
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 std::wstring& 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<std::wstring, NodeSet> Index;
56
57  // Used when finding the set of bookmarks that match a query. Each match
58  // represents a set of terms (as an interator into the Index) matching the
59  // query as well as the set of nodes that contain those terms in their titles.
60  struct Match {
61    // List of terms matching the query.
62    std::list<Index::const_iterator> terms;
63
64    // The set of nodes matching the terms. As an optimization this is empty
65    // when we match only one term, and is filled in when we get more than one
66    // term. We can do this as when we have only one matching term we know
67    // the set of matching nodes is terms.front()->second.
68    //
69    // Use nodes_begin() and nodes_end() to get an iterator over the set as
70    // it handles the necessary switching between nodes and terms.front().
71    NodeSet nodes;
72
73    // Returns an iterator to the beginning of the matching nodes. See
74    // description of nodes for why this should be used over nodes.begin().
75    NodeSet::const_iterator nodes_begin() const;
76
77    // Returns an iterator to the beginning of the matching nodes. See
78    // description of nodes for why this should be used over nodes.end().
79    NodeSet::const_iterator nodes_end() const;
80  };
81
82  typedef std::vector<Match> Matches;
83
84  // Pairs BookmarkNodes and the number of times the nodes' URLs were typed.
85  // Used to sort Matches in decreasing order of typed count.
86  typedef std::pair<const BookmarkNode*, int> NodeTypedCountPair;
87  typedef std::vector<NodeTypedCountPair> NodeTypedCountPairs;
88
89  // Extracts |matches.nodes| into NodeTypedCountPairs and sorts the pairs in
90  // decreasing order of typed count.
91  void SortMatches(const Matches& matches,
92                   NodeTypedCountPairs* node_typed_counts) const;
93
94  // Extracts BookmarkNodes from |match| and retrieves typed counts for each
95  // node from the in-memory database. Inserts pairs containing the node and
96  // typed count into the vector |node_typed_counts|. |node_typed_counts| is
97  // sorted in decreasing order of typed count.
98  void ExtractBookmarkNodePairs(history::URLDatabase* url_db,
99                                const Match& match,
100                                NodeTypedCountPairs* node_typed_counts) const;
101
102  // Sort function for NodeTypedCountPairs. We sort in decreasing order of typed
103  // count so that the best matches will always be added to the results.
104  static bool NodeTypedCountPairSortFunc(const NodeTypedCountPair& a,
105                                         const NodeTypedCountPair& b) {
106      return a.second > b.second;
107  }
108
109  // Add |node| to |results| if the node matches the query.
110  void AddMatchToResults(const BookmarkNode* node,
111                         QueryParser* parser,
112                         const std::vector<QueryNode*>& query_nodes,
113                         std::vector<bookmark_utils::TitleMatch>* results);
114
115  // Populates |matches| for the specified term. If |first_term| is true, this
116  // is the first term in the query. Returns true if there is at least one node
117  // matching the term.
118  bool GetBookmarksWithTitleMatchingTerm(const std::wstring& term,
119                                         bool first_term,
120                                         Matches* matches);
121
122  // Iterates over |matches| updating each Match's nodes to contain the
123  // intersection of the Match's current nodes and the nodes at |index_i|.
124  // If the intersection is empty, the Match is removed.
125  //
126  // This is invoked from GetBookmarksWithTitleMatchingTerm.
127  void CombineMatchesInPlace(const Index::const_iterator& index_i,
128                             Matches* matches);
129
130  // Iterates over |current_matches| calculating the intersection between the
131  // Match's nodes and the nodes at |index_i|. If the intersection between the
132  // two is non-empty, a new match is added to |result|.
133  //
134  // This differs from CombineMatchesInPlace in that if the intersection is
135  // non-empty the result is added to result, not combined in place. This
136  // variant is used for prefix matching.
137  //
138  // This is invoked from GetBookmarksWithTitleMatchingTerm.
139  void CombineMatches(const Index::const_iterator& index_i,
140                      const Matches& current_matches,
141                      Matches* result);
142
143  // Returns the set of query words from |query|.
144  std::vector<std::wstring> ExtractQueryWords(const std::wstring& query);
145
146  // Adds |node| to |index_|.
147  void RegisterNode(const std::wstring& term, const BookmarkNode* node);
148
149  // Removes |node| from |index_|.
150  void UnregisterNode(const std::wstring& term, const BookmarkNode* node);
151
152  Index index_;
153
154  Profile* profile_;
155
156  DISALLOW_COPY_AND_ASSIGN(BookmarkIndex);
157};
158
159#endif  // CHROME_BROWSER_BOOKMARKS_BOOKMARK_INDEX_H_
160