EiffelBase class
(HTML page generated by ISE Eiffel 4.2)
Eiffel Class
indexing
description: "Sorted sets implemented as binary search trees";
status: "See notice at end of class";
names: binary_search_tree_set, set, binary_search_tree;
representation: recursive, array;
access: membership, min, max;
contents: generic;
date: "$Date: 2007-03-30 19:10:11 +0000 (Fri, 30 Mar 2007) $";
revision: "$Revision: 95354 $"
class BINARY_SEARCH_TREE_SET [G -> COMPARABLE]
inherit
COMPARABLE_SET [G]
redefine
min, max, has
end
creation
make
feature -- Initialization
make is
do
before := true
end;
feature -- Access
has (v: like item): BOOLEAN is
-- Is there a node with item v in tree?
-- (Reference or object equality,
-- based on object_comparison.)
do
if tree /= void then
if object_comparison then
tree.compare_objects
else
tree.compare_references
end;
Result := tree.has (v)
end
end;
feature -- Measurement
count: INTEGER is
-- Number of items in tree
do
if tree /= void then
Result := tree.count
end
end;
min: like item is
-- Minimum item in tree
do
Result := tree.min
end;
max: like item is
-- Maximum item in tree
do
Result := tree.max
end;
item: G is
do
Result := active_node.item
end;
feature -- Status report
empty: BOOLEAN is
do
Result := tree = void
end;
Extendible: BOOLEAN is true;
-- Can new items be added? (Answer: yes.)
Prunable: BOOLEAN is true;
-- Can items be removed? (Answer: yes.)
after: BOOLEAN;
-- Is there no valid cursor position to the right of cursor?
before: BOOLEAN;
-- Is there no valid cursor position to the left of cursor?
feature -- Cursor movement
start is
do
before := false;
if tree = void then
after := true
else
after := false;
active_node := tree.min_node
end
end;
finish is
do
after := false;
if tree = void then
before := true
else
before := false;
active_node := tree.max_node
end
end;
forth is
local
new_node, prev_node: like tree
do
if before then
before := false;
if empty then
after := true
end
else
if active_node.has_right then
active_node := active_node.right_child.min_node
else
prev_node := active_node;
active_node := active_node.parent;
from
until
active_node = void or else prev_node = active_node.left_child
loop
prev_node := active_node;
active_node := active_node.parent
end;
if active_node = void then
active_node := tree;
after := true
end
end
end
end;
back is
local
new_node, prev_node: like tree
do
if after then
after := false;
if empty then
before := true
end
else
if tree.has_left then
active_node := active_node.left_child.max_node
else
prev_node := active_node;
active_node := active_node.parent;
from
until
active_node = void or else prev_node = active_node.right_child
loop
prev_node := active_node;
active_node := active_node.parent
end;
if active_node = void then
active_node := tree;
before := true
end
end
end
end;
feature -- Comparison
is_subset (other: like Current): BOOLEAN is
-- Is current structure a subset of other?
do
if other.tree /= void then
Result := tree = void or else tree.is_subset (other.tree)
else
Result := true
end
end;
feature -- Element change
put (v: like item) is
-- Put v at proper position in set
-- (unless one already exists).
-- Was declared in BINARY_SEARCH_TREE_SET as synonym of put and extend.
require
item_exists: v /= void
do
if tree = void then
tree := new_tree (v)
else
tree.extend (v)
end
end;
extend (v: like item) is
-- Put v at proper position in set
-- (unless one already exists).
-- Was declared in BINARY_SEARCH_TREE_SET as synonym of put and extend.
require
item_exists: v /= void
do
if tree = void then
tree := new_tree (v)
else
tree.extend (v)
end
end;
feature -- Removal
wipe_out is
-- Remove all items.
do
tree := void
end;
prune (v: like item) is
do
if tree /= void then
tree := tree.pruned (v)
end
end;
feature -- Duplication
duplicate (n: INTEGER): BINARY_SEARCH_TREE_SET [G] is
-- New structure containing min (n, count)
-- items from current structure
local
temp_tree: BINARY_SEARCH_TREE [G]
do
create Result.make;
Result.set_tree (tree.duplicate (n))
end;
feature -- Basic operations
intersect (other: like Current) is
-- Remove all items not in other.
require
set_exists: other /= void
local
m: like tree
do
if other.tree = void or tree = void then
tree := void
else
if tree.has_left then
tree.left_child.intersect (other.tree)
end;
if tree.has_right then
tree.right_child.intersect (other.tree)
end;
if notother.has (tree.item) then
if nottree.has_left then
tree := tree.right_child
elseif nottree.has_right then
tree := tree.left_child
else
m := tree.min_node;
m.remove_node;
tree.replace (m.item)
end
end
end
end;
subtract (other: like Current) is
-- Remove all items also in other.
require
set_exists: other /= void
local
m: like tree
do
if other.tree /= void and tree /= void then
if tree.has_left then
tree.left_child.subtract (other.tree)
end;
if tree.has_right then
tree.right_child.subtract (other.tree)
end;
if other.has (tree.item) then
if nottree.has_left then
tree := tree.right_child
elseif nottree.has_right then
tree := tree.left_child
else
m := tree.min_node;
m.remove_node;
tree.replace (m.item)
end
end
end
end;
merge (other: like Current) is
-- Add all items of other.
do
if other.tree /= void then
if tree = void then
tree := new_tree (other.tree.item);
if other.tree.has_left then
tree.merge (other.tree.left_child)
end;
if other.tree.has_right then
tree.merge (other.tree.right_child)
end
else
tree.merge (other.tree)
end
end
end;
feature {BINARY_SEARCH_TREE_SET} -- Implementation
tree: BINARY_SEARCH_TREE [G];
active_node: like tree;
set_tree (t: like tree) is
-- Set tree and active_node to t
do
tree := t;
active_node := t
end;
feature {NONE} -- Implementation
new_tree (v: like item): like tree is
-- New allocated node with item set to v
do
create Result.make (v)
end;
end -- class BINARY_SEARCH_TREE_SET
|
