indexing
description: "[
Trees where each node has a fixed number of children
(The number of children is arbitrary but cannot be
changed once the node has been created
]"
legal: "See notice at end of class."
status: "See notice at end of class."
names: fixed_tree, tree, fixed_list
representation: recursive, array
access: cursor, membership
contents: generic
date: "$Date: 2006-09-15 17:28:10 -0700 (Fri, 15 Sep 2006) $"
revision: "$Revision: 63620 $"
class interface
FIXED_TREE [G]
create
make (n: INTEGER_32; v: G)
`n'`v'
require
valid_number_of_children: n >= 0
ensure
node_item: item = v
node_arity: arity = 0
make_filled (n: INTEGER_32; v: G)
`n'`v'
require
valid_number_of_children: n >= 0
ensure
node_item: item = v
node_arity: arity = n
feature
make (n: INTEGER_32; v: G)
`n'`v'
require
valid_number_of_children: n >= 0
ensure
node_item: item = v
node_arity: arity = 0
make_filled (n: INTEGER_32; v: G)
`n'`v'
require
valid_number_of_children: n >= 0
ensure
node_item: item = v
node_arity: arity = n
feature
arity: INTEGER_32
array_item (n: INTEGER_32): FIXED_TREE [G]
array_make (min_index: INTEGER_32; max_index: INTEGER_32)
capacity: INTEGER_32
child: like parent
require TREE
readable: readable_child
child_after: BOOLEAN
child_back
child_before: BOOLEAN
child_cursor: CURSOR
child_finish
child_forth
child_go_i_th (i: INTEGER_32)
ensure then TREE
position: child_index = i
child_go_to (p: CURSOR)
child_index: INTEGER_32
ensure TREE
valid_index: Result >= 0 and Result <= arity + 1
child_item: like item
require TREE
readable: child_readable
child_off: BOOLEAN
child_start
first_child: like parent
require TREE
is_not_leaf: not is_leaf
generating_type: STRING_8
ANY
generator: STRING_8
ANY
index_of (v: FIXED_TREE [like item]; i: INTEGER_32): INTEGER_32
item: G
CELL
last_child: like first_child
require TREE
is_not_leaf: not is_leaf
left_sibling: like parent
require TREE
is_not_root: not is_root
ensure TREE
is_sibling: Result /= Void implies is_sibling (Result)
right_is_current: (Result /= Void) implies (Result.right_sibling = Current)
parent: FIXED_TREE [G]
prune (n: like parent)
require TREE
is_child: n.parent = Current
ensure TREE
n_is_root: n.is_root
put_i_th (v: FIXED_TREE [like item]; n: INTEGER_32)
right_sibling: like parent
require TREE
is_not_root: not is_root
ensure TREE
is_sibling: Result /= Void implies is_sibling (Result)
left_is_current: (Result /= Void) implies (Result.left_sibling = Current)
search_child (v: FIXED_TREE [like item])
wipe_out
ensure TREE
is_leaf: is_leaf
feature
count: INTEGER_32
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'
object_comparison
TREE
require ANY
other_not_void: other /= Void
ensure ANY
symmetric: Result implies other.is_equal (Current)
consistent: standard_is_equal (other) implies Result
node_is_equal (other: like Current): BOOLEAN
`other'
TREE
require TREE
other_not_void: other /= Void
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
changeable_comparison_criterion: BOOLEAN
object_comparison
CONTAINER
child_contractable: BOOLEAN
ensure
Result = not child_off
child_isfirst: BOOLEAN
TREE
ensure TREE
not_is_leaf: Result implies not is_leaf
child_islast: BOOLEAN
TREE
ensure TREE
not_is_leaf: Result implies not is_leaf
child_readable: BOOLEAN
child_item
TREE
child_writable: BOOLEAN
child_item
TREE
conforms_to (other: ANY): BOOLEAN
`other'
ANY
require ANY
other_not_void: other /= Void
full: BOOLEAN is True
has (v: G): BOOLEAN
`v'
object_comparison
TREE
ensure CONTAINER
not_found_in_empty: Result implies not is_empty
is_empty: BOOLEAN
TREE
is_leaf: BOOLEAN
TREE
is_root: BOOLEAN
TREE
is_sibling (other: like parent): BOOLEAN
`other'
TREE
require TREE
other_exists: other /= Void
ensure TREE
not_root: Result implies not is_root
other_not_root: Result implies not other.is_root
same_parent: Result = not is_root and other.parent = parent
object_comparison: BOOLEAN
equal`='
`='
CONTAINER
readable: BOOLEAN is True
TREE
readable_child: BOOLEAN
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_index (i: INTEGER_32): BOOLEAN
`i'
TREE
ensure TREE
valid_cursor_index_definition: Result = (i >= 0) and (i <= child_capacity + 1)
writable: BOOLEAN is True
TREE
writable_child: BOOLEAN
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
child_put (v: like item)
`v'
FIXED_TREEchild_replace
require TREE
child_writable: child_writable
ensure TREE
item_inserted: child_item = v
child_replace (v: like item)
`v'
FIXED_TREEchild_put
require TREE
child_writable: child_writable
ensure TREE
item_inserted: child_item = v
fill (other: TREE [G])
`other'
`other'
TREE
put (v: like item)
`v'item
CELLreplace
CELL
require TREE
is_writable: writable
ensure TREE
item_inserted: item = v
ensure CELL
item_inserted: item = v
put_child (n: like parent)
`n'
require TREE
non_void_argument: n /= Void
require else
not_full: arity < capacity
ensure then
child_replaced: n.parent = Current
put_left (v: like item)
`v'
require
is_not_root: not is_root
has_left_sibling: left_sibling /= Void
ensure
item_put: left_sibling.item = v
put_left_sibling (other: like parent)
`other'
require
is_not_root: not is_root
has_left_sibling: left_sibling /= Void
ensure
left_sibling_replaced: left_sibling = other
put_right (v: like item)
`v'
require
is_not_root: not is_root
has_right_sibling: right_sibling /= Void
ensure
item_put: right_sibling.item = v
put_right_sibling (other: like parent)
`other'
require
is_not_root: not is_root
has_right_sibling: right_sibling /= Void
ensure
right_sibling_replaced: right_sibling = other
replace (v: like item)
`v'item
CELLput
CELL
require TREE
is_writable: writable
ensure TREE
item_inserted: item = v
ensure CELL
item_inserted: item = v
replace_child (n: like parent)
`n'
require TREE
writable_child: writable_child
ensure TREE
child_replaced: child = n
ensure then
child_replaced: n.parent = Current
sprout
TREE
feature
forget_left
forget_right
remove_child
ensure then
child_removed: child = Void
feature
binary_representation: BINARY_TREE [G]
TREE
ensure TREE
result_is_root: Result.is_root
result_has_no_right_child: not Result.has_right
linear_representation: LINEAR [G]
TREE
feature
copy (other: like Current)
`other'
TREE
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)
duplicate (n: INTEGER_32): like Current
`n'aritychild_index
require TREE
not_child_off: not child_off
valid_sublist: n >= 0
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)
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
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
child_capacity: INTEGER_32
invariant
ANY
reflexive_equality: standard_is_equal (Current)
reflexive_conformance: conforms_to (Current)
TREE
tree_consistency: child_readable implies child.parent = Current
leaf_definition: is_leaf = (arity = 0)
child_off_definition: child_off = child_before or child_after
child_before_definition: child_before = (child_index = 0)
child_isfirst_definition: child_isfirst = (not is_leaf and child_index = 1)
child_islast_definition: child_islast = (not is_leaf and child_index = child_capacity)
child_after_definition: child_after = (child_index >= child_capacity + 1)
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 FIXED_TREE