Automatic generation produced by ISE Eiffel

Classes
Clusters
Cluster hierarchy
Chart
Relations
Text
Flat
Contracts
Flat contracts
Go to: 
indexing
	description: "Two-way lists, kept sorted"
	status: "See notice at end of class"
	names: sorted_two_way_list, sorted_struct, sequence
	representation: linked
	access: index, cursor, membership, min, max
	contents: generic
	date: "$Date: 2001-11-16 20:32:23 +0000 (Fri, 16 Nov 2001) $"
	revision: "$Revision: 51435 $"

class 
	PART_SORTED_TWO_WAY_LIST [G -> PART_COMPARABLE]

create 
	make

feature -- Initialization

	make is
			-- Create an empty list.
			-- (from LINKED_LIST)
		do
			before := True
		ensure -- from LINKED_LIST
			is_before: before
		end
	
feature -- Access

	cursor: CURSOR is
			-- Current cursor position
			-- (from LINKED_LIST)
		do
			create {LINKED_LIST_CURSOR [G]} Result.make (active, after, before)
		end

	first: like item is
			-- Item at first position
			-- (from LINKED_LIST)
		require -- from CHAIN
			not_empty: not is_empty
		do
			Result := first_element.item
		end

	first_element: BI_LINKABLE [G]
			-- Head of list
			-- (Anchor redefinition)
			-- (from TWO_WAY_LIST)

	has (v: G): BOOLEAN is
			-- Does structure include v?
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from PART_SORTED_LIST)
		local
			pos: CURSOR
		do
			if not is_empty then
				pos := cursor
				start
				search (v)
				Result := not after
				go_to (pos)
			end
		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
			-- Index of current position
			-- (from LINKED_LIST)
		local
			p: LINKED_LIST_CURSOR [G]
		do
			if after then
				Result := count + 1
			elseif not before then
				p ?= cursor;
				check
					p /= void
				end;
				from
					start
					Result := 1
				until
					p.active = active
				loop
					forth
					Result := Result + 1
				end;
				go_to (p)
			end
		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
			-- Current item
			-- (from LINKED_LIST)
		require -- from TRAVERSABLE
			not_off: not off
		require -- from ACTIVE
			readable: readable
		do
			Result := active.item
		end

	last: like item is
			-- Item at last position
			-- (from LINKED_LIST)
		require -- from CHAIN
			not_empty: not is_empty
		do
			Result := last_element.item
		end

	last_element: like first_element
			-- Tail of the list
			-- (from TWO_WAY_LIST)

	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

	search_after (v: like item) is
			-- Go to first position with item greater
			-- than or equal to v.
			-- (from PART_SORTED_LIST)
		do
			from
				start
			until
				after or else v <= item
			loop
				forth
			end
		ensure -- from PART_SORTED_LIST
			argument_less_than_item: (not after) implies (v <= item)
		end

	search_before (v: like item) is
			-- Go to last position with item less
			-- than or equal to v.
			-- (from PART_SORTED_LIST)
		do
			from
				finish
			until
				before or else v >= item
			loop
				back
			end
		ensure -- from PART_SORTED_LIST
			(not off) implies (item <= v)
		end

	sublist: like Current
			-- Result produced by last split
			-- (from TWO_WAY_LIST)

	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
			-- Number of items
			-- (from LINKED_LIST)

	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 -- 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 there no valid cursor position to the right of cursor?
			-- (from LINKED_LIST)

	before: BOOLEAN
			-- Is there no valid cursor position to the left of cursor?
			-- (from LINKED_LIST)

	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 False
			-- Is structured filled to capacity? (Answer: no.)
			-- (from LINKED_LIST)

	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 LINKED_LIST)
		do
			Result := not after and not before and (active = first_element)
		ensure -- from CHAIN
			valid_position: Result implies not is_empty
		end

	islast: BOOLEAN is
			-- Is cursor at last position?
			-- (from TWO_WAY_LIST)
		do
			Result := (active = last_element) and then not after and then not before
		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 LINKED_LIST)
		do
			Result := after or before
		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 LINKED_LIST)
		do
			Result := not off
		end

	sorted: BOOLEAN is
			-- is the structures topologically sorted
			-- i.e i < j implies not i_th (i) > i_th (j)
		local
			c: CURSOR
			prev: like item
		do
			Result := True
			if count > 1 then
				from
					c := cursor
					start
					check
						not off
					end
					prev := item
					forth
				until
					after or not Result
				loop
					Result := (prev <= item)
					prev := item
					forth
				end
				go_to (c)
			end
		end

	valid_cursor (p: CURSOR): BOOLEAN is
			-- Can the cursor be moved to position p?
			-- (from LINKED_LIST)
		local
			ll_c: LINKED_LIST_CURSOR [G]
			temp, sought: like first_element
		do
			ll_c ?= p
			if ll_c /= void then
				from
					temp := first_element
					sought := ll_c.active
					Result := ll_c.after or else ll_c.before
				until
					Result or else temp = void
				loop
					Result := (temp = sought)
					temp := temp.right
				end
			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 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 position, if any.
			-- (from TWO_WAY_LIST)
		require -- from BILINEAR
			not_before: not before
		do
			if after then
				after := False
				if is_empty then
					before := True
				end
			else
				active := active.left
				if active = void then
					active := first_element
					before := True
				end
			end
		end

	finish is
			-- Move cursor to last position.
			-- (Go before if empty)
			-- (from TWO_WAY_LIST)
		do
			if not is_empty then
				active := last_element
				after := False
				before := False
			else
				after := False
				before := True
			end
		ensure then -- from CHAIN
			at_last: not is_empty implies islast
		ensure then -- from LINKED_LIST
			empty_convention: is_empty implies before
		ensure then -- from TWO_WAY_LIST
			not_after: not after
		end

	forth is
			-- Move cursor to next position, if any.
			-- (from TWO_WAY_LIST)
		require -- from LINEAR
			not_after: not after
		do
			if before then
				before := False
				if is_empty then
					after := True
				end
			else
				active := active.right
				if active = void then
					active := last_element
					after := True
				end
			end
		ensure then -- from LIST
			moved_forth: index = old index + 1
		end

	go_i_th (i: INTEGER) is
			-- Move cursor to i-th position.
			-- (from LINKED_LIST)
		require -- from CHAIN
			valid_cursor_index: valid_cursor_index (i)
		do
			if i = 0 then
				before := True
				after := False
				active := first_element
			elseif i = count + 1 then
				before := False;
				after := True;
				active := last_element
			else
				move (i - index)
			end
		ensure -- from CHAIN
			position_expected: index = i
		end

	go_to (p: CURSOR) is
			-- Move cursor to position p.
			-- (from LINKED_LIST)
		require -- from CURSOR_STRUCTURE
			cursor_position_valid: valid_cursor (p)
		local
			ll_c: LINKED_LIST_CURSOR [G]
		do
			ll_c ?= p
			check
				ll_c /= void
			end
			after := ll_c.after
			before := ll_c.before
			if before then
				active := first_element
			elseif after then
				active := last_element
			else
				active := ll_c.active
			end
		end

	move (i: INTEGER) is
			-- Move cursor i positions. The cursor
			-- may end up off if the offset is to big.
			-- (from TWO_WAY_LIST)
		local
			counter: INTEGER
			p: like first_element
		do
			if i > 0 then
				ll_move (i)
			elseif i < 0 then
				if after then
					after := False;
					counter := - 1
				end;
				from
					p := active
				until
					(counter = i) or else (p = void)
				loop
					p := p.left
					counter := counter - 1
				end;
				if p = void then
					before := True;
					active := first_element
				else
					active := p
				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)
		ensure then -- from LINKED_LIST
			moved_if_inbounds: ((old index + i) >= 0 and (old index + i) <= (count + 1)) implies index = (old index + i)
			before_set: (old index + i) <= 0 implies before
			after_set: (old index + i) >= (count + 1) implies after
		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.
			-- (from LINKED_LIST)
		do
			if first_element /= void then
				active := first_element
				after := False
			else
				after := True
			end
			before := False
		ensure then -- from CHAIN
			at_first: not is_empty implies isfirst
		ensure then -- from LINKED_LIST
			empty_convention: is_empty implies after
		end
	
feature {NONE} -- Cursor movement

	ll_move (i: INTEGER) is
			-- Move cursor i positions. The cursor
			-- may end up off if the offset is too big.
			-- (from LINKED_LIST)
		local
			counter, new_index: INTEGER
			p: like first_element
		do
			if i > 0 then
				if before then
					before := False
					counter := 1
				end
				from
					p := active
				until
					(counter = i) or else (p = void)
				loop
					active := p
					p := p.right
					counter := counter + 1
				end
				if p = void then
					after := True
				else
					active := p
				end
			elseif i < 0 then
				new_index := index + i;
				before := True;
				after := False;
				active := first_element;
				if (new_index > 0) then
					move (new_index)
				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)
		ensure then -- from LINKED_LIST
			moved_if_inbounds: ((old index + i) >= 0 and (old index + i) <= (count + 1)) implies index = (old index + i)
			before_set: (old index + i) <= 0 implies before
			after_set: (old index + i) >= (count + 1) 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
			-- Put v at proper position in list.
			-- The cursor ends up on the newly inserted
			-- item.
		require -- from COLLECTION
			extendible: extendible
		do
			search_after (v)
			put_left (v)
			back
		ensure -- from COLLECTION
			item_inserted: is_inserted (v)
		ensure then -- from BAG
			one_more_occurrence: occurrences (v) = old (occurrences (v)) + 1
		ensure then -- from PART_SORTED_LIST
			remains_sorted: (old sorted) implies sorted
			item_inserted: item = v
		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 (other: LINEAR [G]) is
			-- Add all items from other at their proper positions.
			-- (from PART_SORTED_LIST)
		do
			from
				other.start
			until
				other.off
			loop
				extend (other.item)
				other.forth
			end
		ensure then -- from PART_SORTED_LIST
			remains_sorted: (old sorted) implies sorted
		end

	merge_left (other: like Current) is
			-- Merge other into current structure before cursor
			-- position. Do not move cursor. Empty other.
			-- (from TWO_WAY_LIST)
		require -- from DYNAMIC_CHAIN
			extendible: extendible
			not_before: not before
			other_exists: other /= void
		local
			other_first_element: like first_element
			other_last_element: like first_element
			other_count: INTEGER
		do
			if not other.is_empty then
				other_first_element := other.first_element
				other_last_element := other.last_element
				other_count := other.count
				check
					other_first_element /= void
					other_last_element /= void
				end
				if is_empty then
					last_element := other_last_element
					first_element := other_first_element
					if before then
						active := first_element
					else
						active := last_element
					end
				elseif isfirst then
					other_last_element.put_right (first_element);
					first_element := other_first_element
				elseif after then
					other_first_element.put_left (last_element);
					last_element := other_last_element;
					active := last_element
				else
					other_first_element.put_left (active.left)
					active.put_left (other_last_element)
				end
				count := count + other_count
				other.wipe_out
			end
		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: like Current) is
			-- Merge other into current structure after cursor
			-- position. Do not move cursor. Empty other.
			-- (from TWO_WAY_LIST)
		require -- from DYNAMIC_CHAIN
			extendible: extendible
			not_after: not after
			other_exists: other /= void
		do
			if is_empty or else islast then
				last_element := other.last_element
			end
			ll_merge_right (other)
		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_front (v: like item) is
			-- Add v to beginning.
			-- Do not move cursor.
			-- (from TWO_WAY_LIST)
		do
			ll_put_front (v)
			if count = 1 then
				last_element := first_element
			end
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count + 1
			item_inserted: first = v
		end

	put_i_th (v: like item; i: INTEGER) is
			-- Put v at i-th position.
			-- (from CHAIN)
		require -- from TABLE
			valid_key: valid_index (k)
		local
			pos: CURSOR
		do
			pos := cursor
			go_i_th (i)
			replace (v)
			go_to (pos)
		ensure then -- from INDEXABLE
			insertion_done: i_th (k) = v
		end

	put_left (v: like item) is
			-- Add v to the left of cursor position.
			-- Do not move cursor.
			-- (from TWO_WAY_LIST)
		require -- from DYNAMIC_CHAIN
			extendible: extendible
			not_before: not before
		local
			p: like first_element
		do
			p := new_cell (v)
			if is_empty then
				first_element := p
				last_element := p
				active := p
				before := False
			elseif after then
				p.put_left (last_element);
				last_element := p;
				active := p
			elseif isfirst then
				p.put_right (active);
				first_element := p
			else
				p.put_left (active.left)
				p.put_right (active)
			end
			count := count + 1
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count + 1
			new_index: index = old index + 1
		ensure then -- from LINKED_LIST
			previous_exists: previous /= void
			item_inserted: previous.item = v
		end

	put_right (v: like item) is
			-- Add v to the right of cursor position.
			-- Do not move cursor.
			-- (from TWO_WAY_LIST)
		require -- from DYNAMIC_CHAIN
			extendible: extendible
			not_after: not after
		local
			was_last: BOOLEAN
		do
			was_last := islast
			ll_put_right (v)
			if count = 1 then
				last_element := active
			elseif was_last then
				last_element := active.right
			end
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count + 1
			same_index: index = old index
		ensure then -- from LINKED_LIST
			next_exists: next /= void
			item_inserted: not old before implies next.item = v
			item_inserted_before: old before implies active.item = v
		end

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

	ll_merge_right (other: like Current) is
			-- Merge other into current structure after cursor
			-- position. Do not move cursor. Empty other.
			-- (from LINKED_LIST)
		require -- from DYNAMIC_CHAIN
			extendible: extendible
			not_after: not after
			other_exists: other /= void
		local
			other_first_element: like first_element
			other_last_element: like first_element
			other_count: INTEGER
		do
			if not other.is_empty then
				other_first_element := other.first_element
				other_last_element := other.last_element
				other_count := other.count
				check
					other_first_element /= void
					other_last_element /= void
				end
				if is_empty then
					first_element := other_first_element
					active := first_element
				else
					if not islast then
						other_last_element.put_right (active.right)
					end
					active.put_right (other_first_element)
				end
				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

	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

	ll_put_front (v: like item) is
			-- Add v to beginning.
			-- Do not move cursor.
			-- (from LINKED_LIST)
		local
			p: like first_element
		do
			p := new_cell (v)
			p.put_right (first_element)
			first_element := p
			if before or is_empty then
				active := p
			end
			count := count + 1
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count + 1
			item_inserted: first = v
		end

	ll_put_right (v: like item) is
			-- Add v to the right of cursor position.
			-- Do not move cursor.
			-- (from LINKED_LIST)
		require -- from DYNAMIC_CHAIN
			extendible: extendible
			not_after: not after
		local
			p: like first_element
		do
			p := new_cell (v)
			check
				is_empty implies before
			end
			if before then
				p.put_right (first_element)
				first_element := p
				active := p
			else
				p.put_right (active.right)
				active.put_right (p)
			end
			count := count + 1
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count + 1
			same_index: index = old index
		ensure then -- from LINKED_LIST
			next_exists: next /= void
			item_inserted: not old before implies next.item = v
			item_inserted_before: old before implies active.item = v
		end
	
feature -- Removal

	prune (v: like item) is
			-- Remove first occurrence of v, if any,
			-- after cursor position.
			-- If found, move cursor to right neighbor;
			-- if not, make structure exhausted.
			-- (from DYNAMIC_CHAIN)
		require -- from COLLECTION
			prunable: prunable
		do
			search (v)
			if not exhausted then
				remove
			end
		end

	prune_all (v: like item) is
			-- Remove all items identical to v.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- Leave cursor off.
		require -- from COLLECTION
			prunable
		do
			from
				start
				search (v)
			until
				off or else v < item
			loop
				remove
			end
			if not off then
				finish
				forth
			end
		ensure -- from COLLECTION
			no_more_occurrences: not has (v)
		ensure then -- from DYNAMIC_CHAIN
			is_exhausted: exhausted
		end

	remove is
			-- Remove current item.
			-- Move cursor to right neighbor
			-- (or after if no right neighbor).
			-- (from TWO_WAY_LIST)
		require -- from ACTIVE
			prunable: prunable
			writable: writable
		local
			succ, pred, removed: like first_element
		do
			removed := active
			if isfirst then
				active := first_element.right
				first_element.forget_right
				first_element := active
				if count = 1 then
					check
						no_active: active = void
					end
					after := True
					last_element := void
				end
			elseif islast then
				active := last_element.left;
				last_element.forget_left;
				last_element := active;
				after := True
			else
				pred := active.left
				succ := active.right
				pred.forget_right
				succ.forget_left
				pred.put_right (succ)
				active := succ
			end
			count := count - 1
			cleanup_after_remove (removed)
		ensure then -- from DYNAMIC_LIST
			after_when_empty: is_empty implies after
		end

	remove_left is
			-- Remove item to the left of cursor position.
			-- Do not move cursor.
			-- (from TWO_WAY_LIST)
		require -- from DYNAMIC_CHAIN
			left_exists: index > 1
		require else -- from DYNAMIC_LIST
			not_before: not before
		do
			back
			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.
			-- (from TWO_WAY_LIST)
		require -- from DYNAMIC_CHAIN
			right_exists: index < count
		do
			forth
			remove
			back
		ensure -- from DYNAMIC_CHAIN
			new_count: count = old count - 1
			same_index: index = old index
		end

	remove_sublist is
			-- (from TWO_WAY_LIST)
		do
			sublist := void
		end

	split (n: INTEGER) is
			-- Remove from current list
			-- min (n, count - index - 1) items
			-- starting at cursor position.
			-- Move cursor right one position.
			-- Make extracted sublist accessible
			-- through attribute sublist.
			-- (from TWO_WAY_LIST)
		require -- from TWO_WAY_LIST
			not_off: not off
			valid_sublist: n >= 0
		local
			actual_number, active_index: INTEGER
			p_elem, s_elem, e_elem, n_elem: like first_element
		do
			if n = 0 then
				create sublist.make
			else
				active_index := index
				if active_index + n > count + 1 then
					actual_number := count + 1 - active_index
				else
					actual_number := n
				end
				s_elem := active
				p_elem := previous
				move (actual_number - 1)
				e_elem := active
				n_elem := next
				s_elem.forget_left
				e_elem.forget_right
				create sublist.make_sublist (s_elem, e_elem, actual_number)
				count := count - actual_number
				if p_elem /= void then
					p_elem.put_right (n_elem)
				else
					first_element := n_elem
				end
				if n_elem /= void then
					active := n_elem
				else
					last_element := p_elem
					active := p_elem
					after := True
				end
			end
		end

	wipe_out is
			-- Remove all items.
			-- (from TWO_WAY_LIST)
		require -- from COLLECTION
			prunable
		do
			ll_wipe_out
			last_element := void
		ensure -- from COLLECTION
			wiped_out: is_empty
		ensure then -- from DYNAMIC_LIST
			is_before: before
		end
	
feature {NONE} -- Removal

	ll_wipe_out is
			-- Remove all items.
			-- (from LINKED_LIST)
		require -- from COLLECTION
			prunable
		do
			active := void
			first_element := void
			before := True
			after := False
			count := 0
		ensure -- from COLLECTION
			wiped_out: is_empty
		ensure then -- from DYNAMIC_LIST
			is_before: before
		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 -- Transformation

	sort is
			-- sort the list
			-- Has O(count * log (count)) complexity.
		local
			no_change: BOOLEAN
			gap: INTEGER
			left_cell, cell: like first_element
			left_cell_item, cell_item: like item
		do
			if not is_empty then
				from
					gap := count * 10 // 13
				until
					gap = 0
				loop
					from
						no_change := False
						go_i_th (1 + gap)
					until
						no_change
					loop
						no_change := True
						from
							left_cell := first_element
							cell := active
						until
							cell = void
						loop
							left_cell_item := left_cell.item
							cell_item := cell.item
							if cell_item < left_cell_item then
								no_change := False
								cell.put (left_cell_item)
								left_cell.put (cell_item)
							end
							left_cell := left_cell.right
							cell := cell.right
						end
					end
					gap := gap * 10 // 13
				end
			end
		end

	swap (i: INTEGER) is
			-- Exchange item at i-th position with item
			-- at cursor position.
			-- (from CHAIN)
		require -- from CHAIN
			not_off: not off
			valid_index: valid_index (i)
		local
			old_item, new_item: like item
			pos: CURSOR
		do
			pos := cursor
			old_item := item
			go_i_th (i)
			new_item := item
			replace (old_item)
			go_to (pos)
			replace (new_item)
		ensure -- from CHAIN
			swapped_to_item: item = old i_th (i)
			swapped_from_item: i_th (i) = old item
		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
			-- Update current object using fields of object attached
			-- to other, so as to yield equal objects.
			-- (from LINKED_LIST)
		require -- from ANY
			other_not_void: other /= void
			type_identity: same_type (other)
		local
			cur: LINKED_LIST_CURSOR [G]
			new_list: like Current
			obj_comparison: BOOLEAN
		do
			obj_comparison := other.object_comparison
			if not other.is_empty then
				cur ?= other.cursor
				create new_list.make
				from
					other.start
				until
					other.off
				loop
					new_list.extend (other.item)
					other.forth
				end
				other.go_to (cur)
			else
				new_list := other
			end
			standard_copy (new_list)
			object_comparison := obj_comparison
		ensure -- from ANY
			is_equal: is_equal (other)
		end

	duplicate (n: INTEGER): like Current is
			-- Copy of sub-chain beginning at current position
			-- and having min (n, from_here) items,
			-- where from_here is the number of items
			-- at or to the right of current position.
			-- (from DYNAMIC_CHAIN)
		require -- from CHAIN
			not_off_unless_after: off implies after
			valid_subchain: n >= 0
		local
			pos: CURSOR
			counter: INTEGER
		do
			from
				Result := new_chain
				if object_comparison then
					Result.compare_objects
				end
				pos := cursor
			until
				(counter = n) or else exhausted
			loop
				Result.extend (item)
				forth
				counter := counter + 1
			end
			go_to (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
	
feature {PART_SORTED_TWO_WAY_LIST} -- Implementation

	new_chain: like Current is
			-- A newly created instance of the same type.
			-- This feature may be redefined in descendants so as to
			-- produce an adequately allocated and initialized object.
		do
			create Result.make
		ensure -- from DYNAMIC_CHAIN
			result_exists: Result /= void
		end
	
feature {TWO_WAY_LIST} -- Implementation

	make_sublist (first_item, last_item: like first_element; n: INTEGER) is
			-- Create sublist
			-- (from TWO_WAY_LIST)
		do
			make
			first_element := first_item
			last_element := last_item
			active := first_element
			count := n
		end

	new_cell (v: like item): like first_element is
			-- A newly created instance of the type of first_element.
			-- (from TWO_WAY_LIST)
		do
			create Result
			Result.put (v)
		ensure -- from LINKED_LIST
			result_exists: Result /= void
		end

	previous: like first_element is
			-- Element left of cursor
			-- (from TWO_WAY_LIST)
		do
			if after then
				Result := active
			elseif active /= void then
				Result := active.left
			end
		end
	
feature {LINKED_LIST} -- Implementation

	active: like first_element
			-- Element at cursor position
			-- (from LINKED_LIST)

	cleanup_after_remove (v: like first_element) is
			-- Clean-up a just removed cell.
			-- (from LINKED_LIST)
		require -- from LINKED_LIST
			non_void_cell: v /= void
		do
		end

	next: like first_element is
			-- Element right of cursor
			-- (from LINKED_LIST)
		do
			if before then
				Result := active
			elseif active /= void then
				Result := active.right
			end
		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

		-- from ANY
	reflexive_equality: standard_is_equal (Current)
	reflexive_conformance: conforms_to (Current)
		-- from TWO_WAY_LIST
	non_empty_list_has_two_endpoints: not is_empty implies (first_element /= void and last_element /= void)
	first_element_constraint: first_element /= void implies first_element.left = void
	last_element_constraint: last_element /= void implies last_element.right = void
		-- from LINKED_LIST
	prunable: prunable
	empty_constraint: is_empty implies ((first_element = void) and (active = void))
	not_void_unless_empty: (active = void) implies is_empty
	before_constraint: before implies (active = first_element)
	after_constraint: after implies (active = last_element)
		-- 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 INDEXABLE
	index_set_not_void: index_set /= void
		-- 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 FINITE
	empty_definition: is_empty = (count = 0)
	non_negative_count: count >= 0
		-- 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 PART_SORTED_TWO_WAY_LIST


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

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