← immutable hash dictionary ideal • runtime • elements • base hash set hash set →
Base class for the dictionary backed by a linked list.
public abstract class base hash set[readonly value element type]
implements readonly set[element type]
namespace parameters
protected class hash cell[readonly value element type]
protected integer the hash
protected var hash cell[element type] or null next
public overload hash cell(element type the value, integer the hash, hash cell[element type] or null next)
this • the value = the value
this • the hash = the hash
this • next = next
public overload hash cell(element type the value, integer the hash)
this(the value, the hash, missing • instance)
Wrapper of an array that implements on-demand resizing and copy-on-write semantics. The same set_state can be shared by multiple instances of base_hash_sets.
protected class set state[readonly value element type]
import ideal • machine • elements • array
Specifies whether this instance of set_state is writable. A single non-writable copy can be shared among multiple instances of base_hash_set.
var boolean writable
An array used to store the elements.
var array[hash cell[element type] or null] the buckets
Specifies how many elements are stored in this set_state. The size is less or equal to the_buckets.size.
var nonnegative size
Construct a dictionary state with an array of specified size.
overload set state(nonnegative initial size)
the buckets = array[hash cell[element type] or null] • new(initial size)
size = 0
Construct a dictionary state with a table of default size.
overload set state()
protected void clear()
if size != 0
size = 0
Make sure the array is of at least the specified size.
void reserve(nonnegative reserve size)
if the buckets • size >= reserve size
return
var new size : the buckets • size * 2
if new size < reserve size
new size = reserve size
the buckets = array[hash cell[element type] or null] • new(new size)
for var nonnegative i : 0; i < old buckets • size; i += 1
var bucket : old buckets[i]
while bucket is_not null
old next : bucket • next
bucket • next = the buckets[new index]
the buckets[new index] = bucket
bucket = old next
old buckets • scrub(0, old buckets • size)
protected nonnegative bucket index(integer hash)
index : ((hash % bucket size) + bucket size) % bucket size
assert index is nonnegative
return index
protected set state[element type] copy()
result : set state[element type] • new(the buckets • size)
for var nonnegative i : 0; i < the buckets • size; i += 1
var bucket : the buckets[i]
while bucket is_not null
new cell : hash cell[element type] • new(bucket • the value, bucket • the hash, result • the buckets[i])
result • the buckets[i] = new cell
bucket = bucket • next
result • size = this • size
return result
protected equivalence with hash[element type] equivalence
protected var set state[element type] state
protected overload base hash set(equivalence with hash[element type] equivalence)
this • equivalence = equivalence
this • state = set state[element type] • new()
protected overload base hash set(equivalence with hash[element type] equivalence, set state[element type] state)
this • equivalence = equivalence
this • state = state
The number of elements in the collection.
implement nonnegative size => state • size
Specifies whether the collection has zero elements.
implement boolean is empty => state • size == 0
Specifies whether the collection has more than zero elements. Shortcut for !is_empty.
implement boolean is not empty => state • size != 0
Enumerates elements in some collection-defined order. This method returns a snapshot of the collection state, so subsequent mutations of the collection do not cause changes in the returned list.
implement immutable list[element type] elements()
if is empty
return empty[element type] • new()
for var nonnegative i : 0; i < state • the buckets • size; i += 1
for var entry : state • the buckets[i]; entry is_not null; entry = entry • next
result • append(entry • the value)
return result • frozen copy()
implement immutable set[element type] frozen copy()
implement boolean contains(element type key)
assert key is_not null
hash : equivalence • hash(key)
for var entry : bucket; entry is_not null; entry = entry • next
if hash == entry • the hash && equivalence(key, entry • the value)
return true
return false
← immutable hash dictionary ideal • runtime • elements • base hash set hash set →