home
wiki
classes/clusters list
class information
+
Point of view
All features
ANY
INTERNALS_HANDLER
All features
deferred class AVL_TREE [E_ ->
COMPARABLE
]
Summary
top
Definition of a mathematical set of comparable objects. All common operations on mathematical sets are available.
Direct parents
insert list:
AVL_CONSTANTS
Known children
insert list:
AVL_DICTIONARY
,
AVL_SET
Class invariant
top
map
/= Void
not
map_dirty
implies
map
.count =
count
count
> 0 implies
root
/= Void and then
root
.count =
count
Overview
top
features
debug_string
:
STRING
count
:
INTEGER_32
Adding and removing:
remove
(e: E_)
fast_remove
(e: E_)
root
:
AVL_TREE_NODE
[E_]
rebalance
:
BOOLEAN
item_memory
: E_
set_value_and_key
(n:
AVL_TREE_NODE
[E_])
set_value
(n:
AVL_TREE_NODE
[E_])
fast_do_insert
(n:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
do_insert
(n:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
left_grown
(n:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
right_grown
(n:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
fast_do_remove
(n:
AVL_TREE_NODE
[E_], e: E_):
AVL_TREE_NODE
[E_]
do_remove
(n:
AVL_TREE_NODE
[E_], e: E_):
AVL_TREE_NODE
[E_]
remove_right
(n1:
AVL_TREE_NODE
[E_], n2:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
left_shrunk
(n:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
right_shrunk
(n:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
exchange_and_discard
(n1:
AVL_TREE_NODE
[E_], n2:
AVL_TREE_NODE
[E_])
clear_nodes
(node:
AVL_TREE_NODE
[E_])
node_height
(node:
AVL_TREE_NODE
[E_]):
INTEGER_32
Looking and searching:
has
(e: E_):
BOOLEAN
Is element
e
in the set?
fast_has
(e: E_):
BOOLEAN
Is element
e
in the set?
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.
new_node
:
AVL_TREE_NODE
[E_]
a_new_node
:
AVL_TREE_NODE
[E_]
discard_node
(n:
AVL_TREE_NODE
[E_])
lost_nodes
:
WEAK_REFERENCE
[
AVL_TREE_NODE
[E_]]
balanced
:
INTEGER_32
imbalanced_left
:
INTEGER_32
imbalanced_right
:
INTEGER_32
debug_string
:
STRING
effective function
top
count
:
INTEGER_32
writable attribute
top
remove
(e: E_)
effective procedure
top
fast_remove
(e: E_)
effective procedure
top
root
:
AVL_TREE_NODE
[E_]
writable attribute
top
rebalance
:
BOOLEAN
writable attribute
top
item_memory
: E_
writable attribute
top
set_value_and_key
(n:
AVL_TREE_NODE
[E_])
deferred procedure
top
set_value
(n:
AVL_TREE_NODE
[E_])
deferred procedure
top
fast_do_insert
(n:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
effective function
top
ensure
Result /= Void
Result.balance =
node_height
(Result.right) -
node_height
(Result.left)
rebalance
=
node_height
(Result) > old
node_height
(n)
do_insert
(n:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
effective function
top
ensure
Result /= Void
Result.balance =
node_height
(Result.right) -
node_height
(Result.left)
rebalance
=
node_height
(Result) > old
node_height
(n)
left_grown
(n:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
effective function
top
require
rebalance
n /= Void
node_height
(n.right) -
node_height
(n.left) + 1 = n.balance
ensure
Result /= Void
Result.balance =
node_height
(Result.right) -
node_height
(Result.left)
rebalance
=
node_height
(Result) > 1 + old
node_height
(n.right).max(
node_height
(n.left) - 1)
right_grown
(n:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
effective function
top
require
rebalance
n /= Void
node_height
(n.right) - 1 -
node_height
(n.left) = n.balance
ensure
Result /= Void
Result.balance =
node_height
(Result.right) -
node_height
(Result.left)
rebalance
=
node_height
(Result) > 1 + old
node_height
(n.left).max(
node_height
(n.right) - 1)
fast_do_remove
(n:
AVL_TREE_NODE
[E_], e: E_):
AVL_TREE_NODE
[E_]
effective function
top
ensure
Result = Void or else Result.balance =
node_height
(Result.right) -
node_height
(Result.left)
rebalance
=
node_height
(Result) < old
node_height
(n)
do_remove
(n:
AVL_TREE_NODE
[E_], e: E_):
AVL_TREE_NODE
[E_]
effective function
top
ensure
Result = Void or else Result.balance =
node_height
(Result.right) -
node_height
(Result.left)
rebalance
=
node_height
(Result) < old
node_height
(n)
remove_right
(n1:
AVL_TREE_NODE
[E_], n2:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
effective function
top
require
n1 /= Void
n2 /= Void
ensure
Result = Void or else Result.balance =
node_height
(Result.right) -
node_height
(Result.left)
rebalance
=
node_height
(Result) < old
node_height
(n2)
left_shrunk
(n:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
effective function
top
require
rebalance
n /= Void
node_height
(n.right) -
node_height
(n.left) - 1 = n.balance
ensure
Result /= Void
Result.balance =
node_height
(Result.right) -
node_height
(Result.left)
rebalance
=
node_height
(Result) < 1 + old
node_height
(n.right).max(
node_height
(n.left) + 1)
right_shrunk
(n:
AVL_TREE_NODE
[E_]):
AVL_TREE_NODE
[E_]
effective function
top
require
rebalance
n /= Void
node_height
(n.right) + 1 -
node_height
(n.left) = n.balance
ensure
Result /= Void
Result.balance =
node_height
(Result.right) -
node_height
(Result.left)
rebalance
=
node_height
(Result) < 1 + old
node_height
(n.left).max(
node_height
(n.right) + 1)
exchange_and_discard
(n1:
AVL_TREE_NODE
[E_], n2:
AVL_TREE_NODE
[E_])
deferred procedure
top
require
n1 /= Void
n2 /= Void
ensure
map_dirty
count
= old
count
- 1
rebalance
clear_nodes
(node:
AVL_TREE_NODE
[E_])
effective procedure
top
node_height
(node:
AVL_TREE_NODE
[E_]):
INTEGER_32
effective function
top
has
(e: E_):
BOOLEAN
effective function
top
Is element
e
in the set?
fast_has
(e: E_):
BOOLEAN
effective function
top
Is element
e
in the set?
build_map
effective procedure
top
require
build_needed:
map_dirty
ensure
build_done:
not
map_dirty
map
:
FAST_ARRAY
[
AVL_TREE_NODE
[E_]]
writable attribute
top
Elements in a row for iteration.
See
build_map
.
map_dirty
:
BOOLEAN
writable attribute
top
True when the map needs to be built again for the iterators.
See
build_map
.
new_node
:
AVL_TREE_NODE
[E_]
effective function
top
a_new_node
:
AVL_TREE_NODE
[E_]
deferred function
top
discard_node
(n:
AVL_TREE_NODE
[E_])
deferred procedure
top
require
n /= Void
lost_nodes
:
WEAK_REFERENCE
[
AVL_TREE_NODE
[E_]]
writable attribute
top
balanced
:
INTEGER_32
constant attribute
top
imbalanced_left
:
INTEGER_32
constant attribute
top
imbalanced_right
:
INTEGER_32
constant attribute
top