note
	description: "Item of a 2-3-4 tree"
	legal: "See notice at end of class."
	status: "See notice at end of class."
	author: "Christophe Bonnard"
	date: "$Date$"
	revision: "$Revision$"

deferred class
	TREE_ITEM

inherit
	ANY

feature -- Access

	tree: detachable B_345_TREE

	key: detachable TREE_KEY [like Current]
		-- Tree Key of Current

	next: detachable like Current
		-- next item
		-- Void if Current is the last item.

	previous: detachable like Current
		-- previous item
		-- Void if Current is the last item.

	index: INTEGER
			-- index of item in tree
		require
			is_valid: is_valid
		local
			l_key: like key
		do
			l_key := key
			check l_key /= Void end -- Implied by precondition
			Result := l_key.number
		end

feature -- Status report

	is_valid: BOOLEAN
			-- Is current item valid in the tree?
		do
			Result := tree /= Void and then
					(attached key as l_key and then
					l_key.is_valid)
		end

feature -- Element change

	set_key (k: detachable like key)
			-- Make `k' the value of `key'.
		do
			key := k
		end

	set_tree (t: detachable like tree)
			-- Make `t' the value of `tree'.
		do
			tree := t
		end

	set_next (ti: detachable like Current)
			-- Make `ti' the next item.
		do
			next := ti
		end

	set_previous (ti: detachable like Current)
			-- Make `ti' the previous item.
		do
			previous := ti
		end

feature -- Removal

	delete
			-- Supress Current.
			-- If Current is the only line of `tree', prompt `tree' so.
		require
			key_not_void: key /= Void
		local
			l_key: like key
		do
			l_key := key
			check l_key /= Void end -- Implied by precondition
			l_key.delete
			unlink
		end

	unlink
			-- link `previous' to `next'. used in deletion.
		require
			tree_not_void: tree /= Void
		local
			l_tree: like tree
			l_next: like next
			l_previous: like previous
		do
			l_next := next
			l_previous := previous
			if l_next /= Void then
				l_next.set_previous (l_previous)
			end
			if l_previous /= Void then
				l_previous.set_next (l_next)
			end
			l_tree := tree
			check l_tree /= Void end -- Implied by precondition
			if Current = l_tree.last_data then
				if Current = l_tree.first_data then
					l_tree.wipe_out
				else
					l_tree.set_last_data (l_previous)
				end
			else
				if Current = l_tree.first_data then
					l_tree.set_first_data (l_next)
				end
			end
		end

feature -- Basic Operations

	add_right (other: like Current)
			-- add `other' to the right of Current
		require
			other_not_void: other /= Void
			key_not_void: key /= Void
		local
			ti, l_key: like key
		do
			other.set_tree (tree)
			link_right (other)
			create ti.make (other)
			other.set_key (ti)
			l_key := key
			check l_key_not_void: l_key /= Void end -- Implied by precondition
			l_key.add_right (ti)
		ensure
			other_has_key: other.key /= Void
			other_has_tree: other.tree /= void
		end

	add_left (other: like Current)
			-- add `other' to the left of Current
		require
			other_not_void: other /= Void
			key_not_void: key /= Void
		local
			ti, l_key: like key
		do
			other.set_tree (tree)
			link_left (other)
			create ti.make (other)
			other.set_key (ti)
			l_key := key
			check l_key_not_void: l_key /= Void end -- Implied by precondition
			l_key.add_left (ti)
		ensure
			other_has_key: other.key /= Void
			other_has_tree: other.tree /= void
		end

	link_right (other: like Current)
			-- Add `other' to the right of current.
			-- Change links
		require
			tree_set: tree /= Void
		local
			l_next: like next
			l_tree: like tree
		do
			other.set_next (next)
			other.set_previous (Current)
			l_next := next
			if l_next /= Void then
				l_next.set_previous (other)
			end
				-- Being last tree data is not the same as having no following data.
			l_tree := tree
			check l_tree /= Void end -- Implied by precondition
			if Current = l_tree.last_data then
				l_tree.set_last_data (other)
			end
			set_next (other)
				--| `set_next' is last to not interfere
				--| with "if next /= Void ..." instruction
		end

	link_left (other: like Current)
			-- Add `other' to the left of current.
			-- Change links
		require
			tree_set: tree /= Void
		local
			l_pre: like previous
			l_tree: like tree
		do
			other.set_previous (previous)
			other.set_next (Current)
			l_pre := previous
			if l_pre /= Void then
				l_pre.set_next (other)
			end
				-- Being first tree data is not the same as having no previous data.
			l_tree := tree
			check l_tree /= Void end -- Implied by precondition
			if Current = l_tree.first_data then
				l_tree.set_first_data (other)
			end
			set_previous (other)
				--| `set_previous' is last to not interfere
				--| with "if previous /= Void ..." instruction
		end

note
	copyright:	"Copyright (c) 1984-2006, Eiffel Software and others"
	license:	"Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)"
	source: "[
			 Eiffel Software
			 356 Storke Road, 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 TREE_ITEM