GNU
|
Liberty Eiffel
|
Automated Tests
|
Wiki
|
Savannah project
|
Debian packages
|
Documentation
>
libraries
>
AVL_TREE
+
Point of view
All features
ANY
All features
deferred class AVL_TREE [E_]
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:
ABSTRACT_AVL_DICTIONARY
,
ABSTRACT_AVL_SET
Class invariant
top
map
/= Void
not
map_dirty
implies
map
.count =
count
count
> 0 implies
root
/= Void and then
root
.count =
count
lost_nodes
/= Void
Overview
top
Features
{
ANY
}
debug_string
:
STRING
count
:
INTEGER_32
Adding and removing:
{
ANY
}
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:
{
ANY
}
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
: RECYCLING_POOL[AVL_TREE_NODE[E_]]
lost_nodes_memory
: RECYCLING_POOL[AVL_TREE_NODE[E_]]
lost_nodes_pool
:
HASHED_DICTIONARY
[
RECYCLING_POOL
[
AVL_TREE_NODE_ANY
],
FIXED_STRING
]
ordered
(e1: E_, e2: E_):
BOOLEAN
True if [e1, e2] is a correctly ordered sequence; usually, e1 < e2
{}
balanced
:
INTEGER_32
imbalanced_left
:
INTEGER_32
imbalanced_right
:
INTEGER_32
debug_string
:
STRING
effective function
{
ANY
}
top
count
:
INTEGER_32
writable attribute
{
ANY
}
top
remove
(e: E_)
effective procedure
{
ANY
}
top
fast_remove
(e: E_)
effective procedure
{
ANY
}
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
{
ANY
}
top
Is element
e
in the set?
fast_has
(e: E_):
BOOLEAN
effective function
{
ANY
}
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_])
effective procedure
{}
top
require
n /= Void
lost_nodes
: RECYCLING_POOL[AVL_TREE_NODE[E_]]
effective function
{}
top
lost_nodes_memory
: RECYCLING_POOL[AVL_TREE_NODE[E_]]
writable attribute
{}
top
lost_nodes_pool
:
HASHED_DICTIONARY
[
RECYCLING_POOL
[
AVL_TREE_NODE_ANY
],
FIXED_STRING
]
once function
{}
top
ordered
(e1: E_, e2: E_):
BOOLEAN
deferred function
{}
top
True if [e1, e2] is a correctly ordered sequence; usually, e1 < e2
require
e1 /= Void
e2 /= Void
balanced
:
INTEGER_32
is 0
constant attribute
{}
top
imbalanced_left
:
INTEGER_32
is -1
constant attribute
{}
top
imbalanced_right
:
INTEGER_32
is 1
constant attribute
{}
top