-----------------------------------------------------------------------------
--
--         libwww-ada95 : A World Wide Web client library for Ada95
--
--                          U T I L . L L I S T S
--
--                                 S p e c
--
--     Copyright (C) 1997-1998  Regents of the University of California
--
--  libwww-ada95 is free software; you can redistribute it and/or modify it
--  under the terms of the GNU General Public License as published by the Free
--  Software Foundation, with or without the single exception listed below;
--  either version 2, or (at your option) any later version.  libwww-ada95 is
--  distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
--  without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
--  PARTICULAR PURPOSE.  See the GNU General Public License for more details.
--  You should have received a copy of the GNU General Public License
--  distributed with libwww-ada95; see the file COPYING.  If not, write to the
--  Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
--  02111-1307, USA.
--
--  As a special exception, if other files instantiate generics from this
--  library, or you link this library with other files to produce an
--  executable, this library does not by itself cause the resulting
--  executable to be covered by the GNU General Public License.  This
--  exception does not however invalidate any other reasons why the
--  executable file might be covered by the GNU General Public License.
--
--  Created in 1997 by Kari Nies
-----------------------------------------------------------------------------
--
--  Generic linked list package.
--

generic
   type Item_Type is private;

   with function Equal (X, Y : in Item_Type) return boolean is "=";
                              --  | This allows the user to define
                              --  | equality on Item_Type.  For instance
                              --  | if Item_Type is an abstract type
                              --  | then equality is defined in terms of
                              --  | the abstract type.  If this function
                              --  | is not provided equality defaults to
                              --  | =.

package Util.LLists is

   type List is private;
   type List_Iterator is private;

   Empty_List : constant List;

   ------------------------------------------------
   --  Insert item I at beginning of list L
   ------------------------------------------------
   procedure Insert (L : in out List;
                     I : Item_Type);

   ------------------------------------------------
   --  Append item I to end of list L
   ------------------------------------------------
   procedure Append (L : in out List;
                     I : Item_Type);

   ------------------------------------------------
   --  Append L2 to the end of L1. does not copy.
   --  L2 is reset to be empty.
   ------------------------------------------------
   procedure Append (L1 : in out List;
                     L2 : in out List);

   ------------------------------------------------
   --  Removes the first item of the list equal to I
   ------------------------------------------------
   procedure Delete_Item (L : in out List;
                          I : in     Item_Type);

   ------------------------------------------------
   --  Returns the number of items in the given list
   ------------------------------------------------
   function Length (L : List) return NATURAL;

   ------------------------------------------------
   --  Queries if the given list is empty
   ------------------------------------------------
   function Is_Empty (L : List) return BOOLEAN;

   ------------------------------------------------
   --  Queries if the item I is in the list L.
   ------------------------------------------------
   function Is_In_List (L : List;
                        I : Item_Type) return boolean;

   ------------------------------------------------
   --  Copies the contents of L to a new list
   ------------------------------------------------
   function Copy (L : in List) return List;

   ------------------------------------------------
   --  Deallocates all items in a list;
   ------------------------------------------------
   procedure Destroy (L : in out List);


   --  Iterator operations

   ------------------------------------------------
   --  Create a new iterator for list L
   ------------------------------------------------
   function New_Iterator (L : List) return List_Iterator;

   ------------------------------------------------
   --  Query if the given iterator is exhausted
   ------------------------------------------------
   function More (LI : List_Iterator) return BOOLEAN;

   ------------------------------------------------
   --  Advance the given iterator and return the
   --  next item.
   ------------------------------------------------
   procedure Next (LI : in out List_Iterator;
                   I  : out Item_Type);

   --  exceptions
   No_More_Items    : exception; --  raised it an attempt is made to get the
                                 --  next item after iteration is complete
   Item_Not_Present : exception; --  raised if an attempt is made to remove
                                 --  an item which does not exist

private

   type Cell;
   type Cell_Ptr is access Cell;

   type Cell is record
      Info : Item_Type;
      Next : Cell_Ptr;
   end record;

   type List is record
       First  : Cell_Ptr := null;  -- ptr to first item in list
       Last   : Cell_Ptr := null;  -- ptr to last item in list
       Length : NATURAL  := 0;     -- currentl length of list
   end record;

   type List_Iterator is new Cell_Ptr;

   Empty_List : constant List := (null, null, 0);

end Util.LLists;