Bags

In bag.cecil:

abstract object bag[T] isa unordered_collection[T];
extend type bag[`T] subtypes bag[`S >= T];
signature copy(bag[`T]):bag[T];
abstract object i_bag[T] isa bag[T], i_unordered_collection[T];
signature copy(i_bag[`T]):i_bag[T];
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];

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

template object list_bag[T] isa m_bag[T];
  method collection_name(@:list_bag[`T]):string;
  method length(m@:list_bag[`T]):int;
  method is_empty(m@:list_bag[`T]):bool;
  method do(m@:list_bag[`T], c:&(T):void):void;
  method add(m@:list_bag[`T], x:T):void;
  method remove(m@:list_bag[`T <= comparable[T]], x:T,
                if_absent:&():void):void;
  method remove_any(m@:list_bag[`T], if_empty:&():`S):T|S;
  method remove_if(m@:list_bag[`T], pred:&(T):bool):int;
  method remove_all(m@:list_bag[`T]):void;
  method new_list_bag[T]():list_bag[T];
  method copy_empty(c@:list_bag[`T]):list_bag[T];
  method as_ordered_collection(c@:list_bag[`T]):m_list[T];

The list_bag class is a concrete implementation of the mutable bag abstraction, using a linked list as the core representation. The new_list_bag method is the ``constructor'' for this data structure.

template object hash_bag[T <= hashable[T]] isa m_bag[T];
  var field length(@:hash_bag[`T]):int;
  method collection_name(@:hash_bag[`T]):string;
  method =(m1@:hash_bag[`T], m2@:hash_bag[T]):bool;
  method is_empty(m@:hash_bag[`T]):bool;

The hash_bag class is a concrete implementation of the mutable bag abstraction, using a hash table mapping bag elements to an occurrence count. new_hash_bag method is the ``constructor'' for this data structure.

  method do_with_counts(m@:hash_bag[`T], c:&(T,int):void):void;
  method do(m@:hash_bag[`T], c:&(T):void):void;
  method do_allowing_updates(m@:hash_bag[`T], c:&(T):void):void;
  method includes(m@:hash_bag[`T], x:T):bool;
  method includes_some(m@:hash_bag[`T], test:&(T):bool):bool;
  method count(m@:hash_bag[`T], x:T):int;
  method count_pred(m@:hash_bag[`T], test:&(T):bool):int;
  method find(m@:hash_bag[`T], test:&(T):bool, if_absent:&():`S):T|S;
  method every(m@:hash_bag[`T], test:&(T):bool):bool;
  method any(m@:hash_bag[`T], test:&(T):bool):bool;
  method as_list_set(m@:hash_bag[`T]):m_set[T];
  method union(m1@:hash_bag[`T], m2@:hash_bag[T]):hash_bag[T];
  method intersection(m1@:hash_bag[`T], m2@:hash_bag[T]):hash_bag[T];
  method difference(m1@:hash_bag[`T], m2@:hash_bag[T]):hash_bag[T];
  method is_disjoint(m1@:hash_bag[`T], m2@:hash_bag[T]):bool;
  method is_subset(m1@:hash_bag[`T], m2@:hash_bag[T]):bool;
  method add_count(m@:hash_bag[`T], x:T, count:int):void;
  method add_nonmember_count(m@:hash_bag[`T], x:T, count:int):void;
  method add(m@:hash_bag[`T], x:T):void;
  method add_nonmember(m@:hash_bag[`T], x:T):void;
  method remove(m@:hash_bag[`T], x:T, if_absent:&():void):void;
  method remove_if(m@:hash_bag[`T], pred:&(T):bool):int;
  method remove_all(m@:hash_bag[`T]):void;
  method new_hash_bag[T <= hashable[T]]():hash_bag[T];
  method copy(c@:hash_bag[`T]):hash_bag[T];
  method copy_empty(c@:hash_bag[`T]):hash_bag[T];

Hash-bags support iterating through runs of elements as a group, using do_with_counts. Each distinct element value is visited only once.