gcc/ada/a-crdlli.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT LIBRARY COMPONENTS                          --
   4 --                                                                          --
   5 --              ADA.CONTAINERS.RESTRICTED_DOUBLY_LINKED_LISTS               --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --          Copyright (C) 2004-2008, Free Software Foundation, Inc.         --
  10 --                                                                          --
  11 -- GNAT is free software;  you can  redistribute it  and/or modify it under --
  12 -- terms of the  GNU General Public License as published  by the Free Soft- --
  13 -- ware  Foundation;  either version 2,  or (at your option) any later ver- --
  14 -- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
  15 -- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
  16 -- or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License --
  17 -- for  more details.  You should have  received  a copy of the GNU General --
  18 -- Public License  distributed with GNAT;  see file COPYING.  If not, write --
  19 -- to  the  Free Software Foundation,  51  Franklin  Street,  Fifth  Floor, --
  20 -- Boston, MA 02110-1301, USA.                                              --
  21 --                                                                          --
  22 -- As a special exception,  if other files  instantiate  generics from this --
  23 -- unit, or you link  this unit with other files  to produce an executable, --
  24 -- this  unit  does not  by itself cause  the resulting  executable  to  be --
  25 -- covered  by the  GNU  General  Public  License.  This exception does not --
  26 -- however invalidate  any other reasons why  the executable file  might be --
  27 -- covered by the  GNU Public License.                                      --
  28 --                                                                          --
  29 -- This unit was originally developed by Matthew J Heaney.                  --
  30 ------------------------------------------------------------------------------
  31
  32 --  The doubly-linked list container provides constant-time insertion and
  33 --  deletion at all positions, and allows iteration in both the forward and
  34 --  reverse directions. This list form allocates storage for all nodes
  35 --  statically (there is no dynamic allocation), and a discriminant is used to
  36 --  specify the capacity. This container is also "restricted", meaning that
  37 --  even though it does raise exceptions (as described below), it does not use
  38 --  internal exception handlers. No state changes are made that would need to
  39 --  be reverted (in the event of an exception), and so as a consequence, this
  40 --  container cannot detect tampering (of cursors or elements).
  41
  42 generic
  43    type Element_Type is private;
  44
  45    with function "=" (Left, Right : Element_Type)
  46       return Boolean is <>;
  47
  48 package Ada.Containers.Restricted_Doubly_Linked_Lists is
  49    pragma Pure;
  50
  51    type List (Capacity : Count_Type) is tagged limited private;
  52    pragma Preelaborable_Initialization (List);
  53
  54    type Cursor is private;
  55    pragma Preelaborable_Initialization (Cursor);
  56
  57    Empty_List : constant List;
  58    --  The default value for list objects declared without an explicit
  59    --  initialization expression.
  60
  61    No_Element : constant Cursor;
  62    --  The default value for cursor objects declared without an explicit
  63    --  initialization expression.
  64
  65    function "=" (Left, Right : List) return Boolean;
  66    --  If Left denotes the same list object as Right, then equality returns
  67    --  True. If the length of Left is different from the length of Right, then
  68    --  it returns False. Otherwise, list equality iterates over Left and Right,
  69    --  comparing the element of Left to the corresponding element of Right
  70    --  using the generic actual equality operator for elements. If the elements
  71    --  compare False, then the iteration terminates and list equality returns
  72    --  False. Otherwise, if all elements return True, then list equality
  73    --  returns True.
  74
  75    procedure Assign (Target : in out List; Source : List);
  76    --  If Target denotes the same list object as Source, the operation does
  77    --  nothing. If Target.Capacity is less than Source.Length, then it raises
  78    --  Constraint_Error. Otherwise, it clears Target, and then inserts each
  79    --  element of Source into Target.
  80
  81    function Length (Container : List) return Count_Type;
  82    --  Returns the total number of (active) elements in Container
  83
  84    function Is_Empty (Container : List) return Boolean;
  85    --  Returns True if Container.Length is 0
  86
  87    procedure Clear (Container : in out List);
  88    --  Deletes all elements from Container. Note that this is a bounded
  89    --  container and so the element is not "deallocated" in the same sense that
  90    --  an unbounded form would deallocate the element. Rather, the node is
  91    --  relinked off of the active part of the list and onto the inactive part
  92    --  of the list (the storage from which new elements are "allocated").
  93
  94    function Element (Position : Cursor) return Element_Type;
  95    --  If Position equals No_Element, then Constraint_Error is raised.
  96    --  Otherwise, function Element returns the element designed by Position.
  97
  98    procedure Replace_Element
  99      (Container : in out List;
 100       Position  : Cursor;
 101       New_Item  : Element_Type);
 102    --  If Position equals No_Element, then Constraint_Error is raised. If
 103    --  Position is associated with a list object different from Container,
 104    --  Program_Error is raised. Otherwise, the element designated by Position
 105    --  is assigned the value New_Item.
 106
 107    procedure Query_Element
 108      (Position : Cursor;
 109       Process  : not null access procedure (Element : Element_Type));
 110    --  If Position equals No_Element, then Constraint_Error is raised.
 111    --  Otherwise, it calls Process with (a constant view of) the element
 112    --  designated by Position as the parameter.
 113
 114    procedure Update_Element
 115      (Container : in out List;
 116       Position  : Cursor;
 117       Process   : not null access procedure (Element : in out Element_Type));
 118    --  If Position equals No_Element, then Constraint_Error is raised.
 119    --  Otherwise, it calls Process with (a variable view of) the element
 120    --  designated by Position as the parameter.
 121
 122    procedure Insert
 123      (Container : in out List;
 124       Before    : Cursor;
 125       New_Item  : Element_Type;
 126       Count     : Count_Type := 1);
 127    --  Inserts Count new elements, all with the value New_Item, into Container,
 128    --  immediately prior to the position specified by Before. If Before has the
 129    --  value No_Element, this is interpreted to mean that the elements are
 130    --  appended to the list. If Before is associated with a list object
 131    --  different from Container, then Program_Error is raised. If there are
 132    --  fewer than Count nodes available, then Constraint_Error is raised.
 133
 134    procedure Insert
 135      (Container : in out List;
 136       Before    : Cursor;
 137       New_Item  : Element_Type;
 138       Position  : out Cursor;
 139       Count     : Count_Type := 1);
 140    --  Inserts elements into Container as described above, but with the
 141    --  difference that cursor Position is returned, which designates the first
 142    --  of the new elements inserted. If Count is 0, Position returns the value
 143    --  Before.
 144
 145    procedure Insert
 146      (Container : in out List;
 147       Before    : Cursor;
 148       Position  : out Cursor;
 149       Count     : Count_Type := 1);
 150    --  Inserts elements in Container as described above, but with the
 151    --  difference that the new elements are initialized to the default value
 152    --  for objects of type Element_Type.
 153
 154    procedure Prepend
 155      (Container : in out List;
 156       New_Item  : Element_Type;
 157       Count     : Count_Type := 1);
 158    --  Inserts Count elements, all having the value New_Item, prior to the
 159    --  first element of Container.
 160
 161    procedure Append
 162      (Container : in out List;
 163       New_Item  : Element_Type;
 164       Count     : Count_Type := 1);
 165    --  Inserts Count elements, all having the value New_Item, following the
 166    --  last element of Container.
 167
 168    procedure Delete
 169      (Container : in out List;
 170       Position  : in out Cursor;
 171       Count     : Count_Type := 1);
 172    --  If Position equals No_Element, Constraint_Error is raised. If Position
 173    --  is associated with a list object different from Container, then
 174    --  Program_Error is raised. Otherwise, the Count nodes starting from
 175    --  Position are removed from Container ("removed" meaning that the nodes
 176    --  are unlinked from the active nodes of the list and relinked to inactive
 177    --  storage). On return, Position is set to No_Element.
 178
 179    procedure Delete_First
 180      (Container : in out List;
 181       Count     : Count_Type := 1);
 182    --  Removes the first Count nodes from Container
 183
 184    procedure Delete_Last
 185      (Container : in out List;
 186       Count     : Count_Type := 1);
 187    --  Removes the last Count nodes from Container
 188
 189    procedure Reverse_Elements (Container : in out List);
 190    --  Relinks the nodes in reverse order
 191
 192    procedure Swap
 193      (Container : in out List;
 194       I, J      : Cursor);
 195    --  If I or J equals No_Element, then Constraint_Error is raised. If I or J
 196    --  is associated with a list object different from Container, then
 197    --  Program_Error is raised. Otherwise, Swap exchanges (copies) the values
 198    --  of the elements (on the nodes) designated by I and J.
 199
 200    procedure Swap_Links
 201      (Container : in out List;
 202       I, J      : Cursor);
 203    --  If I or J equals No_Element, then Constraint_Error is raised. If I or J
 204    --  is associated with a list object different from Container, then
 205    --  Program_Error is raised. Otherwise, Swap exchanges (relinks) the nodes
 206    --  designated by I and J.
 207
 208    procedure Splice
 209      (Container : in out List;
 210       Before    : Cursor;
 211       Position  : in out Cursor);
 212    --  If Before is associated with a list object different from Container,
 213    --  then Program_Error is raised. If Position equals No_element, then
 214    --  Constraint_Error is raised; if it associated with a list object
 215    --  different from Container, then Program_Error is raised. Otherwise, the
 216    --  node designated by Position is relinked immediately prior to Before. If
 217    --  Before equals No_Element, this is interpreted to mean to move the node
 218    --  designed by Position to the last end of the list.
 219
 220    function First (Container : List) return Cursor;
 221    --  If Container is empty, the function returns No_Element. Otherwise, it
 222    --  returns a cursor designating the first element.
 223
 224    function First_Element (Container : List) return Element_Type;
 225    --  Equivalent to Element (First (Container))
 226
 227    function Last (Container : List) return Cursor;
 228    --  If Container is empty, the function returns No_Element. Otherwise, it
 229    --  returns a cursor designating the last element.
 230
 231    function Last_Element (Container : List) return Element_Type;
 232    --  Equivalent to Element (Last (Container))
 233
 234    function Next (Position : Cursor) return Cursor;
 235    --  If Position equals No_Element or Last (Container), the function returns
 236    --  No_Element. Otherwise, it returns a cursor designating the node that
 237    --  immediately follows the node designated by Position.
 238
 239    procedure Next (Position : in out Cursor);
 240    --  Equivalent to Position := Next (Position)
 241
 242    function Previous (Position : Cursor) return Cursor;
 243    --  If Position equals No_Element or First (Container), the function returns
 244    --  No_Element. Otherwise, it returns a cursor designating the node that
 245    --  immediately precedes the node designated by Position.
 246
 247    procedure Previous (Position : in out Cursor);
 248    --  Equivalent to Position := Previous (Position)
 249
 250    function Find
 251      (Container : List;
 252       Item      : Element_Type;
 253       Position  : Cursor := No_Element) return Cursor;
 254    --  Searches for the node whose element is equal to Item, starting from
 255    --  Position and continuing to the last end of the list. If Position equals
 256    --  No_Element, the search starts from the first node. If Position is
 257    --  associated with a list object different from Container, then
 258    --  Program_Error is raised. If no node is found having an element equal to
 259    --  Item, then Find returns No_Element.
 260
 261    function Reverse_Find
 262      (Container : List;
 263       Item      : Element_Type;
 264       Position  : Cursor := No_Element) return Cursor;
 265    --  Searches in reverse for the node whose element is equal to Item,
 266    --  starting from Position and continuing to the first end of the list. If
 267    --  Position equals No_Element, the search starts from the last node. If
 268    --  Position is associated with a list object different from Container, then
 269    --  Program_Error is raised. If no node is found having an element equal to
 270    --  Item, then Reverse_Find returns No_Element.
 271
 272    function Contains
 273      (Container : List;
 274       Item      : Element_Type) return Boolean;
 275    --  Equivalent to Container.Find (Item) /= No_Element
 276
 277    function Has_Element (Position : Cursor) return Boolean;
 278    --  Equivalent to Position /= No_Element
 279
 280    procedure Iterate
 281      (Container : List;
 282       Process   : not null access procedure (Position : Cursor));
 283    --  Calls Process with a cursor designating each element of Container, in
 284    --  order from Container.First to Container.Last.
 285
 286    procedure Reverse_Iterate
 287      (Container : List;
 288       Process   : not null access procedure (Position : Cursor));
 289    --  Calls Process with a cursor designating each element of Container, in
 290    --  order from Container.Last to Container.First.
 291
 292    generic
 293       with function "<" (Left, Right : Element_Type) return Boolean is <>;
 294    package Generic_Sorting is
 295
 296       function Is_Sorted (Container : List) return Boolean;
 297       --  Returns False if there exists an element which is less than its
 298       --  predecessor.
 299
 300       procedure Sort (Container : in out List);
 301       --  Sorts the elements of Container (by relinking nodes), according to
 302       --  the order specified by the generic formal less-than operator, such
 303       --  that smaller elements are first in the list. The sort is stable,
 304       --  meaning that the relative order of elements is preserved.
 305
 306    end Generic_Sorting;
 307
 308 private
 309
 310    type Node_Type is limited record
 311       Prev    : Count_Type'Base;
 312       Next    : Count_Type;
 313       Element : Element_Type;
 314    end record;
 315
 316    type Node_Array is array (Count_Type range <>) of Node_Type;
 317
 318    type List (Capacity : Count_Type) is tagged limited record
 319       Nodes  : Node_Array (1 .. Capacity) := (others => <>);
 320       Free   : Count_Type'Base := -1;
 321       First  : Count_Type := 0;
 322       Last   : Count_Type := 0;
 323       Length : Count_Type := 0;
 324    end record;
 325
 326    Empty_List : constant List := (0, others => <>);
 327
 328    type List_Access is access all List;
 329    for List_Access'Storage_Size use 0;
 330
 331    type Cursor is
 332       record
 333          Container : List_Access;
 334          Node      : Count_Type := 0;
 335       end record;
 336
 337    No_Element : constant Cursor := (null, 0);
 338
 339 end Ada.Containers.Restricted_Doubly_Linked_Lists;