1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- A D A . C O N T A I N E R S . --
6 -- I N D E F I N I T E _ O R D E R E D _ M A P S --
10 -- Copyright (C) 2004-2005 Free Software Foundation, Inc. --
12 -- This specification is derived from the Ada Reference Manual for use with --
13 -- GNAT. The copyright notice above, and the license provisions that follow --
14 -- apply solely to the contents of the part following the private keyword. --
16 -- GNAT is free software; you can redistribute it and/or modify it under --
17 -- terms of the GNU General Public License as published by the Free Soft- --
18 -- ware Foundation; either version 2, or (at your option) any later ver- --
19 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
20 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
21 -- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License --
22 -- for more details. You should have received a copy of the GNU General --
23 -- Public License distributed with GNAT; see file COPYING. If not, write --
24 -- to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, --
25 -- MA 02111-1307, USA. --
27 -- As a special exception, if other files instantiate generics from this --
28 -- unit, or you link this unit with other files to produce an executable, --
29 -- this unit does not by itself cause the resulting executable to be --
30 -- covered by the GNU General Public License. This exception does not --
31 -- however invalidate any other reasons why the executable file might be --
32 -- covered by the GNU Public License. --
34 -- This unit was originally developed by Matthew J Heaney. --
35 ------------------------------------------------------------------------------
37 with Ada.Unchecked_Deallocation;
39 with Ada.Containers.Red_Black_Trees.Generic_Operations;
40 pragma Elaborate_All (Ada.Containers.Red_Black_Trees.Generic_Operations);
42 with Ada.Containers.Red_Black_Trees.Generic_Keys;
43 pragma Elaborate_All (Ada.Containers.Red_Black_Trees.Generic_Keys);
45 package body Ada.Containers.Indefinite_Ordered_Maps is
47 -----------------------------
48 -- Node Access Subprograms --
49 -----------------------------
51 -- These subprograms provide a functional interface to access fields
52 -- of a node, and a procedural interface for modifying these values.
54 function Color (Node : Node_Access) return Color_Type;
55 pragma Inline (Color);
57 function Left (Node : Node_Access) return Node_Access;
60 function Parent (Node : Node_Access) return Node_Access;
61 pragma Inline (Parent);
63 function Right (Node : Node_Access) return Node_Access;
64 pragma Inline (Right);
66 procedure Set_Parent (Node : Node_Access; Parent : Node_Access);
67 pragma Inline (Set_Parent);
69 procedure Set_Left (Node : Node_Access; Left : Node_Access);
70 pragma Inline (Set_Left);
72 procedure Set_Right (Node : Node_Access; Right : Node_Access);
73 pragma Inline (Set_Right);
75 procedure Set_Color (Node : Node_Access; Color : Color_Type);
76 pragma Inline (Set_Color);
78 -----------------------
79 -- Local Subprograms --
80 -----------------------
82 function Copy_Node (Source : Node_Access) return Node_Access;
83 pragma Inline (Copy_Node);
85 procedure Free (X : in out Node_Access);
87 function Is_Equal_Node_Node
88 (L, R : Node_Access) return Boolean;
89 pragma Inline (Is_Equal_Node_Node);
91 function Is_Greater_Key_Node
93 Right : Node_Access) return Boolean;
94 pragma Inline (Is_Greater_Key_Node);
96 function Is_Less_Key_Node
98 Right : Node_Access) return Boolean;
99 pragma Inline (Is_Less_Key_Node);
101 --------------------------
102 -- Local Instantiations --
103 --------------------------
105 package Tree_Operations is
106 new Red_Black_Trees.Generic_Operations (Tree_Types);
108 procedure Delete_Tree is
109 new Tree_Operations.Generic_Delete_Tree (Free);
111 function Copy_Tree is
112 new Tree_Operations.Generic_Copy_Tree (Copy_Node, Delete_Tree);
117 new Red_Black_Trees.Generic_Keys
118 (Tree_Operations => Tree_Operations,
119 Key_Type => Key_Type,
120 Is_Less_Key_Node => Is_Less_Key_Node,
121 Is_Greater_Key_Node => Is_Greater_Key_Node);
123 procedure Free_Key is
124 new Ada.Unchecked_Deallocation (Key_Type, Key_Access);
126 procedure Free_Element is
127 new Ada.Unchecked_Deallocation (Element_Type, Element_Access);
130 new Tree_Operations.Generic_Equal (Is_Equal_Node_Node);
136 function "<" (Left, Right : Cursor) return Boolean is
138 return Left.Node.Key.all < Right.Node.Key.all;
141 function "<" (Left : Cursor; Right : Key_Type) return Boolean is
143 return Left.Node.Key.all < Right;
146 function "<" (Left : Key_Type; Right : Cursor) return Boolean is
148 return Left < Right.Node.Key.all;
155 function "=" (Left, Right : Map) return Boolean is
157 return Is_Equal (Left.Tree, Right.Tree);
164 function ">" (Left, Right : Cursor) return Boolean is
166 return Right.Node.Key.all < Left.Node.Key.all;
169 function ">" (Left : Cursor; Right : Key_Type) return Boolean is
171 return Right < Left.Node.Key.all;
174 function ">" (Left : Key_Type; Right : Cursor) return Boolean is
176 return Right.Node.Key.all < Left;
184 new Tree_Operations.Generic_Adjust (Copy_Tree);
186 procedure Adjust (Container : in out Map) is
188 Adjust (Container.Tree);
195 function Ceiling (Container : Map; Key : Key_Type) return Cursor is
196 Node : constant Node_Access := Key_Ops.Ceiling (Container.Tree, Key);
201 return Cursor'(Container'Unrestricted_Access, Node);
210 new Tree_Operations.Generic_Clear (Delete_Tree);
212 procedure Clear (Container : in out Map) is
214 Clear (Container.Tree);
221 function Color (Node : Node_Access) return Color_Type is
230 function Contains (Container : Map; Key : Key_Type) return Boolean is
232 return Find (Container, Key) /= No_Element;
239 function Copy_Node (Source : Node_Access) return Node_Access is
240 K : Key_Access := new Key_Type'(Source.Key.all);
243 E := new Element_Type'(Source.Element.all);
245 return new Node_Type'(Parent => null,
248 Color => Source.Color,
263 (Container : in out Map;
264 Position : in out Cursor)
267 if Position.Node = null then
268 raise Constraint_Error;
271 if Position.Container /= Map_Access'(Container'Unrestricted_Access) then
275 Delete_Node_Sans_Free (Container.Tree, Position.Node);
276 Free (Position.Node);
278 Position.Container := null;
281 procedure Delete (Container : in out Map; Key : Key_Type) is
282 X : Node_Access := Key_Ops.Find (Container.Tree, Key);
285 raise Constraint_Error;
287 Delete_Node_Sans_Free (Container.Tree, X);
296 procedure Delete_First (Container : in out Map) is
297 X : Node_Access := Container.Tree.First;
300 Tree_Operations.Delete_Node_Sans_Free (Container.Tree, X);
309 procedure Delete_Last (Container : in out Map) is
310 X : Node_Access := Container.Tree.Last;
313 Tree_Operations.Delete_Node_Sans_Free (Container.Tree, X);
322 function Element (Position : Cursor) return Element_Type is
324 return Position.Node.Element.all;
327 function Element (Container : Map; Key : Key_Type) return Element_Type is
328 Node : constant Node_Access := Key_Ops.Find (Container.Tree, Key);
330 return Node.Element.all;
337 procedure Exclude (Container : in out Map; Key : Key_Type) is
338 X : Node_Access := Key_Ops.Find (Container.Tree, Key);
342 Delete_Node_Sans_Free (Container.Tree, X);
351 function Find (Container : Map; Key : Key_Type) return Cursor is
352 Node : constant Node_Access := Key_Ops.Find (Container.Tree, Key);
357 return Cursor'(Container'Unrestricted_Access, Node);
365 function First (Container : Map) return Cursor is
367 if Container.Tree.First = null then
370 return Cursor'(Container'Unrestricted_Access, Container.Tree.First);
378 function First_Element (Container : Map) return Element_Type is
380 return Container.Tree.First.Element.all;
387 function First_Key (Container : Map) return Key_Type is
389 return Container.Tree.First.Key.all;
396 function Floor (Container : Map; Key : Key_Type) return Cursor is
397 Node : constant Node_Access := Key_Ops.Floor (Container.Tree, Key);
402 return Cursor'(Container'Unrestricted_Access, Node);
410 procedure Free (X : in out Node_Access) is
411 procedure Deallocate is
412 new Ada.Unchecked_Deallocation (Node_Type, Node_Access);
425 Free_Element (X.Element);
436 Free_Element (X.Element);
452 function Has_Element (Position : Cursor) return Boolean is
454 return Position /= No_Element;
462 (Container : in out Map;
464 New_Item : Element_Type)
473 Insert (Container, Key, New_Item, Position, Inserted);
476 if Container.Tree.Lock > 0 then
480 K := Position.Node.Key;
481 E := Position.Node.Element;
483 Position.Node.Key := new Key_Type'(Key);
486 Position.Node.Element := new Element_Type'(New_Item);
503 (Container : in out Map;
505 New_Item : Element_Type;
506 Position : out Cursor;
507 Inserted : out Boolean)
509 function New_Node return Node_Access;
510 pragma Inline (New_Node);
512 procedure Insert_Post is
513 new Key_Ops.Generic_Insert_Post (New_Node);
515 procedure Insert_Sans_Hint is
516 new Key_Ops.Generic_Conditional_Insert (Insert_Post);
522 function New_Node return Node_Access is
523 Node : Node_Access := new Node_Type;
526 Node.Key := new Key_Type'(Key);
527 Node.Element := new Element_Type'(New_Item);
533 -- On exception, deallocate key and elem
535 Free (Node); -- Note that Free deallocates key and elem too
539 -- Start of processing for Insert
548 Position.Container := Container'Unrestricted_Access;
552 (Container : in out Map;
554 New_Item : Element_Type)
561 Insert (Container, Key, New_Item, Position, Inserted);
564 raise Constraint_Error;
572 function Is_Empty (Container : Map) return Boolean is
574 return Container.Tree.Length = 0;
577 ------------------------
578 -- Is_Equal_Node_Node --
579 ------------------------
581 function Is_Equal_Node_Node
582 (L, R : Node_Access) return Boolean is
584 if L.Key.all < R.Key.all then
587 elsif R.Key.all < L.Key.all then
591 return L.Element.all = R.Element.all;
593 end Is_Equal_Node_Node;
595 -------------------------
596 -- Is_Greater_Key_Node --
597 -------------------------
599 function Is_Greater_Key_Node
601 Right : Node_Access) return Boolean
604 -- k > node same as node < k
606 return Right.Key.all < Left;
607 end Is_Greater_Key_Node;
609 ----------------------
610 -- Is_Less_Key_Node --
611 ----------------------
613 function Is_Less_Key_Node
615 Right : Node_Access) return Boolean is
617 return Left < Right.Key.all;
618 end Is_Less_Key_Node;
626 Process : not null access procedure (Position : Cursor))
628 procedure Process_Node (Node : Node_Access);
629 pragma Inline (Process_Node);
631 procedure Local_Iterate is
632 new Tree_Operations.Generic_Iteration (Process_Node);
638 procedure Process_Node (Node : Node_Access) is
640 Process (Cursor'(Container'Unrestricted_Access, Node));
643 B : Natural renames Container.Tree'Unrestricted_Access.all.Busy;
645 -- Start of processing for Iterate
651 Local_Iterate (Container.Tree);
665 function Key (Position : Cursor) return Key_Type is
667 return Position.Node.Key.all;
674 function Last (Container : Map) return Cursor is
676 if Container.Tree.Last = null then
679 return Cursor'(Container'Unrestricted_Access, Container.Tree.Last);
687 function Last_Element (Container : Map) return Element_Type is
689 return Container.Tree.Last.Element.all;
696 function Last_Key (Container : Map) return Key_Type is
698 return Container.Tree.Last.Key.all;
705 function Left (Node : Node_Access) return Node_Access is
714 function Length (Container : Map) return Count_Type is
716 return Container.Tree.Length;
724 new Tree_Operations.Generic_Move (Clear);
726 procedure Move (Target : in out Map; Source : in out Map) is
728 Move (Target => Target.Tree, Source => Source.Tree);
735 function Next (Position : Cursor) return Cursor is
737 if Position = No_Element then
742 Node : constant Node_Access := Tree_Operations.Next (Position.Node);
747 return Cursor'(Position.Container, Node);
752 procedure Next (Position : in out Cursor) is
754 Position := Next (Position);
761 function Parent (Node : Node_Access) return Node_Access is
770 function Previous (Position : Cursor) return Cursor is
772 if Position = No_Element then
777 Node : constant Node_Access :=
778 Tree_Operations.Previous (Position.Node);
784 return Cursor'(Position.Container, Node);
788 procedure Previous (Position : in out Cursor) is
790 Position := Previous (Position);
797 procedure Query_Element
799 Process : not null access procedure (Key : Key_Type;
800 Element : Element_Type))
802 K : Key_Type renames Position.Node.Key.all;
803 E : Element_Type renames Position.Node.Element.all;
805 T : Tree_Type renames Position.Container.Tree;
807 B : Natural renames T.Busy;
808 L : Natural renames T.Lock;
832 (Stream : access Root_Stream_Type'Class;
836 (Stream : access Root_Stream_Type'Class) return Node_Access;
837 pragma Inline (Read_Node);
840 new Tree_Operations.Generic_Read (Clear, Read_Node);
847 (Stream : access Root_Stream_Type'Class) return Node_Access
849 Node : Node_Access := new Node_Type;
851 Node.Key := new Key_Type'(Key_Type'Input (Stream));
852 Node.Element := new Element_Type'(Element_Type'Input (Stream));
856 Free (Node); -- Note that Free deallocates key and elem too
860 -- Start of processing for Read
863 Read (Stream, Container.Tree);
871 (Container : in out Map;
873 New_Item : Element_Type)
875 Node : constant Node_Access :=
876 Key_Ops.Find (Container.Tree, Key);
883 raise Constraint_Error;
886 if Container.Tree.Lock > 0 then
893 Node.Key := new Key_Type'(Key);
896 Node.Element := new Element_Type'(New_Item);
907 ---------------------
908 -- Replace_Element --
909 ---------------------
911 procedure Replace_Element (Position : Cursor; By : Element_Type) is
912 X : Element_Access := Position.Node.Element;
914 if Position.Container.Tree.Lock > 0 then
918 Position.Node.Element := new Element_Type'(By);
922 ---------------------
923 -- Reverse_Iterate --
924 ---------------------
926 procedure Reverse_Iterate
928 Process : not null access procedure (Position : Cursor))
930 procedure Process_Node (Node : Node_Access);
931 pragma Inline (Process_Node);
933 procedure Local_Reverse_Iterate is
934 new Tree_Operations.Generic_Reverse_Iteration (Process_Node);
940 procedure Process_Node (Node : Node_Access) is
942 Process (Cursor'(Container'Unrestricted_Access, Node));
945 B : Natural renames Container.Tree'Unrestricted_Access.all.Busy;
947 -- Start of processing for Reverse_Iterate
953 Local_Reverse_Iterate (Container.Tree);
967 function Right (Node : Node_Access) return Node_Access is
976 procedure Set_Color (Node : Node_Access; Color : Color_Type) is
985 procedure Set_Left (Node : Node_Access; Left : Node_Access) is
994 procedure Set_Parent (Node : Node_Access; Parent : Node_Access) is
996 Node.Parent := Parent;
1003 procedure Set_Right (Node : Node_Access; Right : Node_Access) is
1005 Node.Right := Right;
1008 --------------------
1009 -- Update_Element --
1010 --------------------
1012 procedure Update_Element
1014 Process : not null access procedure (Key : Key_Type;
1015 Element : in out Element_Type))
1017 K : Key_Type renames Position.Node.Key.all;
1018 E : Element_Type renames Position.Node.Element.all;
1020 T : Tree_Type renames Position.Container.Tree;
1022 B : Natural renames T.Busy;
1023 L : Natural renames T.Lock;
1047 (Stream : access Root_Stream_Type'Class;
1050 procedure Write_Node
1051 (Stream : access Root_Stream_Type'Class;
1052 Node : Node_Access);
1053 pragma Inline (Write_Node);
1056 new Tree_Operations.Generic_Write (Write_Node);
1062 procedure Write_Node
1063 (Stream : access Root_Stream_Type'Class;
1067 Key_Type'Output (Stream, Node.Key.all);
1068 Element_Type'Output (Stream, Node.Element.all);
1071 -- Start of processing for Write
1074 Write (Stream, Container.Tree);
1077 end Ada.Containers.Indefinite_Ordered_Maps;