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/archive.txt | 207 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 207 insertions(+) create mode 100644 chain/src/item/archive.txt (limited to 'chain/src/item/archive.txt') diff --git a/chain/src/item/archive.txt b/chain/src/item/archive.txt new file mode 100644 index 0000000..fab3814 --- /dev/null +++ b/chain/src/item/archive.txt @@ -0,0 +1,207 @@ +// /// 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; +// } +// -- cgit v1.2.3-18-g5258