1------------------------------------------------------------------------------ 2-- -- 3-- GNAT LIBRARY COMPONENTS -- 4-- -- 5-- A D A . C O N T A I N E R S . D O U B L Y _ L I N K E D _ L I S T S -- 6-- -- 7-- S p e c -- 8-- -- 9-- Copyright (C) 2004-2013, 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 36private with Ada.Finalization; 37private with Ada.Streams; 38 39generic 40 type Element_Type is private; 41 42 with function "=" (Left, Right : Element_Type) 43 return Boolean is <>; 44 45package Ada.Containers.Doubly_Linked_Lists is 46 pragma Preelaborate; 47 pragma Remote_Types; 48 49 type List is tagged private 50 with 51 Constant_Indexing => Constant_Reference, 52 Variable_Indexing => Reference, 53 Default_Iterator => Iterate, 54 Iterator_Element => Element_Type; 55 56 pragma Preelaborable_Initialization (List); 57 58 type Cursor is private; 59 pragma Preelaborable_Initialization (Cursor); 60 61 Empty_List : constant List; 62 63 No_Element : constant Cursor; 64 65 function Has_Element (Position : Cursor) return Boolean; 66 67 package List_Iterator_Interfaces is new 68 Ada.Iterator_Interfaces (Cursor, Has_Element); 69 70 function "=" (Left, Right : List) return Boolean; 71 72 function Length (Container : List) return Count_Type; 73 74 function Is_Empty (Container : List) return Boolean; 75 76 procedure Clear (Container : in out List); 77 78 function Element (Position : Cursor) return Element_Type; 79 80 procedure Replace_Element 81 (Container : in out List; 82 Position : Cursor; 83 New_Item : Element_Type); 84 85 procedure Query_Element 86 (Position : Cursor; 87 Process : not null access procedure (Element : Element_Type)); 88 89 procedure Update_Element 90 (Container : in out List; 91 Position : Cursor; 92 Process : not null access procedure (Element : in out Element_Type)); 93 94 type Constant_Reference_Type 95 (Element : not null access constant Element_Type) is private 96 with 97 Implicit_Dereference => Element; 98 99 type Reference_Type 100 (Element : not null access Element_Type) is private 101 with 102 Implicit_Dereference => Element; 103 104 function Constant_Reference 105 (Container : aliased List; 106 Position : Cursor) return Constant_Reference_Type; 107 pragma Inline (Constant_Reference); 108 109 function Reference 110 (Container : aliased in out List; 111 Position : Cursor) return Reference_Type; 112 pragma Inline (Reference); 113 114 procedure Assign (Target : in out List; Source : List); 115 116 function Copy (Source : List) return List; 117 118 procedure Move 119 (Target : in out List; 120 Source : in out List); 121 122 procedure Insert 123 (Container : in out List; 124 Before : Cursor; 125 New_Item : Element_Type; 126 Count : Count_Type := 1); 127 128 procedure Insert 129 (Container : in out List; 130 Before : Cursor; 131 New_Item : Element_Type; 132 Position : out Cursor; 133 Count : Count_Type := 1); 134 135 procedure Insert 136 (Container : in out List; 137 Before : Cursor; 138 Position : out Cursor; 139 Count : Count_Type := 1); 140 141 procedure Prepend 142 (Container : in out List; 143 New_Item : Element_Type; 144 Count : Count_Type := 1); 145 146 procedure Append 147 (Container : in out List; 148 New_Item : Element_Type; 149 Count : Count_Type := 1); 150 151 procedure Delete 152 (Container : in out List; 153 Position : in out Cursor; 154 Count : Count_Type := 1); 155 156 procedure Delete_First 157 (Container : in out List; 158 Count : Count_Type := 1); 159 160 procedure Delete_Last 161 (Container : in out List; 162 Count : Count_Type := 1); 163 164 procedure Reverse_Elements (Container : in out List); 165 166 function Iterate (Container : List) 167 return List_Iterator_Interfaces.Reversible_Iterator'Class; 168 169 function Iterate (Container : List; Start : Cursor) 170 return List_Iterator_Interfaces.Reversible_Iterator'Class; 171 172 procedure Swap 173 (Container : in out List; 174 I, J : Cursor); 175 176 procedure Swap_Links 177 (Container : in out List; 178 I, J : Cursor); 179 180 procedure Splice 181 (Target : in out List; 182 Before : Cursor; 183 Source : in out List); 184 185 procedure Splice 186 (Target : in out List; 187 Before : Cursor; 188 Source : in out List; 189 Position : in out Cursor); 190 191 procedure Splice 192 (Container : in out List; 193 Before : Cursor; 194 Position : Cursor); 195 196 function First (Container : List) return Cursor; 197 198 function First_Element (Container : List) return Element_Type; 199 200 function Last (Container : List) return Cursor; 201 202 function Last_Element (Container : List) return Element_Type; 203 204 function Next (Position : Cursor) return Cursor; 205 206 procedure Next (Position : in out Cursor); 207 208 function Previous (Position : Cursor) return Cursor; 209 210 procedure Previous (Position : in out Cursor); 211 212 function Find 213 (Container : List; 214 Item : Element_Type; 215 Position : Cursor := No_Element) return Cursor; 216 217 function Reverse_Find 218 (Container : List; 219 Item : Element_Type; 220 Position : Cursor := No_Element) return Cursor; 221 222 function Contains 223 (Container : List; 224 Item : Element_Type) return Boolean; 225 226 procedure Iterate 227 (Container : List; 228 Process : not null access procedure (Position : Cursor)); 229 230 procedure Reverse_Iterate 231 (Container : List; 232 Process : not null access procedure (Position : Cursor)); 233 234 generic 235 with function "<" (Left, Right : Element_Type) return Boolean is <>; 236 package Generic_Sorting is 237 238 function Is_Sorted (Container : List) return Boolean; 239 240 procedure Sort (Container : in out List); 241 242 procedure Merge (Target, Source : in out List); 243 244 end Generic_Sorting; 245 246private 247 248 pragma Inline (Next); 249 pragma Inline (Previous); 250 251 type Node_Type; 252 type Node_Access is access Node_Type; 253 254 type Node_Type is 255 limited record 256 Element : aliased Element_Type; 257 Next : Node_Access; 258 Prev : Node_Access; 259 end record; 260 261 use Ada.Finalization; 262 use Ada.Streams; 263 264 type List is 265 new Controlled with record 266 First : Node_Access; 267 Last : Node_Access; 268 Length : Count_Type := 0; 269 Busy : Natural := 0; 270 Lock : Natural := 0; 271 end record; 272 273 overriding procedure Adjust (Container : in out List); 274 275 overriding procedure Finalize (Container : in out List) renames Clear; 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 293 record 294 Container : List_Access; 295 Node : Node_Access; 296 end record; 297 298 procedure Read 299 (Stream : not null access Root_Stream_Type'Class; 300 Item : out Cursor); 301 302 for Cursor'Read use Read; 303 304 procedure Write 305 (Stream : not null access Root_Stream_Type'Class; 306 Item : Cursor); 307 308 for Cursor'Write use Write; 309 310 type Reference_Control_Type is 311 new Controlled with record 312 Container : List_Access; 313 end record; 314 315 overriding procedure Adjust (Control : in out Reference_Control_Type); 316 pragma Inline (Adjust); 317 318 overriding procedure Finalize (Control : in out Reference_Control_Type); 319 pragma Inline (Finalize); 320 321 type Constant_Reference_Type 322 (Element : not null access constant Element_Type) is 323 record 324 Control : Reference_Control_Type; 325 end record; 326 327 procedure Write 328 (Stream : not null access Root_Stream_Type'Class; 329 Item : Constant_Reference_Type); 330 331 for Constant_Reference_Type'Write use Write; 332 333 procedure Read 334 (Stream : not null access Root_Stream_Type'Class; 335 Item : out Constant_Reference_Type); 336 337 for Constant_Reference_Type'Read use Read; 338 339 type Reference_Type 340 (Element : not null access Element_Type) is 341 record 342 Control : Reference_Control_Type; 343 end record; 344 345 procedure Write 346 (Stream : not null access Root_Stream_Type'Class; 347 Item : Reference_Type); 348 349 for Reference_Type'Write use Write; 350 351 procedure Read 352 (Stream : not null access Root_Stream_Type'Class; 353 Item : out Reference_Type); 354 355 for Reference_Type'Read use Read; 356 357 Empty_List : constant List := (Controlled with null, null, 0, 0, 0); 358 359 No_Element : constant Cursor := Cursor'(null, null); 360 361 type Iterator is new Limited_Controlled and 362 List_Iterator_Interfaces.Reversible_Iterator with 363 record 364 Container : List_Access; 365 Node : Node_Access; 366 end record; 367 368 overriding procedure Finalize (Object : in out Iterator); 369 370 overriding function First (Object : Iterator) return Cursor; 371 overriding function Last (Object : Iterator) return Cursor; 372 373 overriding function Next 374 (Object : Iterator; 375 Position : Cursor) return Cursor; 376 377 overriding function Previous 378 (Object : Iterator; 379 Position : Cursor) return Cursor; 380 381end Ada.Containers.Doubly_Linked_Lists; 382