class HASHED_DICTIONARY [V_, K_ -> HASHABLE]

All features

Associative memory. Values of type V_ are stored using Keys of type K_.

Efficient implementation of DICTIONARY using hash_code on keys.

Direct parents

conformant parents

SIMPLE_DICTIONARY

Summary

creation features

exported features

Counting:

Basic access:

Looking and searching some value:

Removing:

To provide iterating facilities:

Agents based features:

Implement manifest generic creation.

Indexing:

Details

make

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

  • capacity = Default_size
  • is_empty

with_capacity (medium_size: INTEGER)

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

  • is_empty
  • capacity >= medium_size

special_common_dictionary (fn: WEAK_REFERENCE[HASHED_DICTIONARY_NODE[V_K_]])

Used to avoid having a recursive once function while initializing common_free_nodes.

require

  • fn /= Void

    common_free_nodes = Void {V_} ?:= free_nodes {K_} ?:= generating_type

ensure

  • count = 0

buckets: NATIVE_ARRAY[HASHED_DICTIONARY_NODE[V_K_]]

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 HASH_TABLE_SIZE).

Default_size: INTEGER

Default size for the storage area in number of items.

capacity: INTEGER

Of the buckets storage area. Note: this not the accurate capacity value, but it does not hurt.

count: INTEGER

Actual count of stored elements.

ensure

  • definition: Result = upper - lower + 1

has (k: K_): BOOLEAN

Is there a value currently associated with key k?

See also fast_has, at.

require

  • k /= Void

at (k: K_): V_

Return the value associated to key k.

See also fast_at, reference_at, has.

require

  • has(k)

reference_at (k: K_): V_

Return Void or the value associated with key k. Actually, this feature is useful 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.

See also fast_reference_at, at, has.

require

  • k /= Void
  • values_are_expanded: Result /= Void implies not Result.is_expanded_type

ensure

  • has(k) implies Result = at(k)

fast_has (k: K_): BOOLEAN

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_

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_

Same work as reference_at, but basic = is used for comparison.

See also reference_at, at, has.

require

  • k /= Void
  • values_are_expanded: Result /= Void implies not Result.is_expanded_type

ensure

  • fast_has(k) implies Result = fast_at(k)

put (v: V_, k: K_)

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_)

Same job as put, but uses basic = for comparison.

See also put, add.

require

  • k /= Void

ensure

  • v = at(k)

add (v: V_, k: K_)

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_)

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_)

Same job as remove, but uses basic = for comparison.

See also remove, clear_count.

require

  • k /= Void

ensure

  • not has(k)

clear_count

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

  • capacity = old capacity
  • is_empty: count = 0
  • capacity = old capacity

clear_count_and_capacity

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

  • capacity = old capacity
  • is_empty: count = 0
  • capacity <= old capacity

item (index: INTEGER): V_

Item at the corresponding index i.

See also lower, upper, valid_index.

require

  • valid_index(index)

ensure

  • Result = at(key(index))

key (index: INTEGER): K_

require

  • valid_index(index)

ensure

  • at(Result) = item(index)

get_new_iterator_on_keys: ITERATOR[K_]

ensure

  • Result /= Void

key_map_in (buffer: COLLECTION[K_])

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_])

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: HASHED_DICTIONARY [V_, K_ -> HASHABLE])

Reinitialize by copying all associations of other.

require

  • same_dynamic_type(other)

ensure

  • is_equal(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).

See also has, fast_has.

require

  • has(k)

ensure

  • Result.is_equal(k)

increase_capacity

There is no more free slots: the dictionary must grow.

require

  • capacity = count

ensure

  • count = old count
  • capacity > old capacity

set_cache_user (index: INTEGER)

Set the internal memory cache (cache_user, cache_node and cache_buckets) to the appropriate valid value.

require

  • valid_index(index)

ensure

  • cache_user = index
  • cache_buckets.in_range(0, capacity - 1)
  • cache_node /= Void

cache_user: INTEGER

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 save in cache_buckets and the corresponding node in cache_node.

cache_node: HASHED_DICTIONARY_NODE[V_K_]

Meaningful only when cache_user is not -1.

cache_buckets: INTEGER

Meaningful only when cache_user is not -1.

free_nodes: WEAK_REFERENCE[HASHED_DICTIONARY_NODE[V_K_]]

If any, they are ready to be recycled.

common_free_nodes: DICTIONARY [V_, K_][WEAK_REFERENCE [G_][ANY_HASHED_DICTIONARY_NODE]STRING]
dispose_node (node: HASHED_DICTIONARY_NODE[V_K_]): HASHED_DICTIONARY_NODE[V_K_]

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_]

Recycle from free_nodes or create a new one.

make

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

  • capacity = Default_size
  • is_empty

with_capacity (medium_size: INTEGER)

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

  • is_empty
  • capacity >= medium_size

special_common_dictionary (fn: WEAK_REFERENCE[HASHED_DICTIONARY_NODE[V_K_]])

Used to avoid having a recursive once function while initializing common_free_nodes.

require

  • fn /= Void

    common_free_nodes = Void {V_} ?:= free_nodes {K_} ?:= generating_type

ensure

  • count = 0

is_empty: BOOLEAN

Is it empty?

ensure

  • definition: Result = (count = 0)

frozen @ (k: K_): V_

The infix notation which is actually a synonym for at.

require

  • has(k)

ensure

  • definition: Result = at(k)

occurrences (v: V_): INTEGER

Number of occurrences using is_equal for comparison.

See also fast_occurrences, fast_has, has.

ensure

  • Result >= 0

fast_occurrences (v: V_): INTEGER

Number of occurrences using basic = for comparison.

See also occurrences, fast_has, has.

ensure

  • Result >= 0

key_at (v: V_): K_

Retrieve the key used for value v using is_equal for comparison.

See also fast_key_at, at.

require

  • occurrences(v) = 1

ensure

  • (create {SAFE_EQUAL[V_]}.default_create).test(at(Result), v)

fast_key_at (v: V_): K_

Retrieve the key used for value v using = for comparison.

See also key_at, at.

require

  • fast_occurrences(v) = 1

ensure

  • at(Result) = v

clear
This feature is obsolete: You must decide to use `clear_count' or `clear_count_and_capacity' (may 9th 2004).
lower: INTEGER

Minimum index.

See also upper, valid_index, item.

upper: INTEGER

Maximum index.

See also lower, valid_index, item.

ensure

  • Result = count

first: V_

The very first item.

See also last, item.

require

  • not is_empty

ensure

  • definition: Result = item(lower)

last: V_

The last item.

See also first, item.

require

  • not is_empty

ensure

  • definition: Result = item(upper)

get_new_iterator_on_items: ITERATOR[V_]

ensure

  • Result /= Void

is_equal (other: HASHED_DICTIONARY [V_, K_ -> HASHABLE]): BOOLEAN

Do both dictionaries have the same set of associations? Keys are compared with is_equal and values are comnpared with the basic = operator.

See also is_equal_map.

require

  • other /= Void

ensure

  • Result implies count = other.count
  • commutative: generating_type = other.generating_type implies Result = other.is_equal(Current)

is_equal_map (other: HASHED_DICTIONARY [V_, K_ -> HASHABLE]): BOOLEAN

Do both dictionaries have the same set of associations? Both keys and values are compared with is_equal.

See also is_equal.

do_all (action: ROUTINE[TUPLE[TUPLE 2[V_K_]]])

Apply action to every [V_, K_] associations of Current.

See also for_all, exist.

for_all (test: PREDICATE[TUPLE[TUPLE 2[V_K_]]]): BOOLEAN

Do all [V_, K_] associations satisfy test?

See also do_all, exist.

exists (test: PREDICATE[TUPLE[TUPLE 2[V_K_]]]): BOOLEAN

Does at least one [V_, K_] association satisfy test?

See also for_all, do_all.

manifest_make (needed_capacity: INTEGER)

Manifest creation of a dictionary.

manifest_put (index: INTEGER, v: V_, k: K_)

require

  • not has(k)

manifest_semicolon_check: INTEGER

Put semicolons between successive value-key pairs.

key_safe_equal (k1: K_, k2: K_): BOOLEAN

Because keys are never Void, we do not rely on the SAFE_EQUAL class.

require

  • k1 /= Void
  • k2 /= Void

valid_index (i: INTEGER): BOOLEAN

True when i is valid (i.e., inside actual bounds).

See also lower, upper, item.

ensure

  • definition: Result = (lower <= i and i <= upper)

Class invariant