note
	description: "Sequential, two-way linked lists"
	library: "Free implementation of ELKS library"
	legal: "See notice at end of class."
	status: "See notice at end of class."
	names: two_way_list, sequence
	representation: linked
	access: index, cursor, membership
	contents: generic
	date: "$Date$"
	revision: "$Revision$"

class TWO_WAY_LIST [G] inherit

	LINKED_LIST [G]
		redefine
			first_element, last_element,
			extend, put_front, put_left, put_right,
			merge_right, merge_left, new_cell,
			remove, remove_left, remove_right, wipe_out,
			previous, finish, move, islast, new_chain,
			forth, back, cursor, new_cursor
		end

create
	make,
	make_from_iterable

create {TWO_WAY_LIST}
	make_sublist

convert
	make_from_iterable ({ARRAY [G]})

feature -- Access

	first_element: detachable like new_cell
			-- Head of list
			-- (Anchor redefinition)

	last_element: like first_element
			-- Tail of the list

	sublist: detachable like Current
			-- Result produced by last `split'

	cursor: TWO_WAY_LIST_CURSOR [G]
			-- Current cursor position
		do
			create Result.make (active, after, before)
		end

	new_cursor: TWO_WAY_LIST_ITERATION_CURSOR [G]
			-- <Precursor>
		do
			create Result.make (Current)
			Result.start
		end

feature -- Status report

	islast: BOOLEAN
			-- Is cursor at last position?
		do
			Result := (active = last_element)
				and then not after
				and then not before
		end

feature -- Cursor movement

	forth
			-- Move cursor to next position, if any.
		local
			a: like active
		do
			if before then
				before := False
				if is_empty then
					after := True
				end
			else
				a := active
				if a /= Void then
					a := a.right
					if a = Void then
						active := last_element
						after := True
					else
						active := a
					end
				end
			end
		end

	back
			-- Move cursor to previous position, if any.
		local
			a: like active
		do
			if after then
				after := False
				if is_empty then
					before := True
				end
			else
				a := active
				if a /= Void then
					a := a.left
					if a = Void then
						active := first_element
						before := True
					else
						active := a
					end
				end
			end
		end

	finish
			-- Move cursor to last position.
			-- (Go before if empty)
		do
			if not is_empty then
				active := last_element
				after := False
				before := False
			else
				after := False
				before := True
			end
		ensure then
			not_after: not after
		end

	move (i: INTEGER)
			-- Move cursor `i' positions. The cursor
			-- may end up `off' if the offset is to big.
		local
			counter: INTEGER
			p: like first_element
		do
			if i > 0 then
				Precursor (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
		end

feature -- Element change

	put_front (v: like item)
			-- Add `v' to beginning.
			-- Do not move cursor.
		do
			Precursor (v)
			if count = 1 then
				last_element := first_element
			end
		end

	extend (v: like item)
			-- Add `v' to end.
			-- Do not move cursor.
		local
			p: like first_element
		do
			p := new_cell (v)
			if is_empty then
				first_element := p
				active := p
			else
				p.put_left (last_element)
			end
			last_element := p
			if after then
				active := p
			end
			count := count + 1
		end

	put_left (v: like item)
			-- Add `v' to the left of cursor position.
			-- Do not move cursor.
		local
			p: like first_element
			a: like active
		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
				a := active
				if a /= Void then
					p.put_left (a.left)
				end
				p.put_right (active)
			End
			count := count + 1
		end

	put_right (v: like item)
			-- Add `v' to the right of cursor position.
			-- Do not move cursor.
		local
			was_last: BOOLEAN
			a: like active
		do
			was_last := islast
			Precursor (v)
			if count = 1 then
					-- `p' is only element in list
				last_element := active
			elseif was_last then
					-- `p' is last element in list
				a := active
				if a /= Void then
					last_element := a.right
				end
			end
		end

	merge_left (other: like Current)
			-- Merge `other' into current structure before cursor
			-- position. Do not move cursor. Empty `other'.
		local
			other_count: INTEGER
		do
			if not other.is_empty then
				other_count := other.count
				check
					attached other.first_element as other_first_element
					attached other.last_element as other_last_element
				then
					other.wipe_out
					if is_empty then
						last_element := other_last_element
						first_element := other_first_element
						if before then
							active := first_element
						else -- after because of invariant 'empty_property'
							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
					elseif attached active as a then
						other_first_element.put_left (a.left)
						a.put_left (other_last_element)
					end
				end
				count := count + other_count
			end
		end

	merge_right (other: like Current)
			-- Merge `other' into current structure after cursor
			-- position. Do not move cursor. Empty `other'.
		do
			if is_empty or else islast then
				last_element := other.last_element
			end
			Precursor (other)
		end

feature -- Removal

	remove
			-- Remove current item.
			-- Move cursor to right neighbor
			-- (or `after' if no right neighbor).
		local
			succ, pred, removed: like first_element
			a: like active
		do
			removed := active
			if isfirst then
				a := first_element
				if a /= Void then
					active := a.right
					a.forget_right
				end
				first_element := active
				if count = 1 then
					check
						no_active: active = Void
					end
					after := True
					last_element := Void
				end
			elseif islast then
				a := last_element
				if a /= Void then
					active := a.left
					a.forget_left
				end
				last_element := active
				after := True
			else
				a := active
				if a /= Void then
					pred := a.left
					succ := a.right
				end
				if pred /= Void and then succ /= Void then
					pred.forget_right
					succ.forget_left
					pred.put_right (succ)
				end
				active := succ
			end
			count := count - 1
			cleanup_after_remove (removed)
		end

	remove_left
			-- Remove item to the left of cursor position.
			-- Do not move cursor.
		do
			back; remove
		end

	remove_right
			-- Remove item to the right of cursor position.
			-- Do not move cursor.
		do
			forth; remove; back
		end

	wipe_out
			-- Remove all items.
		do
			Precursor
			last_element := Void
		end

	split (n: INTEGER)
			-- 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'.
		require
			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
					--just create new empty sublist
				create sublist.make
			else
					-- recognize first breakpoint
				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
					-- recognize second breakpoint
				move (actual_number - 1)
				e_elem := active
				n_elem := next
					-- make sublist
				if s_elem /= Void then
					s_elem.forget_left
				end
				if e_elem /= Void then
					e_elem.forget_right
				end
				create sublist.make_sublist (s_elem, e_elem, actual_number)
					-- fix `Current'
				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

	remove_sublist
		do
			sublist := Void
		end

feature {TWO_WAY_LIST} -- Implementation

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

	new_chain: like Current
			-- 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.
		obsolete "Use explicit creation instead. See also explanations for `duplicate`. [2018-11-30]"
		do
			create Result.make
		end

	new_cell (v: like item): BI_LINKABLE [G]
			-- A newly created instance of the type of `first_element'.
		do
			create Result.put (v)
		end

	previous: like first_element
			-- Element left of cursor
		local
			a: like active
		do
			if after then
				Result := active
			else
				a := active
				if a /= Void then
					Result := a.left
				end
			end
		end

invariant
	non_empty_list_has_two_endpoints: not is_empty implies
				(first_element /= Void and last_element /= Void)
	empty_list_has_no_endpoints: is_empty implies last_element = Void
	first_element_constraint: attached first_element as f implies
				f.left = Void
	last_element_constraint: attached last_element as l implies
				l.right = Void

note
	copyright: "Copyright (c) 1984-2021, Eiffel Software and others"
	license:   "Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)"
	source: "[
			Eiffel Software
			5949 Hollister Ave., Goleta, CA 93117 USA
			Telephone 805-685-1006, Fax 805-685-6869
			Website http://www.eiffel.com
			Customer support http://support.eiffel.com
		]"

end