Interface UpdatingInterval
-
- All Known Implementing Classes:
BitIndexUpdatingInterval
,KeyUpdatingInterval
interface UpdatingInterval
An interval that contains indices used for partitioning an array into multiple regions.The interval provides the following functionality:
- Return the supported bounds of the interval
[left <= right]
. - Update the left or right bound of the interval using an index
k
inside the interval. - Split the interval around two indices
k1
andk2
.
Note that the interval provides the supported bounds. If an search index
k
is outside the supported bounds the result is undefined.Implementations may assume indices are positive.
- Since:
- 1.2
-
-
Method Summary
All Methods Instance Methods Abstract Methods Modifier and Type Method Description int
left()
The start (inclusive) of the interval.int
right()
The end (inclusive) of the interval.UpdatingInterval
splitLeft(int ka, int kb)
Split the interval using two splitting indices.int
updateLeft(int k)
Update the left bound of the interval sok <= left
.int
updateRight(int k)
Update the right bound of the interval soright <= k
.
-
-
-
Method Detail
-
left
int left()
The start (inclusive) of the interval.- Returns:
- start of the interval
-
right
int right()
The end (inclusive) of the interval.- Returns:
- end of the interval
-
updateLeft
int updateLeft(int k)
Update the left bound of the interval sok <= left
.Note: Requires
left < k <= right
, i.e. there exists a valid interval above the index.l-----------k----------r |--> l
- Parameters:
k
- Index to start checking from (inclusive).- Returns:
- the new left
-
updateRight
int updateRight(int k)
Update the right bound of the interval soright <= k
.Note: Requires
left <= k < right
, i.e. there exists a valid interval below the index.l-----------k----------r r <--|
- Parameters:
k
- Index to start checking from (inclusive).- Returns:
- the new right
-
splitLeft
UpdatingInterval splitLeft(int ka, int kb)
Split the interval using two splitting indices. Returns the left interval that occurs before the specified split indexka
, and updates the current interval left bound to after the specified split indexkb
.Note: Requires
left < ka <= kb < right
, i.e. there exists a valid interval both above and below the splitting indices.l-----------ka-kb----------r r1 <--| |--> l1 r1 < ka l1 > kb
If
ka <= left
orkb >= right
the result is undefined.- Parameters:
ka
- Split index.kb
- Split index.- Returns:
- the left interval
-
-