cc: Change RTree::Search to return results, add comments, more tests.

cc/base/rtree.h

 // Copyright (c) 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef CC_BASE_RTREE_H_
 #define CC_BASE_RTREE_H_
 
 #include <stddef.h>
 #include <stdint.h>
 
@@ skipping 22 matching lines @@
 // For more details see:
 //
 //  Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990).
 //  "The R*-tree: an efficient and robust access method for points and
 //  rectangles"
 class CC_BASE_EXPORT RTree {
  public:
   RTree();
   ~RTree();
 
+  // Constructs the rtree from a given container of gfx::Rects. Queries using
+  // Search will then return indices into this container.
+  template <typename Container>
+  void Build(const Container& items) {
+    Build(items, [](const gfx::Rect& bounds) { return bounds; });
+  }
+
+  // Build helper that takes a container and a function used to get gfx::Rect
+  // from each item. That is, "bounds_getter(items[i]);" should return a
+  // gfx::Rect representing the bounds of items[i] for each i.
   template <typename Container, typename Functor>
   void Build(const Container& items, const Functor& bounds_getter) {
     DCHECK_EQ(0u, num_data_elements_);
 
     std::vector<Branch> branches;
     branches.reserve(items.size());
 
     for (size_t i = 0; i < items.size(); i++) {
       const gfx::Rect& bounds = bounds_getter(items[i]);
       if (bounds.IsEmpty())
@@ skipping 26 matching lines @@
           kMinChildren;
       nodes_.reserve(node_count);
 
       root_ = BuildRecursive(&branches, 0);
     }
     // We should've wasted at most kMinChildren nodes.
     DCHECK_LE(nodes_.capacity() - nodes_.size(),
               static_cast<size_t>(kMinChildren));
   }
 
-  template <typename Container>
-  void Build(const Container& items) {
-    Build(items, [](const gfx::Rect& bounds) { return bounds; });
-  }
+  // Given a query rect, returns sorted indices of elements that were used to
+  // construct this rtree.
+  std::vector<size_t> Search(const gfx::Rect& query) const;
 
-  void Search(const gfx::Rect& query, std::vector<size_t>* results) const;
-
+  // Returns the total bounds of all items in this rtree.
   gfx::Rect GetBounds() const;
 
  private:
   // These values were empirically determined to produce reasonable performance
   // in most cases.
   enum { kMinChildren = 6 };
   enum { kMaxChildren = 11 };
 
   struct Node;
   struct Branch {
@@ skipping 32 matching lines @@
   size_t num_data_elements_;
   Branch root_;
   std::vector<Node> nodes_;
 
   DISALLOW_COPY_AND_ASSIGN(RTree);
 };
 
 }  // namespace cc
 
 #endif  // CC_BASE_RTREE_H_