From 1b9addbec8cce85f7568207078cd5eef05c1c9fb Mon Sep 17 00:00:00 2001 From: Jed Barber 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(-) (limited to 'src') 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