1 files changed, 2 insertions, 207 deletions
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<T: GraphLabel> {
-    label: T,
-    status: ForestLabelType,
-}
-
-impl<T: GraphLabel> std::fmt::Display for ForestLabel<T> {
-    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<T: GraphLabel> ForestLabel<T> {
-    /// 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<usize> {
-        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<F>(self, forest: &F) -> Result<Self, ForestLabelError>
-    where
-        F: LabelGraph<ForestLabel<T>>,
-    {
-        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<Self, ForestLabelError> {
-        if self.clone_index().is_some() {
-            Err(ForestLabelError::PackClone)
-        } else {
-            let new_label = Self {
-                status: ForestLabelType::Packed,
-                ..self
-            };
-
-            Ok(new_label)
-        }
-    }
-}
-
-impl<T: GraphLabel> From<T> for ForestLabel<T> {
-    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<T: GraphLabel>: ParentsGraph + LabelGraph<ForestLabel<T>> {
-    /// The type of errors for operations on the forest.
-    type Error: std::error::Error + From<GError> + From<ForestLabelError>;
-
-    /// Return the root of the forest.
-    ///
-    /// A forest without a root is regarded as empty.
-    fn root(&self) -> Option<usize>;
-
-    /// 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<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>
-    where
-        F: Borrow<Self>;
-
-    /// Extend the forest by adjoining another forest at a given node.
-    fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error>
-    where
-        F: Borrow<Self>;
-
-    /// 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<usize, Self::Error>;
-}
-
 pub mod default;
 
 pub mod genins;