Iteration specifications added for Parse_Graphs

4 files changed, 460 insertions, 50 deletions

diff --git a/packrat_parser_lib_notes.txt b/packrat_parser_lib_notes.txt
index 333b999..2a8e0cc 100644
--- a/packrat_parser_lib_notes.txt
+++ b/packrat_parser_lib_notes.txt
@@ -315,9 +315,20 @@ Packrat.Interfaces
    ends up being necessary for parsing
 
 List of interfaces:
+Node
+ - Leaf (constructor)
+ - Branch (constructor)
+ - Is_Leaf
+ - Is_Branch
+ - Label
+ - Elements
+ - Start
+ - Finish
+
 Cursor
  - Is_Nothing
  - Depth
+ - Is_Node
  - Is_Root
  - Is_Branch
  - Is_Leaf
@@ -341,8 +352,7 @@ Cursor
 
 Directed_Acyclic_Graph
  - Contains
- - Leaf
- - Branch
+ - Singleton (constructor)
  - Is_Empty
  - Is_Ambiguous
  - Node_Count
@@ -363,20 +373,22 @@ Packrat.Graphs
  - can be replaced with a user-supplied type, assuming proper care is taken to avoid exponential issues
 
 List_of_datatypes:
-Graph_Cursor
- - (implements all of Interfaces.Cursor)
-Parse_Graph
- - (implements all of Interfaces.Directed_Acyclic_Graph)
+Node (implements all of Interfaces.Node)
+Node_Reference
+Cursor (implements all of Interfaces.Cursor)
+Iter_Cursor (wraps a Cursor, necessary for iteration)
+Parse_Graph (implements all of Interfaces.Directed_Acyclic_Graph)
+Choosing_Function (used in Iterate_Choice)
 
 List of funcs:
 Debug_String
 
+Node_At
+
+Is_Valid_Node
 Iterate
-Reverse_Iterate
+Iterate_Subtree
 Iterate_Choice
-Reverse_Iterate_Choice
-Iterate_SUbtree
-Iterate_Subtree_Choice
 
 
 
diff --git a/src/packrat-graphs.adb b/src/packrat-graphs.adb
index 2cf74b3..1206a89 100644
--- a/src/packrat-graphs.adb
+++ b/src/packrat-graphs.adb
@@ -3,6 +3,86 @@
 package body Packrat.Graphs is
 
 
+
+    function Leaf
+           (New_Item : in Element_Array;
+            Start    : in Positive;
+            Finish   : in Natural)
+        return Node is
+    begin
+        return This : Node;
+    end Leaf;
+
+
+    function Branch
+           (Label  : in Label_Enum;
+            Start  : in Positive;
+            Finish : in Natural)
+        return Node is
+    begin
+        return This : Node;
+    end Branch;
+
+
+
+
+
+    function Is_Leaf
+           (This : in Node)
+        return Boolean is
+    begin
+        return False;
+    end Is_Leaf;
+
+
+    function Is_Branch
+           (This : in Node)
+        return Boolean is
+    begin
+        return False;
+    end Is_Branch;
+
+
+
+
+
+    function Label
+           (This : in Node)
+        return Label_Enum is
+    begin
+        return Label_Enum'First;
+    end Label;
+
+
+    function Elements
+           (This : in Node)
+        return Element_Array
+    is
+        Empty : Element_Array (1 .. 0);
+    begin
+        return Empty;
+    end Elements;
+
+
+    function Start
+           (This : in Node)
+        return Positive is
+    begin
+        return 1;
+    end Start;
+
+
+    function Finish
+           (This : in Node)
+        return Natural is
+    begin
+        return 0;
+    end Finish;
+
+
+
+
+
     function Is_Nothing
            (Position : in Cursor)
         return Boolean is
@@ -22,6 +102,14 @@ package body Packrat.Graphs is
     end Depth;
 
 
+    function Is_Node
+           (Position : in Cursor)
+        return Boolean is
+    begin
+        return False;
+    end Is_Node;
+
+
     function Is_Root
            (Position : in Cursor)
         return Boolean is
@@ -241,24 +329,21 @@ package body Packrat.Graphs is
 
 
 
-    function Leaf
-           (New_Item : in Element_Array;
-            Start    : in Positive;
-            Finish   : in Natural)
+    function Singleton
+           (Input : in My_Interfaces.Node'Class)
         return Parse_Graph is
     begin
         return This : Parse_Graph;
-    end Leaf;
+    end Singleton;
 
 
-    function Branch
-           (Label  : in Label_Enum;
-            Start  : in Positive;
-            Finish : in Natural)
-        return Parse_Graph is
+    function Node_At
+           (Container : in Parse_Graph;
+            Position  : in My_Interfaces.Cursor'Class)
+        return Node_Reference is
     begin
-        return This : Parse_Graph;
-    end Branch;
+        return (Data => No_Node'Unrestricted_Access);
+    end Node_At;
 
 
 
@@ -366,6 +451,111 @@ package body Packrat.Graphs is
     end Find;
 
 
+
+
+
+    function Is_Valid_Node
+           (Position : in Iter_Cursor)
+        return Boolean is
+    begin
+        return Position.Data.Is_Node;
+    end Is_Valid_Node;
+
+
+
+
+
+    function Iterate
+           (This : in Parse_Graph)
+        return Graph_Iterators.Reversible_Iterator'Class is
+    begin
+        return Result : Reversible_Iterator do
+            Result.My_Container := This'Unrestricted_Access;
+            Result.My_Position := No_Position;
+        end return;
+    end Iterate;
+
+
+    function Iterate_Subtree
+           (This     : in Parse_Graph;
+            Position : in My_Interfaces.Cursor'Class)
+        return Graph_Iterators.Reversible_Iterator'Class is
+    begin
+        return Result : Reversible_Iterator do
+            Result.My_Container := This'Unrestricted_Access;
+            Result.My_Position := No_Position;
+        end return;
+    end Iterate_Subtree;
+
+
+    function Iterate_Choice
+           (This : in Parse_Graph;
+            Func : in Choosing_Function)
+        return Graph_Iterators.Forward_Iterator'Class is
+    begin
+        return Result : Forward_Iterator do
+            Result.My_Container := This'Unrestricted_Access;
+            Result.My_Position := No_Position;
+        end return;
+    end Iterate_Choice;
+
+
+
+
+
+    function First
+           (Object : in Forward_Iterator)
+        return Iter_Cursor is
+    begin
+        return (Data => Object.My_Position'Unrestricted_Access);
+    end First;
+
+    function Next
+           (Object : in Forward_Iterator;
+            Place  : in Iter_Cursor)
+        return Iter_Cursor is
+    begin
+        return (Data => Object.My_Position'Unrestricted_Access);
+    end Next;
+
+
+
+
+
+    function First
+           (Object : in Reversible_Iterator)
+        return Iter_Cursor is
+    begin
+        return (Data => Object.My_Position'Unrestricted_Access);
+    end First;
+
+
+    function Next
+           (Object : in Reversible_Iterator;
+            Place  : in Iter_Cursor)
+        return Iter_Cursor is
+    begin
+        return (Data => Object.My_Position'Unrestricted_Access);
+    end Next;
+
+
+    function Last
+           (Object : in Reversible_Iterator)
+        return Iter_Cursor is
+    begin
+        return (Data => Object.My_Position'Unrestricted_Access);
+    end Last;
+
+
+    function Previous
+           (Object : in Reversible_Iterator;
+            Place  : in Iter_Cursor)
+        return Iter_Cursor is
+    begin
+        return (Data => Object.My_Position'Unrestricted_Access);
+    end Previous;
+
+
 end Packrat.Graphs;
 
 
diff --git a/src/packrat-graphs.ads b/src/packrat-graphs.ads
index 4095360..877be3a 100644
--- a/src/packrat-graphs.ads
+++ b/src/packrat-graphs.ads
@@ -1,5 +1,10 @@
 
 
+with
+
+    Ada.Iterator_Interfaces;
+
+
 generic
     type Label_Enum is (<>);
     type Element is private;
@@ -8,10 +13,70 @@ generic
 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 Parse_Graph is new My_Interfaces.Graph with private;
+    type Iter_Cursor (Data : not null access Cursor) is private
+        with Implicit_Dereference => Data;
+
+
+    type Parse_Graph is new My_Interfaces.Graph with private
+        with Default_Iterator  => Iterate,
+             Iterator_Element  => Node_Reference,
+             Variable_Indexing => Node_At;
+
+
+
+
+    No_Position : constant Cursor;
+
+    Empty_Graph : constant Parse_Graph;
+
+
+
+
+    function Leaf
+           (New_Item : in Element_Array;
+            Start    : in Positive;
+            Finish   : in Natural)
+        return Node;
+
+    function Branch
+           (Label  : in Label_Enum;
+            Start  : in Positive;
+            Finish : in Natural)
+        return Node;
+
+
+    function Is_Leaf
+           (This : in Node)
+        return Boolean;
+
+    function Is_Branch
+           (This : in Node)
+        return Boolean;
+
+
+    function Label
+           (This : in Node)
+        return Label_Enum;
+
+    function Elements
+           (This : in Node)
+        return Element_Array;
+
+    function Start
+           (This : in Node)
+        return Positive;
+
+    function Finish
+           (This : in Node)
+        return Natural;
 
 
 
@@ -27,6 +92,10 @@ package Packrat.Graphs is
            (Position : in Cursor)
         return Natural;
 
+    function Is_Node
+           (Position : in Cursor)
+        return Boolean;
+
     function Is_Root
            (Position : in Cursor)
         return Boolean;
@@ -39,6 +108,9 @@ package Packrat.Graphs is
            (Position : in Cursor)
         return Boolean;
 
+
+
+
     function Label
            (Position : in Cursor)
         return Label_Enum;
@@ -47,9 +119,6 @@ package Packrat.Graphs is
            (Position : in Cursor)
         return Element_Array;
 
-
-
-
     function Start
            (Position : in Cursor)
         return Positive;
@@ -145,17 +214,16 @@ package Packrat.Graphs is
 
 
 
-    function Leaf
-           (New_Item : in Element_Array;
-            Start    : in Positive;
-            Finish   : in Natural)
+    function Singleton
+           (Input : in My_Interfaces.Node'Class)
         return Parse_Graph;
 
-    function Branch
-           (Label  : in Label_Enum;
-            Start  : in Positive;
-            Finish : in Natural)
-        return Parse_Graph;
+    function Node_At
+           (Container : in Parse_Graph;
+            Position  : in My_Interfaces.Cursor'Class)
+        return Node_Reference
+    with Pre =>
+            Position.Is_Node;
 
 
 
@@ -221,15 +289,101 @@ package Packrat.Graphs is
 
 
 
+    function Is_Valid_Node
+           (Position : in Iter_Cursor)
+        return Boolean;
+
+
+
+
+    package Graph_Iterators is
+        new Ada.Iterator_Interfaces (Iter_Cursor, Is_Valid_Node);
+
+    type Choosing_Function is access function
+           (Position : in Cursor)
+        return Natural;
+
+
+
+
+    function Iterate
+           (This : in Parse_Graph)
+        return Graph_Iterators.Reversible_Iterator'Class;
+
+    function Iterate_Subtree
+           (This     : in Parse_Graph;
+            Position : in My_Interfaces.Cursor'Class)
+        return Graph_Iterators.Reversible_Iterator'Class;
+
+    function Iterate_Choice
+           (This : in Parse_Graph;
+            Func : in Choosing_Function)
+        return Graph_Iterators.Forward_Iterator'Class;
+
+
+
+
 private
 
 
+    type Node is new My_Interfaces.Node with null record;
+
     type Cursor is new My_Interfaces.Cursor with null record;
 
+    type Iter_Cursor (Data : not null access Cursor) is null record;
 
     type Parse_Graph is new My_Interfaces.Graph with null record;
 
 
+
+
+    No_Node : constant Node := (My_Interfaces.Node with null record);
+
+    No_Position : constant Cursor := (My_Interfaces.Cursor with null record);
+
+    Empty_Graph : constant Parse_Graph := (My_Interfaces.Graph with null record);
+
+
+
+
+    type Forward_Iterator is new Graph_Iterators.Forward_Iterator with record
+        My_Container : access Parse_Graph;
+        My_Position  : Cursor;
+    end record;
+
+    overriding function First
+           (Object : in Forward_Iterator)
+        return Iter_Cursor;
+
+    overriding function Next
+           (Object : in Forward_Iterator;
+            Place  : in Iter_Cursor)
+        return Iter_Cursor;
+
+    type Reversible_Iterator is new Graph_Iterators.Reversible_Iterator with record
+        My_Container : access Parse_Graph;
+        My_Position  : Cursor;
+    end record;
+
+    overriding function First
+           (Object : in Reversible_Iterator)
+        return Iter_Cursor;
+
+    overriding function Next
+           (Object : in Reversible_Iterator;
+            Place  : in Iter_Cursor)
+        return Iter_Cursor;
+
+    overriding function Last
+           (Object : in Reversible_Iterator)
+        return Iter_Cursor;
+
+    overriding function Previous
+           (Object : in Reversible_Iterator;
+            Place  : in Iter_Cursor)
+        return Iter_Cursor;
+
+
 end Packrat.Graphs;
 
 
diff --git a/src/packrat.ads b/src/packrat.ads
index 05a8e6a..d1fc9a0 100644
--- a/src/packrat.ads
+++ b/src/packrat.ads
@@ -191,6 +191,62 @@ package Packrat is
     package Interfaces is
 
 
+        type Node is interface;
+
+
+        function Leaf
+               (New_Item : in Element_Array;
+                Start    : in Positive;
+                Finish   : in Natural)
+            return Node is abstract
+        with Pre'Class =>
+                Finish + 1 >= Start,
+            Post'Class =>
+                Is_Leaf (Leaf'Result);
+
+        function Branch
+               (Label  : in Label_Enum;
+                Start  : in Positive;
+                Finish : in Natural)
+            return Node is abstract
+        with Pre'Class =>
+                Finish + 1 >= Start,
+            Post'Class =>
+                Is_Branch (Branch'Result);
+
+
+        function Is_Leaf
+               (This : in Node)
+            return Boolean is abstract;
+
+        function Is_Branch
+               (This : in Node)
+            return Boolean is abstract;
+
+
+        function Label
+               (This : in Node)
+            return Label_Enum is abstract
+        with Pre'Class =>
+                This.Is_Branch;
+
+        function Elements
+               (This : in Node)
+            return Element_Array is abstract
+        with Pre'Class =>
+                This.Is_Leaf;
+
+        function Start
+               (This : in Node)
+            return Positive is abstract;
+
+        function Finish
+               (This : in Node)
+            return Natural is abstract;
+
+
+
+
         type Cursor is interface;
 
 
@@ -205,12 +261,20 @@ package Packrat is
         with Pre'Class =>
                 not Position.Is_Nothing;
 
+        function Is_Node
+               (Position : in Cursor)
+            return Boolean is abstract
+        with Post'Class =>
+               (if Is_Node'Result then not Position.Is_Nothing);
+
         function Is_Root
                (Position : in Cursor)
             return Boolean is abstract
         with Post'Class =>
                (if Is_Root'Result then
-                Position.Parent.Is_Nothing and Position.Depth = 0);
+                not Position.Is_Nothing and
+                Position.Parent.Is_Nothing and
+                Position.Depth = 0);
 
         function Is_Branch
                (Position : in Cursor)
@@ -224,6 +288,7 @@ package Packrat is
         with Post'Class =>
                (if Is_Leaf'Result then not Position.Is_Nothing);
 
+
         function Label
                (Position : in Cursor)
             return Label_Enum is abstract
@@ -236,7 +301,6 @@ package Packrat is
         with Pre'Class =>
                 Position.Is_Leaf;
 
-
         function Start
                (Position : in Cursor)
             return Positive is abstract
@@ -370,21 +434,11 @@ package Packrat is
                (if Contains'Result then not Position.Is_Nothing);
 
 
-        function Leaf
-               (New_Item : in Element_Array;
-                Start    : in Positive;
-                Finish   : in Natural)
-            return Graph is abstract
-        with Post'Class =>
-                Leaf'Result.Node_Count = 1;
-
-        function Branch
-               (Label  : in Label_Enum;
-                Start  : in Positive;
-                Finish : in Natural)
+        function Singleton
+               (Input : in Node'Class)
             return Graph is abstract
         with Post'Class =>
-                Branch'Result.Node_Count = 1;
+                Singleton'Result.Node_Count = 1;
 
 
         function Is_Empty