1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- ADA.CONTAINERS.RED_BLACK_TREES.GENERIC_SET_OPERATIONS --
9 -- Copyright (C) 2004-2009, 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 System; use type System.Address;
32 package body Ada.Containers.Red_Black_Trees.Generic_Set_Operations is
34 -----------------------
35 -- Local Subprograms --
36 -----------------------
38 procedure Clear (Tree : in out Tree_Type);
40 function Copy (Source : Tree_Type) return Tree_Type;
46 procedure Clear (Tree : in out Tree_Type) is
47 pragma Assert (Tree.Busy = 0);
48 pragma Assert (Tree.Lock = 0);
50 Root : Node_Access := Tree.Root;
51 pragma Warnings (Off, Root);
66 function Copy (Source : Tree_Type) return Tree_Type is
70 if Source.Length = 0 then
74 Target.Root := Copy_Tree (Source.Root);
75 Target.First := Tree_Operations.Min (Target.Root);
76 Target.Last := Tree_Operations.Max (Target.Root);
77 Target.Length := Source.Length;
86 procedure Difference (Target : in out Tree_Type; Source : Tree_Type) is
87 Tgt : Node_Access := Target.First;
88 Src : Node_Access := Source.First;
91 if Target'Address = Source'Address then
92 if Target.Busy > 0 then
93 raise Program_Error with
94 "attempt to tamper with cursors (container is busy)";
101 if Source.Length = 0 then
105 if Target.Busy > 0 then
106 raise Program_Error with
107 "attempt to tamper with cursors (container is busy)";
119 if Is_Less (Tgt, Src) then
120 Tgt := Tree_Operations.Next (Tgt);
122 elsif Is_Less (Src, Tgt) then
123 Src := Tree_Operations.Next (Src);
127 X : Node_Access := Tgt;
129 Tgt := Tree_Operations.Next (Tgt);
130 Tree_Operations.Delete_Node_Sans_Free (Target, X);
134 Src := Tree_Operations.Next (Src);
139 function Difference (Left, Right : Tree_Type) return Tree_Type is
142 L_Node : Node_Access := Left.First;
143 R_Node : Node_Access := Right.First;
145 Dst_Node : Node_Access;
146 pragma Warnings (Off, Dst_Node);
149 if Left'Address = Right'Address then
150 return Tree; -- Empty set
153 if Left.Length = 0 then
154 return Tree; -- Empty set
157 if Right.Length = 0 then
162 if L_Node = null then
166 if R_Node = null then
167 while L_Node /= null loop
172 Dst_Node => Dst_Node);
174 L_Node := Tree_Operations.Next (L_Node);
181 if Is_Less (L_Node, R_Node) then
186 Dst_Node => Dst_Node);
188 L_Node := Tree_Operations.Next (L_Node);
190 elsif Is_Less (R_Node, L_Node) then
191 R_Node := Tree_Operations.Next (R_Node);
194 L_Node := Tree_Operations.Next (L_Node);
195 R_Node := Tree_Operations.Next (R_Node);
201 Delete_Tree (Tree.Root);
209 procedure Intersection
210 (Target : in out Tree_Type;
213 Tgt : Node_Access := Target.First;
214 Src : Node_Access := Source.First;
217 if Target'Address = Source'Address then
221 if Target.Busy > 0 then
222 raise Program_Error with
223 "attempt to tamper with cursors (container is busy)";
226 if Source.Length = 0 then
234 if Is_Less (Tgt, Src) then
236 X : Node_Access := Tgt;
238 Tgt := Tree_Operations.Next (Tgt);
239 Tree_Operations.Delete_Node_Sans_Free (Target, X);
243 elsif Is_Less (Src, Tgt) then
244 Src := Tree_Operations.Next (Src);
247 Tgt := Tree_Operations.Next (Tgt);
248 Src := Tree_Operations.Next (Src);
252 while Tgt /= null loop
254 X : Node_Access := Tgt;
256 Tgt := Tree_Operations.Next (Tgt);
257 Tree_Operations.Delete_Node_Sans_Free (Target, X);
263 function Intersection (Left, Right : Tree_Type) return Tree_Type is
266 L_Node : Node_Access := Left.First;
267 R_Node : Node_Access := Right.First;
269 Dst_Node : Node_Access;
270 pragma Warnings (Off, Dst_Node);
273 if Left'Address = Right'Address then
278 if L_Node = null then
282 if R_Node = null then
286 if Is_Less (L_Node, R_Node) then
287 L_Node := Tree_Operations.Next (L_Node);
289 elsif Is_Less (R_Node, L_Node) then
290 R_Node := Tree_Operations.Next (R_Node);
297 Dst_Node => Dst_Node);
299 L_Node := Tree_Operations.Next (L_Node);
300 R_Node := Tree_Operations.Next (R_Node);
306 Delete_Tree (Tree.Root);
316 Of_Set : Tree_Type) return Boolean
319 if Subset'Address = Of_Set'Address then
323 if Subset.Length > Of_Set.Length then
328 Subset_Node : Node_Access := Subset.First;
329 Set_Node : Node_Access := Of_Set.First;
333 if Set_Node = null then
334 return Subset_Node = null;
337 if Subset_Node = null then
341 if Is_Less (Subset_Node, Set_Node) then
345 if Is_Less (Set_Node, Subset_Node) then
346 Set_Node := Tree_Operations.Next (Set_Node);
348 Set_Node := Tree_Operations.Next (Set_Node);
349 Subset_Node := Tree_Operations.Next (Subset_Node);
359 function Overlap (Left, Right : Tree_Type) return Boolean is
360 L_Node : Node_Access := Left.First;
361 R_Node : Node_Access := Right.First;
364 if Left'Address = Right'Address then
365 return Left.Length /= 0;
370 or else R_Node = null
375 if Is_Less (L_Node, R_Node) then
376 L_Node := Tree_Operations.Next (L_Node);
378 elsif Is_Less (R_Node, L_Node) then
379 R_Node := Tree_Operations.Next (R_Node);
387 --------------------------
388 -- Symmetric_Difference --
389 --------------------------
391 procedure Symmetric_Difference
392 (Target : in out Tree_Type;
395 Tgt : Node_Access := Target.First;
396 Src : Node_Access := Source.First;
398 New_Tgt_Node : Node_Access;
399 pragma Warnings (Off, New_Tgt_Node);
402 if Target.Busy > 0 then
403 raise Program_Error with
404 "attempt to tamper with cursors (container is busy)";
407 if Target'Address = Source'Address then
414 while Src /= null loop
419 Dst_Node => New_Tgt_Node);
421 Src := Tree_Operations.Next (Src);
431 if Is_Less (Tgt, Src) then
432 Tgt := Tree_Operations.Next (Tgt);
434 elsif Is_Less (Src, Tgt) then
439 Dst_Node => New_Tgt_Node);
441 Src := Tree_Operations.Next (Src);
445 X : Node_Access := Tgt;
447 Tgt := Tree_Operations.Next (Tgt);
448 Tree_Operations.Delete_Node_Sans_Free (Target, X);
452 Src := Tree_Operations.Next (Src);
455 end Symmetric_Difference;
457 function Symmetric_Difference (Left, Right : Tree_Type) return Tree_Type is
460 L_Node : Node_Access := Left.First;
461 R_Node : Node_Access := Right.First;
463 Dst_Node : Node_Access;
464 pragma Warnings (Off, Dst_Node);
467 if Left'Address = Right'Address then
468 return Tree; -- Empty set
471 if Right.Length = 0 then
475 if Left.Length = 0 then
480 if L_Node = null then
481 while R_Node /= null loop
486 Dst_Node => Dst_Node);
487 R_Node := Tree_Operations.Next (R_Node);
493 if R_Node = null then
494 while L_Node /= null loop
499 Dst_Node => Dst_Node);
501 L_Node := Tree_Operations.Next (L_Node);
507 if Is_Less (L_Node, R_Node) then
512 Dst_Node => Dst_Node);
514 L_Node := Tree_Operations.Next (L_Node);
516 elsif Is_Less (R_Node, L_Node) then
521 Dst_Node => Dst_Node);
523 R_Node := Tree_Operations.Next (R_Node);
526 L_Node := Tree_Operations.Next (L_Node);
527 R_Node := Tree_Operations.Next (R_Node);
533 Delete_Tree (Tree.Root);
535 end Symmetric_Difference;
541 procedure Union (Target : in out Tree_Type; Source : Tree_Type)
545 procedure Process (Node : Node_Access);
546 pragma Inline (Process);
548 procedure Iterate is new Tree_Operations.Generic_Iteration (Process);
554 procedure Process (Node : Node_Access) is
563 -- Start of processing for Union
566 if Target'Address = Source'Address then
570 if Target.Busy > 0 then
571 raise Program_Error with
572 "attempt to tamper with cursors (container is busy)";
578 function Union (Left, Right : Tree_Type) return Tree_Type is
580 if Left'Address = Right'Address then
584 if Left.Length = 0 then
588 if Right.Length = 0 then
593 Tree : Tree_Type := Copy (Left);
597 procedure Process (Node : Node_Access);
598 pragma Inline (Process);
601 new Tree_Operations.Generic_Iteration (Process);
607 procedure Process (Node : Node_Access) is
616 -- Start of processing for Union
624 Delete_Tree (Tree.Root);
630 end Ada.Containers.Red_Black_Trees.Generic_Set_Operations;