Automatic generation produced by ISE Eiffel

Classes
Clusters
Cluster hierarchy
Chart
Relations
Text
Flat
Contracts
Flat contracts
Go to: 
indexing
	description: "Dynamically modifiable circular chains"
	status: "See notice at end of class"
	names: dynamic_circular, ring, sequence
	access: index, cursor, membership
	contents: generic
	date: "$Date: 2001/11/16 20:34:19 $"
	revision: "$Revision: 1.1.1.1 $"

deferred class 
	DYNAMIC_CIRCULAR [G]

feature -- Access

	cursor: CURSOR is
			-- Current cursor position
			-- (from CURSOR_STRUCTURE)
		deferred
		end

	first: G is
			-- Item at position currently defined as first
			-- (from CIRCULAR)
		require -- from CHAIN
			not_empty: not is_empty
		local
			pos: INTEGER
		do
			pos := standard_index
			start
			Result := item
			move (pos - 1)
		end

	has (v: like item): BOOLEAN is
			-- Does chain include v?
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from CHAIN)
		local
			pos: CURSOR
		do
			pos := cursor
			Result := sequential_has (v)
			go_to (pos)
		ensure -- from CONTAINER
			not_found_in_empty: Result implies not is_empty
		end

	i_th (i: INTEGER): like item is
			-- Item at i-th position
			-- Was declared in CHAIN as synonym of @.
			-- (from CHAIN)
		require -- from TABLE
			valid_key: valid_index (k)
		local
			pos: CURSOR
		do
			pos := cursor
			go_i_th (i)
			Result := item
			go_to (pos)
		end

	index: INTEGER is
			-- Current cursor index, with respect to position
			-- currently defined as first
			-- (from CIRCULAR)
		local
			first_ind, std_ind: INTEGER
			p: CURSOR
		do
			p := cursor
			std_ind := standard_index
			start
			first_ind := standard_index
			Result := std_ind - first_ind + 1
			if Result < 0 then
				Result := count + Result
			end
			move (Result - 1)
			go_to (p)
		end

	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: G is
			-- Item at current position
			-- (from TRAVERSABLE)
		require -- from TRAVERSABLE
			not_off: not off
		require -- from ACTIVE
			readable: readable
		deferred
		end

	last: like first is
			-- Item at position currently defined as last
			-- (from CIRCULAR)
		require -- from CHAIN
			not_empty: not is_empty
		local
			pos: INTEGER
		do
			pos := standard_index
			finish
			Result := item
			start
			move (pos - 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): like item is
			-- Item at i-th position
			-- Was declared in CHAIN as synonym of i_th.
			-- (from CHAIN)
		require -- from TABLE
			valid_key: valid_index (k)
		local
			pos: CURSOR
		do
			pos := cursor
			go_i_th (i)
			Result := item
			go_to (pos)
		end
	
feature {NONE} -- Access

	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 is
			-- Number of items
			-- (from FINITE)
		deferred
		end

	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 -- Status report

	after: BOOLEAN is
			-- Is there no valid cursor position to the right of cursor?
			-- (from CIRCULAR)
		do
			Result := is_empty and standard_after
		ensure then -- from CIRCULAR
			empty_and_std_after: Result = (is_empty and standard_after)
		end

	before: BOOLEAN is
			-- Is there no valid cursor position to the right of cursor?
			-- (from CIRCULAR)
		do
			Result := is_empty and standard_before
		ensure then -- from CIRCULAR
			empty_and_std_before: Result = (is_empty and standard_before)
		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 CIRCULAR)
		do
			Result := is_empty or internal_exhausted
		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?
			-- (from BOX)
		deferred
		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 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

	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 CIRCULAR)
		do
			Result := is_empty
		ensure then -- from CIRCULAR
			only_when_empty: Result = is_empty
		end

	prunable: BOOLEAN is
			-- May items be removed? (Answer: yes.)
			-- (from DYNAMIC_CHAIN)
		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?
			-- (from CURSOR_STRUCTURE)
		deferred
		end

	valid_cursor_index (i: INTEGER): BOOLEAN is
			-- Is i a possible cursor position?
			-- (from CIRCULAR)
		do
			Result := (i >= 0) and (i <= count)
		ensure -- from CHAIN
			valid_cursor_index_definition: Result = ((i >= 0) and (i <= count + 1))
		ensure then -- from CIRCULAR
			valid_cursor_index_definition: Result = ((i >= 0) and (i <= count))
		end

	valid_index (i: INTEGER): BOOLEAN is
			-- Is i within allowable bounds?
			-- (from CHAIN)
		do
			Result := (i >= 1) 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 -- 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 to previous item, cyclically.
			-- (from CIRCULAR)
		require -- from BILINEAR
			not_before: not before
		do
			if isfirst then
				internal_exhausted := True
			end
			standard_back
			if standard_before then
				standard_finish
			end
		end

	finish is
			-- Move cursor to last position.
			-- (No effect if empty)
			-- (from CHAIN)
		do
			if not is_empty then
				go_i_th (count)
			end
		ensure then -- from CHAIN
			at_last: not is_empty implies islast
		end

	forth is
			-- Move cursor to next item, cyclically.
			-- (from CIRCULAR)
		require -- from LINEAR
			not_after: not after
		do
			if islast then
				internal_exhausted := True
			end
			standard_forth
			if standard_after then
				standard_start
			end
		ensure then -- from CIRCULAR
			moved_forth_at_end: (old index = count) implies (index = 1)
		end

	go_i_th (i: INTEGER) is
			-- Move cursor to i-th position from current start, cyclically.
			-- (from CIRCULAR)
		require -- from CHAIN
			valid_cursor_index: valid_cursor_index (i)
		require else -- from CIRCULAR
			index_big_enough: i >= 1
			not_empty: not is_empty
		do
			start
			move (i - 1)
		ensure -- from CHAIN
			position_expected: index = i
		end

	go_to (p: CURSOR) is
			-- Move cursor to position p.
			-- (from CURSOR_STRUCTURE)
		require -- from CURSOR_STRUCTURE
			cursor_position_valid: valid_cursor (p)
		deferred
		end

	move (i: INTEGER) is
			-- Move cursor to i-th item from current position,
			-- cyclically.
			-- (from CIRCULAR)
		local
			real_move, counter, start_index: INTEGER
		do
			if i /= 0 and count > 0 then
				start_index := index
				real_move := i \\ count
				if real_move < 0 then
					real_move := count + real_move
				end
				from
				until
					counter = real_move
				loop
					forth
					counter := counter + 1
				end
				if (start_index + i > count) or (start_index + i < 1) then
					internal_exhausted := True
				end
			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

	set_start is
			-- Define current position as the first.
			-- (from CIRCULAR)
		require -- from CIRCULAR
			not_empty: not is_empty
		deferred
		end

	start is
			-- Move cursor to first position.
			-- (No effect if empty)
			-- (from CHAIN)
		do
			if not is_empty then
				go_i_th (1)
			end
		ensure then -- from CHAIN
			at_first: not is_empty implies isfirst
		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: G) is
			-- Add a new occurrence of v.
			-- (from BAG)
		require -- from COLLECTION
			extendible: extendible
		deferred
		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.
			-- (from SEQUENCE)
		require -- from SEQUENCE
			extendible: extendible
		do
			extend (v)
		ensure then -- from SEQUENCE
			new_count: count = old count + 1
			item_inserted: has (v)
		end

	merge_left (other: like Current) is
			-- Merge other into current structure before cursor
			-- position. Do not move cursor. Empty other.
			-- (from DYNAMIC_CHAIN)
		require -- from DYNAMIC_CHAIN
			extendible: extendible
			not_before: not before
			other_exists: other /= void
		deferred
		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
		end

	merge_right (other: like Current) is
			-- Merge other into current structure after cursor
			-- position. Do not move cursor. Empty other.
			-- (from DYNAMIC_CHAIN)
		require -- from DYNAMIC_CHAIN
			extendible: extendible
			not_after: not after
			other_exists: other /= void
		deferred
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count + old other.count
			same_index: index = old index
			other_is_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_front (v: like item) is
			-- Add v at beginning.
			-- Do not move cursor.
			-- (from DYNAMIC_CHAIN)
		deferred
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count + 1
			item_inserted: first = v