Next: Bags
Up: Unordered collections
Previous: Sets
Index
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];
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.
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];
In chained-hash-set.diesel:
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.
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];
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.
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;
Next: Bags
Up: Unordered collections
Previous: Sets
Index
Cecil/Vortex Project