-- Copyright 1993-1998, by the Cecil Project
-- Department of Computer Science and Engineering, University of Washington
-- See the LICENSE file for license information.

-- Comparable, PartiallyOrdered, Ordered, and Hashable


(--DOC
  Comparable objects can be tested for equality. This equality should
  be an abstract notion of equality which compares two abstract
  values, as appropriate to the kind of data types being compared. It
  is not a low-level representation equality such as `==', which, like
  Lisp's `eq', tests "pointer equality."
  By default, operations that compare elements use `=' rather than `==',
  unless the operation's name includes `identity_'.
--)
module Comparable {
  abstract object comparable[T <= comparable[T]];
    extend type comparable[`T] subtypes comparable[`S <= T];

  -- define this for specific kind of comparisons
  --DOCSHORT equal (abstract) values?
  signature =(x1:`T <= comparable[T], x2:`T <= comparable[T]):bool;

  --DOCSHORT not `='
  method !=(x1@:`T <= comparable[T], x2@:`T <= comparable[T]):bool {
      not(x1 = x2) }

  precedence =, != non_associative above &;
};


(--DOC
  Partially ordered objects are comparable objects that also can be
  compared for being less than one another, and other
  combinations.  Since they form only a partial order,
  `not(a <  b)' does not imply `a >= b'.
--)
module PartiallyOrdered extends Comparable {
  abstract object partially_ordered[T <= partially_ordered[T]]
	isa comparable[T];
    extend type partially_ordered[`T] subtypes partially_ordered[`S <= T];

  --DOCSHORT x1 ordered below x2?
  signature <(x1:`T <= partially_ordered[T],
	      x2:`T <= partially_ordered[T]):bool;

  --DOCSHORT `<' or `='
  method <=(x1@:`T <= partially_ordered[T],
	    x2@:`T <= partially_ordered[T]):bool {
      x1 = x2 | { x1 < x2 } }
  --DOCSHORT x2 `<' x1?
  method > (x1@:`T <= partially_ordered[T],
	    x2@:`T <= partially_ordered[T]):bool {
      x2 < x1 }
  --DOCSHORT `>' or `='
  method >=(x1@:`T <= partially_ordered[T],
	    x2@:`T <= partially_ordered[T]):bool {
      x2 <= x1 }

  precedence <, <=, >=, > non_associative above & with =;
};


(--DOC
  Ordered objects refine partially-ordered objects by imposing a total
  order, i.e., `not(a < b)' does imply `a >= b'. The `min' and `max'
  functions are defined for all ordered objects. The `compare' function
  implements a three-way comparison, invoking one of its argument closures
  depending on how the first argument compares to its second
  argument.  By default, concrete subclasses provide implementations of
  `=' and `<', and `compare' is provided by default in terms of those
  primitives.  Alternatively, a concrete subclass can inherit from
  `ordered_using_compare', which assumes the subclass will provide an
  implementation of `compare' and defines `=' and `<' in terms of it.
--)
module Ordered extends PartiallyOrdered {
  abstract object ordered[T <= ordered[T]] isa partially_ordered[T];
    extend type ordered[`T] subtypes ordered[`S <= T];

  -- override these implementations to exploit ordering to be faster
  method <=(x1@:`T <= ordered[T], x2@:`T <= ordered[T]):bool { not(x1 > x2) }
  method >=(x1@:`T <= ordered[T], x2@:`T <= ordered[T]):bool { not(x1 < x2) }

  method min (x1:`T <= ordered[T], x2:`T <= ordered[T]):T {
      if(x1 < x2, { x1 }, { x2 }) }
  method max (x1:`T <= ordered[T], x2:`T <= ordered[T]):T {
      if(x1 > x2, { x1 }, { x2 }) }

  -- provide default implementation of compare in terms of = and <
  method compare(x1@:`T <= ordered[T], x2@:`T <= ordered[T],
		 if_less:&():`S, if_equal:&():`S, if_greater:&():`S
		 ):S (** recursive_customization **) {
      if(x1 = x2, if_equal, { if(x1 < x2, if_less, if_greater) }) }
};

module OrderedUsingCompare extends Ordered {
  abstract object ordered_using_compare[T <= ordered[T]] isa ordered[T];
   extend type ordered_using_compare[`T] subtypes ordered_using_compare[`S<=T];

  -- provide default implementations of = and < in terms of compare
  method =(x1@:`T <= ordered_using_compare[T],
	   x2@:`T <= ordered_using_compare[T]):bool {
      compare(x1, x2, { false }, { true }, { false }) }
  method <(x1@:`T <= ordered_using_compare[T],
	   x2@:`T <= ordered_using_compare[T]):bool {
      compare(x1, x2, { true }, { false }, { false }) }

  method compare(x1@:`T <= ordered_using_compare[T],
		 x2@:`T <= ordered_using_compare[T],
		 if_less:&():`S, if_equal:&():`S, if_greater:&():`S
		 ):S {
      error("subclasses should override this method") }
};


(--DOC
  A hashable object is a comparable (equality-testable) object
  that also supports a `hash' function. `hash(x, r)' returns an
  integer in the range `[0..r-1]', subject to the constraint that
  if `a = b', then `hash(a, r) = hash(b, r)'.
--)
module Hashable extends Comparable {
  abstract object hashable[T <= hashable[T]] isa comparable[T];
    extend type hashable[`T] subtypes hashable[`S <= T];

  -- a = b must imply a.hash = b.hash
  signature hash(hashable[`T], range:int):int;
};


(--DOC
  An ordered_hashable object is both hashable and ordered.
--)
module HashableOrdered extends Hashable, Ordered {
  abstract object ordered_hashable[T <= ordered_hashable[T]] isa ordered[T],
								 hashable[T];
    extend type ordered_hashable[`T] subtypes ordered_hashable[`S <= T];
};