Class KeyUpdatingInterval
- java.lang.Object
-
- org.apache.commons.numbers.arrays.KeyUpdatingInterval
-
- All Implemented Interfaces:
UpdatingInterval
final class KeyUpdatingInterval extends java.lang.Object implements UpdatingInterval
AnUpdatingInterval
backed by an array of ordered keys.- Since:
- 1.2
-
-
Constructor Summary
Constructors Modifier Constructor Description (package private)
KeyUpdatingInterval(int[] indices, int n)
Create an instance with the providedindices
.private
KeyUpdatingInterval(int[] indices, int l, int r)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description int
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.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
.
-
-
-
Field Detail
-
SCAN_SIZE
private static final int SCAN_SIZE
Size 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:
- Constant Field Values
-
keys
private final int[] keys
The ordered keys.
-
l
private int l
Index of the left key.
-
r
private int r
Index of the right key.
-
-
Constructor Detail
-
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 Detail
-
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
public UpdatingInterval splitLeft(int ka, int kb)
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] <= k : left <= i <= 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
-
-