From b586137f3475d5eb1fcfde2ba2f6b74e7c564cef Mon Sep 17 00:00:00 2001 From: Jed Barber Date: Wed, 22 Apr 2020 22:35:19 +1000 Subject: Factored notes for directed graph lib out to separate repo --- packrat_parser_lib_notes.txt | 104 +------------------------------------------ 1 file changed, 1 insertion(+), 103 deletions(-) (limited to 'packrat_parser_lib_notes.txt') 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 -- cgit