-----------------------------------------------------------------------------
--
--                     Onions Network Streams Library
--
--                   O N I O N S . L I S T _ Q U E U E S
--
--                                 S p e c
--
--     Copyright (C) 1997-1998  Regents of the University of California
--
--  Onions 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.  Onions 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 Onions; 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 Roy T. Fielding and Kari Nies
-----------------------------------------------------------------------------
--
--  This package implements a doubly-linked list and undoable FIFO queue
--  with a generic element type.  They are too tightly coupled to
--  justify separate packages.

generic

   type Element_Type is private;

package Onions.List_Queues is

   type Cell;

   type List is access Cell;

   type Cell is
      record
         Data : Element_Type;
         Prev : List := null;
         Next : List := null;
      end record;

   type Queue is limited private;

   -----------------------
   --  List Operations  --
   -----------------------

   function IsEmpty (L : in List) return Boolean;

   function Length (L : in List) return Natural;

   function Front_of_List (L : in List) return List;

   function End_of_List (L : in List) return List;

   function Add_Before (Successor : in List; Element : in Element_Type)
      return List;

   function Add_After (Predecessor : in List; Element : in Element_Type)
      return List;

   --  Head is a non-destructive grab of the first element in L
   --
   function Head (L : in List) return Element_Type;

   --  Tail is a non-destructive grab of the list after L.
   --  Raises Constraint_Error if L = null.
   --
   function Tail (L : in List) return List;

   --  Nose is a non-destructive grab of the list before L.
   --  Raises Constraint_Error if L = null.
   --
   function Nose (L : in List) return List;

   --  Extract is a destructive Head + Tail combo.
   --  Raises Constraint_Error if Pos is empty.
   --
   procedure Extract (Pos : in out List; Element : out Element_Type);

   --  Extract_Last is a destructive pop from the list end.
   --  Raises Constraint_Error if Front is empty.
   --
   procedure Extract_Last (Front : in out List; Element : out Element_Type);

   --  Split separates a list into two lists, where Pos is the beginning
   --  of the second list.  It is assumed the caller knows where the
   --  resulting two lists begin (e.g., Front_of_List(Pos) and Pos).
   --  Raises Constraint_Error if Pos is empty.
   --
   procedure Split (Pos : in List);

   --  Splice inserts a list into another list without copying.
   --  Raises Constraint_Error if After is empty.
   --
   procedure Splice (After : in List; Wedgie : in List);

   --  Copy a list as if it were fronted at Pos (not a deep copy).
   --
   function Copy (L : in List) return List;

   --  The "&" operator returns a new list consisting of a copy of
   --  Front linked to a copy of Back.  Use Splice to avoid the copy.
   --
   function "&" (Front, Back : in List) return List;

   ------------------------
   --  Queue Operations  --
   ------------------------

   function Length (Q : in Queue) return Natural;

   procedure Enqueue (Q : in out Queue; Element : in Element_Type);

   procedure Enqueue (Q : in out Queue; L : in List);

   procedure Dequeue (Q : in out Queue; Element : out Element_Type);

   procedure Dequeue (Q : in out Queue; L : out List);

   procedure Undequeue (Q : in out Queue; Element : in Element_Type);

   procedure Undequeue (Q : in out Queue; L : in List);

   Empty : exception;

private

   type Queue is
      record
         Count : Natural := 0;
         First : List := null;
         Last  : List := null;
      end record;

end Onions.List_Queues;