goldman.collection.spatial
Class AlternatingComparator<E>

java.lang.Object
  extended by 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.


Field Summary
protected  Comparator<? super E>[] comparators
           
 
Constructor Summary
AlternatingComparator(Comparator<? super E>... comparators)
           
 
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
 
Methods inherited from interface java.util.Comparator
equals
 

Field Detail

comparators

protected Comparator<? super E>[] comparators
Constructor Detail

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
Method Detail

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 element
b - 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 element
b - the element to be compared against the reference
discriminator - 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 element
b - 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 element
b - 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