cc: Added a spiral difference iterator to tiling data.

cc: Added a spiral difference iterator to tiling data.

This patch adds another iterator to tiling data. This iterator acts
similar to the difference iterator, but it also takes an extra center
rect parameter. The indices are returned in a counter-clockwise spiral
around the center rect. Note that the center rect itself is also
considered to be ignored.

Added tests to verify the behavior. Currently, the iterator is not used
anywhere outside of the unit tests.

R=enne@chromium.org

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=254622

[vmpstr, 2014-02-28 18:37:48]

Hi,

Please take a look. This change is to allow me to refactor the tiling iterators
and use them in update tile priorities. That is, the skewport and eventually
rect would use this spiral iterator to get tiles. 

Let me know which other unittests you'd like to see, or any other concerns that
you have.

Thank you.

[enne (OOO), 2014-02-28 19:19:55]

Shouldn't it be around the center rect and not the center point? If you have
like a really tall window, then prepainting the sides will be prioritized over
prepainting off the top and bottom, right?

[vmpstr, 2014-02-28 19:37:18]

On 2014/02/28 19:19:55, enne wrote:
> Shouldn't it be around the center rect and not the center point? If you have
> like a really tall window, then prepainting the sides will be prioritized over
> prepainting off the top and bottom, right?

Good point. We can spiral around the given rect, but then how do we return the
tiles within the rect? I mean, I know that in our use case, the rect we spiral
around is also within the ignore rect, but I don't think that should be a
requirement?

Maybe spiral inside the center rect around the center of the rect (ie pretend
center rect is consider rect), then spiral the rest of the tiling around the
center rect? So like a two phase iteration? Wdyt? I'm also not sure if I'm
making sense.

[enne (OOO), 2014-02-28 19:45:38]

On 2014/02/28 19:37:18, vmpstr wrote:
> On 2014/02/28 19:19:55, enne wrote:
> > Shouldn't it be around the center rect and not the center point? If you have
> > like a really tall window, then prepainting the sides will be prioritized
over
> > prepainting off the top and bottom, right?
> 
> Good point. We can spiral around the given rect, but then how do we return the
> tiles within the rect? I mean, I know that in our use case, the rect we spiral
> around is also within the ignore rect, but I don't think that should be a
> requirement?

I'd just say you don't.  If you want to spiral around one tile instead of a
rect, then you just make a very small rect, so that's still supported. 
(Although I don't know where it would be used.)
 
> Maybe spiral inside the center rect around the center of the rect (ie pretend
> center rect is consider rect), then spiral the rest of the tiling around the
> center rect? So like a two phase iteration? Wdyt? I'm also not sure if I'm
> making sense.

I think there are three things you want to iterate.

(1) Visible can be done with a simple iterator.
(2) Skew seems like it's spiraling outward from some rect, but ignoring tiles
outside a bounds rect.
(3) Soon seems like it's also spiraling outward from some rect, but ignoring
tiles inside an ignore rect.

[vmpstr, 2014-02-28 21:33:01]

On 2014/02/28 19:45:38, enne wrote:
> On 2014/02/28 19:37:18, vmpstr wrote:
> > On 2014/02/28 19:19:55, enne wrote:
> > > Shouldn't it be around the center rect and not the center point? If you
have
> > > like a really tall window, then prepainting the sides will be prioritized
> over
> > > prepainting off the top and bottom, right?
> > 
> > Good point. We can spiral around the given rect, but then how do we return
the
> > tiles within the rect? I mean, I know that in our use case, the rect we
spiral
> > around is also within the ignore rect, but I don't think that should be a
> > requirement?
> 
> I'd just say you don't.  If you want to spiral around one tile instead of a
> rect, then you just make a very small rect, so that's still supported. 
> (Although I don't know where it would be used.)
>  
> > Maybe spiral inside the center rect around the center of the rect (ie
pretend
> > center rect is consider rect), then spiral the rest of the tiling around the
> > center rect? So like a two phase iteration? Wdyt? I'm also not sure if I'm
> > making sense.
> 
> I think there are three things you want to iterate.
> 
> (1) Visible can be done with a simple iterator.
> (2) Skew seems like it's spiraling outward from some rect, but ignoring tiles
> outside a bounds rect.
> (3) Soon seems like it's also spiraling outward from some rect, but ignoring
> tiles inside an ignore rect.


Hi again,

Please take another look. The center is now a rect, which, for all intents and
purposes, is also ignored. This should sufficient for our use-cases. For the
record, corners are returned before sides, but have larger distance to the
spiraled rect. I think that's an acceptable limitation.

Thanks!

[enne (OOO), 2014-02-28 22:22:11]

Whoa, I really like the tests.  This looks great.  The logic seems a bit
complicated, but tests make me feel more comfortable.

Here's a few more test suggestions for edge cases that you should either assert
about or add tests around:

* Ignore contains (but is not equal to) consider and center?
* Center intersects with consider (but is not contained)
* Consider and ignore are non-intersecting
* Center intersects with ignore (but is not contained)
* Center == ignore
* Non-empty rects on empty bounds tiling data
* empty consider
* empty center (what should happen here?)
* all empty rects

[vmpstr, 2014-03-01 00:28:56]

On 2014/02/28 22:22:11, enne wrote:
> Whoa, I really like the tests.  This looks great.  The logic seems a bit
> complicated, but tests make me feel more comfortable.

I agree with both parts of that statement. I think the logic makes sense (as the
author of the CL, I'm a bit biased here). But, the unittests give me some
confidence in the correctness.

> 
> Here's a few more test suggestions for edge cases that you should either
assert
> about or add tests around:
> 
> * Ignore contains (but is not equal to) consider and center?
> * Center intersects with consider (but is not contained)
> * Consider and ignore are non-intersecting
> * Center intersects with ignore (but is not contained)
> * Center == ignore
> * Non-empty rects on empty bounds tiling data
> * empty consider
> * empty center (what should happen here?)
> * all empty rects

I've added all of those tests. Please let me know of some other ones that I
could add. The empty center case was kind of not handled, and did arbitrarily
wrong thing. Now it does an arbitrarily right thing by enumerating all indecies
and pretending that center is actually off the top-left corner.

Thanks in advance.

[enne (OOO), 2014-03-01 00:43:45]

lgtm

+aelias FYI for spiral iterators

https://codereview.chromium.org/183123004/diff/60001/cc/base/tiling_data_unit...
File cc/base/tiling_data_unittest.cc (right):

https://codereview.chromium.org/183123004/diff/60001/cc/base/tiling_data_unit...
cc/base/tiling_data_unittest.cc:1678: // Empty center. Note: This arbitrarily
puts the center to be off the top-left
I think I'd weakly prefer an empty center to just not return anything at all. 
Empty rects don't really have a position.

[aelias_OOO_until_Jul13, 2014-03-01 01:15:17]

lgtm

https://codereview.chromium.org/183123004/diff/60001/cc/base/tiling_data.h
File cc/base/tiling_data.h (right):

https://codereview.chromium.org/183123004/diff/60001/cc/base/tiling_data.h#ne...
cc/base/tiling_data.h:139: inline bool in_consider_rect() const {
nit: I don't think "inline" does anything, may as well remove it.

[vmpstr, 2014-03-03 18:32:22]

https://codereview.chromium.org/183123004/diff/60001/cc/base/tiling_data.h
File cc/base/tiling_data.h (right):

https://codereview.chromium.org/183123004/diff/60001/cc/base/tiling_data.h#ne...
cc/base/tiling_data.h:139: inline bool in_consider_rect() const {
On 2014/03/01 01:15:17, aelias wrote:
> nit: I don't think "inline" does anything, may as well remove it.

Done.

https://codereview.chromium.org/183123004/diff/60001/cc/base/tiling_data_unit...
File cc/base/tiling_data_unittest.cc (right):

https://codereview.chromium.org/183123004/diff/60001/cc/base/tiling_data_unit...
cc/base/tiling_data_unittest.cc:1678: // Empty center. Note: This arbitrarily
puts the center to be off the top-left
On 2014/03/01 00:43:45, enne wrote:
> I think I'd weakly prefer an empty center to just not return anything at all. 
> Empty rects don't really have a position.

I kept it as is, since I believe that an empty center should still enumerate all
indecies, it's just the order of those is not defined (arbitrary). I fear that
making empty center not return anything can result is subtle bugs where the
center becomes empty through some calculation and then nothing is iterated. I'm
going to CQ as is, but if you feel strongly please un-cq.

[vmpstr, 2014-03-03 18:32:27]

The CQ bit was checked by vmpstr@chromium.org

[commit-bot: I haz the power, 2014-03-03 18:38:23]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/vmpstr@chromium.org/183123004/100001

[enne (OOO), 2014-03-03 18:38:33]

lgtmstill

Having the center return everything sounds fine.  However, when you add calling
code for this, maybe add a (D?)CHECK that the center is not empty so we make
sure to not fall into this case.

[vmpstr, 2014-03-03 18:40:16]

On 2014/03/03 18:38:33, enne wrote:
> lgtmstill
> 
> Having the center return everything sounds fine.  However, when you add
calling
> code for this, maybe add a (D?)CHECK that the center is not empty so we make
> sure to not fall into this case.

sgtm.

[commit-bot: I haz the power, 2014-03-03 20:00:40]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/vmpstr@chromium.org/183123004/100001

[commit-bot: I haz the power, 2014-03-04 01:01:10]

Change committed as 254622