cc: Add ReverseSpiralDifferenceIterator.

cc: Add ReverseSpiralDifferenceIterator.

This patch adds an iterator similar to spiral difference iterator,
except that it iterates the indecies in reverse order. This is needed
for a fast eviction iterator.

R=danakj, enne

Committed: https://crrev.com/71f7f0a6516e22456a396a02fcdd1920f7f2aa0e
Cr-Commit-Position: refs/heads/master@{#300221}

[vmpstr, 2014-10-11 01:18:51]

PTAL.

Let me know if you'd like more test coverage. Currently the coverage is the same
as the spiral difference iterator, which should be pretty good. However, if you
can think of some other case that you would like tested, please let me know and
I'll add it.

[danakj, 2014-10-11 01:35:25]

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc
File cc/base/tiling_data.cc (right):

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc#n...
cc/base/tiling_data.cc:741: else if (center.x() >
tiling_data->tiling_size().width())
u mean >= width()?

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc#n...
cc/base/tiling_data.cc:749: else if (center.y() >
tiling_data->tiling_size().height())
you mean >= height()?

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc#n...
cc/base/tiling_data.cc:758: } else if (right_src_coord >
tiling_data->tiling_size().width()) {
you mean >= width()?

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc#n...
cc/base/tiling_data.cc:768: } else if (bottom_src_coord >
tiling_data->tiling_size().height()) {
and >= height()?

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc#n...
cc/base/tiling_data.cc:775: int max_distance = 0;
what if max_distance comes out negative?

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc#n...
cc/base/tiling_data.cc:817: while (!in_around_rect()) {
you could avoid nesting by recursing instead. it'd be tail recursion as long as
you return on the same line like "return ++(*this);" so it's about the same as a
loop but without the nesting? maybe? if you want

[vmpstr, 2014-10-11 02:17:44]

PTAL

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc
File cc/base/tiling_data.cc (right):

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc#n...
cc/base/tiling_data.cc:741: else if (center.x() >
tiling_data->tiling_size().width())
On 2014/10/11 01:35:24, danakj wrote:
> u mean >= width()?

I think I do?

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc#n...
cc/base/tiling_data.cc:749: else if (center.y() >
tiling_data->tiling_size().height())
On 2014/10/11 01:35:24, danakj wrote:
> you mean >= height()?

Done.

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc#n...
cc/base/tiling_data.cc:758: } else if (right_src_coord >
tiling_data->tiling_size().width()) {
On 2014/10/11 01:35:24, danakj wrote:
> you mean >= width()?

Done.

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc#n...
cc/base/tiling_data.cc:768: } else if (bottom_src_coord >
tiling_data->tiling_size().height()) {
On 2014/10/11 01:35:24, danakj wrote:
> and >= height()?

Done.

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc#n...
cc/base/tiling_data.cc:775: int max_distance = 0;
On 2014/10/11 01:35:24, danakj wrote:
> what if max_distance comes out negative?

That can only be if |consider| is contained in |around|? Then 0 padding will
work just fine, since the next step will take it into around and it will be done

https://codereview.chromium.org/645173004/diff/50001/cc/base/tiling_data.cc#n...
cc/base/tiling_data.cc:817: while (!in_around_rect()) {
On 2014/10/11 01:35:24, danakj wrote:
> you could avoid nesting by recursing instead. it'd be tail recursion as long
as
> you return on the same line like "return ++(*this);" so it's about the same as
a
> loop but without the nesting? maybe? if you want

Ehh.. I'm kind of weary of recursion in this function, since it could rotate
around for a few loops before finding a correct index or ending it, so the stack
size might grow for no good reason. I'd prefer to leave it this way, if you're
ok with that. Plus it kind of mimics the spiral iterator.

[ajuma, 2014-10-15 17:56:52]

ajuma@chromium.org changed reviewers:
+ ajuma@chromium.org

[ajuma, 2014-10-15 17:56:52]

https://codereview.chromium.org/645173004/diff/100001/cc/base/tiling_data.cc
File cc/base/tiling_data.cc (right):

https://codereview.chromium.org/645173004/diff/100001/cc/base/tiling_data.cc#...
cc/base/tiling_data.cc:802: //     -..........I
The vertical |md| had me confused for a bit, thinking these were spots labeled
'm' and 'd'. Not really sure how to make this better, but maybe inserting a
column of spaces between that and the grid might help?

https://codereview.chromium.org/645173004/diff/100001/cc/base/tiling_data.cc#...
cc/base/tiling_data.cc:854: int steps_to_take = std::min(steps_to_edge,
max_steps);
Why doesn't this need to take delta_x_ or delta_y_ into account? Is it just
because we're assuming they'll never be greater than 1 in absolute value?

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

https://codereview.chromium.org/645173004/diff/100001/cc/base/tiling_data.h#n...
cc/base/tiling_data.h:229: int around_bottom_;
Just to make sure I'm understanding, the reason we need to store the around rect
for this iterator but not for the SpiralDifferenceIterator is that it determines
the end state of this iterator but just the start state of the
SpiralDifferenceIterator?

[vmpstr, 2014-10-15 18:10:46]

ptal.

https://codereview.chromium.org/645173004/diff/100001/cc/base/tiling_data.cc
File cc/base/tiling_data.cc (right):

https://codereview.chromium.org/645173004/diff/100001/cc/base/tiling_data.cc#...
cc/base/tiling_data.cc:802: //     -..........I
On 2014/10/15 17:56:52, ajuma wrote:
> The vertical |md| had me confused for a bit, thinking these were spots labeled
> 'm' and 'd'. Not really sure how to make this better, but maybe inserting a
> column of spaces between that and the grid might help?

Ya, sorry about that :P I've added some spaces, see if that's better.

https://codereview.chromium.org/645173004/diff/100001/cc/base/tiling_data.cc#...
cc/base/tiling_data.cc:854: int steps_to_take = std::min(steps_to_edge,
max_steps);
On 2014/10/15 17:56:52, ajuma wrote:
> Why doesn't this need to take delta_x_ or delta_y_ into account? Is it just
> because we're assuming they'll never be greater than 1 in absolute value?

Yeah, delta_x_ and delta_y_ are always less than or equal to 1 in absolute
value. Maybe a better name to make this clear?

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

https://codereview.chromium.org/645173004/diff/100001/cc/base/tiling_data.h#n...
cc/base/tiling_data.h:229: int around_bottom_;
On 2014/10/15 17:56:52, ajuma wrote:
> Just to make sure I'm understanding, the reason we need to store the around
rect
> for this iterator but not for the SpiralDifferenceIterator is that it
determines
> the end state of this iterator but just the start state of the
> SpiralDifferenceIterator?

That's correct. In the outward spiral, we just start with around and set the
step counts in such a way that we don't ever enter the around rect. Here, we
kinda have to end up in the around rect, so hence storing the values.

[ajuma, 2014-10-15 18:21:27]

lgtm

https://codereview.chromium.org/645173004/diff/100001/cc/base/tiling_data.cc
File cc/base/tiling_data.cc (right):

https://codereview.chromium.org/645173004/diff/100001/cc/base/tiling_data.cc#...
cc/base/tiling_data.cc:802: //     -..........I
On 2014/10/15 18:10:46, vmpstr wrote:
> On 2014/10/15 17:56:52, ajuma wrote:
> > The vertical |md| had me confused for a bit, thinking these were spots
labeled
> > 'm' and 'd'. Not really sure how to make this better, but maybe inserting a
> > column of spaces between that and the grid might help?
> 
> Ya, sorry about that :P I've added some spaces, see if that's better.

Yes, looks better now.

https://codereview.chromium.org/645173004/diff/100001/cc/base/tiling_data.cc#...
cc/base/tiling_data.cc:854: int steps_to_take = std::min(steps_to_edge,
max_steps);
On 2014/10/15 18:10:46, vmpstr wrote:
> On 2014/10/15 17:56:52, ajuma wrote:
> > Why doesn't this need to take delta_x_ or delta_y_ into account? Is it just
> > because we're assuming they'll never be greater than 1 in absolute value?
> 
> Yeah, delta_x_ and delta_y_ are always less than or equal to 1 in absolute
> value. Maybe a better name to make this clear?

Possibly, though I'm not quite sure what that to call something that takes on
values in {-1, 0, 1}. Otherwise, maybe a comment somewhere would clarify this.

[vmpstr, 2014-10-18 19:43:12]

https://codereview.chromium.org/645173004/diff/100001/cc/base/tiling_data.cc
File cc/base/tiling_data.cc (right):

https://codereview.chromium.org/645173004/diff/100001/cc/base/tiling_data.cc#...
cc/base/tiling_data.cc:854: int steps_to_take = std::min(steps_to_edge,
max_steps);
On 2014/10/15 18:21:27, ajuma wrote:
> On 2014/10/15 18:10:46, vmpstr wrote:
> > On 2014/10/15 17:56:52, ajuma wrote:
> > > Why doesn't this need to take delta_x_ or delta_y_ into account? Is it
just
> > > because we're assuming they'll never be greater than 1 in absolute value?
> > 
> > Yeah, delta_x_ and delta_y_ are always less than or equal to 1 in absolute
> > value. Maybe a better name to make this clear?
> 
> Possibly, though I'm not quite sure what that to call something that takes on
> values in {-1, 0, 1}. Otherwise, maybe a comment somewhere would clarify this.

Done.

[vmpstr, 2014-10-18 19:43:19]

The CQ bit was checked by vmpstr@chromium.org

[commit-bot: I haz the power, 2014-10-18 19:44:00]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/645173004/150001

[commit-bot: I haz the power, 2014-10-18 22:04:58]

Committed patchset #5 (id:150001)

[commit-bot: I haz the power, 2014-10-18 22:05:51]

Patchset 5 (id:??) landed as
https://crrev.com/71f7f0a6516e22456a396a02fcdd1920f7f2aa0e
Cr-Commit-Position: refs/heads/master@{#300221}

[edlewis1876, 2014-10-19 03:13:21]

On 2014/10/11 01:18:51, vmpstr wrote:
> PTAL.
> 
> Let me know if you'd like more test coverage. Currently the coverage is the
same
> as the spiral difference iterator, which should be pretty good. However, if
you
> can think of some other case that you would like tested, please let me know
and
> I'll add it.

We need to abort project. Remove auth and all fingerprints. Need it to be sqeaky
clean