Class KeyUpdatingInterval
- All Implemented Interfaces:
UpdatingInterval
UpdatingInterval
backed by an array of ordered keys.- Since:
- 1.2
-
Field Summary
Fields -
Constructor Summary
ConstructorsModifierConstructorDescription(package private)
KeyUpdatingInterval
(int[] indices, int n) Create an instance with the providedindices
.private
KeyUpdatingInterval
(int[] indices, int l, int r) -
Method Summary
Modifier and TypeMethodDescriptionint
left()
The start (inclusive) of the interval.int
right()
The end (inclusive) of the interval.(package private) static int
searchLessOrEqual
(int[] a, int left, int right, int k) Search the data for the largest indexi
wherea[i]
is less-than-or-equal to thekey
; else returnleft - 1
.(package private) int
size()
Return the current number of indices in the interval.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
.
-
Field Details
-
SCAN_SIZE
private static final int SCAN_SIZESize to use a scan of the keys when splitting instead of binary search. Note binary search has an overhead on small size due to the random left/right branching per iteration. It is much faster on very large sizes.- See Also:
-
keys
private final int[] keysThe ordered keys. -
l
private int lIndex of the left key. -
r
private int rIndex of the right key.
-
-
Constructor Details
-
KeyUpdatingInterval
KeyUpdatingInterval(int[] indices, int n) Create an instance with the providedindices
.Warning: Indices must be sorted and distinct.
- Parameters:
indices
- Indices.n
- Number of indices.
-
KeyUpdatingInterval
private KeyUpdatingInterval(int[] indices, int l, int r) - Parameters:
indices
- Indices.l
- Index of left key.r
- Index of right key.
-
-
Method Details
-
left
public int left()Description copied from interface:UpdatingInterval
The start (inclusive) of the interval.- Specified by:
left
in interfaceUpdatingInterval
- Returns:
- start of the interval
-
right
public int right()Description copied from interface:UpdatingInterval
The end (inclusive) of the interval.- Specified by:
right
in interfaceUpdatingInterval
- Returns:
- end of the interval
-
updateLeft
public int updateLeft(int k) Description copied from interface:UpdatingInterval
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
- Specified by:
updateLeft
in interfaceUpdatingInterval
- Parameters:
k
- Index to start checking from (inclusive).- Returns:
- the new left
-
updateRight
public int updateRight(int k) Description copied from interface:UpdatingInterval
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 <--|
- Specified by:
updateRight
in interfaceUpdatingInterval
- Parameters:
k
- Index to start checking from (inclusive).- Returns:
- the new right
-
splitLeft
Description copied from interface:UpdatingInterval
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.- Specified by:
splitLeft
in interfaceUpdatingInterval
- Parameters:
ka
- Split index.kb
- Split index.- Returns:
- the left interval
-
size
int size()Return the current number of indices in the interval.- Returns:
- the size
-
searchLessOrEqual
static int searchLessOrEqual(int[] a, int left, int right, int k) Search the data for the largest indexi
wherea[i]
is less-than-or-equal to thekey
; else returnleft - 1
.a[i] invalid input: '<'= k : left invalid input: '<'= i invalid input: '<'= right, or (left - 1)
The data is assumed to be in ascending order, otherwise the behaviour is undefined. If the range contains multiple elements with the
key
value, the result index may be any that match.This is similar to using
Arrays.binarySearch
. The method differs in:- use of an inclusive upper bound;
- returning the closest index with a value below
key
if no match was not found; - performing no range checks: it is assumed
left <= right
and they are valid indices into the array.
An equivalent use of binary search is:
int i = Arrays.binarySearch(a, left, right + 1, k); if (i < 0) { i = ~i - 1; }
This specialisation avoids the caller checking the binary search result for the use case when the presence or absence of a key is not important; only that the returned index for an absence of a key is the largest index. When used on unique keys this method can be used to update an upper index so all keys are known to be below a key:
int[] keys = ... // [i0, i1] contains all keys int i0 = 0; int i1 = keys.length - 1; // Update: [i0, i1] contains all keys <= k i1 = searchLessOrEqual(keys, i0, i1, k);
- Parameters:
a
- Data.left
- Lower bound (inclusive).right
- Upper bound (inclusive).k
- Key.- Returns:
- largest index
i
such thata[i] <= k
, orleft - 1
if no such index exists
-