
Parallel Colt 0.7.2  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object cern.colt.Partitioning
public class Partitioning
Given some interval boundaries, partitions arrays such that all elements falling into an interval are placed next to each other.
The algorithms partition arrays into two or more intervals. They distinguish between synchronously partitioning either one, two or three arrays. They further come in templated versions, either partitioning int[] arrays or double[] arrays.
You may want to start out reading about the simplest case: Partitioning one
int[] array into two intervals. To do so, read
partition(int[],int,int,int)
.
Next, building upon that foundation comes a method partitioning
int[] arrays into multiple intervals. See
partition(int[],int,int,int[],int,int,int[])
for related
documentation.
All other methods are no different than the one's you now already understand, except that they operate on slightly different data types.
Performance
Partitioning into two intervals is O( N ). Partitioning into k intervals is O( N * log(k)). Constants factors are minimized. No temporary memory is allocated; Partitioning is inplace.
DoublePartitioning
Field Summary  

static int 
swappedElements

Method Summary  

static int 
dualPartition(double[] list,
double[] secondary,
int from,
int to,
double splitter)
Same as dualPartition(int[],int[],int,int,int) except that it
synchronously partitions double[] rather than
int[] arrays. 
static void 
dualPartition(double[] list,
double[] secondary,
int from,
int to,
double[] splitters,
int splitFrom,
int splitTo,
int[] splitIndexes)
Same as dualPartition(int[],int[],int,int,int[],int,int,int[])
except that it synchronously partitions double[] rather
than int[] arrays. 
static int 
dualPartition(int[] list,
int[] secondary,
int from,
int to,
int splitter)
Same as partition(int[],int,int,int) except that this method
synchronously partitions two arrays at the same time; both arrays
are partially sorted according to the elements of the primary array. 
static void 
dualPartition(int[] list,
int[] secondary,
int from,
int to,
int[] splitters,
int splitFrom,
int splitTo,
int[] splitIndexes)
Same as partition(int[],int,int,int[],int,int,int[]) except that
this method synchronously partitions two arrays at the same time;
both arrays are partially sorted according to the elements of the primary
array. 
static void 
genericPartition(int from,
int to,
int splitFrom,
int splitTo,
int[] splitIndexes,
IntComparator comp,
IntComparator comp2,
IntComparator comp3,
Swapper swapper)
Same as partition(int[],int,int,int[],int,int,int[]) except that
it generically partitions arbitrary shaped data (for example
matrices or multiple arrays) rather than int[] arrays. 
static int 
partition(double[] list,
int from,
int to,
double splitter)
Same as partition(int[],int,int,int) except that it partitions
double[] rather than int[] arrays. 
static void 
partition(double[] list,
int from,
int to,
double[] splitters,
int splitFrom,
int splitTo,
int[] splitIndexes)
Same as partition(int[],int,int,int[],int,int,int[]) except that
it partitions double[] rather than int[] arrays. 
static void 
partition(DoubleArrayList list,
int from,
int to,
DoubleArrayList splitters,
IntArrayList splitIndexes)
Equivalent to partition(list.elements(), from, to, splitters.elements(), 0, splitters.size()1, splitIndexes.elements()) . 
static int 
partition(int[] list,
int from,
int to,
int splitter)
Partitions (partially sorts) the given list such that all elements falling into the given interval are placed next to each other. 
static void 
partition(int[] list,
int from,
int to,
int[] splitters,
int splitFrom,
int splitTo,
int[] splitIndexes)
Partitions (partially sorts) the given list such that all elements falling into some intervals are placed next to each other. 
static void 
partition(IntArrayList list,
int from,
int to,
IntArrayList splitters,
IntArrayList splitIndexes)
Equivalent to partition(list.elements(), from, to, splitters.elements(), 0, splitters.size()1, splitIndexes.elements()) . 
static void 
partition(Object[] list,
int from,
int to,
Object[] splitters,
int splitFrom,
int splitTo,
int[] splitIndexes,
Comparator comp)
Same as partition(int[],int,int,int[],int,int,int[]) except that
it partitions Object[] rather than int[] arrays. 
static int 
partition(Object[] list,
int from,
int to,
Object splitter,
Comparator comp)
Same as partition(int[],int,int,int) except that it
synchronously partitions the objects of the given list by the
order of the given comparator. 
static int 
triplePartition(double[] list,
double[] secondary,
double[] tertiary,
int from,
int to,
double splitter)
Same as triplePartition(int[],int[],int[],int,int,int) except
that it synchronously partitions double[] rather than
int[] arrays. 
static void 
triplePartition(double[] list,
double[] secondary,
double[] tertiary,
int from,
int to,
double[] splitters,
int splitFrom,
int splitTo,
int[] splitIndexes)
Same as triplePartition(int[],int[],int[],int,int,int[],int,int,int[])
except that it synchronously partitions double[] rather
than int[] arrays. 
static int 
triplePartition(int[] list,
int[] secondary,
int[] tertiary,
int from,
int to,
int splitter)
Same as partition(int[],int,int,int) except that this method
synchronously partitions three arrays at the same time; all three
arrays are partially sorted according to the elements of the primary
array. 
static void 
triplePartition(int[] list,
int[] secondary,
int[] tertiary,
int from,
int to,
int[] splitters,
int splitFrom,
int splitTo,
int[] splitIndexes)
Same as partition(int[],int,int,int[],int,int,int[]) except that
this method synchronously partitions three arrays at the same
time; all three arrays are partially sorted according to the elements of
the primary array. 
Methods inherited from class java.lang.Object 

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Field Detail 

public static int swappedElements
Method Detail 

public static void dualPartition(double[] list, double[] secondary, int from, int to, double[] splitters, int splitFrom, int splitTo, int[] splitIndexes)
dualPartition(int[],int[],int,int,int[],int,int,int[])
except that it synchronously partitions double[] rather
than int[] arrays.
public static int dualPartition(double[] list, double[] secondary, int from, int to, double splitter)
dualPartition(int[],int[],int,int,int)
except that it
synchronously partitions double[] rather than
int[] arrays.
public static void dualPartition(int[] list, int[] secondary, int from, int to, int[] splitters, int splitFrom, int splitTo, int[] splitIndexes)
partition(int[],int,int,int[],int,int,int[])
except that
this method synchronously partitions two arrays at the same time;
both arrays are partially sorted according to the elements of the primary
array. In other words, each time an element in the primary array is moved
from index A to B, the correspoding element within the secondary array is
also moved from index A to B.
Use cases:
Image having a large list of 2dimensional points. If memory consumption and performance matter, it is a good idea to physically lay them out as two 1dimensional arrays (using something like Point2D objects would be prohibitively expensive, both in terms of time and space). Now imagine wanting to histogram the points. We may want to partially sort the points by xcoordinate into intervals. This method efficiently does the job.
Performance:
Same as for singlepartition methods.
public static int dualPartition(int[] list, int[] secondary, int from, int to, int splitter)
partition(int[],int,int,int)
except that this method
synchronously partitions two arrays at the same time; both arrays
are partially sorted according to the elements of the primary array. In
other words, each time an element in the primary array is moved from
index A to B, the correspoding element within the secondary array is also
moved from index A to B.
Performance:
Same as for singlepartition methods.
public static void genericPartition(int from, int to, int splitFrom, int splitTo, int[] splitIndexes, IntComparator comp, IntComparator comp2, IntComparator comp3, Swapper swapper)
partition(int[],int,int,int[],int,int,int[])
except that
it generically partitions arbitrary shaped data (for example
matrices or multiple arrays) rather than int[] arrays.
This method operates on arbitrary shaped data and arbitrary shaped splitters. In fact, it has no idea what kind of data by what kind of splitters it is partitioning. Comparisons and swapping are delegated to user provided objects which know their data and can do the job.
Lets call the generic data g (it may be a matrix, one array,
three linked lists or whatever). Lets call the generic splitters
s. This class takes a user comparison function operating on two
indexes (a,b), namely an IntComparator
. The comparison
function determines whether s[a] is equal, less or greater than
g[b]. This method can then decide to swap the data g[b]
with the data g[c] (yes, c, not a). It calls a
user provided Swapper
object that knows how to swap the
data of these two indexes.
Again, note the details: Comparisons compare s[a] with g[b]. Swaps swap g[b] with g[c]. Prior to calling this method, the generic splitters s must be sorted ascending and must not contain multiple equal values. These preconditions are not checked; be sure that they are met.
from
 the index of the first element within g to be
considered.to
 the index of the last element within g to be
considered. The method considers the elements
g[from] .. g[to].splitFrom
 the index of the first splitter element to be considered.splitTo
 the index of the last splitter element to be considered. The
method considers the splitter elements
s[splitFrom] .. s[splitTo].splitIndexes
 a list into which this method fills the indexes of elements
delimiting intervals. Upon return
splitIndexes[splitFrom..splitTo] will be set
accordingly. Therefore, must satisfy
splitIndexes.length > splitTo.comp
 the comparator comparing a splitter with an element of the
generic data. Takes as first argument the index a
within the generic splitters s. Takes as second
argument the index b within the generic data
g.comp2
 the comparator to determine the order of the generic data.
Takes as first argument the index a within the
generic data g. Takes as second argument the index
b within the generic data g.comp3
 the comparator comparing a splitter with another splitter.
Takes as first argument the index a within the
generic splitters s. Takes as second argument the
index b within the generic splitters g.swapper
 an object that knows how to swap the elements at any two
indexes (a,b). Takes as first argument the index b
within the generic data g. Takes as second argument
the index c within the generic data g.
Tip: Normally you will have splitIndexes.length == s.length as well as from==0, to==g.length1 and splitFrom==0, splitTo==s.length1.
Sorting.binarySearchFromTo(int,int,IntComparator)
public static void partition(double[] list, int from, int to, double[] splitters, int splitFrom, int splitTo, int[] splitIndexes)
partition(int[],int,int,int[],int,int,int[])
except that
it partitions double[] rather than int[] arrays.
public static int partition(double[] list, int from, int to, double splitter)
partition(int[],int,int,int)
except that it partitions
double[] rather than int[] arrays.
public static void partition(int[] list, int from, int to, int[] splitters, int splitFrom, int splitTo, int[] splitIndexes)
Example:
list = (7, 4, 5, 50, 6, 4, 3, 6), splitters = (5, 10, 30) defines the three intervals [infinity,5), [5,10), [10,30). Lets define to sort the entire list (from=0, to=7) using all splitters (splitFrom==0, splitTo=2).
The method modifies the list to be list = (4, 4, 3, 6, 7, 5, 6, 50) and returns the splitIndexes = (2, 6, 6). In other words,
More formally, this method guarantees that upon return
for all j = splitFrom .. splitTo there holds:
for all i = splitIndexes[j1]+1 .. splitIndexes[j]: splitters[j1] <= list[i] < splitters[j].
Performance:
Let N=tofrom+1 be the number of elements to be partitioned. Let k=splitTosplitFrom+1 be the number of splitter elements. Then we have the following time complexities
Implementation:
The algorithm can be seen as a Bentley/McIlroy quicksort where swapping and insertion sort are omitted. It is designed to detect and take advantage of skew while maintaining good performance in the uniform case.
list
 the list to be partially sorted.from
 the index of the first element within list to be
considered.to
 the index of the last element within list to be
considered. The method considers the elements
list[from] .. list[to].splitters
 the values at which the list shall be split into intervals.
Must be sorted ascending and must not contain multiple
identical values. These preconditions are not checked; be sure
that they are met.splitFrom
 the index of the first splitter element to be considered.splitTo
 the index of the last splitter element to be considered. The
method considers the splitter elements
splitters[splitFrom] .. splitters[splitTo].splitIndexes
 a list into which this method fills the indexes of elements
delimiting intervals. Upon return
splitIndexes[splitFrom..splitTo] will be set
accordingly. Therefore, must satisfy
splitIndexes.length > splitTo.
Tip: Normally you will have splitIndexes.length == splitters.length as well as from==0, to==list.length1 and splitFrom==0, splitTo==splitters.length1.
Arrays
,
GenericSorting
,
Arrays
public static int partition(int[] list, int from, int to, int splitter)
Example:
list = (7, 4, 5, 50, 6, 4, 3, 6), splitter = 5 defines the two intervals [infinity,5), [5,+infinity].
The method modifies the list to be list = (4, 4, 3, 50, 6, 7, 5, 6) and returns the split index 2. In other words,
More formally, this method guarantees that upon return there holds:
Performance:
Let N=tofrom+1 be the number of elements to be partially sorted. Then the time complexity is O( N ). No temporary memory is allocated; the sort is inplace.
list
 the list to be partially sorted.from
 the index of the first element within list to be
considered.to
 the index of the last element within list to be
considered. The method considers the elements
list[from] .. list[to].splitter
 the value at which the list shall be split.
public static void partition(Object[] list, int from, int to, Object[] splitters, int splitFrom, int splitTo, int[] splitIndexes, Comparator comp)
partition(int[],int,int,int[],int,int,int[])
except that
it partitions Object[] rather than int[] arrays.
public static int partition(Object[] list, int from, int to, Object splitter, Comparator comp)
partition(int[],int,int,int)
except that it
synchronously partitions the objects of the given list by the
order of the given comparator.
public static void partition(DoubleArrayList list, int from, int to, DoubleArrayList splitters, IntArrayList splitIndexes)
public static void partition(IntArrayList list, int from, int to, IntArrayList splitters, IntArrayList splitIndexes)
public static void triplePartition(double[] list, double[] secondary, double[] tertiary, int from, int to, double[] splitters, int splitFrom, int splitTo, int[] splitIndexes)
triplePartition(int[],int[],int[],int,int,int[],int,int,int[])
except that it synchronously partitions double[] rather
than int[] arrays.
public static int triplePartition(double[] list, double[] secondary, double[] tertiary, int from, int to, double splitter)
triplePartition(int[],int[],int[],int,int,int)
except
that it synchronously partitions double[] rather than
int[] arrays.
public static void triplePartition(int[] list, int[] secondary, int[] tertiary, int from, int to, int[] splitters, int splitFrom, int splitTo, int[] splitIndexes)
partition(int[],int,int,int[],int,int,int[])
except that
this method synchronously partitions three arrays at the same
time; all three arrays are partially sorted according to the elements of
the primary array. In other words, each time an element in the primary
array is moved from index A to B, the correspoding element within the
secondary array as well as the corresponding element within the tertiary
array are also moved from index A to B.
Use cases:
Image having a large list of 3dimensional points. If memory consumption and performance matter, it is a good idea to physically lay them out as three 1dimensional arrays (using something like Point3D objects would be prohibitively expensive, both in terms of time and space). Now imagine wanting to histogram the points. We may want to partially sort the points by xcoordinate into intervals. This method efficiently does the job.
Performance:
Same as for singlepartition methods.
public static int triplePartition(int[] list, int[] secondary, int[] tertiary, int from, int to, int splitter)
partition(int[],int,int,int)
except that this method
synchronously partitions three arrays at the same time; all three
arrays are partially sorted according to the elements of the primary
array. In other words, each time an element in the primary array is moved
from index A to B, the correspoding element within the secondary array as
well as the corresponding element within the tertiary array are also
moved from index A to B.
Performance:
Same as for singlepartition methods.

Parallel Colt 0.7.2  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 