Lisaac prototype interface

Lisaac^TM Platform

AVL_SET

2003-2005 Jérome Boutet, 2003-2007 Benoit Sonntag

Inherit/Insert Summary
`parent_set`
`parent_avl_tree`
`parent_traversable` No developed.
`parent_safe_equal` No developed.
`parent_avl_constants` No developed.

Constructor Summary
`create`

Slot Summary
`add` Add new item e to the set. The mathematical definition of adding in a set is followed, i.e. the element e is added only and only if it is not yet present in the set. As this `add` feature is actually using is_equal, you may consider to use `fast_add` for expanded objects as well while trying to get the very best performances.
`fast_add` Same job as `add`, but uses basic = for comparison.
`clear_count` Empty the current set (`is_empty` is True after that call). If possible, the actual implementation is supposed to keep its internal storage area in order to refill Current in an efficient way. See also `clear_count_and_capacity` to select the most appropriate.
`reference_at` Non Void when e is in the set. In such a situation, Result is the object which is actually stored in the Current set (see ensure assertion).
`item` Item at the corresponding index i. See also `lower`, `upper`, valid_index. SETs are intrinsically unordered, so there is no guarantee that `item`(i) after performing an `add` or `remove` operation is related in any way to `item`(i) before that operation. Item at the corresponding index i. See also `lower`, `upper`, valid_index.
`make` Creation of an empty SET.
`count` Cardinality of the set (i.e. actual `count` of stored elements). Number of available indices. See also `is_empty`, `lower`, `upper`.
`is_empty` Is the set empty? Is collection empty ? See also `count`.
`debug_string`
`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 item e from the set: the mathematical definition of removing from a set is followed.
`fast_remove` Same job as `remove`, but uses basic = for comparison.
`clear`
`clear_count_and_capacity` Empty the current set (`is_empty` is True after that call). If possible, the actual implementation is supposed to release its internal storage area for this memory to be used by other objects. See also `clear_count` to select the most appropriate.

Looking and searching:
`has` Is element e in the set? As this query is actually using is_equal, you may consider to use `fast_has` for expanded objects as well while trying to get the very best performances. Is element e in the set?
`fast_has` Is element e actually stored in the set? Warning: this query is using basic = for comparison. See also `has` when dealing with reference types. Is element e in the set?

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`. SETs are intrinsically unordered, so there is no guarantee that `first` after performing an `add` or `remove` operation is related in any way to `first` before that operation. The very `first` item. See also `last`, `item`.
`last` The `last` item. See also `first`, `item`. SETs are intrinsically unordered, so there is no guarantee that `last` after performing an `add` or `remove` operation is related in any way to `last` before that operation. The `last` item. See also `first`, `item`.

Mathematical operations:
`union` Make the union of the Current set with other.
`fast_union` Make the union of the Current set with other.
`Infix '+'` Return the union of the Current set with other.
`intersection` Make the intersection of the Current set with other.
`fast_intersection` Make the intersection of the Current set with other.
`Infix '^'` Return the intersection of the Current set with other.
`minus` Make the set Current - other.
`Infix '-'` Return the set Current - other.

Comparison:
`is_subset_of` Is the Current set a subset of other?
`is_disjoint_from` Is the Current set disjoint from other ?
`fast_is_disjoint_from` Is the Current set disjoint from other ?
`Infix '=='` Is the Current set equal to other?

Duplication.
`copy` Copy 'other' into the current set
`from_collection` Add all items of model.

Agents based features:
`foreach`
`do_all` Apply action to every item of Self. See also `for_all`, `exists`.
`for_all` Do all items satisfy predicate? See also `do_all`, `exists`.
`exists` Does at least one item satisfy predicate? See also `do_all`, `for_all`.

Iterating internals:
`build_map`

Inherit/Insert Detail

parent_set

.../base/collection/avl_set.li line #10
Section:: Inherit
Profile:: + Self: SELF. parent_set :Expanded SET( V)

parent_avl_tree

.../base/collection/avl_set.li line #12
Section:: Inherit
Profile:: + Self: SELF. parent_avl_tree :Expanded AVL_TREE( V)

parent_traversable

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

parent_safe_equal

.../base/collection/low_level/set.li line #17
Section:: Inherit
Profile:: + Self: SELF. parent_safe_equal : SAFE_EQUAL( V)

parent_avl_constants

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

Constructor Detail

create

.../base/collection/avl_set.li line #93
Section:: Public
Profile:: - Self: SELF. create : SELF

Detail slot

add

.../base/collection/avl_set.li line #16
Section:: Public
Profile:: - Self: SELF. add e : V
Description:: Add new item e to the set. The mathematical definition of adding in a set is followed, i.e. the element e is added only and only if it is not yet present in the set. As this add feature is actually using is_equal, you may consider to use fast_add for expanded objects as well while trying to get the very best performances.

fast_add

.../base/collection/avl_set.li line #22
Section:: Public
Profile:: - Self: SELF. fast_add e : V
Description:: Same job as add, but uses basic = for comparison.

clear_count

.../base/collection/avl_set.li line #28
Section:: Public
Profile:: - Self: SELF. clear_count
Description:: Empty the current set (is_empty is True after that call). If possible, the actual implementation is supposed to keep its internal storage area in order to refill Current in an efficient way.
See also clear_count_and_capacity to select the most appropriate.

reference_at

.../base/collection/avl_set.li line #38
Section:: Public
Profile:: - Self: SELF. reference_at e : V : V
Description:: Non Void when e is in the set. In such a situation, Result is the object which is actually stored in the Current set (see ensure assertion).

item

.../base/collection/avl_set.li line #51
Section:: Public
Profile:: - Self: SELF. item index : INTEGER : V
Description:: Item at the corresponding index i.
See also lower, upper, valid_index.
SETs are intrinsically unordered, so there is no guarantee that item(i) after performing an add or remove operation is related in any way to item(i) before that operation. Item at the corresponding index i.
See also lower, upper, valid_index.

make

.../base/collection/avl_set.li line #101
Section:: Public
Profile:: - Self: SELF. make
Description:: Creation of an empty SET.

count

.../base/collection/low_level/set.li line #24
Section:: Public
Profile:: - Self: SELF. count : INTEGER
Description:: Cardinality of the set (i.e. actual count of stored elements). Number of available indices.
See also is_empty, lower, upper.

is_empty

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

debug_string

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

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/set.li line #71
Section:: Public
Profile:: - Self: SELF. remove e : V
Description:: Remove item e from the set: the mathematical definition of removing from a set is followed.

fast_remove

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

clear

.../base/collection/low_level/set.li line #100
Section:: Public
Profile:: - Self: SELF. clear

clear_count_and_capacity

.../base/collection/low_level/set.li line #116
Section:: Public
Profile:: - Self: SELF. clear_count_and_capacity
Description:: Empty the current set (is_empty is True after that call). If possible, the actual implementation is supposed to release its internal storage area for this memory to be used by other objects.
See also clear_count to select the most appropriate.

Looking and searching:

has

.../base/collection/low_level/set.li line #133
Section:: Public
Profile:: - Self: SELF. has e : V : BOOLEAN
Description:: Is element e in the set? As this query is actually using is_equal, you may consider to use fast_has for expanded objects as well while trying to get the very best performances. Is element e in the set?

fast_has

.../base/collection/low_level/set.li line #149
Section:: Public
Profile:: - Self: SELF. fast_has e : V : BOOLEAN
Description:: Is element e actually stored in the set? Warning: this query is using basic = for comparison.
See also has when dealing with reference types. Is element e in the set?

To provide iterating facilities:

lower

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

upper

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

first

.../base/collection/low_level/set.li line #208
Section:: Public
Profile:: - Self: SELF. first : V
Description:: The very first item.
See also last, item.
SETs are intrinsically unordered, so there is no guarantee that first after performing an add or remove operation is related in any way to first before that operation. The very first item.
See also last, item.

last

.../base/collection/low_level/set.li line #217
Section:: Public
Profile:: - Self: SELF. last : V
Description:: The last item.
See also first, item.
SETs are intrinsically unordered, so there is no guarantee that last after performing an add or remove operation is related in any way to last before that operation. The last item.
See also first, item.

Mathematical operations:

union

.../base/collection/low_level/set.li line #230
Section:: Public
Profile:: - Self: SELF. union other : SELF
Description:: Make the union of the Current set with other.

fast_union

.../base/collection/low_level/set.li line #251
Section:: Public
Profile:: - Self: SELF. fast_union other : SELF
Description:: Make the union of the Current set with other.

Infix '+'

.../base/collection/low_level/set.li line #272
Section:: Public
Profile:: - Self: SELF ' + ' other : SELF : SELF
Description:: Return the union of the Current set with other.

intersection

.../base/collection/low_level/set.li line #288
Section:: Public
Profile:: - Self: SELF. intersection other : SELF
Description:: Make the intersection of the Current set with other.

fast_intersection

.../base/collection/low_level/set.li line #309
Section:: Public
Profile:: - Self: SELF. fast_intersection other : SELF
Description:: Make the intersection of the Current set with other.

Infix '^'

.../base/collection/low_level/set.li line #330
Section:: Public
Profile:: - Self: SELF ' ^ ' other : SELF : SELF
Description:: Return the intersection of the Current set with other.

minus

.../base/collection/low_level/set.li line #346
Section:: Public
Profile:: - Self: SELF. minus other : SELF
Description:: Make the set Current - other.

Infix '-'

.../base/collection/low_level/set.li line #367
Section:: Public
Profile:: - Self: SELF ' - ' other : SELF : SELF
Description:: Return the set Current - other.

Comparison:

is_subset_of

.../base/collection/low_level/set.li line #387
Section:: Public
Profile:: - Self: SELF. is_subset_of other : SELF : BOOLEAN
Description:: Is the Current set a subset of other?

is_disjoint_from

.../base/collection/low_level/set.li line #411
Section:: Public
Profile:: - Self: SELF. is_disjoint_from other : SELF : BOOLEAN
Description:: Is the Current set disjoint from other ?

fast_is_disjoint_from

.../base/collection/low_level/set.li line #440
Section:: Public
Profile:: - Self: SELF. fast_is_disjoint_from other : SELF : BOOLEAN
Description:: Is the Current set disjoint from other ?

Infix '=='

.../base/collection/low_level/set.li line #469
Section:: Public
Profile:: - Self: SELF ' == ' other : SELF : BOOLEAN
Description:: Is the Current set equal to other?

Duplication.

copy

.../base/collection/low_level/set.li line #494
Section:: Public
Profile:: - Self: SELF. copy other : SELF
Description:: Copy 'other' into the current set

from_collection

.../base/collection/low_level/set.li line #509
Section:: Public
Profile:: - Self: SELF. from_collection model : COLLECTION( V)
Description:: Add all items of model.

Agents based features:

foreach

.../base/collection/low_level/set.li line #529
Section:: Public
Profile:: - Self: SELF. foreach action :{ V; }

do_all

.../base/collection/low_level/set.li line #531
Section:: Public
Profile:: - Self: SELF. do_all action :{ V; }
Description:: Apply action to every item of Self.
See also for_all, exists.

for_all

.../base/collection/low_level/set.li line #544
Section:: Public
Profile:: - Self: SELF. for_all predicate : BLOCK : BOOLEAN
Description:: Do all items satisfy predicate?
See also do_all, exists.

exists

.../base/collection/low_level/set.li line #560
Section:: Public
Profile:: - Self: SELF. exists predicate : BLOCK : BOOLEAN
Description:: Does at least one item satisfy predicate?
See also do_all, for_all.

Iterating internals:

build_map

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