← immutable list dictionary ideal • runtime • elements • base hash dictionary hash dictionary →
Base class for the dictionary backed by a linked list.
public abstract class base hash dictionary[readonly value key type, value value type]
implements readonly dictionary[key type, value type]
namespace parameters
protected class hash cell[readonly value key type, value value type]
implements dictionary • entry[key type, value type]
private key type the key
protected integer the key hash
private var value type the value
protected var hash cell[key type, value type] or null next
public overload hash cell(key type the key, integer the key hash, value type the value, hash cell[key type, value type] or null next)
this • the key = the key
this • the key hash = the key hash
this • the value = the value
this • next = next
public overload hash cell(key type the key, integer the key hash, value type the value)
this(the key, the key hash, the value, missing • instance)
override key type key()
return the key
override value type value()
return the value
protected void set value(value type new value)
this • the value = new value
Wrapper of an array that implements on-demand resizing and copy-on-write semantics. The same dictionary_state can be shared by multiple instances of base_hash_dictionarys.
protected class dictionary state[readonly value key type, value value type]
import ideal • machine • elements • array
Specifies whether this instance of dictionary_state is writable. A single non-writable copy can be shared among multiple instances of base_hash_dictionary.
var boolean writable
An array used to store the elements.
var array[hash cell[key type, value type] or null] the buckets
Specifies how many elements are stored in this dictionary_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 dictionary state(nonnegative initial size)
the buckets = array[hash cell[key type, value type] or null] • new(initial size)
size = 0
Construct a dictionary state with a table of default size.
overload dictionary 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[key type, value 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 dictionary state[key type, value type] copy()
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[key type, value type] • new(bucket • key, bucket • the key hash, bucket • value, result • the buckets[i])
result • the buckets[i] = new cell
bucket = bucket • next
result • size = this • size
return result
protected equivalence with hash[key type] equivalence
protected var dictionary state[key type, value type] state
protected overload base hash dictionary(equivalence with hash[key type] equivalence)
this • equivalence = equivalence
this • state = dictionary state[key type, value type] • new()
protected overload base hash dictionary(equivalence with hash[key type] equivalence, dictionary state[key type, value 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[dictionary • entry[key type, value type]] elements()
if is empty
return empty[dictionary • entry[key type, value 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(base dictionary entry[key type, value type] • new(entry))
return result • frozen copy()
implement immutable dictionary[key type, value type] frozen copy()
private hash cell[key type, value type] or null bucket(integer hash)
return state • the buckets[state • bucket index(hash)]
implement value type or null get(key type key)
assert key is_not null
hash : equivalence • hash(key)
for var entry : bucket(hash); entry is_not null; entry = entry • next
if hash == entry • the key hash && equivalence(key, entry • key)
return entry • value
return missing • instance
implement boolean contains key(key type key)
assert key is_not null
hash : equivalence • hash(key)
for var entry : bucket(hash); entry is_not null; entry = entry • next
if hash == entry • the key hash && equivalence(key, entry • key)
return true
return false
implement immutable set[key type] keys()
if is empty
pass
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 • add(entry • key)
return result • frozen copy()
implement readonly collection[value type] values()
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 • value)
return result • frozen copy()
private string debug display()
var string s : ""
for var nonnegative i : 0; i < state • the buckets • size; i += 1
s = s ++ "b" ++ i ++ ": "
for var entry : state • the buckets[i]; entry is_not null; entry = entry • next
s = s ++ "<" ++ (entry • key !> string) ++ ":" ++ (entry • value !> string) ++ ">"
s = s ++ "\n"
return s
← immutable list dictionary ideal • runtime • elements • base hash dictionary hash dictionary →