1------------------------------------------------------------------------------ 2-- -- 3-- GNAT LIBRARY COMPONENTS -- 4-- -- 5-- ADA.CONTAINERS.BOUNDED_DOUBLY_LINKED_LISTS -- 6-- -- 7-- S p e c -- 8-- -- 9-- Copyright (C) 2004-2015, Free Software Foundation, Inc. -- 10-- -- 11-- This specification is derived from the Ada Reference Manual for use with -- 12-- GNAT. The copyright notice above, and the license provisions that follow -- 13-- apply solely to the contents of the part following the private keyword. -- 14-- -- 15-- GNAT is free software; you can redistribute it and/or modify it under -- 16-- terms of the GNU General Public License as published by the Free Soft- -- 17-- ware Foundation; either version 3, or (at your option) any later ver- -- 18-- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- 19-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- 20-- or FITNESS FOR A PARTICULAR PURPOSE. -- 21-- -- 22-- As a special exception under Section 7 of GPL version 3, you are granted -- 23-- additional permissions described in the GCC Runtime Library Exception, -- 24-- version 3.1, as published by the Free Software Foundation. -- 25-- -- 26-- You should have received a copy of the GNU General Public License and -- 27-- a copy of the GCC Runtime Library Exception along with this program; -- 28-- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -- 29-- <http://www.gnu.org/licenses/>. -- 30-- -- 31-- This unit was originally developed by Matthew J Heaney. -- 32------------------------------------------------------------------------------ 33 34with Ada.Iterator_Interfaces; 35 36with Ada.Containers.Helpers; 37private with Ada.Streams; 38private with Ada.Finalization; 39 40generic 41 type Element_Type is private; 42 43 with function "=" (Left, Right : Element_Type) 44 return Boolean is <>; 45 46package Ada.Containers.Bounded_Doubly_Linked_Lists is 47 pragma Annotate (CodePeer, Skip_Analysis); 48 pragma Pure; 49 pragma Remote_Types; 50 51 type List (Capacity : Count_Type) is tagged private with 52 Constant_Indexing => Constant_Reference, 53 Variable_Indexing => Reference, 54 Default_Iterator => Iterate, 55 Iterator_Element => Element_Type; 56 57 pragma Preelaborable_Initialization (List); 58 59 type Cursor is private; 60 pragma Preelaborable_Initialization (Cursor); 61 62 Empty_List : constant List; 63 64 No_Element : constant Cursor; 65 66 function Has_Element (Position : Cursor) return Boolean; 67 68 package List_Iterator_Interfaces is new 69 Ada.Iterator_Interfaces (Cursor, Has_Element); 70 71 function "=" (Left, Right : List) return Boolean; 72 73 function Length (Container : List) return Count_Type; 74 75 function Is_Empty (Container : List) return Boolean; 76 77 procedure Clear (Container : in out List); 78 79 function Element (Position : Cursor) return Element_Type; 80 81 procedure Replace_Element 82 (Container : in out List; 83 Position : Cursor; 84 New_Item : Element_Type); 85 86 procedure Query_Element 87 (Position : Cursor; 88 Process : not null access procedure (Element : Element_Type)); 89 90 procedure Update_Element 91 (Container : in out List; 92 Position : Cursor; 93 Process : not null access procedure (Element : in out Element_Type)); 94 95 type Constant_Reference_Type 96 (Element : not null access constant Element_Type) is private 97 with 98 Implicit_Dereference => Element; 99 100 type Reference_Type 101 (Element : not null access Element_Type) is private 102 with 103 Implicit_Dereference => Element; 104 105 function Constant_Reference 106 (Container : aliased List; 107 Position : Cursor) return Constant_Reference_Type; 108 109 function Reference 110 (Container : aliased in out List; 111 Position : Cursor) return Reference_Type; 112 113 procedure Assign (Target : in out List; Source : List); 114 115 function Copy (Source : List; Capacity : Count_Type := 0) return List; 116 117 procedure Move 118 (Target : in out List; 119 Source : in out List); 120 121 procedure Insert 122 (Container : in out List; 123 Before : Cursor; 124 New_Item : Element_Type; 125 Count : Count_Type := 1); 126 127 procedure Insert 128 (Container : in out List; 129 Before : Cursor; 130 New_Item : Element_Type; 131 Position : out Cursor; 132 Count : Count_Type := 1); 133 134 procedure Insert 135 (Container : in out List; 136 Before : Cursor; 137 Position : out Cursor; 138 Count : Count_Type := 1); 139 140 procedure Prepend 141 (Container : in out List; 142 New_Item : Element_Type; 143 Count : Count_Type := 1); 144 145 procedure Append 146 (Container : in out List; 147 New_Item : Element_Type; 148 Count : Count_Type := 1); 149 150 procedure Delete 151 (Container : in out List; 152 Position : in out Cursor; 153 Count : Count_Type := 1); 154 155 procedure Delete_First 156 (Container : in out List; 157 Count : Count_Type := 1); 158 159 procedure Delete_Last 160 (Container : in out List; 161 Count : Count_Type := 1); 162 163 procedure Reverse_Elements (Container : in out List); 164 165 function Iterate 166 (Container : List) 167 return List_Iterator_Interfaces.Reversible_Iterator'class; 168 169 function Iterate 170 (Container : List; 171 Start : Cursor) 172 return List_Iterator_Interfaces.Reversible_Iterator'class; 173 174 procedure Swap 175 (Container : in out List; 176 I, J : Cursor); 177 178 procedure Swap_Links 179 (Container : in out List; 180 I, J : Cursor); 181 182 procedure Splice 183 (Target : in out List; 184 Before : Cursor; 185 Source : in out List); 186 187 procedure Splice 188 (Target : in out List; 189 Before : Cursor; 190 Source : in out List; 191 Position : in out Cursor); 192 193 procedure Splice 194 (Container : in out List; 195 Before : Cursor; 196 Position : Cursor); 197 198 function First (Container : List) return Cursor; 199 200 function First_Element (Container : List) return Element_Type; 201 202 function Last (Container : List) return Cursor; 203 204 function Last_Element (Container : List) return Element_Type; 205 206 function Next (Position : Cursor) return Cursor; 207 208 procedure Next (Position : in out Cursor); 209 210 function Previous (Position : Cursor) return Cursor; 211 212 procedure Previous (Position : in out Cursor); 213 214 function Find 215 (Container : List; 216 Item : Element_Type; 217 Position : Cursor := No_Element) return Cursor; 218 219 function Reverse_Find 220 (Container : List; 221 Item : Element_Type; 222 Position : Cursor := No_Element) return Cursor; 223 224 function Contains 225 (Container : List; 226 Item : Element_Type) return Boolean; 227 228 procedure Iterate 229 (Container : List; 230 Process : not null access procedure (Position : Cursor)); 231 232 procedure Reverse_Iterate 233 (Container : List; 234 Process : not null access procedure (Position : Cursor)); 235 236 generic 237 with function "<" (Left, Right : Element_Type) return Boolean is <>; 238 package Generic_Sorting is 239 240 function Is_Sorted (Container : List) return Boolean; 241 242 procedure Sort (Container : in out List); 243 244 procedure Merge (Target, Source : in out List); 245 246 end Generic_Sorting; 247 248private 249 250 pragma Inline (Next); 251 pragma Inline (Previous); 252 253 use Ada.Containers.Helpers; 254 package Implementation is new Generic_Implementation; 255 use Implementation; 256 257 use Ada.Streams; 258 use Ada.Finalization; 259 260 type Node_Type is record 261 Prev : Count_Type'Base; 262 Next : Count_Type; 263 Element : aliased Element_Type; 264 end record; 265 266 type Node_Array is array (Count_Type range <>) of Node_Type; 267 268 type List (Capacity : Count_Type) is tagged record 269 Nodes : Node_Array (1 .. Capacity) := (others => <>); 270 Free : Count_Type'Base := -1; 271 First : Count_Type := 0; 272 Last : Count_Type := 0; 273 Length : Count_Type := 0; 274 TC : aliased Tamper_Counts; 275 end record; 276 277 procedure Read 278 (Stream : not null access Root_Stream_Type'Class; 279 Item : out List); 280 281 for List'Read use Read; 282 283 procedure Write 284 (Stream : not null access Root_Stream_Type'Class; 285 Item : List); 286 287 for List'Write use Write; 288 289 type List_Access is access all List; 290 for List_Access'Storage_Size use 0; 291 292 type Cursor is record 293 Container : List_Access; 294 Node : Count_Type := 0; 295 end record; 296 297 procedure Read 298 (Stream : not null access Root_Stream_Type'Class; 299 Item : out Cursor); 300 301 for Cursor'Read use Read; 302 303 procedure Write 304 (Stream : not null access Root_Stream_Type'Class; 305 Item : Cursor); 306 307 for Cursor'Write use Write; 308 309 subtype Reference_Control_Type is Implementation.Reference_Control_Type; 310 -- It is necessary to rename this here, so that the compiler can find it 311 312 type Constant_Reference_Type 313 (Element : not null access constant Element_Type) is 314 record 315 Control : Reference_Control_Type := 316 raise Program_Error with "uninitialized reference"; 317 -- The RM says, "The default initialization of an object of 318 -- type Constant_Reference_Type or Reference_Type propagates 319 -- Program_Error." 320 end record; 321 322 procedure Read 323 (Stream : not null access Root_Stream_Type'Class; 324 Item : out Constant_Reference_Type); 325 326 for Constant_Reference_Type'Read use Read; 327 328 procedure Write 329 (Stream : not null access Root_Stream_Type'Class; 330 Item : Constant_Reference_Type); 331 332 for Constant_Reference_Type'Write use Write; 333 334 type Reference_Type (Element : not null access Element_Type) is record 335 Control : Reference_Control_Type := 336 raise Program_Error with "uninitialized reference"; 337 -- The RM says, "The default initialization of an object of 338 -- type Constant_Reference_Type or Reference_Type propagates 339 -- Program_Error." 340 end record; 341 342 procedure Write 343 (Stream : not null access Root_Stream_Type'Class; 344 Item : Reference_Type); 345 346 for Reference_Type'Write use Write; 347 348 procedure Read 349 (Stream : not null access Root_Stream_Type'Class; 350 Item : out Reference_Type); 351 352 for Reference_Type'Read use Read; 353 354 -- Three operations are used to optimize in the expansion of "for ... of" 355 -- loops: the Next(Cursor) procedure in the visible part, and the following 356 -- Pseudo_Reference and Get_Element_Access functions. See Exp_Ch5 for 357 -- details. 358 359 function Pseudo_Reference 360 (Container : aliased List'Class) return Reference_Control_Type; 361 pragma Inline (Pseudo_Reference); 362 -- Creates an object of type Reference_Control_Type pointing to the 363 -- container, and increments the Lock. Finalization of this object will 364 -- decrement the Lock. 365 366 type Element_Access is access all Element_Type with 367 Storage_Size => 0; 368 369 function Get_Element_Access 370 (Position : Cursor) return not null Element_Access; 371 -- Returns a pointer to the element designated by Position. 372 373 Empty_List : constant List := (Capacity => 0, others => <>); 374 375 No_Element : constant Cursor := Cursor'(null, 0); 376 377 type Iterator is new Limited_Controlled and 378 List_Iterator_Interfaces.Reversible_Iterator with 379 record 380 Container : List_Access; 381 Node : Count_Type; 382 end record 383 with Disable_Controlled => not T_Check; 384 385 overriding procedure Finalize (Object : in out Iterator); 386 387 overriding function First (Object : Iterator) return Cursor; 388 overriding function Last (Object : Iterator) return Cursor; 389 390 overriding function Next 391 (Object : Iterator; 392 Position : Cursor) return Cursor; 393 394 overriding function Previous 395 (Object : Iterator; 396 Position : Cursor) return Cursor; 397 398end Ada.Containers.Bounded_Doubly_Linked_Lists; 399