Bags

In bag.diesel:

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

extend module Stdlib;

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];

end module Bag;

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.

extend module Stdlib;

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];

end module HashBag;