diff options
Diffstat (limited to 'src/packrat-graphs.ads')
| -rw-r--r-- | src/packrat-graphs.ads | 381 |
1 files changed, 285 insertions, 96 deletions
diff --git a/src/packrat-graphs.ads b/src/packrat-graphs.ads index 0ef298e..cd5c364 100644 --- a/src/packrat-graphs.ads +++ b/src/packrat-graphs.ads @@ -4,28 +4,27 @@ with Ada.Iterator_Interfaces; +private with + + Ada.Containers.Ordered_Maps, + Ada.Containers.Vectors; + generic type Label_Enum is (<>); type Element is private; type Element_Array is array (Positive range <>) of Element; - with package My_Interfaces is new Interfaces (Label_Enum, Element, Element_Array); package Packrat.Graphs is - type Node is new My_Interfaces.Node with private; - - type Node_Reference (Data : not null access Node'Class) is limited null record - with Implicit_Dereference => Data; - - - type Cursor is new My_Interfaces.Cursor with private; + type Node is private; - type Iter_Cursor (Data : not null access Cursor) is private + type Node_Reference (Data : not null access Node) is limited null record with Implicit_Dereference => Data; + type Cursor is private; - type Parse_Graph is new My_Interfaces.Graph with private + type Graph is tagged private with Default_Iterator => Iterate, Iterator_Element => Node_Reference, Variable_Indexing => Node_At; @@ -33,9 +32,9 @@ package Packrat.Graphs is - No_Position : constant My_Interfaces.Cursor'Class; + No_Position : constant Cursor; - Empty_Graph : constant Parse_Graph; + Empty_Graph : constant Graph; @@ -44,13 +43,23 @@ package Packrat.Graphs is (New_Item : in Element_Array; Start : in Positive; Finish : in Natural) - return Node; + return Node + with Pre => + Finish + 1 >= Start, + Post => + Is_Leaf (Leaf'Result); function Branch (Label : in Label_Enum; Start : in Positive; Finish : in Natural) - return Node; + return Node + with Pre => + Finish + 1 >= Start, + Post => + Is_Branch (Branch'Result); + + function Is_Leaf @@ -62,13 +71,19 @@ package Packrat.Graphs is return Boolean; + + function Label (This : in Node) - return Label_Enum; + return Label_Enum + with Pre => + Is_Branch (This); function Elements (This : in Node) - return Element_Array; + return Element_Array + with Pre => + Is_Leaf (This); function Start (This : in Node) @@ -94,38 +109,57 @@ package Packrat.Graphs is function Is_Node (Position : in Cursor) - return Boolean; + return Boolean + with Post => + (if Is_Node'Result then not Is_Nothing (Position)); function Is_Root (Position : in Cursor) - return Boolean; + return Boolean + with Post => + (if Is_Root'Result then + not Is_Nothing (Position) and + Is_Nothing (Parent (Position)) and + Depth (Position) = 0); function Is_Branch (Position : in Cursor) - return Boolean; + return Boolean + with Post => + (if Is_Branch'Result then not Is_Nothing (Position)); function Is_Leaf (Position : in Cursor) - return Boolean; + return Boolean + with Post => + (if Is_Leaf'Result then not Is_Nothing (Position)); function Label (Position : in Cursor) - return Label_Enum; + return Label_Enum + with Pre => + Is_Branch (Position); function Elements (Position : in Cursor) - return Element_Array; + return Element_Array + with Pre => + Is_Leaf (Position); function Start (Position : in Cursor) - return Positive; + return Positive + with Pre => + not Is_Nothing (Position); function Finish (Position : in Cursor) - return Natural; + return Natural + with Pre => + not Is_Nothing (Position); function Choices (Position : in Cursor) @@ -141,7 +175,9 @@ package Packrat.Graphs is function Child_Count (Position : in Cursor; Choice : in Positive) - return Natural; + return Natural + with Pre => + Choice <= Choices (Position); function Child_Count (Position : in Cursor) @@ -154,38 +190,62 @@ package Packrat.Graphs is function First_Child (Position : in Cursor; Choice : in Positive) - return Cursor; + return Cursor + with Pre => + Choice <= Choices (Position), + Post => + Parent (First_Child'Result) = Position; function Last_Child (Position : in Cursor; Choice : in Positive) - return Cursor; + return Cursor + with Pre => + Choice <= Choices (Position), + Post => + Parent (Last_Child'Result) = Position; function First_Child (Position : in Cursor) - return Cursor; + return Cursor + with Post => + Parent (First_Child'Result) = Position; function Last_Child (Position : in Cursor) - return Cursor; + return Cursor + with Post => + Parent (Last_Child'Result) = Position; function Next_Sibling (Position : in Cursor) - return Cursor; + return Cursor + with Post => + Parent (Next_Sibling'Result) = Parent (Position); function Prev_Sibling (Position : in Cursor) - return Cursor; + return Cursor + with Post => + Parent (Prev_Sibling'Result) = Parent (Position); procedure Delete_Children (Position : in out Cursor; - Choice : in Positive); + Choice : in Positive) + with Pre => + Choice <= Choices (Position), + Post => + Child_Count (Position, Choice) = 0; procedure Delete_Children - (Position : in out Cursor); + (Position : in out Cursor) + with Post => + Child_Count (Position) = 0; procedure Delete_All_Children - (Position : in out Cursor); + (Position : in out Cursor) + with Post => + All_Child_Count (Position) = 0; @@ -201,103 +261,129 @@ package Packrat.Graphs is function Find_In_Subgraph (Position : in Cursor; Item : in Element_Array) - return Cursor; + return Cursor + with Post => + Is_Nothing (Find_In_Subgraph'Result) or + Is_Leaf (Find_In_Subgraph'Result); function Contains - (Container : in Parse_Graph; - Position : in My_Interfaces.Cursor'Class) - return Boolean; + (Container : in Graph; + Position : in Cursor) + return Boolean + with Post => + (if Contains'Result then not Is_Nothing (Position)); function Singleton - (Input : in My_Interfaces.Node'Class) - return Parse_Graph; + (Input : in Node) + return Graph + with Post => + Singleton'Result.Node_Count = 1; function Node_At - (Container : in Parse_Graph; - Position : in My_Interfaces.Cursor'Class) + (Container : in Graph; + Position : in Cursor) return Node_Reference with Pre => - Position.Is_Node; + Contains (Container, Position); function Is_Empty - (Container : in Parse_Graph) - return Boolean; + (Container : in Graph) + return Boolean + with Post => + (if Is_Empty'Result then Container.Node_Count = 0 else Container.Node_Count /= 0); function Is_Ambiguous - (Container : in Parse_Graph) + (Container : in Graph) return Boolean; function Node_Count - (Container : in Parse_Graph) + (Container : in Graph) return Natural; function Root_Count - (Container : in Parse_Graph) - return Natural; + (Container : in Graph) + return Natural + with Post => + (if Container.Is_Empty then Root_Count'Result = 0 else Root_Count'Result > 0); function Root - (Container : in Parse_Graph; + (Container : in Graph; Index : in Positive) - return My_Interfaces.Cursor'Class; + return Cursor + with Pre => + Index <= Container.Root_Count; procedure Append - (Container : in out Parse_Graph; - Addition : in Parse_Graph); + (Container : in out Graph; + Addition : in Graph) + with Pre => + Container.Is_Empty or else Addition.Is_Empty or else + Finish (Container.Root (Container.Root_Count)) < Start (Addition.Root (1)); procedure Prepend - (Container : in out Parse_Graph; - Addition : in Parse_Graph); + (Container : in out Graph; + Addition : in Graph) + with Pre => + Container.Is_Empty or else Addition.Is_Empty or else + Start (Container.Root (1)) > Finish (Addition.Root (Addition.Root_Count)); procedure Attach_Choice - (Container : in out Parse_Graph; - Position : in My_Interfaces.Cursor'Class; - Addition : in Parse_Graph); + (Container : in out Graph; + Position : in Cursor; + Addition : in Graph) + with Pre => + Container.Contains (Position) and Is_Branch (Position) and + (Addition.Is_Empty or else + (Start (Position) <= Start (Addition.Root (1)) and + Finish (Position) >= Finish (Addition.Root (Addition.Root_Count)))); procedure Clear - (Container : in out Parse_Graph); + (Container : in out Graph) + with Post => + Container.Is_Empty; procedure Delete_Position - (Container : in out Parse_Graph; - Position : in out My_Interfaces.Cursor'Class); + (Container : in out Graph; + Position : in out Cursor) + with Pre'Class => + Container.Contains (Position), + Post'Class => + not Container.Contains (Position); function Find - (Container : in Parse_Graph; + (Container : in Graph; Item : in Element_Array) - return My_Interfaces.Cursor'Class; - - - - - function Is_Valid_Node - (Position : in Iter_Cursor) - return Boolean; + return Cursor + with Post => + Is_Leaf (Find'Result) or + Is_Nothing (Find'Result); package Graph_Iterators is - new Ada.Iterator_Interfaces (Iter_Cursor, Is_Valid_Node); + new Ada.Iterator_Interfaces (Cursor, Is_Node); type Choosing_Function is access function (Position : in Cursor) @@ -307,16 +393,16 @@ package Packrat.Graphs is function Iterate - (This : in Parse_Graph) + (This : in Graph) return Graph_Iterators.Reversible_Iterator'Class; function Iterate_Subtree - (This : in Parse_Graph; - Position : in My_Interfaces.Cursor'Class) + (This : in Graph; + Position : in Cursor) return Graph_Iterators.Reversible_Iterator'Class; function Iterate_Choice - (This : in Parse_Graph; + (This : in Graph; Func : in Choosing_Function) return Graph_Iterators.Forward_Iterator'Class; @@ -326,63 +412,166 @@ package Packrat.Graphs is private - type Node is new My_Interfaces.Node with null record; + subtype Node_Index is Positive; + subtype Extended_Node_Index is Natural; + + package Index_Vectors is new Ada.Containers.Vectors + (Index_Type => Positive, + Element_Type => Node_Index); + + + + + type Choice_Down is record + From : Extended_Node_Index; + Choice : Natural; + end record; + + function "<" + (Left, Right : in Choice_Down) + return Boolean; + + package Choice_Down_Vectors is new Ada.Containers.Vectors + (Index_Type => Positive, + Element_Type => Choice_Down); + + + + + package Choice_Maps is new Ada.Containers.Ordered_Maps + (Key_Type => Node_Index, + Element_Type => Natural); + + package Edge_Down_Maps is new Ada.Containers.Ordered_Maps + (Key_Type => Choice_Down, + Element_Type => Index_Vectors.Vector, + "=" => Index_Vectors."="); + + package Edge_Up_Maps is new Ada.Containers.Ordered_Maps + (Key_Type => Node_Index, + Element_Type => Index_Vectors.Vector, + "=" => Index_Vectors."="); + + + + + type Element_Array_Access is access Element_Array; + + type Elem_Wrapper is new Ada.Finalization.Controlled with record + Data : Element_Array_Access; + end record; + + overriding procedure Adjust + (This : in out Elem_Wrapper); + + overriding procedure Finalize + (This : in out Elem_Wrapper); + + function Wrap + (Data : in Element_Array) + return Elem_Wrapper; + + Empty_Wrapper : constant Elem_Wrapper := + (Ada.Finalization.Controlled with Data => null); + + type Node_Kind is (Null_Node, Branch_Node, Leaf_Node); + + type Node is record + Kind : Node_Kind; + Ident : Label_Enum; + Content : Elem_Wrapper; + Start : Positive; + Finish : Natural; + end record; + + package Node_Vectors is new Ada.Containers.Vectors + (Index_Type => Node_Index, + Element_Type => Node); + + - type Cursor is new My_Interfaces.Cursor with null record; - type Iter_Cursor (Data : not null access Cursor) is null record; + type Cursor is record + My_Graph : access Graph; + Index : Extended_Node_Index; + Track : Choice_Down_Vectors.Vector; + end record; + - type Parse_Graph is new My_Interfaces.Graph with null record; + type Graph is tagged record + Root_List : Index_Vectors.Vector; + Node_List : Node_Vectors.Vector; + Add_Place : Node_Index; + Choices : Choice_Maps.Map; + Down_Edges : Edge_Down_Maps.Map; + Up_Edges : Edge_Up_Maps.Map; + end record; - No_Node : constant Node := (My_Interfaces.Node with null record); - No_Position_Actual : constant Cursor := (My_Interfaces.Cursor with null record); - No_Position : constant My_Interfaces.Cursor'Class := No_Position_Actual; - Empty_Graph : constant Parse_Graph := (My_Interfaces.Graph with null record); + No_Node : constant Node := + (Kind => Null_Node, + Ident => Label_Enum'First, + Content => Empty_Wrapper, + Start => 1, + Finish => 0); + + No_Position : constant Cursor := + (My_Graph => null, + Index => 0, + Track => Choice_Down_Vectors.Empty_Vector); + + Empty_Graph : constant Graph := + (Root_List => Index_Vectors.Empty_Vector, + Node_List => Node_Vectors.Empty_Vector, + Add_Place => 1, + Choices => Choice_Maps.Empty_Map, + Down_Edges => Edge_Down_Maps.Empty_Map, + Up_Edges => Edge_Up_Maps.Empty_Map); type Forward_Iterator is new Graph_Iterators.Forward_Iterator with record - My_Container : access Parse_Graph; - My_Position : Cursor; + Position : Cursor; end record; overriding function First (Object : in Forward_Iterator) - return Iter_Cursor; + return Cursor; overriding function Next (Object : in Forward_Iterator; - Place : in Iter_Cursor) - return Iter_Cursor; + Place : in Cursor) + return Cursor; + + + type Reversible_Iterator is new Graph_Iterators.Reversible_Iterator with record - My_Container : access Parse_Graph; - My_Position : Cursor; + Position : Cursor; end record; overriding function First (Object : in Reversible_Iterator) - return Iter_Cursor; + return Cursor; overriding function Next (Object : in Reversible_Iterator; - Place : in Iter_Cursor) - return Iter_Cursor; + Place : in Cursor) + return Cursor; overriding function Last (Object : in Reversible_Iterator) - return Iter_Cursor; + return Cursor; overriding function Previous (Object : in Reversible_Iterator; - Place : in Iter_Cursor) - return Iter_Cursor; + Place : in Cursor) + return Cursor; end Packrat.Graphs; |