-- This is a simple package for generic linked lists.
-- It provides a simple 1-directional iterator facility.
-- Both lists and iterators are accessed by pointers,
--  of respective types listptr and iterptr.
-- The behavior of iterators into lists which are modified
--  is not guaranteed.


generic
  type T is private;             -- the element type

package link is
  type listptr is private;
  type iterptr is private;



-- creates and returns an empty list.  
-- no iterator is automatically created for the list

function make_list return listptr;


-- creates and returns an iterator for a given list,
--  initialized to the beginning of the list.

function make_iterator(s:listptr) return iterptr;


-- returns true iff iterator is not poisitioned at
--   the last element of the list.

function has_next(it:iterptr) return boolean; 


-- advances the iterator to the next element of the list.
-- does not advance if there is no next element.

procedure next(it:iterptr);


-- returns (a shallow copy of) the element at the current 
--   position of the iterator.
  
function get_current(it:iterptr) return T;


-- makes and returns a copy of a given iterator.
-- advancing the iterator will not advance its copy,
--   and vice versa

function copy_iterator(it:iterptr) return iterptr;


-- adds (a shallow copy of) a given element to the end of a given list

procedure add_to_end(s:listptr; i:T);


-- adds (a shallow copy of) a given element to the beginning of a given list

procedure add_to_beginning(s:listptr; i:T);


-- finds the length of a given list

function length(s:listptr) return integer;


-- returns a new list obtained by appending l2 to the end of l1
-- the elements of the new list are shallow copies of the 
--   elements of the input list

function append(l1,l2: listptr) return listptr;




private

type list;
type listptr is access list;
type iterator;
type iterptr is access iterator;

end link;