Set implementations

let var warn_for_list_sets_longer_than:int;

list_set is an implementation of m_set using a linked list as the core representation.

class list_set[T <= comparable[T]] isa m_set[T];
  fun new_list_set[T <= comparable[T]]():list_set[T];
  fun as_list_set(c:collection_exactly[`T <= comparable[T]]):m_set[T];

end module Set;

In hash-set.diesel:

An m_set implementation using an open hashing algorithm. Set elements must be hashable.

The new_[chained_]hash_set methods optionally take a max_size argument, which is the expected maximum size of the set; the initial size of all newly-created sets is 0. All hashing set implementations automatically resize if the set grows too large or small. Warning: the do_allowing_updates function on hash_set (and hash_table and hash_keyed_set, the other open-hash-table-based implementations) may not support more than one add (or store or fetch_or_init or any operation that increases the size of the collection) during the iteration, because they are blocked from resizing but they may need to resize to support multiple adds.

extend module Stdlib;

module HashSet;
class hash_set[T <= hashable[T]] isa m_set[T];
fun new_hash_set[T <= hashable[T]]():hash_set[T];
fun new_hash_set[T <= hashable[T]](size:int):hash_set[T];
fun copy_as_hash_set(src:collection[`T <= hashable[T]]):hash_set[T];
fun copy_as_hash_set[T](src:collection[`T <= hashable[T]]):hash_set[T];
fun copy_as_hash_set[T](src   :collection[`T <= hashable[T]],
                               length:int
                               )     :hash_set[T];
fun new_hash_set_from(src:collection[`Src],
                             cl :&(Src):`Res <= hashable[Res]
                             )  :hash_set[Res];
fun new_hash_set_from[Res <= hashable[Res]](src:collection[`Src],
                                                   cl :&(Src):Res
                                                   )  :hash_set[Res];
fun new_hash_set_from[Res <= hashable[Res]](src   :collection[`Src],
                                                   length:int,
                                                   cl    :&(Src):Res
                                                   )     :hash_set[Res];

end module HashSet;

In chained-hash-set.diesel:

extend module Stdlib;

module ChainedHashSet;

chained_hash_set is an m_set implementation using a closed hashing algorithm. Set elements must be hashable.

class chained_hash_set[T <= hashable[T]] isa m_set[T];
fun new_chained_hash_set[T <= hashable[T]]():chained_hash_set[T];
fun new_chained_hash_set[T <= hashable[T]](size:int):chained_hash_set[T];

end module ChainedHashSet;

In small-set.diesel:

An implementation of m_set that is space efficient when there are only a few elements, but scales well when there are a large number of elements. Elements of small sets are required to be hashable.

extend module Stdlib;

module SmallSet;
class small_set[T <= hashable[T]] isa m_set[T];
fun shrink_set(t:small_set[`T]):void;
fun new_small_set[T <= hashable[T]]():small_set[T];

end module SmallSet;

module AbsentSmallElement;
object absent_small_element;
  fun elem_present(:any):bool;

end module AbsentSmallElement;

In bit-set.diesel:

A bit_set is an abstract class for bit-vector-based set representations. Concrete subclasses of bit_set must provide the element_to_index and index_to_element functions mapping between elements and bit positions. If the elements store their own set indices as an id_num field, the interface provided by the caching_bit_set subclass can be used. If a separate table mapping elements to indices is needed, the hashing_bit_set subclass can be used.

Concrete subclasses must also provide implementations of new_bit_set to call the correct constructor.

extend module Stdlib;

module BitSet;
abstract class bit_set[T <= comparable[T]] isa m_set[T],
                                                      hashable[bit_set[T]];
  fun element_to_index(:bit_set[`T], :T):int;
  fun index_to_element(:bit_set[`T], :int):T;
  fun new_bit_set(:bit_set[`T], :bit_vector, cached_length:int
                         ):bit_set[T];
  fun union_in_place(a:`S <= bit_set[`T], b:`S <= bit_set[`T]):void;
  fun intersection_in_place(a:`S <= bit_set[`T],
                                   b:`S <= bit_set[`T]):void;
  fun difference_in_place(a:`S <= bit_set[`T],
                                 b:`S <= bit_set[`T]):void;
  fun includes_id(a:bit_set[`T], idx:int):bool;
  fun add_id(a:bit_set[`T], idx:int):void;
class bit_set_id_manager[T];
  fun allocate_index_for_element(t:bit_set_id_manager[`T], elem:T):int;
  fun lookup_element_for_index(t:bit_set_id_manager[`T], idx:int):T;
  fun remove_element(t:bit_set_id_manager[`T], elem:T, idx:int):void;
  fun reset_id_manager(t:bit_set_id_manager[`T]):void;
  fun new_bit_set_id_manager[T]():bit_set_id_manager[T];
abstract class hashing_bit_set[T <= hashable[T]] isa bit_set[T];
class hashing_bit_set_id_manager[T <= hashable[T]]
                                                isa bit_set_id_manager[T];
  fun lookup_index_for_element(t:hashing_bit_set_id_manager[`T],
                                      elem:T):int;
  fun new_hashing_bit_set_id_manager[T <= hashable[T]]()
     :hashing_bit_set_id_manager[T];
abstract class caching_bit_set[T <= caching_bit_set_element[T]]
                                isa bit_set[T];
  fun id_manager(:caching_bit_set[`T]):bit_set_id_manager[T];
abstract class caching_bit_set_element[T <= caching_bit_set_element[T]]
                                isa hashable[caching_bit_set_element[T]];
  fun elem_id_manager(:`T <= caching_bit_set_element[T]
                             ):bit_set_id_manager[T];
  var field id_num(t:`T <= caching_bit_set_element[T]):int;
  fun reset_id_num(t:`T <= caching_bit_set_element[T]):void;
abstract class caching_bit_set_2[T <= caching_bit_set_element_2[T]]
                                                                isa bit_set[T];
abstract class caching_bit_set_element_2[
                                        T <= caching_bit_set_element_2[T]]
                                isa hashable[caching_bit_set_element_2[T]];
  fun elem_id_manager_2(:`T <= caching_bit_set_element_2[T]
                               ):bit_set_id_manager[T];
  var field id_num_2(t:`T <= caching_bit_set_element_2[T]):int;
  fun reset_id_num_2(t:`T <= caching_bit_set_element_2[T]):void;

end module BitSet;