1. /*

  2.  * @(#)Comparator.java	1.15 00/02/02

  3.  *

  4.  * Copyright 1997-2000 Sun Microsystems, Inc. All Rights Reserved.

  5.  * 

  6.  * This software is the proprietary information of Sun Microsystems, Inc.  

  7.  * Use is subject to license terms.

  8.  * 

  9.  */

  10. 

  11. package java.util;

  12. 

  13. /**

  14.  * A comparison function, which imposes a <i>total ordering</i> on some

  15.  * collection of objects.  Comparators can be passed to a sort method (such as

  16.  * <tt>Collections.sort</tt>) to allow precise control over the sort order.

  17.  * Comparators can also be used to control the order of certain data

  18.  * structures (such as <tt>TreeSet</tt> or <tt>TreeMap</tt>).<p>

  19.  *

  20.  * The ordering imposed by a Comparator <tt>c</tt> on a set of elements

  21.  * <tt>S</tt> is said to be <i>consistent with equals</i> if and only if

  22.  * <tt>(compare((Object)e1, (Object)e2)==0)</tt> has the same boolean value as

  23.  * <tt>e1.equals((Object)e2)</tt> for every <tt>e1</tt> and <tt>e2</tt> in

  24.  * <tt>S</tt>.<p>

  25.  *

  26.  * Caution should be exercised when using a comparator capable of imposing an

  27.  * ordering inconsistent with equals to order a sorted set (or sorted map).

  28.  * Suppose a sorted set (or sorted map) with an explicit Comparator <tt>c</tt>

  29.  * is used with elements (or keys) drawn from a set <tt>S</tt>.  If the

  30.  * ordering imposed by <tt>c</tt> on <tt>S</tt> is inconsistent with equals,

  31.  * the sorted set (or sorted map) will behave "strangely."  In particular the

  32.  * sorted set (or sorted map) will violate the general contract for set (or

  33.  * map), which is defined in terms of <tt>equals</tt>.<p>

  34.  * 

  35.  * For example, if one adds two keys <tt>a</tt> and <tt>b</tt> such that

  36.  * <tt>(a.equals((Object)b) && c.compare((Object)a, (Object)b) != 0)</tt> to a

  37.  * sorted set with comparator <tt>c</tt>, the second <tt>add</tt> operation

  38.  * will return false (and the size of the sorted set will not increase)

  39.  * because <tt>a</tt> and <tt>b</tt> are equivalent from the sorted set's

  40.  * perspective.<p>

  41.  *

  42.  * Note: It is generally a good idea for comparators to implement

  43.  * <tt>java.io.Serializable</tt>, as they may be used as ordering methods in

  44.  * serializable data structures (like <tt>TreeSet</tt>, <tt>TreeMap</tt>).  In

  45.  * order for the data structure to serialize successfully, the comparator (if

  46.  * provided) must implement <tt>Serializable</tt>.<p>

  47.  *

  48.  * For the mathematically inclined, the <i>relation</i> that defines

  49.  * the <i>total order</i> that a given comparator <tt>c</tt> imposes on a

  50.  * given set of objects <tt>S</tt> is:<pre>

  51.  *       {(x, y) such that c.compare((Object)x, (Object)y) <= 0}.

  52.  * </pre> The <i>quotient</i> for this total order is:<pre>

  53.  *       {(x, y) such that x.compareTo((Object)y) == 0}.

  54.  * </pre>

  55.  *

  56.  * It follows immediately from the contract for <tt>compare</tt> that the

  57.  * quotient is an <i>equivalence relation</i> on <tt>S</tt>, and that the

  58.  * natural ordering is a <i>total order</i> on <tt>S</tt>.  When we say that

  59.  * the ordering imposed by <tt>c</tt> on <tt>S</tt> is <i>consistent with

  60.  * equals</i>, we mean that the quotient for the natural ordering is the

  61.  * equivalence relation defined by the objects' <tt>equals(Object)</tt>

  62.  * method(s):<pre>

  63.  *       {(x, y) such that x.equals((Object)y)}.

  64.  * </pre>

  65.  *

  66.  * @author  Josh Bloch

  67.  * @version 1.15, 02/02/00

  68.  * @see Comparable

  69.  * @see Arrays#sort(Object[], Comparator)

  70.  * @see TreeMap

  71.  * @see TreeSet

  72.  * @see SortedMap

  73.  * @see SortedSet

  74.  * @see java.io.Serializable

  75.  * @since 1.2

  76.  */

  77. 

  78. public interface Comparator {

  79.     /**

  80.      * Compares its two arguments for order.  Returns a negative integer,

  81.      * zero, or a positive integer as the first argument is less than, equal

  82.      * to, or greater than the second.<p>

  83.      *

  84.      * The implementor must ensure that <tt>sgn(compare(x, y)) ==

  85.      * -sgn(compare(y, x))</tt> for all <tt>x</tt> and <tt>y</tt>.  (This

  86.      * implies that <tt>compare(x, y)</tt> must throw an exception if and only

  87.      * if <tt>compare(y, x)</tt> throws an exception.)<p>

  88.      *

  89.      * The implementor must also ensure that the relation is transitive:

  90.      * <tt>((compare(x, y)>0) && (compare(y, z)>0))</tt> implies

  91.      * <tt>compare(x, z)>0</tt>.<p>

  92.      *

  93.      * Finally, the implementer must ensure that <tt>compare(x, y)==0</tt>

  94.      * implies that <tt>sgn(compare(x, z))==sgn(compare(y, z))</tt> for all

  95.      * <tt>z</tt>.<p>

  96.      *

  97.      * It is generally the case, but <i>not</i> strictly required that 

  98.      * <tt>(compare(x, y)==0) == (x.equals(y))</tt>.  Generally speaking,

  99.      * any comparator that violates this condition should clearly indicate

  100.      * this fact.  The recommended language is "Note: this comparator

  101.      * imposes orderings that are inconsistent with equals."

  102.      * 

  103.      * @param o1 the first object to be compared.

  104.      * @param o2 the second object to be compared.

  105.      * @return a negative integer, zero, or a positive integer as the

  106.      * 	       first argument is less than, equal to, or greater than the

  107.      *	       second. 

  108.      * @throws ClassCastException if the arguments' types prevent them from

  109.      * 	       being compared by this Comparator.

  110.      */

  111.     int compare(Object o1, Object o2);

  112. 

  113.     /**

  114.      * 

  115.      * Indicates whether some other object is "equal to" this

  116.      * Comparator.  This method must obey the general contract of

  117.      * <tt>Object.equals(Object)</tt>.  Additionally, this method can return

  118.      * <tt>true</tt> <i>only</i> if the specified Object is also a comparator

  119.      * and it imposes the same ordering as this comparator.  Thus,

  120.      * <code>comp1.equals(comp2)</code> implies that <tt>sgn(comp1.compare(o1,

  121.      * o2))==sgn(comp2.compare(o1, o2))</tt> for every object reference

  122.      * <tt>o1</tt> and <tt>o2</tt>.<p>

  123.      *

  124.      * Note that it is <i>always</i> safe <i>not</i> to override

  125.      * <tt>Object.equals(Object)</tt>.  However, overriding this method may,

  126.      * in some cases, improve performance by allowing programs to determine

  127.      * that two distinct Comparators impose the same order.

  128.      *

  129.      * @param   obj   the reference object with which to compare.

  130.      * @return  <code>true</code> only if the specified object is also

  131.      *		a comparator and it imposes the same ordering as this

  132.      *		comparator.

  133.      * @see     java.lang.Object#equals(java.lang.Object)

  134.      * @see java.lang.Object#hashCode()

  135.      */

  136.     boolean equals(Object obj);

  137. }