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#pragma once
8
9#include <map>
10#include <set>
11#include <vector>
12
13#include "base/basictypes.h"
14#include "base/string16.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);
40  ~BookmarkIndex();
41
42  // Invoked when a bookmark has been added to the model.
43  void Add(const BookmarkNode* node);
44
45  // Invoked when a bookmark has been removed from the model.
46  void Remove(const BookmarkNode* node);
47
48  // Returns up to |max_count| of bookmarks containing the text |query|.
49  void GetBookmarksWithTitlesMatching(
50      const string16& query,
51      size_t max_count,
52      std::vector<bookmark_utils::TitleMatch>* results);
53
54 private:
55  typedef std::set<const BookmarkNode*> NodeSet;
56  typedef std::map<string16, NodeSet> Index;
57
58  struct Match;
59  typedef std::vector<Match> Matches;
60
61  // Pairs BookmarkNodes and the number of times the nodes' URLs were typed.
62  // Used to sort Matches in decreasing order of typed count.
63  typedef std::pair<const BookmarkNode*, int> NodeTypedCountPair;
64  typedef std::vector<NodeTypedCountPair> NodeTypedCountPairs;
65
66  // Extracts |matches.nodes| into NodeTypedCountPairs and sorts the pairs in
67  // decreasing order of typed count.
68  void SortMatches(const Matches& matches,
69                   NodeTypedCountPairs* node_typed_counts) const;
70
71  // Extracts BookmarkNodes from |match| and retrieves typed counts for each
72  // node from the in-memory database. Inserts pairs containing the node and
73  // typed count into the vector |node_typed_counts|. |node_typed_counts| is
74  // sorted in decreasing order of typed count.
75  void ExtractBookmarkNodePairs(history::URLDatabase* url_db,
76                                const Match& match,
77                                NodeTypedCountPairs* node_typed_counts) const;
78
79  // Sort function for NodeTypedCountPairs. We sort in decreasing order of typed
80  // count so that the best matches will always be added to the results.
81  static bool NodeTypedCountPairSortFunc(const NodeTypedCountPair& a,
82                                         const NodeTypedCountPair& b) {
83      return a.second > b.second;
84  }
85
86  // Add |node| to |results| if the node matches the query.
87  void AddMatchToResults(const BookmarkNode* node,
88                         QueryParser* parser,
89                         const std::vector<QueryNode*>& query_nodes,
90                         std::vector<bookmark_utils::TitleMatch>* results);
91
92  // Populates |matches| for the specified term. If |first_term| is true, this
93  // is the first term in the query. Returns true if there is at least one node
94  // matching the term.
95  bool GetBookmarksWithTitleMatchingTerm(const string16& term,
96                                         bool first_term,
97                                         Matches* matches);
98
99  // Iterates over |matches| updating each Match's nodes to contain the
100  // intersection of the Match's current nodes and the nodes at |index_i|.
101  // If the intersection is empty, the Match is removed.
102  //
103  // This is invoked from GetBookmarksWithTitleMatchingTerm.
104  void CombineMatchesInPlace(const Index::const_iterator& index_i,
105                             Matches* matches);
106
107  // Iterates over |current_matches| calculating the intersection between the
108  // Match's nodes and the nodes at |index_i|. If the intersection between the
109  // two is non-empty, a new match is added to |result|.
110  //
111  // This differs from CombineMatchesInPlace in that if the intersection is
112  // non-empty the result is added to result, not combined in place. This
113  // variant is used for prefix matching.
114  //
115  // This is invoked from GetBookmarksWithTitleMatchingTerm.
116  void CombineMatches(const Index::const_iterator& index_i,
117                      const Matches& current_matches,
118                      Matches* result);
119
120  // Returns the set of query words from |query|.
121  std::vector<string16> ExtractQueryWords(const string16& query);
122
123  // Adds |node| to |index_|.
124  void RegisterNode(const string16& term, const BookmarkNode* node);
125
126  // Removes |node| from |index_|.
127  void UnregisterNode(const string16& term, const BookmarkNode* node);
128
129  Index index_;
130
131  Profile* profile_;
132
133  DISALLOW_COPY_AND_ASSIGN(BookmarkIndex);
134};
135
136#endif  // CHROME_BROWSER_BOOKMARKS_BOOKMARK_INDEX_H_
137