note description: "3-4-5 Balanced Tree" legal: "See notice at end of class." status: "See notice at end of class." author: "Christophe Bonnard" date: "$Date$" revision: "$Revision$" class B_345_TREE inherit ANY create make feature -- Initialization make do create root_node.make end feature -- Access count: INTEGER do Result := root_node.keys_plus_one - 1 end first_data: detachable TREE_ITEM last_data: detachable like first_data item (i: INTEGER): like first_data require i_is_valid: i >= 1 and i <= count do Result := root_node.item (i).data end feature -- Element Change set_first_data (tl: like first_data) do first_data := tl end set_last_data (tl: like first_data) do last_data := tl end prepend_data (tl: attached like first_data) -- add tl at the beginning of the tree. require tl_not_linked: tl.next = Void and then tl.previous = Void local ti: TREE_KEY [attached like first_data] l_key: detachable TREE_KEY [attached like first_data] l_first_data: like first_data do tl.set_tree (Current) create ti.make (tl) tl.set_key (ti) l_first_data := first_data if l_first_data = Void then set_last_data (tl) root_node.insert_first (ti) else tl.set_next (first_data) l_first_data.set_previous (tl) l_key := l_first_data.key check l_key /= Void end -- Implied by the invariant. l_key.add_left (ti) end set_first_data (tl) ensure tl_linked: tl /= last_data implies (attached tl.next as l_next and then l_next.previous = tl) tl_has_key: tl.key /= Void tl_has_tree: tl.tree /= Void end append_data (tl: attached like first_data) -- add tl at the end of the tree. require tl_not_linked: tl.next = Void and then tl.previous = Void local ti: TREE_KEY [attached like first_data] l_key: detachable TREE_KEY [attached like first_data] l_last_data: like last_data do tl.set_tree (Current) create ti.make (tl) tl.set_key (ti) l_last_data := last_data if l_last_data = Void then set_first_data (tl) root_node.insert_last (ti) else tl.set_previous (l_last_data) l_last_data.set_next (tl) l_key := l_last_data.key check l_key /= Void end -- Implied by the invariant. l_key.add_right (ti) end set_last_data (tl) ensure tl_linked: tl /= first_data implies (attached tl.previous as l_previous and then l_previous.next = tl) tl_has_key: tl.key /= Void tl_has_tree: tl.tree /= Void end feature -- Removal wipe_out -- Erase data. local l_default: like first_data do set_first_data (l_default) set_last_data (l_default) create root_node.make end feature {NONE} -- Implementation root_node: TREE_NODE [attached like first_data]; invariant first_data_valid: attached first_data as l_first_data implies l_first_data.is_valid last_data_valid: attached last_data as l_last_data implies l_last_data.is_valid note copyright: "Copyright (c) 1984-2016, 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 -- B_345_TREE