-- This is the implementation of a simple generic list package, with
--   1-directional iterators.



package body link is
 

type node;
type nodeptr is access node;


-- Lists are represented as singly linked lists of nodes, with 
--   header and footer nodes.  Header and footer nodes
--   have uninitialized data values (this is safe, due to 
--   encapsulation, and necessary, since the type of the
--   data values is unknown).
-- An iterator consists of a pointer to the list that it is
--   iterating over, and a pointer to the next element
--   of the list.  This pointer points to the footer of the
--   list if there is no next element.

type node is record  
  data:T;  
  link:nodeptr;
end record;

type list is record
  header: nodeptr;
  footer: nodeptr;  
end record;

type iterator is record
  mainlist:listptr;
  cursor:nodeptr;
end record;


-- The public function that creates and returns an empty list.
-- It simply creates a list with only a header and a footer node.

function make_list return listptr is
l:listptr := new list;
begin
  l.header := new node;
  l.footer := new node;         
  l.header.link := l.footer;
  return l;
end make_list;


-- This is the public procedure that adds an item i to the 
--   beginning of a linked list s.  The implementation simply
--   adds i immediately after s's header node)

procedure add_to_beginning(s:listptr; i:T) is
q:nodeptr:=new node'(i,s.header.link);
begin
  s.header.link := q;
end add_to_beginning;


-- This is the public procedure that adds an item i to the
--   end of a linked list.  It uses the common trick of 
--   adding a new node after the footer, putting the new
--   data into the old footer, and updating the footer pointer
--   to point to the new node.

procedure add_to_end(s:listptr; i:T) is
q:nodeptr:= new node;
begin
    s.footer.data := i;
    s.footer.link := q;
    s.footer      := q;
end add_to_end;  


-- This is the public function that creates and returns an
--   iterator for the list s.  It initializes the current (next)
--   pointer to the first node after the header.  Note that
--   for an empty list, this will be the footer.

function make_iterator(s:listptr) return iterptr is
begin
  return new iterator'(s,s.header.link);
end make_iterator;


-- This is the public function that makes and returns a copy
--   of a given iterator.  It simply constructs a new iterator
--   whose fields are copied from the old one.

function copy_iterator(it:iterptr) return iterptr is
begin
  return new iterator'(it.mainlist, it.cursor);
end copy_iterator;


-- This is the public function that determines whether a given
--   iterator is not positioned at the end of its list.  It simply
--   checks to see whether it is positioned at its list's footer.
      
function has_next(it:iterptr) return boolean is
s:listptr := it.mainlist;
begin
  return it.cursor /= s.footer;
end has_next;


-- This is the public procedure that advances an iterator.
-- It does not advance if there is no next element.

procedure next(it:iterptr) is
begin
  if has_next(it) then
    it.cursor := it.cursor.link;
  end if;
end next;


-- This is the public function that returns (a shallow copy of)
--   the current (next) element.
  
function get_current(it:iterptr) return T is
begin
  return it.cursor.data;
end get_current;


-- Finds and returns the length of a list by doing a
--   straightforward iterator-based traversal.

function length(s:listptr) return integer is
len:integer := 0;
it:iterptr := make_iterator(s);
begin
  while has_next(it) loop
    len := len + 1;
    next(it);      
  end loop;
  return len;
end length;


-- This is the public function that appends two lists.
-- It returns a new lists containing a shallow copy of 
--   each item in l1 followed by a shallow copy of 
--   each item in l2.
-- It simply creates a new empty list, and then 
--   traverses the two lists using iterators, adding 
--   successive elements to the end of the output list.

function append(l1,l2: listptr) return listptr is
output:listptr := make_list;
it:iterptr := make_iterator(l1);
next_item:T;
begin 
  while has_next(it) loop
    next_item := get_current(it);
    add_to_end(output,next_item);
    next(it);      
  end loop;
  it := make_iterator(l2);
  while has_next(it) loop
    next_item := get_current(it);
    add_to_end(output,next_item);
    next(it);      
  end loop;
  return output;
end append;

end link;