From 4ec9c8abe1b2bb8aff74edaf954453070bef89fd Mon Sep 17 00:00:00 2001 From: Geoffrey Washburn Date: Thu, 3 Apr 2008 14:16:41 +0000 Subject: 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". --- src/library/scala/Equiv.scala | 27 ++++++++++--- src/library/scala/Ordering.scala | 72 +++++++++++++++++++++++++++++---- src/library/scala/PartialOrdering.scala | 62 ++++++++++++++++++++++++++++ 3 files changed, 148 insertions(+), 13 deletions(-) create mode 100644 src/library/scala/PartialOrdering.scala 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 equivalence + * relation is a binary relation on a type. This relation is exposed as + * the equiv method of the Equiv trait. This + * relation must be: + * + * + * @author Geoffrey Washburn + * @version 1.0, 2008-04-03 */ trait Equiv[T] { /** Returns true iff x is equivalent to - * y. The implementation should be equivalence - * relation: reflexive, transitive, symmetric. + * y. */ 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 total ordering + * is a binary relation on a type T that is also a partial + * ordering on values of type T. This relation is exposed as + * the compare method of the Ordering trait. + * This relation must be: + * + * + * @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 x comes before + * y in the ordering, returns 0 iff x + * is the same in the ordering as y, and returns a + * positive number iff x comes after + * y 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 true iff x comes before + * y in the ordering. + */ + override def lteq(x: T, y: T): Boolean = compare(x, y) <= 0 + + /** Returns true iff y comes before + * x in the ordering. + */ + override def gteq(x: T, y: T): Boolean = compare(x, y) >= 0 + + /** Returns true iff x comes before + * y in the ordering and is not the same as y. + */ + override def lt(x: T, y: T): Boolean = compare(x, y) < 0 + + /** Returns true iff y comes before + * x in the ordering and is not the same as x. + */ + override def gt(x: T, y: T): Boolean = compare(x, y) > 0 + + /** Returns true iff x is equivalent to + * y 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 partial ordering + * is a binary relation on a type T that is also an equivalence + * relation on values of type T. This relation is exposed as + * the lteq method of the PartialOrdering trait. + * This relation must be: + * + * + * @author Geoffrey Washburn + * @version 1.0, 2008-04-0-3 + */ + +trait PartialOrdering[T] extends Equiv[T] { + /** Returns true iff x comes before + * y in the ordering. + */ + def lteq(x: T, y: T): Boolean + + /** Returns true iff y comes before + * x in the ordering. + */ + def gteq(x: T, y: T): Boolean = lteq(y, x) + + /** Returns true iff x comes before + * y in the ordering and is not the same as y. + */ + def lt(x: T, y: T): Boolean = lteq(x, y) && !equiv(x, y) + + /** Returns true iff y comes before + * x in the ordering and is not the same as x. + */ + def gt(x: T, y: T): Boolean = gteq(x, y) && !equiv(x, y) + + /** Returns true iff x is equivalent to + * y in the ordering. + */ + def equiv(x: T, y: T): Boolean = lteq(x,y) && lteq(y,x) +} -- cgit v1.2.3