1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- ADA.CONTAINERS.INDEFINITE_ORDERED_SETS --
9 -- Copyright (C) 2004-2012, Free Software Foundation, Inc. --
11 -- GNAT is free software; you can redistribute it and/or modify it under --
12 -- terms of the GNU General Public License as published by the Free Soft- --
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
16 -- or FITNESS FOR A PARTICULAR PURPOSE. --
18 -- As a special exception under Section 7 of GPL version 3, you are granted --
19 -- additional permissions described in the GCC Runtime Library Exception, --
20 -- version 3.1, as published by the Free Software Foundation. --
22 -- You should have received a copy of the GNU General Public License and --
23 -- a copy of the GCC Runtime Library Exception along with this program; --
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
25 -- <http://www.gnu.org/licenses/>. --
27 -- This unit was originally developed by Matthew J Heaney. --
28 ------------------------------------------------------------------------------
30 with Ada.Containers.Red_Black_Trees.Generic_Operations;
31 pragma Elaborate_All (Ada.Containers.Red_Black_Trees.Generic_Operations);
33 with Ada.Containers.Red_Black_Trees.Generic_Keys;
34 pragma Elaborate_All (Ada.Containers.Red_Black_Trees.Generic_Keys);
36 with Ada.Containers.Red_Black_Trees.Generic_Set_Operations;
37 pragma Elaborate_All (Ada.Containers.Red_Black_Trees.Generic_Set_Operations);
39 with Ada.Unchecked_Deallocation;
41 with System; use type System.Address;
43 package body Ada.Containers.Indefinite_Ordered_Sets is
45 type Iterator is new Limited_Controlled and
46 Set_Iterator_Interfaces.Reversible_Iterator with
48 Container : Set_Access;
52 overriding procedure Finalize (Object : in out Iterator);
54 overriding function First (Object : Iterator) return Cursor;
55 overriding function Last (Object : Iterator) return Cursor;
57 overriding function Next
59 Position : Cursor) return Cursor;
61 overriding function Previous
63 Position : Cursor) return Cursor;
65 -----------------------
66 -- Local Subprograms --
67 -----------------------
69 function Color (Node : Node_Access) return Color_Type;
70 pragma Inline (Color);
72 function Copy_Node (Source : Node_Access) return Node_Access;
73 pragma Inline (Copy_Node);
75 procedure Free (X : in out Node_Access);
77 procedure Insert_Sans_Hint
78 (Tree : in out Tree_Type;
79 New_Item : Element_Type;
80 Node : out Node_Access;
81 Inserted : out Boolean);
83 procedure Insert_With_Hint
84 (Dst_Tree : in out Tree_Type;
85 Dst_Hint : Node_Access;
86 Src_Node : Node_Access;
87 Dst_Node : out Node_Access);
89 function Is_Greater_Element_Node
91 Right : Node_Access) return Boolean;
92 pragma Inline (Is_Greater_Element_Node);
94 function Is_Less_Element_Node
96 Right : Node_Access) return Boolean;
97 pragma Inline (Is_Less_Element_Node);
99 function Is_Less_Node_Node (L, R : Node_Access) return Boolean;
100 pragma Inline (Is_Less_Node_Node);
102 function Left (Node : Node_Access) return Node_Access;
103 pragma Inline (Left);
105 function Parent (Node : Node_Access) return Node_Access;
106 pragma Inline (Parent);
108 procedure Replace_Element
109 (Tree : in out Tree_Type;
111 Item : Element_Type);
113 function Right (Node : Node_Access) return Node_Access;
114 pragma Inline (Right);
116 procedure Set_Color (Node : Node_Access; Color : Color_Type);
117 pragma Inline (Set_Color);
119 procedure Set_Left (Node : Node_Access; Left : Node_Access);
120 pragma Inline (Set_Left);
122 procedure Set_Parent (Node : Node_Access; Parent : Node_Access);
123 pragma Inline (Set_Parent);
125 procedure Set_Right (Node : Node_Access; Right : Node_Access);
126 pragma Inline (Set_Right);
128 --------------------------
129 -- Local Instantiations --
130 --------------------------
132 procedure Free_Element is
133 new Ada.Unchecked_Deallocation (Element_Type, Element_Access);
135 package Tree_Operations is
136 new Red_Black_Trees.Generic_Operations (Tree_Types);
138 procedure Delete_Tree is
139 new Tree_Operations.Generic_Delete_Tree (Free);
141 function Copy_Tree is
142 new Tree_Operations.Generic_Copy_Tree (Copy_Node, Delete_Tree);
146 package Element_Keys is
147 new Red_Black_Trees.Generic_Keys
148 (Tree_Operations => Tree_Operations,
149 Key_Type => Element_Type,
150 Is_Less_Key_Node => Is_Less_Element_Node,
151 Is_Greater_Key_Node => Is_Greater_Element_Node);
154 new Generic_Set_Operations
155 (Tree_Operations => Tree_Operations,
156 Insert_With_Hint => Insert_With_Hint,
157 Copy_Tree => Copy_Tree,
158 Delete_Tree => Delete_Tree,
159 Is_Less => Is_Less_Node_Node,
166 function "<" (Left, Right : Cursor) return Boolean is
168 if Left.Node = null then
169 raise Constraint_Error with "Left cursor equals No_Element";
172 if Right.Node = null then
173 raise Constraint_Error with "Right cursor equals No_Element";
176 if Left.Node.Element = null then
177 raise Program_Error with "Left cursor is bad";
180 if Right.Node.Element = null then
181 raise Program_Error with "Right cursor is bad";
184 pragma Assert (Vet (Left.Container.Tree, Left.Node),
185 "bad Left cursor in ""<""");
187 pragma Assert (Vet (Right.Container.Tree, Right.Node),
188 "bad Right cursor in ""<""");
190 return Left.Node.Element.all < Right.Node.Element.all;
193 function "<" (Left : Cursor; Right : Element_Type) return Boolean is
195 if Left.Node = null then
196 raise Constraint_Error with "Left cursor equals No_Element";
199 if Left.Node.Element = null then
200 raise Program_Error with "Left cursor is bad";
203 pragma Assert (Vet (Left.Container.Tree, Left.Node),
204 "bad Left cursor in ""<""");
206 return Left.Node.Element.all < Right;
209 function "<" (Left : Element_Type; Right : Cursor) return Boolean is
211 if Right.Node = null then
212 raise Constraint_Error with "Right cursor equals No_Element";
215 if Right.Node.Element = null then
216 raise Program_Error with "Right cursor is bad";
219 pragma Assert (Vet (Right.Container.Tree, Right.Node),
220 "bad Right cursor in ""<""");
222 return Left < Right.Node.Element.all;
229 function "=" (Left, Right : Set) return Boolean is
231 function Is_Equal_Node_Node (L, R : Node_Access) return Boolean;
232 pragma Inline (Is_Equal_Node_Node);
235 new Tree_Operations.Generic_Equal (Is_Equal_Node_Node);
237 ------------------------
238 -- Is_Equal_Node_Node --
239 ------------------------
241 function Is_Equal_Node_Node (L, R : Node_Access) return Boolean is
243 return L.Element.all = R.Element.all;
244 end Is_Equal_Node_Node;
246 -- Start of processing for "="
249 return Is_Equal (Left.Tree, Right.Tree);
256 function ">" (Left, Right : Cursor) return Boolean is
258 if Left.Node = null then
259 raise Constraint_Error with "Left cursor equals No_Element";
262 if Right.Node = null then
263 raise Constraint_Error with "Right cursor equals No_Element";
266 if Left.Node.Element = null then
267 raise Program_Error with "Left cursor is bad";
270 if Right.Node.Element = null then
271 raise Program_Error with "Right cursor is bad";
274 pragma Assert (Vet (Left.Container.Tree, Left.Node),
275 "bad Left cursor in "">""");
277 pragma Assert (Vet (Right.Container.Tree, Right.Node),
278 "bad Right cursor in "">""");
280 -- L > R same as R < L
282 return Right.Node.Element.all < Left.Node.Element.all;
285 function ">" (Left : Cursor; Right : Element_Type) return Boolean is
287 if Left.Node = null then
288 raise Constraint_Error with "Left cursor equals No_Element";
291 if Left.Node.Element = null then
292 raise Program_Error with "Left cursor is bad";
295 pragma Assert (Vet (Left.Container.Tree, Left.Node),
296 "bad Left cursor in "">""");
298 return Right < Left.Node.Element.all;
301 function ">" (Left : Element_Type; Right : Cursor) return Boolean is
303 if Right.Node = null then
304 raise Constraint_Error with "Right cursor equals No_Element";
307 if Right.Node.Element = null then
308 raise Program_Error with "Right cursor is bad";
311 pragma Assert (Vet (Right.Container.Tree, Right.Node),
312 "bad Right cursor in "">""");
314 return Right.Node.Element.all < Left;
321 procedure Adjust is new Tree_Operations.Generic_Adjust (Copy_Tree);
323 procedure Adjust (Container : in out Set) is
325 Adjust (Container.Tree);
328 procedure Adjust (Control : in out Reference_Control_Type) is
330 if Control.Container /= null then
332 Tree : Tree_Type renames Control.Container.all.Tree;
333 B : Natural renames Tree.Busy;
334 L : Natural renames Tree.Lock;
346 procedure Assign (Target : in out Set; Source : Set) is
348 if Target'Address = Source'Address then
353 Target.Union (Source);
360 function Ceiling (Container : Set; Item : Element_Type) return Cursor is
361 Node : constant Node_Access :=
362 Element_Keys.Ceiling (Container.Tree, Item);
364 return (if Node = null then No_Element
365 else Cursor'(Container'Unrestricted_Access, Node));
373 new Tree_Operations.Generic_Clear (Delete_Tree);
375 procedure Clear (Container : in out Set) is
377 Clear (Container.Tree);
384 function Color (Node : Node_Access) return Color_Type is
389 ------------------------
390 -- Constant_Reference --
391 ------------------------
393 function Constant_Reference
394 (Container : aliased Set;
395 Position : Cursor) return Constant_Reference_Type
398 if Position.Container = null then
399 raise Constraint_Error with "Position cursor has no element";
402 if Position.Container /= Container'Unrestricted_Access then
403 raise Program_Error with
404 "Position cursor designates wrong container";
407 if Position.Node.Element = null then
408 raise Program_Error with "Node has no element";
412 (Vet (Container.Tree, Position.Node),
413 "bad cursor in Constant_Reference");
416 Tree : Tree_Type renames Position.Container.all.Tree;
417 B : Natural renames Tree.Busy;
418 L : Natural renames Tree.Lock;
420 return R : constant Constant_Reference_Type :=
421 (Element => Position.Node.Element.all'Access,
423 (Controlled with Container'Unrestricted_Access))
429 end Constant_Reference;
435 function Contains (Container : Set; Item : Element_Type) return Boolean is
437 return Find (Container, Item) /= No_Element;
444 function Copy (Source : Set) return Set is
446 return Target : Set do
447 Target.Assign (Source);
455 function Copy_Node (Source : Node_Access) return Node_Access is
456 Element : Element_Access := new Element_Type'(Source.Element.all);
459 return new Node_Type'(Parent => null,
462 Color => Source.Color,
466 Free_Element (Element);
474 procedure Delete (Container : in out Set; Position : in out Cursor) is
476 if Position.Node = null then
477 raise Constraint_Error with "Position cursor equals No_Element";
480 if Position.Node.Element = null then
481 raise Program_Error with "Position cursor is bad";
484 if Position.Container /= Container'Unrestricted_Access then
485 raise Program_Error with "Position cursor designates wrong set";
488 pragma Assert (Vet (Container.Tree, Position.Node),
489 "bad cursor in Delete");
491 Tree_Operations.Delete_Node_Sans_Free (Container.Tree, Position.Node);
492 Free (Position.Node);
493 Position.Container := null;
496 procedure Delete (Container : in out Set; Item : Element_Type) is
498 Element_Keys.Find (Container.Tree, Item);
502 raise Constraint_Error with "attempt to delete element not in set";
505 Tree_Operations.Delete_Node_Sans_Free (Container.Tree, X);
513 procedure Delete_First (Container : in out Set) is
514 Tree : Tree_Type renames Container.Tree;
515 X : Node_Access := Tree.First;
518 Tree_Operations.Delete_Node_Sans_Free (Tree, X);
527 procedure Delete_Last (Container : in out Set) is
528 Tree : Tree_Type renames Container.Tree;
529 X : Node_Access := Tree.Last;
532 Tree_Operations.Delete_Node_Sans_Free (Tree, X);
541 procedure Difference (Target : in out Set; Source : Set) is
543 Set_Ops.Difference (Target.Tree, Source.Tree);
546 function Difference (Left, Right : Set) return Set is
547 Tree : constant Tree_Type := Set_Ops.Difference (Left.Tree, Right.Tree);
549 return Set'(Controlled with Tree);
556 function Element (Position : Cursor) return Element_Type is
558 if Position.Node = null then
559 raise Constraint_Error with "Position cursor equals No_Element";
562 if Position.Node.Element = null then
563 raise Program_Error with "Position cursor is bad";
566 pragma Assert (Vet (Position.Container.Tree, Position.Node),
567 "bad cursor in Element");
569 return Position.Node.Element.all;
572 -------------------------
573 -- Equivalent_Elements --
574 -------------------------
576 function Equivalent_Elements (Left, Right : Element_Type) return Boolean is
578 if Left < Right or else Right < Left then
583 end Equivalent_Elements;
585 ---------------------
586 -- Equivalent_Sets --
587 ---------------------
589 function Equivalent_Sets (Left, Right : Set) return Boolean is
591 function Is_Equivalent_Node_Node (L, R : Node_Access) return Boolean;
592 pragma Inline (Is_Equivalent_Node_Node);
594 function Is_Equivalent is
595 new Tree_Operations.Generic_Equal (Is_Equivalent_Node_Node);
597 -----------------------------
598 -- Is_Equivalent_Node_Node --
599 -----------------------------
601 function Is_Equivalent_Node_Node (L, R : Node_Access) return Boolean is
603 if L.Element.all < R.Element.all then
605 elsif R.Element.all < L.Element.all then
610 end Is_Equivalent_Node_Node;
612 -- Start of processing for Equivalent_Sets
615 return Is_Equivalent (Left.Tree, Right.Tree);
622 procedure Exclude (Container : in out Set; Item : Element_Type) is
624 Element_Keys.Find (Container.Tree, Item);
627 Tree_Operations.Delete_Node_Sans_Free (Container.Tree, X);
636 procedure Finalize (Object : in out Iterator) is
638 if Object.Container /= null then
640 B : Natural renames Object.Container.all.Tree.Busy;
647 procedure Finalize (Control : in out Reference_Control_Type) is
649 if Control.Container /= null then
651 Tree : Tree_Type renames Control.Container.all.Tree;
652 B : Natural renames Tree.Busy;
653 L : Natural renames Tree.Lock;
659 Control.Container := null;
667 function Find (Container : Set; Item : Element_Type) return Cursor is
668 Node : constant Node_Access :=
669 Element_Keys.Find (Container.Tree, Item);
674 return Cursor'(Container'Unrestricted_Access, Node);
682 function First (Container : Set) return Cursor is
685 (if Container.Tree.First = null then No_Element
686 else Cursor'(Container'Unrestricted_Access, Container.Tree.First));
689 function First (Object : Iterator) return Cursor is
691 -- The value of the iterator object's Node component influences the
692 -- behavior of the First (and Last) selector function.
694 -- When the Node component is null, this means the iterator object was
695 -- constructed without a start expression, in which case the (forward)
696 -- iteration starts from the (logical) beginning of the entire sequence
697 -- of items (corresponding to Container.First, for a forward iterator).
699 -- Otherwise, this is iteration over a partial sequence of items. When
700 -- the Node component is non-null, the iterator object was constructed
701 -- with a start expression, that specifies the position from which the
702 -- (forward) partial iteration begins.
704 if Object.Node = null then
705 return Object.Container.First;
707 return Cursor'(Object.Container, Object.Node);
715 function First_Element (Container : Set) return Element_Type is
717 if Container.Tree.First = null then
718 raise Constraint_Error with "set is empty";
720 return Container.Tree.First.Element.all;
728 function Floor (Container : Set; Item : Element_Type) return Cursor is
729 Node : constant Node_Access :=
730 Element_Keys.Floor (Container.Tree, Item);
732 return (if Node = null then No_Element
733 else Cursor'(Container'Unrestricted_Access, Node));
740 procedure Free (X : in out Node_Access) is
741 procedure Deallocate is
742 new Ada.Unchecked_Deallocation (Node_Type, Node_Access);
754 Free_Element (X.Element);
769 package body Generic_Keys is
771 -----------------------
772 -- Local Subprograms --
773 -----------------------
775 function Is_Greater_Key_Node
777 Right : Node_Access) return Boolean;
778 pragma Inline (Is_Greater_Key_Node);
780 function Is_Less_Key_Node
782 Right : Node_Access) return Boolean;
783 pragma Inline (Is_Less_Key_Node);
785 --------------------------
786 -- Local Instantiations --
787 --------------------------
790 new Red_Black_Trees.Generic_Keys
791 (Tree_Operations => Tree_Operations,
792 Key_Type => Key_Type,
793 Is_Less_Key_Node => Is_Less_Key_Node,
794 Is_Greater_Key_Node => Is_Greater_Key_Node);
800 function Ceiling (Container : Set; Key : Key_Type) return Cursor is
801 Node : constant Node_Access :=
802 Key_Keys.Ceiling (Container.Tree, Key);
804 return (if Node = null then No_Element
805 else Cursor'(Container'Unrestricted_Access, Node));
808 ------------------------
809 -- Constant_Reference --
810 ------------------------
812 function Constant_Reference
813 (Container : aliased Set;
814 Key : Key_Type) return Constant_Reference_Type
816 Node : constant Node_Access :=
817 Key_Keys.Find (Container.Tree, Key);
821 raise Constraint_Error with "Key not in set";
824 if Node.Element = null then
825 raise Program_Error with "Node has no element";
829 Tree : Tree_Type renames Container'Unrestricted_Access.all.Tree;
830 B : Natural renames Tree.Busy;
831 L : Natural renames Tree.Lock;
833 return R : constant Constant_Reference_Type :=
834 (Element => Node.Element.all'Access,
836 (Controlled with Container'Unrestricted_Access))
842 end Constant_Reference;
848 function Contains (Container : Set; Key : Key_Type) return Boolean is
850 return Find (Container, Key) /= No_Element;
857 procedure Delete (Container : in out Set; Key : Key_Type) is
858 X : Node_Access := Key_Keys.Find (Container.Tree, Key);
862 raise Constraint_Error with "attempt to delete key not in set";
865 Tree_Operations.Delete_Node_Sans_Free (Container.Tree, X);
873 function Element (Container : Set; Key : Key_Type) return Element_Type is
874 Node : constant Node_Access :=
875 Key_Keys.Find (Container.Tree, Key);
878 raise Constraint_Error with "key not in set";
880 return Node.Element.all;
884 ---------------------
885 -- Equivalent_Keys --
886 ---------------------
888 function Equivalent_Keys (Left, Right : Key_Type) return Boolean is
890 if Left < Right or else Right < Left then
901 procedure Exclude (Container : in out Set; Key : Key_Type) is
902 X : Node_Access := Key_Keys.Find (Container.Tree, Key);
905 Tree_Operations.Delete_Node_Sans_Free (Container.Tree, X);
914 function Find (Container : Set; Key : Key_Type) return Cursor is
915 Node : constant Node_Access :=
916 Key_Keys.Find (Container.Tree, Key);
918 return (if Node = null then No_Element
919 else Cursor'(Container'Unrestricted_Access, Node));
926 function Floor (Container : Set; Key : Key_Type) return Cursor is
927 Node : constant Node_Access :=
928 Key_Keys.Floor (Container.Tree, Key);
930 return (if Node = null then No_Element
931 else Cursor'(Container'Unrestricted_Access, Node));
934 -------------------------
935 -- Is_Greater_Key_Node --
936 -------------------------
938 function Is_Greater_Key_Node
940 Right : Node_Access) return Boolean
943 return Key (Right.Element.all) < Left;
944 end Is_Greater_Key_Node;
946 ----------------------
947 -- Is_Less_Key_Node --
948 ----------------------
950 function Is_Less_Key_Node
952 Right : Node_Access) return Boolean
955 return Left < Key (Right.Element.all);
956 end Is_Less_Key_Node;
962 function Key (Position : Cursor) return Key_Type is
964 if Position.Node = null then
965 raise Constraint_Error with
966 "Position cursor equals No_Element";
969 if Position.Node.Element = null then
970 raise Program_Error with
971 "Position cursor is bad";
974 pragma Assert (Vet (Position.Container.Tree, Position.Node),
975 "bad cursor in Key");
977 return Key (Position.Node.Element.all);
985 (Container : in out Set;
987 New_Item : Element_Type)
989 Node : constant Node_Access := Key_Keys.Find (Container.Tree, Key);
993 raise Constraint_Error with
994 "attempt to replace key not in set";
997 Replace_Element (Container.Tree, Node, New_Item);
1005 (Stream : not null access Root_Stream_Type'Class;
1006 Item : out Reference_Type)
1009 raise Program_Error with "attempt to stream reference";
1012 ------------------------------
1013 -- Reference_Preserving_Key --
1014 ------------------------------
1016 function Reference_Preserving_Key
1017 (Container : aliased in out Set;
1018 Position : Cursor) return Reference_Type
1021 if Position.Container = null then
1022 raise Constraint_Error with "Position cursor has no element";
1025 if Position.Container /= Container'Unrestricted_Access then
1026 raise Program_Error with
1027 "Position cursor designates wrong container";
1030 if Position.Node.Element = null then
1031 raise Program_Error with "Node has no element";
1035 (Vet (Container.Tree, Position.Node),
1036 "bad cursor in function Reference_Preserving_Key");
1038 -- Some form of finalization will be required in order to actually
1039 -- check that the key-part of the element designated by Position has
1042 return (Element => Position.Node.Element.all'Access);
1043 end Reference_Preserving_Key;
1045 function Reference_Preserving_Key
1046 (Container : aliased in out Set;
1047 Key : Key_Type) return Reference_Type
1049 Node : constant Node_Access :=
1050 Key_Keys.Find (Container.Tree, Key);
1054 raise Constraint_Error with "Key not in set";
1057 if Node.Element = null then
1058 raise Program_Error with "Node has no element";
1061 -- Some form of finalization will be required in order to actually
1062 -- check that the key-part of the element designated by Key has not
1065 return (Element => Node.Element.all'Access);
1066 end Reference_Preserving_Key;
1068 -----------------------------------
1069 -- Update_Element_Preserving_Key --
1070 -----------------------------------
1072 procedure Update_Element_Preserving_Key
1073 (Container : in out Set;
1075 Process : not null access
1076 procedure (Element : in out Element_Type))
1078 Tree : Tree_Type renames Container.Tree;
1081 if Position.Node = null then
1082 raise Constraint_Error with "Position cursor equals No_Element";
1085 if Position.Node.Element = null then
1086 raise Program_Error with "Position cursor is bad";
1089 if Position.Container /= Container'Unrestricted_Access then
1090 raise Program_Error with "Position cursor designates wrong set";
1093 pragma Assert (Vet (Container.Tree, Position.Node),
1094 "bad cursor in Update_Element_Preserving_Key");
1097 E : Element_Type renames Position.Node.Element.all;
1098 K : constant Key_Type := Key (E);
1100 B : Natural renames Tree.Busy;
1101 L : Natural renames Tree.Lock;
1119 if Equivalent_Keys (K, Key (E)) then
1125 X : Node_Access := Position.Node;
1127 Tree_Operations.Delete_Node_Sans_Free (Tree, X);
1131 raise Program_Error with "key was modified";
1132 end Update_Element_Preserving_Key;
1139 (Stream : not null access Root_Stream_Type'Class;
1140 Item : Reference_Type)
1143 raise Program_Error with "attempt to stream reference";
1152 function Has_Element (Position : Cursor) return Boolean is
1154 return Position /= No_Element;
1161 procedure Include (Container : in out Set; New_Item : Element_Type) is
1168 Insert (Container, New_Item, Position, Inserted);
1170 if not Inserted then
1171 if Container.Tree.Lock > 0 then
1172 raise Program_Error with
1173 "attempt to tamper with elements (set is locked)";
1176 X := Position.Node.Element;
1177 Position.Node.Element := new Element_Type'(New_Item);
1187 (Container : in out Set;
1188 New_Item : Element_Type;
1189 Position : out Cursor;
1190 Inserted : out Boolean)
1199 Position.Container := Container'Unrestricted_Access;
1202 procedure Insert (Container : in out Set; New_Item : Element_Type) is
1204 pragma Unreferenced (Position);
1209 Insert (Container, New_Item, Position, Inserted);
1211 if not Inserted then
1212 raise Constraint_Error with
1213 "attempt to insert element already in set";
1217 ----------------------
1218 -- Insert_Sans_Hint --
1219 ----------------------
1221 procedure Insert_Sans_Hint
1222 (Tree : in out Tree_Type;
1223 New_Item : Element_Type;
1224 Node : out Node_Access;
1225 Inserted : out Boolean)
1227 function New_Node return Node_Access;
1228 pragma Inline (New_Node);
1230 procedure Insert_Post is
1231 new Element_Keys.Generic_Insert_Post (New_Node);
1233 procedure Conditional_Insert_Sans_Hint is
1234 new Element_Keys.Generic_Conditional_Insert (Insert_Post);
1240 function New_Node return Node_Access is
1241 Element : Element_Access := new Element_Type'(New_Item);
1244 return new Node_Type'(Parent => null,
1247 Color => Red_Black_Trees.Red,
1248 Element => Element);
1251 Free_Element (Element);
1255 -- Start of processing for Insert_Sans_Hint
1258 Conditional_Insert_Sans_Hint
1263 end Insert_Sans_Hint;
1265 ----------------------
1266 -- Insert_With_Hint --
1267 ----------------------
1269 procedure Insert_With_Hint
1270 (Dst_Tree : in out Tree_Type;
1271 Dst_Hint : Node_Access;
1272 Src_Node : Node_Access;
1273 Dst_Node : out Node_Access)
1276 pragma Unreferenced (Success);
1278 function New_Node return Node_Access;
1280 procedure Insert_Post is
1281 new Element_Keys.Generic_Insert_Post (New_Node);
1283 procedure Insert_Sans_Hint is
1284 new Element_Keys.Generic_Conditional_Insert (Insert_Post);
1286 procedure Insert_With_Hint is
1287 new Element_Keys.Generic_Conditional_Insert_With_Hint
1295 function New_Node return Node_Access is
1296 Element : Element_Access :=
1297 new Element_Type'(Src_Node.Element.all);
1302 Node := new Node_Type;
1305 Free_Element (Element);
1309 Node.Element := Element;
1313 -- Start of processing for Insert_With_Hint
1319 Src_Node.Element.all,
1322 end Insert_With_Hint;
1328 procedure Intersection (Target : in out Set; Source : Set) is
1330 Set_Ops.Intersection (Target.Tree, Source.Tree);
1333 function Intersection (Left, Right : Set) return Set is
1334 Tree : constant Tree_Type :=
1335 Set_Ops.Intersection (Left.Tree, Right.Tree);
1337 return Set'(Controlled with Tree);
1344 function Is_Empty (Container : Set) return Boolean is
1346 return Container.Tree.Length = 0;
1349 -----------------------------
1350 -- Is_Greater_Element_Node --
1351 -----------------------------
1353 function Is_Greater_Element_Node
1354 (Left : Element_Type;
1355 Right : Node_Access) return Boolean
1358 -- e > node same as node < e
1360 return Right.Element.all < Left;
1361 end Is_Greater_Element_Node;
1363 --------------------------
1364 -- Is_Less_Element_Node --
1365 --------------------------
1367 function Is_Less_Element_Node
1368 (Left : Element_Type;
1369 Right : Node_Access) return Boolean
1372 return Left < Right.Element.all;
1373 end Is_Less_Element_Node;
1375 -----------------------
1376 -- Is_Less_Node_Node --
1377 -----------------------
1379 function Is_Less_Node_Node (L, R : Node_Access) return Boolean is
1381 return L.Element.all < R.Element.all;
1382 end Is_Less_Node_Node;
1388 function Is_Subset (Subset : Set; Of_Set : Set) return Boolean is
1390 return Set_Ops.Is_Subset (Subset => Subset.Tree, Of_Set => Of_Set.Tree);
1399 Process : not null access procedure (Position : Cursor))
1401 procedure Process_Node (Node : Node_Access);
1402 pragma Inline (Process_Node);
1404 procedure Local_Iterate is
1405 new Tree_Operations.Generic_Iteration (Process_Node);
1411 procedure Process_Node (Node : Node_Access) is
1413 Process (Cursor'(Container'Unrestricted_Access, Node));
1416 T : Tree_Type renames Container'Unrestricted_Access.all.Tree;
1417 B : Natural renames T.Busy;
1419 -- Start of processing for Iterate
1437 return Set_Iterator_Interfaces.Reversible_Iterator'class
1439 B : Natural renames Container'Unrestricted_Access.all.Tree.Busy;
1442 -- The value of the Node component influences the behavior of the First
1443 -- and Last selector functions of the iterator object. When the Node
1444 -- component is null (as is the case here), this means the iterator
1445 -- object was constructed without a start expression. This is a complete
1446 -- iterator, meaning that the iteration starts from the (logical)
1447 -- beginning of the sequence of items.
1449 -- Note: For a forward iterator, Container.First is the beginning, and
1450 -- for a reverse iterator, Container.Last is the beginning.
1452 return It : constant Iterator :=
1453 Iterator'(Limited_Controlled with
1454 Container => Container'Unrestricted_Access,
1464 return Set_Iterator_Interfaces.Reversible_Iterator'class
1466 B : Natural renames Container'Unrestricted_Access.all.Tree.Busy;
1469 -- It was formerly the case that when Start = No_Element, the partial
1470 -- iterator was defined to behave the same as for a complete iterator,
1471 -- and iterate over the entire sequence of items. However, those
1472 -- semantics were unintuitive and arguably error-prone (it is too easy
1473 -- to accidentally create an endless loop), and so they were changed,
1474 -- per the ARG meeting in Denver on 2011/11. However, there was no
1475 -- consensus about what positive meaning this corner case should have,
1476 -- and so it was decided to simply raise an exception. This does imply,
1477 -- however, that it is not possible to use a partial iterator to specify
1478 -- an empty sequence of items.
1480 if Start = No_Element then
1481 raise Constraint_Error with
1482 "Start position for iterator equals No_Element";
1485 if Start.Container /= Container'Unrestricted_Access then
1486 raise Program_Error with
1487 "Start cursor of Iterate designates wrong set";
1490 pragma Assert (Vet (Container.Tree, Start.Node),
1491 "Start cursor of Iterate is bad");
1493 -- The value of the Node component influences the behavior of the First
1494 -- and Last selector functions of the iterator object. When the Node
1495 -- component is non-null (as is the case here), it means that this is a
1496 -- partial iteration, over a subset of the complete sequence of
1497 -- items. The iterator object was constructed with a start expression,
1498 -- indicating the position from which the iteration begins. Note that
1499 -- the start position has the same value irrespective of whether this is
1500 -- a forward or reverse iteration.
1502 return It : constant Iterator :=
1503 (Limited_Controlled with
1504 Container => Container'Unrestricted_Access,
1515 function Last (Container : Set) return Cursor is
1518 (if Container.Tree.Last = null then No_Element
1519 else Cursor'(Container'Unrestricted_Access, Container.Tree.Last));
1522 function Last (Object : Iterator) return Cursor is
1524 -- The value of the iterator object's Node component influences the
1525 -- behavior of the Last (and First) selector function.
1527 -- When the Node component is null, this means the iterator object was
1528 -- constructed without a start expression, in which case the (reverse)
1529 -- iteration starts from the (logical) beginning of the entire sequence
1530 -- (corresponding to Container.Last, for a reverse iterator).
1532 -- Otherwise, this is iteration over a partial sequence of items. When
1533 -- the Node component is non-null, the iterator object was constructed
1534 -- with a start expression, that specifies the position from which the
1535 -- (reverse) partial iteration begins.
1537 if Object.Node = null then
1538 return Object.Container.Last;
1540 return Cursor'(Object.Container, Object.Node);
1548 function Last_Element (Container : Set) return Element_Type is
1550 if Container.Tree.Last = null then
1551 raise Constraint_Error with "set is empty";
1553 return Container.Tree.Last.Element.all;
1561 function Left (Node : Node_Access) return Node_Access is
1570 function Length (Container : Set) return Count_Type is
1572 return Container.Tree.Length;
1579 procedure Move is new Tree_Operations.Generic_Move (Clear);
1581 procedure Move (Target : in out Set; Source : in out Set) is
1583 Move (Target => Target.Tree, Source => Source.Tree);
1590 procedure Next (Position : in out Cursor) is
1592 Position := Next (Position);
1595 function Next (Position : Cursor) return Cursor is
1597 if Position = No_Element then
1601 if Position.Node.Element = null then
1602 raise Program_Error with "Position cursor is bad";
1605 pragma Assert (Vet (Position.Container.Tree, Position.Node),
1606 "bad cursor in Next");
1609 Node : constant Node_Access :=
1610 Tree_Operations.Next (Position.Node);
1612 return (if Node = null then No_Element
1613 else Cursor'(Position.Container, Node));
1619 Position : Cursor) return Cursor
1622 if Position.Container = null then
1626 if Position.Container /= Object.Container then
1627 raise Program_Error with
1628 "Position cursor of Next designates wrong set";
1631 return Next (Position);
1638 function Overlap (Left, Right : Set) return Boolean is
1640 return Set_Ops.Overlap (Left.Tree, Right.Tree);
1647 function Parent (Node : Node_Access) return Node_Access is
1656 procedure Previous (Position : in out Cursor) is
1658 Position := Previous (Position);
1661 function Previous (Position : Cursor) return Cursor is
1663 if Position = No_Element then
1667 if Position.Node.Element = null then
1668 raise Program_Error with "Position cursor is bad";
1671 pragma Assert (Vet (Position.Container.Tree, Position.Node),
1672 "bad cursor in Previous");
1675 Node : constant Node_Access :=
1676 Tree_Operations.Previous (Position.Node);
1678 return (if Node = null then No_Element
1679 else Cursor'(Position.Container, Node));
1685 Position : Cursor) return Cursor
1688 if Position.Container = null then
1692 if Position.Container /= Object.Container then
1693 raise Program_Error with
1694 "Position cursor of Previous designates wrong set";
1697 return Previous (Position);
1704 procedure Query_Element
1706 Process : not null access procedure (Element : Element_Type))
1709 if Position.Node = null then
1710 raise Constraint_Error with "Position cursor equals No_Element";
1713 if Position.Node.Element = null then
1714 raise Program_Error with "Position cursor is bad";
1717 pragma Assert (Vet (Position.Container.Tree, Position.Node),
1718 "bad cursor in Query_Element");
1721 T : Tree_Type renames Position.Container.Tree;
1723 B : Natural renames T.Busy;
1724 L : Natural renames T.Lock;
1731 Process (Position.Node.Element.all);
1749 (Stream : not null access Root_Stream_Type'Class;
1750 Container : out Set)
1753 (Stream : not null access Root_Stream_Type'Class) return Node_Access;
1754 pragma Inline (Read_Node);
1757 new Tree_Operations.Generic_Read (Clear, Read_Node);
1764 (Stream : not null access Root_Stream_Type'Class) return Node_Access
1766 Node : Node_Access := new Node_Type;
1769 Node.Element := new Element_Type'(Element_Type'Input (Stream));
1774 Free (Node); -- Note that Free deallocates elem too
1778 -- Start of processing for Read
1781 Read (Stream, Container.Tree);
1785 (Stream : not null access Root_Stream_Type'Class;
1789 raise Program_Error with "attempt to stream set cursor";
1793 (Stream : not null access Root_Stream_Type'Class;
1794 Item : out Constant_Reference_Type)
1797 raise Program_Error with "attempt to stream reference";
1804 procedure Replace (Container : in out Set; New_Item : Element_Type) is
1805 Node : constant Node_Access :=
1806 Element_Keys.Find (Container.Tree, New_Item);
1809 pragma Warnings (Off, X);
1813 raise Constraint_Error with "attempt to replace element not in set";
1816 if Container.Tree.Lock > 0 then
1817 raise Program_Error with
1818 "attempt to tamper with elements (set is locked)";
1822 Node.Element := new Element_Type'(New_Item);
1826 ---------------------
1827 -- Replace_Element --
1828 ---------------------
1830 procedure Replace_Element
1831 (Tree : in out Tree_Type;
1833 Item : Element_Type)
1835 pragma Assert (Node /= null);
1836 pragma Assert (Node.Element /= null);
1838 function New_Node return Node_Access;
1839 pragma Inline (New_Node);
1841 procedure Local_Insert_Post is
1842 new Element_Keys.Generic_Insert_Post (New_Node);
1844 procedure Local_Insert_Sans_Hint is
1845 new Element_Keys.Generic_Conditional_Insert (Local_Insert_Post);
1847 procedure Local_Insert_With_Hint is
1848 new Element_Keys.Generic_Conditional_Insert_With_Hint
1850 Local_Insert_Sans_Hint);
1856 function New_Node return Node_Access is
1858 Node.Element := new Element_Type'(Item); -- OK if fails
1860 Node.Parent := null;
1867 Result : Node_Access;
1870 X : Element_Access := Node.Element;
1872 -- Start of processing for Replace_Element
1875 if Item < Node.Element.all
1876 or else Node.Element.all < Item
1881 if Tree.Lock > 0 then
1882 raise Program_Error with
1883 "attempt to tamper with elements (set is locked)";
1886 Node.Element := new Element_Type'(Item);
1892 Hint := Element_Keys.Ceiling (Tree, Item);
1897 elsif Item < Hint.Element.all then
1899 if Tree.Lock > 0 then
1900 raise Program_Error with
1901 "attempt to tamper with elements (set is locked)";
1904 Node.Element := new Element_Type'(Item);
1911 pragma Assert (not (Hint.Element.all < Item));
1912 raise Program_Error with "attempt to replace existing element";
1915 Tree_Operations.Delete_Node_Sans_Free (Tree, Node); -- Checks busy-bit
1917 Local_Insert_With_Hint
1922 Inserted => Inserted);
1924 pragma Assert (Inserted);
1925 pragma Assert (Result = Node);
1928 end Replace_Element;
1930 procedure Replace_Element
1931 (Container : in out Set;
1933 New_Item : Element_Type)
1936 if Position.Node = null then
1937 raise Constraint_Error with "Position cursor equals No_Element";
1940 if Position.Node.Element = null then
1941 raise Program_Error with "Position cursor is bad";
1944 if Position.Container /= Container'Unrestricted_Access then
1945 raise Program_Error with "Position cursor designates wrong set";
1948 pragma Assert (Vet (Container.Tree, Position.Node),
1949 "bad cursor in Replace_Element");
1951 Replace_Element (Container.Tree, Position.Node, New_Item);
1952 end Replace_Element;
1954 ---------------------
1955 -- Reverse_Iterate --
1956 ---------------------
1958 procedure Reverse_Iterate
1960 Process : not null access procedure (Position : Cursor))
1962 procedure Process_Node (Node : Node_Access);
1963 pragma Inline (Process_Node);
1965 procedure Local_Reverse_Iterate is
1966 new Tree_Operations.Generic_Reverse_Iteration (Process_Node);
1972 procedure Process_Node (Node : Node_Access) is
1974 Process (Cursor'(Container'Unrestricted_Access, Node));
1977 T : Tree_Type renames Container.Tree'Unrestricted_Access.all;
1978 B : Natural renames T.Busy;
1980 -- Start of processing for Reverse_Iterate
1986 Local_Reverse_Iterate (T);
1994 end Reverse_Iterate;
2000 function Right (Node : Node_Access) return Node_Access is
2009 procedure Set_Color (Node : Node_Access; Color : Color_Type) is
2011 Node.Color := Color;
2018 procedure Set_Left (Node : Node_Access; Left : Node_Access) is
2027 procedure Set_Parent (Node : Node_Access; Parent : Node_Access) is
2029 Node.Parent := Parent;
2036 procedure Set_Right (Node : Node_Access; Right : Node_Access) is
2038 Node.Right := Right;
2041 --------------------------
2042 -- Symmetric_Difference --
2043 --------------------------
2045 procedure Symmetric_Difference (Target : in out Set; Source : Set) is
2047 Set_Ops.Symmetric_Difference (Target.Tree, Source.Tree);
2048 end Symmetric_Difference;
2050 function Symmetric_Difference (Left, Right : Set) return Set is
2051 Tree : constant Tree_Type :=
2052 Set_Ops.Symmetric_Difference (Left.Tree, Right.Tree);
2054 return Set'(Controlled with Tree);
2055 end Symmetric_Difference;
2061 function To_Set (New_Item : Element_Type) return Set is
2065 pragma Unreferenced (Node, Inserted);
2067 Insert_Sans_Hint (Tree, New_Item, Node, Inserted);
2068 return Set'(Controlled with Tree);
2075 procedure Union (Target : in out Set; Source : Set) is
2077 Set_Ops.Union (Target.Tree, Source.Tree);
2080 function Union (Left, Right : Set) return Set is
2081 Tree : constant Tree_Type :=
2082 Set_Ops.Union (Left.Tree, Right.Tree);
2084 return Set'(Controlled with Tree);
2092 (Stream : not null access Root_Stream_Type'Class;
2095 procedure Write_Node
2096 (Stream : not null access Root_Stream_Type'Class;
2097 Node : Node_Access);
2098 pragma Inline (Write_Node);
2101 new Tree_Operations.Generic_Write (Write_Node);
2107 procedure Write_Node
2108 (Stream : not null access Root_Stream_Type'Class;
2112 Element_Type'Output (Stream, Node.Element.all);
2115 -- Start of processing for Write
2118 Write (Stream, Container.Tree);
2122 (Stream : not null access Root_Stream_Type'Class;
2126 raise Program_Error with "attempt to stream set cursor";
2130 (Stream : not null access Root_Stream_Type'Class;
2131 Item : Constant_Reference_Type)
2134 raise Program_Error with "attempt to stream reference";
2137 end Ada.Containers.Indefinite_Ordered_Sets;