1// Copyright 2014 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 COMPONENTS_BOOKMARKS_BROWSER_BOOKMARK_INDEX_H_
6#define COMPONENTS_BOOKMARKS_BROWSER_BOOKMARK_INDEX_H_
7
8#include <map>
9#include <set>
10#include <string>
11#include <vector>
12
13#include "base/basictypes.h"
14#include "base/strings/string16.h"
15#include "components/query_parser/query_parser.h"
16
17class BookmarkNode;
18
19namespace bookmarks {
20
21class BookmarkClient;
22struct BookmarkMatch;
23
24// BookmarkIndex maintains an index of the titles and URLs of bookmarks for
25// quick look up. BookmarkIndex is owned and maintained by BookmarkModel, you
26// shouldn't need to interact directly with BookmarkIndex.
27//
28// BookmarkIndex maintains the index (index_) as a map of sets. The map (type
29// Index) maps from a lower case string to the set (type NodeSet) of
30// BookmarkNodes that contain that string in their title or URL.
31class BookmarkIndex {
32 public:
33  // |languages| is used to help parse IDNs in URLs for the bookmark index.
34  BookmarkIndex(BookmarkClient* client,
35                const std::string& languages);
36  ~BookmarkIndex();
37
38  // Invoked when a bookmark has been added to the model.
39  void Add(const BookmarkNode* node);
40
41  // Invoked when a bookmark has been removed from the model.
42  void Remove(const BookmarkNode* node);
43
44  // Returns up to |max_count| of bookmarks containing each term from
45  // the text |query| in either the title or the URL.
46  void GetBookmarksMatching(
47      const base::string16& query,
48      size_t max_count,
49      std::vector<BookmarkMatch>* results);
50
51 private:
52  typedef std::vector<const BookmarkNode*> Nodes;
53  typedef std::set<const BookmarkNode*> NodeSet;
54  typedef std::map<base::string16, NodeSet> Index;
55
56  struct Match;
57  typedef std::vector<Match> Matches;
58
59  // Extracts |matches.nodes| into Nodes, sorts the pairs in decreasing order of
60  // typed count (if supported by the client), and then de-dupes the matches.
61  void SortMatches(const Matches& matches, Nodes* sorted_nodes) const;
62
63  // Add |node| to |results| if the node matches the query.
64  void AddMatchToResults(
65      const BookmarkNode* node,
66      query_parser::QueryParser* parser,
67      const query_parser::QueryNodeStarVector& query_nodes,
68      std::vector<BookmarkMatch>* results);
69
70  // Populates |matches| for the specified term. If |first_term| is true, this
71  // is the first term in the query. Returns true if there is at least one node
72  // matching the term.
73  bool GetBookmarksMatchingTerm(const base::string16& term,
74                                bool first_term,
75                                Matches* matches);
76
77  // Iterates over |matches| updating each Match's nodes to contain the
78  // intersection of the Match's current nodes and the nodes at |index_i|.
79  // If the intersection is empty, the Match is removed.
80  //
81  // This is invoked from GetBookmarksMatchingTerm.
82  void CombineMatchesInPlace(const Index::const_iterator& index_i,
83                             Matches* matches);
84
85  // Iterates over |current_matches| calculating the intersection between the
86  // Match's nodes and the nodes at |index_i|. If the intersection between the
87  // two is non-empty, a new match is added to |result|.
88  //
89  // This differs from CombineMatchesInPlace in that if the intersection is
90  // non-empty the result is added to result, not combined in place. This
91  // variant is used for prefix matching.
92  //
93  // This is invoked from GetBookmarksMatchingTerm.
94  void CombineMatches(const Index::const_iterator& index_i,
95                      const Matches& current_matches,
96                      Matches* result);
97
98  // Returns the set of query words from |query|.
99  std::vector<base::string16> ExtractQueryWords(const base::string16& query);
100
101  // Adds |node| to |index_|.
102  void RegisterNode(const base::string16& term, const BookmarkNode* node);
103
104  // Removes |node| from |index_|.
105  void UnregisterNode(const base::string16& term, const BookmarkNode* node);
106
107  Index index_;
108
109  BookmarkClient* const client_;
110
111  // Languages used to help parse IDNs in URLs for the bookmark index.
112  const std::string languages_;
113
114  DISALLOW_COPY_AND_ASSIGN(BookmarkIndex);
115};
116
117}  // namespace bookmarks
118
119#endif  // COMPONENTS_BOOKMARKS_BROWSER_BOOKMARK_INDEX_H_
120