class HASHED_DICTIONARY [V_, K_ -> HASHABLE]

Features exported to ANY

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:

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

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)

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.

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