+
Point of view
All features
deferred class ABSTRACT_HASHED_DICTIONARY [V_, K_]
Summary
Associative memory. Values of type V_ are stored using Keys of type K_.
Efficient implementation of DICTIONARY using hash_code on keys.
Direct parents
Inherit list: SIMPLE_DICTIONARY
Insert list: HASH_TABLE_SIZE
Known children
Inherit list: ABSTRACT_LINKED_HASHED_DICTIONARY, EXT_HASHED_DICTIONARY, HASHED_DICTIONARY
Class invariant
Overview
Features
{HASHED_DICTIONARY}
  • buckets: NATIVE_ARRAY[HASHED_DICTIONARY_NODE[V_, K_]]
    The buckets storage area is the primary hash table of capacity elements.
{}
{ANY}
{ANY}
  • put (v: V_, k: K_)
    Change some existing entry or add the new one.
  • fast_put (v: V_, k: K_)
    Same job as put, but uses basic = for comparison.
  • add (v: V_, k: K_)
    To add a new entry k with its associated value v.
  • remove (k: K_)
    Remove entry k (which may exist or not before this call).
  • fast_remove (k: K_)
    Same job as remove, but uses basic = for comparison.
  • clear_count
    Discard all items (is_empty is True after that call).
  • clear_count_and_capacity
    Discard all items (is_empty is True after that call).
  • set_item (v: V_, index: INTEGER_32)
  • item (index: INTEGER_32): V_
    Item at the corresponding index i.
  • key (index: INTEGER_32): K_
  • new_iterator_on_keys: ITERATOR[K_]
  • new_iterator: ITERATOR[TUPLE 2[V_, K_]]
  • key_map_in (buffer: COLLECTION[K_])
    Append in buffer, all available keys (this may be useful to speed up the traversal).
  • item_map_in (buffer: COLLECTION[V_])
    Append in buffer, all available items (this may be useful to speed up the traversal).
  • copy (other: ABSTRACT_HASHED_DICTIONARY [V_, K_])
    Reinitialize by copying all associations of other.
  • internal_key (k: K_): K_
    Retrieve the internal key object which correspond to the existing entry k (the one memorized into the Current dictionary).
Implement manifest generic creation:
{}
{}
{ANY}
Implement manifest generic creation:
{}
{}
Counting:
{ANY}
Basic access:
{ANY}
  • infix "@" (k: K_): V_
    The infix notation which is actually a synonym for at.
Looking and searching some value:
{ANY}
To provide iterating facilities:
{ANY}
{ANY}
  • fast_is_equal (other: ABSTRACT_HASHED_DICTIONARY [V_, K_]): BOOLEAN
    Do both dictionaries have the same set of associations?
  • is_equal (other: ABSTRACT_HASHED_DICTIONARY [V_, K_]): BOOLEAN
    Do both dictionaries have the same set of associations?
  • is_equal_map (other: ABSTRACT_HASHED_DICTIONARY [V_, K_]): BOOLEAN
    Do both collections have the same lower, upper, and items?
Display support:
{ANY}
Agents based features:
{ANY}
{}
{}
{ANY}
Other features:
{ANY}
{ANY}
{}
{}
Indexing:
{ANY}
{}
Capacity management: ideally we try to keep the dictionary less than 2/3rd filled
{}
Maximum:
{}
Minimum:
{}
Bits:
{}
buckets: NATIVE_ARRAY[HASHED_DICTIONARY_NODE[V_, K_]]
writable attribute
The buckets storage area is the primary hash table of capacity elements.
hash_code (k: K_): INTEGER_32
deferred function
{}
buckets_item (a_buckets: NATIVE_ARRAY[HASHED_DICTIONARY_NODE[V_, K_]], idx: INTEGER_32): HASHED_DICTIONARY_NODE[V_, K_]
effective function
{}
Default_size: INTEGER_32
is 53
constant attribute
{ANY}
Default size for the storage area in number of items.
capacity: INTEGER_32
writable attribute
{ANY}
Of the buckets storage area.
count: INTEGER_32
writable attribute
{ANY}
Number of available items in the hoard.
has (k: K_): BOOLEAN
effective function
{ANY}
Is there a value currently associated with key k?
at (k: K_): V_
effective function
{ANY}
Return the value associated to key k.
reference_at (k: K_): V_
effective function
{ANY}
Return Void or the value associated with key k.
fast_has (k: K_): BOOLEAN
effective function
{ANY}
Is there a value currently associated with key k?
fast_at (k: K_): V_
effective function
{ANY}
Return the value associated to key k using basic = for comparison.
fast_reference_at (k: K_): V_
effective function
{ANY}
Same work as reference_at, but basic = is used for comparison.
put (v: V_, k: K_)
effective procedure
{ANY}
Change some existing entry or add the new one.
fast_put (v: V_, k: K_)
effective procedure
{ANY}
Same job as put, but uses basic = for comparison.
add (v: V_, k: K_)
effective procedure
{ANY}
To add a new entry k with its associated value v.
remove (k: K_)
effective procedure
{ANY}
Remove entry k (which may exist or not before this call).
fast_remove (k: K_)
effective procedure
{ANY}
Same job as remove, but uses basic = for comparison.
clear_count
effective procedure
{ANY}
Discard all items (is_empty is True after that call).
clear_count_and_capacity
effective procedure
{ANY}
Discard all items (is_empty is True after that call).
set_item (v: V_, index: INTEGER_32)
effective procedure
{ANY}
item (index: INTEGER_32): V_
effective function
{ANY}
Item at the corresponding index i.
key (index: INTEGER_32): K_
effective function
{ANY}
new_iterator_on_keys: ITERATOR[K_]
effective function
{ANY}
new_iterator: ITERATOR[TUPLE 2[V_, K_]]
effective function
{ANY}
key_map_in (buffer: COLLECTION[K_])
effective procedure
{ANY}
Append in buffer, all available keys (this may be useful to speed up the traversal).
item_map_in (buffer: COLLECTION[V_])
effective procedure
{ANY}
Append in buffer, all available items (this may be useful to speed up the traversal).
copy (other: ABSTRACT_HASHED_DICTIONARY [V_, K_])
effective procedure
{ANY}
Reinitialize by copying all associations of other.
internal_key (k: K_): K_
effective function
{ANY}
Retrieve the internal key object which correspond to the existing entry k (the one memorized into the Current dictionary).
manifest_make (needed_capacity: INTEGER_32)
effective procedure
{}
Manifest creation of a HASHED_DICTIONARY.
increase_capacity
effective procedure
{}
There are not enough free slots: the dictionary must grow.
set_cache_user (index: INTEGER_32)
effective procedure
{}
Set the internal memory cache (cache_user, cache_node and cache_buckets) to the appropriate valid value.
cache_user: INTEGER_32
writable attribute
{}
The last user's external index in range [1 .. count] (see item and valid_index for example) may be saved in cache_user otherwise -1 to indicate that the cache is not active.
cache_node: HASHED_DICTIONARY_NODE[V_, K_]
writable attribute
{}
Meaningful only when cache_user is not -1.
cache_buckets: INTEGER_32
writable attribute
{}
Meaningful only when cache_user is not -1.
free_nodes: WEAK_REFERENCE[HASHED_DICTIONARY_NODE[V_, K_]]
writable attribute
{}
If any, they are ready to be recycled.
nodes_list: FAST_ARRAY[HASHED_DICTIONARY_NODE[V_, K_]]
writable attribute
{}
Only in debug: the nodes list, in insertion order.
once function
{}
dispose_node (node: HASHED_DICTIONARY_NODE[V_, K_]): HASHED_DICTIONARY_NODE[V_, K_]
effective function
{}
Add node in the free_nodes list.
new_node (v: V_, k: K_, next: HASHED_DICTIONARY_NODE[V_, K_]): HASHED_DICTIONARY_NODE[V_, K_]
effective function
{}
Recycle from free_nodes or create a new one.
create_with_capacity (new_capacity: INTEGER_32)
effective procedure
{}
make
effective procedure
{}
Create an empty dictionary.
default_create
effective procedure
{}
Create an empty dictionary.
with_capacity (medium_size: INTEGER_32)
effective procedure
{}
May be used to save some execution time if one is sure that storage size will rapidly become really bigger than Default_size.
new_iterator_on_items: ITERATOR[V_]
effective function
{ANY}
manifest_put (index: INTEGER_32, v: V_, k: K_)
effective procedure
{}
manifest_semicolon_check: INTEGER_32
is 2
constant attribute
{}
Put semicolons between successive value-key pairs.
key_safe_equal (k1: K_, k2: K_): BOOLEAN
effective function
{}
Because keys are never Void, we do not rely on the SAFE_EQUAL class.
is_empty: BOOLEAN
effective function
{ANY}
Is it empty?
infix "@" (k: K_): V_
frozen
effective function
{ANY}
The infix notation which is actually a synonym for at.
occurrences (v: V_): INTEGER_32
effective function
{ANY}
Number of occurrences using is_equal for comparison.
fast_occurrences (v: V_): INTEGER_32
effective function
{ANY}
Number of occurrences using basic = for comparison.
key_at (v: V_): K_
effective function
{ANY}
Retrieve the key used for value v using is_equal for comparison.
fast_key_at (v: V_): K_
effective function
{ANY}
Retrieve the key used for value v using = for comparison.
lower: INTEGER_32
is 1
constant attribute
{ANY}
Minimum index.
upper: INTEGER_32
effective function
{ANY}
Maximum index.
first: V_
effective function
{ANY}
The very first item.
last: V_
effective function
{ANY}
The last item.
keys: TRAVERSABLE[K_]
effective function
{ANY}
An iterable of this map keys
items: TRAVERSABLE[V_]
effective function
{ANY}
An iterable of this map values Usually returns Current because MAP is TRAVERSABLE.
fast_is_equal (other: ABSTRACT_HASHED_DICTIONARY [V_, K_]): BOOLEAN
effective function
{ANY}
Do both dictionaries have the same set of associations?
is_equal (other: ABSTRACT_HASHED_DICTIONARY [V_, K_]): BOOLEAN
effective function
{ANY}
Do both dictionaries have the same set of associations?
is_equal_map (other: ABSTRACT_HASHED_DICTIONARY [V_, K_]): BOOLEAN
effective function
{ANY}
Do both collections have the same lower, upper, and items?
out_in_tagged_out_memory
effective procedure
{ANY}
Append terse printable representation of current object in tagged_out_memory.
for_each (action: PROCEDURE[TUPLE[TUPLE 2[V_, K_]]])
effective procedure
{ANY}
Apply action to every [V_, K_] associations of Current.
do_all (action: ROUTINE[TUPLE[TUPLE 2[V_, K_]]])
frozen
effective procedure
{ANY}
Apply action to every [V_, K_] associations of Current.
for_all (test: FUNCTION[TUPLE[TUPLE 2[V_, K_]]]): BOOLEAN
effective function
{ANY}
Do all [V_, K_] associations satisfy test?
exists (test: FUNCTION[TUPLE[TUPLE 2[V_, K_]]]): BOOLEAN
effective function
{ANY}
Does at least one [V_, K_] association satisfy test?
aggregate (action: FUNCTION[TUPLE[TUPLE 3[V_, V_, K_], V_]], initial: V_): V_
effective function
{ANY}
Aggregate all the elements starting from the initial value.
keys_memory: DICTIONARY_KEY_TRAVERSER[V_, K_]
writable attribute
{}
_inline_agent43 (v: V_, k: K_)
frozen
effective procedure
{}
enumerate: ENUMERATE[E_]
effective function
{ANY}
get_new_iterator: ITERATOR[E_]
frozen
effective function
{ANY}
generation: INTEGER_32
writable attribute
{ANY}
next_generation
effective procedure
{}
_inline_agent1 (a: ROUTINE[TUPLE[TUPLE 1[E_]]], e: E_)
frozen
effective procedure
{}
valid_index (i: INTEGER_32): BOOLEAN
effective function
{ANY}
True when i is valid (i.e., inside actual bounds).
prime_number_ceiling (integer: INTEGER_32): INTEGER_32
effective function
{}
A good prime number, large enough, and no smaller than integer.
prime_capacity (a_capacity: INTEGER_32): INTEGER_32
effective function
{}
should_increase_capacity (a_capacity: INTEGER_32, a_count: INTEGER_32): BOOLEAN
effective function
{}
Maximum_character_code: INTEGER_16
{}
Largest supported code for CHARACTER values.
Maximum_integer_8: INTEGER_8
is 127
constant attribute
{}
Largest supported value of type INTEGER_8.
Maximum_integer_16: INTEGER_16
is 32767
constant attribute
{}
Largest supported value of type INTEGER_16.
Maximum_integer: INTEGER_32
is 2147483647
constant attribute
{}
Largest supported value of type INTEGER/INTEGER_32.
Maximum_integer_32: INTEGER_32
is 2147483647
constant attribute
{}
Largest supported value of type INTEGER/INTEGER_32.
Maximum_integer_64: INTEGER_64
is 9223372036854775807
constant attribute
{}
Largest supported value of type INTEGER_64.
Maximum_real_32: REAL_32
is {REAL_32 3.4028234663852885981170418348451692544e+38}
constant attribute
{}
Largest non-special (no NaNs nor infinity) supported value of type REAL_32.
Maximum_real: REAL_64
{}
Largest non-special (no NaNs nor infinity) supported value of type REAL.
Maximum_real_64: REAL_64
{}
Largest non-special (no NaNs nor infinity) supported value of type REAL.
Maximum_real_80: REAL_EXTENDED
{}
Largest supported value of type REAL_80.
Minimum_character_code: INTEGER_16
{}
Smallest supported code for CHARACTER values.
Minimum_integer_8: INTEGER_8
is -128
constant attribute
{}
Smallest supported value of type INTEGER_8.
Minimum_integer_16: INTEGER_16
is -32768
constant attribute
{}
Smallest supported value of type INTEGER_16.
Minimum_integer: INTEGER_32
is -2147483648
constant attribute
{}
Smallest supported value of type INTEGER/INTEGER_32.
Minimum_integer_32: INTEGER_32
is -2147483648
constant attribute
{}
Smallest supported value of type INTEGER/INTEGER_32.
Minimum_integer_64: INTEGER_64
is -9223372036854775808
constant attribute
{}
Smallest supported value of type INTEGER_64.
Minimum_real_32: REAL_32
is {REAL_32 -3.40282346638528859811704183484516925440e+38}
constant attribute
{}
Smallest non-special (no NaNs nor infinity) supported value of type REAL_32.
Minimum_real: REAL_64
{}
Smallest non-special (no NaNs nor infinity) supported value of type REAL.
Minimum_real_64: REAL_64
{}
Smallest non-special (no NaNs nor infinity) supported value of type REAL.
Minimum_real_80: REAL_64
{}
Smallest supported value of type REAL_80.
Boolean_bits: INTEGER_32
{}
Number of bits in a value of type BOOLEAN.
Character_bits: INTEGER_32
{}
Number of bits in a value of type CHARACTER.
Integer_bits: INTEGER_32
{}
Number of bits in a value of type INTEGER.
Real_bits: INTEGER_32
is 64
constant attribute
{}
Number of bits in a value of type REAL.
Pointer_bits: INTEGER_32
{}
Number of bits in a value of type POINTER.