indexing
	description: "Structures that may be traversed forward"
	library: "Gobo Eiffel Structure Library"
	author: "Eric Bezault <ericb@gobo.demon.co.uk>"
	copyright: "Copyright (c) 1997, Eric Bezault"

deferred class interface
	DS_LINEAR [G]

feature -- Access

	first: G
			-- First item in structure
		require
			not_empty: not is_empty
		ensure
			has_first: has (Result)

	new_cursor: DS_LINEAR_CURSOR [G]
			-- New cursor for traversal
		ensure -- from DS_TRAVERSABLE
			cursor_not_void: Result /= void;
			valid_cursor: valid_cursor (Result)

	searcher: DS_LINEAR_SEARCHER [G]
			-- Structure searcher
	
feature -- Measurement

	count: INTEGER
			-- Number of items in structure
			-- (from DS_CONTAINER)

	occurrences (v: G): INTEGER
			-- Number of times v appears in structure
			-- (Use searcher's comparison criterion.)
			-- (from DS_SEARCHABLE)
		ensure -- from DS_SEARCHABLE
			positive: Result >= 0;
			has: has (v) implies Result >= 1
	
feature -- Comparison

	is_equal (other: like Current): BOOLEAN
			-- Is current structure equal to other?
			-- (from DS_CONTAINER)
		require -- from GENERAL
			other_not_void: other /= void
		ensure -- from GENERAL
			symmetric: Result implies other.is_equal (Current);
			consistent: standard_is_equal (other) implies Result
		ensure then -- from DS_CONTAINER
			same_count: Result implies count = other.count
		ensure then -- from DS_CONTAINER
			same_count: Result implies count = other.count
	
feature -- Status report

	has (v: G): BOOLEAN
			-- Does structure incluse v?
			-- (Use searcher's comparison criterion.)
			-- (from DS_SEARCHABLE)
		ensure -- from DS_SEARCHABLE
			not_empty: Result implies not is_empty

	is_empty: BOOLEAN
			-- Is structure empty?
			-- (from DS_CONTAINER)

	valid_cursor (a_cursor: like new_cursor): BOOLEAN
			-- Is a_cursor a valid cursor?
			-- (A cursor might become invalid if structure
			-- has been modified during traversal.)
			-- (from DS_TRAVERSABLE)
		require -- from DS_TRAVERSABLE
			a_cursor_not_void: a_cursor /= void
		ensure -- from DS_TRAVERSABLE
			is_valid: Result implies a_cursor.is_valid
	
feature -- Removal

	wipe_out
			-- Remove all items from structure.
			-- (from DS_CONTAINER)
		ensure -- from DS_CONTAINER
			wipe_out: is_empty
		ensure -- from DS_CONTAINER
			wipe_out: is_empty
	
feature -- Setting

	set_searcher (a_searcher: like searcher)
			-- Set searcher to a_searcher.
			-- (from DS_SEARCHABLE)
		require -- from DS_SEARCHABLE
			a_searcher_not_void: a_searcher /= void
		ensure -- from DS_SEARCHABLE
			searcher_set: searcher = a_searcher
	
invariant

		-- from GENERAL
	reflexive_equality: standard_is_equal (Current);
	reflexive_conformance: conforms_to (Current);
		-- from DS_CONTAINER
	positive_count: count >= 0;
	empty_definition: is_empty = (count = 0);
		-- from DS_SEARCHABLE
	searcher_not_void: searcher /= void;

end -- class DS_LINEAR