Set implementations

let var warn_for_list_sets_longer_than:int;
template object list_set[T <= comparable[T]] isa m_set[T];
  method collection_name(@:list_set[`T]):string;
  method add(m@:list_set[`T], x:T):void;
  method add_nonmember(m@:list_set[`T], x:T):void;
  method new_list_set[T <= comparable[T]]():list_set[T];
  method copy_empty(c@:list_set[`T]):list_set[T];

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

template object chained_hash_set[T <= hashable[T]] isa m_set[T];
method collection_name(@:chained_hash_set[`T]):string;
method do(t@:chained_hash_set[`T], c:&(T):void):void;
method do_allowing_updates(t@:chained_hash_set[`T], c:&(T):void):void;
method includes(t@:chained_hash_set[`T], x:T):bool;
method add(t@:chained_hash_set[`T], x:T):void;
method add_nonmember(t@:chained_hash_set[`T], x:T):void;
method remove(t@:chained_hash_set[`T], x:T, if_absent:&():void):void;
method remove_if(t@:chained_hash_set[`T], pred:&(T):bool):int;
method remove_any(t@:chained_hash_set[`T], if_empty:&():`S):T|S;
method remove_all(t@:chained_hash_set[`T]):void;
method union(m1@:chained_hash_set[`T], m2@:chained_hash_set[T]):m_set[T];
method intersection(m1@:chained_hash_set[`T],
                    m2@:chained_hash_set[T]):m_set[T];
let var default_chained_hash_set_size:int;
method new_chained_hash_set[T <= hashable[T]]():chained_hash_set[T];
method new_chained_hash_set[T <= hashable[T]](size:int):chained_hash_set[T];
method copy_empty(c@:chained_hash_set[`T]):chained_hash_set[T];

chained_hash_set is an m_set implementation using a closed hashing algorithm. Set elements must be hashable. In hash-set.cecil:

template object hash_set[T <= hashable[T]] isa m_set[T], open_table[T];
method collection_name(@:hash_set[`T]):string;
method do(t@:hash_set[`T], c:&(T):void):void;
method do_allowing_updates(t@:hash_set[`T], c:&(T):void):void;
method includes(t@:hash_set[`T], x:T):bool;
method add(t@:hash_set[`T], x:T):void;
method remove(t@:hash_set[`T], x:T, if_absent:&():void):void;
method remove_if(t@:hash_set[`T], pred:&(T):bool):int;
method remove_any(t@:hash_set[`T], if_empty:&():`S):T|S;
method remove_all(t@:hash_set[`T]):void;
method union(m1@:hash_set[`T], m2@:hash_set[T]):m_set[T];
method intersection(m1@:hash_set[`T], m2@:hash_set[T]):m_set[T];
method new_hash_set[T <= hashable[T]]():hash_set[T];
method new_hash_set[T <= hashable[T]](size:int):hash_set[T];
method copy_empty(c@:hash_set[`T]):hash_set[T];
method copy(t@:hash_set[`T]):hash_set[T];
method copy_as_hash_set(src:collection[`T<=hashable[T]]
                        )  :hash_set[T];
method copy_as_hash_set[T](src:collection[`T<=hashable[T]]
                           )  :hash_set[T];
method copy_as_hash_set[T](src   :collection[`T<=hashable[T]],
                           length:int
                           )     :hash_set[T];
method new_hash_set_from(src:collection[`Src],
                         cl :&(Src):`Res<=hashable[Res]
                         )  :hash_set[Res];
method new_hash_set_from[Res<=hashable[Res]](src:collection[`Src],
                                             cl :&(Src):Res
                                             )  :hash_set[Res];
method new_hash_set_from[Res<=hashable[Res]](src   :collection[`Src],
                                             length:int,
                                             cl    :&(Src):Res
                                             )     :hash_set[Res];

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.

In small-set.cecil:

concrete object empty_big_set[T <= hashable[T]]
        isa i_unordered_collection[T],
            functionally_extensible_removable_collection[T];
  method length(@:empty_big_set[`T]):int;
  method do(@:empty_big_set[`T], c:&(T):void):void;
  method includes(@:empty_big_set[`T], x:T):bool;
  method add_functional(@:empty_big_set[`T], x:T):m_set[T];
  method remove(@:empty_big_set[`T], x:T, if_absent:&():void):void;
  method remove_any(@:empty_big_set[`T], if_empty:&():`S):T|S;
  method remove_all(@:empty_big_set[`T]):void;
  method copy_empty(t@:empty_big_set[`T]):empty_big_set[T];
  method copy(t@:empty_big_set[`T]):empty_big_set[T];
  method print_string(t@:empty_big_set[`T]):string;
  method collection_name(@:empty_big_set[`T]):string;
template object small_set[T <= hashable[T]] isa m_set[T];
method collection_name(@:small_set[`T]):string;
method length(t@:small_set[`T]):int;
method is_empty(t@:small_set[`T]):bool;
method includes(t@:small_set[`T], x:T):bool;
method add_nonmember(t@:small_set[`T], x:T):void;
method remove(t@:small_set[`T], x:T, if_absent:&():void):void;
method remove_any(t@:small_set[`T], if_empty:&():`S):T|S;
method remove_all(t@:small_set[`T]):void;
method shrink_set(t@:small_set[`T]):void;
method do(t@:small_set[`T], c:&(T):void):void;
method new_small_set[T <= hashable[T]]():small_set[T];
method copy_empty(t@:small_set[`T]):small_set[T];
method copy(t@:small_set[`T]):small_set[T];

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. In bit-set.cecil:

abstract object bit_set[T <= comparable[T]] isa m_set[T], hashable[bit_set[T]];
  signature element_to_index(bit_set[`T], T):int;
  signature index_to_element(bit_set[`T], int):T;
  signature new_bit_set(bit_set[`T], bit_vector, cached_length:int):bit_set[T];
  method copy(a@:`S <= bit_set[`T]):R
                        where signature new_bit_set(S, bit_vector, int):`R;
  method union(a@:`S <= bit_set[`T], b@:`S <= bit_set[`T]):R
                        where signature new_bit_set(S, bit_vector, int):`R;
  method intersection(a@:`S <= bit_set[`T], b@:`S <= bit_set[`T]):R
                        where signature new_bit_set(S, bit_vector, int):`R;
  method difference(a@:`S <= bit_set[`T], b@:`S <= bit_set[`T]):R
                        where signature new_bit_set(S, bit_vector, int):`R;
  method union_in_place(a@:`S <= bit_set[`T], b@:`S <= bit_set[`T]):void;
  method intersection_in_place(a@:`S <= bit_set[`T], b@:`S <= bit_set[`T]
                               ):void;
  method difference_in_place(a@:`S <= bit_set[`T], b@:`S <= bit_set[`T]):void;
  method is_empty(a@:bit_set[`T]):bool;
  method =(a@:bit_set[`T], b@:bit_set[T]):bool;
  method hash(c@:bit_set[`T], range:int):int;
  method remove(a@:bit_set[`T], elem:T, if_absent:&():void):void;
  method includes(a@:bit_set[`T], elem:T):bool;
  method includes_id(a@:bit_set[`T], idx:int):bool;
  method includes_all(a@:bit_set[`T], b@:bit_set[T]):bool;
  method add(a@:bit_set[`T], elem:T):void;
  method add_id(a@:bit_set[`T], idx:int):void;
  method add_all(a@:bit_set[`T], b@:bit_set[T]):void;
  method do(a@:bit_set[`T], cl:&(T):void):void;
  method is_disjoint(m1@:bit_set[`T], m2@:bit_set[T]):bool;
  method remove_any(a@:bit_set[`T], if_empty:&():`S):T|S;
  method remove_all(a@:bit_set[`T]):void;
  method length(a@:bit_set[`T]):int;
  method collection_name(@:bit_set[`T]):string;
abstract object caching_bit_set_element[T <= hashable[T]]
                                isa hashable[caching_bit_set_element[T]]
                                - type parameter is contravariant:
                                subtypes caching_bit_set_element[`S <= T];
  signature id_manager(caching_bit_set_element[`T]
                       ):bit_set_id_manager[caching_bit_set_element[T]];
  var field id_num(t@:caching_bit_set_element[`T]):int;
  method reset_id_num(t@:caching_bit_set_element[`T]):void;
abstract object caching_bit_set[T <= caching_bit_set_element[T]] isa bit_set[T];
  signature id_manager(caching_bit_set[`T]):bit_set_id_manager[T];
  method element_to_index(t@:caching_bit_set[`T], elem:T):int;
  method index_to_element(t@:caching_bit_set[`T], idx:int):T;
abstract object caching_bit_set_element_2[T <= hashable[T]]
                                isa hashable[caching_bit_set_element_2[T]]
                                - type parameter is contravariant:
                                subtypes caching_bit_set_element_2[`S <= T];
  signature id_manager_2(caching_bit_set_element_2[`T]
                         ):bit_set_id_manager[caching_bit_set_element_2[T]];
  var field id_num_2(t@:caching_bit_set_element_2[`T]):int;
  method reset_id_num_2(t@:caching_bit_set_element_2[`T]):void;
abstract object caching_bit_set_2[T <= caching_bit_set_element_2[T]]
                                isa bit_set[T];
  signature id_manager(caching_bit_set_2[`T]):bit_set_id_manager[T];
  method element_to_index(t@:caching_bit_set_2[`T], elem:T):int;
  method index_to_element(t@:caching_bit_set_2[`T], idx:int):T;
template object bit_set_id_manager[T <= hashable[T]];
  method element_to_index(t@:bit_set_id_manager[`T], elem:T):int;
  method index_to_element(t@:bit_set_id_manager[`T], idx:int):T;
  method remove_element(t@:bit_set_id_manager[`T], elem:T, idx:int):void;
  method reset_id_manager(t@:bit_set_id_manager[`T]):void;
  method length(t@:bit_set_id_manager[`T]):int;
  method new_bit_set_id_manager[T <= hashable[T]]()
                :bit_set_id_manager[T];
abstract object hashing_bit_set[T <= hashable[T]] isa bit_set[T];
  signature id_manager(hashing_bit_set[`T]
                       ):hashing_bit_set_id_manager[T];
  method element_to_index(t@:hashing_bit_set[`T], elem:T):int;
  method index_to_element(t@:hashing_bit_set[`T], idx:int):T;
template object hashing_bit_set_id_manager[T <= hashable[T]]
                                                isa bit_set_id_manager[T];
  method element_to_index(t@:hashing_bit_set_id_manager[`T], elem:T):int;
  method remove_element(t@:hashing_bit_set_id_manager[`T], elem:T, idx:int
                        ):void;
  method reset_id_manager(t@:hashing_bit_set_id_manager[`T]):void;
  method new_hashing_bit_set_id_manager[T <= hashable[T]]()
                :hashing_bit_set_id_manager[T];

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.

In bounded-set.cecil:

template object bounded_set[T <= hashable[T]] isa m_set[T];
signature big_set(bounded_set[`T]):set[T];
method collection_name(@:bounded_set[`T]):string;
method print_string(t@:bounded_set[`T]):string;
method length(t@:bounded_set[`T]):int;
method is_empty(t@:bounded_set[`T]):bool;
method includes(t@:bounded_set[`T], x:T):bool;
method add_nonmember(t@:bounded_set[`T], x:T):void;
method add_all(t@:bounded_set[`T], xs:collection[T]):void;
method remove(t@:bounded_set[`T], x:T, if_absent:&():void):void;
method remove_any(t@:bounded_set[`T], if_empty:&():`S):T|S;
method remove_all(t@:bounded_set[`T]):void;
method do(t@:bounded_set[`T], c:&(T):void):void;
method new_bounded_set[T <= hashable[T]]():bounded_set[T];
method copy_empty(t@:bounded_set[`T]):bounded_set[T];
method copy(t@:bounded_set[`T]):bounded_set[T];

An implementation of m_set that is efficient and correct when there are fewer than three elements, but approximates larger sets by a ``big set.'' This implementation is useful when the set needs to be efficient, and it is OK to approximate a smaller set by a larger one.