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-2012, 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; 37 38generic 39 type Element_Type is private; 40 41 with function "=" (Left, Right : Element_Type) 42 return Boolean is <>; 43 44package Ada.Containers.Bounded_Doubly_Linked_Lists is 45 pragma Pure; 46 pragma Remote_Types; 47 48 type List (Capacity : Count_Type) is tagged private with 49 Constant_Indexing => Constant_Reference, 50 Variable_Indexing => Reference, 51 Default_Iterator => Iterate, 52 Iterator_Element => Element_Type; 53 54 pragma Preelaborable_Initialization (List); 55 56 type Cursor is private; 57 pragma Preelaborable_Initialization (Cursor); 58 59 Empty_List : constant List; 60 61 No_Element : constant Cursor; 62 63 function Has_Element (Position : Cursor) return Boolean; 64 65 package List_Iterator_Interfaces is new 66 Ada.Iterator_Interfaces (Cursor, Has_Element); 67 68 function "=" (Left, Right : List) return Boolean; 69 70 function Length (Container : List) return Count_Type; 71 72 function Is_Empty (Container : List) return Boolean; 73 74 procedure Clear (Container : in out List); 75 76 function Element (Position : Cursor) return Element_Type; 77 78 procedure Replace_Element 79 (Container : in out List; 80 Position : Cursor; 81 New_Item : Element_Type); 82 83 procedure Query_Element 84 (Position : Cursor; 85 Process : not null access procedure (Element : Element_Type)); 86 87 procedure Update_Element 88 (Container : in out List; 89 Position : Cursor; 90 Process : not null access procedure (Element : in out Element_Type)); 91 92 type Constant_Reference_Type 93 (Element : not null access constant Element_Type) is private 94 with 95 Implicit_Dereference => Element; 96 97 type Reference_Type 98 (Element : not null access Element_Type) is private 99 with 100 Implicit_Dereference => Element; 101 102 function Constant_Reference 103 (Container : aliased List; 104 Position : Cursor) return Constant_Reference_Type; 105 106 function Reference 107 (Container : aliased in out List; 108 Position : Cursor) return Reference_Type; 109 110 procedure Assign (Target : in out List; Source : List); 111 112 function Copy (Source : List; Capacity : Count_Type := 0) return List; 113 114 procedure Move 115 (Target : in out List; 116 Source : in out List); 117 118 procedure Insert 119 (Container : in out List; 120 Before : Cursor; 121 New_Item : Element_Type; 122 Count : Count_Type := 1); 123 124 procedure Insert 125 (Container : in out List; 126 Before : Cursor; 127 New_Item : Element_Type; 128 Position : out Cursor; 129 Count : Count_Type := 1); 130 131 procedure Insert 132 (Container : in out List; 133 Before : Cursor; 134 Position : out Cursor; 135 Count : Count_Type := 1); 136 137 procedure Prepend 138 (Container : in out List; 139 New_Item : Element_Type; 140 Count : Count_Type := 1); 141 142 procedure Append 143 (Container : in out List; 144 New_Item : Element_Type; 145 Count : Count_Type := 1); 146 147 procedure Delete 148 (Container : in out List; 149 Position : in out Cursor; 150 Count : Count_Type := 1); 151 152 procedure Delete_First 153 (Container : in out List; 154 Count : Count_Type := 1); 155 156 procedure Delete_Last 157 (Container : in out List; 158 Count : Count_Type := 1); 159 160 procedure Reverse_Elements (Container : in out List); 161 162 function Iterate 163 (Container : List) 164 return List_Iterator_Interfaces.Reversible_Iterator'class; 165 166 function Iterate 167 (Container : List; 168 Start : Cursor) 169 return List_Iterator_Interfaces.Reversible_Iterator'class; 170 171 procedure Swap 172 (Container : in out List; 173 I, J : Cursor); 174 175 procedure Swap_Links 176 (Container : in out List; 177 I, J : Cursor); 178 179 procedure Splice 180 (Target : in out List; 181 Before : Cursor; 182 Source : in out List); 183 184 procedure Splice 185 (Target : in out List; 186 Before : Cursor; 187 Source : in out List; 188 Position : in out Cursor); 189 190 procedure Splice 191 (Container : in out List; 192 Before : Cursor; 193 Position : Cursor); 194 195 function First (Container : List) return Cursor; 196 197 function First_Element (Container : List) return Element_Type; 198 199 function Last (Container : List) return Cursor; 200 201 function Last_Element (Container : List) return Element_Type; 202 203 function Next (Position : Cursor) return Cursor; 204 205 procedure Next (Position : in out Cursor); 206 207 function Previous (Position : Cursor) return Cursor; 208 209 procedure Previous (Position : in out Cursor); 210 211 function Find 212 (Container : List; 213 Item : Element_Type; 214 Position : Cursor := No_Element) return Cursor; 215 216 function Reverse_Find 217 (Container : List; 218 Item : Element_Type; 219 Position : Cursor := No_Element) return Cursor; 220 221 function Contains 222 (Container : List; 223 Item : Element_Type) return Boolean; 224 225 procedure Iterate 226 (Container : List; 227 Process : not null access procedure (Position : Cursor)); 228 229 procedure Reverse_Iterate 230 (Container : List; 231 Process : not null access procedure (Position : Cursor)); 232 233 generic 234 with function "<" (Left, Right : Element_Type) return Boolean is <>; 235 package Generic_Sorting is 236 237 function Is_Sorted (Container : List) return Boolean; 238 239 procedure Sort (Container : in out List); 240 241 procedure Merge (Target, Source : in out List); 242 243 end Generic_Sorting; 244 245private 246 247 pragma Inline (Next); 248 pragma Inline (Previous); 249 250 use Ada.Streams; 251 252 type Node_Type is record 253 Prev : Count_Type'Base; 254 Next : Count_Type; 255 Element : aliased Element_Type; 256 end record; 257 258 type Node_Array is array (Count_Type range <>) of Node_Type; 259 260 type List (Capacity : Count_Type) is tagged record 261 Nodes : Node_Array (1 .. Capacity) := (others => <>); 262 Free : Count_Type'Base := -1; 263 First : Count_Type := 0; 264 Last : Count_Type := 0; 265 Length : Count_Type := 0; 266 Busy : Natural := 0; 267 Lock : Natural := 0; 268 end record; 269 270 procedure Read 271 (Stream : not null access Root_Stream_Type'Class; 272 Item : out List); 273 274 for List'Read use Read; 275 276 procedure Write 277 (Stream : not null access Root_Stream_Type'Class; 278 Item : List); 279 280 for List'Write use Write; 281 282 type List_Access is access all List; 283 for List_Access'Storage_Size use 0; 284 285 type Cursor is 286 record 287 Container : List_Access; 288 Node : Count_Type := 0; 289 end record; 290 291 procedure Read 292 (Stream : not null access Root_Stream_Type'Class; 293 Item : out Cursor); 294 295 for Cursor'Read use Read; 296 297 procedure Write 298 (Stream : not null access Root_Stream_Type'Class; 299 Item : Cursor); 300 301 for Cursor'Write use Write; 302 303 type Constant_Reference_Type 304 (Element : not null access constant Element_Type) is null record; 305 306 procedure Write 307 (Stream : not null access Root_Stream_Type'Class; 308 Item : Constant_Reference_Type); 309 310 for Constant_Reference_Type'Write use Write; 311 312 procedure Read 313 (Stream : not null access Root_Stream_Type'Class; 314 Item : out Constant_Reference_Type); 315 316 for Constant_Reference_Type'Read use Read; 317 318 type Reference_Type 319 (Element : not null access Element_Type) is null record; 320 321 procedure Write 322 (Stream : not null access Root_Stream_Type'Class; 323 Item : Reference_Type); 324 325 for Reference_Type'Write use Write; 326 327 procedure Read 328 (Stream : not null access Root_Stream_Type'Class; 329 Item : out Reference_Type); 330 331 for Reference_Type'Read use Read; 332 333 Empty_List : constant List := (Capacity => 0, others => <>); 334 335 No_Element : constant Cursor := Cursor'(null, 0); 336 337end Ada.Containers.Bounded_Doubly_Linked_Lists; 338