15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2010 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef CHROME_BROWSER_BOOKMARKS_BOOKMARK_INDEX_H_ 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define CHROME_BROWSER_BOOKMARKS_BOOKMARK_INDEX_H_ 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <map> 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <set> 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector> 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 13868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/strings/string16.h" 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class BookmarkNode; 16868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)struct BookmarkTitleMatch; 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class QueryNode; 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class QueryParser; 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace content { 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class BrowserContext; 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace history { 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class URLDatabase; 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// BookmarkIndex maintains an index of the titles of bookmarks for quick 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// look up. BookmarkIndex is owned and maintained by BookmarkModel, you 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// shouldn't need to interact directly with BookmarkIndex. 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// BookmarkIndex maintains the index (index_) as a map of sets. The map (type 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Index) maps from a lower case string to the set (type NodeSet) of 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// BookmarkNodes that contain that string in their title. 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class BookmarkIndex { 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) explicit BookmarkIndex(content::BrowserContext* browser_context); 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~BookmarkIndex(); 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Invoked when a bookmark has been added to the model. 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Add(const BookmarkNode* node); 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Invoked when a bookmark has been removed from the model. 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Remove(const BookmarkNode* node); 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns up to |max_count| of bookmarks containing the text |query|. 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void GetBookmarksWithTitlesMatching( 48a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) const base::string16& query, 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t max_count, 50868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) std::vector<BookmarkTitleMatch>* results); 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::set<const BookmarkNode*> NodeSet; 54d57369da7c6519fef57db42085f7b42d4c8845c1Torne (Richard Coles) typedef std::map<base::string16, NodeSet> Index; 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct Match; 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<Match> Matches; 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pairs BookmarkNodes and the number of times the nodes' URLs were typed. 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Used to sort Matches in decreasing order of typed count. 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::pair<const BookmarkNode*, int> NodeTypedCountPair; 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<NodeTypedCountPair> NodeTypedCountPairs; 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Extracts |matches.nodes| into NodeTypedCountPairs, sorts the pairs in 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // decreasing order of typed count, and then de-dupes the matches. 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void SortMatches(const Matches& matches, 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodeTypedCountPairs* node_typed_counts) const; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Extracts BookmarkNodes from |match| and retrieves typed counts for each 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // node from the in-memory database. Inserts pairs containing the node and 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // typed count into the vector |node_typed_counts|. |node_typed_counts| is 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // sorted in decreasing order of typed count. 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void ExtractBookmarkNodePairs(history::URLDatabase* url_db, 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Match& match, 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodeTypedCountPairs* node_typed_counts) const; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Sort function for NodeTypedCountPairs. We sort in decreasing order of typed 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // count so that the best matches will always be added to the results. 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static bool NodeTypedCountPairSortFunc(const NodeTypedCountPair& a, 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const NodeTypedCountPair& b) { 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return a.second > b.second; 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Add |node| to |results| if the node matches the query. 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void AddMatchToResults(const BookmarkNode* node, 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QueryParser* parser, 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::vector<QueryNode*>& query_nodes, 88868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) std::vector<BookmarkTitleMatch>* results); 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Populates |matches| for the specified term. If |first_term| is true, this 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // is the first term in the query. Returns true if there is at least one node 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // matching the term. 93a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) bool GetBookmarksWithTitleMatchingTerm(const base::string16& term, 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool first_term, 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Matches* matches); 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Iterates over |matches| updating each Match's nodes to contain the 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // intersection of the Match's current nodes and the nodes at |index_i|. 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the intersection is empty, the Match is removed. 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is invoked from GetBookmarksWithTitleMatchingTerm. 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void CombineMatchesInPlace(const Index::const_iterator& index_i, 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Matches* matches); 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Iterates over |current_matches| calculating the intersection between the 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Match's nodes and the nodes at |index_i|. If the intersection between the 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // two is non-empty, a new match is added to |result|. 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This differs from CombineMatchesInPlace in that if the intersection is 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // non-empty the result is added to result, not combined in place. This 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // variant is used for prefix matching. 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is invoked from GetBookmarksWithTitleMatchingTerm. 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void CombineMatches(const Index::const_iterator& index_i, 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Matches& current_matches, 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Matches* result); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns the set of query words from |query|. 119d57369da7c6519fef57db42085f7b42d4c8845c1Torne (Richard Coles) std::vector<base::string16> ExtractQueryWords(const base::string16& query); 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Adds |node| to |index_|. 122a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) void RegisterNode(const base::string16& term, const BookmarkNode* node); 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Removes |node| from |index_|. 125a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) void UnregisterNode(const base::string16& term, const BookmarkNode* node); 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Index index_; 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) content::BrowserContext* browser_context_; 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(BookmarkIndex); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // CHROME_BROWSER_BOOKMARKS_BOOKMARK_INDEX_H_ 135