goldman.collection.spatial
Class AlternatingComparator<E>
java.lang.Object
goldman.collection.spatial.AlternatingComparator<E>
- All Implemented Interfaces:
- Comparator<E>
public class AlternatingComparator<E>
- extends Object
- implements Comparator<E>
The alternating comparator manages the
various comparators used by the k-d tree.
Method Summary |
int |
compare(E a,
E b)
Calling the compare method has the side-effect of advancing this alternating comparator to the next dimension in
the cycle, wrapping around to dimension 0 as needed. |
int |
compare(E a,
E b,
int discriminator)
|
boolean |
equalTo(E a,
E b)
|
int |
getLastDiscriminatorUsed()
|
int |
getNumDimensions()
|
int |
nextDiscriminator(int discriminator)
|
boolean |
noGreaterThan(E a,
E b)
Two calls to this method, using the maximum and minimum corners of a multidimensional bounding box,
are sufficient to determine whether a given element lies within the box. |
void |
reset()
Returns the comparator to the beginning of the cycle of
dimensions, so that the next dimension used for unqualified comparison will be dimension 0. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
comparators
protected Comparator<? super E>[] comparators
AlternatingComparator
public AlternatingComparator(Comparator<? super E>... comparators)
- Parameters:
comparators
- a variable number of comparators defining the
dimensions of this comparator
REQUIRES:
at least two comparators are provided
reset
public void reset()
- Returns the comparator to the beginning of the cycle of
dimensions, so that the next dimension used for unqualified comparison will be dimension 0.
compare
public int compare(E a,
E b)
- Calling the compare method has the side-effect of advancing this alternating comparator to the next dimension in
the cycle, wrapping around to dimension 0 as needed.
The comparator then determines the relative ordering of two elements on the basis of that dimension of comparison.
It is important to note that two values are deemed equal only if they match along all dimensions. If they match
along the current dimension in the cycle but differ in another dimension, then a positive value is returned.
This semantics is convenient for the KDTree implementation, in which ties along a node's dimension of comparison should
result in traversal of the right subtree.
It is assumed that the first parameter is always the reference point (e.g., the element in the tree) and the second parameter is the
element under consideration (e.g., the one to be placed to its left or right).
It is important to note that this unqualified compare method violates the usual symmetric convention for comparators when a tie
occurs along the dimension of comparison.
If the elements passed to this compare method are equal with respect to the current dimension of
comparison, but differ in some other dimension, then the method returns a positive value, regardless of the order in which the
actual parameters are passed to the method.
- Specified by:
compare
in interface Comparator<E>
- Parameters:
a
- the reference elementb
- the element to be compared against the reference
- Returns:
- a negative value if a < b along the dimension of comparison, zero if a and b are equal along all dimensions,
and a positive value if a > b along the dimension of comparison
compare
public int compare(E a,
E b,
int discriminator)
- Parameters:
a
- the reference elementb
- the element to be compared against the referencediscriminator
- the index of the dimension along with the
elements should be compared
- Returns:
- a negative value if a < b, zero if a = b, and a positive value if a > b with respect to the specified dimension
noGreaterThan
public boolean noGreaterThan(E a,
E b)
- Two calls to this method, using the maximum and minimum corners of a multidimensional bounding box,
are sufficient to determine whether a given element lies within the box.
- Parameters:
a
- the candidate elementb
- the boundary element
- Returns:
- true if and only if the candidate is less than or equal to the boundary along all dimensions
equalTo
public boolean equalTo(E a,
E b)
- Parameters:
a
- the candidate elementb
- the target element
- Returns:
- true if and only if the candidate is equal to the target along all dimensions
getLastDiscriminatorUsed
public int getLastDiscriminatorUsed()
- Returns:
- the index of the most recently used dimension in this comparator's cycle, or -1 if the comparator has
not made an unqualified comparison since it was last reset
nextDiscriminator
public int nextDiscriminator(int discriminator)
- Parameters:
discriminator
- the index of a dimension of this comparator
- Returns:
- the index of the next dimension on the cycle
getNumDimensions
public int getNumDimensions()
- Returns:
- the number of dimensions used by this comparator, which is equal to the number of comparators provided to the constructor