note
	description: "Sequential, one-way linked lists"
	library: "Free implementation of ELKS library"
	legal: "See notice at end of class."
	status: "See notice at end of class."
	names: linked_list, sequence
	representation: linked
	access: index, cursor, membership
	contents: generic
	date: "$Date: 2018-11-14 15:15:17 +0000 (Wed, 14 Nov 2018) $"
	revision: "$Revision: 102463 $"

class 
	LINKED_LIST [G]

inherit
	DYNAMIC_LIST [G]
		redefine
			go_i_th,
			put_left,
			move,
			wipe_out,
			isfirst,
			islast,
			is_inserted,
			first,
			last,
			finish,
			merge_left,
			merge_right,
			readable,
			start,
			before,
			after,
			off,
			copy,
			new_cursor
		end

create 
	make,
	make_from_iterable

feature {NONE} -- Initialization

	make
			-- Create an empty list.
		do
			before := True
		ensure
			is_before: before
		end

	make_from_iterable (other: ITERABLE [G])
			-- Create a linked list with all items obtained from other.
		do
			make
			across
				other as o
			loop
				extend (o.item)
			end
		end
	
feature -- Access

	item: G
			-- Current item
		do
			check
					attached active as a
			then
				Result := a.item
			end
		end

	first: like item
			-- Item at first position
		do
			check
					attached first_element as f
			then
				Result := f.item
			end
		end

	last: like item
			-- Item at last position
		do
			check
					attached last_element as l
			then
				Result := l.item
			end
		end

	index: INTEGER_32
			-- Index of current position
		local
			l_active, l_active_iterator: like active
		do
			if after then
				Result := count + 1
			elseif not before then
				from
					Result := 1
					l_active := active
					l_active_iterator := first_element
				until
					l_active_iterator = l_active or else l_active_iterator = Void
				loop
					l_active_iterator := l_active_iterator.right
					Result := Result + 1
				end
			end
		end

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

	new_cursor: LINKED_LIST_ITERATION_CURSOR [G]
			-- Fresh cursor associated with current structure
		do
			create Result.make (Current)
			Result.start
		end
	
feature {LINKED_LIST, LINKED_LIST_ITERATION_CURSOR} -- Access

	first_element: detachable like new_cell
			-- Head of list
	
feature -- Measurement

	count: INTEGER_32
			-- Number of items
	
feature -- Status report

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

	after: BOOLEAN
			-- Is there no valid cursor position to the right of cursor?

	before: BOOLEAN
			-- Is there no valid cursor position to the left of cursor?

	off: BOOLEAN
			-- Is there no current item?
		do
			Result := after or before
		end

	isfirst: BOOLEAN
			-- Is cursor at first position?
		do
			Result := not after and not before and (active = first_element)
		end

	islast: BOOLEAN
			-- Is cursor at last position?
		local
			a: like active
		do
			if not after and then not before then
				a := active
				Result := a /= Void and then a.right = Void
			end
		end

	valid_cursor (p: CURSOR): BOOLEAN
			-- Can the cursor be moved to position p?
		local
			temp, sought: like first_element
		do
			if attached {like cursor} p as ll_c 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

	Full: BOOLEAN = False
			-- Is structured filled to capacity? (Answer: no.)

	is_inserted (v: G): BOOLEAN
			-- Has v been inserted at the end by the most recent put or
			-- extend?
		local
			l: like last_element
		do
			l := last_element
			if l /= Void then
				check
					put_constraint: (v /= l.item) implies not off
				end
				Result := (v = l.item) or else (v = item)
			end
		end
	
feature -- Cursor movement

	start
			-- Move cursor to first position.
		do
			if first_element /= Void then
				active := first_element
				after := False
			else
				after := True
			end
			before := False
		ensure then
			empty_convention: is_empty implies after
		end

	finish
			-- Move cursor to last position.
			-- (Go before if empty)
		local
			p: detachable like new_cell
		do
			from
				p := active
			until
				p = Void
			loop
				active := p
				p := p.right
			end
			after := False
			before := active = Void
		ensure then
			empty_convention: is_empty implies before
		end

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

	back
			-- Move to previous item.
		do
			if is_empty then
				before := True
				after := False
			elseif after then
				after := False
			elseif isfirst then
				before := True
			else
				active := previous
			end
		end

	move (i: INTEGER_32)
			-- Move cursor i positions. The cursor
			-- may end up off if the offset is too big.
		local
			counter, new_index: INTEGER_32
			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 then
			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

	go_i_th (i: INTEGER_32)
			-- Move cursor to i-th position.
		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
		end

	go_to (p: CURSOR)
			-- Move cursor to position p.
		do
			if attached {like cursor} p as ll_c then
				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
			else
				check
					correct_cursor_type: False
				end
			end
		end
	
feature -- Element change

	put_front (v: like item)
			-- Add v to beginning.
			-- Do not move cursor.
		local
			p: like new_cell
		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
		end

	extend (v: like item)
			-- Add v to end.
			-- Do not move cursor.
		local
			p: like first_element
			l: like last_element
		do
			p := new_cell (v)
			if is_empty then
				first_element := p
				active := p
			else
				l := last_element
				if l /= Void then
					l.put_right (p)
					if after then
						active := p
					end
				end
			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 new_cell
			a: like active
		do
			a := active
			if a = Void then
				put_front (v)
			elseif after then
				back
				put_right (v)
				move (2)
			else
				p := new_cell (a.item)
				p.put_right (a.right)
				a.put (v)
				a.put_right (p)
				active := p
				count := count + 1
			end
		ensure then
			previous_exists: previous /= Void
			item_inserted: attached previous as q and then q.item = v
		end

	put_right (v: like item)
			-- Add v to the right of cursor position.
			-- Do not move cursor.
		local
			p: like new_cell
			a: like active
		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
				a := active
				if a /= Void then
					p.put_right (a.right)
					a.put_right (p)
				end
			end
			count := count + 1
		ensure then
			next_exists: next /= Void
			item_inserted: not old before implies (attached next as n and then n.item = v)
			item_inserted_before: old before implies (attached active as c and then c.item = v)
		end

	replace (v: like item)
			-- Replace current item by v.
		local
			a: like active
		do
			a := active
			if a /= Void then
				a.put (v)
			end
		end

	merge_left (other: like Current)
			-- Merge other into current structure before cursor
			-- position. Do not move cursor. Empty other.
		local
			other_first_element: like first_element
			other_count: INTEGER_32
			p: like first_element
		do
			if attached other.last_element as other_last_element then
				other_first_element := other.first_element
				other_count := other.count
				other.wipe_out
				check
						other_first_element /= Void
				end
				if is_empty then
					first_element := other_first_element
					active := first_element
				elseif isfirst then
					other_last_element.put_right (first_element)
					first_element := other_first_element
				else
					p := previous
					if p /= Void then
						p.put_right (other_first_element)
					end
					other_last_element.put_right (active)
				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.
		local
			other_first_element: like first_element
			other_count: INTEGER_32
			a: like active
		do
			if attached other.last_element as other_last_element then
				other_first_element := other.first_element
				other_count := other.count
				other.wipe_out
				check
						other_first_element /= Void
				end
				a := active
				if a = Void then
					first_element := other_first_element
					active := first_element
				else
					if not islast then
						other_last_element.put_right (a.right)
					end
					a.put_right (other_first_element)
				end
				count := count + other_count
			end
		end
	
feature -- Removal

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

	remove_left
			-- Remove item to the left of cursor position.
			-- Do not move cursor.
		do
			move (-2)
			remove_right
			forth
		end

	remove_right
			-- Remove item to the right of cursor position.
			-- Do not move cursor.
		local
			removed: like first_element
			f: like first_element
			a: like active
			succ: like active
		do
			if before then
				f := first_element
				if f /= Void then
					removed := f
					first_element := f.right
					a := active
					if a /= Void then
						a.forget_right
					end
					active := first_element
				end
			else
				a := active
				if a /= Void then
					succ := a.right
					if succ /= Void then
						removed := succ
						a.put_right (succ.right)
						succ.forget_right
					end
				end
			end
			count := count - 1
			cleanup_after_remove (removed)
		end

	wipe_out
			-- Remove all items.
		do
			internal_wipe_out
		end
	
feature -- Duplication

	copy (other: like Current)
			-- Update current object using fields of object attached
			-- to other, so as to yield equal objects.
		local
			cur: LINKED_LIST_CURSOR [G]
		do
			if other /= Current then
				standard_copy (other)
				if not other.is_empty then
					internal_wipe_out
					cur := other.cursor
					from
						other.start
					until
						other.off
					loop
						extend (other.item)
						finish
						other.forth
					end
					if cur /= Void then
						other.go_to (cur)
					end
				end
			end
		end
	
feature {LINKED_LIST} -- Implementation

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

	new_cell (v: like item): LINKABLE [like item]
			-- A newly created instance of the same type as first_element.
			-- This feature may be redefined in descendants so as to
			-- produce an adequately allocated and initialized object.
		do
			create Result.put (v)
		ensure
			result_exists: Result /= Void
		end

	previous: like first_element
			-- Element left of cursor
		local
			p: like first_element
		do
			if after then
				Result := active
			elseif not (isfirst or before) then
				from
					p := first_element
				until
					p = Void or else p.right = active
				loop
					p := p.right
				end
				Result := p
			end
		end

	next: like first_element
			-- Element right of cursor
		local
			a: like active
		do
			if before then
				Result := active
			else
				a := active
				if a /= Void then
					Result := a.right
				end
			end
		end

	active: like first_element
			-- Element at cursor position

	last_element: like first_element
			-- Tail of list
		local
			p: like first_element
		do
			from
				p := active
			until
				p = Void
			loop
				Result := p
				p := p.right
			end
		end

	cleanup_after_remove (v: like first_element)
			-- Clean-up a just removed cell.
		require
			non_void_cell: v /= Void
		do
		end
	
feature {NONE} -- Implementation

	frozen internal_wipe_out
			-- Remove all items.
		require
				prunable
		do
			active := Void
			first_element := Void
			before := True
			after := False
			count := 0
		ensure
			wiped_out: is_empty
			is_before: before
		end
	
invariant
	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)

note
	copyright: "Copyright (c) 1984-2018, 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 -- class LINKED_LIST

Generated by ISE EiffelStudio