note description: "Trees as active structures that may be traversed using a cursor" library: "Free implementation of ELKS library" legal: "See notice at end of class." status: "See notice at end of class." names: cursor_tree, tree access: cursor, membership contents: generic date: "$Date: 2017-03-23 19:18:26 +0000 (Thu, 23 Mar 2017) $" revision: "$Revision: 100033 $" deferred class interface CURSOR_TREE [G] feature -- Access parent_item: G -- Item in parent. require not_on_root: not is_root child_item (i: INTEGER_32): G -- Item in i-th child require argument_within_bounds: i >= 1 and then i <= arity not_off: not off has (v: G): BOOLEAN -- Does structure include an occurrence of v? -- (Reference or object equality, -- based on object_comparison.) occurrences (v: G): INTEGER_32 -- Number of times v appears in structure -- (Reference or object equality, -- based on object_comparison.) feature -- Measurement depth: INTEGER_32 -- Depth of the tree level: INTEGER_32 -- Level of current node in tree -- (Root is on level 1) breadth: INTEGER_32 -- Breadth of current level feature -- Status report readable: BOOLEAN -- Is there a current item that may be read? writable: BOOLEAN -- Is there a current item that may be modified? extendible: BOOLEAN -- May new items be added? is_leaf: BOOLEAN -- Is cursor on a leaf? off: BOOLEAN -- Is there no current item? -- (True if is_empty) 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? above: BOOLEAN -- Is there no valid cursor position above cursor? below: BOOLEAN -- Is there no valid cursor position below cursor? isfirst: BOOLEAN -- Is cursor on first sibling? islast: BOOLEAN -- Is cursor on last sibling? is_root: BOOLEAN -- Is cursor on root? valid_cursor_index (i: INTEGER_32): BOOLEAN -- Can cursor be moved to i-th child? -- 0 is before and arity + 1 is after. feature -- Cursor movement start -- Move cursor to root. -- Leave cursor off if is_empty. ensure then on_root_unless_empty: not is_empty implies is_root go_last_child -- Go to the last child of current parent. -- No effect if below require else not_above: not above back -- Move cursor one position backward. forth -- Move cursor one position forward. up -- Move cursor one level upward to parent, -- or above if is_root holds. require else not_above: not above ensure then not_before: not before not_after: not after not_below: not below coherency: (not old off and above) = (old is_root) down (i: INTEGER_32) -- Move cursor one level downward: -- to i-th child if there is one, -- or after if i = arity + 1, -- or before if i = 0. require else not_before: not before not_after: not after not_below: not below valid_cursor_index: (above and i = 0) or else valid_cursor_index (i) ensure then gone_before: (i = 0) implies before preorder_forth -- Move cursor to next position in preorder. -- If the active node is the last in -- preorder, the cursor ends up off. postorder_forth -- Move cursor to next position in postorder. -- If the active node is the last in -- postorder, the cursor ends up off. require not_off: not off breadth_forth -- Move cursor to next position in breadth-first order. -- If the active node is the last in -- breadth-first order, the cursor ends up off. require not_off: not off start_on_level (l: INTEGER_32) -- Move the cursor to the first position -- of the l-th level counting from root. require argument_within_bounds: l >= 1 and then depth >= l ensure level_expected: level = l is_first: isfirst level_forth -- Move cursor to next position of current level. level_back -- Move cursor to previous position of current level. postorder_start -- Move cursor to first position in postorder. -- Leave cursor off if tree is empty. feature -- Element change put (v: G) -- Put v at cursor position. -- (Synonym for replace) extend (v: G) -- Add v after last child. -- Make v the first_child if below and place -- cursor before. put_left (v: G) -- Add v to the left of cursor position. require not_before: not before not_above: not above only_one_root: (level = 1) implies is_empty put_right (v: G) -- Add v to the right of cursor position. require not_after: not after not_above: not above only_one_root: (level = 1) implies is_empty fill (other: CURSOR_TREE [G]) -- Fill with as many items of other -- as possible. -- The representations of other and current structure -- need not be the same. require is_empty: is_empty fill_from_active (other: CURSOR_TREE [G]) -- Copy subtree of other's active node -- onto active node of current tree. require cursor_on_leaf: is_leaf merge_right (other: CURSOR_TREE [G]) -- Merge the items of other into current structure to -- the right of cursor position. require other_exists: other /= Void not_after: not after not_above: not above only_one_root: (level = 1) implies is_empty merge_left (other: CURSOR_TREE [G]) -- Merge the items of other into current structure to -- the left of cursor position. require other_exists: other /= Void not_before: not before not_above: not above only_one_root: (level = 1) implies is_empty feature -- Duplication subtree: like Current -- Subtree rooted at current node require not_off: not off parent_tree: like Current -- Subtree rooted at parent require not_on_root: not is_root not_off: not off child_tree (i: INTEGER_32): like Current -- Subtree rooted at i-th child require argument_within_bounds: i >= 1 and then i <= arity not_off: not off feature -- Inapplicable prune (v: G) -- Remove item v. feature -- Not applicable index: INTEGER_32 -- Index of current position invariant non_negative_depth: depth >= 0 non_negative_breadth: breadth >= 0 is_leaf_definition: not off implies is_leaf = (arity = 0) above_property: above implies (arity <= 1) on_tree: (isfirst or islast or is_leaf or is_root) implies not off off_definition: off = after or before or above or below below_constraint: below implies ((after or before) and not above) above_constraint: above implies not (before or after or below) after_constraint: after implies not (before or above) before_constaint: before implies not (after or above) empty_below_constraint: (is_empty and (after or before)) implies below note copyright: "Copyright (c) 1984-2017, 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 CURSOR_TREE
Generated by ISE EiffelStudio