Add R-Tree data structure.

Add R-Tree data structure.
Committed: https://code.google.com/p/skia/source/detail?r=5401

[rileya, 2012-08-29 21:13:03]

Sorry about the gigantic CL, but I don't think this can really be broken up too
well...

This doesn't include anything specific to the Picture stuff, this is just the
R-Tree.

[bsalomon, 2012-08-29 21:25:09]

On 2012/08/29 21:13:03, rileya wrote:
> Sorry about the gigantic CL, but I don't think this can really be broken up
too
> well...
> 
> This doesn't include anything specific to the Picture stuff, this is just the
> R-Tree.

I'm not sure this CL adds enough code. So should we also add a bench that throws
random rects at the tree? I can imagine we might even want multiple benches that
exercise extreme cases:

1. every rect is a subrect of or encloses the previous
2. all rects are tiny/large relative to the overall bounds
3. ...

Maybe not all/any of these would be hard cases for the current implementation
but it would give us some way of measuring trade-offs for alternate
tree-building algs.

[reed1, 2012-08-30 11:58:57]

does every stitch of code need to be templated? that's a lot of duplication if
we ever use this in more than on place.

[robertphillips, 2012-08-30 13:25:34]

LGTM + questions & comment suggestions

http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h
File src/core/SkRTree.h (right):

http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode197
src/core/SkRTree.h:197: 
Comment? // Recursively descend the tree to find the final resting spot of
'branch'. Update the bounding boxes on the way up.

http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode245
src/core/SkRTree.h:245: // root's child pointers do not point to leaves, so
minimize area increase
Don't we have these defined somewhere?

http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode273
src/core/SkRTree.h:273: if (j == i) continue;
expand on the "old overlap?" comment?

http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode314
src/core/SkRTree.h:314: // We want choose an axis to split on, then a
distribution along that axis; we'll need
want _to_

http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode495
src/core/SkRTree.h:495: 
Add check that node bounding box includes all children?

http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode532
src/core/SkRTree.h:532: 
comment here?

http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode547
src/core/SkRTree.h:547: 
// expand 'out' to include 'joinWith'

http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode550
src/core/SkRTree.h:550: // and we can save the empty check that SkIRect::join
requires
Add {}s

http://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp
File tests/RTreeTest.cpp (right):

http://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode81
tests/RTreeTest.cpp:81: 
test getCount in here? getDepth?

[bsalomon, 2012-08-30 13:48:04]

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h
File src/core/SkRTree.h (right):

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode17
src/core/SkRTree.h:17: static inline uint32_t getArea(const SkIRect& rect);
i_find_it_easier_to_read_file_local_non_member_functions_named_like_this_because_it_makes_it_more_obvious_that_they_arent_just_missing_a_this_arrow();

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode242
src/core/SkRTree.h:242: int chooseSubtree(Node* root, Branch* branch) {
I don't think it is necessary for this change, but we could consider making this
an installable function pointer to play with different metrics (and compare
trees w/out recompiling).

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode245
src/core/SkRTree.h:245: // root's child pointers do not point to leaves, so
minimize area increase
On 2012/08/30 13:25:34, robertphillips wrote:
> Don't we have these defined somewhere?

We could retype them as int32_t and use INT32_MAX

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode388
src/core/SkRTree.h:388: static bool rectLessX(int&, const Branch lhs, const
Branch rhs) {
Do these need to be part of the class at all? Also static members
AreNamedWithAnInitialCap()

[robertphillips, 2012-08-30 13:53:03]

https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp
File tests/RTreeTest.cpp (right):

https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode57
tests/RTreeTest.cpp:57: return false;
I think this might be clearer w/o the else. The test is then clearly a skip of
the array comparison.

[rileya, 2012-08-30 14:42:28]

@Mike on templating: As we discussed, I can change the T to a void*, T really
shouldn't be bigger than a pointer anyways and that would get rid of some
templating. Min/max children are convenient as template params, since we can
have fixed size arrays in the nodes.

@Brian On benches: I have bench tests that I can add as a new CL, though I'm
finding that there are a huge number of variables, and I'm ending up with tons
of variations (testing tree construction and query performance, bulk-loaded vs
immediate insertions, for 4 or 5 different types of rectangle distributions,
with several different types of queries, etc, all the permutations end up being
a ton of tests...).

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h
File src/core/SkRTree.h (right):

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode17
src/core/SkRTree.h:17: static inline uint32_t getArea(const SkIRect& rect);
On 2012/08/30 13:48:04, bsalomon wrote:
>
i_find_it_easier_to_read_file_local_non_member_functions_named_like_this_because_it_makes_it_more_obvious_that_they_arent_just_missing_a_this_arrow();

Fixed.

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode197
src/core/SkRTree.h:197: 
On 2012/08/30 13:25:34, robertphillips wrote:
> Comment? // Recursively descend the tree to find the final resting spot of
> 'branch'. Update the bounding boxes on the way up.

Added.

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode245
src/core/SkRTree.h:245: // root's child pointers do not point to leaves, so
minimize area increase
On 2012/08/30 13:48:04, bsalomon wrote:
> On 2012/08/30 13:25:34, robertphillips wrote:
> > Don't we have these defined somewhere?
> 
> We could retype them as int32_t and use INT32_MAX

I may have been a little too aggressive with the int->int32_t replaces, but
done.

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode273
src/core/SkRTree.h:273: if (j == i) continue;
On 2012/08/30 13:25:34, robertphillips wrote:
> expand on the "old overlap?" comment?

Done.

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode314
src/core/SkRTree.h:314: // We want choose an axis to split on, then a
distribution along that axis; we'll need
On 2012/08/30 13:25:34, robertphillips wrote:
> want _to_

Fixed.

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode388
src/core/SkRTree.h:388: static bool rectLessX(int&, const Branch lhs, const
Branch rhs) {
On 2012/08/30 13:48:04, bsalomon wrote:
> Do these need to be part of the class at all? Also static members
> AreNamedWithAnInitialCap()

Because it takes Branches as params, which are inner structs of the RTree, it
avoids some ugly template soup in the function headers. But I can change it if
that is preferable.

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode495
src/core/SkRTree.h:495: 
On 2012/08/30 13:25:34, robertphillips wrote:
> Add check that node bounding box includes all children?

Good call, added.

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode532
src/core/SkRTree.h:532: 
On 2012/08/30 13:25:34, robertphillips wrote:
> comment here?

Added.

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode547
src/core/SkRTree.h:547: 
On 2012/08/30 13:25:34, robertphillips wrote:
> // expand 'out' to include 'joinWith'

Added.

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode550
src/core/SkRTree.h:550: // and we can save the empty check that SkIRect::join
requires
On 2012/08/30 13:25:34, robertphillips wrote:
> Add {}s

Done.

https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp
File tests/RTreeTest.cpp (right):

https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode57
tests/RTreeTest.cpp:57: return false;
On 2012/08/30 13:53:03, robertphillips wrote:
> I think this might be clearer w/o the else. The test is then clearly a skip of
> the array comparison.

Done.

https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode81
tests/RTreeTest.cpp:81: 
On 2012/08/30 13:25:34, robertphillips wrote:
> test getCount in here? getDepth?

Since the tree depth is variable depending on the rects/order of insertion/etc I
don't see a way of checking that, but I added a check for count.

[bsalomon, 2012-08-30 14:54:13]

On 2012/08/30 14:42:28, rileya wrote:
> @Mike on templating: As we discussed, I can change the T to a void*, T really
> shouldn't be bigger than a pointer anyways and that would get rid of some
> templating. Min/max children are convenient as template params, since we can
> have fixed size arrays in the nodes.

pseudo-C:

struct Node {
  bool isLeaf() { return 0 == fLevel; }
  bool isFull() { return fNumChildren == MAX_CHILDREN; }

  uint16_t fNumChildren;
  uint16_t fLevel;
  Branch* child(int i) {
    STATIC_ASSERT(this = 2 * sizeof(uint16_t);
    return (Branch*)((char*)this + 2 * sizeof(uint16_t) + i * sizeof(Branch));
  }
};

size_t NodeSize = sizeof(Node + fMaxBranch * sizeof(Branch));
Node* newNode = (Node*) chunky_malloc_allocate(NodeSize);


> 
> @Brian On benches: I have bench tests that I can add as a new CL, though I'm
> finding that there are a huge number of variables, and I'm ending up with tons
> of variations (testing tree construction and query performance, bulk-loaded vs
> immediate insertions, for 4 or 5 different types of rectangle distributions,
> with several different types of queries, etc, all the permutations end up
being
> a ton of tests...).

Maybe just stick with one rectangle distro for now? Agree on adding as a
separate CL.

> 
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h
> File src/core/SkRTree.h (right):
> 
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode17
> src/core/SkRTree.h:17: static inline uint32_t getArea(const SkIRect& rect);
> On 2012/08/30 13:48:04, bsalomon wrote:
> >
>
i_find_it_easier_to_read_file_local_non_member_functions_named_like_this_because_it_makes_it_more_obvious_that_they_arent_just_missing_a_this_arrow();
> 
> Fixed.
> 
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode197
> src/core/SkRTree.h:197: 
> On 2012/08/30 13:25:34, robertphillips wrote:
> > Comment? // Recursively descend the tree to find the final resting spot of
> > 'branch'. Update the bounding boxes on the way up.
> 
> Added.
> 
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode245
> src/core/SkRTree.h:245: // root's child pointers do not point to leaves, so
> minimize area increase
> On 2012/08/30 13:48:04, bsalomon wrote:
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > Don't we have these defined somewhere?
> > 
> > We could retype them as int32_t and use INT32_MAX
> 
> I may have been a little too aggressive with the int->int32_t replaces, but
> done.
> 
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode273
> src/core/SkRTree.h:273: if (j == i) continue;
> On 2012/08/30 13:25:34, robertphillips wrote:
> > expand on the "old overlap?" comment?
> 
> Done.
> 
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode314
> src/core/SkRTree.h:314: // We want choose an axis to split on, then a
> distribution along that axis; we'll need
> On 2012/08/30 13:25:34, robertphillips wrote:
> > want _to_
> 
> Fixed.
> 
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode388
> src/core/SkRTree.h:388: static bool rectLessX(int&, const Branch lhs, const
> Branch rhs) {
> On 2012/08/30 13:48:04, bsalomon wrote:
> > Do these need to be part of the class at all? Also static members
> > AreNamedWithAnInitialCap()
> 
> Because it takes Branches as params, which are inner structs of the RTree, it
> avoids some ugly template soup in the function headers. But I can change it if
> that is preferable.
> 
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode495
> src/core/SkRTree.h:495: 
> On 2012/08/30 13:25:34, robertphillips wrote:
> > Add check that node bounding box includes all children?
> 
> Good call, added.
> 
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode532
> src/core/SkRTree.h:532: 
> On 2012/08/30 13:25:34, robertphillips wrote:
> > comment here?
> 
> Added.
> 
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode547
> src/core/SkRTree.h:547: 
> On 2012/08/30 13:25:34, robertphillips wrote:
> > // expand 'out' to include 'joinWith'
> 
> Added.
> 
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode550
> src/core/SkRTree.h:550: // and we can save the empty check that SkIRect::join
> requires
> On 2012/08/30 13:25:34, robertphillips wrote:
> > Add {}s
> 
> Done.
> 
> https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp
> File tests/RTreeTest.cpp (right):
> 
> https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode57
> tests/RTreeTest.cpp:57: return false;
> On 2012/08/30 13:53:03, robertphillips wrote:
> > I think this might be clearer w/o the else. The test is then clearly a skip
of
> > the array comparison.
> 
> Done.
> 
> https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode81
> tests/RTreeTest.cpp:81: 
> On 2012/08/30 13:25:34, robertphillips wrote:
> > test getCount in here? getDepth?
> 
> Since the tree depth is variable depending on the rects/order of insertion/etc
I
> don't see a way of checking that, but I added a check for count.

[bsalomon, 2012-08-30 14:57:10]

On 2012/08/30 14:54:13, bsalomon wrote:
> On 2012/08/30 14:42:28, rileya wrote:
> > @Mike on templating: As we discussed, I can change the T to a void*, T
really
> > shouldn't be bigger than a pointer anyways and that would get rid of some
> > templating. Min/max children are convenient as template params, since we can
> > have fixed size arrays in the nodes.
> 
> pseudo-C:
> 
> struct Node {
>   bool isLeaf() { return 0 == fLevel; }
>   bool isFull() { return fNumChildren == MAX_CHILDREN; }
> 
>   uint16_t fNumChildren;
>   uint16_t fLevel;
>   Branch* child(int i) {
>     STATIC_ASSERT(this = 2 * sizeof(uint16_t);
>     return (Branch*)((char*)this + 2 * sizeof(uint16_t) + i * sizeof(Branch));

remove static assert, 2 * sizeof(uint16_t) -> sizeof(Node)

>   }
> };
> 
> size_t NodeSize = sizeof(Node + fMaxBranch * sizeof(Branch));
> Node* newNode = (Node*) chunky_malloc_allocate(NodeSize);
> 
> 
> > 
> > @Brian On benches: I have bench tests that I can add as a new CL, though I'm
> > finding that there are a huge number of variables, and I'm ending up with
tons
> > of variations (testing tree construction and query performance, bulk-loaded
vs
> > immediate insertions, for 4 or 5 different types of rectangle distributions,
> > with several different types of queries, etc, all the permutations end up
> being
> > a ton of tests...).
> 
> Maybe just stick with one rectangle distro for now? Agree on adding as a
> separate CL.
> 
> > 
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h
> > File src/core/SkRTree.h (right):
> > 
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode17
> > src/core/SkRTree.h:17: static inline uint32_t getArea(const SkIRect& rect);
> > On 2012/08/30 13:48:04, bsalomon wrote:
> > >
> >
>
i_find_it_easier_to_read_file_local_non_member_functions_named_like_this_because_it_makes_it_more_obvious_that_they_arent_just_missing_a_this_arrow();
> > 
> > Fixed.
> > 
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode197
> > src/core/SkRTree.h:197: 
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > Comment? // Recursively descend the tree to find the final resting spot of
> > > 'branch'. Update the bounding boxes on the way up.
> > 
> > Added.
> > 
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode245
> > src/core/SkRTree.h:245: // root's child pointers do not point to leaves, so
> > minimize area increase
> > On 2012/08/30 13:48:04, bsalomon wrote:
> > > On 2012/08/30 13:25:34, robertphillips wrote:
> > > > Don't we have these defined somewhere?
> > > 
> > > We could retype them as int32_t and use INT32_MAX
> > 
> > I may have been a little too aggressive with the int->int32_t replaces, but
> > done.
> > 
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode273
> > src/core/SkRTree.h:273: if (j == i) continue;
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > expand on the "old overlap?" comment?
> > 
> > Done.
> > 
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode314
> > src/core/SkRTree.h:314: // We want choose an axis to split on, then a
> > distribution along that axis; we'll need
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > want _to_
> > 
> > Fixed.
> > 
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode388
> > src/core/SkRTree.h:388: static bool rectLessX(int&, const Branch lhs, const
> > Branch rhs) {
> > On 2012/08/30 13:48:04, bsalomon wrote:
> > > Do these need to be part of the class at all? Also static members
> > > AreNamedWithAnInitialCap()
> > 
> > Because it takes Branches as params, which are inner structs of the RTree,
it
> > avoids some ugly template soup in the function headers. But I can change it
if
> > that is preferable.
> > 
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode495
> > src/core/SkRTree.h:495: 
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > Add check that node bounding box includes all children?
> > 
> > Good call, added.
> > 
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode532
> > src/core/SkRTree.h:532: 
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > comment here?
> > 
> > Added.
> > 
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode547
> > src/core/SkRTree.h:547: 
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > // expand 'out' to include 'joinWith'
> > 
> > Added.
> > 
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode550
> > src/core/SkRTree.h:550: // and we can save the empty check that
SkIRect::join
> > requires
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > Add {}s
> > 
> > Done.
> > 
> > https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp
> > File tests/RTreeTest.cpp (right):
> > 
> > https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode57
> > tests/RTreeTest.cpp:57: return false;
> > On 2012/08/30 13:53:03, robertphillips wrote:
> > > I think this might be clearer w/o the else. The test is then clearly a
skip
> of
> > > the array comparison.
> > 
> > Done.
> > 
> > https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode81
> > tests/RTreeTest.cpp:81: 
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > test getCount in here? getDepth?
> > 
> > Since the tree depth is variable depending on the rects/order of
insertion/etc
> I
> > don't see a way of checking that, but I added a check for count.

[bsalomon, 2012-08-30 14:58:07]

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h
File src/core/SkRTree.h (right):

https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode388
src/core/SkRTree.h:388: static bool rectLessX(int&, const Branch lhs, const
Branch rhs) {
On 2012/08/30 14:42:28, rileya wrote:
> On 2012/08/30 13:48:04, bsalomon wrote:
> > Do these need to be part of the class at all? Also static members
> > AreNamedWithAnInitialCap()
> 
> Because it takes Branches as params, which are inner structs of the RTree, it
> avoids some ugly template soup in the function headers. But I can change it if
> that is preferable.

Duh, right.

[rileya, 2012-08-30 21:40:56]

Un-templated it, and moved implementation to a source file.

[reed1, 2012-08-31 12:00:02]

I like much better now.

1. Can we see how this class gets used for (a) recording and (b) playback? Maybe
post other CLs just for reference?

2. How much can be done to fission the API into a recording part and a playback
part? i.e. how simple can we make the API look to just the recording-canvas?

3. If we wanted to experiment with different recording techniques, would we want
a common baseclass for this guy, or different recording classes but a common
playback class?

https://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h
File src/core/SkRTree.h (right):

https://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h#newcode44
src/core/SkRTree.h:44: 
nit: parameters should almost never be smaller than an int.

Also, is it useful for both values to have defaults? I can say

new SkRTree(20);

Which would be wacky, since 20 > 15.

Default args are great, and they're terrible. Maybe

SkRTree();
SkRTree(int min, int max);
?

[bsalomon, 2012-08-31 15:51:57]

https://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h
File src/core/SkRTree.h (right):

https://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h#newcode71
src/core/SkRTree.h:71: int getCount() const { return fCount; }
Maybe a comment about whether this is a count of nodes or insertions

https://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h#newcode98
src/core/SkRTree.h:98: return
reinterpret_cast<Branch*>(reinterpret_cast<char*>(this) + sizeof(Node)
Could be shortened to:

return reinterpret_cast<Branch*>(this + 1) + index;

[rileya, 2012-09-04 16:20:10]

Addressed a few more things, also added a base class for this (naming could
probably be better: SkBBoxHierarchy), which should help with plugging in and
testing alternate spatial data structures.

[rileya, 2012-09-04 16:20:20]

http://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h
File src/core/SkRTree.h (right):

http://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h#newcode44
src/core/SkRTree.h:44: 
On 2012/08/31 12:00:02, reed1 wrote:
> nit: parameters should almost never be smaller than an int.
> 
> Also, is it useful for both values to have defaults? I can say
> 
> new SkRTree(20);
> 
> Which would be wacky, since 20 > 15.
> 
> Default args are great, and they're terrible. Maybe
> 
> SkRTree();
> SkRTree(int min, int max);
> ?

I just removed the defaults altogether, and changed them to ints (also added
some asserts in the constructor to check the min/max are valid).

http://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h#newcode71
src/core/SkRTree.h:71: int getCount() const { return fCount; }
On 2012/08/31 15:51:57, bsalomon wrote:
> Maybe a comment about whether this is a count of nodes or insertions
Added.

http://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h#newcode98
src/core/SkRTree.h:98: return
reinterpret_cast<Branch*>(reinterpret_cast<char*>(this) + sizeof(Node)
On 2012/08/31 15:51:57, bsalomon wrote:
> Could be shortened to:
> 
> return reinterpret_cast<Branch*>(this + 1) + index;
Good catch. Done.

[bsalomon, 2012-09-04 20:36:50]

https://codereview.appspot.com/6489055/diff/8/src/core/SkRTree.cpp
File src/core/SkRTree.cpp (right):

https://codereview.appspot.com/6489055/diff/8/src/core/SkRTree.cpp#newcode28
src/core/SkRTree.cpp:28: SkASSERT(minChildren > maxChildren && minChildren > 0);
maxChildren > minChildren?

SkRTree* SkRTree::Create()?

[rileya, 2012-09-05 12:56:57]

http://codereview.appspot.com/6489055/diff/8/src/core/SkRTree.cpp
File src/core/SkRTree.cpp (right):

http://codereview.appspot.com/6489055/diff/8/src/core/SkRTree.cpp#newcode28
src/core/SkRTree.cpp:28: SkASSERT(minChildren > maxChildren && minChildren > 0);
On 2012/09/04 20:36:50, bsalomon wrote:
> maxChildren > minChildren?
> 
> SkRTree* SkRTree::Create()?

Whoops, fixed. And added a static create function.

[bsalomon, 2012-09-05 13:02:24]

LGTM (with two minor nits)

https://codereview.appspot.com/6489055/diff/1014/src/core/SkBBoxHierarchy.h
File src/core/SkBBoxHierarchy.h (right):

https://codereview.appspot.com/6489055/diff/1014/src/core/SkBBoxHierarchy.h#n...
src/core/SkBBoxHierarchy.h:29: *        structures than repeated inserts) until
flushDeferredInserts is called or the first search.
line wrap

https://codereview.appspot.com/6489055/diff/1014/src/core/SkRTree.h
File src/core/SkRTree.h (right):

https://codereview.appspot.com/6489055/diff/1014/src/core/SkRTree.h#newcode46
src/core/SkRTree.h:46: static SkRTree* Create(int minChildren, int maxChildren);
Can you document the restrictions on min and max?

[rileya, 2012-09-05 13:38:26]

Fixed the unit test, and addressed the nits.

http://codereview.appspot.com/6489055/diff/1014/src/core/SkBBoxHierarchy.h
File src/core/SkBBoxHierarchy.h (right):

http://codereview.appspot.com/6489055/diff/1014/src/core/SkBBoxHierarchy.h#ne...
src/core/SkBBoxHierarchy.h:29: *        structures than repeated inserts) until
flushDeferredInserts is called or the first search.
On 2012/09/05 13:02:24, bsalomon wrote:
> line wrap
Fixed.

http://codereview.appspot.com/6489055/diff/1014/src/core/SkRTree.h
File src/core/SkRTree.h (right):

http://codereview.appspot.com/6489055/diff/1014/src/core/SkRTree.h#newcode46
src/core/SkRTree.h:46: static SkRTree* Create(int minChildren, int maxChildren);
On 2012/09/05 13:02:24, bsalomon wrote:
> Can you document the restrictions on min and max?
Done.

[bsalomon, 2012-09-05 13:49:27]

On 2012/09/05 13:38:26, rileya wrote:
> Fixed the unit test, and addressed the nits.
> 
> http://codereview.appspot.com/6489055/diff/1014/src/core/SkBBoxHierarchy.h
> File src/core/SkBBoxHierarchy.h (right):
> 
>
http://codereview.appspot.com/6489055/diff/1014/src/core/SkBBoxHierarchy.h#ne...
> src/core/SkBBoxHierarchy.h:29: *        structures than repeated inserts)
until
> flushDeferredInserts is called or the first search.
> On 2012/09/05 13:02:24, bsalomon wrote:
> > line wrap
> Fixed.
> 
> http://codereview.appspot.com/6489055/diff/1014/src/core/SkRTree.h
> File src/core/SkRTree.h (right):
> 
> http://codereview.appspot.com/6489055/diff/1014/src/core/SkRTree.h#newcode46
> src/core/SkRTree.h:46: static SkRTree* Create(int minChildren, int
maxChildren);
> On 2012/09/05 13:02:24, bsalomon wrote:
> > Can you document the restrictions on min and max?
> Done.

LGTM