indexing
	description: "Objects that are able to iterate over cursor trees, on which they can perform repeated actions and tests according to a number of predefined control structures such as ``if%'%', ``until%'%' and others."
	names: iterators, iteration, cursor_tree_iterators, cursor_tree_iteration, tree_iterators, tree_iteration
	exploration: depth_first, breadth_first
	traversal: preorder, postorder, inorder

class interface
	CURSOR_TREE_ITERATOR [G]

feature -- Status report

	invariant_value: BOOLEAN
			-- Is the invariant satisfied?
			-- (Redefinitions of this feature will usually involve
			-- target; if so, make sure that the result is defined
			-- when target = Void.)
			-- (from ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void

	item_test (v: G): BOOLEAN
			-- Test to be applied to item v
			-- (default: false)
			-- (from ITERATOR)

	target: CURSOR_TREE [G]
			-- The structure to which iteration features will apply

	test: BOOLEAN
			-- Test to be applied to item at current position in target
			-- (default: value of item_test on item)
			-- (from ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void;
			not_off: not target.off
		ensure -- from ITERATOR
			not_off: not target.off
	
feature -- Status setting

	set (s: like target)
			-- Make s the new target of iterations.
			-- (from ITERATOR)
		require -- from ITERATOR
			s /= void
		ensure -- from ITERATOR
			target = s;
			target /= void
	
feature -- Cursor movement

	breadth_forth
			-- Move cursor of target to next position in breadth-first.
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void

	breadth_start
			-- Move cursor of target to root position
			-- (first position in preorder and breadth-first).
			-- Was declared in CURSOR_TREE_ITERATOR as synonym of pre_start and breadth_start.

	pre_continue_for (n, k: INTEGER)
			-- Apply action to every k-th item,
			-- n times if possible.
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void;
			valid_repetition: n >= 0;
			valid_skip: k >= 1

	post_continue_for (n, k: INTEGER)
			-- Apply action to every k-th item,
			-- n times if possible.
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void;
			valid_repetition: n >= 0;
			valid_skip: k >= 1

	breadth_continue_for (n, k: INTEGER)
			-- Apply action to every k-th item,
			-- n times if possible.
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void;
			valid_repetition: n >= 0;
			valid_skip: k >= 1

	post_continue_search (b: BOOLEAN)
			-- Search the first item of target
			-- satisfying: test equals to b
			-- (from the current position of target).
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			found: not exhausted = (b = test)

	pre_continue_search (b: BOOLEAN)
			-- Search the first item of target
			-- satisfying: test equals to b
			-- (from the current position of target).
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			found: not exhausted = (b = test)

	breadth_continue_search (b: BOOLEAN)
			-- Search the first item of target
			-- satisfying: test equals to b
			-- (from the current position of target).
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			found: not exhausted = (b = test)

	pre_continue_until
			-- Apply action to every item of target up to
			-- and including first one satisfying test.
			-- (from the current position of target).
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void;
			invariant_satisfied: invariant_value
		ensure then -- from LINEAR_ITERATOR
			achieved: not exhausted implies test

	post_continue_until
			-- Apply action to every item of target up to
			-- and including first one satisfying test.
			-- (from the current position of target).
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void;
			invariant_satisfied: invariant_value
		ensure then -- from LINEAR_ITERATOR
			achieved: not exhausted implies test

	breadth_continue_until
			-- Apply action to every item of target up to
			-- and including first one satisfying test.
			-- (from the current position of target).
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void;
			invariant_satisfied: invariant_value
		ensure then -- from LINEAR_ITERATOR
			achieved: not exhausted implies test

	post_continue_while
			-- Apply action to every item of target up to
			-- and including first one not satisfying test
			-- (from the current position of target).
			-- (from LINEAR_ITERATOR)
		require else -- from LINEAR_ITERATOR
			traversable_exists: target /= void;
			invariant_satisfied: invariant_value
		ensure then -- from LINEAR_ITERATOR
			finished: not exhausted implies not test

	breadth_continue_while
			-- Apply action to every item of target up to
			-- and including first one not satisfying test
			-- (from the current position of target).
			-- (from LINEAR_ITERATOR)
		require else -- from LINEAR_ITERATOR
			traversable_exists: target /= void;
			invariant_satisfied: invariant_value
		ensure then -- from LINEAR_ITERATOR
			finished: not exhausted implies not test

	pre_continue_while
			-- Apply action to every item of target up to
			-- and including first one not satisfying test
			-- (from the current position of target).
			-- (from LINEAR_ITERATOR)
		require else -- from LINEAR_ITERATOR
			traversable_exists: target /= void;
			invariant_satisfied: invariant_value
		ensure then -- from LINEAR_ITERATOR
			finished: not exhausted implies not test

	post_do_all
			-- Apply action to every item of target.
			-- (from the start of target)
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			exhausted

	pre_do_all
			-- Apply action to every item of target.
			-- (from the start of target)
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			exhausted

	breadth_do_all
			-- Apply action to every item of target.
			-- (from the start of target)
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			exhausted

	post_do_for (i, n, k: INTEGER)
			-- Apply action to every k-th item,
			-- n times if possible, starting from i-th.
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void;
			valid_start: i >= 1;
			valid_repetition: n >= 0;
			valid_skip: k >= 1

	pre_do_for (i, n, k: INTEGER)
			-- Apply action to every k-th item,
			-- n times if possible, starting from i-th.
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void;
			valid_start: i >= 1;
			valid_repetition: n >= 0;
			valid_skip: k >= 1

	breadth_do_for (i, n, k: INTEGER)
			-- Apply action to every k-th item,
			-- n times if possible, starting from i-th.
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void;
			valid_start: i >= 1;
			valid_repetition: n >= 0;
			valid_skip: k >= 1

	breadth_do_if
			-- Apply action to every item of target
			-- satisfying test.
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void

	pre_do_if
			-- Apply action to every item of target
			-- satisfying test.
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void

	post_do_if
			-- Apply action to every item of target
			-- satisfying test.
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void

	pre_do_until
			-- Apply action to every item of target up to
			-- and including first one satisfying test.
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			achieved: not exhausted implies test

	post_do_until
			-- Apply action to every item of target up to
			-- and including first one satisfying test.
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			achieved: not exhausted implies test

	breadth_do_until
			-- Apply action to every item of target up to
			-- and including first one satisfying test.
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			achieved: not exhausted implies test

	post_do_while
			-- Apply action to every item of target up to
			-- and including first one not satisfying test.
			-- (from the start of target)
			-- (from LINEAR_ITERATOR)
		ensure then -- from LINEAR_ITERATOR
			finished: not exhausted implies not test

	pre_do_while
			-- Apply action to every item of target up to
			-- and including first one not satisfying test.
			-- (from the start of target)
			-- (from LINEAR_ITERATOR)
		ensure then -- from LINEAR_ITERATOR
			finished: not exhausted implies not test

	breadth_do_while
			-- Apply action to every item of target up to
			-- and including first one not satisfying test.
			-- (from the start of target)
			-- (from LINEAR_ITERATOR)
		ensure then -- from LINEAR_ITERATOR
			finished: not exhausted implies not test

	exhausted: BOOLEAN
			-- Is target exhausted?
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void

	pre_exists: BOOLEAN
			-- Does test return true for
			-- at least one item of target?
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void

	breadth_exists: BOOLEAN
			-- Does test return true for
			-- at least one item of target?
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void

	post_exists: BOOLEAN
			-- Does test return true for
			-- at least one item of target?
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void

	post_forall: BOOLEAN
			-- Does test return true for
			-- all items of target?
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void

	pre_forall: BOOLEAN
			-- Does test return true for
			-- all items of target?
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void

	breadth_forall: BOOLEAN
			-- Does test return true for
			-- all items of target?
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void

	off: BOOLEAN
			-- Is position of target off?
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void

	post_forth
			-- Move cursor of target to next position in postorder.
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void

	post_start
			-- Move cursor of target to first position in postorder.
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void

	pre_forth
			-- Move cursor of target to next position in preorder.
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void

	pre_start
			-- Move cursor of target to root position
			-- (first position in preorder and breadth-first).
			-- Was declared in CURSOR_TREE_ITERATOR as synonym of pre_start and breadth_start.

	pre_search (b: BOOLEAN)
			-- Search the first item of target for which test
			-- has the same value as b (both true or both false).
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void

	breadth_search (b: BOOLEAN)
			-- Search the first item of target for which test
			-- has the same value as b (both true or both false).
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void

	post_search (b: BOOLEAN)
			-- Search the first item of target for which test
			-- has the same value as b (both true or both false).
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void

	start
			-- Move to first position of target.
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void

	until_continue
			-- Apply action to every item of target from current
			-- position, up to but excluding first one satisfying test.
			-- (from LINEAR_ITERATOR)
		require -- from LINEAR_ITERATOR
			traversable_exists: target /= void;
			invariant_satisfied: invariant_value
		ensure -- from LINEAR_ITERATOR
			achieved: exhausted or else test;
			invariant_satisfied: invariant_value

	pre_until_do
			-- Apply action to every item of target up to
			-- but excluding first one satisfying test.
			-- (Apply to full list if no item satisfies test.)
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			achieved: not exhausted implies test

	post_until_do
			-- Apply action to every item of target up to
			-- but excluding first one satisfying test.
			-- (Apply to full list if no item satisfies test.)
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			achieved: not exhausted implies test

	breadth_until_do
			-- Apply action to every item of target up to
			-- but excluding first one satisfying test.
			-- (Apply to full list if no item satisfies test.)
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			achieved: not exhausted implies test

	pre_while_continue
			-- Apply action to every item of target up to
			-- but excluding first one not satisfying test.
			-- (from LINEAR_ITERATOR)
		ensure -- from LINEAR_ITERATOR
			finished: not exhausted implies not test

	post_while_continue
			-- Apply action to every item of target up to
			-- but excluding first one not satisfying test.
			-- (from LINEAR_ITERATOR)
		ensure -- from LINEAR_ITERATOR
			finished: not exhausted implies not test

	breadth_while_continue
			-- Apply action to every item of target up to
			-- but excluding first one not satisfying test.
			-- (from LINEAR_ITERATOR)
		ensure -- from LINEAR_ITERATOR
			finished: not exhausted implies not test

	pre_while_do
			-- Apply action to every item of target up to
			-- but excluding first one not satisfying test.
			-- (Apply to full list if all items satisfy test.)
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			finished: not exhausted implies not test

	post_while_do
			-- Apply action to every item of target up to
			-- but excluding first one not satisfying test.
			-- (Apply to full list if all items satisfy test.)
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			finished: not exhausted implies not test

	breadth_while_do
			-- Apply action to every item of target up to
			-- but excluding first one not satisfying test.
			-- (Apply to full list if all items satisfy test.)
			-- (from LINEAR_ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void
		ensure then -- from LINEAR_ITERATOR
			finished: not exhausted implies not test
	
feature -- Element change

	action
			-- Action to be applied to item at current position
			-- in target (default: item_action on that item).
			-- For iterators to work properly, redefined versions of
			-- this feature should not change the traversable's
			-- structure.
			-- (from ITERATOR)
		require -- from ITERATOR
			traversable_exists: target /= void;
			not_off: not target.off;
			invariant_satisfied: invariant_value
		ensure -- from ITERATOR
			not_off: not target.off;
			invariant_satisfied: invariant_value

	item_action (v: G)
			-- Action to be applied to item v
			-- (Default: do nothing.)
			-- (from ITERATOR)
	
invariant

		-- from GENERAL
	reflexive_equality: standard_is_equal (Current);
	reflexive_conformance: conforms_to (Current);

end -- class CURSOR_TREE_ITERATOR