From b8a2d05a3c0d835556d5ddbd44e4a1e201302af5 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Thu, 10 Aug 2023 11:14:04 +0800 Subject: Move the trait `Forest` to the crate "forest". The purpose of this change is to share this trait with other crates, such as the forth-coming "semiring" crate that will be responsible for handling some simple semiring operations as well as the querying, in my plans. --- chain/src/item/mod.rs | 209 +------------------------------------------------- 1 file changed, 2 insertions(+), 207 deletions(-) (limited to 'chain/src/item/mod.rs') diff --git a/chain/src/item/mod.rs b/chain/src/item/mod.rs index ed41c61..54ea168 100644 --- a/chain/src/item/mod.rs +++ b/chain/src/item/mod.rs @@ -9,6 +9,8 @@ use graph::{error::Error as GError, GraphLabel, LabelGraph, Parent, ParentsGraph use std::borrow::Borrow; +use forest::{Forest, ForestLabel, ForestLabelError, ForestLabelType}; + /// A parent or a virtual segment. /// /// # Parent @@ -86,213 +88,6 @@ impl PaVi { } } -/// An internal type that indicates the status of a node as either a -/// packed, cloned, or plain node. -#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)] -pub enum ForestLabelType { - /// A packed node - Packed, - /// A plain node - #[default] - Plain, - /// A cloned node - Cloned(usize), -} - -impl std::fmt::Display for ForestLabelType { - fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { - match self { - Self::Packed => write!(f, "packed"), - Self::Plain => write!(f, "plain"), - Self::Cloned(index) => write!(f, "clone({index})"), - } - } -} - -/// A type that encodes the properties demanded by a forest. -#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)] -pub struct ForestLabel { - label: T, - status: ForestLabelType, -} - -impl std::fmt::Display for ForestLabel { - fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - if !matches!(self.status, ForestLabelType::Plain) { - write!(f, "{}, {}", self.label, self.status) - } else { - write!(f, "{}", self.label) - } - } -} - -/// The type of erros for converting forest labels. -#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)] -pub enum ForestLabelError { - /// Try to pack a cloned node. - PackClone, - /// Try to clone a packed node. - ClonePack, -} - -impl std::fmt::Display for ForestLabelError { - fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - match self { - Self::PackClone => write!(f, "cannot pack a cloned node"), - Self::ClonePack => write!(f, "cannot clone a packed node"), - } - } -} - -impl std::error::Error for ForestLabelError {} - -impl ForestLabel { - /// Construct a new label with the inner `label` and `status`. - pub fn new(label: T, status: ForestLabelType) -> Self { - Self { label, status } - } - - /// Retrieve the label. - pub fn label(&self) -> T { - self.label - } - - /// Return true if and only if this node is packed. - pub fn is_packed(&self) -> bool { - self.status == ForestLabelType::Packed - } - - /// Retrieve the optional clone index. - pub fn clone_index(&self) -> Option { - match self.status { - ForestLabelType::Cloned(index) => Some(index), - _ => None, - } - } - - /// Return true if and only if this node is a plain node. - pub fn is_plain(&self) -> bool { - self.status == ForestLabelType::Plain - } - - /// Try to clone a node. - pub fn clone(self, forest: &F) -> Result - where - F: LabelGraph>, - { - if self.is_packed() { - dbg!(); - Err(ForestLabelError::ClonePack) - } else { - let clone_index = if let Some(old_index) = self.clone_index() { - let mut new_index: usize = old_index + 1; - - let mut new_label = Self { - status: ForestLabelType::Cloned(new_index), - ..self - }; - - while forest.query_label(new_label).is_some() { - new_index += 1; - new_label = Self { - status: ForestLabelType::Cloned(new_index), - ..self - }; - } - - new_index - } else { - 0 - }; - - Ok(Self { - status: ForestLabelType::Cloned(clone_index), - ..self - }) - } - } - - /// Try to pack a node. - pub fn pack(self) -> Result { - if self.clone_index().is_some() { - Err(ForestLabelError::PackClone) - } else { - let new_label = Self { - status: ForestLabelType::Packed, - ..self - }; - - Ok(new_label) - } - } -} - -impl From for ForestLabel { - fn from(label: T) -> Self { - let status = ForestLabelType::default(); - Self { label, status } - } -} - -// REVIEW: Should we move this trait (and only this trait) to a -// separate crate, or is it enough to keep it here? - -/// The expected behaviours of an item derivation forest. -/// -/// Note that it requires only a subset of the functionalities of -/// labelled graphs. -pub trait Forest: ParentsGraph + LabelGraph> { - /// The type of errors for operations on the forest. - type Error: std::error::Error + From + From; - - /// Return the root of the forest. - /// - /// A forest without a root is regarded as empty. - fn root(&self) -> Option; - - /// Construct a forest consisting of one leaf node with the given - /// label. - fn new_leaf(label: T) -> Self; - - /// Transform the label at the given node. - fn transform_label( - &mut self, - node_id: usize, - transform: impl FnOnce(T) -> T, - ) -> Result<(), Self::Error>; - - /// Detect if the fragment is a prefix of the sub-forest rooted at - /// `node_id`. - fn is_prefix(&self, node_id: usize, fragment: F) -> Result - where - F: Borrow; - - /// Extend the forest by adjoining another forest at a given node. - fn plant(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error> - where - F: Borrow; - - /// Clone a node by making a new node and making all the nodes - /// that previously pointed to the old node now point to the new - /// node, and the new node points to the old node. Return the - /// index of the new node. However, if, and only if, - /// `no_new_clone` is `true`, do not make a new clone; instead - /// return the clone index that would be used if a new clone was - /// made. - /// - /// Also, `preserved_edges_num` many edges out of the old node - /// will be copied to be the children of the new node. - /// - /// The labels of the representing node and of the cloned node - /// will be handled automatically. - fn clone_node( - &mut self, - node_id: usize, - preserved_edges_num: usize, - no_new_clone: bool, - ) -> Result; -} - pub mod default; pub mod genins; -- cgit v1.2.3-18-g5258