Automatic generation produced by ISE Eiffel

Classes
Clusters
Cluster hierarchy
Chart
Relations
Text
Flat
Contracts
Flat contracts
Go to: 
indexing
	description: "Compact trees as active structures that may be traversed using a cursor"
	status: "See notice at end of class"
	names: compact_cursor_tree, cursor_tree
	representation: array
	access: cursor, membership
	size: resizable
	contents: generic
	date: "$Date: 2001/11/16 20:34:16 $"
	revision: "$Revision: 1.1.1.1 $"

class 
	COMPACT_CURSOR_TREE [G]

create 
	make

feature -- Initialization

	make (i: INTEGER) is
			-- Create an empty tree.
			-- i is an estimate of the number of nodes.
		do
			last := 1
			active := 1
			above := True
			create item_table.make (1, i + 1)
			create next_sibling_table.make (1, i + 1)
			create first_child_table.make (1, i + 1)
		ensure
			is_above: above
			is_empty: is_empty
		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
		do
			create {COMPACT_TREE_CURSOR} Result.make (active, after, before, below, above)
		end

	has (v: like item): BOOLEAN is
			-- Does structure include an occurrence of v?
			-- (Reference or object equality,
			-- based on object_comparison.)
		do
			if object_comparison then
				item_table.compare_objects
			else
				item_table.compare_references
			end
			Result := item_table.has (v)
		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
			-- Current item
		require -- from TRAVERSABLE
			not_off: not off
		require -- from ACTIVE
			readable: readable
		do
			Result := item_table.item (active)
		end

	occurrences (v: G): INTEGER is
			-- Number of times v appears.
			-- (Reference or object equality,
			-- based on object_comparison.)
		do
			if object_comparison then
				item_table.compare_objects
			else
				item_table.compare_references
			end
			Result := item_table.occurrences (v)
		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
		require -- from HIERARCHICAL
			not_off: not off
		local
			index: INTEGER
		do
			index := first_child_table.item (active)
			from
			until
				index <= 0
			loop
				Result := Result + 1
				index := next_sibling_table.item (index)
			end
		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 subtree
		do
			Result := last - free_list_count - 1
		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 there no valid cursor position above the cursor?

	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?

	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?
			-- (from CURSOR_TREE)
		do
			Result := not above and then (level = 1) implies is_empty
		end

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

	is_empty: BOOLEAN is
		do
			Result := count = 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
			-- Is cursor on a leaf?
			-- (from CURSOR_TREE)
		do
			if not off then
				Result := (arity = 0)
			end
		end

	is_root: BOOLEAN is
			-- Is cursor on root?
		do
			if not off then
				Result := next_sibling_table.item (active) = 0
			end
		end

	isfirst: BOOLEAN is
			-- Is cursor on first sibling?
		local
			index: INTEGER
		do
			if not off then
				from
					index := next_sibling_table.item (active)
				until
					index <= 0
				loop
					index := next_sibling_table.item (index)
				end
				Result := (index = 0) or else (first_child_table.item (- index) = active)
			end
		end

	islast: BOOLEAN is
			-- Is cursor on last sibling?
		do
			if not off then
				Result := (next_sibling_table.item (active) <= 0)
			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
		do
			Result := True
		end

	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?
		local
			temp: COMPACT_TREE_CURSOR
		do
			temp ?= p
			if temp /= void then
				Result := (first_child_table.item (temp.active) /= removed_mark)
			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.
		local
			index, next: INTEGER
		do
			if below then
				check
					after
				end
				after := False
				before := True
			elseif after then
				after := False
			else
				from
					index := next_sibling_table.item (active)
				until
					index <= 0
				loop
					index := next_sibling_table.item (index)
				end
				if index = 0 then
					before := True
				elseif first_child_table.item (- index) = active then
					before := True
				else
					from
						index := first_child_table.item (- index)
						next := next_sibling_table.item (index)
					until
						next = active
					loop
						index := next
						next := next_sibling_table.item (index)
					end
					active := index
				end
			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.
		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)
		require else
			True
		local
			index, next, counter: INTEGER
		do
			index := first_child_table.item (active)
			if above then
				above := False
				below := is_empty
				before := is_empty
				after := False
			elseif index <= 0 then
				below := True;
				if i = 0 then
					before := True;
					after := False
				else
					after := True;
					before := False
				end
			else
				from
					next := next_sibling_table.item (index)
				until
					counter = i or next <= 0
				loop
					index := next
					next := next_sibling_table.item (index)
					counter := counter + 1
				end
				active := index
				if i = 0 then
					before := True
					after := False
				elseif counter < i then
					after := True;
					before := False
				end
			end
		ensure then -- from CURSOR_TREE
			gone_before: (i = 0) implies before
		end

	forth is
			-- Move cursor one position forward.
		do
			if below then
				check
					before
				end
				before := False
				after := True
			elseif before then
				before := False
			elseif islast then
				after := True
			else
				active := next_sibling_table.item (active)
			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.
		require -- from CURSOR_STRUCTURE
			cursor_position_valid: valid_cursor (p)
		local
			temp: COMPACT_TREE_CURSOR
		do
			temp ?= p
			check
				temp /= void
			end
			active := temp.active
			after := temp.after
			before := temp.before
			below := temp.below
			above := temp.above
		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.
		require -- from HIERARCHICAL
			not_off: not off
		require else -- from CURSOR_TREE
			not_above: not above
		local
			index: INTEGER
		do
			if below then
				below := False
			else
				from
					index := next_sibling_table.item (active)
				until
					index <= 0
				loop
					index := next_sibling_table.item (index)
				end
				if index = 0 then
					above := True
				else
					active := - index
				end
			end
			after := False
			before := False
		ensure then -- from CURSOR_TREE
			not_before: not before
			not_after: not after
			not_below