note description: "Data structures that may be traversed forward" library: "Gobo Eiffel Structure Library" copyright: "Copyright (c) 1999-2007, Eric Bezault and others" license: "MIT License" date: "$Date$" revision: "$Revision$" deferred class DS_LINEAR [G] inherit DS_TRAVERSABLE [G] redefine new_cursor, do_all, do_if end DS_SEARCHABLE [G] feature -- Access first: G -- First item in container require not_empty: not is_empty deferred ensure has_first: has (Result) end new_cursor: DS_LINEAR_CURSOR [G] -- New external cursor for traversal deferred end feature -- Status report is_first: BOOLEAN -- Is internal cursor on first item? do Result := cursor_is_first (internal_cursor) ensure not_empty: Result implies not is_empty not_off: Result implies not off definition: Result implies (item_for_iteration = first) end after: BOOLEAN -- Is there no valid position to right of internal cursor? do Result := cursor_after (internal_cursor) end has (v: G): BOOLEAN -- Does container include `v'? -- (Use `equality_tester''s comparison criterion -- if not void, use `=' criterion otherwise.) local a_cursor: like new_cursor do a_cursor := new_cursor a_cursor.start a_cursor.search_forth (v) if not a_cursor.after then Result := True a_cursor.go_after end end feature -- Measurement occurrences (v: G): INTEGER -- Number of times `v' appears in container -- (Use `equality_tester''s comparison criterion -- if not void, use `=' criterion otherwise.) local a_cursor: like new_cursor do a_cursor := new_cursor from a_cursor.start until a_cursor.after loop a_cursor.search_forth (v) if not a_cursor.after then Result := Result + 1 a_cursor.forth end end end feature -- Cursor movement start -- Move internal cursor to first position. do cursor_start (internal_cursor) ensure empty_behavior: is_empty implies after not_empty_behavior: not is_empty implies is_first end forth -- Move internal cursor to next position. require not_after: not after do cursor_forth (internal_cursor) end search_forth (v: G) -- Move internal cursor to first position at or after current -- position where `item_for_iteration' and `v' are equal. -- (Use `equality_tester''s comparison criterion -- if not void, use `=' criterion otherwise.) -- Move `after' if not found. require not_off: not off or after do cursor_search_forth (internal_cursor, v) end go_after -- Move internal cursor to `after' position. do cursor_go_after (internal_cursor) ensure after: after end feature -- Iteration do_all (an_action: PROCEDURE [ANY, TUPLE [G]]) -- Apply `an_action' to every item, from first to last. -- (Semantics not guaranteed if `an_action' changes the structure.) deferred end do_all_with_index (an_action: PROCEDURE [ANY, TUPLE [G, INTEGER]]) -- Apply `an_action' to every item, from first to last. -- `an_action' receives the item and its index. -- (Semantics not guaranteed if `an_action' changes the structure.) require an_action_not_void: an_action /= Void deferred end do_if (an_action: PROCEDURE [ANY, TUPLE [G]]; a_test: FUNCTION [ANY, TUPLE [G], BOOLEAN]) -- Apply `an_action' to every item that satisfies `a_test', from first to last. -- (Semantics not guaranteed if `an_action' or `a_test' change the structure.) deferred end do_if_with_index (an_action: PROCEDURE [ANY, TUPLE [G, INTEGER]]; a_test: FUNCTION [ANY, TUPLE [G, INTEGER], BOOLEAN]) -- Apply `an_action' to every item that satisfies `a_test', from first to last. -- `an_action' and `a_test' receive the item and its index. -- (Semantics not guaranteed if `an_action' or `a_test' change the structure.) require an_action_not_void: an_action /= Void a_test_not_void: a_test /= Void deferred end feature -- Duplication to_array: ARRAY [G] -- Array containing the same items as current -- container in the same order local a_cursor: like new_cursor i: INTEGER l_default: G do create Result.make_filled (l_default, 1, count) a_cursor := new_cursor from a_cursor.start until a_cursor.after loop i := i + 1 Result.put (a_cursor.item, i) a_cursor.forth end ensure to_array_not_void: Result /= Void same_count: Result.count = count end feature {DS_CURSOR} -- Cursor implementation cursor_off (a_cursor: like new_cursor): BOOLEAN -- Is there no item at `a_cursor' position? do Result := cursor_after (a_cursor) end feature {DS_LINEAR_CURSOR} -- Cursor implementation cursor_is_first (a_cursor: like new_cursor): BOOLEAN -- Is `a_cursor' on first item? require a_cursor_not_void: a_cursor /= Void a_cursor_valid: valid_cursor (a_cursor) deferred ensure not_empty: Result implies not is_empty a_cursor_not_off: Result implies not cursor_off (a_cursor) definition: Result implies (cursor_item (a_cursor) = first) end cursor_after (a_cursor: like new_cursor): BOOLEAN -- Is there no valid position to right of `a_cursor'? require a_cursor_not_void: a_cursor /= Void a_cursor_valid: valid_cursor (a_cursor) deferred end cursor_start (a_cursor: like new_cursor) -- Move `a_cursor' to first position. require a_cursor_not_void: a_cursor /= Void a_cursor_valid: valid_cursor (a_cursor) deferred ensure empty_behavior: is_empty implies cursor_after (a_cursor) not_empty_behavior: not is_empty implies cursor_is_first (a_cursor) end cursor_forth (a_cursor: like new_cursor) -- Move `a_cursor' to next position. require a_cursor_not_void: a_cursor /= Void a_cursor_valid: valid_cursor (a_cursor) a_cursor_not_after: not cursor_after (a_cursor) deferred end cursor_search_forth (a_cursor: like new_cursor; v: G) -- Move `a_cursor' to first position at or after its current -- position where `cursor_item (a_cursor)' and `v' are equal. -- (Use `equality_tester''s comparison criterion -- if not void, use `=' criterion otherwise.) -- Move `after' if not found. require a_cursor_not_void: a_cursor /= Void a_cursor_valid: valid_cursor (a_cursor) a_cursor_not_off: not cursor_off (a_cursor) or cursor_after (a_cursor) deferred end cursor_go_after (a_cursor: like new_cursor) -- Move `a_cursor' to `after' position. require a_cursor_not_void: a_cursor /= Void a_cursor_valid: valid_cursor (a_cursor) deferred ensure a_cursor_after: cursor_after (a_cursor) end invariant after_constraint: initialized implies (after implies off) end