note
	description: "Binary tree: each node may have a left child and a right child"
	library: "Free implementation of ELKS library"
	legal: "See notice at end of class."
	status: "See notice at end of class."
	names: binary_tree, tree, fixed_tree
	representation: recursive, array
	access: cursor, membership
	contents: generic
	date: "$Date: 2018-12-15 18:06:16 +0000 (Sat, 15 Dec 2018) $"
	revision: "$Revision: 102608 $"

class interface
	BINARY_TREE [G]

create 
	make

feature -- Access

	parent: detachable like Current
			-- Parent of current node

	child_index: INTEGER_32
			-- Index of cursor position

	left_child: like parent
			-- Left child, if any

	right_child: like parent
			-- Right child, if any

	left_item: like item
			-- Value of left child
		require
			has_left: left_child /= Void

	right_item: like item
			-- Value of right child
		require
			has_right: right_child /= Void

	first_child: like parent
			-- Left child

	last_child: like parent
			-- Right child

	child: like parent
			-- Child at cursor position

	child_cursor: ARRAYED_LIST_CURSOR
			-- Current cursor position

	left_sibling: like parent
			-- Left neighbor, if any

	right_sibling: like parent
			-- Right neighbor, if any
	
feature -- Measurement

	arity: INTEGER_32
			-- Number of children
		ensure then
			valid_arity: Result <= Child_capacity

	Child_capacity: INTEGER_32 = 2
			-- Maximum number of children
	
feature -- Status report

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

	is_leaf: BOOLEAN
			-- Are there no children?
			-- Was declared in BINARY_TREE as synonym of has_none.

	has_none: BOOLEAN
			-- Are there no children?
			-- Was declared in BINARY_TREE as synonym of is_leaf.

	has_left: BOOLEAN
			-- Has current node a left child?
		ensure
				Result = (left_child /= Void)

	has_right: BOOLEAN
			-- Has current node a right child?
		ensure
				Result = (right_child /= Void)

	has_both: BOOLEAN
			-- Has current node two children?
		ensure
				Result = (has_left and has_right)
	
feature -- Cursor movement

	child_go_to (p: ARRAYED_LIST_CURSOR)
			-- Move cursor to child remembered by p.

	child_start
			-- Move to first child.

	child_finish
			-- Move cursor to last child.

	child_forth
			-- Move cursor to next child.

	child_back
			-- Move cursor to previous child.

	child_go_i_th (i: INTEGER_32)
			-- Move cursor to i-th child.
	
feature -- Element change

	put_left_child (n: like parent)
			-- Set left_child to n.
		require
			no_parent: n = Void or else n.is_root

	put_right_child (n: like parent)
			-- Set right_child to n.
		require
			no_parent: n = Void or else n.is_root

	child_put (v: like item)
			-- Put v at current child position.
			-- Was declared in BINARY_TREE as synonym of child_replace.

	child_replace (v: like item)
			-- Put v at current child position.
			-- Was declared in BINARY_TREE as synonym of child_put.

	put_child (n: like new_tree)
			-- Put n at current child position.
			-- Was declared in BINARY_TREE as synonym of replace_child.

	replace_child (n: like new_tree)
			-- Put n at current child position.
			-- Was declared in BINARY_TREE as synonym of put_child.
	
feature -- Removal

	remove_left_child
			-- Remove left child.
		ensure
				not has_left

	remove_right_child
			-- Remove right child.
		ensure
				not has_right

	child_remove
			-- Remove current child.

	prune (n: like new_tree)
			-- Prune n from child nodes.

	wipe_out
			-- Remove all children.

	forget_left
			-- Forget left sibling.

	forget_right
			-- Forget right sibling.
	
invariant
	tree_is_binary: Child_capacity = 2

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 BINARY_TREE

Generated by ISE EiffelStudio