package java.util;

import ej.annotation.Nullable;

/**
 * A comparison function, which imposes a <i>total ordering</i> on some collection of objects.
 * Comparators can be passed to a sort method to allow precise control over the sort order.
 * Comparators can also be used to control the order of certain data structures, or to provide an
 * ordering for collections of objects that don't have a {@link Comparable natural ordering}.
 * <p>
 *
 * The ordering imposed by a comparator <code>c</code> on a set of elements <code>S</code> is said to be
 * <i>consistent with equals</i> if and only if <code>c.compare(e1, e2)==0</code> has the same boolean
 * value as <code>e1.equals(e2)</code> for every <code>e1</code> and <code>e2</code> in <code>S</code>.
 * <p>
 *
 * Caution should be exercised when using a comparator capable of imposing an ordering inconsistent
 * with equals to order a sorted set (or sorted map). Suppose a sorted set (or sorted map) with an
 * explicit comparator <code>c</code> is used with elements (or keys) drawn from a set <code>S</code>. If
 * the ordering imposed by <code>c</code> on <code>S</code> is inconsistent with equals, the sorted set (or
 * sorted map) will behave "strangely." In particular the sorted set (or sorted map) will violate
 * the general contract for set (or map), which is defined in terms of <code>equals</code>.
 * <p>
 *
 * For example, suppose one adds two elements {@code a} and {@code b} such that
 * {@code (a.equals(b) && c.compare(a, b) != 0)} to an empty {@code TreeSet} with comparator
 * {@code c}. The second {@code add} operation will return true (and the size of the tree set will
 * increase) because {@code a} and {@code b} are not equivalent from the tree set's perspective,
 * even though this is contrary to the specification of the {@link Set#add Set.add} method.
 * <p>
 *
 * For the mathematically inclined, the <i>relation</i> that defines the <i>imposed ordering</i>
 * that a given comparator <code>c</code> imposes on a given set of objects <code>S</code> is:
 *
 * <pre>
 *       {(x, y) such that c.compare(x, y) &lt;= 0}.
 * </pre>
 *
 * The <i>quotient</i> for this total order is:
 *
 * <pre>
 *       {(x, y) such that c.compare(x, y) == 0}.
 * </pre>
 *
 * It follows immediately from the contract for <code>compare</code> that the quotient is an
 * <i>equivalence relation</i> on <code>S</code>, and that the imposed ordering is a <i>total order</i>
 * on <code>S</code>. When we say that the ordering imposed by <code>c</code> on <code>S</code> is <i>consistent
 * with equals</i>, we mean that the quotient for the ordering is the equivalence relation defined
 * by the objects' {@link Object#equals(Object) equals(Object)} method(s):
 *
 * <pre>
 *     {(x, y) such that x.equals(y)}.
 * </pre>
 *
 * <p>
 * Unlike {@code Comparable}, a comparator may optionally permit comparison of null arguments, while
 * maintaining the requirements for an equivalence relation.
 *
 * <p>
 * This interface is a member of the Java Collections Framework
 *
 * @param <T>
 *        the type of objects that may be compared by this comparator
 *
 */

public interface Comparator<T> {
	/**
	 * Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as
	 * the first argument is less than, equal to, or greater than the second.
	 * <p>
	 *
	 * In the foregoing description, the notation <code>sgn(</code><i>expression</i> <code>)</code> designates
	 * the mathematical <i>signum</i> function, which is defined to return one of <code>-1</code>,
	 * <code>0</code>, or <code>1</code> according to whether the value of <i>expression</i> is negative, zero
	 * or positive.
	 * <p>
	 *
	 * The implementor must ensure that <code>sgn(compare(x, y)) ==
	 * -sgn(compare(y, x))</code> for all <code>x</code> and <code>y</code>. (This implies that
	 * <code>compare(x, y)</code> must throw an exception if and only if <code>compare(y, x)</code> throws an
	 * exception.)
	 * <p>
	 *
	 * The implementor must also ensure that the relation is transitive:
	 * <code>((compare(x, y)&gt;0) &amp;&amp; (compare(y, z)&gt;0))</code> implies
	 * <code>compare(x, z)&gt;0</code>.
	 * <p>
	 *
	 * Finally, the implementor must ensure that <code>compare(x, y)==0</code> implies that
	 * <code>sgn(compare(x, z))==sgn(compare(y, z))</code> for all <code>z</code>.
	 * <p>
	 *
	 * It is generally the case, but <i>not</i> strictly required that
	 * <code>(compare(x, y)==0) == (x.equals(y))</code>. Generally speaking, any comparator that violates
	 * this condition should clearly indicate this fact. The recommended language is "Note: this
	 * comparator imposes orderings that are inconsistent with equals."
	 *
	 * @param o1
	 *        the first object to be compared.
	 * @param o2
	 *        the second object to be compared.
	 * @return a negative integer, zero, or a positive integer as the first argument is less than, equal
	 *         to, or greater than the second.
	 * @throws NullPointerException
	 *         if an argument is null and this comparator does not permit null arguments
	 * @throws ClassCastException
	 *         if the arguments' types prevent them from being compared by this comparator.
	 */
	int compare(T o1, T o2);

	/**
	 * Indicates whether some other object is &quot;equal to&quot; this comparator. This method must
	 * obey the general contract of {@link Object#equals(Object)}. Additionally, this method can return
	 * <code>true</code> <i>only</i> if the specified object is also a comparator and it imposes the same
	 * ordering as this comparator. Thus, <code>comp1.equals(comp2)</code> implies that
	 * <code>sgn(comp1.compare(o1,
	 * o2))==sgn(comp2.compare(o1, o2))</code> for every object reference <code>o1</code> and <code>o2</code>.
	 * <p>
	 *
	 * Note that it is <i>always</i> safe <i>not</i> to override <code>Object.equals(Object)</code>.
	 * However, overriding this method may, in some cases, improve performance by allowing programs to
	 * determine that two distinct comparators impose the same order.
	 *
	 * @param obj
	 *        the reference object with which to compare.
	 * @return <code>true</code> only if the specified object is also a comparator and it imposes the
	 *         same ordering as this comparator.
	 * @see Object#equals(Object)
	 * @see Object#hashCode()
	 */
	@Override
	boolean equals(@Nullable Object obj);
}