Next: Union-find sets
Up: Unordered collections
Previous: Set implementations
Index
In bag.diesel:
Bags are a specialization of unordered collections that
explicitly allow duplicates.
module Bag;
abstract class bag[T] isa unordered_collection[T],
- type parameter is covariant
bag[`S >= T];
abstract class bag_exactly[T] isa bag[T];
abstract class i_bag[T] isa bag[T], i_unordered_collection[T],
- type parameter is covariant
i_bag[`S >= T];
abstract class i_bag_exactly[T]
isa bag_exactly[T], i_unordered_collection_exactly[T], i_bag[T];
abstract class m_bag[T] isa bag_exactly[T], m_unordered_collection[T];
extend class m_bag[`T <= comparable[T]] isa removable_collection[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.
class list_bag[T] isa m_bag[T];
fun new_list_bag[T]():list_bag[T];
In hash-bag.diesel:
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.
module HashBag;
class hash_bag[T <= hashable[T]] isa m_bag[T];
fun set_length(:hash_bag[`T], :int):void;
Hash-bags support iterating through runs of elements as a
group, using do_with_counts
. Each distinct element value is
visited only once.
fun do_with_counts(m:hash_bag[`T], c:&(T,int):void):void;
fun add_count(m:hash_bag[`T], x:T, count:int):void;
fun add_nonmember_count(m:hash_bag[`T], x:T, count:int):void;
fun new_hash_bag[T <= hashable[T]]():hash_bag[T];
Next: Union-find sets
Up: Unordered collections
Previous: Set implementations
Index
Cecil/Vortex Project