note
	description: "Trees with a dynamically modifiable structure"
	library: "Free implementation of ELKS library"
	legal: "See notice at end of class."
	status: "See notice at end of class."
	names: dynamic_tree, tree
	representation: recursive
	access: cursor, membership
	contents: generic
	date: "$Date: 2018-11-14 15:15:17 +0000 (Wed, 14 Nov 2018) $"
	revision: "$Revision: 102463 $"

deferred class interface
	DYNAMIC_TREE [G]

feature -- Access

	parent: detachable DYNAMIC_TREE [G]
			-- Parent of current node.
	
feature -- Status report

	Extendible: BOOLEAN = True
			-- May new items be added?
	
feature -- Element change

	extend (v: like item)
			-- Add v as new child.

	child_extend (v: like item)
			-- Add v to the list of children.
			-- Do not move child cursor.

	child_put_left (v: like item)
			-- Add v to the left of cursor position.
			-- Do not move child cursor.
		require
			not_child_before: not child_before

	child_put_right (v: like item)
			-- Add v to the right of cursor position.
			-- Do not move child cursor.
		require
			not_child_after: not child_after

	put_child_left (n: like parent)
			-- Add n to the left of cursor position.
			-- Do not move cursor.
		require
			not_child_before: not child_before
			non_void_argument: n /= Void

	put_child_right (n: like parent)
			-- Add n to the right of cursor position.
			-- Do not move cursor.
		require
			not_child_after: not child_after
			non_void_argument: n /= Void

	merge_tree_before (other: attached like first_child)
			-- Merge children of other into current structure
			-- after cursor position. Do not move cursor.
			-- Make other a leaf.
		require
			not_child_off: not child_off
			other_exists: other /= Void
		ensure
			other_is_leaf: other.is_leaf

	merge_tree_after (other: attached like first_child)
			-- Merge children of other into current structure
			-- after cursor position. Do not move cursor.
			-- Make other a leaf.
		require
			not_child_off: not child_off
			other_exists: other /= Void
		ensure
			other_is_leaf: other.is_leaf
	
feature -- Removal

	remove_left_child
			-- Remove item to the left of cursor position.
			-- Do not move cursor.
		require
			is_not_first: not child_isfirst
		ensure
			new_arity: arity = old arity - 1
			new_child_index: child_index = old child_index - 1

	remove_right_child
			-- Remove item to the right of cursor position.
			-- Do not move cursor.
		require
			is_not_last: not child_islast
		ensure
			new_arity: arity = old arity - 1
			new_child_index: child_index = old child_index

	remove_child
			-- Remove child at cursor position.
			-- Move cursor to next sibling, or after if none.
		require
			child_not_off: not child_off
		ensure
			new_arity: arity = old arity - 1
			new_child_index: child_index = old child_index
	
feature -- Conversion

	fill_from_binary (b: BINARY_TREE [G])
			-- Fill from a binary tree representation.
			-- Left child becomes first child.
			-- Right child becomes right sibling.
			-- Any right child of b is ignored.
	
invariant
	extendible_definition: Extendible
	child_after_definition: child_after = (child_index = arity + 1)

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 DYNAMIC_TREE

Generated by ISE EiffelStudio