First complete draft of the equivalence, partia...

First complete draft of the equivalence, partial ordering, and total
ordering traits. Documentation for the total ordering is a little
"novel".

3 files changed, 148 insertions, 13 deletions

diff --git a/src/library/scala/Equiv.scala b/src/library/scala/Equiv.scala
index bcbaf26c8b..07e7793d58 100644
--- a/src/library/scala/Equiv.scala
+++ b/src/library/scala/Equiv.scala
@@ -10,15 +10,32 @@
 
 package scala
 
-/** A trait for representing equivalence relations.
- *  @author  Geoffrey Washburn
- *  @version 0.9, 2008-03-19
+/** A trait for representing equivalence relations.  It is important to
+ * distinguish between a type that can be compared for equality or
+ * equivalence and a representation of equivalence on some type.  This
+ * trait is for representing the latter.
+ *
+ * An <a href="http://en.wikipedia.org/wiki/Equivalence_relation">equivalence
+ * relation</a> is a binary relation on a type.  This relation is exposed as
+ * the <code>equiv</code> method of the <code>Equiv</code> trait.  This
+ * relation must be:
+ * <ul>
+ * <li>reflexive: <code>equiv(x, x) == true</code>, for any <code>x</code> of
+ * type <code>T</code>.</li>
+ * <li>symmetric: <code>equiv(x, y) == equiv(y, x)</code>, for any <code>x</code>
+ * and <code>y</code> of type <code>T</code>.</li>
+ * <li>transitive: if <code>equiv(x, y) == true</code> and <code>equiv(y, z) == true</code>
+ * then <code>equiv(x, z) == true</code>, for any <code>x</code>, <code>y</code>,
+ * and <code>z</code> of type <code>T</code>.</li>
+ * </ul>
+ *
+ * @author  Geoffrey Washburn
+ * @version 1.0, 2008-04-03
  */
 
 trait Equiv[T] {
   /** Returns <code>true</code> iff <code>x</code> is equivalent to
-   *  <code>y</code>.  The implementation should be equivalence
-   *  relation: reflexive, transitive, symmetric.
+   *  <code>y</code>.
    */
   def equiv(x: T, y: T): Boolean
 }
diff --git a/src/library/scala/Ordering.scala b/src/library/scala/Ordering.scala
index 9ae63fd641..358cfb5bdf 100644
--- a/src/library/scala/Ordering.scala
+++ b/src/library/scala/Ordering.scala
@@ -10,15 +10,71 @@
 
 package scala
 
-/** A trait for representing total orderings.
- *  @author  Geoffrey Washburn
- *  @version 0.9, 2008-03-19
+/** A trait for representing total orderings.  It is important to
+ * distinguish between a type that has a total order and a represnetation
+ * of total  ordering on some type.  This trait is for representing the
+ * latter.
+ *
+ * A <a href="http://en.wikipedia.org/wiki/Total_order">total ordering</a>
+ * is a binary relation on a type <code>T</code> that is also a partial
+ * ordering on values of type <code>T</code>.  This relation is exposed as
+ * the <code>compare</code> method of the <code>Ordering</code> trait.
+ * This relation must be:
+ * <ul>
+ * <li>reflexive: <code>compare(x, x) == 0</code>, for any <code>x</code> of
+ * type <code>T</code>.</li>
+ * <li>(need a name): <code>compare(x, y) == z</code> and <code>compare(y, x) == w</code>
+ * then <code>Math.signum(z) == -Math.signum(w)</code>, for any <code>x</code> and <code>y</code> of
+ * type <code>T</code> and <code>z</code> and <code>w</code> of type <code>Int</code>.</li>
+ * <li>upward transitive: if <code>compare(x, y) == z</code> and <code>lteq(y, w) == v</code>
+ * and <code>Math.signum(z) >= 0</code> and <code>Math.signum(v) >= 0</code> then
+ * <code>compare(x, w) == u</code> and <code>Math.signum(z + v) == Math.signum(u)</code>,
+ * for any <code>x</code>, <code>y</code>,
+ * and <code>w</code> of type <code>T</code> and <code>z</code>, <code>v</code>, and <code>u</code>
+ * of type <code>Int</code>.</li>
+ * <li>downward transitive: if <code>compare(x, y) == z</code> and <code>lteq(y, w) == v</code>
+ * and <code>Math.signum(z) <= 0</code> and <code>Math.signum(v) <= 0</code> then
+ * <code>compare(x, w) == u</code> and <code>Math.signum(z + v) == Math.signum(u)</code>,
+ * for any <code>x</code>, <code>y</code>,
+ * and <code>w</code> of type <code>T</code> and <code>z</code>, <code>v</code>, and <code>u</code>
+ * of type <code>Int</code>.</li>
+ * </ul>
+ *
+ * @author Geoffrey Washburn
+ * @version 0.9, 2008-04-03
  */
 
-trait Ordering[T] extends Equiv[T] {
+trait Ordering[T] extends PartialOrdering[T] {
+ /** Returns a negative integer iff <code>x</code> comes before
+   * <code>y</code> in the ordering, returns 0 iff <code>x</code>
+   * is the same in the ordering as <code>y</code>, and returns a
+   * positive number iff <code>x</code> comes after
+   * <code>y</code> in the ordering.
+   */
   def compare(x: T, y: T): Int
-  def gteq(x: T, y: T): Boolean = compare(x, y) >= 0
-  def lteq(x: T, y: T): Boolean = compare(x, y) <= 0
-  def lt(x: T, y: T): Boolean = compare(x, y) < 0
-  def gt(x: T, y: T): Boolean = compare(x, y) > 0
+
+ /** Returns <code>true</code> iff <code>x</code> comes before
+   *  <code>y</code> in the ordering.
+   */
+  override def lteq(x: T, y: T): Boolean = compare(x, y) <= 0
+
+  /** Returns <code>true</code> iff <code>y</code> comes before
+   *  <code>x</code> in the ordering.
+   */
+  override def gteq(x: T, y: T): Boolean = compare(x, y) >= 0
+
+  /** Returns <code>true</code> iff <code>x</code> comes before
+   *  <code>y</code> in the ordering and is not the same as <code>y</code>.
+   */
+  override def lt(x: T, y: T): Boolean = compare(x, y) < 0
+
+  /** Returns <code>true</code> iff <code>y</code> comes before
+   *  <code>x</code> in the ordering and is not the same as <code>x</code>.
+   */
+  override def gt(x: T, y: T): Boolean = compare(x, y) > 0
+
+  /** Returns <code>true</code> iff <code>x</code> is equivalent to
+   *  <code>y</code> in the ordering.
+   */
+  override def equiv(x: T, y: T): Boolean = compare(x, y) == 0
 }
diff --git a/src/library/scala/PartialOrdering.scala b/src/library/scala/PartialOrdering.scala
new file mode 100644
index 0000000000..0945121724
--- /dev/null
+++ b/src/library/scala/PartialOrdering.scala
@@ -0,0 +1,62 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2008, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala
+
+/** A trait for representing partial orderings.  It is important to
+ * distinguish between a type that has a partial order and a represnetation
+ * of partial ordering on some type.  This trait is for representing the latter.
+ *
+ * A <a href="http://en.wikipedia.org/wiki/Partial_order">partial ordering</a>
+ * is a binary relation on a type <code>T</code> that is also an equivalence
+ * relation on values of type <code>T</code>.  This relation is exposed as
+ * the <code>lteq</code> method of the <code>PartialOrdering</code> trait.
+ * This relation must be:
+ * <ul>
+ * <li>an equivalence relation: if <code>equiv(x, y)</code> then <code>lteq(x, y)</code>,
+ * for any <code>x</code> and <code>y</code> of type <code>T</code>.</li>
+ * <li>anti-symmetric: <code>lteq(x, y) == true</code> and <code>lteq(y, x) == true</code>
+ * then <code>equiv(x, y)</code>, for any <code>x</code> and <code>y</code> of
+ * type <code>T</code>.</li>
+ * <li>transitive: if <code>lteq(x, y) == true</code> and <code>lteq(y, z) == true</code>
+ * then <code>lteq(x, z) == true</code>,  for any <code>x</code>, <code>y</code>,
+ * and <code>z</code> of type <code>T</code>.</li>
+ * </ul>
+ *
+ *  @author  Geoffrey Washburn
+ *  @version 1.0, 2008-04-0-3
+ */
+
+trait PartialOrdering[T] extends Equiv[T] {
+  /** Returns <code>true</code> iff <code>x</code> comes before
+   *  <code>y</code> in the ordering.
+   */
+  def lteq(x: T, y: T): Boolean
+
+  /** Returns <code>true</code> iff <code>y</code> comes before
+   *  <code>x</code> in the ordering.
+   */
+  def gteq(x: T, y: T): Boolean = lteq(y, x)
+
+  /** Returns <code>true</code> iff <code>x</code> comes before
+   *  <code>y</code> in the ordering and is not the same as <code>y</code>.
+   */
+  def lt(x: T, y: T): Boolean = lteq(x, y) && !equiv(x, y)
+
+  /** Returns <code>true</code> iff <code>y</code> comes before
+   *  <code>x</code> in the ordering and is not the same as <code>x</code>.
+   */
+  def gt(x: T, y: T): Boolean = gteq(x, y) && !equiv(x, y)
+
+  /** Returns <code>true</code> iff <code>x</code> is equivalent to
+   *  <code>y</code> in the ordering.
+   */
+  def equiv(x: T, y: T): Boolean = lteq(x,y) && lteq(y,x)
+}