Automatic generation produced by ISE Eiffel

Classes
Clusters
Cluster hierarchy
Chart
Relations
Text
Flat
Contracts
Flat contracts
Go to: 
indexing
	description: "Lists implemented by resizable arrays"
	status: "See notice at end of class"
	names: sequence
	representation: array
	access: index, cursor, membership
	size: fixed
	contents: generic
	date: "$Date: 2001-11-16 20:32:23 +0000 (Fri, 16 Nov 2001) $"
	revision: "$Revision: 51435 $"

class 
	ARRAYED_LIST [G]

create 
	make,
	make_filled,
	make_from_array

feature -- Initialization

	make (n: INTEGER) is
			-- Allocate list with n items.
			-- (n may be zero for empty list.)
		require
			valid_number_of_items: n >= 0
		do
			index := 0
			count := 0
			array_make (1, n)
		ensure
			correct_position: before
		end

	make_filled (n: INTEGER) is
			-- Allocate list with n items.
			-- (n may be zero for empty list.)
			-- This list will be full.
		require
			valid_number_of_items: n >= 0
		do
			index := 0
			count := n
			array_make (1, n)
		ensure
			correct_position: before
			filled: full
		end

	make_from_array (a: ARRAY [G]) is
			-- Create list from array a.
		require -- from ARRAY
			array_exists: a /= void
		do
			Precursor  (a)
			lower := 1
			count := a.count
			upper := count
			index := 0
		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 {NONE} -- Initialization

	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 -- Access

	cursor: CURSOR is
			-- Current cursor position
		do
			create {ARRAYED_LIST_CURSOR} Result.make (index)
		end

	first: G is
			-- Item at first position
		require -- from CHAIN
			not_empty: not is_empty
		do
			Result := area.item (0)
		end

	has (v: 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 (i_th (i) /= void and then i_th (i).is_equal (v))
					loop
						i := i + 1
					end
				end
			else
				from
					i := lower
				until
					i > upper_bound or else (i_th (i) = v)
				loop
					i := i + 1
				end
			end
			Result := not (i > upper_bound)
		ensure -- from CONTAINER
			not_found_in_empty: Result implies not is_empty
		end

	index: INTEGER
			-- Index of item, if valid.

	index_of (v: like item; 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 := cursor
			Result := sequential_index_of (v, i)
			go_to (pos)
		ensure -- from LINEAR
			non_negative_result: Result >= 0
		end

	item: like first is
			-- Current item
		require -- from TRAVERSABLE
			not_off: not off
		require -- from ACTIVE
			readable: readable
		require else
			index_is_valid: valid_index (index)
		do
			Result := area.item (index - 1)
		end

	i_th (i: INTEGER): 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: like first is
			-- Item at last position
		require -- from CHAIN
			not_empty: not is_empty
		do
			Result := area.item (count - 1)
		end

	sequential_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
				forth
				search (v)
			end
		ensure -- from BAG
			non_negative_occurrences: Result >= 0
		end

	infix "@" (i: INTEGER): 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 [G]
			-- Special data zone
			-- (from TO_SPECIAL)

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

	sequential_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

	sequential_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
					forth
					pos := pos + 1
				end
			else
				from
					start
					pos := 1
				until
					off or (occur = i)
				loop
					if item = v then
						occur := occur + 1
					end
					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 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
					forth
				end
			else
				from
				until
					exhausted or else v = item
				loop
					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 -- Measurement

	count: INTEGER
			-- Number of items.

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

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

	occurrences (v: like item): INTEGER is
			-- Number of times v appears.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from CHAIN)
		local
			pos: CURSOR
		do
			pos := cursor
			Result := sequential_occurrences (v)
			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 = count
			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?
			-- (from LIST)
		require -- from ANY
			other_not_void: other /= void
		local
			c1, c2: CURSOR
		do
			if Current = other then
				Result := True
			else
				Result := (is_empty = other.is_empty) and (object_comparison = other.object_comparison)
				if Result and not is_empty then
					c1 ?= cursor
					c2 ?= other.cursor
					check
						cursors_exist: c1 /= void and c2 /= void
					end
					from
						start
						other.start
					until
						after or not Result
					loop
						if object_comparison then
							Result := equal (item, other.item)
						else
							Result := (item = other.item)
						end
						forth
						other.forth
					end
					go_to (c1)
					other.go_to (c2)
				elseif is_empty and other.is_empty and object_comparison = other.object_comparison then
					Result := True
				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: index = old index and other.index = old other.index
			true_implies_same_size: Result implies count = other.count
		end
	
feature -- Status report

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

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

	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 True
			-- May new items be added? (Answer: yes.)
			-- (from DYNAMIC_CHAIN)

	full: BOOLEAN is
			-- Is structure filled to capacity?
		do
			Result := (count = capacity)
		end

	is_empty: BOOLEAN is
			-- Is structure empty?
			-- (from FINITE)
		do
			Result := (count = 0)
		end

	is_inserted (v: G): BOOLEAN is
			-- Has v been inserted at the end by the most recent put or
			-- extend?
		do
			check
				put_constraint: (v /= last) implies not off
			end
			Result := (v = last) or else (v = item)
		end

	isfirst: BOOLEAN is
			-- Is cursor at first position?
			-- (from CHAIN)
		do
			Result := not is_empty and (index = 1)
		ensure -- from CHAIN
			valid_position: Result implies not is_empty
		end

	islast: BOOLEAN is
			-- Is cursor at last position?
			-- (from CHAIN)
		do
			Result := not is_empty and (index = count)
		ensure -- from CHAIN
			valid_position: Result implies not is_empty
		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?
			-- (from CHAIN)
		do
			Result := (index = 0) or (index = count + 1)
		end

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

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

	valid_cursor (p: CURSOR): BOOLEAN is
			-- Can the cursor be moved to position p?
		local
			al_c: ARRAYED_LIST_CURSOR
		do
			al_c ?= p
			if al_c /= void then
				Result := valid_cursor_index (al_c.index)
			end
		end

	valid_cursor_index (i: INTEGER): BOOLEAN is
			-- Is i correctly bounded for cursor movement?
			-- (from CHAIN)
		do
			Result := (i >= 0) and (i <= count + 1)
		ensure -- from CHAIN
			valid_cursor_index_definition: Result = ((i >= 0) and (i <= count + 1))
		end

	valid_index (i: INTEGER): BOOLEAN is
			-- Is i a valid index?
		do
			Result := (1 <= i) and (i <= count)
		ensure then -- from INDEXABLE
			only_if_in_index_set: Result implies ((i >= index_set.lower) and (i <= index_set.upper))
		ensure then -- from CHAIN
			valid_index_definition: Result = ((i >= 1) and (i <= count))
		end

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

	all_cleared: BOOLEAN is
		obsolete "Use `all_default' instead"
			-- Are all items set to default values?
			-- (from ARRAY)
		do
			Result := all_default
		end

	all_default: BOOLEAN is
			-- Are all items set to default values?
			-- (from ARRAY)
		do
			Result := area.all_default (upper - lower)
		ensure -- from ARRAY
			definition: Result = (count = 0 or else ((i_th (upper) = void or else i_th (upper) = i_th (upper).default) and subarray (lower, upper - 1).all_default))
		end

	resizable: BOOLEAN is
			-- May capacity be changed? (Answer: yes.)
			-- (from RESIZABLE)
		do
			Result := True
		end

	same_items (other: like Current): BOOLEAN is
			-- Do other and Current have same items?
			-- (from ARRAY)
		require -- from ARRAY
			other_not_void: other /= void
		do
			if count = other.count then
				Result := area.same_items (other.area, upper - lower)
			end
		ensure -- from ARRAY
			definition: Result = ((count = other.count) and then (count = 0 or else (i_th (upper) = other.i_th (other.upper) and subarray (lower, upper - 1).same_items (other.subarray (other.lower, other.upper - 1)))))
		end

	array_valid_index (i: INTEGER): BOOLEAN is
			-- Is i within the bounds of the array?
			-- (from ARRAY)
		do
			Result := (lower <= i) and then (i <= upper)
		ensure then -- from INDEXABLE
			only_if_in_index_set: Result implies ((i >= index_set.lower) and (i <= index_set.upper))
		end

	valid_index_set: BOOLEAN is
			-- (from ARRAY)
		do
			Result := index_set.count = count
		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.
		require -- from BILINEAR
			not_before: not before
		do
			index := index - 1
		end

	finish is
			-- Move cursor to last position if any.
		do
			index := count
		ensure then -- from CHAIN
			at_last: not is_empty implies islast
		ensure then
			before_when_empty: is_empty implies before
		end

	forth is
			-- Move cursor one position forward.
		require -- from LINEAR
			not_after: not after
		do
			index := index + 1
		ensure then -- from LIST
			moved_forth: index = old index + 1
		end

	go_i_th (i: INTEGER) is
			-- Move cursor to i-th position.
		require -- from CHAIN
			valid_cursor_index: valid_cursor_index (i)
		do
			index := i
		ensure -- from CHAIN
			position_expected: index = i
		end

	go_to (p: CURSOR) is
			-- Move cursor to position p.
		require -- from CURSOR_STRUCTURE
			cursor_position_valid: valid_cursor (p)
		local
			al_c: ARRAYED_LIST_CURSOR
		do
			al_c ?= p
			check
				al_c /= void
			end
			index := al_c.index
		end

	move (i: INTEGER) is
			-- Move cursor i positions.
		do
			index := index + i
			if (index > count + 1) then
				index := count + 1
			elseif (index < 0) then
				index := 0
			end
		ensure -- from CHAIN
			too_far_right: (old index + i > count) implies exhausted
			too_far_left: (old index + i < 1) implies exhausted
			expected_index: (not exhausted) implies (index = old index + i)
		end

	search (v: like item) is
			-- Move to first position (at or after current
			-- position) where item and v are equal.
			-- If structure does not include v ensure that
			-- exhausted will be true.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from BILINEAR)
		do
			if before and not is_empty then
				forth
			end
			sequential_search (v)
		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

	start is
			-- Move cursor to first position if any.
		do
			index := 1
		ensure then -- from CHAIN
			at_first: not is_empty implies isfirst
		ensure then
			after_when_empty: is_empty implies after
		end
	
feature -- Element change

	append (s: SEQUENCE [G]) is
			-- Append a copy of s.
			-- (from SEQUENCE)
		require -- from SEQUENCE
			argument_not_void: s /= void
		local
			l: like s
		do
			if s = Current then
				l := deep_clone (s)
			else
				l := s
			end
			from
				l.start
			until
				l.exhausted
			loop
				extend (l.item)
				l.forth
			end
		ensure -- from SEQUENCE
			new_count: count >= old count
		end

	extend (v: like item) is
			-- Add v to end.
			-- Do not move cursor.
			-- Was declared in ARRAYED_LIST as synonym of force.
		require -- from COLLECTION
			extendible: extendible
		do
			count := count + 1
			force_i_th (v, count)
		ensure -- from COLLECTION
			item_inserted: is_inserted (v)
		ensure then -- from BAG
			one_more_occurrence: occurrences (v) = old (occurrences (v)) + 1
		end

	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

	force (v: like item) is
			-- Add v to end.
			-- Do not move cursor.
			-- Was declared in ARRAYED_LIST as synonym of extend.
		require -- from SEQUENCE
			extendible: extendible
		do
			count := count + 1
			force_i_th (v, count)
		ensure then -- from SEQUENCE
			new_count: count = old count + 1
			item_inserted: has (v)
		end

	merge_left (other: ARRAYED_LIST [G]) is
			-- Merge other into current structure before cursor.
		require -- from DYNAMIC_CHAIN
			extendible: extendible
			not_before: not before
			other_exists: other /= void
		local
			old_index: INTEGER
			old_other_count: INTEGER
		do
			old_index := index
			old_other_count := other.count
			index := index - 1
			merge_right (other)
			index := old_index + old_other_count
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count + old other.count
			new_index: index = old index + old other.count
			other_is_empty: other.is_empty
		ensure then -- from DYNAMIC_LIST
			other_empty: other.is_empty
		end

	merge_right (other: ARRAYED_LIST [G]) is
			-- Merge other into current structure after cursor.
		require -- from DYNAMIC_CHAIN
			extendible: extendible
			not_after: not after
			other_exists: other /= void
		do
			if not other.is_empty then
				resize (1, count + other.count)
				if index < count then
					subcopy (Current, index + 1, count, index + other.count + 1)
				end
				subcopy (other, 1, other.count, index + 1)
				count := count + other.count
				other.wipe_out
			end
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count + old other.count
			same_index: index = old index
			other_is_empty: other.is_empty
		ensure then -- from DYNAMIC_LIST
			other_empty: other.is_empty
		end

	put (v: like item) is
			-- Replace current item by v.
			-- (Synonym for replace)
			-- (from CHAIN)
		require -- from COLLECTION
			extendible: extendible
		do
			replace (v)
		ensure -- from COLLECTION
			item_inserted: is_inserted (v)
		ensure then -- from CHAIN
			same_count: count = old count
		end

	put_i_th (v: like i_th; i: INTEGER) is
			-- Replace i-th entry, if in index interval, by v.
			-- (from ARRAY)
		require -- from TABLE
			valid_key: array_valid_index (k)
		do
			area.put (v, i - lower)
		ensure then -- from INDEXABLE
			insertion_done: i_th (k) = v
		end

	put_front (v: like item) is
			-- Add v to the beginning.
			-- Do not move cursor.
		do
			if is_empty then
				extend (v)
			else
				insert (v, 1)
			end
			index := index + 1
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count + 1
			item_inserted: first = v
		end

	put_left (v: like item) is
			-- Add v to the left of current position.
			-- Do not move cursor.
		require -- from DYNAMIC_CHAIN
			extendible: extendible
			not_before: not before
		do
			if after or is_empty then
				extend (v)
			else
				insert (v, index)
			end
			index := index + 1
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count + 1
			new_index: index = old index + 1
		end

	put_right (v: like item) is
			-- Add v to the right of current position.
			-- Do not move cursor.
		require -- from DYNAMIC_CHAIN
			extendible: extendible
			not_after: not after
		do
			if index = count then
				extend (v)
			else
				insert (v, index + 1)
			end
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count + 1
			same_index: index = old index
		end

	replace (v: like first) is
			-- Replace current item by v.
		require -- from ACTIVE
			writable: writable
		do
			put_i_th (v, index)
		ensure -- from ACTIVE
			item_replaced: item = v
		end
	
feature {NONE} -- Element change

	enter (v: like i_th; i: INTEGER) is
			-- Replace i-th entry, if in index interval, by v.
			-- (from ARRAY)
		require -- from ARRAY
			valid_key: array_valid_index (i)
		do
			area.put (v, i - lower)
		end

	force_i_th (v: like i_th; i: INTEGER) is
			-- Assign item v to i-th entry.
			-- Always applicable: resize the array if i falls out of
			-- currently defined bounds; preserve existing items.
			-- (from ARRAY)
		do
			if i < lower then
				auto_resize (i, upper)
			elseif i > upper then
				auto_resize (lower, i)
			end
			put_i_th (v, i)
		ensure -- from ARRAY
			inserted: i_th (i) = v
			higher_count: count >= old count
		end

	sequence_put (v: like item) is
			-- Add v to end.
			-- (from SEQUENCE)
		require -- from COLLECTION
			extendible: extendible
		do
			extend (v)
		ensure -- from COLLECTION
			item_inserted: is_inserted (v)
		ensure then -- from SEQUENCE
			new_count: count = old count + 1
		end

	set_area (other: like area) is
			-- Make other the new area
			-- (from TO_SPECIAL)
		do
			area := other
		end
	
feature {ARRAYED_LIST} -- Element change

	subcopy (other: like Current; start_pos, end_pos, index_pos: INTEGER) is
			-- Copy items of other within bounds start_pos and end_pos
			-- to current array starting at index index_pos.
			-- (from ARRAY)
		require -- from ARRAY
			other_not_void: other /= void
			valid_start_pos: other.array_valid_index (start_pos)
			valid_end_pos: other.array_valid_index (end_pos)
			valid_bounds: (start_pos <= end_pos) or (start_pos = end_pos + 1)
			valid_index_pos: array_valid_index (index_pos)
			enough_space: (upper - index_pos) >= (end_pos - start_pos)
		local
			other_area: like area
			other_lower: INTEGER
			start0, end0, index0: INTEGER
		do
			other_area := other.area
			other_lower := other.lower
			start0 := start_pos - other_lower
			end0 := end_pos - other_lower
			index0 := index_pos - lower
			spsubcopy ($other_area, $area, start0, end0, index0)
		end
	
feature -- Removal

	prune (v: like item) is
			-- Remove first occurrence of v, if any,
			-- after cursor position.
			-- Move cursor to right neighbor.
			-- (or after if no right neighbor or v does not occur)
		require -- from COLLECTION
			prunable: prunable
		do
			if before then
				index := 1
			end
			if object_comparison then
				if v /= void then
					from
					until
						after or else (item /= void and then v.is_equal (item))
					loop
						forth
					end
				end
			else
				from
				until
					after or else item = v
				loop
					forth
				end
			end
			if not after then
				remove
			end
		end

	prune_all (v: like item) is
			-- Remove all occurrences of v.
			-- (Reference or object equality,
			-- based on object_comparison.)
		require -- from COLLECTION
			prunable
		local
			i: INTEGER
			offset: INTEGER
			res: BOOLEAN
			obj_cmp: BOOLEAN
			default_val: like item
		do
			obj_cmp := object_comparison
			from
				i := 1
			until
				i > count
			loop
				if i <= count - offset then
					if offset > 0 then
						put_i_th (i_th (i + offset), i)
					end
					if obj_cmp then
						res := equal (v, i_th (i))
					else
						res := (v = i_th (i))
					end
					if res then
						offset := offset + 1
					else
						i := i + 1
					end
				else
					put_i_th (default_val, i)
					i := i + 1
				end
			end
			count := count - offset
			index := count + 1
		ensure -- from COLLECTION
			no_more_occurrences: not has (v)
		ensure then -- from DYNAMIC_CHAIN
			is_exhausted: exhausted
		ensure then
			is_after: after
		end

	remove is
			-- Remove current item.
			-- Move cursor to right neighbor
			-- (or after if no right neighbor)
		require -- from ACTIVE
			prunable: prunable
			writable: writable
		local
			default_value: G
		do
			if index < count then
				subcopy (Current, index + 1, count, index)
			end
			count := count - 1
			area.put (default_value, count)
		ensure then -- from DYNAMIC_LIST
			after_when_empty: is_empty implies after
		ensure then
			index: index = old index
		end

	remove_left is
			-- Remove item to the left of cursor position.
			-- Do not move cursor.
		require -- from DYNAMIC_CHAIN
			left_exists: index > 1
		require else -- from DYNAMIC_LIST
			not_before: not before
		do
			index := index - 1
			remove
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count - 1
			new_index: index = old index - 1
		end

	remove_right is
			-- Remove item to the right of cursor position
			-- Do not move cursor
		require -- from DYNAMIC_CHAIN
			right_exists: index < count
		do
			index := index + 1
			remove
			index := index - 1
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count - 1
			same_index: index = old index
		end

	wipe_out is
			-- Remove all items.
		require -- from COLLECTION
			prunable
		do
			count := 0
			index := 0
			discard_items
		ensure -- from COLLECTION
			wiped_out: is_empty
		ensure then -- from DYNAMIC_LIST
			is_before: before
		end
	
feature {NONE} -- Removal

	clear_all is
			-- Reset all items to default values.
			-- (from ARRAY)
		do
			area.clear_all
		ensure -- from ARRAY
			stable_lower: lower = old lower
			stable_upper: upper = old upper
			default_items: all_default
		end

	discard_items is
			-- Reset all items to default values with reallocation.
			-- (from ARRAY)
		do
			make_area (capacity)
		ensure -- from ARRAY
			default_items: all_default
		end

	chain_wipe_out is
			-- Remove all items.
			-- (from DYNAMIC_CHAIN)
		require -- from COLLECTION
			prunable
		do
			from
				start
			until
				is_empty
			loop
				remove
			end
		ensure -- from COLLECTION
			wiped_out: is_empty
		end
	
feature {NONE} -- Resizing

	automatic_grow is
			-- Change the capacity to accommodate at least
			-- Growth_percentage more items.
			-- (from RESIZABLE)
		do
			grow (capacity + additional_space)
		ensure -- from RESIZABLE
			increased_capacity: capacity >= old capacity + old capacity * growth_percentage // 100
		end

	grow (i: INTEGER) is
			-- Change the capacity to at least i.
			-- (from ARRAY)
		do
			if i > capacity then
				resize (lower, upper + i - capacity)
			end
		ensure -- from RESIZABLE
			new_capacity: capacity >= i
		end

	resize (min_index, max_index: INTEGER) is
			-- Rearrange array so that it can accommodate
			-- indices down to min_index and up to max_index.
			-- Do not lose any previously entered item.
			-- (from ARRAY)
		require -- from ARRAY
			good_indices: min_index <= max_index
		local
			old_size, new_size, old_count: INTEGER
			new_lower, new_upper: INTEGER
		do
			if empty_area then
				new_lower := min_index
				new_upper := max_index
			else
				new_lower := min_index.min (lower)
				new_upper := max_index.max (upper)
			end
			new_size := new_upper - new_lower + 1
			if not empty_area then
				old_size := area.count
				old_count := upper - lower + 1
			end
			if empty_area then
				make_area (new_size)
			elseif new_size > old_size or new_lower < lower then
				area := arycpy ($area, new_size, lower - new_lower, old_count)
			end
			lower := new_lower
			upper := new_upper
		ensure -- from ARRAY
			no_low_lost: lower = min_index or else lower = old lower
			no_high_lost: upper = max_index or else upper = old upper
		end
	
feature -- Transformation

	swap (i: INTEGER) is
			-- Exchange item at i-th position with item
			-- at cursor position.
		require -- from CHAIN
			not_off: not off
			valid_index: array_valid_index (i)
		local
			old_item: like item
		do
			old_item := item
			replace (area.item (i - 1))
			area.put (old_item, i - 1)
		ensure -- from CHAIN
			swapped_to_item: item = old i_th (i)
			swapped_from_item: i_th (i) = old item
		end
	
feature {NONE} -- Conversion

	to_c: ANY is
			-- Address of actual sequence of values,
			-- for passing to external (non-Eiffel) routines.
			-- (from ARRAY)
		do
			Result := area
		end
	
feature -- Conversion

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

	copy (other: like Current) is
			-- Reinitialize by copying all the items of other.
			-- (This is also used by clone.)
			-- (from ARRAY)
		require -- from ANY
			other_not_void: other /= void
			type_identity: same_type (other)
		do
			if other /= Current then
				standard_copy (other)
				set_area (standard_clone (other.area))
			end
		ensure -- from ANY
			is_equal: is_equal (other)
		ensure then -- from ARRAY
			equal_areas: area.is_equal (other.area)
		end

	duplicate (n: INTEGER): like Current is
			-- Copy of sub-list beginning at current position
			-- and having min (n, count - index + 1) items.
		require -- from CHAIN
			not_off_unless_after: off implies after
			valid_subchain: n >= 0
		local
			end_pos: INTEGER
		do
			if after then
				create Result.make (0)
			else
				end_pos := count.min (index + n - 1)
				create Result.make_filled (end_pos - index + 1)
				Result.subcopy (Current, index, end_pos, 1)
			end
		end
	
feature {NONE} -- Duplication

	subarray (start_pos, end_pos: INTEGER): like Current is
			-- Array made of items of current array within
			-- bounds start_pos and end_pos.
			-- (from ARRAY)
		require -- from ARRAY
			valid_start_pos: array_valid_index (start_pos)
			valid_end_pos: array_valid_index (end_pos)
			valid_bounds: (start_pos <= end_pos) or (start_pos = end_pos + 1)
		do
			create Result.array_make (start_pos, end_pos)
			Result.subcopy (Current, start_pos, end_pos, start_pos)
		ensure -- from ARRAY
			lower: Result.lower = start_pos
			upper: Result.upper = end_pos
		end
	
feature {NONE} -- Inapplicable

	bag_put (v: G) is
			-- (from TABLE)
		require -- from COLLECTION
			extendible: extendible
		do
		ensure -- from COLLECTION
			item_inserted: is_inserted (v)
		end

	new_chain: like Current is
			-- Unused
		do
		ensure -- from DYNAMIC_CHAIN
			result_exists: Result /= void
		end
	
feature {NONE} -- Implementation

	arycpy (old_area: POINTER; newsize, s, n: INTEGER): like area is
			-- New area of size newsize containing n items
			-- from oldarea.
			-- Old items are at position s in new area.
			-- (from ARRAY)
		external
			"C | %"eif_misc.h%""
		end

	auto_resize (min_index, max_index: INTEGER) is
			-- Rearrange array so that it can accommodate
			-- indices down to min_index and up to max_index.
			-- Do not lose any previously entered item.
			-- If area must be extended, ensure that space for at least
			-- additional_space item is added.
			-- (from ARRAY)
		require -- from ARRAY
			valid_indices: min_index <= max_index
		local
			old_size, new_size: INTEGER
			new_lower, new_upper: INTEGER
		do
			if empty_area then
				new_lower := min_index
				new_upper := max_index
			else
				new_lower := min_index.min (lower)
				new_upper := max_index.max (upper)
			end
			new_size := new_upper - new_lower + 1
			if not empty_area then
				old_size := area.count
				if new_size > old_size and new_size - old_size < additional_space then
					new_size := old_size + additional_space
				end
			end
			if empty_area then
				make_area (new_size)
			elseif new_size > old_size or new_lower < lower then
				area := arycpy ($area, new_size, lower - new_lower, capacity)
			end
			lower := new_lower
			upper := new_upper
		end

	empty_area: BOOLEAN is
			-- Is area empty?
			-- (from ARRAY)
		do
			Result := (area.count = 0)
		end

	insert (v: like item; pos: INTEGER) is
			-- Add v at pos, moving subsequent items
			-- to the right.
		require
			index_small_enough: pos <= count
			index_large_enough: pos >= 1
		do
			if count + 1 > capacity then
				auto_resize (lower, count + 1)
			end
			count := count + 1
			subcopy (Current, pos, count - 1, pos + 1)
			enter (v, pos)
		ensure
			new_count: count = old count + 1
			index_unchanged: index = old index
			insertion_done: i_th (pos) = v
		end

	spsubcopy (source, target: POINTER; s, e, i: INTEGER) is
			-- Copy elements of source within bounds s
			-- and e to target starting at index i.
			-- (from ARRAY)
		external
			"C | %"eif_copy.h%""
		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 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)
				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 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
				forth
			end
		end

	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)
				forth
			end
			if cs /= void then
				cs.go_to (c)
			end
		end

	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)
				forth
			end
			if cs /= void then
				cs.go_to (c)
			end
		end
	
invariant

	prunable: prunable
	starts_from_one: lower = 1
	empty_means_storage_empty: is_empty implies all_default
		-- from ANY
	reflexive_equality: standard_is_equal (Current)
	reflexive_conformance: conforms_to (Current)
		-- from ARRAY
	area_exists: area /= void
	consistent_size: capacity = upper - lower + 1
	non_negative_count: count >= 0
	index_set_has_same_count: valid_index_set
	index_set_has_same_bounds: ((index_set.lower = lower) and (index_set.upper = lower + count - 1))
		-- from RESIZABLE
	increase_by_at_least_one: minimal_increase >= 1
		-- from BOUNDED
	valid_count: count <= capacity
	full_definition: full = (count = capacity)
		-- from FINITE
	empty_definition: is_empty = (count = 0)
	non_negative_count: count >= 0
		-- from INDEXABLE
	index_set_not_void: index_set /= void
		-- from LIST
	before_definition: before = (index = 0)
	after_definition: after = (index = count + 1)
		-- from CHAIN
	non_negative_index: index >= 0
	index_small_enough: index <= count + 1
	off_definition: off = ((index = 0) or (index = count + 1))
	isfirst_definition: isfirst = ((not is_empty) and (index = 1))
	islast_definition: islast = ((not is_empty) and (index = count))
	item_corresponds_to_index: (not off) implies (item = i_th (index))
	index_set_has_same_count: index_set.count = count
		-- from ACTIVE
	writable_constraint: writable implies readable
	empty_constraint: is_empty implies (not readable) and (not writable)
		-- from BILINEAR
	not_both: not (after and before)
	before_constraint: before implies off
		-- from LINEAR
	after_constraint: after implies off
		-- from TRAVERSABLE
	empty_constraint: is_empty implies off
		-- from DYNAMIC_CHAIN
	extendible: extendible

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 ARRAYED_LIST


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

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