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-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.Streams; 37private with Ada.Finalization; 38 39generic 40 type Element_Type is private; 41 42 with function "=" (Left, Right : Element_Type) 43 return Boolean is <>; 44 45package Ada.Containers.Bounded_Doubly_Linked_Lists is 46 pragma Pure; 47 pragma Remote_Types; 48 49 type List (Capacity : Count_Type) is tagged private with 50 Constant_Indexing => Constant_Reference, 51 Variable_Indexing => Reference, 52 Default_Iterator => Iterate, 53 Iterator_Element => Element_Type; 54 55 pragma Preelaborable_Initialization (List); 56 57 type Cursor is private; 58 pragma Preelaborable_Initialization (Cursor); 59 60 Empty_List : constant List; 61 62 No_Element : constant Cursor; 63 64 function Has_Element (Position : Cursor) return Boolean; 65 66 package List_Iterator_Interfaces is new 67 Ada.Iterator_Interfaces (Cursor, Has_Element); 68 69 function "=" (Left, Right : List) return Boolean; 70 71 function Length (Container : List) return Count_Type; 72 73 function Is_Empty (Container : List) return Boolean; 74 75 procedure Clear (Container : in out List); 76 77 function Element (Position : Cursor) return Element_Type; 78 79 procedure Replace_Element 80 (Container : in out List; 81 Position : Cursor; 82 New_Item : Element_Type); 83 84 procedure Query_Element 85 (Position : Cursor; 86 Process : not null access procedure (Element : Element_Type)); 87 88 procedure Update_Element 89 (Container : in out List; 90 Position : Cursor; 91 Process : not null access procedure (Element : in out Element_Type)); 92 93 type Constant_Reference_Type 94 (Element : not null access constant Element_Type) is private 95 with 96 Implicit_Dereference => Element; 97 98 type Reference_Type 99 (Element : not null access Element_Type) is private 100 with 101 Implicit_Dereference => Element; 102 103 function Constant_Reference 104 (Container : aliased List; 105 Position : Cursor) return Constant_Reference_Type; 106 107 function Reference 108 (Container : aliased in out List; 109 Position : Cursor) return Reference_Type; 110 111 procedure Assign (Target : in out List; Source : List); 112 113 function Copy (Source : List; Capacity : Count_Type := 0) return List; 114 115 procedure Move 116 (Target : in out List; 117 Source : in out List); 118 119 procedure Insert 120 (Container : in out List; 121 Before : Cursor; 122 New_Item : Element_Type; 123 Count : Count_Type := 1); 124 125 procedure Insert 126 (Container : in out List; 127 Before : Cursor; 128 New_Item : Element_Type; 129 Position : out Cursor; 130 Count : Count_Type := 1); 131 132 procedure Insert 133 (Container : in out List; 134 Before : Cursor; 135 Position : out Cursor; 136 Count : Count_Type := 1); 137 138 procedure Prepend 139 (Container : in out List; 140 New_Item : Element_Type; 141 Count : Count_Type := 1); 142 143 procedure Append 144 (Container : in out List; 145 New_Item : Element_Type; 146 Count : Count_Type := 1); 147 148 procedure Delete 149 (Container : in out List; 150 Position : in out Cursor; 151 Count : Count_Type := 1); 152 153 procedure Delete_First 154 (Container : in out List; 155 Count : Count_Type := 1); 156 157 procedure Delete_Last 158 (Container : in out List; 159 Count : Count_Type := 1); 160 161 procedure Reverse_Elements (Container : in out List); 162 163 function Iterate 164 (Container : List) 165 return List_Iterator_Interfaces.Reversible_Iterator'class; 166 167 function Iterate 168 (Container : List; 169 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 use Ada.Streams; 252 use Ada.Finalization; 253 254 type Node_Type is record 255 Prev : Count_Type'Base; 256 Next : Count_Type; 257 Element : aliased Element_Type; 258 end record; 259 260 type Node_Array is array (Count_Type range <>) of Node_Type; 261 262 type List (Capacity : Count_Type) is tagged record 263 Nodes : Node_Array (1 .. Capacity) := (others => <>); 264 Free : Count_Type'Base := -1; 265 First : Count_Type := 0; 266 Last : Count_Type := 0; 267 Length : Count_Type := 0; 268 Busy : Natural := 0; 269 Lock : Natural := 0; 270 end record; 271 272 procedure Read 273 (Stream : not null access Root_Stream_Type'Class; 274 Item : out List); 275 276 for List'Read use Read; 277 278 procedure Write 279 (Stream : not null access Root_Stream_Type'Class; 280 Item : List); 281 282 for List'Write use Write; 283 284 type List_Access is access all List; 285 for List_Access'Storage_Size use 0; 286 287 type Cursor is 288 record 289 Container : List_Access; 290 Node : Count_Type := 0; 291 end record; 292 293 procedure Read 294 (Stream : not null access Root_Stream_Type'Class; 295 Item : out Cursor); 296 297 for Cursor'Read use Read; 298 299 procedure Write 300 (Stream : not null access Root_Stream_Type'Class; 301 Item : Cursor); 302 303 for Cursor'Write use Write; 304 305 type Constant_Reference_Type 306 (Element : not null access constant Element_Type) is null record; 307 308 procedure Write 309 (Stream : not null access Root_Stream_Type'Class; 310 Item : Constant_Reference_Type); 311 312 for Constant_Reference_Type'Write use Write; 313 314 procedure Read 315 (Stream : not null access Root_Stream_Type'Class; 316 Item : out Constant_Reference_Type); 317 318 for Constant_Reference_Type'Read use Read; 319 320 type Reference_Type 321 (Element : not null access Element_Type) is null record; 322 323 procedure Write 324 (Stream : not null access Root_Stream_Type'Class; 325 Item : Reference_Type); 326 327 for Reference_Type'Write use Write; 328 329 procedure Read 330 (Stream : not null access Root_Stream_Type'Class; 331 Item : out Reference_Type); 332 333 for Reference_Type'Read use Read; 334 335 Empty_List : constant List := (Capacity => 0, others => <>); 336 337 No_Element : constant Cursor := Cursor'(null, 0); 338 339 type Iterator is new Limited_Controlled and 340 List_Iterator_Interfaces.Reversible_Iterator with 341 record 342 Container : List_Access; 343 Node : Count_Type; 344 end record; 345 346 overriding procedure Finalize (Object : in out Iterator); 347 348 overriding function First (Object : Iterator) return Cursor; 349 overriding function Last (Object : Iterator) return Cursor; 350 351 overriding function Next 352 (Object : Iterator; 353 Position : Cursor) return Cursor; 354 355 overriding function Previous 356 (Object : Iterator; 357 Position : Cursor) return Cursor; 358 359end Ada.Containers.Bounded_Doubly_Linked_Lists; 360