diff options
Diffstat (limited to 'forest/src/bytes.rs')
| -rw-r--r-- | forest/src/bytes.rs | 261 |
1 files changed, 243 insertions, 18 deletions
diff --git a/forest/src/bytes.rs b/forest/src/bytes.rs index d0d7e1e..6e854c8 100644 --- a/forest/src/bytes.rs +++ b/forest/src/bytes.rs @@ -65,18 +65,18 @@ //! Each label has 3 parts: //! //! 1. Status: either Packed, Cloned, or Plain. If the node is -//! cloned, it has a clone index. So in total this part occupies 1 -//! byte for the status and 8 bytes for the clone index. +//! cloned, it has a clone index. So in total this part occupies 1 +//! byte for the status and 8 bytes for the clone index. //! 2. Start and end: the range in the input sentence. We just store -//! two numbers here. Hence this part occupies 16 bytes. +//! two numbers here. Hence this part occupies 16 bytes. //! 3. Grammar label: either a terminal, a non-terminal, or a rule. -//! Each variant needs a number to speify its index. So in total this -//! part occupies 1 byte for the variant discriminant and 8 bytes for -//! the number. +//! Each variant needs a number to speify its index. So in total +//! this part occupies 1 byte for the variant discriminant and 8 +//! bytes for the number. //! //! To sum up, each label occupies 34 bytes. -use super::Forest; +use super::{Forest, ForestLabel, ForestLabelType}; use grammar::{GrammarLabel, GrammarLabelType, TNT}; use graph::error::Error as GError; @@ -95,13 +95,16 @@ pub fn forest_to_bytes<F: Forest<GrammarLabel>>(forest: &F) -> Vec<u8> { let total_degree: usize = degrees.iter().copied().sum(); - let len: usize = 8 // total number of bytes at the start + let label_offset: usize = 8 // total number of bytes = len + 3 // special mark + 8 // number of nodes + 8 // offset of labels + 16 * nodes_len // degree & offset for each node + 8 * total_degree // children of each node - + 34 * nodes_len // labels + ; + + let len: usize = label_offset // see that variable for details. + + 34 * nodes_len // labels ; // Then fill in the bytes. @@ -113,17 +116,18 @@ pub fn forest_to_bytes<F: Forest<GrammarLabel>>(forest: &F) -> Vec<u8> { bytes.extend(len.to_be_bytes()); bytes.extend([114, 101, 112]); // rep bytes.extend(nodes_len.to_be_bytes()); - bytes.extend((len - 34 * nodes_len).to_be_bytes()); + bytes.extend(label_offset.to_be_bytes()); - let mut accumulated: usize = 0; + let mut accumulated: usize = 8 + 3 + 8 + 8 + 16 * nodes_len; // Then degrees and offsets for degree in degrees.iter().copied() { bytes.extend(degree.to_be_bytes()); - bytes.extend((8 + 3 + 8 + 8 + 16 * nodes_len + 8 * accumulated).to_be_bytes()); + bytes.extend(accumulated.to_be_bytes()); + // bytes.extend((8 + 3 + 8 + 8 + 16 * nodes_len + 8 * accumulated).to_be_bytes()); - accumulated += degree; + accumulated += 8 * degree; } // Then the children @@ -337,43 +341,147 @@ impl TryFrom<Vec<u8>> for BytesForest { pub struct BytesChildrenIter<'a> { vec: &'a [u8], offset: usize, + label_offset: usize, degree: usize, current: usize, } +/// The delegation of iterators for children and labels of nodes. +#[derive(Debug, Clone)] +pub struct BytesLabelChildrenIter<'a>(BytesChildrenIter<'a>); + +impl<'a> Iterator for BytesLabelChildrenIter<'a> { + type Item = (ForestLabel<GrammarLabel>, usize); + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + let iter = &self.0; + + if iter.current >= iter.degree { + return None; + } + + let len = iter.vec.len(); + + if iter.offset + 8 * iter.degree >= len { + dbg!(); + return None; + } + + if iter.label_offset + 34 * iter.degree > len { + dbg!(); + return None; + } + + let result_index = usize::from_be_bytes( + (&iter.vec[(iter.offset + 8 * iter.current)..(iter.offset + 8 * iter.current + 8)]) + .try_into() + .ok()?, + ); + + let result_label = read_label( + &iter.vec[(iter.label_offset + iter.current * 34) + ..(iter.label_offset + iter.current * 34 + 34)], + ) + .ok()?; + + self.0.current += 1; + + Some((result_label, result_index)) + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + (self.0.degree, Some(self.0.degree)) + } +} + +impl<'a> ExactSizeIterator for BytesLabelChildrenIter<'a> { + #[inline] + fn len(&self) -> usize { + self.0.degree + } +} + impl<'a> Iterator for BytesChildrenIter<'a> { type Item = usize; + #[inline] fn next(&mut self) -> Option<Self::Item> { - if self.current + 1 >= self.degree { + if self.current >= self.degree { return None; } let len = self.vec.len(); - if self.offset + 8 * self.degree > len { + if self.offset + 8 * self.degree >= len { dbg!(); return None; } - Some(usize::from_be_bytes( + let result = usize::from_be_bytes( (&self.vec[(self.offset + 8 * self.current)..(self.offset + 8 * self.current + 8)]) .try_into() .ok()?, - )) + ); + + self.current += 1; + + Some(result) } + #[inline] fn size_hint(&self) -> (usize, Option<usize>) { (self.degree, Some(self.degree)) } } impl<'a> ExactSizeIterator for BytesChildrenIter<'a> { + #[inline] fn len(&self) -> usize { self.degree } } +fn read_label(data: &[u8]) -> Result<ForestLabel<GrammarLabel>, GError> { + let len = data.len(); + + if len < 34 { + return Err(GError::IndexOutOfBounds(34, len)); + } + + let pack_status: ForestLabelType = match data.first().copied().unwrap() { + 0 => ForestLabelType::Plain, + 1 => ForestLabelType::Packed, + _ => ForestLabelType::Cloned(usize::from_be_bytes( + data[1..9].try_into().expect("should not happen"), + )), + }; + + let start = usize::from_be_bytes(data[9..17].try_into().expect("should not happen")); + let end = usize::from_be_bytes(data[17..25].try_into().expect("should not happen")); + + let grammarlabeltype = match data.get(25).unwrap() { + 0 => GrammarLabelType::TNT(TNT::Ter(usize::from_be_bytes( + data[26..34].try_into().expect("should not happen"), + ))), + 1 => GrammarLabelType::TNT(TNT::Non(usize::from_be_bytes( + data[26..34].try_into().expect("should not happen"), + ))), + _ => GrammarLabelType::Rule(usize::from_be_bytes( + data[26..34].try_into().expect("should not happen"), + )), + }; + + let label = if end == 0 { + GrammarLabel::new(grammarlabeltype, start) + } else { + GrammarLabel::new_closed(grammarlabeltype, start, end) + }; + + Ok(ForestLabel::new(label, pack_status)) +} + impl graph::Graph for BytesForest { type Iter<'a> = BytesChildrenIter<'a> where @@ -404,6 +512,8 @@ impl graph::Graph for BytesForest { .unwrap(), ); + let label_offset = usize::from_be_bytes((&self.bytes[19..27]).try_into().unwrap()); + let current = 0; let vec = &self.bytes; @@ -411,6 +521,7 @@ impl graph::Graph for BytesForest { Ok(BytesChildrenIter { vec, offset, + label_offset, degree, current, }) @@ -453,4 +564,118 @@ impl graph::Graph for BytesForest { } } -// TODO: Implement labelgraph +impl graph::VLabelGraph<ForestLabel<GrammarLabel>> for BytesForest { + type TupleIter<'a> = BytesLabelChildrenIter<'a> + where + Self: 'a, + ForestLabel<GrammarLabel>: 'a; + + fn verlabren_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> { + if node_id >= self.nodes_len { + return Err(GError::IndexOutOfBounds(node_id, self.nodes_len)); + } + + let degree = usize::from_be_bytes( + (&self.bytes[(27 + 16 * node_id)..(35 + 16 * node_id)]) + .try_into() + .unwrap(), + ); + + let offset = usize::from_be_bytes( + (&self.bytes[(35 + 16 * node_id)..(43 + 16 * node_id)]) + .try_into() + .unwrap(), + ); + + let label_offset = usize::from_be_bytes((&self.bytes[19..27]).try_into().unwrap()); + + let current = 0; + + let vec = &self.bytes; + + Ok(BytesLabelChildrenIter(BytesChildrenIter { + vec, + offset, + label_offset, + degree, + current, + })) + } +} + +impl graph::LabelGraph<ForestLabel<GrammarLabel>> for BytesForest { + fn query_label(&self, label: ForestLabel<GrammarLabel>) -> Option<usize> { + use graph::Graph; + let nodes_len = self.nodes_len(); + + for index in 0..nodes_len { + let index_label = read_label( + &self.bytes[(self.offset + index * 34)..(self.offset + index * 34 + 34)], + ) + .ok()?; + + if index_label == label { + return Some(index); + } + } + + None + } + + fn vertex_label(&self, node_id: usize) -> Result<Option<ForestLabel<GrammarLabel>>, GError> { + read_label(&self.bytes[(self.offset + node_id * 34)..(self.offset + node_id * 34 + 34)]) + .map(Some) + } + + type Iter<'a> = std::iter::Empty<usize> + where + Self: 'a; + + type TupleIter<'a>=std::iter::Empty<(ForestLabel<GrammarLabel>, usize)> + where + Self: 'a, + ForestLabel<GrammarLabel>: 'a; + + type LabelIter<'a> = std::iter::Empty<(&'a ForestLabel<GrammarLabel>, std::iter::Empty<usize>)> + where + Self: 'a, + ForestLabel<GrammarLabel>: 'a; + + type EdgeLabelIter<'a> = std::iter::Empty<ForestLabel<GrammarLabel>> + where + Self: 'a, + ForestLabel<GrammarLabel>: 'a; + + fn edge_label( + &self, + _source: usize, + _target: usize, + ) -> Result<Self::EdgeLabelIter<'_>, GError> { + unimplemented!("bytes forests do not have edge labels") + } + + fn find_children_with_label( + &self, + _node_id: usize, + _label: &ForestLabel<GrammarLabel>, + ) -> Result<<Self as graph::LabelGraph<ForestLabel<GrammarLabel>>>::Iter<'_>, GError> { + unimplemented!("bytes forests do not have edge labels") + } + + fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, GError> { + unimplemented!("bytes forests do not have edge labels") + } + + fn tuples_of(&self, _node_id: usize) -> Result<Self::TupleIter<'_>, GError> { + unimplemented!("bytes forests do not have edge labels") + } + + fn has_edge_label( + &self, + _node_id: usize, + _label: &ForestLabel<GrammarLabel>, + _target: usize, + ) -> Result<bool, GError> { + unimplemented!("bytes forests do not have edge labels") + } +} |