+
Point of view
All features
deferred class ABSTRACT_HASHED_DICTIONARY [V_, K_]
Summary
top
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
top
Overview
top
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
{HASHED_DICTIONARY}
top
The buckets storage area is the primary hash table of capacity elements.
To search some key, the first access is done in buckets using the remainder of the division of the key hash_code by capacity. In order to try to avoid clashes, capacity is always a prime number (selected using HASHED_CAPACITY).
hash_code (k: K_): INTEGER_32
deferred function
{}
top
require
  • k /= Void
buckets_item (a_buckets: NATIVE_ARRAY[HASHED_DICTIONARY_NODE[V_, K_]], idx: INTEGER_32): HASHED_DICTIONARY_NODE[V_, K_]
effective function
{}
top
require
Default_size: INTEGER_32
is 53
constant attribute
{ANY}
top
Default size for the storage area in number of items.
capacity: INTEGER_32
writable attribute
{ANY}
top
Of the buckets storage area.
Note: this not the accurate capacity value, but it does not hurt.
count: INTEGER_32
writable attribute
{ANY}
top
Number of available items in the hoard.
See also is_empty
ensure
  • Result >= 0
has (k: K_): BOOLEAN
effective function
{ANY}
top
Is there a value currently associated with key k?
See also fast_has, at.
require
  • k /= Void
at (k: K_): V_
effective function
{ANY}
top
Return the value associated to key k.
See also fast_at, reference_at, has.
require
  • has(k)
reference_at (k: K_): V_
effective function
{ANY}
top
Return Void or the value associated with key k.
Actually, this feature is useful only when the type of values (the type V_) is a reference type, to avoid using has just followed by at to get the corresponding value with the very best performances.
See also fast_reference_at, at, has.
require
  • k /= Void
  • values_are_not_expanded: Result = Void
ensure
  • has(k) implies Result = at(k)
fast_has (k: K_): BOOLEAN
effective function
{ANY}
top
Is there a value currently associated with key k?
Using basic = for comparison.
See also has, at, fast_at.
require
  • k /= Void
fast_at (k: K_): V_
effective function
{ANY}
top
Return the value associated to key k using basic = for comparison.
See also at, reference_at, fast_reference_at.
require
  • fast_has(k)
fast_reference_at (k: K_): V_
effective function
{ANY}
top
Same work as reference_at, but basic = is used for comparison.
See also reference_at, at, has.
require
  • k /= Void
  • values_are_reference: Result = Void
ensure
  • fast_has(k) implies Result = fast_at(k)
put (v: V_, k: K_)
effective procedure
{ANY}
top
Change some existing entry or add the new one.
If there is as yet no key k in the dictionary, enter it with item v. Otherwise overwrite the item associated with key k. As the put procedure actually uses is_equal, you may consider to use fast_put for expanded objects as well while trying to get the very best performances.
See also fast_put, add.
require
  • k /= Void
ensure
  • v = at(k)
fast_put (v: V_, k: K_)
effective procedure
{ANY}
top
Same job as put, but uses basic = for comparison.
If you are sure that k is not an existing entry, please consider using add to get very best performances.
See also put, add.
require
  • k /= Void
ensure
  • v = at(k)
add (v: V_, k: K_)
effective procedure
{ANY}
top
To add a new entry k with its associated value v.
Actually, this is equivalent to call put, but it may run a little bit faster.
See also put, fast_put.
require
  • not has(k)
ensure
  • count = 1 + old count
  • v = at(k)
remove (k: K_)
effective procedure
{ANY}
top
Remove entry k (which may exist or not before this call).
As the remove procedure actually uses is_equal, you may consider to use fast_remove for expanded objects as well while trying to get the very best performances.
See also fast_remove, clear_count.
require
  • k /= Void
ensure
  • not has(k)
fast_remove (k: K_)
effective procedure
{ANY}
top
Same job as remove, but uses basic = for comparison.
See also remove, clear_count.
require
  • k /= Void
ensure
  • not fast_has(k)
clear_count
effective procedure
{ANY}
top
Discard all items (is_empty is True after that call).
The internal capacity is not changed by this call.
See also clear_count_and_capacity, remove.
ensure
clear_count_and_capacity
effective procedure
{ANY}
top
Discard all items (is_empty is True after that call).
The internal capacity may also be reduced after this call.
See also clear_count, remove.
ensure
set_item (v: V_, index: INTEGER_32)
effective procedure
{ANY}
top
require
  • valid_index(index)
ensure
  • count = old count
  • v = item(index)
item (index: INTEGER_32): V_
effective function
{ANY}
top
Item at the corresponding index i.
See also lower, upper, valid_index.
require
  • valid_index(index)
ensure
  • Result = at(key(index))
key (index: INTEGER_32): K_
effective function
{ANY}
top
require
  • valid_index(index)
ensure
  • at(Result) = item(index)
new_iterator_on_keys: ITERATOR[K_]
effective function
{ANY}
top
ensure
  • Result /= Void
new_iterator: ITERATOR[TUPLE 2[V_, K_]]
effective function
{ANY}
top
ensure
  • Result /= Void
key_map_in (buffer: COLLECTION[K_])
effective procedure
{ANY}
top
Append in buffer, all available keys (this may be useful to speed up the traversal).
See also item_map_in.
require
  • buffer /= Void
ensure
  • buffer.count = count + old buffer.count
item_map_in (buffer: COLLECTION[V_])
effective procedure
{ANY}
top
Append in buffer, all available items (this may be useful to speed up the traversal).
See also key_map_in.
require
  • buffer /= Void
ensure
  • buffer.count = count + old buffer.count
copy (other: ABSTRACT_HASHED_DICTIONARY [V_, K_])
effective procedure
{ANY}
top
Reinitialize by copying all associations of other.
require
    • not immutable
    • same_dynamic_type(other)
      • not immutable
      • same_dynamic_type(other)
      • not immutable
      • same_dynamic_type(other)
ensure
  • is_equal(other)
internal_key (k: K_): K_
effective function
{ANY}
top
Retrieve the internal key object which correspond to the existing entry k (the one memorized into the Current dictionary).
See also has, fast_has.
require
  • has(k)
ensure
  • Result.is_equal(k)
manifest_make (needed_capacity: INTEGER_32)
effective procedure
{}
top
Manifest creation of a HASHED_DICTIONARY.
increase_capacity
effective procedure
{}
top
There are not enough free slots: the dictionary must grow.
set_cache_user (index: INTEGER_32)
effective procedure
{}
top
Set the internal memory cache (cache_user, cache_node and cache_buckets) to the appropriate valid value.
require ensure
cache_user: INTEGER_32
writable attribute
{}
top
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.
When the cache is active, the corresponding index in buckets is saved in cache_buckets and the corresponding node in cache_node.
cache_node: HASHED_DICTIONARY_NODE[V_, K_]
writable attribute
{}
top
Meaningful only when cache_user is not -1.
cache_buckets: INTEGER_32
writable attribute
{}
top
Meaningful only when cache_user is not -1.
free_nodes: WEAK_REFERENCE[HASHED_DICTIONARY_NODE[V_, K_]]
writable attribute
{}
top
If any, they are ready to be recycled.
nodes_list: FAST_ARRAY[HASHED_DICTIONARY_NODE[V_, K_]]
writable attribute
{}
top
Only in debug: the nodes list, in insertion order.
Useful with sedb when browsing the nodes
once function
{}
top
dispose_node (node: HASHED_DICTIONARY_NODE[V_, K_]): HASHED_DICTIONARY_NODE[V_, K_]
effective function
{}
top
Add node in the free_nodes list.
require
  • node /= Void
ensure
  • Result = old node.next
new_node (v: V_, k: K_, next: HASHED_DICTIONARY_NODE[V_, K_]): HASHED_DICTIONARY_NODE[V_, K_]
effective function
{}
top
Recycle from free_nodes or create a new one.
create_with_capacity (new_capacity: INTEGER_32)
effective procedure
{}
top
require
  • new_capacity > 0
make
effective procedure
{}
top
Create an empty dictionary.
Internal storage capacity of the dictionary is initialized using the Default_size value. Then, tuning of needed storage capacity is performed automatically according to usage. If you are really sure that your dictionary is always really bigger than Default_size, you may consider to use with_capacity to save some execution time.
ensure
default_create
effective procedure
{}
top
Create an empty dictionary.
Internal storage capacity of the dictionary is initialized using the Default_size value. Then, tuning of needed storage capacity is performed automatically according to usage. If you are really sure that your dictionary is always really bigger than Default_size, you may consider to use with_capacity to save some execution time.
ensure
with_capacity (medium_size: INTEGER_32)
effective procedure
{}
top
May be used to save some execution time if one is sure that storage size will rapidly become really bigger than Default_size.
 When first remove occurs, storage size may naturally become
smaller than medium_size. Afterall, tuning of storage size is done automatically according to
usage.
require
  • medium_size >= 0
ensure
new_iterator_on_items: ITERATOR[V_]
effective function
{ANY}
top
ensure
  • Result /= Void
  • Result /= Void
  • Result /= Void
  • Result.generation = generation
manifest_put (index: INTEGER_32, v: V_, k: K_)
effective procedure
{}
top
require
manifest_semicolon_check: INTEGER_32
is 2
constant attribute
{}
top
Put semicolons between successive value-key pairs.
key_safe_equal (k1: K_, k2: K_): BOOLEAN
effective function
{}
top
Because keys are never Void, we do not rely on the SAFE_EQUAL class.
require
  • k1 /= Void
  • k2 /= Void
is_empty: BOOLEAN
effective function
{ANY}
top
Is it empty?
ensure
  • definition: Result = count = 0
infix "@" (k: K_): V_
frozen
effective function
{ANY}
top
The infix notation which is actually a synonym for at.
require ensure
  • definition: Result = at(k)
occurrences (v: V_): INTEGER_32
effective function
{ANY}
top
Number of occurrences using is_equal for comparison.
See also fast_occurrences, fast_has, has.
ensure
  • Result >= 0
fast_occurrences (v: V_): INTEGER_32
effective function
{ANY}
top
Number of occurrences using basic = for comparison.
See also occurrences, fast_has, has.
ensure
  • Result >= 0
key_at (v: V_): K_
effective function
{ANY}
top
Retrieve the key used for value v using is_equal for comparison.
See also fast_key_at, at.
require ensure
fast_key_at (v: V_): K_
effective function
{ANY}
top
Retrieve the key used for value v using = for comparison.
See also key_at, at.
require ensure
  • at(Result) = v
lower: INTEGER_32
is 1
constant attribute
{ANY}
top
Minimum index.
See also upper, valid_index, item.
upper: INTEGER_32
effective function
{ANY}
top
Maximum index.
See also lower, valid_index, item.
ensure
first: V_
effective function
{ANY}
top
The very first item.
See also last, item.
require
  • not is_empty
ensure
  • definition: Result = item(lower)
last: V_
effective function
{ANY}
top
The last item.
See also first, item.
require
  • not is_empty
ensure
  • definition: Result = item(upper)
keys: TRAVERSABLE[K_]
effective function
{ANY}
top
An iterable of this map keys
ensure
items: TRAVERSABLE[V_]
effective function
{ANY}
top
An iterable of this map values Usually returns Current because MAP is TRAVERSABLE.
ensure
fast_is_equal (other: ABSTRACT_HASHED_DICTIONARY [V_, K_]): BOOLEAN
effective function
{ANY}
top
Do both dictionaries have the same set of associations?
Keys are compared with is_equal and values are compared with the basic = operator.
See also is_equal.
ensure
is_equal (other: ABSTRACT_HASHED_DICTIONARY [V_, K_]): BOOLEAN
effective function
{ANY}
top
Do both dictionaries have the same set of associations?
Both keys and values are compared with is_equal.
See also fast_is_equal.
require
    • other /= Void
    • other /= Void
ensure
  • commutative: generating_type = other.generating_type implies Result = other.is_equal(Current)
is_equal_map (other: ABSTRACT_HASHED_DICTIONARY [V_, K_]): BOOLEAN
effective function
{ANY}
top
Do both collections have the same lower, upper, and items?
This feature is obsolete: Use `is_equal' instead.
out_in_tagged_out_memory
effective procedure
{ANY}
top
Append terse printable representation of current object in tagged_out_memory.
require
    • locked: tagged_out_locked
    • locked: tagged_out_locked
ensure
  • still_locked: tagged_out_locked
  • not_cleared: tagged_out_memory.count >= old tagged_out_memory.count
  • append_only: old tagged_out_memory.twin.is_equal(tagged_out_memory.substring(1, old tagged_out_memory.count))
for_each (action: PROCEDURE[TUPLE[TUPLE 2[V_, K_]]])
effective procedure
{ANY}
top
Apply action to every [V_, K_] associations of Current.
See also for_all, exist.
require
  • action /= Void
do_all (action: ROUTINE[TUPLE[TUPLE 2[V_, K_]]])
frozen
effective procedure
{ANY}
top
Apply action to every [V_, K_] associations of Current.
This feature is obsolete: This feature is not secure because it accepts a FUNCTION, the result of which is lost. Plese use `for_each` instead.
for_all (test: FUNCTION[TUPLE[TUPLE 2[V_, K_]]]): BOOLEAN
effective function
{ANY}
top
Do all [V_, K_] associations satisfy test?
See also for_each, exist.
require
  • test /= Void
exists (test: FUNCTION[TUPLE[TUPLE 2[V_, K_]]]): BOOLEAN
effective function
{ANY}
top
Does at least one [V_, K_] association satisfy test?
See also for_all, for_each.
require
  • test /= Void
aggregate (action: FUNCTION[TUPLE[TUPLE 3[V_, V_, K_], V_]], initial: V_): V_
effective function
{ANY}
top
Aggregate all the elements starting from the initial value.
See also for_each, for_all, exists.
require
  • action /= Void
keys_memory: DICTIONARY_KEY_TRAVERSER[V_, K_]
writable attribute
{}
top
_inline_agent43 (v: V_, k: K_)
frozen
effective procedure
{}
top
enumerate: ENUMERATE[E_]
effective function
{ANY}
top
get_new_iterator: ITERATOR[E_]
frozen
effective function
{ANY}
top
This feature is obsolete: Use `new_iterator' instead. This historical SmartEiffel feature is badly named.
generation: INTEGER_32
writable attribute
{ANY}
top
next_generation
effective procedure
{}
top
ensure
_inline_agent1 (a: ROUTINE[TUPLE[TUPLE 1[E_]]], e: E_)
frozen
effective procedure
{}
top
valid_index (i: INTEGER_32): BOOLEAN
effective function
{ANY}
top
True when i is valid (i.e., inside actual bounds).
See also lower, upper, item.
ensure
prime_number_ceiling (integer: INTEGER_32): INTEGER_32
effective function
{}
top
A good prime number, large enough, and no smaller than integer.
require
  • is_positive: integer >= 0
ensure
  • Result >= integer.max(1)
prime_capacity (a_capacity: INTEGER_32): INTEGER_32
effective function
{}
top
require
  • a_capacity >= 0
ensure
  • Result >= a_capacity
should_increase_capacity (a_capacity: INTEGER_32, a_count: INTEGER_32): BOOLEAN
effective function
{}
top
Maximum_character_code: INTEGER_16
{}
top
Largest supported code for CHARACTER values.
ensure
  • meaningful: Result >= 127
Maximum_integer_8: INTEGER_8
is 127
constant attribute
{}
top
Largest supported value of type INTEGER_8.
Maximum_integer_16: INTEGER_16
is 32767
constant attribute
{}
top
Largest supported value of type INTEGER_16.
Maximum_integer: INTEGER_32
is 2147483647
constant attribute
{}
top
Largest supported value of type INTEGER/INTEGER_32.
Maximum_integer_32: INTEGER_32
is 2147483647
constant attribute
{}
top
Largest supported value of type INTEGER/INTEGER_32.
Maximum_integer_64: INTEGER_64
is 9223372036854775807
constant attribute
{}
top
Largest supported value of type INTEGER_64.
Maximum_real_32: REAL_32
is {REAL_32 3.4028234663852885981170418348451692544e+38}
constant attribute
{}
top
Largest non-special (no NaNs nor infinity) supported value of type REAL_32.
Maximum_real: REAL_64
{}
top
Largest non-special (no NaNs nor infinity) supported value of type REAL.
Just to give an idea of this value: 1.79769313486231570....e+308
Maximum_real_64: REAL_64
{}
top
Largest non-special (no NaNs nor infinity) supported value of type REAL.
Just to give an idea of this value: 1.79769313486231570....e+308
Maximum_real_80: REAL_EXTENDED
{}
top
Largest supported value of type REAL_80.
ensure
Minimum_character_code: INTEGER_16
{}
top
Smallest supported code for CHARACTER values.
ensure
  • meaningful: Result <= 0
Minimum_integer_8: INTEGER_8
is -128
constant attribute
{}
top
Smallest supported value of type INTEGER_8.
Minimum_integer_16: INTEGER_16
is -32768
constant attribute
{}
top
Smallest supported value of type INTEGER_16.
Minimum_integer: INTEGER_32
is -2147483648
constant attribute
{}
top
Smallest supported value of type INTEGER/INTEGER_32.
Minimum_integer_32: INTEGER_32
is -2147483648
constant attribute
{}
top
Smallest supported value of type INTEGER/INTEGER_32.
Minimum_integer_64: INTEGER_64
is -9223372036854775808
constant attribute
{}
top
Smallest supported value of type INTEGER_64.
Minimum_real_32: REAL_32
is {REAL_32 -3.40282346638528859811704183484516925440e+38}
constant attribute
{}
top
Smallest non-special (no NaNs nor infinity) supported value of type REAL_32.
Minimum_real: REAL_64
{}
top
Smallest non-special (no NaNs nor infinity) supported value of type REAL.
Just to give an idea of this value: -1.79769313486231570....e+308
Minimum_real_64: REAL_64
{}
top
Smallest non-special (no NaNs nor infinity) supported value of type REAL.
Just to give an idea of this value: -1.79769313486231570....e+308
Minimum_real_80: REAL_64
{}
top
Smallest supported value of type REAL_80.
ensure
  • meaningful: Result <= 0.0
Boolean_bits: INTEGER_32
{}
top
Number of bits in a value of type BOOLEAN.
ensure
  • meaningful: Result >= 1
Character_bits: INTEGER_32
{}
top
Number of bits in a value of type CHARACTER.
ensure
Integer_bits: INTEGER_32
{}
top
Number of bits in a value of type INTEGER.
ensure
  • integer_definition: Result = 32
Real_bits: INTEGER_32
is 64
constant attribute
{}
top
Number of bits in a value of type REAL.
Pointer_bits: INTEGER_32
{}
top
Number of bits in a value of type POINTER.