Automatic generation produced by ISE Eiffel

Classes
Clusters
Cluster hierarchy
Chart
Relations
Text
Flat
Contracts
Flat contracts
Go to: 
indexing
	description: "Cursor trees in linked representation"
	status: "See notice at end of class"
	names: linked_cursor_tree, cursor_tree
	access: cursor, membership
	representation: recursive, linked
	contents: generic
	date: "$Date: 2001-11-16 20:32:23 +0000 (Fri, 16 Nov 2001) $"
	revision: "$Revision: 51435 $"

class 
	LINKED_CURSOR_TREE [G]

create 
	make,
	make_root

feature -- Initialization

	make is
			-- Create an empty tree.
		local
			dummy: G
		do
			create above_node.make (dummy)
			active := above_node
		ensure
			is_above: above
			is_empty: is_empty
		end

	make_root (v: G) is
			-- Create a tree with v as root.
		do
			make
			put_root (v)
		end
	
feature -- Access

	child_item (i: INTEGER): G is
			-- Item in i-th child
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			argument_within_bounds: i >= 1 and then i <= arity
			not_off: not off
		local
			pos: CURSOR
		do
			pos := cursor
			down (i)
			Result := item
			go_to (pos)
		end

	cursor: CURSOR is
			-- Current cursor position
			-- (from RECURSIVE_CURSOR_TREE)
		local
			temp: like cursor_anchor
		do
			create temp.make (active, active_parent, after, before, below)
			Result := temp
		end

	has (v: G): BOOLEAN is
			-- Does structure include an occurrence of v?
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from CURSOR_TREE)
		local
			pos: CURSOR
		do
			pos := cursor
			Result := linear_has (v)
			go_to (pos)
		ensure -- from CONTAINER
			not_found_in_empty: Result implies not is_empty
		end

	index_of (v: like item; i: INTEGER): INTEGER is
			-- Index of i-th occurrence of v.
			-- 0 if none.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from LINEAR)
		require -- from LINEAR
			positive_occurrences: i > 0
		local
			occur, pos: INTEGER
		do
			if object_comparison and v /= void then
				from
					start
					pos := 1
				until
					off or (occur = i)
				loop
					if item /= void and then v.is_equal (item) then
						occur := occur + 1
					end
					preorder_forth
					pos := pos + 1
				end
			else
				from
					start
					pos := 1
				until
					off or (occur = i)
				loop
					if item = v then
						occur := occur + 1
					end
					preorder_forth
					pos := pos + 1
				end
			end
			if occur = i then
				Result := pos - 1
			end
		ensure -- from LINEAR
			non_negative_result: Result >= 0
		end

	item: G is
			-- Item at cursor position
			-- (from RECURSIVE_CURSOR_TREE)
		require -- from TRAVERSABLE
			not_off: not off
		require -- from ACTIVE
			readable: readable
		do
			Result := active.item
		end

	occurrences (v: G): INTEGER is
			-- (from CURSOR_TREE)
		local
			pos: CURSOR
		do
			pos := cursor
			Result := linear_occurrences (v)
			go_to (pos)
		ensure -- from BAG
			non_negative_occurrences: Result >= 0
		end

	parent_item: G is
			-- Item in parent.
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			not_on_root: not is_root
		local
			pos: CURSOR
		do
			pos := cursor
			up
			Result := item
			go_to (pos)
		end

	search (v: like item) is
			-- Move to first position (at or after current
			-- position) where item and v are equal.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- If no such position ensure that exhausted will be true.
			-- (from LINEAR)
		do
			if object_comparison and v /= void then
				from
				until
					exhausted or else (item /= void and then v.is_equal (item))
				loop
					preorder_forth
				end
			else
				from
				until
					exhausted or else v = item
				loop
					preorder_forth
				end
			end
		ensure -- from LINEAR
			object_found: (not exhausted and object_comparison) implies equal (v, item)
			item_found: (not exhausted and not object_comparison) implies v = item
		end
	
feature {NONE} -- Access

	linear_has (v: like item): BOOLEAN is
			-- Does structure include an occurrence of v?
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from LINEAR)
		do
			start
			if not off then
				search (v)
			end
			Result := not exhausted
		ensure -- from CONTAINER
			not_found_in_empty: Result implies not is_empty
		end

	linear_occurrences (v: G): INTEGER is
			-- Number of times v appears.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from LINEAR)
		do
			from
				start
				search (v)
			until
				exhausted
			loop
				Result := Result + 1
				preorder_forth
				search (v)
			end
		end
	
feature -- Measurement

	arity: INTEGER is
			-- Number of children of active node.
			-- If cursor is above, 0 if tree is empty, 1 otherwise.
			-- (from RECURSIVE_CURSOR_TREE)
		require -- from HIERARCHICAL
			not_off: not off
		require else -- from RECURSIVE_CURSOR_TREE
			valid_cursor: not off or else above
		do
			Result := active.arity
		end

	breadth: INTEGER is
			-- Breadth of current level
			-- (from CURSOR_TREE)
		local
			l: INTEGER
			pos: CURSOR
		do
			l := level
			if l > 0 then
				pos := cursor
				go_above
				Result := breadth_of_level_from_active (l + 1)
				go_to (pos)
			end
		end

	count: INTEGER is
			-- Number of items in the tree
			-- (from RECURSIVE_CURSOR_TREE)
		local
			pos: like cursor_anchor
		do
			pos ?= cursor
			from
				start
			until
				off
			loop
				Result := Result + 1
				preorder_forth
			end
			go_to (pos)
			corresponding_child
		end

	depth: INTEGER is
			-- Depth of the tree
			-- (from CURSOR_TREE)
		local
			pos: CURSOR
		do
			if not is_empty then
				pos := cursor
				go_above
				Result := depth_from_active - 1
				go_to (pos)
			end
		end

	level: INTEGER is
			-- Level of current node in tree
			-- (Root is on level 1)
			-- (from CURSOR_TREE)
		local
			pos: CURSOR
		do
			from
				pos := cursor
			until
				above
			loop
				Result := Result + 1
				up
			end
			go_to (pos)
		end
	
feature -- Status report

	above: BOOLEAN is
			-- Is there no valid cursor position above cursor?
			-- (from RECURSIVE_CURSOR_TREE)
		do
			if not below then
				Result := (active_parent = void)
			end
		end

	after: BOOLEAN
			-- Is there no valid cursor position to the right of cursor?
			-- (from RECURSIVE_CURSOR_TREE)

	before: BOOLEAN
			-- Is there no valid cursor position to the left of cursor?
			-- (from RECURSIVE_CURSOR_TREE)

	below: BOOLEAN
			-- Is there no valid cursor position below cursor?
			-- (from CURSOR_TREE)

	changeable_comparison_criterion: BOOLEAN is
			-- May object_comparison be changed?
			-- (Answer: yes by default.)
			-- (from CONTAINER)
		do
			Result := True
		end

	empty: BOOLEAN is
		obsolete "ELKS 2000: Use `is_empty' instead"
			-- Is there no element?
			-- (from CONTAINER)
		do
			Result := is_empty
		end

	exhausted: BOOLEAN is
			-- Has structure been completely explored?
			-- (from LINEAR)
		do
			Result := off
		ensure -- from LINEAR
			exhausted_when_off: off implies Result
		end

	extendible: BOOLEAN is
			-- May new items be added on current level?
			-- (from RECURSIVE_CURSOR_TREE)
		do
			Result := (not above) and (not is_root)
		end

	Full: BOOLEAN is False
			-- Is tree filled to capacity? (Answer: no.)

	is_empty: BOOLEAN is
			-- Is the tree empty?
			-- (from RECURSIVE_CURSOR_TREE)
		do
			Result := (above_node.arity = 0)
		end

	is_inserted (v: G): BOOLEAN is
			-- Has v been inserted by the most recent insertion?
			-- (By default, the value returned is equivalent to calling
			-- `has (v)'. However, descendants might be able to provide more
			-- efficient implementations.)
			-- (from COLLECTION)
		do
			Result := has (v)
		end

	is_leaf: BOOLEAN is
		do
			if not off then
				Result := not below and then active.arity = 0
			end
		end

	is_root: BOOLEAN is
			-- Is cursor on tree root?
			-- (from RECURSIVE_CURSOR_TREE)
		do
			if not off then
				Result := (active_parent = above_node)
			end
		end

	isfirst: BOOLEAN is
			-- Is cursor on first sibling?
			-- (from RECURSIVE_CURSOR_TREE)
		do
			if not off then
				Result := active_parent.child_isfirst
			end
		end

	islast: BOOLEAN is
			-- Is cursor on last sibling?
			-- (from RECURSIVE_CURSOR_TREE)
		do
			if not off then
				Result := active_parent.child_islast
			end
		end

	object_comparison: BOOLEAN
			-- Must search operations use equal rather than =
			-- for comparing references? (Default: no, use =.)
			-- (from CONTAINER)

	off: BOOLEAN is
			-- Is there no current item?
			-- (True if is_empty)
			-- (from CURSOR_TREE)
		do
			Result := (after or before or below or above)
		end

	Prunable: BOOLEAN is True

	readable: BOOLEAN is
			-- Is there a current item that may be read?
			-- (from CURSOR_TREE)
		do
			Result := not off
		end

	valid_cursor (p: CURSOR): BOOLEAN is
			-- Can the cursor be moved to position p?
			-- (from RECURSIVE_CURSOR_TREE)
		local
			temp: like cursor_anchor
			pos: CURSOR
		do
			temp ?= p
			if temp /= void then
				if temp.active = above_node or temp.before or temp.after or temp.below then
					Result := True
				else
					pos := cursor
					from
						start
					until
						active = temp.active or else off
					loop
						preorder_forth
					end
					Result := not off
					go_to (pos)
				end
			end
		end

	valid_cursor_index (i: INTEGER): BOOLEAN is
			-- Can cursor be moved to i-th child?
			-- 0 is before and arity + 1 is after.
			-- (from CURSOR_TREE)
		do
			Result := i >= 0 and i <= (arity + 1)
		end

	writable: BOOLEAN is
			-- Is there a current item that may be modified?
			-- (from CURSOR_TREE)
		do
			Result := not off
		end
	
feature {NONE} -- Status report

	linear_off: BOOLEAN is
			-- Is there no current item?
			-- (from LINEAR)
		do
			Result := is_empty or after
		end
	
feature -- Status setting

	compare_objects is
			-- Ensure that future search operations will use equal
			-- rather than = for comparing references.
			-- (from CONTAINER)
		require -- from CONTAINER
			changeable_comparison_criterion
		do
			object_comparison := True
		ensure -- from CONTAINER
			object_comparison
		end

	compare_references is
			-- Ensure that future search operations will use =
			-- rather than equal for comparing references.
			-- (from CONTAINER)
		require -- from CONTAINER
			changeable_comparison_criterion
		do
			object_comparison := False
		ensure -- from CONTAINER
			reference_comparison: not object_comparison
		end
	
feature -- Cursor movement

	back is
			-- Move cursor one position backward.
			-- (from RECURSIVE_CURSOR_TREE)
		do
			if below then
				after := False
				before := True
			elseif after then
				after := False
			elseif isfirst then
				before := True
			else
				active_parent.child_back
				active := active_parent.child
			end
		end

	breadth_forth is
			-- Move cursor to next position in breadth-first order.
			-- If the active node is the last in
			-- breadth-first order, the cursor ends up off.
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			not_off: not off
		local
			l: INTEGER
		do
			l := level
			level_forth
			if above and (l < depth) then
				start_on_level (l + 1)
			end
		end

	down (i: INTEGER) is
			-- Move cursor one level downward:
			-- to i-th child if there is one,
			-- or after if i = arity + 1,
			-- or before if i = 0.
			-- (from RECURSIVE_CURSOR_TREE)
		require -- from HIERARCHICAL
			not_off: not off
			argument_within_bounds: i >= 1 and i <= arity
		require else -- from 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)
		do
			if i = 0 then
				if arity = 0 then
					below := True
				else
					active_parent := active
					active.child_go_i_th (1)
					active := active.child
				end
				before := True
			elseif above or else i <= arity then
				active_parent := active;
				active.child_go_i_th (i);
				active := active.child
			else
				if arity = 0 then
					below := True
				else
					active_parent := active
					active.child_go_i_th (arity)
					active := active.child
				end
				after := True
			end
		ensure then -- from CURSOR_TREE
			gone_before: (i = 0) implies before
		end

	forth is
			-- Move cursor one position forward.
			-- (from RECURSIVE_CURSOR_TREE)
		do
			if below then
				before := False
				after := True
			elseif before then
				before := False
			elseif islast then
				after := True
			else
				active_parent.child_forth
				active := active_parent.child
			end
		end

	go_last_child is
			-- Go to the last child of current parent.
			-- No effect if below
			-- (from CURSOR_TREE)
		require -- from  LINEAR
			True
		require else -- from CURSOR_TREE
			not_above: not above
		do
			up
			down (arity)
		end

	go_to (p: CURSOR) is
			-- Move cursor to position p.
			-- (from RECURSIVE_CURSOR_TREE)
		require -- from CURSOR_STRUCTURE
			cursor_position_valid: valid_cursor (p)
		local
			temp: like cursor_anchor
		do
			temp ?= p
			check
				temp /= void
			end
			unchecked_go (temp)
		end

	level_back is
			-- Move cursor to previous position of current level.
			-- (from CURSOR_TREE)
		do
			if not isfirst then
				back
			elseif not above then
				from
					up
					level_back
				until
					above or else not is_leaf
				loop
					level_back
				end;
				if not above then
					down (arity)
				end
			end
		end

	level_forth is
			-- Move cursor to next position of current level.
			-- (from CURSOR_TREE)
		do
			if not above and then not islast then
				forth
			elseif not above then
				from
					up
					level_forth
				until
					above or else not is_leaf
				loop
					level_forth
				end;
				if not above then
					down (1)
				end
			end
		end

	postorder_forth is
			-- Move cursor to next position in postorder.
			-- If the active node is the last in
			-- postorder, the cursor ends up off.
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			not_off: not off
		do
			if islast then
				up
			else
				forth
				from
				until
					is_leaf
				loop
					down (1)
				end
			end
		end

	postorder_start is
			-- Move cursor to first position in postorder.
			-- Leave cursor off if tree is empty.
			-- (from CURSOR_TREE)
		do
			from
				go_above
			until
				arity = 0
			loop
				down (1)
			end
		end

	preorder_forth is
			-- Move cursor to next position in preorder.
			-- If the active node is the last in
			-- preorder, the cursor ends up off.
			-- (from CURSOR_TREE)
		require -- from LINEAR
			not_after: not after
		do
			if is_leaf then
				from
				until
					not islast
				loop
					up
				end
				if not above then
					forth
				end
			else
				down (1)
			end
		end

	start is
			-- Move cursor to root.
			-- Leave cursor off if is_empty.
			-- (from CURSOR_TREE)
		do
			go_above
			if not is_empty then
				down (1)
			end
		ensure then -- from CURSOR_TREE
			on_root_unless_empty: not is_empty implies is_root
		end

	start_on_level (l: INTEGER) is
			-- Move the cursor to the first position
			-- of the l-th level counting from root.
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			argument_within_bounds: l >= 1 and then depth >= l
		do
			go_above
			start_on_level_from_active (l + 1)
		ensure -- from CURSOR_TREE
			level_expected: level = l
			is_first: isfirst
		end

	up is
			-- Move cursor one level upward to parent,
			-- or above if is_root holds.
			-- (from RECURSIVE_CURSOR_TREE)
		require -- from HIERARCHICAL
			not_off: not off
		require else -- from CURSOR_TREE
			not_above: not above
		do
			if below then
				below := False
			else
				active := active_parent
				if active /= void then
					active_parent := active.parent
				end
				corresponding_child
			end
			after := False
			before := False
		ensure then -- from CURSOR_TREE
			not_before: not before
			not_after: not after
			not_below: not below
			coherency: (not old off and above) = (old is_root)
		end
	
feature -- Element change

	fill (other: CURSOR_TREE [G]) is
			-- Fill with as many items of other
			-- as possible.
			-- The representations of other and current structure
			-- need not be the same.
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			is_empty: is_empty
		do
			go_above
			if not other.is_empty then
				other.start
				down (0)
				put_right (other.item)
				forth
				fill_from_active (other)
			end
		end

	container_fill (other: CONTAINER [G]) is
			-- Fill with as many items of other as possible.
			-- The representations of other and current structure
			-- need not be the same.
			-- (from COLLECTION)
		require -- from COLLECTION
			other_not_void: other /= void
			extendible
		local
			lin_rep: LINEAR [G]
		do
			lin_rep := other.linear_representation
			from
				lin_rep.start
			until
				not extendible or else lin_rep.off
			loop
				extend (lin_rep.item)
				lin_rep.forth
			end
		end

	fill_from_active (other: CURSOR_TREE [G]) is
			-- Copy subtree of other's active node
			-- onto active node of current tree.
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			cursor_on_leaf: is_leaf
		do
			if not other.is_leaf then
				from
					other.down (1)
					down (0)
				until
					other.after
				loop
					put_right (other.item)
					forth
					fill_from_active (other)
					other.forth
				end
				other.up
				up
			end
		end

	merge_left (other: CURSOR_TREE [G]) is
			-- Merge the items of other into current structure to
			-- the left of cursor position.
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			other_exists: other /= void
			not_before: not before
			not_above: not above
			only_one_root: (level = 1) implies is_empty
		do
			back
			merge_right (other)
		end

	merge_right (other: CURSOR_TREE [G]) is
			-- Merge the items of other into current structure to
			-- the right of cursor position.
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			other_exists: other /= void
			not_after: not after
			not_above: not above
			only_one_root: (level = 1) implies is_empty
		local
			pos: CURSOR
		do
			if not other.is_empty then
				pos := other.cursor
				other.start
				put_right (other.item)
				forth
				if not other.is_leaf then
					down (0)
					other.down (0)
					from
					until
						other.islast
					loop
						other.forth
						merge_right (other.subtree)
					end
					up
				end
				other.go_to (pos)
			end
		end

	put (v: G) is
			-- Put v at cursor position.
			-- (Synonym for replace)
			-- (from CURSOR_TREE)
		require -- from COLLECTION
			extendible: extendible
		do
			replace (v)
		ensure -- from COLLECTION
			item_inserted: is_inserted (v)
		end

	put_child (v: G) is
			-- Put v as child of a leaf.
		require
			is_leaf: is_leaf
		do
			down (0)
			put_right (v)
		end

	put_left (v: G) is
			-- Add v to the left of cursor position.
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			not_before: not before
			not_above: not above
			only_one_root: (level = 1) implies is_empty
		do
			back
			put_right (v)
			forth
			forth
		end

	put_right (v: G) is
			-- Add v to the right of cursor position.
		require -- from CURSOR_TREE
			not_after: not after
			not_above: not above
			only_one_root: (level = 1) implies is_empty
		do
			if below then
				active.child_put_right (v)
				active.child_forth
				active_parent := active
				active := active_parent.child
				below := False
			elseif before then
				active_parent.child_put_left (v);
				active_parent.child_back;
				active := active_parent.child
			else
				active_parent.child_put_right (v)
			end
		end

	put_root (v: G) is
			-- Put v as root of an empty tree.
		require
			is_empty: is_empty
		do
			above_node.child_put_right (v)
			active_parent := above_node
			active := active_parent.child
		ensure
			is_root: is_root
			count = 1
		end

	replace (v: G) is
			-- Replace current item by v.
			-- (from RECURSIVE_CURSOR_TREE)
		require -- from ACTIVE
			writable: writable
		do
			active.replace (v)
		ensure -- from ACTIVE
			item_replaced: item = v
		end
	
feature -- Removal

	remove is
			-- Remove node at cursor position
			-- (and consequently the corresponding
			-- subtree). Cursor moved up one level.
			-- (from RECURSIVE_CURSOR_TREE)
		require -- from ACTIVE
			prunable: prunable
			writable: writable
		do
			corresponding_child
			active := active_parent
			active_parent := active.parent
			active.remove_child
			active.child_back
		ensure then -- from RECURSIVE_CURSOR_TREE
			not_off_unless_empty: is_empty or else not off
		end

	wipe_out is
			-- Remove all items.
			-- (from RECURSIVE_CURSOR_TREE)
		require -- from COLLECTION
			prunable
		do
			if not is_empty then
				above_node.child_start
				above_node.remove_child
			end
			active := above_node
			active_parent := void
			after := False
			before := False
			below := False
		ensure -- from COLLECTION
			wiped_out: is_empty
		ensure then -- from RECURSIVE_CURSOR_TREE
			cursor_above: above
		end
	
feature {NONE} -- Removal

	prune_all (v: G) is
			-- Remove all occurrences of v.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from COLLECTION)
		require -- from COLLECTION
			prunable
		do
			from
			until
				not has (v)
			loop
				prune (v)
			end
		ensure -- from COLLECTION
			no_more_occurrences: not has (v)
		end
	
feature -- Conversion

	linear_representation: LINEAR [G] is
			-- Representation as a linear structure
			-- (from LINEAR)
		do
			Result := Current
		end
	
feature -- Duplication

	child_tree (i: INTEGER): like Current is
			-- Subtree rooted at i-th child
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			argument_within_bounds: i >= 1 and then i <= arity
			not_off: not off
		local
			pos: CURSOR
		do
			pos := cursor
			down (i)
			Result := subtree
			go_to (pos)
		end

	parent_tree: like Current is
			-- Subtree rooted at parent
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			not_on_root: not is_root
			not_off: not off
		local
			pos: CURSOR
		do
			pos := cursor
			up
			Result := subtree
			go_to (pos)
		end

	subtree: like Current is
			-- Subtree rooted at current node
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			not_off: not off
		do
			Result := new_tree
			Result.go_above
			Result.down (0)
			Result.put_right (item)
			Result.forth
			Result.fill_from_active (Current)
		end
	
feature {NONE} -- Inapplicable

	prune (v: G) is
			-- Remove item v.
			-- (from CURSOR_TREE)
		require -- from COLLECTION
			prunable: prunable
		do
		end
	
feature {LINKED_CURSOR_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.
		do
			create Result.make
		ensure -- from CURSOR_TREE
			result_exists: Result /= void
			result_is_empty: Result.is_empty
		end
	
feature {NONE} -- Implementation

	above_node: like active
			-- Node above root; physical root of tree
			-- (from RECURSIVE_CURSOR_TREE)

	active: LINKED_TREE [G]
			-- Current node

	active_parent: like active
			-- Parent of current node
			-- (from RECURSIVE_CURSOR_TREE)

	breadth_of_level_from_active (a_level: INTEGER): INTEGER is
			-- Breadth of level level of subtree starting at current node
			-- (from CURSOR_TREE)
		do
			if (a_level = 2) or else is_leaf then
				Result := arity
			else
				from
					down (1)
				until
					after
				loop
					Result := Result + breadth_of_level_from_active (a_level - 1)
					forth
				end
				up
			end
		end

	corresponding_child is
			-- Make active the current child of active_parent.
			-- (from RECURSIVE_CURSOR_TREE)
		require -- from RECURSIVE_CURSOR_TREE
			active_exists: active /= void
		do
			if active_parent /= void then
				active_parent.set_child (active)
			end
		end

	cursor_anchor: LINKED_TREE_CURSOR [G]
			-- Anchor for definitions concerning cursors

	depth_from_active: INTEGER is
			-- Depth of subtree starting at active
			-- (from CURSOR_TREE)
		do
			if not off and then arity = 0 then
				Result := 1
			else
				from
					down (1)
				until
					after
				loop
					Result := Result.max (depth_from_active + 1)
					forth
				end
				up
			end
		end

	start_on_level_from_active (l: INTEGER) is
			-- Move the cursor to the first position
			-- of the l-th level counting from active.
			-- (from CURSOR_TREE)
		require -- from CURSOR_TREE
			deep_enough: depth_from_active >= l
		do
			from
				down (1)
			until
				depth_from_active >= l - 1
			loop
				forth
			end
			if (l > 2) then
				start_on_level_from_active (l - 1)
			end
		end

	unchecked_go (p: like cursor_anchor) is
			-- Make an attempt to move cursor
			-- to position p, without checking
			-- whether p is a valid cursor position
			-- or not.
			-- (from RECURSIVE_CURSOR_TREE)
		do
			active_parent := p.active_parent
			active := p.active
			corresponding_child
			after := p.after
			before := p.before
			below := p.below
		end
	
feature {CURSOR_TREE} -- Implementation

	go_above is
			-- Move the cursor above the tree
			-- (from CURSOR_TREE)
		do
			from
			until
				above
			loop
				up
			end
		end
	
feature -- Insert element

	extend (v: G) is
			-- Add v after last child.
			-- Make v the first_child if below and place
			-- cursor before.
			-- (from RECURSIVE_CURSOR_TREE)
		require -- from COLLECTION
			extendible: extendible
		local
			pos: CURSOR
		do
			pos := cursor
			go_last_child
			put_right (v)
			go_to (pos)
			if below then
				below := False
				before := False
				after := False
				down (0)
			end
		ensure -- from COLLECTION
			item_inserted: is_inserted (v)
		ensure then -- from BAG
			one_more_occurrence: occurrences (v) = old (occurrences (v)) + 1
		end
	
feature -- Iteration

	do_all (action: PROCEDURE [ANY, TUPLE [G]]) is
			-- Apply action to every item.
			-- Semantics not guaranteed if action changes the structure;
			-- in such a case, apply iterator to clone of structure instead.
			-- (from TRAVERSABLE)
		require -- from TRAVERSABLE
			action_exists: action /= void
		do
			linear_representation.do_all (action)
		end

	linear_do_all (action: PROCEDURE [ANY, TUPLE [G]]) is
			-- Apply action to every item.
			-- Semantics not guaranteed if action changes the structure;
			-- in such a case, apply iterator to clone of structure instead.
			-- (from LINEAR)
		require -- from TRAVERSABLE
			action_exists: action /= void
		local
			t: TUPLE [G]
		do
			create t.make
			from
				start
			until
				after
			loop
				t.put (item, 1)
				action.call (t)
				preorder_forth
			end
		end

	do_if (action: PROCEDURE [ANY, TUPLE [G]]; test: FUNCTION [ANY, TUPLE [G], BOOLEAN]) is
			-- Apply action to every item that satisfies test.
			-- Semantics not guaranteed if action or test changes the structure;
			-- in such a case, apply iterator to clone of structure instead.
			-- (from TRAVERSABLE)
		require -- from TRAVERSABLE
			action_exists: action /= void
			test_exits: test /= void
		do
			linear_representation.do_if (action, test)
		end

	linear_do_if (action: PROCEDURE [ANY, TUPLE [G]]; test: FUNCTION [ANY, TUPLE [G], BOOLEAN]) is
			-- Apply action to every item that satisfies test.
			-- Semantics not guaranteed if action or test changes the structure;
			-- in such a case, apply iterator to clone of structure instead.
			-- (from LINEAR)
		require -- from TRAVERSABLE
			action_exists: action /= void
			test_exits: test /= void
		local
			t: TUPLE [G]
		do
			create t.make
			from
				start
			until
				after
			loop
				t.put (item, 1)
				if test.item (t) then
					action.call (t)
				end
				preorder_forth
			end
		end

	linear_for_all (test: FUNCTION [ANY, TUPLE [G], BOOLEAN]): BOOLEAN is
			-- Is test true for all items?
			-- (from LINEAR)
		require -- from TRAVERSABLE
			test_exits: test /= void
		local
			cs: CURSOR_STRUCTURE [G]
			c: CURSOR
			t: TUPLE [G]
		do
			create t.make
			cs ?= Current
			if cs /= void then
				c := cs.cursor
			end
			from
				start
				Result := True
			until
				after or not Result
			loop
				t.put (item, 1)
				Result := test.item (t)
				preorder_forth
			end
			if cs /= void then
				cs.go_to (c)
			end
		end

	for_all (test: FUNCTION [ANY, TUPLE [G], BOOLEAN]): BOOLEAN is
			-- Is test true for all items?
			-- (from TRAVERSABLE)
		require -- from TRAVERSABLE
			test_exits: test /= void
		do
			Result := linear_representation.for_all (test)
		end

	there_exists (test: FUNCTION [ANY, TUPLE [G], BOOLEAN]): BOOLEAN is
			-- Is test true for at least one item?
			-- (from TRAVERSABLE)
		require -- from TRAVERSABLE
			test_exits: test /= void
		do
			Result := linear_representation.there_exists (test)
		end

	linear_there_exists (test: FUNCTION [ANY, TUPLE [G], BOOLEAN]): BOOLEAN is
			-- Is test true for at least one item?
			-- (from LINEAR)
		require -- from TRAVERSABLE
			test_exits: test /= void
		local
			cs: CURSOR_STRUCTURE [G]
			c: CURSOR
			t: TUPLE [G]
		do
			create t.make
			cs ?= Current
			if cs /= void then
				c := cs.cursor
			end
			from
				start
			until
				after or Result
			loop
				t.put (item, 1)
				Result := test.item (t)
				preorder_forth
			end
			if cs /= void then
				cs.go_to (c)
			end
		end
	
feature {NONE} -- Not applicable

	index: INTEGER is
			-- (from CURSOR_TREE)
		do
		end
	
invariant

		-- from ANY
	reflexive_equality: standard_is_equal (Current)
	reflexive_conformance: conforms_to (Current)
		-- from RECURSIVE_CURSOR_TREE
	coherency: not above implies active_parent.child = active
		-- from 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
		-- from HIERARCHICAL
	non_negative_successor_count: arity >= 0
		-- from TRAVERSABLE
	empty_constraint: is_empty implies off
		-- from ACTIVE
	writable_constraint: writable implies readable
	empty_constraint: is_empty implies (not readable) and (not writable)
		-- from LINEAR
	after_constraint: after implies off

indexing
	library: "[
			EiffelBase: Library of reusable components for Eiffel.
	]"
	status: "[
			Copyright 1986-2001 Interactive Software Engineering (ISE).
			For ISE customers the original versions are an ISE product
			covered by the ISE Eiffel license and support agreements.
	]"
	license: "[
			EiffelBase may now be used by anyone as FREE SOFTWARE to
			develop any product, public-domain or commercial, without
			payment to ISE, under the terms of the ISE Free Eiffel Library
			License (IFELL) at http://eiffel.com/products/base/license.html.
	]"
	source: "[
			Interactive Software Engineering Inc.
			ISE Building
			360 Storke Road, Goleta, CA 93117 USA
			Telephone 805-685-1006, Fax 805-685-6869
			Electronic mail <info@eiffel.com>
			Customer support http://support.eiffel.com
	]"
	info: "[
			For latest info see award-winning pages: http://eiffel.com
	]"

end -- class LINKED_CURSOR_TREE


Classes
Clusters
Cluster hierarchy
Chart
Relations
Text
Flat
Contracts
Flat contracts
Go to: 

-- Generated by ISE Eiffel --
For more details: www.eiffel.com