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