1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- A D A . C O N T A I N E R S . O R D E R E D _ M A P S --
9 -- Copyright (C) 2004-2023, Free Software Foundation, Inc. --
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. --
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. --
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. --
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/>. --
31 -- This unit was originally developed by Matthew J Heaney. --
32 ------------------------------------------------------------------------------
34 with Ada
.Iterator_Interfaces
;
36 private with Ada
.Containers
.Red_Black_Trees
;
37 private with Ada
.Finalization
;
38 private with Ada
.Streams
;
39 private with Ada
.Strings
.Text_Buffers
;
42 type Key_Type
is private;
43 type Element_Type
is private;
45 with function "<" (Left
, Right
: Key_Type
) return Boolean is <>;
46 with function "=" (Left
, Right
: Element_Type
) return Boolean is <>;
48 package Ada
.Containers
.Ordered_Maps
with
51 pragma Annotate
(CodePeer
, Skip_Analysis
);
55 function Equivalent_Keys
(Left
, Right
: Key_Type
) return Boolean;
57 type Map
is tagged private with
58 Constant_Indexing
=> Constant_Reference
,
59 Variable_Indexing
=> Reference
,
60 Default_Iterator
=> Iterate
,
61 Iterator_Element
=> Element_Type
,
62 Aggregate
=> (Empty
=> Empty
,
64 pragma Preelaborable_Initialization
(Map
);
66 type Cursor
is private;
67 pragma Preelaborable_Initialization
(Cursor
);
69 Empty_Map
: constant Map
;
71 function Empty
return Map
;
72 pragma Ada_2022
(Empty
);
74 No_Element
: constant Cursor
;
76 function Has_Element
(Position
: Cursor
) return Boolean;
78 package Map_Iterator_Interfaces
is new
79 Ada
.Iterator_Interfaces
(Cursor
, Has_Element
);
81 function "=" (Left
, Right
: Map
) return Boolean;
83 function Length
(Container
: Map
) return Count_Type
;
85 function Is_Empty
(Container
: Map
) return Boolean;
87 procedure Clear
(Container
: in out Map
);
89 function Key
(Position
: Cursor
) return Key_Type
;
91 function Element
(Position
: Cursor
) return Element_Type
;
93 procedure Replace_Element
94 (Container
: in out Map
;
96 New_Item
: Element_Type
);
98 procedure Query_Element
100 Process
: not null access
101 procedure (Key
: Key_Type
; Element
: Element_Type
));
103 procedure Update_Element
104 (Container
: in out Map
;
106 Process
: not null access
107 procedure (Key
: Key_Type
; Element
: in out Element_Type
));
109 type Constant_Reference_Type
110 (Element
: not null access constant Element_Type
) is private
112 Implicit_Dereference
=> Element
;
114 type Reference_Type
(Element
: not null access Element_Type
) is private
116 Implicit_Dereference
=> Element
;
118 function Constant_Reference
119 (Container
: aliased Map
;
120 Position
: Cursor
) return Constant_Reference_Type
;
121 pragma Inline
(Constant_Reference
);
124 (Container
: aliased in out Map
;
125 Position
: Cursor
) return Reference_Type
;
126 pragma Inline
(Reference
);
128 function Constant_Reference
129 (Container
: aliased Map
;
130 Key
: Key_Type
) return Constant_Reference_Type
;
131 pragma Inline
(Constant_Reference
);
134 (Container
: aliased in out Map
;
135 Key
: Key_Type
) return Reference_Type
;
136 pragma Inline
(Reference
);
138 procedure Assign
(Target
: in out Map
; Source
: Map
);
140 function Copy
(Source
: Map
) return Map
;
142 procedure Move
(Target
: in out Map
; Source
: in out Map
);
145 (Container
: in out Map
;
147 New_Item
: Element_Type
;
148 Position
: out Cursor
;
149 Inserted
: out Boolean);
152 (Container
: in out Map
;
154 Position
: out Cursor
;
155 Inserted
: out Boolean);
158 (Container
: in out Map
;
160 New_Item
: Element_Type
);
163 (Container
: in out Map
;
165 New_Item
: Element_Type
);
168 (Container
: in out Map
;
170 New_Item
: Element_Type
);
172 procedure Exclude
(Container
: in out Map
; Key
: Key_Type
);
174 procedure Delete
(Container
: in out Map
; Key
: Key_Type
);
176 procedure Delete
(Container
: in out Map
; Position
: in out Cursor
);
178 procedure Delete_First
(Container
: in out Map
);
180 procedure Delete_Last
(Container
: in out Map
);
182 function First
(Container
: Map
) return Cursor
;
184 function First_Element
(Container
: Map
) return Element_Type
;
186 function First_Key
(Container
: Map
) return Key_Type
;
188 function Last
(Container
: Map
) return Cursor
;
190 function Last_Element
(Container
: Map
) return Element_Type
;
192 function Last_Key
(Container
: Map
) return Key_Type
;
194 function Next
(Position
: Cursor
) return Cursor
;
196 procedure Next
(Position
: in out Cursor
);
198 function Previous
(Position
: Cursor
) return Cursor
;
200 procedure Previous
(Position
: in out Cursor
);
202 function Find
(Container
: Map
; Key
: Key_Type
) return Cursor
;
204 function Element
(Container
: Map
; Key
: Key_Type
) return Element_Type
;
206 function Floor
(Container
: Map
; Key
: Key_Type
) return Cursor
;
208 function Ceiling
(Container
: Map
; Key
: Key_Type
) return Cursor
;
210 function Contains
(Container
: Map
; Key
: Key_Type
) return Boolean;
212 function "<" (Left
, Right
: Cursor
) return Boolean;
214 function ">" (Left
, Right
: Cursor
) return Boolean;
216 function "<" (Left
: Cursor
; Right
: Key_Type
) return Boolean;
218 function ">" (Left
: Cursor
; Right
: Key_Type
) return Boolean;
220 function "<" (Left
: Key_Type
; Right
: Cursor
) return Boolean;
222 function ">" (Left
: Key_Type
; Right
: Cursor
) return Boolean;
226 Process
: not null access procedure (Position
: Cursor
));
228 procedure Reverse_Iterate
230 Process
: not null access procedure (Position
: Cursor
));
232 -- The map container supports iteration in both the forward and reverse
233 -- directions, hence these constructor functions return an object that
234 -- supports the Reversible_Iterator interface.
238 return Map_Iterator_Interfaces
.Reversible_Iterator
'class;
243 return Map_Iterator_Interfaces
.Reversible_Iterator
'class;
247 pragma Inline
(Next
);
248 pragma Inline
(Previous
);
251 type Node_Access
is access Node_Type
;
253 type Node_Type
is limited record
254 Parent
: Node_Access
;
257 Color
: Red_Black_Trees
.Color_Type
:= Red_Black_Trees
.Red
;
259 Element
: aliased Element_Type
;
262 package Tree_Types
is
263 new Red_Black_Trees
.Generic_Tree_Types
(Node_Type
, Node_Access
);
265 type Map
is new Ada
.Finalization
.Controlled
with record
266 Tree
: Tree_Types
.Tree_Type
;
267 end record with Put_Image
=> Put_Image
;
270 (S
: in out Ada
.Strings
.Text_Buffers
.Root_Buffer_Type
'Class; V
: Map
);
272 overriding
procedure Adjust
(Container
: in out Map
);
274 overriding
procedure Finalize
(Container
: in out Map
) renames Clear
;
277 use Tree_Types
, Tree_Types
.Implementation
;
278 use Ada
.Finalization
;
282 (Stream
: not null access Root_Stream_Type
'Class;
285 for Map
'Write use Write
;
288 (Stream
: not null access Root_Stream_Type
'Class;
289 Container
: out Map
);
291 for Map
'Read use Read
;
293 type Map_Access
is access all Map
;
294 for Map_Access
'Storage_Size use 0;
296 type Cursor
is record
297 Container
: Map_Access
;
302 (Stream
: not null access Root_Stream_Type
'Class;
305 for Cursor
'Write use Write
;
308 (Stream
: not null access Root_Stream_Type
'Class;
311 for Cursor
'Read use Read
;
313 subtype Reference_Control_Type
is Implementation
.Reference_Control_Type
;
314 -- It is necessary to rename this here, so that the compiler can find it
316 type Constant_Reference_Type
317 (Element
: not null access constant Element_Type
) is
319 Control
: Reference_Control_Type
:=
320 raise Program_Error
with "uninitialized reference";
321 -- The RM says, "The default initialization of an object of
322 -- type Constant_Reference_Type or Reference_Type propagates
327 (Stream
: not null access Root_Stream_Type
'Class;
328 Item
: out Constant_Reference_Type
);
330 for Constant_Reference_Type
'Read use Read
;
333 (Stream
: not null access Root_Stream_Type
'Class;
334 Item
: Constant_Reference_Type
);
336 for Constant_Reference_Type
'Write use Write
;
339 (Element
: not null access Element_Type
) is
341 Control
: Reference_Control_Type
:=
342 raise Program_Error
with "uninitialized reference";
343 -- The RM says, "The default initialization of an object of
344 -- type Constant_Reference_Type or Reference_Type propagates
349 (Stream
: not null access Root_Stream_Type
'Class;
350 Item
: out Reference_Type
);
352 for Reference_Type
'Read use Read
;
355 (Stream
: not null access Root_Stream_Type
'Class;
356 Item
: Reference_Type
);
358 for Reference_Type
'Write use Write
;
360 -- See Ada.Containers.Vectors for documentation on the following
362 procedure _Next
(Position
: in out Cursor
) renames Next
;
363 procedure _Previous
(Position
: in out Cursor
) renames Previous
;
365 function Pseudo_Reference
366 (Container
: aliased Map
'Class) return Reference_Control_Type
;
367 pragma Inline
(Pseudo_Reference
);
368 -- Creates an object of type Reference_Control_Type pointing to the
369 -- container, and increments the Lock. Finalization of this object will
370 -- decrement the Lock.
372 type Element_Access
is access all Element_Type
with
375 function Get_Element_Access
376 (Position
: Cursor
) return not null Element_Access
;
377 -- Returns a pointer to the element designated by Position.
379 Empty_Map
: constant Map
:= (Controlled
with others => <>);
380 function Empty
return Map
is (Empty_Map
);
382 No_Element
: constant Cursor
:= Cursor
'(null, null);
384 type Iterator is new Limited_Controlled and
385 Map_Iterator_Interfaces.Reversible_Iterator with
387 Container : Map_Access;
390 with Disable_Controlled => not T_Check;
392 overriding procedure Finalize (Object : in out Iterator);
394 overriding function First (Object : Iterator) return Cursor;
395 overriding function Last (Object : Iterator) return Cursor;
397 overriding function Next
399 Position : Cursor) return Cursor;
401 overriding function Previous
403 Position : Cursor) return Cursor;
405 end Ada.Containers.Ordered_Maps;