From 9a317e56f8a6126583f7d0c431bf878d9b1fe7b1 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Sat, 8 Jul 2023 12:30:21 +0800 Subject: Finished the Emacs binding. Now the binding part is finished. What remains is a bug encountered when planting a fragment to the forest which intersects a packed node, which would lead to invalid forests. This will also cause problem when planting a packed fragment, but until now my testing grammars do not produce packed fragments, so this problem is not encountered yet. I am still figuring out efficient ways to solve this problem. --- graph/src/adlist.rs | 104 ++++++++++++++++++++++++++++++++++++++++++- graph/src/builder.rs | 5 +++ graph/src/labelled/binary.rs | 4 +- 3 files changed, 110 insertions(+), 3 deletions(-) (limited to 'graph/src') diff --git a/graph/src/adlist.rs b/graph/src/adlist.rs index ba3077e..d36b250 100644 --- a/graph/src/adlist.rs +++ b/graph/src/adlist.rs @@ -3,9 +3,16 @@ //! [`Graph`][super::Graph]. This data type represents graphs using //! adjacency lists internally. -use std::ops::{Deref, DerefMut}; +use std::{ + borrow::{Borrow, BorrowMut}, + ops::{Deref, DerefMut}, +}; -use crate::{builder::Builder, error::Error, ExtGraph, Graph}; +use crate::{ + builder::{Builder, BuilderMut}, + error::Error, + ExtGraph, Graph, +}; // #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)] // struct ALEdge { @@ -118,6 +125,99 @@ impl From>> for ALGraph { } } +/// A builder that modifies ALGraph in place. +#[derive(Debug)] +pub struct ALGBuilderMut<'a> { + graph: &'a mut ALGraph, +} + +impl<'a> std::ops::Deref for ALGBuilderMut<'a> { + type Target = ALGraph; + + fn deref(&self) -> &Self::Target { + self.graph.borrow() + } +} + +impl<'a> std::ops::DerefMut for ALGBuilderMut<'a> { + fn deref_mut(&mut self) -> &mut Self::Target { + self.graph.borrow_mut() + } +} + +impl<'a> BuilderMut for ALGBuilderMut<'a> { + type Label = (); + + type Graph = ALGraph; + + type ResultBuilder<'b> = ALGBuilderMut<'b> + where + Self::Label: 'b; + + fn from_graph_mut(graph: &mut Self::Graph) -> Self::ResultBuilder<'_> { + ALGBuilderMut { graph } + } + + fn add_vertex(&mut self, _label: Self::Label) -> usize { + self.nodes.push(Default::default()); + + self.nodes.len() - 1 + } + + fn add_edge(&mut self, source: usize, target: usize, _label: Self::Label) -> Result<(), Error> { + if self.graph.has_edge(source, target)? { + return Ok(()); + } + + self.graph + .nodes + .get_mut(source) + .unwrap() + .children + .push(target); + + Ok(()) + } + + fn append(&mut self, other: Self::Graph) { + let self_len = self.nodes_len(); + + self.graph + .nodes + .extend(other.nodes.into_iter().map(|mut node| { + for child in node.children.iter_mut() { + *child += self_len; + } + + node + })); + } + + fn set_label(&mut self, _node_id: usize, _label: Self::Label) -> Result<(), Error> { + Ok(()) + } + + fn remove_edge(&mut self, source: usize, target: usize, _predicate: F) -> Result<(), Error> + where + F: FnMut(Self::Label) -> bool, + { + let nodes_len = self.nodes.len(); + + let source_children = self + .nodes + .get_mut(source) + .ok_or(Error::IndexOutOfBounds(source, nodes_len))?; + + if !(0..nodes_len).contains(&target) { + return Err(Error::IndexOutOfBounds(target, nodes_len)); + } + + source_children.children.retain(|child| *child != target); + + Ok(()) + } +} + // Builder for this implementation of graph /// A builder for adjacency list graphs. diff --git a/graph/src/builder.rs b/graph/src/builder.rs index c5f9252..1278e26 100644 --- a/graph/src/builder.rs +++ b/graph/src/builder.rs @@ -82,6 +82,11 @@ pub trait BuilderMut { /// Add an edge from the source to the target. fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error>; + /// Append another graph to this builder. + fn append(&mut self, _other: Self::Graph) { + unimplemented!() + } + /// Set the label of an existing node to a new label. fn set_label(&mut self, node_id: usize, label: Self::Label) -> Result<(), Error>; diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs index 9f3afa8..ccbd5cb 100644 --- a/graph/src/labelled/binary.rs +++ b/graph/src/labelled/binary.rs @@ -214,9 +214,11 @@ impl Graph for PLGraph { let mut post = String::new(); - // FIXME: Find a way to print only used nodes. Maybe remove + // SOLVED: Find a way to print only used nodes. Maybe remove // unwanted edges from unwanted nodes, so that we can print // out only those used nodes. + // + // This is solved as we can extract the forest out. for node in self.nodes() { post.push_str(&format!( -- cgit v1.2.3-18-g5258