+
Point of view
All features
class EXT_AVL_DICTIONARY [V_, K_]
Summary
Associative memory. Values of type V_ are stored using Keys of type K_.
Efficient implementation of DICTIONARY using an AVL balanced tree. AVL stands for the names of G. M. Adel'son-Velskii and E. M. Landis, two Russian mathematicians who first came up with this method of keeping the tree balanced.
Direct parents
Inherit list: ABSTRACT_AVL_DICTIONARY
Class invariant
Overview
Creation features
{ANY}
Features
{ANY}
{}
{ANY}
{}
Removing:
{ANY}
  • 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.
Implement manifest generic creation:
{}
{}
Counting:
{ANY}
Basic access:
{ANY}
  • has (k: K_): BOOLEAN
    Is there a value currently associated with key k?
  • infix "@" (k: K_): V_
    The infix notation which is actually a synonym for at.
  • fast_has (k: K_): BOOLEAN
    Is there a value currently associated with key k?
To provide iterating facilities:
{ANY}
  • lower: INTEGER_32
    Minimum index.
  • upper: INTEGER_32
    Maximum index.
  • first: V_
    The very first item.
  • last: V_
    The last item.
  • 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.
{ANY}
  • fast_is_equal (other: EXT_AVL_DICTIONARY [V_, K_]): BOOLEAN
    Do both dictionaries have the same set of associations?
  • is_equal (other: EXT_AVL_DICTIONARY [V_, K_]): BOOLEAN
    Do both dictionaries have the same set of associations?
  • is_equal_map (other: EXT_AVL_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}
{}
Counting:
{ANY}
{}
Indexing:
{ANY}
{ANY}
{}
Iterating internals:
{}
  • build_map
  • map: FAST_ARRAY[AVL_TREE_NODE[E_]]
    Elements in a row for iteration.
  • map_dirty: BOOLEAN
    True when the map needs to be built again for the iterators.
{}
{}
order: FUNCTION[TUPLE[TUPLE 2[K_, K_]]]
writable attribute
{ANY}
ordered (k1: K_, k2: K_): BOOLEAN
effective function
{}
True if [e1, e2] is a correctly ordered sequence; usually, e1 < e2
require
  • k1 /= Void
  • k2 /= Void
a_new_node: EXT_AVL_DICTIONARY_NODE[V_, K_]
effective function
{}
make (a_order: FUNCTION[TUPLE[TUPLE 2[K_, K_]]])
effective procedure
{}
require
  • a_order /= Void
ensure
capacity: INTEGER_32
is 0
constant attribute
{ANY}
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).
at (k: K_): V_
effective function
{ANY}
Return the value associated to key k.
See also fast_at, reference_at, has.
require
  • has(k)
fast_at (k: K_): V_
effective function
{ANY}
Return the value associated to key k using basic = for comparison.
require
  • fast_has(k)
reference_at (k: K_): V_
effective function
{ANY}
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_reference_at (k: K_): V_
effective function
{ANY}
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}
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)
add (v: V_, k: K_)
effective procedure
{ANY}
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)
fast_put (v: V_, k: K_)
effective procedure
{ANY}
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)
occurrences (v: V_): INTEGER_32
effective function
{ANY}
Number of occurrences using is_equal for comparison.
ensure
  • Result >= 0
fast_occurrences (v: V_): INTEGER_32
effective function
{ANY}
Number of occurrences using basic = for comparison.
See also occurrences, fast_has, has.
ensure
  • Result >= 0
key_at (v: V_): K_
effective function
{ANY}
Retrieve the key used for value v using is_equal for comparison.
See also fast_key_at, at.
require
  • occurrences(v) = 1
ensure
fast_key_at (v: V_): K_
effective function
{ANY}
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_count
effective procedure
{ANY}
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
effective procedure
{ANY}
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
set_item (v: V_, index: INTEGER_32)
effective procedure
{ANY}
require
  • valid_index(index)
ensure
  • count = old count
  • v = item(index)
item (index: INTEGER_32): V_
effective function
{ANY}
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}
require
  • valid_index(index)
ensure
  • at(Result) = item(index)
new_iterator_on_keys: ITERATOR[K_]
effective function
{ANY}
ensure
  • Result /= Void
new_iterator_on_items: ITERATOR[V_]
effective function
{ANY}
ensure
  • Result /= Void
  • Result /= Void
  • Result /= Void
  • Result.generation = generation
new_iterator: ITERATOR[TUPLE 2[V_, K_]]
effective function
{ANY}
ensure
  • Result /= Void
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).
See also has, fast_has.
require
  • has(k)
ensure
  • Result.is_equal(k)
copy (other: EXT_AVL_DICTIONARY [V_, K_])
effective procedure
{ANY}
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)
value_memory: V_
writable attribute
{}
set_value_and_key (n: ABSTRACT_AVL_DICTIONARY_NODE[V_, K_])
effective procedure
{}
set_value (n: ABSTRACT_AVL_DICTIONARY_NODE[V_, K_])
effective procedure
{}
exchange_and_discard (n1: ABSTRACT_AVL_DICTIONARY_NODE[V_, K_], n2: ABSTRACT_AVL_DICTIONARY_NODE[V_, K_])
effective procedure
{}
require
  • n1 /= Void
  • n2 /= Void
ensure
  • map_dirty
  • count = old count - 1
  • rebalance
default_create
effective procedure
{}
Default creation method.
It is used when no creation method is specified if allowed. Note it may be renamed.
remove (k: K_)
deferred procedure
{ANY}
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
fast_remove (k: K_)
deferred procedure
{ANY}
Same job as remove, but uses basic = for comparison.
See also remove, clear_count.
require
  • k /= Void
ensure
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
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
{ANY}
Is it empty?
ensure
  • definition: Result = count = 0
has (k: K_): BOOLEAN
deferred function
{ANY}
Is there a value currently associated with key k?
See also fast_has, at.
require
  • k /= Void
infix "@" (k: K_): V_
frozen
effective function
{ANY}
The infix notation which is actually a synonym for at.
require ensure
  • definition: Result = at(k)
fast_has (k: K_): BOOLEAN
deferred function
{ANY}
Is there a value currently associated with key k?
Using basic = for comparison.
See also has, at, fast_at.
require
  • k /= Void
lower: INTEGER_32
is 1
constant attribute
{ANY}
Minimum index.
See also upper, valid_index, item.
upper: INTEGER_32
effective function
{ANY}
Maximum index.
See also lower, valid_index, item.
ensure
first: V_
effective function
{ANY}
The very first item.
See also last, item.
require
  • not is_empty
ensure
  • definition: Result = item(lower)
last: V_
effective function
{ANY}
The last item.
See also first, item.
require
  • not is_empty
ensure
  • definition: Result = item(upper)
key_map_in (buffer: COLLECTION[K_])
effective procedure
{ANY}
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}
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
{ANY}
An iterable of this map keys
ensure
items: TRAVERSABLE[V_]
effective function
{ANY}
An iterable of this map values Usually returns Current because MAP is TRAVERSABLE.
ensure
fast_is_equal (other: EXT_AVL_DICTIONARY [V_, K_]): BOOLEAN
effective function
{ANY}
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: EXT_AVL_DICTIONARY [V_, K_]): BOOLEAN
effective function
{ANY}
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: EXT_AVL_DICTIONARY [V_, K_]): BOOLEAN
effective function
{ANY}
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}
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}
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}
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}
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}
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}
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
{}
_inline_agent43 (v: V_, k: K_)
frozen
effective procedure
{}
enumerate: ENUMERATE[E_]
effective function
{ANY}
get_new_iterator: ITERATOR[E_]
frozen
effective function
{ANY}
This feature is obsolete: Use `new_iterator' instead. This historical SmartEiffel feature is badly named.
generation: INTEGER_32
writable attribute
{ANY}
next_generation
effective procedure
{}
ensure
count: INTEGER_32
deferred function
{ANY}
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
{ANY}
True when i is valid (i.e., inside actual bounds).
See also lower, upper, item.
ensure
debug_string: STRING
effective function
{ANY}
root: AVL_TREE_NODE[E_]
writable attribute
{}
rebalance: BOOLEAN
writable attribute
{}
item_memory: E_
writable attribute
{}
fast_do_insert (n: AVL_TREE_NODE[E_]): AVL_TREE_NODE[E_]
effective function
{}
ensure
do_insert (n: AVL_TREE_NODE[E_]): AVL_TREE_NODE[E_]
effective function
{}
ensure
left_grown (n: AVL_TREE_NODE[E_]): AVL_TREE_NODE[E_]
effective function
{}
require ensure
right_grown (n: AVL_TREE_NODE[E_]): AVL_TREE_NODE[E_]
effective function
{}
require ensure
fast_do_remove (n: AVL_TREE_NODE[E_], e: E_): AVL_TREE_NODE[E_]
effective function
{}
ensure
do_remove (n: AVL_TREE_NODE[E_], e: E_): AVL_TREE_NODE[E_]
effective function
{}
ensure
remove_right (n1: AVL_TREE_NODE[E_], n2: AVL_TREE_NODE[E_]): AVL_TREE_NODE[E_]
effective function
{}
require
  • n1 /= Void
  • n2 /= Void
ensure
left_shrunk (n: AVL_TREE_NODE[E_]): AVL_TREE_NODE[E_]
effective function
{}
require ensure
right_shrunk (n: AVL_TREE_NODE[E_]): AVL_TREE_NODE[E_]
effective function
{}
require ensure
clear_nodes (node: AVL_TREE_NODE[E_])
effective procedure
{}
node_height (node: AVL_TREE_NODE[E_]): INTEGER_32
effective function
{}
build_map
effective procedure
{}
require ensure
map: FAST_ARRAY[AVL_TREE_NODE[E_]]
writable attribute
{}
Elements in a row for iteration.
See build_map.
map_dirty: BOOLEAN
writable attribute
{}
True when the map needs to be built again for the iterators.
See build_map.
new_node: AVL_TREE_NODE[E_]
effective function
{}
discard_node (n: AVL_TREE_NODE[E_])
effective procedure
{}
require
  • n /= Void
lost_nodes: RECYCLING_POOL[AVL_TREE_NODE[E_]]
effective function
{}
lost_nodes_memory: RECYCLING_POOL[AVL_TREE_NODE[E_]]
writable attribute
{}
once function
{}
balanced: INTEGER_32
is 0
constant attribute
{}
imbalanced_left: INTEGER_32
is -1
constant attribute
{}
imbalanced_right: INTEGER_32
is 1
constant attribute
{}