Eiffeldoc: DICTIONARY

+

Point of view

All features

deferred class DICTIONARY [V_, K_]

Summary

Associative memory. Values of type V_ are stored using Keys of type K_. To make a comparison with the well known ARRAY class, with a DICTIONARY, index used are not only INTEGER, you can use for example a STRING to access to your information.

Well known implementations, see HASHED_DICTIONARY, AVL_DICTIONARY and ARRAY_DICTIONARY.

See also BIJECTIVE_DICTIONARY class.

Direct parents: Inherit list: MAP
Known children: Inherit list: ARRAY_DICTIONARY, SIMPLE_DICTIONARY

Overview

Features

Adding:

put (v: V_, k: K_) assign at

Change some existing entry or add the new one.
fast_put (v: V_, k: K_) assign fast_at

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.
set_item (v: V_, index: INTEGER_32)

Removing:

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).
capacity: INTEGER_32

Approximation of the actual internal storage capacity.

copy (other: DICTIONARY [V_, K_])

Reinitialize by copying all associations of other.
new_iterator_on_items: ITERATOR[V_]

{}

make

Creates an empty dictionary.

Implement manifest generic creation:

{}

manifest_make (needed_capacity: INTEGER_32)

Manifest creation of a dictionary.
manifest_put (index: INTEGER_32, v: V_, k: K_)
manifest_semicolon_check: INTEGER_32

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.

Counting:

is_empty: BOOLEAN

Is it empty?

Basic access:

has (k: K_): BOOLEAN

Is there a value currently associated with key k?
at (k: K_): V_

Return the value associated to key k.
infix "@" (k: K_): V_

The infix notation which is actually a synonym for at.
reference_at (k: K_): V_

Return Void or the value associated with key k.
fast_has (k: K_): BOOLEAN

Is there a value currently associated with key k?
fast_at (k: K_): V_

Return the value associated to key k using basic = for comparison.
fast_reference_at (k: K_): V_

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

Looking and searching some value:

occurrences (v: V_): INTEGER_32

Number of occurrences using is_equal for comparison.
fast_occurrences (v: V_): INTEGER_32

Number of occurrences using basic = for comparison.
key_at (v: V_): K_

Retrieve the key used for value v using is_equal for comparison.
fast_key_at (v: V_): K_

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

To provide iterating facilities:

lower: INTEGER_32

Minimum index.
upper: INTEGER_32

Maximum index.
item (index: INTEGER_32): V_

Item at the corresponding index i.
key (index: INTEGER_32): K_
first: V_

The very first item.
last: V_

The last item.
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).
keys: TRAVERSABLE[K_]

An iterable of this map keys
items: TRAVERSABLE[V_]

An iterable of this map values Usually returns Current because MAP is TRAVERSABLE.

fast_is_equal (other: DICTIONARY [V_, K_]): BOOLEAN

Do both dictionaries have the same set of associations?
is_equal (other: DICTIONARY [V_, K_]): BOOLEAN

Do both dictionaries have the same set of associations?
is_equal_map (other: DICTIONARY [V_, K_]): BOOLEAN

Do both collections have the same lower, upper, and items?

Display support:

out_in_tagged_out_memory

Append terse printable representation of current object in tagged_out_memory.

Agents based features:

for_each (action: PROCEDURE[TUPLE[TUPLE 2[V_, K_]]])

Apply action to every [V_, K_] associations of Current.
do_all (action: ROUTINE[TUPLE[TUPLE 2[V_, K_]]])

Apply action to every [V_, K_] associations of Current.
for_all (test: FUNCTION[TUPLE[TUPLE 2[V_, K_]]]): BOOLEAN

Do all [V_, K_] associations satisfy test?
exists (test: FUNCTION[TUPLE[TUPLE 2[V_, K_]]]): BOOLEAN

Does at least one [V_, K_] association satisfy test?
aggregate (action: FUNCTION[TUPLE[TUPLE 3[V_, V_, K_], V_]], initial: V_): V_

Aggregate all the elements starting from the initial value.

Other features:

internal_key (k: K_): K_

Retrieve the internal key object which correspond to the existing entry k (the one memorized into the Current dictionary).

{}

keys_memory: DICTIONARY_KEY_TRAVERSER[V_, K_]

{}

_inline_agent43 (v: V_, k: K_)

enumerate: ENUMERATE[E_]

Other features:

get_new_iterator: ITERATOR[E_]

generation: INTEGER_32

{}

next_generation

Counting:

count: INTEGER_32

Number of available items in the hoard.

{}

_inline_agent1 (a: ROUTINE[TUPLE[TUPLE 1[E_]]], e: E_)

Indexing:

valid_index (i: INTEGER_32): BOOLEAN

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

put (v: V_, k: K_) assign at

deferred procedure

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

deferred procedure

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

deferred procedure

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)

set_item (v: V_, index: INTEGER_32)

deferred procedure

require

valid_index(index)

ensure

count = old count
v = item(index)

remove (k: K_)

deferred procedure

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

deferred procedure

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

See also remove, clear_count.

require

k /= Void

ensure

not fast_has(k)

clear_count

deferred procedure

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

is_empty: count = 0
capacity = old capacity

clear_count_and_capacity

deferred procedure

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

is_empty: count = 0
capacity <= old capacity

capacity: INTEGER_32

deferred function

Approximation of the actual internal storage capacity.

The capacity will grow automatically when needed (i.e. capacity is not a limit for the number of values stored). Also note that the capacity value may not be always accurate depending of the implementation (anyway, this capacity value is at least equals to count).

copy (other: DICTIONARY [V_, K_])

effective procedure

Reinitialize by copying all associations of other.

require

not immutable
same_dynamic_type(other)

not immutable
same_dynamic_type(other)

ensure

is_equal(other)

new_iterator_on_items: ITERATOR[V_]

effective function

ensure

Result /= Void
Result /= Void
Result /= Void
Result.generation = generation

make

deferred procedure

{}

Creates an empty dictionary.

ensure

is_empty

manifest_make (needed_capacity: INTEGER_32)

effective procedure

{}

Manifest creation of a dictionary.

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

effective procedure

{}

require

not has(k)

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.

require

k1 /= Void
k2 /= Void

is_empty: BOOLEAN

effective function

Is it empty?

ensure

definition: Result = count = 0

has (k: K_): BOOLEAN

deferred function

Is there a value currently associated with key k?

See also fast_has, at.

require

k /= Void

at (k: K_): V_

deferred function

Return the value associated to key k.

See also fast_at, reference_at, has.

require

has(k)

infix "@" (k: K_): V_

frozen

effective function

The infix notation which is actually a synonym for at.

require

has(k)

ensure

definition: Result = at(k)

reference_at (k: K_): V_

deferred function

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

deferred function

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_

deferred function

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_

deferred function

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)

occurrences (v: V_): INTEGER_32

effective function

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

Number of occurrences using basic = for comparison.

See also occurrences, fast_has, has.

ensure

Result >= 0

key_at (v: V_): K_

effective function

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}).test(at(Result), v)

fast_key_at (v: V_): K_

effective function

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

See also key_at, at.

require

fast_occurrences(v) = 1

ensure

at(Result) = v

lower: INTEGER_32

is 1

constant attribute

Minimum index.

See also upper, valid_index, item.

upper: INTEGER_32

effective function

Maximum index.

See also lower, valid_index, item.

ensure

count = Result - lower + 1

item (index: INTEGER_32): V_

deferred function

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_

deferred function

require

valid_index(index)

ensure

at(Result) = item(index)

first: V_

effective function

The very first item.

See also last, item.

require

not is_empty

ensure

definition: Result = item(lower)

last: V_

effective function

The last item.

See also first, item.

require

not is_empty

ensure

definition: Result = item(upper)

new_iterator_on_keys: ITERATOR[K_]

deferred function

ensure

Result /= Void

new_iterator: ITERATOR[TUPLE 2[V_, K_]]

deferred function

ensure

Result /= Void

key_map_in (buffer: COLLECTION[K_])

effective procedure

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

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

keys: TRAVERSABLE[K_]

effective function

An iterable of this map keys

ensure

Result.count = count

items: TRAVERSABLE[V_]

effective function

An iterable of this map values Usually returns Current because MAP is TRAVERSABLE.

ensure

Result.count = count

fast_is_equal (other: DICTIONARY [V_, K_]): BOOLEAN

effective function

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

Result implies count = other.count

is_equal (other: DICTIONARY [V_, K_]): BOOLEAN

effective function

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: DICTIONARY [V_, K_]): BOOLEAN

effective function

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

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

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

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

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

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

Aggregate all the elements starting from the initial value.

See also for_each, for_all, exists.

require

action /= Void

internal_key (k: K_): K_

deferred function

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)

keys_memory: DICTIONARY_KEY_TRAVERSER[V_, K_]

writable attribute

{}

_inline_agent43 (v: V_, k: K_)

frozen

effective procedure

{}

enumerate: ENUMERATE[E_]

effective function

get_new_iterator: ITERATOR[E_]

frozen

effective function

This feature is obsolete: Use `new_iterator' instead. This historical SmartEiffel feature is badly named.

generation: INTEGER_32

writable attribute

next_generation

effective procedure

{}

ensure

generation > old generation

count: INTEGER_32

deferred function

Number of available items in the hoard.

See also is_empty

ensure

Result >= 0

_inline_agent1 (a: ROUTINE[TUPLE[TUPLE 1[E_]]], e: E_)

frozen

effective procedure

{}

valid_index (i: INTEGER_32): BOOLEAN

effective function

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

See also lower, upper, item.

ensure

definition: Result = lower <= i and i <= upper