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

--DOC Bags are a specialization of unordered collections that
--DOC explicitly allow duplicates.

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

signature copy(bag[`T]):bag[T];


-- Immutable bag

abstract object i_bag[T] isa bag[T], i_unordered_collection[T];
signature copy(i_bag[`T]):i_bag[T];


-- Mutable bag

abstract object m_bag[T] isa bag[T], m_unordered_collection[T];
extend m_bag[`T <= comparable[T]] isa removable_collection[T];
signature copy(m_bag[`T]):m_bag[T];


--DOC The `list_bag' class is a concrete implementation of the mutable
--DOC bag abstraction, using a linked list as the core representation. The
--DOC `new_list_bag' method is the "constructor" for this data structure.
template object list_bag[T] isa m_bag[T];
  private field elems(@:list_bag[`T]):m_list[T] := new_m_list[T]();
  method collection_name(@:list_bag[`T]):string { "list_bag" }

  method length(m@:list_bag[`T]):int { length(m.elems) }
  method is_empty(m@:list_bag[`T]):bool { is_empty(m.elems) }
  method do(m@:list_bag[`T], c:&(T):void):void { do(m.elems, c); }

  method add(m@:list_bag[`T], x:T):void { m.elems.add_last(x); }

  method remove(m@:list_bag[`T <= comparable[T]], x:T,
		if_absent:&():void):void {
      remove(m.elems, x, if_absent); }
  method remove_any(m@:list_bag[`T], if_empty:&():`S):T|S {
      remove_any(m.elems, if_empty) }
  method remove_if(m@:list_bag[`T], pred:&(T):bool):int {
      remove_if(m.elems, pred); }
  method remove_all(m@:list_bag[`T]):void {
      remove_all(m.elems); }

  method new_list_bag[T]():list_bag[T] { concrete object isa list_bag[T] }

  method copy_empty(c@:list_bag[`T]):list_bag[T] { new_list_bag[T]() }

  method as_ordered_collection(c@:list_bag[`T]):m_list[T] { c.elems }