indexing
description: "Cursor trees implemented in two-way linked representation"
legal: "See notice at end of class."
status: "See notice at end of class."
names: two_way_cursor_tree, cursor_tree
access: cursor, membership
representation: recursive, linked
contents: generic
date: "$Date: 2006-01-22 18:25:44 -0800 (Sun, 22 Jan 2006) $"
revision: "$Revision: 56675 $"
class interface
TWO_WAY_CURSOR_TREE [G]
create
make
ensure
is_above: above
is_empty: is_empty
make_root (v: G)
`v'
feature
make
ensure
is_above: above
is_empty: is_empty
make_root (v: G)
`v'
feature {ANY}
default_create
ANY
feature
child_item (i: INTEGER_32): G
`i'
CURSOR_TREE
require CURSOR_TREE
argument_within_bounds: i >= 1 and then i <= arity
not_off: not off
cursor: TWO_WAY_CURSOR_TREE_CURSOR [G]
require CURSOR_STRUCTURE
True
ensure CURSOR_STRUCTURE
cursor_not_void: Result /= Void
generating_type: STRING_8
ANY
generator: STRING_8
ANY
has (v: G): BOOLEAN
`v'
object_comparison
CURSOR_TREE
require CONTAINER
True
ensure CONTAINER
not_found_in_empty: Result implies not is_empty
index_of (v: like item; i: INTEGER_32): INTEGER_32
`i'`v'
object_comparison
LINEAR
require LINEAR
positive_occurrences: i > 0
ensure LINEAR
non_negative_result: Result >= 0
item: G
RECURSIVE_CURSOR_TREE
require TRAVERSABLE
not_off: not off
require ACTIVE
readable: readable
occurrences (v: G): INTEGER_32
CURSOR_TREE
require BAG
True
require LINEAR
True
ensure BAG
non_negative_occurrences: Result >= 0
parent_item: G
CURSOR_TREE
require CURSOR_TREE
not_on_root: not is_root
search (v: like item)
item`v'
object_comparison
exhausted
LINEAR
ensure LINEAR
object_found: (not exhausted and object_comparison) implies equal (v, item)
item_found: (not exhausted and not object_comparison) implies v = item
feature
arity: INTEGER_32
above
RECURSIVE_CURSOR_TREE
require HIERARCHICAL
not_off: not off
require else RECURSIVE_CURSOR_TREE
valid_cursor: not off or else above
breadth: INTEGER_32
CURSOR_TREE
count: INTEGER_32
RECURSIVE_CURSOR_TREE
depth: INTEGER_32
CURSOR_TREE
level: INTEGER_32
CURSOR_TREE
feature
frozen deep_equal (some: ANY; other: like arg #1): BOOLEAN
`some'`other'
ANY
ensure ANY
shallow_implies_deep: standard_equal (some, other) implies Result
both_or_none_void: (some = Void) implies (Result = (other = Void))
same_type: (Result and (some /= Void)) implies some.same_type (other)
symmetric: Result implies deep_equal (other, some)
frozen equal (some: ANY; other: like arg #1): BOOLEAN
`some'`other'
ANY
ensure ANY
definition: Result = (some = Void and other = Void) or else ((some /= Void and other /= Void) and then some.is_equal (other))
is_equal (other: like Current): BOOLEAN
`other'
ANY
require ANY
other_not_void: other /= Void
ensure ANY
symmetric: Result implies other.is_equal (Current)
consistent: standard_is_equal (other) implies Result
frozen standard_equal (some: ANY; other: like arg #1): BOOLEAN
`some'`other'
ANY
ensure ANY
definition: Result = (some = Void and other = Void) or else ((some /= Void and other /= Void) and then some.standard_is_equal (other))
frozen standard_is_equal (other: like Current): BOOLEAN
`other'
ANY
require ANY
other_not_void: other /= Void
ensure ANY
same_type: Result implies same_type (other)
symmetric: Result implies other.standard_is_equal (Current)
feature
above: BOOLEAN
RECURSIVE_CURSOR_TREE
after: BOOLEAN
RECURSIVE_CURSOR_TREE
before: BOOLEAN
RECURSIVE_CURSOR_TREE
below: BOOLEAN
CURSOR_TREE
changeable_comparison_criterion: BOOLEAN
object_comparison
CONTAINER
conforms_to (other: ANY): BOOLEAN
`other'
ANY
require ANY
other_not_void: other /= Void
exhausted: BOOLEAN
LINEAR
ensure LINEAR
exhausted_when_off: off implies Result
extendible: BOOLEAN
RECURSIVE_CURSOR_TREE
require COLLECTION
True
full: BOOLEAN is False
is_empty: BOOLEAN
RECURSIVE_CURSOR_TREE
is_inserted (v: G): BOOLEAN
`v'
`has (v)'
COLLECTION
is_leaf: BOOLEAN
is_root: BOOLEAN
RECURSIVE_CURSOR_TREE
isfirst: BOOLEAN
RECURSIVE_CURSOR_TREE
islast: BOOLEAN
RECURSIVE_CURSOR_TREE
object_comparison: BOOLEAN
equal`='
`='
CONTAINER
off: BOOLEAN
is_empty
CURSOR_TREE
require TRAVERSABLE
True
prunable: BOOLEAN is True
readable: BOOLEAN
CURSOR_TREE
same_type (other: ANY): BOOLEAN
`other'
ANY
require ANY
other_not_void: other /= Void
ensure ANY
definition: Result = (conforms_to (other) and other.conforms_to (Current))
valid_cursor (p: CURSOR): BOOLEAN
`p'
RECURSIVE_CURSOR_TREE
valid_cursor_index (i: INTEGER_32): BOOLEAN
`i'
arity
CURSOR_TREE
writable: BOOLEAN
CURSOR_TREE
feature
compare_objects
equal
`='
CONTAINER
require CONTAINER
changeable_comparison_criterion: changeable_comparison_criterion
ensure CONTAINER
object_comparison
compare_references
`='
equal
CONTAINER
require CONTAINER
changeable_comparison_criterion: changeable_comparison_criterion
ensure CONTAINER
reference_comparison: not object_comparison
feature
back
RECURSIVE_CURSOR_TREE
breadth_forth
off
CURSOR_TREE
require CURSOR_TREE
not_off: not off
down (i: INTEGER_32)
`i'
after`i'arity
before`i'
RECURSIVE_CURSOR_TREE
require HIERARCHICAL
not_off: not off
argument_within_bounds: i >= 1 and i <= arity
require else CURSOR_TREE
not_before: not before
not_after: not after
not_below: not below
valid_cursor_index: (above and i = 0) or else valid_cursor_index (i)
ensure then CURSOR_TREE
gone_before: (i = 0) implies before
forth
RECURSIVE_CURSOR_TREE
go_last_child
CURSOR_TREE
require LINEAR
True
require else CURSOR_TREE
not_above: not above
go_to (p: CURSOR)
`p'
RECURSIVE_CURSOR_TREE
require CURSOR_STRUCTURE
cursor_position_valid: valid_cursor (p)
level_back
CURSOR_TREE
level_forth
CURSOR_TREE
postorder_forth
off
CURSOR_TREE
require CURSOR_TREE
not_off: not off
postorder_start
CURSOR_TREE
preorder_forth
off
CURSOR_TREE
require LINEAR
not_after: not after
start
offis_empty
CURSOR_TREE
require TRAVERSABLE
True
ensure then CURSOR_TREE
on_root_unless_empty: not is_empty implies is_root
start_on_level (l: INTEGER_32)
`l'
CURSOR_TREE
require CURSOR_TREE
argument_within_bounds: l >= 1 and then depth >= l
ensure CURSOR_TREE
level_expected: level = l
is_first: isfirst
up
aboveis_root
RECURSIVE_CURSOR_TREE
require HIERARCHICAL
not_off: not off
require else CURSOR_TREE
not_above: not above
ensure then CURSOR_TREE
not_before: not before
not_after: not after
not_below: not below
coherency: (not old off and above) = (old is_root)
feature
fill (other: CURSOR_TREE [G])
`other'
`other'
CURSOR_TREE
require CURSOR_TREE
is_empty: is_empty
container_fill (other: CONTAINER [G])
`other'
`other'
COLLECTION
require COLLECTION
other_not_void: other /= Void
extendible: extendible
fill_from_active (other: CURSOR_TREE [G])
`other'
CURSOR_TREE
require CURSOR_TREE
cursor_on_leaf: is_leaf
merge_left (other: CURSOR_TREE [G])
`other'
CURSOR_TREE
require CURSOR_TREE
other_exists: other /= Void
not_before: not before
not_above: not above
only_one_root: (level = 1) implies is_empty
merge_right (other: CURSOR_TREE [G])
`other'
CURSOR_TREE
require CURSOR_TREE
other_exists: other /= Void
not_after: not after
not_above: not above
only_one_root: (level = 1) implies is_empty
put (v: G)
`v'
replace
CURSOR_TREE
require COLLECTION
extendible: extendible
ensure COLLECTION
item_inserted: is_inserted (v)
put_child (v: G)
`v'
require
is_leaf: is_leaf
put_left (v: G)
`v'
CURSOR_TREE
require CURSOR_TREE
not_before: not before
not_above: not above
only_one_root: (level = 1) implies is_empty
put_right (v: G)
`v'
require CURSOR_TREE
not_after: not after
not_above: not above
only_one_root: (level = 1) implies is_empty
put_root (v: G)
`v'
require
is_empty: is_empty
ensure
is_root: is_root
count = 1
replace (v: G)
`v'
RECURSIVE_CURSOR_TREE
require ACTIVE
writable: writable
ensure ACTIVE
item_replaced: item = v
feature
remove
RECURSIVE_CURSOR_TREE
require ACTIVE
prunable: prunable
writable: writable
ensure then RECURSIVE_CURSOR_TREE
not_off_unless_empty: is_empty or else not off
wipe_out
RECURSIVE_CURSOR_TREE
require COLLECTION
prunable: prunable
ensure COLLECTION
wiped_out: is_empty
ensure then RECURSIVE_CURSOR_TREE
cursor_above: above
feature
linear_representation: LINEAR [G]
LINEAR
require CONTAINER
True
feature
child_tree (i: INTEGER_32): like Current
`i'
CURSOR_TREE
require CURSOR_TREE
argument_within_bounds: i >= 1 and then i <= arity
not_off: not off
copy (other: like Current)
`other'
ANY
require ANY
other_not_void: other /= Void
type_identity: same_type (other)
ensure ANY
is_equal: is_equal (other)
frozen deep_copy (other: like Current)
copy`other'deep_twin
ANY
require ANY
other_not_void: other /= Void
ensure ANY
deep_equal: deep_equal (Current, other)
frozen deep_twin: like Current
ANY
ensure ANY
deep_equal: deep_equal (Current, Result)
parent_tree: like Current
CURSOR_TREE
require CURSOR_TREE
not_on_root: not is_root
not_off: not off
frozen standard_copy (other: like Current)
`other'
ANY
require ANY
other_not_void: other /= Void
type_identity: same_type (other)
ensure ANY
is_standard_equal: standard_is_equal (other)
frozen standard_twin: like Current
`other'
ANY
ensure ANY
standard_twin_not_void: Result /= Void
equal: standard_equal (Result, Current)
subtree: like Current
require CURSOR_TREE
not_off: not off
frozen twin: like Current
`Current'
twincopycopy
ANY
ensure ANY
twin_not_void: Result /= Void
is_equal: Result.is_equal (Current)
feature
frozen default: like Current
ANY
frozen default_pointer: POINTER
`POINTER'
`p'default
`p'`POINTER'
ANY
default_rescue
ANY
frozen do_nothing
ANY
feature
extend (v: G)
`v'
`v'`first_child'below
before
RECURSIVE_CURSOR_TREE
require COLLECTION
extendible: extendible
ensure COLLECTION
item_inserted: is_inserted (v)
ensure then BAG
one_more_occurrence: occurrences (v) = old (occurrences (v)) + 1
feature
do_all (action: PROCEDURE [ANY, TUPLE [G]])
`action'
`action'
TRAVERSABLE
require TRAVERSABLE
action_exists: action /= Void
linear_do_all (action: PROCEDURE [ANY, TUPLE [G]])
`action'
`action'
LINEAR
require TRAVERSABLE
action_exists: action /= Void
do_if (action: PROCEDURE [ANY, TUPLE [G]]; test: FUNCTION [ANY, TUPLE [G], BOOLEAN])
`action'`test'
`action'`test'
TRAVERSABLE
require TRAVERSABLE
action_exists: action /= Void
test_exits: test /= Void
linear_do_if (action: PROCEDURE [ANY, TUPLE [G]]; test: FUNCTION [ANY, TUPLE [G], BOOLEAN])
`action'`test'
`action'`test'
LINEAR
require TRAVERSABLE
action_exists: action /= Void
test_exits: test /= Void
linear_for_all (test: FUNCTION [ANY, TUPLE [G], BOOLEAN]): BOOLEAN
`test'
`test'
LINEAR
require TRAVERSABLE
test_exits: test /= Void
ensure then LINEAR
empty: is_empty implies Result
for_all (test: FUNCTION [ANY, TUPLE [G], BOOLEAN]): BOOLEAN
`test'
TRAVERSABLE
require TRAVERSABLE
test_exits: test /= Void
there_exists (test: FUNCTION [ANY, TUPLE [G], BOOLEAN]): BOOLEAN
`test'
TRAVERSABLE
require TRAVERSABLE
test_exits: test /= Void
linear_there_exists (test: FUNCTION [ANY, TUPLE [G], BOOLEAN]): BOOLEAN
`test'
`test'
LINEAR
require TRAVERSABLE
test_exits: test /= Void
feature
io: STD_FILES
ANY
out: STRING_8
ANYtagged_out
ANY
print (some: ANY)
`some'
ANY
frozen tagged_out: STRING_8
ANYout
ANY
feature
operating_environment: OPERATING_ENVIRONMENT
ANY
feature {ANY}
frozen internal_correct_mismatch
`correct_mismatch'
ANY
invariant
RECURSIVE_CURSOR_TREE
coherency: not above implies active_parent.child = active
CURSOR_TREE
non_negative_depth: depth >= 0
non_negative_breadth: breadth >= 0
is_leaf_definition: not off implies is_leaf = (arity = 0)
above_property: above implies (arity <= 1)
on_tree: (isfirst or islast or is_leaf or is_root) implies not off
off_definition: off = after or before or above or below
below_constraint: below implies ((after or before) and not above)
above_constraint: above implies not (before or after or below)
after_constraint: after implies not (before or above)
before_constaint: before implies not (after or above)
empty_below_constraint: (is_empty and (after or before)) implies below
HIERARCHICAL
non_negative_successor_count: arity >= 0
TRAVERSABLE
empty_constraint: is_empty implies off
ANY
reflexive_equality: standard_is_equal (Current)
reflexive_conformance: conforms_to (Current)
ACTIVE
writable_constraint: writable implies readable
empty_constraint: is_empty implies (not readable) and (not writable)
LINEAR
after_constraint: after implies off
indexing
library: "EiffelBase: Library of reusable components for Eiffel."
copyright: "Copyright (c) 1984-2006, Eiffel Software and others"
license: "Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)"
source: "[
Eiffel Software
356 Storke Road, Goleta, CA 93117 USA
Telephone 805-685-1006, Fax 805-685-6869
Website http://www.eiffel.com
Customer support http://support.eiffel.com
]"
end TWO_WAY_CURSOR_TREE