-------------------------------------------------------------------------------
-- This file contains a proposal for a standard Ada list package.
--
-- version - Strawman 1.0
-------------------------------------------------------------------------------
generic
   type Element is private;
package Containers.Lists.Unbounded is

   -----------------------------------------------------------------------------
   -- The list type. I know the name's a bit redundant, but it doesn't look too
   -- bad, and any fully-named use will have to have a different name for the
   -- package anyway.
   -----------------------------------------------------------------------------
   type List is private;

   -----------------------------------------------------------------------------
   -- List construction operations. The returned list will contain *copies* of
   -- all the elements in the source lists, so these routines could get
   -- time-consuming. However, they should be useful for Lisp-like processing.
   --
   -- I considered using unary minus ("-") for the "Construct" routine, but
   -- that's not a common idiom right now.
   -----------------------------------------------------------------------------
   function "&" (Left, Right : Element) return List;
   function "&" (Left : Element; Right : List) return List;
   function "&" (Left : List; Right : Element) return List;
   function "&" (Left, Right : List) return List;
   function Construct (Initial_Element : Element) return List;

   -----------------------------------------------------------------------------
   -- "push" and "pop" operations.
   -----------------------------------------------------------------------------
   procedure Push_Front (Target : in out List; New_Element : in     Element);
   procedure Pop_Front  (Target : in out List; Old_Element :    out Element);
   procedure Push_Back  (Target : in out List; New_Element : in     Element);
   procedure Pop_Back   (Target : in out List; Old_Element :    out Element);

   -----------------------------------------------------------------------------
   -- Non-modifying query operations.
   -----------------------------------------------------------------------------
   function Is_Empty (Subject : List) return Boolean;
   function Size     (Subject : List) return Natural;
   function Front    (Subject : List) return Element;
   function Back     (Subject : List) return Element;

   -----------------------------------------------------------------------------
   -- I'm not too sure how useful these are, since they have to work on global
   -- data.
   -----------------------------------------------------------------------------
   generic
      with procedure Operation (Target : in out Element);
   procedure Closure_Operation (Target : in out List);

   -----------------------------------------------------------------------------
   -- Iteration routines. Next and Previous raise No_More if there is no item in
   -- the given direction. For an empty list, First = Last. As written, a
   -- typical iteration idiom would look like:
   --
   --    i := My_Lists.First (My_List);
   --    loop
   --       do stuff with My_Lists.Item(i);
   --       exit when i = My_Lists.Last (My_List);
   --       i := My_Lists.Next (i);
   --    end loop;
   --
   -- Another alternative using exception handling would be:
   --
   --    declare
   --       i := My_Lists.First (My_List);
   --    begin
   --       loop
   --          do stuff with My_Lists.Item(i);
   --          i := My_Lists.Next (i);
   --       end loop;
   --    exception
   --       when My_Lists.No_More =>
   --          null;
   --    end;
   --
   -- A third alternative using "Size" would be:
   --
   --  i := My_Lists.First (My_List);
   --  for iteration_count in 1..My_Lists.Size (My_List) loop
   --    do stuff with My_Lists.Item (i);
   --    i := My_Lists.Next (i);
   --  end loop;
   --
   -----------------------------------------------------------------------------
   type Iterator is private;
   No_More : exception;

   function First    (Subject : List)      return Iterator;
   function Last     (Subject : List)      return Iterator;
   function Next     (Location : Iterator) return Iterator;
   function Previous (Location : Iterator) return Iterator;
   function Item     (Location : Iterator) return Element;

   -- Ideally this routine would verify that Location was issued for the Subject
   -- list and is still valid, but that would be tough to enforce. Better to call
   -- such misuse a "bounded error", or somesuch.
   procedure Remove   (Subject : in out List; Location : Iterator);

   -----------------------------------------------------------------------------
   -- Sorting routine.
   -- To sort in increasing order, use the ">" routine for the Reverse_Order
   -- parameter. To sort in decreasing order, substitute your "<" routine for
   -- the Reverse_Order parameter. :-)
   -----------------------------------------------------------------------------
   generic
      with function Reverse_Order (Left, Right : in Element) return Boolean;
   procedure Sort (Subject : in out List);

private
   -- Placebo entries to make the compiler happy (so I know the syntax above is correct)
   type List is new Boolean;
   type Iterator is new Boolean;

end Containers.Lists.Unbounded;