Page MenuHomePhabricator

[ADT] CoalescingBitVector: Add advanceToLowerBound iterator operation

Authored by vsk on Mar 19 2020, 4:56 PM.



advanceToLowerBound moves an iterator to the first bit set at, or after,
the given index. This can be faster than doing IntervalMap::find.


Diff Detail

Event Timeline

vsk created this revision.Mar 19 2020, 4:56 PM
vsk updated this revision to Diff 251517.Mar 19 2020, 5:44 PM

Allow advanceToLowerBound to be called on end(), as this happens in practice.

aprantl added inline comments.Mar 20 2020, 8:57 AM

The doxygen comment of find() doesn't actually say what its complexity is. Might be nice to add that information.

aprantl added inline comments.Mar 20 2020, 8:59 AM

It would also be good to explain when to use this function over advance_to().

jmorse accepted this revision.Mar 20 2020, 10:31 AM

LGTM otherwise

This revision is now accepted and ready to land.Mar 20 2020, 10:31 AM
vsk updated this revision to Diff 251712.Mar 20 2020, 11:54 AM
vsk marked 2 inline comments as done.

Add additional documentation, as suggested.

This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptMar 20 2020, 12:29 PM