1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2009, 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 representation
* 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>reflexive: <code>lteq(x, x) == true</code>, for any <code>x</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] {
outer =>
/** 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)
def reverse : PartialOrdering[T] = new PartialOrdering[T]{
override def reverse = outer;
def lteq(x : T, y : T) = outer.lteq(y, x);
}
}
|
