Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(313)

Side by Side Diff: cc/base/rtree.h

Issue 2748263002: Move cc::DisplayItemList and related classes into cc/paint/ (Closed)
Patch Set: Merge branch 'master' into ccpaint Created 3 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « cc/base/rolling_time_delta_history.h ('k') | cc/base/simple_enclosed_region.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright (c) 2015 The Chromium Authors. All rights reserved. 1 // Copyright (c) 2015 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #ifndef CC_BASE_RTREE_H_ 5 #ifndef CC_BASE_RTREE_H_
6 #define CC_BASE_RTREE_H_ 6 #define CC_BASE_RTREE_H_
7 7
8 #include <stddef.h> 8 #include <stddef.h>
9 #include <stdint.h> 9 #include <stdint.h>
10 10
11 #include <vector> 11 #include <vector>
12 12
13 #include "cc/base/cc_export.h" 13 #include "cc/base/base_export.h"
14 #include "ui/gfx/geometry/rect.h" 14 #include "ui/gfx/geometry/rect.h"
15 15
16 namespace cc { 16 namespace cc {
17 17
18 // The following description and most of the implementation is borrowed from 18 // The following description and most of the implementation is borrowed from
19 // Skia's SkRTree implementation. 19 // Skia's SkRTree implementation.
20 // 20 //
21 // An R-Tree implementation. In short, it is a balanced n-ary tree containing a 21 // An R-Tree implementation. In short, it is a balanced n-ary tree containing a
22 // hierarchy of bounding rectangles. 22 // hierarchy of bounding rectangles.
23 // 23 //
24 // It only supports bulk-loading, i.e. creation from a batch of bounding 24 // It only supports bulk-loading, i.e. creation from a batch of bounding
25 // rectangles. This performs a bottom-up bulk load using the STR 25 // rectangles. This performs a bottom-up bulk load using the STR
26 // (sort-tile-recursive) algorithm. 26 // (sort-tile-recursive) algorithm.
27 // 27 //
28 // Things to do: Experiment with other bulk-load algorithms (in particular the 28 // Things to do: Experiment with other bulk-load algorithms (in particular the
29 // Hilbert pack variant, which groups rects by position on the Hilbert curve, is 29 // Hilbert pack variant, which groups rects by position on the Hilbert curve, is
30 // probably worth a look). There also exist top-down bulk load variants 30 // probably worth a look). There also exist top-down bulk load variants
31 // (VAMSplit, TopDownGreedy, etc). 31 // (VAMSplit, TopDownGreedy, etc).
32 // 32 //
33 // For more details see: 33 // For more details see:
34 // 34 //
35 // Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). 35 // Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990).
36 // "The R*-tree: an efficient and robust access method for points and 36 // "The R*-tree: an efficient and robust access method for points and
37 // rectangles" 37 // rectangles"
38 class CC_EXPORT RTree { 38 class CC_BASE_EXPORT RTree {
39 public: 39 public:
40 RTree(); 40 RTree();
41 ~RTree(); 41 ~RTree();
42 42
43 template <typename Container, typename Functor> 43 template <typename Container, typename Functor>
44 void Build(const Container& items, const Functor& bounds_getter) { 44 void Build(const Container& items, const Functor& bounds_getter) {
45 DCHECK_EQ(0u, num_data_elements_); 45 DCHECK_EQ(0u, num_data_elements_);
46 46
47 std::vector<Branch> branches; 47 std::vector<Branch> branches;
48 branches.reserve(items.size()); 48 branches.reserve(items.size());
(...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after
128 std::vector<size_t>* results) const; 128 std::vector<size_t>* results) const;
129 129
130 // Consumes the input array. 130 // Consumes the input array.
131 Branch BuildRecursive(std::vector<Branch>* branches, int level); 131 Branch BuildRecursive(std::vector<Branch>* branches, int level);
132 Node* AllocateNodeAtLevel(int level); 132 Node* AllocateNodeAtLevel(int level);
133 133
134 // This is the count of data elements (rather than total nodes in the tree) 134 // This is the count of data elements (rather than total nodes in the tree)
135 size_t num_data_elements_; 135 size_t num_data_elements_;
136 Branch root_; 136 Branch root_;
137 std::vector<Node> nodes_; 137 std::vector<Node> nodes_;
138
139 DISALLOW_COPY_AND_ASSIGN(RTree);
138 }; 140 };
139 141
140 } // namespace cc 142 } // namespace cc
141 143
142 #endif // CC_BASE_RTREE_H_ 144 #endif // CC_BASE_RTREE_H_
OLDNEW
« no previous file with comments | « cc/base/rolling_time_delta_history.h ('k') | cc/base/simple_enclosed_region.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698