chrome/browser/bookmarks/bookmark_index.h

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