summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJed Barber <jjbarber@y7mail.com>2020-04-22 22:35:19 +1000
committerJed Barber <jjbarber@y7mail.com>2020-04-22 22:35:19 +1000
commitb586137f3475d5eb1fcfde2ba2f6b74e7c564cef (patch)
tree557d8d99c5d64d5ea0515b60cb239efea63bcc02
parent4b1face73de556041fea86c50e35e0ffaa3e8c74 (diff)
Factored notes for directed graph lib out to separate repo
-rw-r--r--packrat_parser_lib_notes.txt104
1 files changed, 1 insertions, 103 deletions
diff --git a/packrat_parser_lib_notes.txt b/packrat_parser_lib_notes.txt
index 67781cd..6aa0d0b 100644
--- a/packrat_parser_lib_notes.txt
+++ b/packrat_parser_lib_notes.txt
@@ -2,8 +2,6 @@
package structure:
-Ada.Containers.Directed_Graphs
-
Packrat
Packrat.Errors (nested)
Packrat.Tokens (nested, generic over contained array)
@@ -36,7 +34,6 @@ Packrat
Packrat.Errors
Packrat.Tokens
Packrat.Lexer
-Ada.Containers.Directed_Graphs
Packrat.Parse_Graphs
Packrat.Parser
Packrat.Text
@@ -188,108 +185,9 @@ List of funcs:
-Ada.Containers.Directed_Graphs
- - generic over discrete node type, array of node type, node label type, edge label type
- - implemented using the adjacancy list method
- - allows both nodes and edges to be labeled, one arbitrary type for each
- - nodes and edges don't *have* to be labeled
- - API in the style of the Ada Containers library
- - inspiration also taken from Haskell Data.Graph.Inductive.Graph
-
-List of types:
- Extended_Node_Type
- Edge_Type
- Edge_Type_Array
- Path (derived from the node array type)
- Graph
- Cursor
- Node_Label_Reference
- Constant_Node_Label_Reference
- Edge_Label_Reference
- Constant_Edge_Label_Reference
-
-Constants:
- No_Node (of Extended_Node_Type)
- No_Element (of Cursor)
- Empty_Graph (of Graph)
-
-List of Cursor funcs:
- Has_Element
- Element (cursor -> node)
-
- Equal_Subgraph
- Subgraph_Node_Count
-
- First_Parent
- Next_Parent
- Previous_Parent
- Last_Parent
- First_Child
- Next_Child
- Previous_Child
- Last_Child
-
-List of Graph funcs:
- "="
-
- Assign
- Copy
- Move
-
- Is_Empty
- Clear
- To_Cursor (node -> cursor)
-
- Node_Count (a measure of number of nodes in the graph)
- Edge_Count (a measure of number of edges in the graph)
-
- Nodes (array of all nodes in the graph)
- Edges (array of all edges in the graph)
- Node_Range (returns minimum and maximum of nodes in the graph)
- Unused_Nodes (returns an array of a specified number of nodes not used in the graph)
-
- Insert (add a node at a given position (with label), add an edge (with label), add multiple nodes, multiple edges)
- Append (add a node at the next available position (with label), return the node added)
- Delete (remove a node, an edge, multiple nodes, multiple edges, from the graph)
- Append_Label (give a node or an edge a label)
- Replace_Label
- Delete_Label (remove a label from a node or an edge)
- Delete_Subgraph
- Swap (switches two nodes in the graph)
-
- Context (returns all parents of a node, all children of the node)
- Labeled_Context (returns all parents of a node, the label of the node, and all the children of the node)
- Has_Label (predicates for testing if a node or edge has a label in the graph)
- Label (returns the label of a node or an edge if it has one)
- Label_Reference (accessor to a label)
- Constant_Label_Reference (constant accessor)
- Neighbors (two nodes are neighbors if they have edges in both directions)
- Parents (nodes with edges going into a node)
- Children (nodes with edges coming from a node)
- Outbound (edges going out of a node)
- Inbound (edges coming into a node)
- Outdegree (outbound degree of a node)
- Indegree (inbound degree of a node)
- Degree (degree of a node; how many other nodes are connected)
- Has_Edge (check whether two nodes are connected)
- Has_Labeled_Edge (check whether two nodes are connected with a labeled edge)
- Has_Neighbor (check whether two nodes are neighbors)
-
- Find (find a node or edge with a particular label)
- Find_In_Subgraph
- Contains (check whether a node or an edge is in the graph)
- Contains_Label (check if graph contains a particular node/edge label)
-
- Iterate
- Iterate_Subgraph
- Iterate_Children
- Iterate_Parents
-
-
-
-
Packrat.Parse_Graphs
- generic over an instantiated Packrat.Tokens and associated types
+ - based on Ada.Containers.Directed_Graphs in the directed-graph repo
- sets up the above directed graph lib for use as a parse graph that will avoid exponential blowup
- provides extra functions to merge graphs and iterate specific parsing choices