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