From 1b9addbec8cce85f7568207078cd5eef05c1c9fb Mon Sep 17 00:00:00 2001
From: Jed Barber <jjbarber@y7mail.com>
Date: Mon, 11 Mar 2019 22:09:36 +1100
Subject: Graph Append and Prepend functions should now work
---
src/packrat-graphs.adb | 104 ++++++++++++++++++++++++++++++++++++++++++++++---
src/packrat-graphs.ads | 4 ++
2 files changed, 102 insertions(+), 6 deletions(-)
diff --git a/src/packrat-graphs.adb b/src/packrat-graphs.adb
index 1cc21b3..f32c628 100644
--- a/src/packrat-graphs.adb
+++ b/src/packrat-graphs.adb
@@ -97,6 +97,14 @@ package body Packrat.Graphs is
+ function Is_Nothing
+ (This : in Node)
+ return Boolean is
+ begin
+ return This.Kind = Null_Node;
+ end Is_Nothing;
+
+
function Is_Leaf
(This : in Node)
return Boolean is
@@ -825,19 +833,103 @@ package body Packrat.Graphs is
- procedure Append
+ procedure Add_Nodes
(Container : in out Graph;
- Addition : in Graph) is
+ Addition : in Node_Vectors.Vector;
+ Mapping : out Index_Maps.Map) is
+ begin
+ Mapping := Index_Maps.Empty_Map;
+ for C in Addition.Iterate loop
+ Mapping.Insert (Node_Vectors.To_Index (C), Container.Add_Place);
+ if Container.Add_Place > Container.Node_List.Last_Index then
+ Container.Node_List.Append (Node_Vectors.Element (C));
+ else
+ Container.Node_List.Replace_Element (Container.Add_Place, Node_Vectors.Element (C));
+ end if;
+ while Container.Add_Place <= Container.Node_List.Last_Index and then
+ not Is_Nothing (Container.Node_List.Element (Container.Add_Place))
+ loop
+ Container.Add_Place := Container.Add_Place + 1;
+ end loop;
+ end loop;
+ end Add_Nodes;
+
+
+ procedure Add_Edges
+ (Container : in out Graph;
+ Addition : in Graph;
+ Mapping : in Index_Maps.Map)
+ is
+ Targets : Index_Vectors.Vector := Index_Vectors.Empty_Vector;
begin
- null;
+ -- Up edges
+ for E in Addition.Up_Edges.Iterate loop
+ Targets.Clear;
+ for T of Edge_Up_Maps.Element (E) loop
+ Targets.Append (Mapping.Element (T));
+ end loop;
+ Container.Up_Edges.Insert
+ (Mapping.Element (Edge_Up_Maps.Key (E)), Targets);
+ end loop;
+
+ -- Down edges
+ for E in Addition.Down_Edges.Iterate loop
+ Targets.Clear;
+ for T of Edge_Down_Maps.Element (E) loop
+ Targets.Append (Mapping.Element (T));
+ end loop;
+ Container.Down_Edges.Insert
+ ((Mapping.Element (Edge_Down_Maps.Key (E).From), Edge_Down_Maps.Key (E).Choice),
+ Targets);
+ end loop;
+
+ -- Choices
+ for C in Addition.Choices.Iterate loop
+ Container.Choices.Insert
+ (Mapping.Element (Choice_Maps.Key (C)), Choice_Maps.Element (C));
+ end loop;
+ end Add_Edges;
+
+
+ procedure Append
+ (Container : in out Graph;
+ Addition : in Graph)
+ is
+ Mapping : Index_Maps.Map;
+ begin
+ -- Add the nodes and edges from the addition to the graph,
+ -- making sure to handle the conversion of the index each node
+ -- is stored at. If index conversion wasn't required this bit would
+ -- be much simpler.
+ Add_Nodes (Container, Addition.Node_List, Mapping);
+ Add_Edges (Container, Addition, Mapping);
+
+ -- Append the root list of the addition to the graph
+ for R of Addition.Root_List loop
+ Container.Root_List.Append (Mapping.Element (R));
+ end loop;
end Append;
procedure Prepend
(Container : in out Graph;
- Addition : in Graph) is
- begin
- null;
+ Addition : in Graph)
+ is
+ Mapping : Index_Maps.Map;
+ Converted_Roots : Index_Vectors.Vector := Index_Vectors.Empty_Vector;
+ begin
+ -- Add the nodes and edges from the addition to the graph,
+ -- making sure to handle the conversion of the index each node
+ -- is stored at. If index conversion wasn't required this bit would
+ -- be much simpler.
+ Add_Nodes (Container, Addition.Node_List, Mapping);
+ Add_Edges (Container, Addition, Mapping);
+
+ -- Prepend the root list of the addition to the graph
+ for R of Addition.Root_List loop
+ Converted_Roots.Append (Mapping.Element (R));
+ end loop;
+ Container.Root_List.Prepend (Converted_Roots);
end Prepend;
diff --git a/src/packrat-graphs.ads b/src/packrat-graphs.ads
index 76be2e4..5074485 100644
--- a/src/packrat-graphs.ads
+++ b/src/packrat-graphs.ads
@@ -469,6 +469,10 @@ private
(Index_Type => Positive,
Element_Type => Node_Index);
+ package Index_Maps is new Ada.Containers.Ordered_Maps
+ (Key_Type => Node_Index,
+ Element_Type => Node_Index);
+
--
cgit