Lisaac prototype interface

Lisaac^TM Platform

AVL_DICTIONARY

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.

Inherit/Insert Summary
`parent_avl_tree`
`parent_simple_dictionary`
`parent_avl_constants` No developed.
`parent_dictionary`
`parent_traversable`
`parent_object` No developed.

Constructor Summary
`create`

Slot Summary
`capacity` 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` Return the value associated to key k. See also `fast_at`, `reference_at`, `has`.
`fast_at` Return the value associated to key k using basic = for comparison. See also `at`, `reference_at`, `fast_reference_at`.
`reference_at` Return NULL 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`.
`fast_reference_at` Same work as `reference_at`, but basic = is used for comparison. See also `reference_at`, `at`, `has`.
`put to` 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.
`add to` 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.
`fast_put to` Same job as put, but uses basic = for comparison. See also put, add.
`occurrences` Number of occurrences using is_equal for comparison. See also `fast_occurrences`, `fast_has`, `has`.
`fast_occurrences` Number of occurrences using basic = for comparison. See also `occurrences`, `fast_has`, `has`.
`key_at` Retrieve the key used for value v using is_equal for comparison. See also `fast_key_at`, `at`.
`fast_key_at` Retrieve the key used for value v using = for comparison. See also `key_at`, `at`.
`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`.
`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`.
`item` Item at the corresponding index i. See also `lower`, `upper`, `valid_index`.
`key`
`internal_key` Retrieve the internal key object which correspond to the existing entry k (the one memorized into the Current dictionary). See also `has`, `fast_has`.
`make` Creates an empty dictionary.
`debug_string`
`count` Actual `count` of stored elements. Number of available indices. See also `is_empty`, `lower`, `upper`.
`root`
`rebalance`
`item_memory`
`set_value_and_key`
`set_value`
`fast_do_insert`
`do_insert`
`left_grown`
`right_grown`
`fast_do_remove`
`do_remove`
`remove_right`
`left_shrunk`
`right_shrunk`
`exchange_and_discard`
`clear_nodes`
`node_height`
`map` Elements in a row for iteration. See `build_map`.
`map_dirty` True when the map needs to be built again for the iterators. See `build_map`.
`new_node`
`a_new_node`
`discard_node`

Adding and removing:
`remove` 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`.
`fast_remove` Same job as `remove`, but uses basic = for comparison. See also `remove`, `clear_count`.

Looking and searching:
`has` Is element e in the set? Is there a value currently associated with key k? See also `fast_has`, `at`.
`fast_has` Is element e in the set? Is there a value currently associated with key k? Using basic = for comparison. See also `has`, `at`, `fast_at`.

Iterating internals:
`build_map`

Counting:
`is_empty` Is it empty? Is collection empty ? See also `count`.

To provide iterating facilities:
`lower` Minimum index. See also `upper`, `valid_index`, `item`.
`upper` Maximum index. See also `lower`, `valid_index`, `item`.
`first` The very `first` item. See also `last`, `item`.
`last` The `last` item. See also `first`, `item`.
`key_map_in` Append in buffer, all available keys (this may be useful to speed up the traversal). See also `item_map_in`.
`item_map_in` Append in buffer, all available items (this may be useful to speed up the traversal). See also `key_map_in`.

Comparaison.
`Infix '=='` 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`.
`is_equal_map` Do both dictionaries have the same set of associations? Both keys and values are compared with is_equal. See also is_equal.
`copy` Reinitialize by copying all associations of other.

Agents based features:
`do_all` Apply action to every (V, K) associations of Current. See also `for_all`, exist.
`foreach_pair`
`foreach_key`
`foreach_key until`
`foreach_key while`
`foreach_value`
`foreach_value until`
`foreach_value while`
`for_all` Do all (V, K) associations satisfy test? See also `do_all`, exist.
`exists` Does at least one (V, K) association satisfy test? See also `for_all`, `do_all`.


`key_safe_equal with` Because keys are never NULL, we do not rely on the SAFE_EQUAL class.

Indexing:
`valid_index` True when i is valid (i.e., inside actual bounds). See also `lower`, `upper`, `item`.

Iterate:
`iterate`
`iterate_index`
`iterate_increment`
`iterate_index increment`
`iterate_reverse`

Inherit/Insert Detail

parent_avl_tree

.../base/collection/avl_dictionary.li line #17
Section:: Insert
Profile:: + Self: SELF. parent_avl_tree :Expanded AVL_TREE( K)

parent_simple_dictionary

.../base/collection/avl_dictionary.li line #21
Section:: Inherit
Profile:: + Self: SELF. parent_simple_dictionary :Expanded SIMPLE_DICTIONARY( V, K)

parent_avl_constants

.../base/collection/low_level/avl_tree.li line #13
Section:: Insert
Profile:: - Self: SELF. parent_avl_constants : AVL_CONSTANTS

parent_dictionary

.../base/collection/low_level/simple_dictionary.li line #13
Section:: Inherit
Profile:: + Self: SELF. parent_dictionary :Expanded DICTIONARY( V, K)

parent_traversable

.../base/collection/low_level/dictionary.li line #19
Section:: Inherit
Profile:: + Self: SELF. parent_traversable :Expanded TRAVERSABLE( V)

parent_object

.../base/property/traversable.li line #28
Section:: Inherit
Profile:: - Self: SELF. parent_object : OBJECT

Constructor Detail

create

.../base/collection/low_level/dictionary.li line #645
Section:: Public
Profile:: - Self: SELF. create : SELF

Detail slot

capacity

.../base/collection/avl_dictionary.li line #29
Section:: Public
Profile:: - Self: SELF. capacity : INTEGER
Description:: 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

.../base/collection/avl_dictionary.li line #31
Section:: Public
Profile:: - Self: SELF. at k : K : V
Description:: Return the value associated to key k.
See also fast_at, reference_at, has.

fast_at

.../base/collection/avl_dictionary.li line #37
Section:: Public
Profile:: - Self: SELF. fast_at k : K : V
Description:: Return the value associated to key k using basic = for comparison.
See also at, reference_at, fast_reference_at.

reference_at

.../base/collection/avl_dictionary.li line #43
Section:: Public
Profile:: - Self: SELF. reference_at k : K : V
Description:: Return NULL 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.

fast_reference_at

.../base/collection/avl_dictionary.li line #56
Section:: Public
Profile:: - Self: SELF. fast_reference_at k : K : V
Description:: Same work as reference_at, but basic = is used for comparison.
See also reference_at, at, has.

put to

.../base/collection/avl_dictionary.li line #69
Section:: Public
Profile:: - Self: SELF. put v : V to k : K
Description:: 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.

add to

.../base/collection/avl_dictionary.li line #71
Section:: Public
Profile:: - Self: SELF. add v : V to k : K
Description:: 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.

fast_put to

.../base/collection/avl_dictionary.li line #78
Section:: Public
Profile:: - Self: SELF. fast_put v : V to k : K
Description:: Same job as put, but uses basic = for comparison.
See also put, add.

occurrences

.../base/collection/avl_dictionary.li line #85
Section:: Public
Profile:: - Self: SELF. occurrences v : V : INTEGER
Description:: Number of occurrences using is_equal for comparison.
See also fast_occurrences, fast_has, has.

fast_occurrences

.../base/collection/avl_dictionary.li line #94
Section:: Public
Profile:: - Self: SELF. fast_occurrences v : V : INTEGER
Description:: Number of occurrences using basic = for comparison.
See also occurrences, fast_has, has.

key_at

.../base/collection/avl_dictionary.li line #103
Section:: Public
Profile:: - Self: SELF. key_at v : V : K
Description:: Retrieve the key used for value v using is_equal for comparison.
See also fast_key_at, at.

fast_key_at

.../base/collection/avl_dictionary.li line #105
Section:: Public
Profile:: - Self: SELF. fast_key_at v : V : K
Description:: Retrieve the key used for value v using = for comparison.
See also key_at, at.

clear_count

.../base/collection/avl_dictionary.li line #107
Section:: Public
Profile:: - Self: SELF. clear_count
Description:: 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.

clear_count_and_capacity

.../base/collection/avl_dictionary.li line #109
Section:: Public
Profile:: - Self: SELF. clear_count_and_capacity
Description:: 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.

item

.../base/collection/avl_dictionary.li line #119
Section:: Public
Profile:: - Self: SELF. item i : INTEGER : V
Description:: Item at the corresponding index i.
See also lower, upper, valid_index.

key

.../base/collection/avl_dictionary.li line #128
Section:: Public
Profile:: - Self: SELF. key index : INTEGER : K

internal_key

.../base/collection/avl_dictionary.li line #136
Section:: Public
Profile:: - Self: SELF. internal_key k : K : K
Description:: Retrieve the internal key object which correspond to the existing entry k (the one memorized into the Current dictionary).
See also has, fast_has.

make

.../base/collection/avl_dictionary.li line #138
Section:: Public
Profile:: - Self: SELF. make
Description:: Creates an empty dictionary.

debug_string

.../base/collection/low_level/avl_tree.li line #17
Section:: Public
Profile:: - Self: SELF. debug_string : STRING

count

.../base/collection/low_level/avl_tree.li line #30
Section:: Public
Profile:: + Self: SELF. count : INTEGER
Description:: Actual count of stored elements. Number of available indices.
See also is_empty, lower, upper.

root

.../base/collection/low_level/avl_tree.li line #50
Section:: SELF
Profile:: + Self: SELF. root : AVL_TREE_NODE( V)

rebalance

.../base/collection/low_level/avl_tree.li line #52
Section:: SELF
Profile:: + Self: SELF. rebalance : BOOLEAN

item_memory

.../base/collection/low_level/avl_tree.li line #54
Section:: SELF
Profile:: + Self: SELF. item_memory : V

set_value_and_key

.../base/collection/low_level/avl_tree.li line #56
Section:: SELF
Profile:: - Self: SELF. set_value_and_key n : AVL_TREE_NODE( V)

set_value

.../base/collection/low_level/avl_tree.li line #61
Section:: SELF
Profile:: - Self: SELF. set_value n : AVL_TREE_NODE( V)

fast_do_insert

.../base/collection/low_level/avl_tree.li line #66
Section:: SELF
Profile:: - Self: SELF. fast_do_insert n : AVL_TREE_NODE( V) : AVL_TREE_NODE( V)

do_insert

.../base/collection/low_level/avl_tree.li line #103
Section:: SELF
Profile:: - Self: SELF. do_insert n : AVL_TREE_NODE( V) : AVL_TREE_NODE( V)

left_grown

.../base/collection/low_level/avl_tree.li line #140
Section:: SELF
Profile:: - Self: SELF. left_grown n : AVL_TREE_NODE( V) : AVL_TREE_NODE( V)

right_grown

.../base/collection/low_level/avl_tree.li line #193
Section:: SELF
Profile:: - Self: SELF. right_grown n : AVL_TREE_NODE( V) : AVL_TREE_NODE( V)

fast_do_remove

.../base/collection/low_level/avl_tree.li line #247
Section:: SELF
Profile:: - Self: SELF. fast_do_remove ( n : AVL_TREE_NODE( V), e : V) : AVL_TREE_NODE( V)

do_remove

.../base/collection/low_level/avl_tree.li line #292
Section:: SELF
Profile:: - Self: SELF. do_remove ( n : AVL_TREE_NODE( V), e : V) : AVL_TREE_NODE( V)

remove_right

.../base/collection/low_level/avl_tree.li line #333
Section:: SELF
Profile:: - Self: SELF. remove_right ( n1 : AVL_TREE_NODE( V), n2 : AVL_TREE_NODE( V)) : AVL_TREE_NODE( V)

left_shrunk

.../base/collection/low_level/avl_tree.li line #359
Section:: SELF
Profile:: - Self: SELF. left_shrunk n : AVL_TREE_NODE( V) : AVL_TREE_NODE( V)

right_shrunk

.../base/collection/low_level/avl_tree.li line #417
Section:: SELF
Profile:: - Self: SELF. right_shrunk n : AVL_TREE_NODE( V) : AVL_TREE_NODE( V)

exchange_and_discard

.../base/collection/low_level/avl_tree.li line #474
Section:: SELF
Profile:: - Self: SELF. exchange_and_discard ( n1 : AVL_TREE_NODE( V), n2 : AVL_TREE_NODE( V))

clear_nodes

.../base/collection/low_level/avl_tree.li line #488
Section:: SELF
Profile:: - Self: SELF. clear_nodes node : AVL_TREE_NODE( V)

node_height

.../base/collection/low_level/avl_tree.li line #499
Section:: SELF
Profile:: - Self: SELF. node_height node : AVL_TREE_NODE( V) : INTEGER

map

.../base/collection/low_level/avl_tree.li line #547
Section:: SELF
Profile:: + Self: SELF. map : FAST_ARRAY( AVL_TREE_NODE( V))
Description:: Elements in a row for iteration. See build_map.

map_dirty

.../base/collection/low_level/avl_tree.li line #550
Section:: SELF
Profile:: + Self: SELF. map_dirty : BOOLEAN
Description:: True when the map needs to be built again for the iterators. See build_map.

new_node

.../base/collection/low_level/avl_tree.li line #556
Section:: SELF
Profile:: - Self: SELF. new_node : AVL_TREE_NODE( V)

a_new_node

.../base/collection/low_level/avl_tree.li line #561
Section:: SELF
Profile:: - Self: SELF. a_new_node : AVL_TREE_NODE( V)

discard_node

.../base/collection/low_level/avl_tree.li line #567
Section:: SELF
Profile:: - Self: SELF. discard_node n : AVL_TREE_NODE( V)

Adding and removing:

remove

.../base/collection/low_level/avl_tree.li line #38
Section:: Public
Profile:: - Self: SELF. remove e : V
Description:: 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.

fast_remove

.../base/collection/low_level/avl_tree.li line #43
Section:: Public
Profile:: - Self: SELF. fast_remove e : V
Description:: Same job as remove, but uses basic = for comparison.
See also remove, clear_count.

Looking and searching:

has

.../base/collection/low_level/avl_tree.li line #514
Section:: Public
Profile:: - Self: SELF. has e : V : BOOLEAN
Description:: Is element e in the set? Is there a value currently associated with key k?
See also fast_has, at.

fast_has

.../base/collection/low_level/avl_tree.li line #520
Section:: Public
Profile:: - Self: SELF. fast_has e : V : BOOLEAN
Description:: Is element e in the set? Is there a value currently associated with key k? Using basic = for comparison.
See also has, at, fast_at.

Iterating internals:

build_map

.../base/collection/low_level/avl_tree.li line #532
Section:: SELF
Profile:: - Self: SELF. build_map

Counting:

is_empty

.../base/collection/low_level/dictionary.li line #34
Section:: Public
Profile:: - Self: SELF. is_empty : BOOLEAN
Description:: Is it empty? Is collection empty ?
See also count.

To provide iterating facilities:

lower

.../base/collection/low_level/dictionary.li line #342
Section:: Public
Profile:: - Self: SELF. lower : INTEGER
Description:: Minimum index.
See also upper, valid_index, item.

upper

.../base/collection/low_level/dictionary.li line #344
Section:: Public
Profile:: - Self: SELF. upper : INTEGER
Description:: Maximum index.
See also lower, valid_index, item.

first

.../base/collection/low_level/dictionary.li line #362
Section:: Public
Profile:: - Self: SELF. first : V
Description:: The very first item.
See also last, item.

last

.../base/collection/low_level/dictionary.li line #364
Section:: Public
Profile:: - Self: SELF. last : V
Description:: The last item.
See also first, item.

key_map_in

.../base/collection/low_level/dictionary.li line #379
Section:: Public
Profile:: - Self: SELF. key_map_in buffer : COLLECTION( K)
Description:: Append in buffer, all available keys (this may be useful to speed up the traversal).
See also item_map_in.

item_map_in

.../base/collection/low_level/dictionary.li line #399
Section:: Public
Profile:: - Self: SELF. item_map_in buffer : COLLECTION( V)
Description:: Append in buffer, all available items (this may be useful to speed up the traversal).
See also key_map_in.

Comparaison.

Infix '=='

.../base/collection/low_level/dictionary.li line #423
Section:: Public
Profile:: - Self: SELF ' == ' other : SELF : BOOLEAN
Description:: 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.

is_equal_map

.../base/collection/low_level/dictionary.li line #455
Section:: Public
Profile:: - Self: SELF. is_equal_map other : SELF : BOOLEAN
Description:: Do both dictionaries have the same set of associations? Both keys and values are compared with is_equal.
See also is_equal.

copy

.../base/collection/low_level/dictionary.li line #486
Section:: Public
Profile:: - Self: SELF. copy other : SELF
Description:: Reinitialize by copying all associations of other.

Agents based features:

do_all

.../base/collection/low_level/dictionary.li line #503
Section:: Public
Profile:: - Self: SELF. do_all action :{( V, K); }
Description:: Apply action to every (V, K) associations of Current.
See also for_all, exist.

foreach_pair

.../base/collection/low_level/dictionary.li line #520
Section:: Public
Profile:: - Self: SELF. foreach_pair action :{( K, V); }

foreach_key

.../base/collection/low_level/dictionary.li line #527
Section:: Public
Profile:: - Self: SELF. foreach_key action :{ K; }

foreach_key until

.../base/collection/low_level/dictionary.li line #534
Section:: Public
Profile:: - Self: SELF. foreach_key action :{ K; } until test :{ K; BOOLEAN}

foreach_key while

.../base/collection/low_level/dictionary.li line #544
Section:: Public
Profile:: - Self: SELF. foreach_key action :{ K; } while test :{ K; BOOLEAN}

foreach_value

.../base/collection/low_level/dictionary.li line #554
Section:: Public
Profile:: - Self: SELF. foreach_value action :{ V; }

foreach_value until

.../base/collection/low_level/dictionary.li line #561
Section:: Public
Profile:: - Self: SELF. foreach_value action :{ V; } until test :{ V; BOOLEAN}

foreach_value while

.../base/collection/low_level/dictionary.li line #571
Section:: Public
Profile:: - Self: SELF. foreach_value action :{ V; } while test :{ V; BOOLEAN}

for_all

.../base/collection/low_level/dictionary.li line #581
Section:: Public
Profile:: - Self: SELF. for_all test :{( V, K); } : BOOLEAN
Description:: Do all (V, K) associations satisfy test?
See also do_all, exist.

exists

.../base/collection/low_level/dictionary.li line #601
Section:: Public
Profile:: - Self: SELF. exists test :{( V, K); } : BOOLEAN
Description:: Does at least one (V, K) association satisfy test?
See also for_all, do_all.

key_safe_equal with

.../base/collection/low_level/dictionary.li line #666
Section:: Public
Profile:: - Self: SELF. key_safe_equal k1 : K with k2 : K : BOOLEAN
Description:: Because keys are never NULL, we do not rely on the SAFE_EQUAL class.

Indexing:

valid_index

.../base/property/traversable.li line #54
Section:: Public
Profile:: - Self: SELF. valid_index i : INTEGER : BOOLEAN
Description:: True when i is valid (i.e., inside actual bounds).
See also lower, upper, item.

Iterate:

iterate

.../base/property/traversable.li line #140
Section:: Public
Profile:: - Self: SELF. iterate : ITERATOR( V)

iterate_index

.../base/property/traversable.li line #142
Section:: Public
Profile:: - Self: SELF. iterate_index idx : INTEGER : ITERATOR( V)

iterate_increment

.../base/property/traversable.li line #145
Section:: Public
Profile:: - Self: SELF. iterate_increment inc : INTEGER : ITERATOR( V)

iterate_index increment

.../base/property/traversable.li line #148
Section:: Public
Profile:: - Self: SELF. iterate_index idx : INTEGER increment inc : INTEGER : ITERATOR( V)

iterate_reverse

.../base/property/traversable.li line #151
Section:: Public
Profile:: - Self: SELF. iterate_reverse : ITERATOR( V)