EiffelBase class
(HTML page generated by ISE Eiffel 4.2)
Eiffel Class
indexing
description: "Trees with a dynamically modifiable structure";
status: "See notice at end of class";
names: dynamic_tree, tree;
representation: recursive;
access: cursor, membership;
contents: generic;
date: "$Date: 2007-03-30 19:10:11 +0000 (Fri, 30 Mar 2007) $";
revision: "$Revision: 95354 $"
deferred class DYNAMIC_TREE [G]
inherit
TREE [G]
redefine
parent
end
feature -- Access
parent: DYNAMIC_TREE [G];
-- Parent of current node.
feature -- Status report
Extendible: BOOLEAN is true;
-- May new items be added?
feature {RECURSIVE_CURSOR_TREE} -- Element change
set_child (n: like parent) is
-- Set the child of parent to n.
require
non_void_argument: n /= void
deferred
end;
feature -- Element change
extend (v: like item) is
-- Add v as new child.
do
child_extend (v)
end;
child_extend (v: like item) is
-- Add v to the list of children.
-- Do not move child cursor.
deferred
end;
child_put_left (v: like item) is
-- Add v to the left of cursor position.
-- Do not move child cursor.
require
not_child_before: notchild_before
deferred
end;
child_put_right (v: like item) is
-- Add v to the right of cursor position.
-- Do not move child cursor.
require
not_child_after: notchild_after
deferred
end;
put_child (n: like parent) is
-- Add n to the list of children.
-- Do not move child cursor.
require
non_void_argument: n /= void
deferred
end;
put_child_left (n: like parent) is
-- Add n to the left of cursor position.
-- Do not move cursor.
require
not_child_before: notchild_before;
non_void_argument: n /= void
deferred
end;
put_child_right (n: like parent) is
-- Add n to the right of cursor position.
-- Do not move cursor.
require
not_child_after: notchild_after;
non_void_argument: n /= void
deferred
end;
merge_tree_before (other: like first_child) is
-- Merge children of other into current structure
-- after cursor position. Do not move cursor.
-- Make other a leaf.
require
not_child_off: notchild_off;
other_exists: (other /= void)
deferred
ensure
other_is_leaf: other.is_leaf
end;
merge_tree_after (other: like first_child) is
-- Merge children of other into current structure
-- after cursor position. Do not move cursor.
-- Make other a leaf.
require
not_child_off: notchild_off;
other_exists: (other /= void)
deferred
ensure
other_is_leaf: other.is_leaf
end;
feature -- Removal
remove_left_child is
-- Remove item to the left of cursor position.
-- Do not move cursor.
require
is_not_first: notchild_isfirst
deferred
ensure
new_arity: arity = old arity - 1;
new_child_index: child_index = old child_index - 1
end;
remove_right_child is
-- Remove item to the right of cursor position.
-- Do not move cursor.
require
is_not_last: notchild_islast
deferred
ensure
new_arity: arity = old arity - 1;
new_child_index: child_index = old child_index
end;
remove_child is
-- Remove child at cursor position.
-- Move cursor to next sibling, or after if none.
require
child_not_off: notchild_off
deferred
ensure
new_arity: arity = old arity - 1;
new_child_index: child_index = old child_index
end;
wipe_out is
-- Remove all child
deferred
end;
feature -- Conversion
fill_from_binary (b: BINARY_TREE [G]) is
-- Fill from a binary tree representation.
-- Left child becomes first child.
-- Right child becomes right sibling.
-- Any right child of b is ignored.
local
current_node: BINARY_TREE [G]
do
replace (b.item);
wipe_out;
if b.has_left then
from
current_node := b.left_child
until
current_node = void
loop
child_put_right (current_node.item);
child_forth;
child.fill_from_binary (current_node);
current_node := current_node.right_child
end
end
end;
feature -- Duplication
duplicate (n: INTEGER): like Current is
-- Copy of sub-tree beginning at cursor position and
-- having min (n, arity - child_index + 1)
-- children
local
pos: CURSOR;
counter: INTEGER
do
from
Result := new_tree;
pos := child_cursor
until
child_after or else (counter = n)
loop
Result.put_child (child.duplicate_all);
child_forth;
counter := counter + 1
end;
child_go_to (pos)
end;
feature {DYNAMIC_TREE} -- Implementation
new_tree: like Current is
-- A newly created instance of the same type.
-- This feature may be redefined in descendants so as to
-- produce an adequately allocated and initialized object.
deferred
ensure
result_exists: Result /= void;
result_item: Result.item = item
end;
duplicate_all: like Current is
-- Copy of sub-tree including all children
local
pos: CURSOR
do
from
Result := new_tree;
pos := child_cursor;
child_start
until
child_off
loop
Result.put_child (child.duplicate_all);
Result.child_forth;
child_forth
end;
child_go_to (pos)
end;
fill_subtree (other: TREE [G]) is
-- Fill children with children of other.
do
from
other.child_start
until
other.child_off
loop
child_extend (other.item);
other.child_forth
end;
from
child_start;
other.child_start
until
child_off
loop
child.fill_subtree (other.child);
other.child_forth;
child_forth
end
end;
invariant
extendible_definition: extendible;
child_after_definition: child_after = (child_index = arity + 1);
end -- class DYNAMIC_TREE
|
