Next: Union-find sets
Up: Unordered collections
Previous: Set implementations
Index
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.
Next: Union-find sets
Up: Unordered collections
Previous: Set implementations
Index
Cecil/Vortex Project