+
Point of view
All features
class AVL_SET [E_ -> COMPARABLE]
Summary
top
Direct parents
Inherit list: ABSTRACT_AVL_SET
Class invariant
top
Overview
top
Creation features
Features
{}
  • ordered (e1: E_, e2: E_): BOOLEAN
    True if [e1, e2] is a correctly ordered sequence; usually, e1 < e2
  • a_new_node: AVL_SET_NODE[E_]
{ANY}
{}
{}
Counting:
{ANY}
Adding and removing:
{ANY}
  • remove (e: E_)
    Remove item e from the set: the mathematical definition of removing from a set is followed.
  • fast_remove (e: E_)
    Same job as remove, but uses basic = for comparison.
Looking and searching:
{ANY}
To provide iterating facilities:
{ANY}
Mathematical operations:
{ANY}
Comparison:
{ANY}
{ANY}
  • copy (other: AVL_SET [E_ -> COMPARABLE])
    Copy 'other' into the current set
  • from_collection (model: TRAVERSABLE[E_])
    Add all items of model.
Implement manifest generic creation:
{}
{ANY}
Other features:
{ANY}
Agent-based features:
{ANY}
Printing:
{ANY}
{ANY}
{}
Counting:
{ANY}
Agent-based features:
{ANY}
{}
Indexing:
{ANY}
{ANY}
  • test (e1: E_, e2: E_): BOOLEAN
    In order to avoid run-time type errors, feature safe_equal calls is_equal only when e1 and e2 have exactly the same dynamic type.
  • safe_equal (e1: E_, e2: E_): BOOLEAN
    In order to avoid run-time type errors, feature safe_equal calls is_equal only when e1 and e2 have exactly the same dynamic type.
{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.
{}
{}
ordered (e1: E_, e2: E_): BOOLEAN
effective function
{}
top
True if [e1, e2] is a correctly ordered sequence; usually, e1 < e2
require
  • e1 /= Void
  • e2 /= Void
a_new_node: AVL_SET_NODE[E_]
effective function
{}
top
new_iterator: ITERATOR[E_]
effective function
{ANY}
top
ensure
  • Result /= Void
  • Result.generation = generation
add (e: E_)
effective procedure
{ANY}
top
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.
require
  • e /= Void
ensure
  • added: has(e)
  • not_in_then_added: not old has(e) implies count = old count + 1
  • in_then_not_added: old has(e) implies count = old count
fast_add (e: E_)
effective procedure
{ANY}
top
Same job as add, but uses basic = for comparison.
require
  • e /= Void
ensure
  • added: has(e)
  • not_in_then_added: not old has(e) implies count = old count + 1
  • in_then_not_added: old has(e) implies count = old count
clear_count
effective procedure
{ANY}
top
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.
ensure
  • is_empty: count = 0
clear_count_and_capacity
effective procedure
{ANY}
top
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.
ensure
  • is_empty: count = 0
reference_at (e: E_): E_
effective function
{ANY}
top
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).
require
  • e /= Void
  • elements_are_not_expanded: Result = Void
ensure
  • has(e) implies Result.is_equal(e)
item (index: INTEGER_32): E_
effective function
{ANY}
top
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.
require
  • valid_index(index)
ensure
  • has(Result)
set_item (n: ABSTRACT_AVL_SET_NODE[E_])
effective procedure
{}
top
set_value (n: ABSTRACT_AVL_SET_NODE[E_])
effective procedure
{}
top
exchange_and_discard (n1: ABSTRACT_AVL_SET_NODE[E_], n2: ABSTRACT_AVL_SET_NODE[E_])
effective procedure
{}
top
require
  • n1 /= Void
  • n2 /= Void
ensure
  • map_dirty
  • count = old count - 1
  • rebalance
make
effective procedure
{}
top
Creation of an empty SET.
ensure
  • is_empty
is_empty: BOOLEAN
effective function
{ANY}
top
Is the set empty?
ensure
  • definition: Result = count = 0
remove (e: E_)
deferred procedure
{ANY}
top
Remove item e from the set: the mathematical definition of removing from a set is followed.
require
  • e /= Void
ensure
fast_remove (e: E_)
deferred procedure
{ANY}
top
Same job as remove, but uses basic = for comparison.
require
  • e /= Void
ensure
has (e: E_): BOOLEAN
deferred function
{ANY}
top
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.
require
  • e /= Void
ensure
fast_has (e: E_): BOOLEAN
deferred function
{ANY}
top
Is element e actually stored in the set?
Warning: this query is using basic = for comparison. See also has when dealing with reference types.
require
  • e /= Void
ensure
lower: INTEGER_32
is 1
constant attribute
{ANY}
top
Minimum index.
See also upper, valid_index, item.
upper: INTEGER_32
effective function
{ANY}
top
Maximum index.
See also lower, valid_index, item.
ensure
first: E_
effective function
{ANY}
top
The very first item.
See also last, item.
require
  • not is_empty
ensure
  • definition: Result = item(lower)
last: E_
effective function
{ANY}
top
The last item.
See also first, item.
require
  • not is_empty
ensure
  • definition: Result = item(upper)
union (other: AVL_SET [E_ -> COMPARABLE])
effective procedure
{ANY}
top
Make the union of the Current set with other.
require
  • other /= Void
ensure
fast_union (other: AVL_SET [E_ -> COMPARABLE])
effective procedure
{ANY}
top
Make the union of the Current set with other.
require
  • other /= Void
ensure
infix "+" (other: AVL_SET [E_ -> COMPARABLE]): AVL_SET [E_ -> COMPARABLE]
effective function
{ANY}
top
Return the union of the Current set with other.
require
  • other /= Void
ensure
intersection (other: AVL_SET [E_ -> COMPARABLE])
effective procedure
{ANY}
top
Make the intersection of the Current set with other.
require
  • other /= Void
ensure
fast_intersection (other: AVL_SET [E_ -> COMPARABLE])
effective procedure
{ANY}
top
Make the intersection of the Current set with other.
require
  • other /= Void
ensure
infix "^" (other: AVL_SET [E_ -> COMPARABLE]): AVL_SET [E_ -> COMPARABLE]
effective function
{ANY}
top
Return the intersection of the Current set with other.
require
  • other /= Void
ensure
minus (other: AVL_SET [E_ -> COMPARABLE])
effective procedure
{ANY}
top
Make the set Current - other.
require
  • other /= Void
ensure
fast_minus (other: AVL_SET [E_ -> COMPARABLE])
effective procedure
{ANY}
top
Make the set Current - other.
require
  • other /= Void
ensure
infix "-" (other: AVL_SET [E_ -> COMPARABLE]): AVL_SET [E_ -> COMPARABLE]
effective function
{ANY}
top
Return the set Current - other.
require
  • other /= Void
ensure
is_subset_of (other: AVL_SET [E_ -> COMPARABLE]): BOOLEAN
effective function
{ANY}
top
Is the Current set a subset of other?
require
  • other /= Void
ensure
is_disjoint_from (other: AVL_SET [E_ -> COMPARABLE]): BOOLEAN
effective function
{ANY}
top
Is the Current set disjoint from other ?
require
  • other /= Void
ensure
is_equal (other: AVL_SET [E_ -> COMPARABLE]): BOOLEAN
effective function
{ANY}
top
Is the Current set equal to other?
require
    • other /= Void
      • other /= Void
      • other /= Void
ensure
  • double_inclusion: Result = is_subset_of(other) and other.is_subset_of(Current)
  • commutative: generating_type = other.generating_type implies Result = other.is_equal(Current)
copy (other: AVL_SET [E_ -> COMPARABLE])
effective procedure
{ANY}
top
Copy 'other' into the current set
require
    • not immutable
    • same_dynamic_type(other)
      • not immutable
      • same_dynamic_type(other)
      • not immutable
      • same_dynamic_type(other)
ensure
  • is_equal(other)
from_collection (model: TRAVERSABLE[E_])
effective procedure
{ANY}
top
Add all items of model.
require
  • model /= Void
manifest_make (needed_capacity: INTEGER_32)
effective procedure
{}
top
Manifest creation of a SET.
manifest_put (index: INTEGER_32, element: E_)
effective procedure
{}
top
manifest_semicolon_check: BOOLEAN
is False
constant attribute
{}
top
enumerate: ENUMERATE[E_]
effective function
{ANY}
top
get_new_iterator: ITERATOR[E_]
frozen
effective function
{ANY}
top
This feature is obsolete: Use `new_iterator' instead. This historical SmartEiffel feature is badly named.
for_each (action: PROCEDURE[TUPLE[TUPLE 1[E_]]])
effective procedure
{ANY}
top
Apply action to every item of Current.
See also for_all, exists, aggregate.
require
  • action /= Void
for_all (test: FUNCTION[TUPLE[TUPLE 1[E_]]]): BOOLEAN
effective function
{ANY}
top
Do all items satisfy test?
See also for_each, exists, aggregate.
require
  • test /= Void
exists (test: FUNCTION[TUPLE[TUPLE 1[E_]]]): BOOLEAN
effective function
{ANY}
top
Does at least one item satisfy test?
See also for_each, for_all, aggregate.
require
  • test /= Void
aggregate (action: FUNCTION[TUPLE[TUPLE 2[E_, E_], E_]], initial: E_): E_
effective function
{ANY}
top
Aggregate all the elements starting from the initial value.
See also for_each, for_all, exists.
require
  • action /= Void
out_in_tagged_out_memory
effective procedure
{ANY}
top
Append terse printable representation of current object in tagged_out_memory.
require
  • 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))
generation: INTEGER_32
writable attribute
{ANY}
top
next_generation
effective procedure
{}
top
ensure
count: INTEGER_32
deferred function
{ANY}
top
Number of available items in the hoard.
See also is_empty
ensure
  • Result >= 0
do_all (action: ROUTINE[TUPLE[TUPLE 1[E_]]])
frozen
effective procedure
{ANY}
top
Apply action to every item of Current.
This feature is obsolete: Use `for_each` instead. This feature is not secure because it accepts a FUNCTION, the result of which is lost.
_inline_agent1 (a: ROUTINE[TUPLE[TUPLE 1[E_]]], e: E_)
frozen
effective procedure
{}
top
valid_index (i: INTEGER_32): BOOLEAN
effective function
{ANY}
top
True when i is valid (i.e., inside actual bounds).
See also lower, upper, item.
ensure
test (e1: E_, e2: E_): BOOLEAN
effective function
{ANY}
top
In order to avoid run-time type errors, feature safe_equal calls is_equal only when e1 and e2 have exactly the same dynamic type.
safe_equal (e1: E_, e2: E_): BOOLEAN
effective function
{ANY}
top
In order to avoid run-time type errors, feature safe_equal calls is_equal only when e1 and e2 have exactly the same dynamic type.
debug_string: STRING
effective function
{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
fast_do_insert (n: AVL_TREE_NODE[E_]): AVL_TREE_NODE[E_]
effective function
{}
top
ensure
do_insert (n: AVL_TREE_NODE[E_]): AVL_TREE_NODE[E_]
effective function
{}
top
ensure
left_grown (n: AVL_TREE_NODE[E_]): AVL_TREE_NODE[E_]
effective function
{}
top
require ensure
right_grown (n: AVL_TREE_NODE[E_]): AVL_TREE_NODE[E_]
effective function
{}
top
require ensure
fast_do_remove (n: AVL_TREE_NODE[E_], e: E_): AVL_TREE_NODE[E_]
effective function
{}
top
ensure
do_remove (n: AVL_TREE_NODE[E_], e: E_): AVL_TREE_NODE[E_]
effective function
{}
top
ensure
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
left_shrunk (n: AVL_TREE_NODE[E_]): AVL_TREE_NODE[E_]
effective function
{}
top
require ensure
right_shrunk (n: AVL_TREE_NODE[E_]): AVL_TREE_NODE[E_]
effective function
{}
top
require ensure
clear_nodes (node: AVL_TREE_NODE[E_])
effective procedure
{}
top
node_height (node: AVL_TREE_NODE[E_]): INTEGER_32
effective function
{}
top
build_map
effective procedure
{}
top
require ensure
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
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
once function
{}
top
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