package body Ada.Containers.Red_Black_Trees.Generic_Set_Operations is
procedure Difference (Target : in out Tree_Type; Source : Tree_Type) is
Tgt : Node_Access := Target.First;
Src : Node_Access := Source.First;
begin
loop
if Tgt = Tree_Operations.Null_Node then
return;
end if;
if Src = Tree_Operations.Null_Node then
return;
end if;
if Is_Less (Tgt, Src) then
Tgt := Tree_Operations.Next (Tgt);
elsif Is_Less (Src, Tgt) then
Src := Tree_Operations.Next (Src);
else
declare
X : Node_Access := Tgt;
begin
Tgt := Tree_Operations.Next (Tgt);
Tree_Operations.Delete_Node_Sans_Free (Target, X);
Free (X);
end;
Src := Tree_Operations.Next (Src);
end if;
end loop;
end Difference;
function Difference (Left, Right : Tree_Type) return Tree_Type is
Tree : Tree_Type := (Length => 0, others => Tree_Operations.Null_Node);
L_Node : Node_Access := Left.First;
R_Node : Node_Access := Right.First;
Dst_Node : Node_Access;
begin
loop
if L_Node = Tree_Operations.Null_Node then
return Tree;
end if;
if R_Node = Tree_Operations.Null_Node then
while L_Node /= Tree_Operations.Null_Node loop
Insert_With_Hint
(Dst_Tree => Tree,
Dst_Hint => Tree_Operations.Null_Node,
Src_Node => L_Node,
Dst_Node => Dst_Node);
L_Node := Tree_Operations.Next (L_Node);
end loop;
return Tree;
end if;
if Is_Less (L_Node, R_Node) then
Insert_With_Hint
(Dst_Tree => Tree,
Dst_Hint => Tree_Operations.Null_Node,
Src_Node => L_Node,
Dst_Node => Dst_Node);
L_Node := Tree_Operations.Next (L_Node);
elsif Is_Less (R_Node, L_Node) then
R_Node := Tree_Operations.Next (R_Node);
else
L_Node := Tree_Operations.Next (L_Node);
R_Node := Tree_Operations.Next (R_Node);
end if;
end loop;
exception
when others =>
Delete_Tree (Tree.Root);
raise;
end Difference;
procedure Intersection
(Target : in out Tree_Type;
Source : Tree_Type)
is
Tgt : Node_Access := Target.First;
Src : Node_Access := Source.First;
begin
while Tgt /= Tree_Operations.Null_Node
and then Src /= Tree_Operations.Null_Node
loop
if Is_Less (Tgt, Src) then
declare
X : Node_Access := Tgt;
begin
Tgt := Tree_Operations.Next (Tgt);
Tree_Operations.Delete_Node_Sans_Free (Target, X);
Free (X);
end;
elsif Is_Less (Src, Tgt) then
Src := Tree_Operations.Next (Src);
else
Tgt := Tree_Operations.Next (Tgt);
Src := Tree_Operations.Next (Src);
end if;
end loop;
end Intersection;
function Intersection (Left, Right : Tree_Type) return Tree_Type is
Tree : Tree_Type := (Length => 0, others => Tree_Operations.Null_Node);
L_Node : Node_Access := Left.First;
R_Node : Node_Access := Right.First;
Dst_Node : Node_Access;
begin
loop
if L_Node = Tree_Operations.Null_Node then
return Tree;
end if;
if R_Node = Tree_Operations.Null_Node then
return Tree;
end if;
if Is_Less (L_Node, R_Node) then
L_Node := Tree_Operations.Next (L_Node);
elsif Is_Less (R_Node, L_Node) then
R_Node := Tree_Operations.Next (R_Node);
else
Insert_With_Hint
(Dst_Tree => Tree,
Dst_Hint => Tree_Operations.Null_Node,
Src_Node => L_Node,
Dst_Node => Dst_Node);
L_Node := Tree_Operations.Next (L_Node);
R_Node := Tree_Operations.Next (R_Node);
end if;
end loop;
exception
when others =>
Delete_Tree (Tree.Root);
raise;
end Intersection;
function Is_Subset
(Subset : Tree_Type;
Of_Set : Tree_Type) return Boolean
is
begin
if Subset.Length > Of_Set.Length then
return False;
end if;
declare
Subset_Node : Node_Access := Subset.First;
Set_Node : Node_Access := Of_Set.First;
begin
loop
if Set_Node = Tree_Operations.Null_Node then
return Subset_Node = Tree_Operations.Null_Node;
end if;
if Subset_Node = Tree_Operations.Null_Node then
return True;
end if;
if Is_Less (Subset_Node, Set_Node) then
return False;
end if;
if Is_Less (Set_Node, Subset_Node) then
Set_Node := Tree_Operations.Next (Set_Node);
else
Set_Node := Tree_Operations.Next (Set_Node);
Subset_Node := Tree_Operations.Next (Subset_Node);
end if;
end loop;
end;
end Is_Subset;
function Overlap (Left, Right : Tree_Type) return Boolean is
L_Node : Node_Access := Left.First;
R_Node : Node_Access := Right.First;
begin
loop
if L_Node = Tree_Operations.Null_Node
or else R_Node = Tree_Operations.Null_Node
then
return False;
end if;
if Is_Less (L_Node, R_Node) then
L_Node := Tree_Operations.Next (L_Node);
elsif Is_Less (R_Node, L_Node) then
R_Node := Tree_Operations.Next (R_Node);
else
return True;
end if;
end loop;
end Overlap;
procedure Symmetric_Difference
(Target : in out Tree_Type;
Source : Tree_Type)
is
Tgt : Node_Access := Target.First;
Src : Node_Access := Source.First;
New_Tgt_Node : Node_Access;
begin
loop
if Tgt = Tree_Operations.Null_Node then
while Src /= Tree_Operations.Null_Node loop
Insert_With_Hint
(Dst_Tree => Target,
Dst_Hint => Tree_Operations.Null_Node,
Src_Node => Src,
Dst_Node => New_Tgt_Node);
Src := Tree_Operations.Next (Src);
end loop;
return;
end if;
if Src = Tree_Operations.Null_Node then
return;
end if;
if Is_Less (Tgt, Src) then
Tgt := Tree_Operations.Next (Tgt);
elsif Is_Less (Src, Tgt) then
Insert_With_Hint
(Dst_Tree => Target,
Dst_Hint => Tgt,
Src_Node => Src,
Dst_Node => New_Tgt_Node);
Src := Tree_Operations.Next (Src);
else
declare
X : Node_Access := Tgt;
begin
Tgt := Tree_Operations.Next (Tgt);
Tree_Operations.Delete_Node_Sans_Free (Target, X);
Free (X);
end;
Src := Tree_Operations.Next (Src);
end if;
end loop;
end Symmetric_Difference;
function Symmetric_Difference (Left, Right : Tree_Type) return Tree_Type is
Tree : Tree_Type := (Length => 0, others => Tree_Operations.Null_Node);
L_Node : Node_Access := Left.First;
R_Node : Node_Access := Right.First;
Dst_Node : Node_Access;
begin
loop
if L_Node = Tree_Operations.Null_Node then
while R_Node /= Tree_Operations.Null_Node loop
Insert_With_Hint
(Dst_Tree => Tree,
Dst_Hint => Tree_Operations.Null_Node,
Src_Node => R_Node,
Dst_Node => Dst_Node);
R_Node := Tree_Operations.Next (R_Node);
end loop;
return Tree;
end if;
if R_Node = Tree_Operations.Null_Node then
while L_Node /= Tree_Operations.Null_Node loop
Insert_With_Hint
(Dst_Tree => Tree,
Dst_Hint => Tree_Operations.Null_Node,
Src_Node => L_Node,
Dst_Node => Dst_Node);
L_Node := Tree_Operations.Next (L_Node);
end loop;
return Tree;
end if;
if Is_Less (L_Node, R_Node) then
Insert_With_Hint
(Dst_Tree => Tree,
Dst_Hint => Tree_Operations.Null_Node,
Src_Node => L_Node,
Dst_Node => Dst_Node);
L_Node := Tree_Operations.Next (L_Node);
elsif Is_Less (R_Node, L_Node) then
Insert_With_Hint
(Dst_Tree => Tree,
Dst_Hint => Tree_Operations.Null_Node,
Src_Node => R_Node,
Dst_Node => Dst_Node);
R_Node := Tree_Operations.Next (R_Node);
else
L_Node := Tree_Operations.Next (L_Node);
R_Node := Tree_Operations.Next (R_Node);
end if;
end loop;
exception
when others =>
Delete_Tree (Tree.Root);
raise;
end Symmetric_Difference;
procedure Union (Target : in out Tree_Type; Source : Tree_Type)
is
Hint : Node_Access;
procedure Process (Node : Node_Access);
pragma Inline (Process);
procedure Iterate is new Tree_Operations.Generic_Iteration (Process);
procedure Process (Node : Node_Access) is
begin
Insert_With_Hint
(Dst_Tree => Target,
Dst_Hint => Hint,
Src_Node => Node,
Dst_Node => Hint);
end Process;
begin
Iterate (Source);
end Union;
function Union (Left, Right : Tree_Type) return Tree_Type is
Tree : Tree_Type;
begin
declare
Root : constant Node_Access := Copy_Tree (Left.Root);
begin
Tree := (Root => Root,
First => Tree_Operations.Min (Root),
Last => Tree_Operations.Max (Root),
Length => Left.Length);
end;
declare
Hint : Node_Access;
procedure Process (Node : Node_Access);
pragma Inline (Process);
procedure Iterate is
new Tree_Operations.Generic_Iteration (Process);
procedure Process (Node : Node_Access) is
begin
Insert_With_Hint
(Dst_Tree => Tree,
Dst_Hint => Hint,
Src_Node => Node,
Dst_Node => Hint);
end Process;
begin
Iterate (Right);
exception
when others =>
Delete_Tree (Tree.Root);
raise;
end;
return Tree;
end Union;
end Ada.Containers.Red_Black_Trees.Generic_Set_Operations;