Automatic generation produced by ISE Eiffel

Classes
Clusters
Cluster hierarchy
Chart
Relations
Text
Flat
Contracts
Flat contracts
Go to: 
indexing
	description: "Trees where the children of each node are kept in an array"
	status: "See notice at end of class"
	names: tree
	representation: recursive, array
	access: cursor, membership
	contents: generic
	date: "$Date: 2001/11/16 20:34:23 $"
	revision: "$Revision: 1.1.1.1 $"

class 
	ARRAYED_TREE [G]

create 
	make

feature -- Initialization

	make (n: INTEGER; v: G) is
			-- Create node with item v.
			-- Allocate space for n children.
		require
			valid_number_of_children: n >= 0
		do
			al_make (n)
			replace (v)
		ensure
			node_item: item = v
		end

	make_filled (n: INTEGER) is
			-- Allocate list with n items.
			-- (n may be zero for empty list.)
			-- This list will be full.
			-- (from ARRAYED_LIST)
		require -- from ARRAYED_LIST
			valid_number_of_items: n >= 0
		do
			child_index := 0
			arity := n
			array_make (1, n)
		ensure -- from ARRAYED_LIST
			correct_position: child_before
			filled: al_full
		end

	make_from_array (a: ARRAY [ARRAYED_TREE [G]]) is
			-- Create list from array a.
			-- (from ARRAYED_LIST)
		require -- from ARRAY
			array_exists: a /= void
		do
			Precursor  (a)
			lower := 1
			arity := a.count
			upper := arity
			child_index := 0
		end
	
feature {NONE} -- Initialization

	al_make (n: INTEGER) is
			-- Allocate list with n items.
			-- (n may be zero for empty list.)
			-- (from ARRAYED_LIST)
		require -- from ARRAYED_LIST
			valid_number_of_items: n >= 0
		do
			child_index := 0
			arity := 0
			array_make (1, n)
		ensure -- from ARRAYED_LIST
			correct_position: child_before
		end

	make_area (n: INTEGER) is
			-- Creates a special object for n entries.
			-- (from TO_SPECIAL)
		require -- from TO_SPECIAL
			non_negative_argument: n >= 0
		do
			create area.make (n)
		ensure -- from TO_SPECIAL
			area_allocated: area /= void and then area.count = n
		end
	
feature {ARRAYED_LIST} -- Initialization

	array_make (min_index, max_index: INTEGER) is
			-- Allocate array; set index interval to
			-- min_index .. max_index; set all values to default.
			-- (Make array empty if min_index = max_index + 1).
			-- (from ARRAY)
		require -- from ARRAY
			valid_bounds: min_index <= max_index + 1
		do
			lower := min_index
			upper := max_index
			if min_index <= max_index then
				make_area (max_index - min_index + 1)
			else
				make_area (0)
			end
		ensure -- from ARRAY
			lower_set: lower = min_index
			upper_set: upper = max_index
			items_set: all_default
		end
	
feature -- Access

	child_item: like item is
			-- Item in current child node
			-- (from TREE)
		require -- from TREE
			readable: child_readable
		do
			Result := child.item
		end

	child_cursor: CURSOR is
			-- Current cursor position
			-- (from ARRAYED_LIST)
		do
			create {ARRAYED_LIST_CURSOR} Result.make (child_index)
		end

	first_child: ARRAYED_TREE [G] is
			-- Item at first position
			-- (from ARRAYED_LIST)
		require -- from CHAIN
			not_empty: not is_leaf
		require -- from TREE
			is_not_leaf: not is_leaf
		do
			Result := area.item (0)
		end

	child_index: INTEGER
			-- Index of item, if valid.
			-- (from ARRAYED_LIST)

	index_of (v: like child; i: INTEGER): INTEGER is
			-- Index of i-th occurrence of item identical to v.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- 0 if none.
			-- (from CHAIN)
		require -- from LINEAR
			positive_occurrences: i > 0
		local
			pos: CURSOR
		do
			pos := child_cursor
			Result := sequential_index_of (v, i)
			child_go_to (pos)
		ensure -- from LINEAR
			non_negative_result: Result >= 0
		end

	item: G
			-- Content of cell.
			-- (from CELL)

	child: like first_child is
			-- Current item
			-- (from ARRAYED_LIST)
		require -- from TRAVERSABLE
			not_off: not child_off
		require -- from ACTIVE
			readable: readable_child
		require -- from TREE
			readable: readable_child
		require else -- from ARRAYED_LIST
			index_is_valid: valid_index (child_index)
		do
			Result := area.item (child_index - 1)
		end

	array_item (i: INTEGER): ARRAYED_TREE [G] is
			-- Entry at index i, if in index interval
			-- Was declared in ARRAY as synonym of @.
			-- (from ARRAY)
		require -- from TABLE
			valid_key: array_valid_index (k)
		do
			Result := area.item (i - lower)
		end

	last_child: like first_child is
			-- Item at last position
			-- (from ARRAYED_LIST)
		require -- from CHAIN
			not_empty: not is_leaf
		require -- from TREE
			is_not_leaf: not is_leaf
		do
			Result := area.item (arity - 1)
		end

	left_sibling: like parent is
			-- Left neighbor if any
		require -- from TREE
			is_not_root: not is_root
		do
			if position_in_parent > 1 then
				Result := parent.array_item (position_in_parent - 1)
			end
		ensure -- from TREE
			is_sibling: Result /= void implies is_sibling (Result)
			right_is_current: (Result /= void) implies (Result.right_sibling = Current)
		end

	sequential_occurrences (v: ARRAYED_TREE [G]): INTEGER is
			-- Number of times v appears.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from LINEAR)
		do
			from
				child_start
				search_child (v)
			until
				exhausted
			loop
				Result := Result + 1
				child_forth
				search_child (v)
			end
		ensure -- from BAG
			non_negative_occurrences: Result >= 0
		end

	parent: ARRAYED_TREE [G]
			-- Parent of current node

	right_sibling: like parent is
			-- Right neighbor if any
		require -- from TREE
			is_not_root: not is_root
		do
			if position_in_parent < parent.arity then
				Result := parent.array_item (position_in_parent + 1)
			end
		ensure -- from TREE
			is_sibling: Result /= void implies is_sibling (Result)
			left_is_current: (Result /= void) implies (Result.left_sibling = Current)
		end

	infix "@" (i: INTEGER): ARRAYED_TREE [G] is
			-- Entry at index i, if in index interval
			-- Was declared in ARRAY as synonym of item.
			-- (from ARRAY)
		require -- from TABLE
			valid_key: array_valid_index (k)
		do
			Result := area.item (i - lower)
		end
	
feature {NONE} -- Access

	area: SPECIAL [ARRAYED_TREE [G]]
			-- Special data zone
			-- (from TO_SPECIAL)

	entry (i: INTEGER): ARRAYED_TREE [G] is
			-- Entry at index i, if in index interval
			-- (from ARRAY)
		require -- from ARRAY
			valid_key: array_valid_index (i)
		do
			Result := array_item (i)
		end

	al_has (v: ARRAYED_TREE [G]): BOOLEAN is
			-- Does v appear in array?
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from ARRAY)
		local
			i: INTEGER
			upper_bound: INTEGER
		do
			upper_bound := upper
			if object_comparison then
				if v = void then
					i := upper_bound + 1
				else
					from
						i := lower
					until
						i > upper_bound or else (array_item (i) /= void and then array_item (i).is_equal (v))
					loop
						i := i + 1
					end
				end
			else
				from
					i := lower
				until
					i > upper_bound or else (array_item (i) = v)
				loop
					i := i + 1
				end
			end
			Result := not (i > upper_bound)
		ensure -- from CONTAINER
			not_found_in_empty: Result implies not is_leaf
		end

	sequential_has (v: like child): BOOLEAN is
			-- Does structure include an occurrence of v?
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from LINEAR)
		do
			child_start
			if not child_off then
				search_child (v)
			end
			Result := not exhausted
		ensure -- from CONTAINER
			not_found_in_empty: Result implies not is_leaf
		end

	sequential_index_of (v: like child; 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
					child_start
					pos := 1
				until
					child_off or (occur = i)
				loop
					if child /= void and then v.is_equal (child) then
						occur := occur + 1
					end
					child_forth
					pos := pos + 1
				end
			else
				from
					child_start
					pos := 1
				until
					child_off or (occur = i)
				loop
					if child = v then
						occur := occur + 1
					end
					child_forth
					pos := pos + 1
				end
			end
			if occur = i then
				Result := pos - 1
			end
		ensure -- from LINEAR
			non_negative_result: Result >= 0
		end

	sequential_search (v: like child) 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 (child /= void and then v.is_equal (child))
				loop
					child_forth
				end
			else
				from
				until
					exhausted or else v = child
				loop
					child_forth
				end
			end
		ensure -- from LINEAR
			object_found: (not exhausted and object_comparison) implies equal (v, child)
			item_found: (not exhausted and not object_comparison) implies v = child
		end
	
feature -- Measurement

	child_capacity: INTEGER is
			-- Maximal number of children
			-- (from TREE)
		do
			Result := arity
		end

	count: INTEGER is
			-- Number of items
			-- (from TREE)
		do
			Result := subtree_count + 1
		end

	arity: INTEGER
			-- Number of items.
			-- (from ARRAYED_LIST)

	index_set: INTEGER_INTERVAL is
			-- Range of acceptable indexes
			-- (from CHAIN)
		do
			create Result.make (1, arity)
		ensure -- from INDEXABLE
			not_void: Result /= void
		ensure then -- from CHAIN
			count_definition: Result.count = arity
		end

	occurrences (v: like child): INTEGER is
			-- Number of times v appears.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from CHAIN)
		local
			pos: CURSOR
		do
			pos := child_cursor
			Result := sequential_occurrences (v)
			child_go_to (pos)
		ensure -- from BAG
			non_negative_occurrences: Result >= 0
		end

	occurrences (v: like child): INTEGER is
			-- Number of times v appears.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from CHAIN)
		local
			pos: CURSOR
		do
			pos := child_cursor
			Result := sequential_occurrences (v)
			child_go_to (pos)
		ensure -- from BAG
			non_negative_occurrences: Result >= 0
		end
	
feature {NONE} -- Measurement

	additional_space: INTEGER is
			-- Proposed number of additional items
			-- (from RESIZABLE)
		do
			Result := (capacity * growth_percentage // 100).max (minimal_increase)
		ensure -- from RESIZABLE
			at_least_one: Result >= 1
		end

	array_count: INTEGER is
			-- Number of available indices
			-- (from ARRAY)
		do
			Result := upper - lower + 1
		ensure then -- from ARRAY
			consistent_with_bounds: Result = upper - lower + 1
		end

	Growth_percentage: INTEGER is 50
			-- Percentage by which structure will grow automatically
			-- (from RESIZABLE)

	array_index_set: INTEGER_INTERVAL is
			-- Range of acceptable indexes
			-- (from ARRAY)
		do
			create Result.make (lower, upper)
		ensure -- from INDEXABLE
			not_void: Result /= void
		ensure then -- from ARRAY
			same_count: Result.count = arity
			same_bounds: ((Result.lower = lower) and (Result.upper = upper))
		end

	lower: INTEGER
			-- Minimum index
			-- (from ARRAY)

	Minimal_increase: INTEGER is 5
			-- Minimal number of additional items
			-- (from RESIZABLE)

	upper: INTEGER
			-- Maximum index
			-- (from ARRAY)
	
feature  -- Measurement

	capacity: INTEGER is
			-- Number of available indices
			-- Was declared in ARRAY as synonym of count.
			-- (from ARRAY)
		do
			Result := upper - lower + 1
		ensure then -- from ARRAY
			consistent_with_bounds: Result = upper - lower + 1
		end
	
feature -- Comparison

	is_equal (other: like Current): BOOLEAN is
			-- Does other contain the same elements?
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from TREE)
		require -- from ANY
			other_not_void: other /= void
		do
			if Current = other then
				Result := True
			else
				Result := (is_leaf = other.is_leaf) and (object_comparison = other.object_comparison) and (child_capacity = other.child_capacity)
				if Result and not is_leaf then
					Result := tree_is_equal (Current, other)
				end
			end
		ensure -- from ANY
			symmetric: Result implies other.is_equal (Current)
			consistent: standard_is_equal (other) implies Result
		ensure then -- from LIST
			indices_unchanged: child_index = old child_index and other.child_index = old other.child_index
			true_implies_same_size: Result implies arity = other.arity
		end
	
feature -- Status report

	child_after: BOOLEAN is
			-- Is there no valid cursor position to the right of cursor?
			-- (from LIST)
		do
			Result := (child_index = arity + 1)
		end

	child_before: BOOLEAN is
			-- Is there no valid cursor position to the left of cursor?
			-- (from LIST)
		do
			Result := (child_index = 0)
		end

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

	child_isfirst: BOOLEAN is
			-- Is cursor under first child?
			-- (from TREE)
		do
			Result := not is_leaf and child_index = 1
		ensure -- from CHAIN
			valid_position: Result implies not is_leaf
		ensure -- from TREE
			not_is_leaf: Result implies not is_leaf
		end

	child_islast: BOOLEAN is
			-- Is cursor under last child?
			-- (from TREE)
		do
			Result := not is_leaf and child_index = child_capacity
		ensure -- from CHAIN
			valid_position: Result implies not is_leaf
		ensure -- from TREE
			not_is_leaf: Result implies not is_leaf
		end

	child_readable: BOOLEAN is
			-- Is there a current child_item to be read?
			-- (from TREE)
		do
			Result := not child_off and then (child /= void)
		end

	child_writable: BOOLEAN is
			-- Is there a current child_item that may be modified?
			-- (from TREE)
		do
			Result := not child_off and then (child /= void)
		end

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

	Extendible: BOOLEAN is True
			-- May new items be added?
			-- (from DYNAMIC_TREE)

	Al_extendible: BOOLEAN is True
			-- May new items be added? (Answer: yes.)
			-- (from DYNAMIC_CHAIN)

	has (v: G): BOOLEAN is
			-- Does subtree include v?
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from TREE)
		do
			if object_comparison then
				Result := (v /= void) and then (item /= void) and then (v.is_equal (item) or else subtree_has (v))
			else
				Result := v = item or else subtree_has (v)
			end
		ensure -- from CONTAINER
			not_found_in_empty: Result implies not is_leaf
		end

	is_empty: BOOLEAN is
			-- Is structure empty of items?
			-- (from TREE)
		do
			Result := False
		end

	is_inserted (v: ARRAYED_TREE [G]): BOOLEAN is
			-- Has v been inserted at the end by the most recent put or
			-- extend?
			-- (from ARRAYED_LIST)
		do
			check
				put_constraint: (v /= last_child) implies not child_off
			end
			Result := (v = last_child) or else (v = child)
		end

	is_leaf: BOOLEAN is
			-- Are there no children?
			-- (from TREE)
		do
			Result := arity = 0
		end

	is_root: BOOLEAN is
			-- Is there no parent?
			-- (from TREE)
		do
			Result := parent = void
		end

	is_sibling (other: like parent): BOOLEAN is
			-- Are current node and other siblings?
			-- (from TREE)
		require -- from TREE
			other_exists: other /= void
		do
			Result := not is_root and other.parent = parent
		ensure -- from TREE
			not_root: Result implies not is_root
			other_not_root: Result implies not other.is_root
			same_parent: Result = not is_root and other.parent = parent
		end

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

	child_off: BOOLEAN is
			-- Is there no current item?
			-- (from CHAIN)
		do
			Result := (child_index = 0) or (child_index = arity + 1)
		end

	prunable: BOOLEAN is
			-- May items be removed? (Answer: yes.)
			-- (from ARRAYED_LIST)
		do
			Result := True
		end

	Readable: BOOLEAN is True
			-- (from TREE)

	readable_child: BOOLEAN is
			-- Is there a current item that may be read?
			-- (from SEQUENCE)
		do
			Result := not child_off
		end

	valid_cursor (p: C