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

-- Extensible / removable collections

----------
-- Removable collections
----------

(--DOC
  A `removable_collection' supports in-place removal of elements. The `remove'
  function removes one element equal to its second argument,
  or raises an error if not found (also defined is a variation that
  takes a closure to handle the not-found  case). The `remove_if'
  function removes all elements that satisfy the test, and
  returns the number of elements removed. The `remove_any'
  function removes and returns a single arbitrary element of the collection
  or raises an error if the collection is empty (again, a variation on
  `remove_any' passes a closure to handle this case in a client-defined
  manner). The `remove_all' function removes all elements of the
  collection. Subclasses need to implement these functions; a default
  `remove_all' is provided, but it is likely that subclasses can provide a much
  more efficient implementation.
--)

abstract object removable_collection[T] isa collection[T];

--DOCSKIP avoid predicate complications in manual
predicate empty_removable_collection[T] isa removable_collection[T],
				            empty_collection[T];
predicate non_empty_removable_collection[T] isa removable_collection[T],
				                non_empty_collection[T];
divide removable_collection[T] into empty_removable_collection[T],
			            non_empty_removable_collection[T];
--DOCENDSKIP

signature remove(removable_collection[`T], x:T, if_absent:&():void):void;
(-- implementations check this explicitly already; predicates too slow
implementation remove(c@:empty_removable_collection[`T], x:T,
		      if_absent:&():void):void {
    eval(if_absent);
}
--)
method remove(c@:removable_collection[`T], x:T):void (** no_inline **) {
    remove(c, x, { error("item not found") });
}

method remove_if(c@:removable_collection[`T], pred:&(T):bool):int {
    let var count:int := 0;
    c.do_allowing_updates(&(x:T){
	if(eval(pred, x), {
	    c.remove(x);
	    count := count + 1;
	});
    });
    count }

signature remove_any(removable_collection[`T], if_empty:&():`S):T|S;
(-- implementations check this explicitly already; predicates too slow
implementation remove_any(c@:empty_removable_collection[`T],
			  if_empty:&():`S):T|S {
    eval(if_empty) }
--)
method remove_any(c@:removable_collection[`T]):T (** no_inline **) {
    remove_any(c, { error("removing from an empty collection") }) }

method remove_all(c@:removable_collection[`T]):void {
    loop({
	c.remove_any({ ^ });
    });
}


----------
-- Functionally extensible collections
----------

(--DOC
  The `functionally_extensible_collection' class generalizes collections that
  are extensible in place (i.e., `add' mutates) and those that are extensible,
  but not in place (i.e., `add' returns a new collection).  The
  `add_functional' operation adds an element to the collection (in
  some unspecified location), returning a collection with the element
  added. This returned collection may either be the receiver
  collection (if the `add' is performed in-place) or some new
  collection.  Since the receiver collection may or may not be changed
  and may or may not contain the new element,  the caller should use
  the returned value (and should not use the argument to
  `add_functional' after the call).

  The weird name of the collection is intended to suggest a functional
  language where `add' returns a new collection.
--)

abstract object functionally_extensible_collection[T] isa collection[T];
  signature add_functional(functionally_extensible_collection[`T], x:T
			   ):functionally_extensible_collection[T];


--DOC A blend of `functionally_extensible_collection' and
--DOC `removable_collection'.
abstract object functionally_extensible_removable_collection[T]
	isa removable_collection[T], functionally_extensible_collection[T];
  signature add_functional(functionally_extensible_removable_collection[`T],x:T
			   ):functionally_extensible_removable_collection[T];
  signature copy(functionally_extensible_removable_collection[`T]
		 ):functionally_extensible_removable_collection[T];


----------
-- Extensible collections
----------

(-- DOC
  An `extensible_collection' supports adding new elements in-place, as well as
  removing elements. The `add' function adds a new element to the collection
  (in some unspecified place). The `add_nonmember' function can be used if the
  element being added is known not to be in the collection already. Its
  effect is that same as that of `add' for collections which allow duplicates,
  but it may be faster than a generic `add' for collections that do not permit
  duplicates (such as `set' and its subclasses). The `add_all' and
  `add_all_nonmember' functions support adding all the elements of some other
  collection to the receiver collection.
--)

abstract object extensible_collection[T]
	isa functionally_extensible_removable_collection[T];
signature add(extensible_collection[`T], x:T):void;
method add_nonmember(c@:extensible_collection[`T], x:T):void { c.add(x); }
method add_all(c@:extensible_collection[`T], xs:collection[T]):void {
    xs.do(&(x:T){ c.add(x) });
}
method add_all_nonmember(c@:extensible_collection[`T], xs:collection[T]):void {
    xs.do(&(x:T){ c.add_nonmember(x) });
}
method add_functional(m@:extensible_collection[`T], x:T
		      ):extensible_collection[T] {
    m.add(x);
    m }


----------
-- Extensible ordered_collection
----------

--DOC Extensible ordered collections can have their first and last
--DOC elements removed, as well as the removing and adding behavior of
--DOC extensible collections.

abstract object extensible_ordered[T]
		isa extensible_collection[T], ordered_collection[T];

--DOCSKIP avoid predicates in manual
predicate empty_extensible_ordered[T] isa extensible_ordered[T],
				          empty_collection[T];
predicate non_empty_extensible_ordered[T] isa extensible_ordered[T],
				              non_empty_collection[T];
divide extensible_ordered[T] into empty_extensible_ordered[T],
				  non_empty_extensible_ordered[T];
--DOCENDSKIP

signature remove_first(extensible_ordered[`T], if_empty:&():`S):T|S;
(-- implementations check this explicitly already; predicates too slow
implementation remove_first(c@:empty_extensible_ordered[`T],
			    if_empty:&():`S):T|S {
    eval(if_empty) }
--)
method remove_first(c@:extensible_ordered[`T]):T (** no_inline **) {
    remove_first(c, { error("removing from an empty collection") }) }

signature remove_last(extensible_ordered[`T], if_empty:&():`S):T|S;
(-- implementations check this explicitly already; predicates too slow
implementation remove_last(c@:empty_extensible_ordered[`T],
			   if_empty:&():`S):T|S {
    eval(if_empty) }
--)
method remove_last(c@:extensible_ordered[`T]):T (** no_inline **) {
    remove_last(c, { error("removing from an empty collection") }) }

-- default remove_any implementation
method remove_any(c@:extensible_ordered[`T], if_empty:&():`S):T|S {
    c.remove_first(if_empty) }


----------
-- Extensible sequence
----------

--DOC Extensible sequences also allow elements to be added to the
--DOC front or end of the sequence.

abstract object extensible_sequence[T] isa extensible_ordered[T], sequence[T];

signature add_first(extensible_sequence[`T], x:T):void;
signature add_last (extensible_sequence[`T], x:T):void;

-- default add implementation
method add(c@:extensible_sequence[`T], x:T):void { c.add_last(x); }

method add_all_last(s@:extensible_sequence[`T], c@:ordered_collection[T]):void{
    c.do(&(e:T){ s.add_last(e); });
}