public abstract class Histogram
extends java.lang.Object
Histogram: an array of nonnegative integer numbers b[v], 0≤v<M,
where every element b[v] represents the number of occurrence of the value v
in some source array A, consisting of integer elements in 0..M−1 range.
The integer values v in the source array are 31bit:
0≤M<2^{31} (int Java type). The elements (bars) of the histogram
b[v] and also the total number of elements in the source array N are 63bit:
0≤N<2^{63} (long Java type).
The source array A is always supposed to be sorted in increasing order:
This class is designed for solving 2 basic tasks:
It's important that this class does not store and does not try to sort the source array A, it stores only the histogram b and solves both tasks on the base of it.
According the simple definition above, the rank and the percentile are integer numbers. However, this class works not with integer, but with real precision, using some generalization of the integer rank and percentile to the floatingpoint case. Below is the formal definition of the real rank and percentile.
Definition of floatingpoint percentile v(r) and rank r(v) Let b[0..M−1] be an array of nonnegative integer numbers, called the histogram (and stored by this class), and let N be the sum of all these elements (the length of the supposed, but not stored source sorted array A). In addition, we suppose that there is an additional "virtual" element b[M], which is always zero. The elements b[k] are called the bars of the histogram.
This class operates with the function v(r), called the percentile, and its inverse function v(r), called the rank. Both variables r and v are real (floatingpoint) numbers in the following ranges:
0.0≤r≤N ,0.0≤v≤M . The definition of both functions depends on so called histogram model. This class supports two following models.
 Simple histogram model
In this case, r(v) is a simple polyline generalization of the integer function: while v is increasing from some integer v_{0} to the next integer
v_{0}+1 (some bar of the histogram), the rankr(v) is either the constant ifb[v_{0}]=0 , or uniformly increased from some r_{0} tor_{0}+b[v_{0}] ifb[v_{0}]>0 . More precisely:
 v(r) = v_{0} + (r−r_{0})/b[v_{0}], where v_{0} is the minimal integer value so that b[0]+b[1]+...+b[v_{0}]>⌊r⌋ (here and below ⌊x⌋ means the integer part of x or (long)x for our nonnegative numbers), and r_{0} = this sum−b[v_{0}] =
b[0]+b[1]+...+b[v_{0}−1] . In the only special case r=N this formula is not correct, because the sum of histogram bars b[k] cannot be greater than the sum of all bars N, and we consider, by definition, thatv(N) = lim_{x→N+1}v(x) = ⌊v(N−1)⌋+1 .
Note: according this definition,v(0) = min (k∈Z: b[k]>0) andv(N) = ⌊v(N−1)⌋+1 = max (k∈Z: b[k]>0)+1 .
In a case N=0 (empty histogram), v(r) functions is considered to be undefined.
 r(v) = r_{0} + (v−v_{0})*b[v_{0}], where v_{0}=⌊v⌋ and r_{0} = b[0]+b[1]+...+b[v_{0}−1].
Note: according this definition, r(v)=0 when v<v(0) and r(v)=N when v>v(N). In particular,r(0)=0 andr(M)=N (remember thatb[M]=0 by definition).
Unlike v(r), r(v) function is defined also if N=0: in this case it is the zero constant.It's easy to see that the r(v) function is continuous, but, unfortunately, the v(r) function is discontinuous if some bars b[k] are zero. This behaviour is not too good for calculating percentiles on sparse histograms, when a lot of bars are zero. In this case, this generalization to floatingpoint almost does not improve the precision of the calculated percentile.
To better understand the sense of this model, please also read the comments to
value(long[], double)
method. Precise histogram model
Here v(r) and r(v) are also polyline functions, and they are identical to these function of the simple model in all points where the rank is integer (r∈Z). However, if the rank is not integer, we consider, by definition, that v(r) is uniformly increased from v(r_{0}) to
v(r_{0}+1) , wherer_{0}=⌊r⌋ . In other words, we interpolate the percentile v(r_{0}) between integer ranks. More precisely:
 v(r) =
As in the simple model, in the special case r=N we consider, by definition, that
 v_{0} + (r−r_{0})/b, where v_{0} is the minimal integer value so that
b[0]+b[1]+...+b[v_{0}]>⌊r⌋ ,r_{0} = b[0]+b[1]+...+b[v_{0}−1] ,b = b[v_{0}] — if b>1 andr_{0} ≤ r ≤ r_{0}+b−1 = r_{0}' ; v_{0}' + (r−r_{0}')*(v_{1}−v_{0}'), where
v_{0}' = v_{0}+(b−1)/b = v(r_{0}') andv_{1} = min (k∈Z: k>v_{0} & b[k]>0) = v(r_{0}'+1) is the next nonzero histogram bar — ifr_{0}'≤r≤r_{0}'+1=r_{1} . In a case r>N−1, there is no the next nonzero bar and we consider, by definition, thatv_{1} = v_{0}+1 .v(N) = lim_{x→N+1}v(x) = ⌊v(N−1)⌋+1 .
As in the simple model, herev(0) = min (k∈Z: b[k]>0) andv(N) = ⌊v(N−1)⌋+1 = max (k∈Z: b[k]>0)+1 .
In a case N=0 (empty histogram), v(r) functions is considered to be undefined.
 r(v) is defined as the inverse function for v(r) if v(0)≤v≤v(N); outside this range, we consider r(v)=0 when v<v(0) and r(v)=N when v>v(N). As in the simple model, in the special case N=0 we consider, by definition, that r(v)=0 for any v.
In this model both functions v(r) and r(v) are increasing and continuous. But calculations are more complicated. The difference appears if there are empty bars (
b[k]=0 ); namely, in each nonempty barb[v_{0}]=b , followed by empty bars, there is new salient point of the polyline r(v):v = v_{0}' = v_{0}+(b−1)/b , and after it the rank r(v) is increasing until the next rankr(v_{0})+b during all zero bars following afterb[v_{0}] . This feature does not appear at the right end of the histogram, if all bars following afterb[v_{0}] are zero.Note: the traditional definition of the median of the source array A with even length N=2n is
(A[n−1]+A[n])/2 (if we supposeA[0]≤A[1]≤...≤A[N−1] ). This definition is identical to the percentilev(n−0.5) in the precise histogram model, if all bars contains 0 or 1 elements (allb[k]≤1 ).To better understand the sense of this model, please also read the comments to
preciseValue(long[], double)
method.
This class is optimized for the case, when we already know some corresponding pair r (rank)
and v (percentile), and we need to slightly change the situation: add or remove several A elements,
then, maybe, little increase or decrease the known rank r or the value v and, after this,
quickly find (recalculate) the second element of the pair: correspondingly the percentile v or the
rank r. To do this, this class provides methods include
and
exlcude
, allowing to increment or decrement elements of b array
(this action corresponds to adding or removing elements to/from the source array A),
and supports the concept of the current rank and current value (percentile)
with a necessary set of methods for setting and getting them.
Usually all these method work quickly (O(1) operations), so every time when you correct the histogram
(add/remove elements) or change the current rank or the value, you can immediately read the second element
of the pair (correspondingly the percentile or the rank).
More precisely, in every object of this class, at any moment, there are:
moveToValue(double)
method or got by currentValue()
method;moveToRank(double)
method or got by currentRank()
method;moveToPreciseRank(double)
method or got by currentPreciseRank()
method.The methods include
and exlcude
do not change the current value,
but can change the current simple and precise ranks.
This class guarantees that for any v we have
This class guarantees that for any r^{S}
we have moveToValue(double)
call, the current value is equal
to the argument of this method.
If such situation takes place after moveToRank(double)
call, the current value is equal
to the moveToRank(0)
the current value v
will be equal to moveToRank(N)
the current value v
will be equal to moveToRank(double)
method.
This class guarantees that for any r^{P}
we have moveToValue(double)
method; but after the call
moveToPreciseRank(0)
the current value v
will be equal to moveToValue(double)
method; but after the call
moveToPreciseRank(N)
the current value v
will be equal to moveToPreciseRank(double)
method.
There are additional methods for setting integer values and ranks:
moveToIValue(int)
and moveToIRank(long)
. They are strictly equivalent
to floatingpoint methods moveToValue(double)
and moveToRank(double)
,
called with the same argument, but work little faster. There is no special integer version
of moveToPreciseRank(double)
method, because for integer ranks the simple and the precise
histogram models are identical.
There are additional methods for getting integer values and ranks:
currentIValue()
and currentIRank()
.
The currentIValue()
method returns the current value, rounded to an integer.
The rules of rounding are complicated enough and described in the comments to this method;
depending on the situation, it can work as rounding to the nearest integer (Math.round)
or as truncating (Math.floor). In any case, there is a guarantee that
currentIValue()
−0.5≤v<currentIValue()
+1currentIRank()
method return the rank, corresponding to w=currentIValue()
:
it is equal to
You can create an instance of this class by the following methods:
newLongHistogram(int histogramLength, int... bitLevelsOfPyramid)
;newLongHistogram(long[] histogram, int... bitLevelsOfPyramid)
;newIntHistogram(int histogramLength, int... bitLevelsOfPyramid)
;newIntHistogram(int[] histogram, int... bitLevelsOfPyramid)
.After creation, the only way to change the bars b[k] is using
include(int)
, exclude(int)
, include(int...)
and exclude(int...)
methods.
After creation, the current value v and both current ranks
Sometimes you need calculating (and supporting) not one, but several pairs "current value + current rank"
in the same histogram. If is possible to use a single object of this class and move from one pair to another,
but if the necessary values are not close to each other, the moveTo... methods work relatively
slowly. In this case, you can share the histogram b[k] between several instance of this
class by share()
method. The sharing instances work with the same b[k] array:
any modification by include
/ exclude
methods are immediately reflected
in all shared instances. But each sharing instance has an independent set of current value, current simple rank
and current precise rank. You can get all sharing instances by nextSharing()
method.
This class also provides static methods for calculating value(long[] histogram, double rank)
, value(int[] histogram, double rank)
for the simple histogram model,
preciseValue(long[] histogram, double rank)
, preciseValue(int[] histogram, double rank)
for the precise histogram model.
These methods can be useful if you need to process the given histogram only once.
The floatingpoint calculations in this class are performed not in strictfp, but in the usual mode. So, there is no guarantee that the results are absolutely identical on all platforms. Moreover, there is no guarantee that the same results, got by different ways (for example, by static methods and by creating an instance of this class and using its methods) are absolutely identical: little mismatches in the last digits after the decimal point are possible.
This class does not implement own equals and hashCode methods. So, this class does not provide a mechanism for comparing different histograms.
This class is not threadsafe, but is threadcompatible and can be synchronized manually, if multithread access is necessary.
Modifier and Type  Method and Description 

abstract long 
bar(int value)
Returns the bar #value of the histogram: b[value].

abstract long[] 
bars()
Returns all bars of the histogram.

static void 
clear(int[] histogram,
int sumOfColumns)
Fills all nonzero elements of histogram by 0.

abstract long 
currentIRank()
Returns the rank
currentIValue() . 
int 
currentIValue()
Returns the
current value v, rounded to an integer number. 
double 
currentPreciseRank()
Returns the current precise rank:

double 
currentRank()
Returns the current simple rank:

double 
currentValue()
Returns the current value v.

abstract void 
exclude(int... values)
Equivalent to a simple loop of calls of
exclude(int) method for all passed values. 
abstract void 
exclude(int value)
Decrements the bar #value of the histogram by 1: b[value].

abstract void 
include(int... values)
Equivalent to a simple loop of calls of
include(int) method for all passed values. 
abstract void 
include(int value)
Increments the bar #value of the histogram by 1: b[value]++.

static int 
iPreciseValue(int[] histogram,
double rank)
Precise equivalent of
iPreciseValue(long[], double) for a case
of int[] type of the histogram. 
static int 
iPreciseValue(long[] histogram,
double rank)
"Interpolated" version of
iValue(long[], long) , rounded to the "best" integer result. 
static int 
iValue(int[] histogram,
long rank)
Precise equivalent of
iValue(long[], long) for a case
of int[] type of the histogram. 
static int 
iValue(long[] histogram,
long rank)
Returns the element with the given index rank in the sorted array
of integer numbers 0..histogram.length1, corresponding to this histogram.

boolean 
leftFromNonZeroPart()
Returns true if and only if the current bar is zero: b[⌊v⌋]=0
(v is the
current value )
and all bars from the left are also zero: b[k]=0 for all k<⌊v⌋. 
boolean 
leftFromOrAtBoundOfNonZeroPart()
Returns true if and only all bars from the left of the current bar are zero:
b[k]=0 for all k<⌊v⌋
(v is the
current value ). 
int 
length()
Returns the number M of bars of the histogram.

abstract Histogram 
moveToIRank(long rank)
Sets the current simple rank r^{S} and
precise rank r^{P}
to be equal of the rank argument.

abstract Histogram 
moveToIValue(int value)
Sets the current value v
to be equal of the value argument.

Histogram 
moveToPreciseRank(double rank)
Sets the current precise rank r^{P}
to be equal of the rank argument.

abstract Histogram 
moveToRank(double rank)
Sets the current simple rank r^{S}
to be equal of the rank argument.

Histogram 
moveToValue(double value)
Sets the current value v
to be equal of the value argument.

static Histogram 
newIntHistogram(int[] histogram,
int... bitLevelsOfPyramid)
Creates new 32bit histogram, consisting of M=histogram.length bars, equal to elements
of the given array.

static Histogram 
newIntHistogram(int histogramLength,
int... bitLevelsOfPyramid)
Creates new 32bit histogram, consisting of M=histogramLength empty bars.

static Histogram 
newLongHistogram(int histogramLength,
int... bitLevelsOfPyramid)
Creates new histogram, consisting of M=histogramLength empty bars.

static Histogram 
newLongHistogram(long[] histogram,
int... bitLevelsOfPyramid)
Creates new histogram, consisting of M=histogram.length bars, equal to elements
of the given array.

abstract Histogram 
nextSharing()
Returns the next instance of this class, sharing the histogram array b[k] with this instance.

boolean 
outsideNonZeroPart()
Returns true if and only if the current bar is zero: b[⌊v⌋]=0
(v is the
current value )
and either all bars from the left, or all bars from the right are also zero. 
static double 
percentile(int[] histogram,
long sumOfColumns,
double percentileLevel)
Equivalent to
preciseValue (histogram,percentileLevel*(sumOfColumns1)),
if sumOfColumns>0. 
static double 
percentile(long[] histogram,
long sumOfColumns,
double percentileLevel)
Equivalent to
preciseValue (histogram,percentileLevel*(sumOfColumns1)),
if sumOfColumns>0. 
static double 
preciseValue(int[] histogram,
double rank)
Precise equivalent of
preciseValue(long[], double) for a case
of int[] type of the histogram. 
static double 
preciseValue(long[] histogram,
double rank)
"Interpolated" version of
iValue(long[], long) . 
boolean 
rightFromNonZeroPart()
Returns true if and only if the current bar is zero: b[⌊v⌋]=0
(v is the
current value )
and all bars from the right are also zero: b[k]=0 for all k>⌊v⌋. 
boolean 
rightFromOrAtBoundOfNonZeroPart()
Returns true if and only all bars from the right of the current bar are zero:
b[k]=0 for all k>⌊v⌋
(v is the
current value ). 
abstract Histogram 
share()
Creates new instance of this class, which uses the same arrays of bars b[k].

abstract long 
shareCount()
Returns the number of instances of this class, sharing the histogram array b[k]
with this instance.

static int 
sumOf(int[] histogram)
Returns the sum of all elements of the passed histogram array.

static long 
sumOf(long[] histogram)
Returns the sum of all elements of the passed histogram array.

abstract long 
total()
Returns the sum N of all bars b[k] of the histogram.

static double 
value(int[] histogram,
double rank)
Precise equivalent of
value(long[], double) for a case
of int[] type of the histogram. 
static double 
value(long[] histogram,
double rank)
Floatingpoint version of
iValue(long[], long) . 
public static Histogram newLongHistogram(int histogramLength, int... bitLevelsOfPyramid)
include(int)
method.
The bitLevelsOfPyramid argument is used for optimization of large histograms, consisting
of thousands or millions bars. Namely, this class automatically builds and supports a
pyramid of histograms: m=bitLevelsOfPyramid.length additional arrays
b^{q}[k] = Σ _{2s*k ≤ j < min(2s*(k+1), M)} b[j], s=bitLevelsOfPyramid[q−1];
b^{q}.length = ⌊M/2^{s}⌋ = histogramLength >> bitLevelsOfPyramid[q−1].
In other words, every "subhistogram" b^{q} consists of "wide" bars,
where the width of bars is
Supporting this pyramid little slows down include(int)
and exclude(int)
methods:
they require O(m) operations to correct m arrays b^{q}.
But it can essentially optimize all methods which set the current value and rank:
in the worst case they require
O (b^{m}.length + Σ _{q=1,2,...,m−1}2^{bitLevelsOfPyramid[q−1]})
and sequential settings of the current value and rank work much faster if the current value changes slightly.
Without the pyramid of histograms (m=bitLevelsOfPyramid.length=0), the required time of setting the current value or rank is O(M) in the worst case, and sequential settings of the current value and rank also work much faster if the current value changes slightly. If the histogram length M is not large, for example, 256 or less, it is possible that this class will work faster without bitLevelsOfPyramid arguments.
The passed bitLevelsOfPyramid argument is cloned by this method: no references to it are maintained by the created object.
If you are sure that the sum of all bars b[k] (the total length of the supposed
source array A) will never exceed Integer.MAX_VALUE, you can use
newIntHistogram(int, int...)
method instead of this one:
the created object will probably work little faster and will occupy less memory.
histogramLength
 the number M of bars of the new histogram.bitLevelsOfPyramid
 the bit levels: binary logarithms of widths of bars in the subhistograms
in the "histogram pyramid"; can be empty, then will be ignored
(the histogram pyramid will not be used).java.lang.NullPointerException
 if bitLevelsOfPyramid argument is null.java.lang.IllegalArgumentException
 if histogramLength<0,
or if bitLevelsOfPyramid.length>30,
or if some of elements bitLevelsOfPyramid is not in 1..31 range,
or if public static Histogram newLongHistogram(long[] histogram, int... bitLevelsOfPyramid)
The bitLevelsOfPyramid argument is used for optimization of large histograms, consisting
of thousands or millions bars. Namely, this class automatically builds and supports a
pyramid of histograms: m=bitLevelsOfPyramid.length additional arrays
b^{q}[k] = Σ _{2s*k ≤ j < min(2s*(k+1), M)} b[j], s=bitLevelsOfPyramid[q−1];
b^{q}.length = ⌊M/2^{s}⌋ = histogram.length >> bitLevelsOfPyramid[q−1].
In other words, every "subhistogram" b^{q} consists of "wide" bars,
where the width of bars is
Supporting this pyramid little slows down include(int)
and exclude(int)
methods:
they require O(m) operations to correct m arrays b^{q}.
But it can essentially optimize all methods which set the current value and rank:
in the worst case they require
O (b^{m}.length + Σ _{q=1,2,...,m−1}2^{bitLevelsOfPyramid[q−1]})
and sequential settings of the current value and rank work much faster if the current value changes slightly.
Without the pyramid of histograms (m=bitLevelsOfPyramid.length=0), the required time of setting the current value or rank is O(M) in the worst case, and sequential settings of the current value and rank also work much faster if the current value changes slightly. If the histogram length M is not large, for example, 256 or less, it is possible that this class will work faster without bitLevelsOfPyramid arguments.
The passed histogram and bitLevelsOfPyramid arguments are cloned by this method: no references to them are maintained by the created object.
If you are sure that the sum of all bars b[k] (the total length of the supposed
source array A) will never exceed Integer.MAX_VALUE, you can use
newIntHistogram(int[], int...)
method instead of this one:
the created object will probably work little faster and will occupy less memory.
histogram
 initial values of the bars b[k] of the histogram.bitLevelsOfPyramid
 the bit levels: binary logarithms of widths of bars in the subhistograms
in the "histogram pyramid"; can be empty, then will be ignored
(the histogram pyramid will not be used).java.lang.NullPointerException
 if histogram or bitLevelsOfPyramid argument is null.java.lang.IllegalArgumentException
 if some of histogram elements are negative (<0),
or if sum of all bars (elements of histogram array) is greater
than Long.MAX_VALUE,
or if bitLevelsOfPyramid.length>30,
or if some of elements bitLevelsOfPyramid is not in 1..31 range,
or if public static Histogram newIntHistogram(int histogramLength, int... bitLevelsOfPyramid)
include(int)
method.
"32bit" means that the sum of all bars b[k] (the total length of the supposed
source array A) will not be able to exceed Integer.MAX_VALUE.
If you need to process greater numbers, please use newLongHistogram(int, int...)
method
instead of this one.
The bitLevelsOfPyramid argument is used for optimization of large histograms, consisting
of thousands or millions bars. Namely, this class automatically builds and supports a
pyramid of histograms: m=bitLevelsOfPyramid.length additional arrays
b^{q}[k] = Σ _{2s*k ≤ j < min(2s*(k+1), M)} b[j], s=bitLevelsOfPyramid[q−1];
b^{q}.length = ⌊M/2^{s}⌋ = histogramLength >> bitLevelsOfPyramid[q−1].
In other words, every "subhistogram" b^{q} consists of "wide" bars,
where the width of bars is
Supporting this pyramid little slows down include(int)
and exclude(int)
methods:
they require O(m) operations to correct m arrays b^{q}.
But it can essentially optimize all methods which set the current value and rank:
in the worst case they require
O (b^{m}.length + Σ _{q=1,2,...,m−1}2^{bitLevelsOfPyramid[q−1]})
and sequential settings of the current value and rank work much faster if the current value changes slightly.
Without the pyramid of histograms (m=bitLevelsOfPyramid.length=0), the required time of setting the current value or rank is O(M) in the worst case, and sequential settings of the current value and rank also work much faster if the current value changes slightly. If the histogram length M is not large, for example, 256 or less, it is possible that this class will work faster without bitLevelsOfPyramid arguments.
The passed bitLevelsOfPyramid argument is cloned by this method: no references to it are maintained by the created object.
histogramLength
 the number M of bars of the new histogram.bitLevelsOfPyramid
 the bit levels: binary logarithms of widths of bars in the subhistograms
in the "histogram pyramid"; can be empty, then will be ignored
(the histogram pyramid will not be used).java.lang.NullPointerException
 if bitLevelsOfPyramid argument is null.java.lang.IllegalArgumentException
 if histogramLength<0,
or if bitLevelsOfPyramid.length>30,
or if some of elements bitLevelsOfPyramid is not in 1..31 range,
or if public static Histogram newIntHistogram(int[] histogram, int... bitLevelsOfPyramid)
newLongHistogram(long[], int...)
method
instead of this one.
The bitLevelsOfPyramid argument is used for optimization of large histograms, consisting
of thousands or millions bars. Namely, this class automatically builds and supports a
pyramid of histograms: m=bitLevelsOfPyramid.length additional arrays
b^{q}[k] = Σ _{2s*k ≤ j < min(2s*(k+1), M)} b[j], s=bitLevelsOfPyramid[q−1];
b^{q}.length = ⌊M/2^{s}⌋ = histogram.length >> bitLevelsOfPyramid[q−1].
In other words, every "subhistogram" b^{q} consists of "wide" bars,
where the width of bars is
Supporting this pyramid little slows down include(int)
and exclude(int)
methods:
they require O(m) operations to correct m arrays b^{q}.
But it can essentially optimize all methods which set the current value and rank:
in the worst case they require
O (b^{m}.length + Σ _{q=1,2,...,m−1}2^{bitLevelsOfPyramid[q−1]})
and sequential settings of the current value and rank work much faster if the current value changes slightly.
Without the pyramid of histograms (m=bitLevelsOfPyramid.length=0), the required time of setting the current value or rank is O(M) in the worst case, and sequential settings of the current value and rank also work much faster if the current value changes slightly. If the histogram length M is not large, for example, 256 or less, it is possible that this class will work faster without bitLevelsOfPyramid arguments.
The passed histogram and bitLevelsOfPyramid arguments are cloned by this method: no references to them are maintained by the created object.
histogram
 initial values of the bars b[k] of the histogram.bitLevelsOfPyramid
 the bit levels: binary logarithms of widths of bars in the subhistograms
in the "histogram pyramid"; can be empty, then will be ignored
(the histogram pyramid will not be used).java.lang.NullPointerException
 if histogram or bitLevelsOfPyramid argument is null.java.lang.IllegalArgumentException
 if some of histogram elements are negative (<0),
or if sum of all bars (elements of histogram array) is greater
than Integer.MAX_VALUE,
or if bitLevelsOfPyramid.length>30,
or if some of elements bitLevelsOfPyramid is not in 1..31 range,
or if public final int length()
The result of this method is always nonnegative (≥0).
public abstract long total()
The result of this method is always nonnegative (≥0).
public abstract long bar(int value)
length()
,
this method returns 0 and does not throw an exception
(unlike include
and exclude
methods).
The result of this method is always nonnegative (≥0).
value
 the index of the bar; can be out of 0..M range.public abstract long[] bars()
length()
,
and the element #k is equal to b[k].
The returned array is never a reference to an internal array stored in this object: if necessary, the internal Java array is cloned.
public abstract void include(int value)
If this histogram is 32bit, that is created by newIntHistogram(int, int...)
or
newIntHistogram(int[], int...)
method, this method throws IllegalStateException
if the current sum of all bars total()
is Integer.MAX_VALUE (2^{31}−1).
In other cases, this method throws IllegalStateException
if the current sum of all bars is Long.MAX_VALUE (2^{63}−1).
In a case of throwing an exception, this method does not change the histogram.
This method does not change the current value, but can change the current simple and precise ranks.
If there are some sharing instances
, this method change ranks in all sharing instances.
value
 the index of the increased histogram bar.java.lang.IndexOutOfBoundsException
 if value<0 or value>=M=length()
.java.lang.IllegalStateException
 if total()
==Long.MAX_VALUE (or Integer.MAX_VALUE
for 32bit histogram).exclude(int)
,
include(int...)
,
exclude(int...)
public abstract void exclude(int value)
If the bar #value of the histogram is zero (b[value]=0), this method throws IllegalStateException and does not change the histogram. So, the bars of the histogram cannot become negative.
This method does not change the current value, but can change the current simple and precise ranks.
If there are some sharing instances
, this method change ranks in all sharing instances.
value
 the index of the increased histogram bar.java.lang.IndexOutOfBoundsException
 if value<0 or value>=M=length()
.java.lang.IllegalStateException
 if b[value]=0.include(int)
,
include(int...)
,
exclude(int...)
public abstract void include(int... values)
include(int)
method for all passed values.
The only possible difference from this loop is that the exception, if it occur, can be thrown
at the very beginning (but can also be thrown only while increasing the corresponding bar).
As well as the simple loop of include(int)
, this method
can be nonatomic regarding this failure: it can increase some histogram bars
and then throw an exception.
values
 the indexes of the increased histogram bars. If some index is repeated several times
in this array, the corresponding histogram bar will be increased several times.java.lang.NullPointerException
 if values array is null.java.lang.IndexOutOfBoundsException
 if some values[k]<0 or
values[k]>=M=length()
.java.lang.IllegalStateException
 if total()
>Long.MAX_VALUEvalues.length
(or Integer.MAX_VALUEvalues.length for 32bit histogram).include(int)
,
exclude(int)
,
exclude(int...)
public abstract void exclude(int... values)
exclude(int)
method for all passed values.
The only possible difference from this loop is that the exception, if it occur, can be thrown
at the very beginning (but can also be thrown only while decreasing the corresponding bar).
As well as the simple loop of exclude(int)
, this method
can be nonatomic regarding this failure: it can decrease some histogram bars
and then throw an exception.
values
 the indexes of the decreased histogram bars. If some index is repeated several times
in this array, the corresponding histogram bar will be decreased several times.java.lang.NullPointerException
 if values array is null.java.lang.IndexOutOfBoundsException
 if some values[k]<0 or
values[k]>=M=length()
.java.lang.IllegalStateException
 if b[values[k]]=0 for some k.include(int)
,
exclude(int)
,
include(int...)
public abstract long currentIRank()
currentIValue()
.
(This rank is the same in both histogram models.)
In other words, it is the sum of all histogram bars b[k] from the left
of the bar #w:
comments to Histogram class
for more details.currentRank()
,
currentPreciseRank()
public final double currentRank()
comments to Histogram class
for more details.currentPreciseRank()
,
currentIRank()
public final double currentPreciseRank()
comments to Histogram class
for more details.currentRank()
,
currentIRank()
public final int currentIValue()
current value
v, rounded to an integer number.
The rules of rounding depend on the order of previous calls of 5 methods, changing
the current value and ranks: moveToValue(double)
, moveToRank(double)
,
moveToPreciseRank(double)
, moveToIValue(int)
, moveToIRank(long)
.
(Calls of any other methods, in particular, include
and exclude
,
do not affect to the result of this method.)
If the last from those methods was
moveToValue
,
moveToRank
,
moveToIValue
or
moveToIRank
,
then the result of this method is just the integer part of the current value: ⌊v⌋.
But after moveToPreciseRank
method the returned value will be equal to
iPreciseValue(histogram, rank)
, where histogram
is this histogram (the result of bars()
method) and rank is the argument of
moveToPreciseRank(double)
.
The special case
total()
=0moveToPreciseRank
,
moveToRank
and moveToIRank
are equivalent,
but the concrete results of currentValue()
method (i.e. v)
and this method are not documented — unlike the result of
iPreciseValue
static function, which returns 0 in this case.
However, in this case, as after any call of moveToRank
/
moveToIRank
, there is a guarantee that the result of this method is equal to
the integer part of the current value ⌊v⌋.
Immediately after creating a new histogram this method always returns 0 (like currentValue()
).
This result of this method always lies between (int)v=⌊v⌋
and
currentValue()
public final double currentValue()
moveToRank(double)
method, or in terms of the precise histogram model,
if before this we called moveToPreciseRank(double)
method.
See comments to Histogram class
for more details.currentIValue()
public final boolean outsideNonZeroPart()
current value
)
and either all bars from the left, or all bars from the right are also zero.
Equivalent to leftFromNonZeroPart()
 rightFromNonZeroPart()
public final boolean leftFromNonZeroPart()
current value
)
and all bars from the left are also zero: b[k]=0 for all k<⌊v⌋.public final boolean leftFromOrAtBoundOfNonZeroPart()
current value
).public final boolean rightFromNonZeroPart()
current value
)
and all bars from the right are also zero: b[k]=0 for all k>⌊v⌋.public final boolean rightFromOrAtBoundOfNonZeroPart()
current value
).public abstract Histogram moveToIRank(long rank)
total()
current value
v automatically changes
in accordance to the new rank.
See comments to Histogram class
for more details.
In the special case N=0 (all bars of the histograms are zero),
both simple and precise ranks are always zero, not depending on calls of this method:
This method works little faster than equivalent calls
moveToRank(rank)
and
moveToPreciseRank(rank)
.
rank
 new rank r^{S}=r^{P}.moveToRank(double)
,
moveToPreciseRank(double)
public abstract Histogram moveToRank(double rank)
total()
current precise rank
r^{P}
and the current value
v
automatically change in accordance to the new simple rank.
See comments to Histogram class
for more details.
In the special case N=0 (all bars of the histograms are zero),
both simple and precise ranks are always zero, not depending on calls of this method:
rank
 new simple rank r^{S}.java.lang.IllegalArgumentException
 if Double.isNaN(rank).moveToPreciseRank(double)
,
moveToIRank(long)
public Histogram moveToPreciseRank(double rank)
total()
current simple rank
r^{S}
and the current value
v automatically change
in accordance to the new precise rank.
See comments to Histogram class
for more details.
In the special case N=0 (all bars of the histograms are zero),
both simple and precise ranks are always zero, not depending on calls of this method:
rank
 new precise rank r^{P}.java.lang.IllegalArgumentException
 if Double.isNaN(rank).moveToRank(double)
,
moveToIRank(long)
public abstract Histogram moveToIValue(int value)
length()
current simple rank
r^{S}
and the current precise rank
r^{P}
automatically change in accordance to the new value.
See comments to Histogram class
for more details.
This methods works little faster than the equivalent call
moveToValue(value)
.
value
 new current value (percentile).moveToValue(double)
public Histogram moveToValue(double value)
length()
current simple rank
r^{S}
and the current precise rank
r^{P}
automatically change in accordance to the new value.
See comments to Histogram class
for more details.value
 new current value (percentile).java.lang.IllegalArgumentException
 if Double.isNaN(value).moveToIValue(int)
public abstract long shareCount()
nextSharing()
method. Returns 1 if share()
method was not used.
It is obvious that this method always returns the same value for all instances sharing the same histogram array.
public abstract Histogram nextSharing()
All instances, created by share()
method, are connected into a circular list, and this method
returns the next element in this list. For example, if the instance h1 was created by
newLongHistogram(int, int...)
method and, after this, the instance h2 was created as
share()
You can get all instances, sharing the same array b[k] with the given histogram hist, by the following loop:
Histogram h = hist.nextSharing(); do { // some processing h instance h = h.nextSharing(); } while (h != hist);
See comments to Histogram class
for more details.
share()
method.shareCount()
public abstract Histogram share()
include
/ exclude
methods
will be immediately reflected in all shared instances. However, the created sharing instance
has an independent set of current value
, current simple rank
and current precise rank
, and they are initially set to 0.
The returned instance has the absolutely same behaviour as this one: it uses the same set of
bit levels (see comments to newLongHistogram(int, int...)
method),
it is 32bit
if and only if this instance is 32bit,
it is a SummingHistogram
if and only if this instance is a SummingHistogram
, etc.
See comments to Histogram class
for more details.
nextSharing()
,
shareCount()
public static int iValue(long[] histogram, long rank)
More precisely, returns minimal integer value v so that
histogram
 histogram[k] is the number of elements in some source array
that are equal to k.
All histogram[k] must be nonnegative; in other case,
IllegalArgumentException can be thrown (but also can be not thrown).rank
 the index in the source array.java.lang.NullPointerException
 if histogram argument is null.value(long[], double)
,
preciseValue(long[], double)
public static int iValue(int[] histogram, long rank)
iValue(long[], long)
for a case
of int[] type of the histogram.histogram
 histogram[k] is the number of elements in the source array
that are equal to k.
All histogram[k] must be nonnegative; in other case,
IllegalArgumentException can be thrown (but also can be not thrown).rank
 the index in the source array.java.lang.NullPointerException
 if histogram argument is null.value(int[], double)
,
preciseValue(int[], double)
public static double value(long[] histogram, double rank)
iValue(long[], long)
.
Alike preciseValue(long[], double)
, this function supposes that the histogram
is built on an array of floatingpoint values after truncating them to an integer value
(long)value, but it doesn't try to interpolate value between different bars of the histogram.
More precisely, we suppose that if b[k]==b
(here and below b[k]=histogram[k]),
it means that the source floatingpoint array contains b values
preciseValue(long[], double)
, we do not find the next element
v_{2}
in the following bars of the histogram, but just interpolate between v_{1}
and v_{2}=v_{1}+1/b[v_{0}].
As iValue(long[], long)
, if rank<0, this method returns
The result of this method is equal to the percentile v(r) for the passed
r=rank in terms of the simple histogram model:
see comments to Histogram class
for more details.
histogram
 histogram[k] is the number of elements in the source floatingpoint array
that are "almost equal" to k.
All histogram[k] must be nonnegative; in other case,
IllegalArgumentException can be thrown (but also can be not thrown).rank
 the index in the source array (if noninteger, this method returns a real value,
which is little greater than the element #r_{1}=(long)rank,
but is less than the next element #r_{1}+1 and has the same integer part).java.lang.NullPointerException
 if histogram argument is null.java.lang.IllegalArgumentException
 if Double.isNaN(rank).preciseValue(long[], double)
public static double value(int[] histogram, double rank)
value(long[], double)
for a case
of int[] type of the histogram.histogram
 histogram[k] is the number of elements in the source floatingpoint array
that are "almost equal" to k.
All histogram[k] must be nonnegative; in other case,
IllegalArgumentException can be thrown (but also can be not thrown).rank
 the index in the source array (if noninteger, this method returns a real value,
which is little greater than the element #r_{1}=(long)rank,
but is less than the next element #r_{1}+1 and has the same integer part).java.lang.NullPointerException
 if histogram argument is null.java.lang.IllegalArgumentException
 if Double.isNaN(rank).preciseValue(int[], double)
public static int iPreciseValue(long[] histogram, double rank)
iValue(long[], long)
, rounded to the "best" integer result.
Alike preciseValue(long[], double)
, this function supposes that the histogram
is built on an array of floatingpoint values after truncating them to an integer value
(long)value. In addition to preciseValue
,
this function tries to approximate the real result by some nearest integer value.
More precisely, we suppose that if b[k]==b
(here and below b[k]=histogram[k]),
it means that the source floatingpoint array contains b values
preciseValue
.
After this, the behaviour of this method is more complicated. If rank is not integer,
we calculate preciseValue
call with the same arguments)
and
This method finds the integer range
The result of this method always lies between (int)p and Math.round(p),
where p=preciseValue
(histogram,rank).
As iValue(long[], long)
, if rank<0, this method returns
histogram
 histogram[k] is the number of elements in the source floatingpoint array
that are "almost equal" to k.
All histogram[k] must be nonnegative; in other case,
IllegalArgumentException can be thrown (but also can be not thrown).rank
 the index in the source array (if noninteger, this method interpolates nearest elements).java.lang.NullPointerException
 if histogram argument is null.java.lang.IllegalArgumentException
 if Double.isNaN(rank).iValue(long[], long)
,
preciseValue(long[], double)
public static int iPreciseValue(int[] histogram, double rank)
iPreciseValue(long[], double)
for a case
of int[] type of the histogram.histogram
 histogram[k] is the number of elements in the source floatingpoint array
that are "almost equal" to k.
All histogram[k] must be nonnegative; in other case,
IllegalArgumentException can be thrown (but also can be not thrown).rank
 the index in the source array (if noninteger, this method interpolates nearest elements).java.lang.NullPointerException
 if histogram argument is null.java.lang.IllegalArgumentException
 if Double.isNaN(rank).iValue(long[], long)
public static double preciseValue(long[] histogram, double rank)
iValue(long[], long)
.
This function supposes that the histogram is built on an array of
floatingpoint values after truncating them to an integer value (long)value.
More precisely, we suppose that if b[k]==b
(here and below b[k]=histogram[k]),
it means that the source floatingpoint array contains b values
After finding v_{1} and v_{2}, this method returns the value
interpolated between them:
As iValue(long[], long)
, if rank<0, this method returns
Please compare the described behaviour with little more simple behaviour of
value(long[], double)
method.
The result of this method is equal to the percentile v(r) for the passed
r=rank in terms of the precise histogram model:
see comments to Histogram class
for more details.
histogram
 histogram[k] is the number of elements in the source array
that are "almost equal" to k.
All histogram[k] must be nonnegative; in other case,
IllegalArgumentException can be thrown (but also can be not thrown).rank
 the index in the source array (if noninteger, this method interpolates nearest elements).java.lang.NullPointerException
 if histogram argument is null.java.lang.IllegalArgumentException
 if Double.isNaN(rank).value(long[], double)
,
iPreciseValue(long[], double)
public static double preciseValue(int[] histogram, double rank)
preciseValue(long[], double)
for a case
of int[] type of the histogram.histogram
 histogram[k] is the number of elements in the source array
that are "almost equal" to k.
All histogram[k] must be nonnegative; in other case,
IllegalArgumentException can be thrown (but also can be not thrown).rank
 the index in the source array (if noninteger, this method interpolates nearest elements).java.lang.NullPointerException
 if histogram argument is null.java.lang.IllegalArgumentException
 if Double.isNaN(rank).iPreciseValue(int[], double)
public static double percentile(long[] histogram, long sumOfColumns, double percentileLevel)
preciseValue
(histogram,percentileLevel*(sumOfColumns1)),
if sumOfColumns>0.
If sumOfColumns==0, this method immediately returns 0.0;
if sumOfColumns<0, this method throws an exception.
If is supposed that sumOfColumns is the sum of all histogram elements.
If it is true, the returned value is usually called the percentile of the source array
with the level specified by percentileLevel argument.
If percentileLevel==0.5, this value is also called the median of the source array.
But, of course, you can pass any positive value as sumOfColumns: in any case,
if sumOfColumns>0, this method returns the result of preciseValue
(histogram,percentileLevel*(sumOfColumns1)).
histogram
 histogram[k] is the number of elements in the source array
that are "almost equal" to k.
All histogram[k] must be nonnegative; in other case,
IllegalArgumentException can be thrown (but also can be not thrown).sumOfColumns
 should be equal to sum of all histogram elements
(in other words, the length of the source array).percentileLevel
 the percentile level (usually from 0.0 to 1.0).java.lang.NullPointerException
 if histogram argument is null.java.lang.IllegalArgumentException
 if Double.isNaN(percentileLevel) or if sumOfColumns<0.sumOf(long[])
public static double percentile(int[] histogram, long sumOfColumns, double percentileLevel)
preciseValue
(histogram,percentileLevel*(sumOfColumns1)),
if sumOfColumns>0.
If sumOfColumns==0, this method immediately returns 0.0;
if sumOfColumns<0, this method throws an exception.
If is supposed that sumOfColumns is the sum of all histogram elements.
If it is true, the returned value is usually called the percentile of the source array
with the level specified by percentileLevel argument.
If percentileLevel==0.5, this value is also called the median of the source array.
But, of course, you can pass any positive value as sumOfColumns: in any case,
if sumOfColumns>0, this method returns the result of preciseValue
(histogram,percentileLevel*(sumOfColumns1)).
histogram
 histogram[k] is the number of elements in the source array
that are "almost equal" to k.
All histogram[k] must be nonnegative; in other case,
IllegalArgumentException can be thrown (but also can be not thrown).sumOfColumns
 should be equal to sum of all histogram elements
(in other words, the length of the source array).percentileLevel
 the percentile level (usually from 0.0 to 1.0).java.lang.NullPointerException
 if histogram argument is null.java.lang.IllegalArgumentException
 if Double.isNaN(percentileLevel) or if sumOfColumns<0.sumOf(int[])
public static long sumOf(long[] histogram)
histogram
 any array (for example, a histogram).java.lang.NullPointerException
 if histogram argument is null.public static int sumOf(int[] histogram)
histogram
 any array (for example, a histogram).java.lang.NullPointerException
 if histogram argument is null.public static void clear(int[] histogram, int sumOfColumns)
Works faster then trivial loop for all elements histogram[0..histogram.length1], if most of last elements of histogram array already contain zero.
histogram
 cleared histogram.sumOfColumns
 should be equal to sum of all histogram elements.