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

(--DOC
  An `unordered_collection' is a group of elements in no particular order.
  It supports collection operations such as `length', `is_empty', `do',
  `pick_any', `includes', `find', and `copy'.
--)

abstract object unordered_collection[T] isa collection[T];
  extend type unordered_collection[`T] subtypes unordered_collection[`S >= T];

  method count(c@:unordered_collection[`T <= comparable[T]], x:T):int {
      let var count:int := 0;
      do(c, &(e:T){ if(x = e, { count := count.succ; }); });
      count }

  --DOC If the elements of the collection are comparable, then so is
  --DOC the collection. Two such collections are equal (`=') if they have
  --DOC the same elements (with the same number of occurrences),
  --DOC independent of order. (By contrast, two ordered collections are
  --DOC equal only if they contain the same elements in the same order.)
  --DOC If the elements of the collection are hashable, then so is the
  --DOC collection.
  extend unordered_collection[`T <= comparable[T]]
		isa comparable[unordered_collection[T]];
  method =(c1@:unordered_collection[`T <= comparable[T]],
	   c2@:unordered_collection[T]):bool {
      c1 == c2 | {
          c1.length = c2.length & {
	  do(c1, &(x:T){ if(count(c1, x) != count(c2, x), { ^ false }); });
	  true } } }

  extend unordered_collection[`T <= hashable[T]]
		isa hashable[unordered_collection[T]];
  method hash(c@:unordered_collection[`T <= hashable[T]], range:int):int {
      let var h:int := 0;
      do(c, &(x:T){ h := h _bit_xor hash(x, range); });
      hash(h, range) }


--DOC Two refinements of `unordered_collection' indicate whether the
--DOC collection is known to be immutable (`i_unordered_collection') or
--DOC mutable (`m_unordered_collection').

(--DOC
  An immutable unordered collection of some type `T' is a subtype of any
  immutable unordered collection of a supertype of `T'. In contrast, a
  mutable unordered collection of a type `T' has no subtyping relation
  to a mutable unordered collection of a different type. Both kinds
  are subtypes or a generic unordered collection of `T' or transitively
  any supertype of `T'.
--)

abstract object i_unordered_collection[T] isa unordered_collection[T];
  extend type i_unordered_collection[`T]
  		subtypes i_unordered_collection[`S >= T];
  method copy(c@:i_unordered_collection[`T]):i_unordered_collection[T] { c }
  method copy_empty(c@:i_unordered_collection[`T]
		    ):i_unordered_collection[T] { c }


--DOC Mutable collections provide remove, add, and other operations of
--DOC `extensible_collection'. Method `copy_empty' always returns an
--DOC empty mutable collection with a type like that of its argument.
abstract object m_unordered_collection[T]
    	isa unordered_collection[T], extensible_collection[T];
  method copy(c@:m_unordered_collection[`T]):m_unordered_collection[T] {
      let copy:m_unordered_collection[T] := c.copy_empty;
      copy.add_all(c);
      copy }
  signature copy_empty(m_unordered_collection[`T]):m_unordered_collection[T];