new startHEADmaster

Now I tested and discussed with claude, and had a working version of
this project.  The rest is to port the claude version to my own
writings.  So this serves as the starting point before that attempt.

In the new attempt the design is better, and a number of bugs were
found and supposedly fixed, so let us see how this goes at the end.

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")
+    }
+}