path: root/forest/src/iter/archive.txt

/// Archive of failed attempts

/// The label of a query graph.
///
/// Such a label is responsible for matching forest labels.
pub trait QueryLabel: GraphLabel {
    /// The type of labels this matches against.
    type Obj: GraphLabel;

    /// Determine whether or not a label matches this query label.
    fn matches(&self, label: Self::Obj, status: ForestLabelType) -> bool {
        let _ = label;
        let _ = status;

        false
    }

    /// Perform the query for one single query label.
    fn run<F>(
        &self,
        forest: &F,
        node: usize,
        packs: &mut Vec<(usize, usize)>,
    ) -> Result<Option<usize>, QRError>
    where
        F: LabelGraph<ForestLabel<<Self as QueryLabel>::Obj>>,
    {
        let mut dfs_stack: Vec<usize> = vec![node];

        let nodes_len = forest.nodes_len();

        while let Some(node) = dfs_stack.pop() {
            let label = match forest.vertex_label(node) {
                Ok(None) => return Err(QRError::NodeNoLabel(node)),
                Err(_) => return Err(QRError::IndexOutOfBounds(node, nodes_len)),
                Ok(Some(label)) => label,
            };

            let status = label.status();
            let label = label.label();

            if status == ForestLabelType::Packed {
                packs.push((node, 0));

                dfs_stack.extend(forest.children_of(node).unwrap().take(1));

                continue;
            }

            if self.matches(label, status) {
                return Ok(Some(node));
            }

            dfs_stack.extend(
                forest
                    .children_of(node)
                    .unwrap()
                    .collect::<Vec<_>>()
                    .into_iter()
                    .rev(),
            );
        }

        Ok(None)
    }
}

/// How should the current query skip nodes
#[derive(Debug, Clone, Copy, Default, Ord, PartialOrd, Hash, Eq, PartialEq)]
pub enum SkipState {
    /// Skip anything in the depth-first search
    Any,
    /// Skip siblings
    Sibling,
    /// Do not skip
    #[default]
    None,
}

impl std::fmt::Display for SkipState {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Any => write!(f, "skip anything"),
            Self::Sibling => write!(f, "skip siblings"),
            Self::None => write!(f, "no skipping"),
        }
    }
}

impl From<bool> for SkipState {
    fn from(value: bool) -> Self {
        if value {
            Self::Sibling
        } else {
            Self::None
        }
    }
}

/// A branch switch is of the form (n, m, v), where n means the n-th
/// node in the forest and m means the m-th child, and v is the vector
/// of children of the packed node.
#[derive(Debug, Clone, Default)]
pub struct BranchSwitch {
    n: usize,
    m: usize,
    v: Vec<usize>,
}

impl BranchSwitch {
    #[allow(dead_code)]
    fn new(n: usize, m: usize, v: Vec<usize>) -> Self {
        Self { n, m, v }
    }

    #[allow(dead_code)]
    fn node(&self) -> usize {
        self.n
    }

    #[allow(dead_code)]
    fn child(&self) -> Option<usize> {
        self.v.get(self.m).copied()
    }

    #[allow(dead_code)]
    fn advance(&mut self) -> bool {
        if self.m < self.v.len() {
            self.m += 1;

            return true;
        }

        false
    }
}

// REVIEW: Change the types into boxed slices so that we can guarantee
// no capacity is ever wasted.

/// The type of forests that would be walked.
///
/// In plain terms this is a preprocessed graph that provides some
/// extra information than a plain graph, which will be useful in
/// walking.
#[derive(Debug, Clone)]
#[allow(unused)]
pub struct QForest {
    current: Option<usize>,
    /// Just for example uses.
    pub dfs_next: Vec<usize>,
    /// Just for example uses.
    pub subtree_ranges: Vec<std::ops::RangeInclusive<usize>>,
    // /// Just for example uses.
    // pub next_branch: Vec<Option<usize>>,
    num_seen_switches: usize,
    /// Switches of branches are packed nodes along with the current
    /// index of the child.  One can switch to use a different child
    /// to "switch branches".
    pub branch_switches: Vec<BranchSwitch>,
    /// Map ordinary node numbering to depth-first numbering.
    ord_to_dfs: Vec<usize>,
    /// Map depth-first numbering to ordinary node numbering.
    dfs_to_ord: Vec<usize>,
    restriction: Option<usize>,
}

impl QForest {
    fn new(
        dfs_next: Vec<usize>,
        subtree_ranges: Vec<std::ops::RangeInclusive<usize>>,
        // next_branch: Vec<Option<usize>>,
        branch_switches: Vec<BranchSwitch>,
        ord_to_dfs: Vec<usize>,
        dfs_to_ord: Vec<usize>,
    ) -> Self {
        let current: Option<usize> = None;
        let restriction: Option<usize> = None;
        let num_seen_switches = 0usize;

        Self {
            current,
            dfs_next,
            subtree_ranges,
            // next_branch,
            num_seen_switches,
            branch_switches,
            restriction,
            ord_to_dfs,
            dfs_to_ord,
        }
    }

    /// Translate the node index from ordinary index to depth-first
    /// index.
    pub fn translate_to_dfs(&self, id: usize) -> Option<usize> {
        self.ord_to_dfs.get(id).copied()
    }

    /// Translate the node index from depth-first index to ordinary
    /// index.
    pub fn translate_from_dfs(&self, id: usize) -> Option<usize> {
        self.dfs_to_ord.get(id).copied()
    }
}

impl Default for QForest {
    fn default() -> Self {
        let current = Default::default();
        let dfs_next = Default::default();
        let subtree_ranges = Default::default();
        // let next_branch = Default::default();
        let branch_switches = Default::default();
        let restriction = Default::default();
        let num_seen_switches = 0usize;

        let ord_to_dfs = Default::default();
        let dfs_to_ord = Default::default();

        Self {
            current,
            dfs_next,
            subtree_ranges,
            // next_branch,
            num_seen_switches,
            branch_switches,
            restriction,
            ord_to_dfs,
            dfs_to_ord,
        }
    }
}

impl Queryable for QForest {
    fn current(&self) -> Option<usize> {
        self.current
    }

    fn next(&mut self) -> bool {
        let current = if let Some(current) = self.current {
            current
        } else {
            return false;
        };

        let mut next = if let Some(next) = self.dfs_next.get(current) {
            *next
        } else {
            return false;
        };

        match self.branch_switches.get(self.num_seen_switches) {
            Some(switch) if switch.node() == next => {
                if let Some(child) = switch.child() {
                    next = child;
                }

                self.num_seen_switches += 1;
            }
            _ => {}
        }

        let dfs_len = self.dfs_next.len();

        if (0..dfs_len).contains(&next) {
            self.current.replace(next);

            true
        } else {
            false
        }
    }

    fn next_branch(&mut self) -> bool {
        self.branch_switches.iter_mut().any(BranchSwitch::advance)

        // let current = if let Some(current) = self.current {
        //     current
        // } else {
        //     return false;
        // };

        // let next = if let Some(next) = self.next_branch.get(current).copied().flatten() {
        //     next
        // } else {
        //     return false;
        // };

        // self.current.replace(next);

        // true
    }

    fn restrict(&mut self, node: usize) -> bool {
        let range = if let Some(range) = self.subtree_ranges.get(node) {
            range
        } else {
            return false;
        };

        self.restriction.replace(node);

        let current = if let Some(current) = &self.current {
            current
        } else {
            return false;
        };

        range.contains(current)
    }
}

/// Calculate some extra information for later processing.
pub fn preprocess_forest<T, F>(forest: F, root: usize) -> Result<QForest, GError>
where
    T: GraphLabel,
    F: LabelGraph<ForestLabel<T>>,
{
    let forest_len = forest.nodes_len();

    // let current: Option<usize> = None;

    let mut dfs_next: Vec<usize> = (0..forest_len).map(|i| i + 1).collect();

    let mut subtree_ranges: Vec<std::ops::RangeInclusive<usize>> =
        (0..forest_len).map(|i| i..=i).collect();

    // let next_branch: Vec<Option<usize>> = std::iter::repeat(None).take(forest_len).collect();

    let mut branch_switches: Vec<BranchSwitch> = Vec::with_capacity(forest_len);

    // let restriction: Option<usize> = None;

    let mut dfs_to_ord: Vec<usize> = (0..forest_len).collect();
    let mut ord_to_dfs: Vec<usize> = (0..forest_len).collect();

    if forest.is_empty_node(root).unwrap_or(true) {
        if let Some(root_item) = dfs_next.get_mut(root) {
            *root_item = forest_len; // out of bounds
        }

        return Ok(QForest::new(
            // current,
            dfs_next,
            subtree_ranges,
            // next_branch,
            // restriction,
            branch_switches,
            ord_to_dfs,
            dfs_to_ord,
        ));
    }

    #[derive(Debug, Clone, Copy)]
    enum StackItem {
        Normal(usize),
        Reflection(usize),
    }

    impl From<usize> for StackItem {
        fn from(value: usize) -> Self {
            Self::Normal(value)
        }
    }

    impl StackItem {
        fn is_normal(&self) -> bool {
            matches!(self, Self::Normal(_))
        }

        fn get_value(&self) -> usize {
            match *self {
                StackItem::Normal(item) => item,
                StackItem::Reflection(item) => item,
            }
        }

        fn reflect(&self) -> Self {
            match self {
                StackItem::Normal(item) => Self::Reflection(*item),
                StackItem::Reflection(_) => *self,
            }
        }
    }

    let mut stack: Vec<StackItem> = Vec::with_capacity(forest_len);

    let mut prev = root;

    let mut children_vec: Vec<usize> = Vec::with_capacity(forest_len);

    stack.extend({
        children_vec.extend(forest.children_of(root)?);

        children_vec.iter().copied().rev().map(StackItem::from)
    });

    let mut seen_nodes: HashMap<usize, Option<usize>> = HashMap::with_capacity(forest_len);

    seen_nodes.insert(root, None);

    let mut dfs_order = 1usize;

    while let Some(top) = stack.pop() {
        let top_value = top.get_value();
        let top_label = forest
            .vertex_label(top_value)?
            .expect("node without label: {top_value}");
        if top.is_normal() {
            if let Some(prev_item) = dfs_next.get_mut(prev) {
                *prev_item = top_value;
            }

            if let std::collections::hash_map::Entry::Vacant(e) = seen_nodes.entry(top_value) {
                if let Some(item) = dfs_to_ord.get_mut(dfs_order) {
                    *item = top_value;
                }

                if let Some(item) = ord_to_dfs.get_mut(top_value) {
                    *item = dfs_order;
                }

                dfs_order += 1;

                stack.push(top.reflect());

                e.insert(top_label.clone_index().map(|_| prev));

                children_vec.clear();

                children_vec.extend(forest.children_of(top_value)?);

                stack.extend(children_vec.iter().copied().rev().map(StackItem::from));
            }

            prev = top_value;
        } else {
            if let Some(range) = subtree_ranges.get_mut(top_value) {
                let top_dfs = ord_to_dfs.get(top_value).copied().unwrap();
                let prev_dfs = ord_to_dfs.get(prev).copied().unwrap();

                *range = top_dfs..=prev_dfs;
            }

            // if top_is_cloned {
            //     if let Some(next) = stack.iter().rev().copied().find(StackItem::is_normal) {
            //         // update branches
            //         let top_dfs = ord_to_dfs.get(top_value).copied().unwrap();
            //         let prev_dfs = ord_to_dfs.get(prev).copied().unwrap();

            //         for i in (top_dfs + 1)..=prev_dfs {
            //             let j = dfs_to_ord.get(i).copied().unwrap();

            //             match next_branch.get_mut(j) {
            //                 Some(branch) if branch.is_none() => {
            //                     *branch = Some(next.get_value());
            //                 }

            //                 _ => {}
            //             }
            //         }
            //     }
            // }

            if !top_label.is_packed() {
                continue;
            }

            let top_children: Vec<usize> = forest.children_of(top_value)?.collect();

            if let Some(next) = stack.iter().rev().copied().find(StackItem::is_normal) {
                for child in top_children.iter() {
                    let child_prev = if let Some(Some(item)) = seen_nodes.get(child) {
                        *item
                    } else {
                        continue;
                    };

                    if let Some(prev_item) = dfs_next.get_mut(child_prev) {
                        *prev_item = next.get_value();

                        // dbg!(child_prev, next.get_value(), child);
                    }
                }
            }

            branch_switches.push(BranchSwitch::new(top_value, 0, top_children));
        }
    }

    Ok(QForest::new(
        // current,
        dfs_next,
        subtree_ranges,
        // next_branch,
        // restriction,
        branch_switches,
        ord_to_dfs,
        dfs_to_ord,
    ))
}

// TODO: The query graph needs the ability to jump to a parent and
// restore the querying contexts.

/// The type that represents queries as dependency graphs of query
/// labels.
///
/// The labels of vertices are query labels that match against forest
/// labels, whereas the labels of graphs indicate whether or not the
/// edge should allow skipping siblings before matching.
#[derive(Debug, Clone, Graph)]
pub struct Query<T: QueryLabel> {
    graph: SLGraph<SkipState>,
    vertex_labels: Vec<T>,
    root: Option<usize>,
}

impl<T: QueryLabel> Query<T> {
    /// Construct a new query from raw fields.
    pub fn new(graph: SLGraph<SkipState>, vertex_labels: Vec<T>, root: Option<usize>) -> Self {
        Self {
            graph,
            vertex_labels,
            root,
        }
    }

    /// Return the root of this query.
    ///
    /// This returns `None` if and only if the graph is empty.
    pub fn root(&self) -> Option<usize> {
        self.root
    }

    /// Return the label of the given node.
    ///
    /// This cannot be implemented as a method of the `LabelGraph`
    /// trait as the type differs from that of the labels.
    #[inline]
    pub fn label_of_vertex(&self, node: usize) -> Result<T, GError> {
        self.vertex_labels
            .get(node)
            .copied()
            .ok_or(GError::IndexOutOfBounds(node, self.vertex_labels.len()))
    }
}

impl<T: QueryLabel> Default for Query<T> {
    fn default() -> Self {
        let graph = Default::default();
        let vertex_labels = Vec::new();
        let root = None;

        Self {
            graph,
            vertex_labels,
            root,
        }
    }
}

// delegation of labelgraph

impl<T: QueryLabel> LabelGraph<SkipState> for Query<T> {
    type Iter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::Iter<'a>
    where
        Self: 'a;

    type TupleIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::TupleIter<'a>
    where
        Self: 'a;

    type LabelIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::LabelIter<'a>
    where
        Self: 'a;

    type EdgeLabelIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::EdgeLabelIter<'a>
    where
        Self: 'a;

    #[inline]
    fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, GError> {
        self.graph.edge_label(source, target)
    }

    fn find_children_with_label(
        &self,
        _node_id: usize,
        _label: &SkipState,
    ) -> Result<<Self as LabelGraph<SkipState>>::Iter<'_>, GError> {
        unimplemented!("Unsupported operation")
    }

    fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, GError> {
        unimplemented!("Unsupported operation")
    }

    #[inline]
    fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> {
        self.graph.tuples_of(node_id)
    }

    #[inline]
    fn has_edge_label(
        &self,
        node_id: usize,
        label: &SkipState,
        target: usize,
    ) -> Result<bool, GError> {
        self.graph.has_edge_label(node_id, label, target)
    }
}

#[derive(Debug, Clone)]
/// The type of errors that can occur when querying forests.
pub enum QRError {
    /// An index is out of bounds.
    IndexOutOfBounds(usize, usize),
    /// A node has no labels while it is required to have one.
    NodeNoLabel(usize),
    /// Encounter an invalid error in converting from an error of
    /// graphs.
    InvalidGraphError(GError),
    /// Not enough memory for vectors.
    NoMemory(std::collections::TryReserveError),
}

impl std::fmt::Display for QRError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            QRError::IndexOutOfBounds(n, b) => {
                write!(f, "index {n} out of bound {b}")
            }
            QRError::NodeNoLabel(n) => write!(f, "the node {n} has no label but should have one"),
            QRError::InvalidGraphError(g) => {
                write!(f, "an invalid error for forest iterators: {g}")
            }
            QRError::NoMemory(e) => write!(f, "not enough memory: {e}"),
        }
    }
}

impl std::error::Error for QRError {}

impl From<GError> for QRError {
    fn from(value: GError) -> Self {
        match value {
            GError::IndexOutOfBounds(n, b) => Self::IndexOutOfBounds(n, b),
            _ => Self::InvalidGraphError(value),
        }
    }
}

impl From<std::collections::TryReserveError> for QRError {
    fn from(value: std::collections::TryReserveError) -> Self {
        Self::NoMemory(value)
    }
}

/// An implementation of the forest iterator for querying purposes.
#[derive(Debug, Clone)]
pub struct QRun<T: QueryLabel> {
    /// The currently visited node.
    current: Option<Vec<usize>>,
    /// The queries dependency graph.
    query: Query<T>,
    /// The nodes of the query graph, in the depth-first order.
    query_dfs: Vec<usize>,
    /// The nodes of the forest, in the depth-first order.
    forest_dfs: Vec<usize>,
    /// The packed nodes that can be used to change to another branch
    /// if needed.
    ///
    /// The tuple is in the following format
    ///
    /// (forest_index, query_index),
    ///
    /// where the indicies are the indices of nodes, in the
    /// depth-first order, of the respective graphs.
    packs: Vec<(usize, usize)>,
}

impl<T: QueryLabel> Default for QRun<T> {
    fn default() -> Self {
        let current = Default::default();
        let query = Default::default();
        let packs = Default::default();

        let query_dfs = Default::default();
        let forest_dfs = Default::default();

        Self {
            current,
            query,
            query_dfs,
            forest_dfs,
            packs,
        }
    }
}

impl<T: QueryLabel> ForestIter for QRun<T> {
    #[inline]
    fn current(&self) -> Option<&[usize]> {
        self.current.as_ref().map(|v| &v[..])
    }

    type ForestLabel = <T as QueryLabel>::Obj;

    type Item<'a> = Option<&'a [usize]>
    where
        Self: 'a;

    type Error = QRError;

    #[allow(unused)]
    #[allow(clippy::collapsible_if)]
    fn next<F>(&mut self, forest: &F, root: usize) -> Result<State, Self::Error>
    where
        F: LabelGraph<ForestLabel<Self::ForestLabel>>,
    {
        #[derive(Debug, Clone, Copy, Default)]
        enum QueryIndex {
            /// A normal index
            Normal(usize),
            #[default]
            /// This means the query is now accepting anything.
            Empty,
        }

        macro_rules! query_match (
            ($index:expr, $label:expr, $status:expr) => {
                if let QueryIndex::Normal($index) = index {
                    self.query
                        .label_of_vertex(qtop)
                        .map(|q| q.matches($label, $status))
                } else {
                    Ok(true)
                }
            }
        );

        #[derive(Debug, Clone, Copy)]
        enum ForestIndex {
            /// A normal index
            Normal(usize),
            /// How many times we fallback in the query graph
            FallbackTimes(usize),
        }

        impl ForestIndex {
            fn is_normal(&self) -> bool {
                matches!(self, Self::Normal(_))
            }

            // /// Increment the index if it is normal, decrement it otherwise.
            // ///
            // /// Return `None` if the advanced index would be out of bounds.
            // fn advance_forest_index(&self, forest_len: usize) -> Option<Self> {
            //     match self {
            //         ForestIndex::Normal(index) => {
            //             if *index + 1 >= forest_len {
            //                 None
            //             } else {
            //                 Some(Self::Normal(*index + 1))
            //             }
            //         }
            //         ForestIndex::FallbackTimes(time) => {
            //             if *time == 0 {
            //                 None
            //             } else {
            //                 Some(Self::FallbackTimes(*time - 1))
            //             }
            //         }
            //     }
            // }

            fn get_index(&self, current_indices: &[usize]) -> Result<usize, QRError> {
                match self {
                    ForestIndex::Normal(index) => Ok(*index),
                    ForestIndex::FallbackTimes(time) => current_indices
                        .get(*time)
                        .copied()
                        .ok_or(QRError::IndexOutOfBounds(*time, current_indices.len())),
                }
            }

            fn get_query_index(&self) -> usize {
                match self {
                    ForestIndex::Normal(_) => 0,
                    ForestIndex::FallbackTimes(time) => *time,
                }
            }
        }

        let query_empty_p = self.query.is_empty();

        let query_len = self.query.nodes_len();
        let forest_len = forest.nodes_len();

        let query_root = if let Some(r) = self.query.root() {
            r
        } else {
            return Ok(State::Finish);
        };

        let orig_top: ForestIndex = match &self.current {
            Some(current) => {
                // re-starting search
                ForestIndex::FallbackTimes(current.len() - 1)
            }
            None => {
                // fresh new search
                ForestIndex::Normal(0)
            }
        };

        let mut top = orig_top.get_index(if let Some(current) = &self.current {
            &current[..]
        } else {
            &[]
        })?;

        let mut qtop = orig_top.get_query_index();

        let mut candidate_captures: Vec<usize> = self
            .current
            .clone()
            .unwrap_or_else(|| std::iter::repeat(0).take(query_len).collect());

        'search: loop {
            let top_index = self
                .forest_dfs
                .get(top)
                .copied()
                .ok_or(QRError::IndexOutOfBounds(top, forest_len))?;
            let top_label = forest
                .vertex_label(top_index)?
                .ok_or(QRError::NodeNoLabel(top_index))?;

            if top_label.is_packed() {
                if forest.is_empty_node(top_index)? {
                    if self.packs.is_empty() {
                        return Ok(State::Finish);
                    } else {
                        return Ok(State::ChangeBranch);
                    }
                }

                top = forest.children_of(top_index)?.next().unwrap();

                continue 'search;
            }

            let query_label = self
                .query_dfs
                .get(qtop)
                .copied()
                .and_then(|ind| self.query.label_of_vertex(ind).ok());

            if query_label
                .map(|label| label.matches(top_label.label(), top_label.status()))
                .unwrap_or(true)
            {
                if let Some(captured_value) = candidate_captures.get_mut(qtop) {
                    *captured_value = top;
                }

                top += 1;
                qtop += 1;

                if query_empty_p || qtop >= query_len {
                    self.current.replace(candidate_captures);

                    return Ok(State::Continue);
                }
            } else if qtop == 0 {
                if self.packs.is_empty() {
                    return Ok(State::Finish);
                } else {
                    return Ok(State::ChangeBranch);
                }
            } else {
                qtop -= 1;
            }
        }
    }

    #[inline]
    fn clear(&mut self) {
        self.current.take();
        self.packs.clear();
    }
}

#[cfg(test)]
mod test_forest_query {
    use std::io::Write;

    use super::*;

    #[test]
    fn test_read_forest() -> Result<(), Box<dyn std::error::Error>> {
        let mut file = std::fs::OpenOptions::new().read(true).open("forest.rep")?;

        use std::io::Read;

        let mut source: Vec<u8> = Vec::new();

        file.read_to_end(&mut source)?;

        use crate::bytes::BytesForest;

        let bytes_forest = BytesForest::try_from(source)?;

        dbg!(
            bytes_forest.nodes_len(),
            bytes_forest.children_of(0)?.collect::<Vec<_>>()
        );

        #[cfg(feature = "test-print-viz")]
        bytes_forest.print_viz("test forest.gv")?;

        let preprocessed = preprocess_forest(bytes_forest, 0)?;

        // dbg!(&preprocessed);

        use std::io::BufRead;

        println!("Input a query:");
        std::io::stdout().flush()?;

        for line in std::io::stdin().lock().lines() {
            let line = line?;

            if line == "q" {
                break;
            }

            let qtype = if line.starts_with('s') {
                1u8
            } else if line.starts_with('n') {
                2u8
            } else {
                0u8
            };

            let type_str: &str;

            let q = if line.starts_with('s') || line.starts_with('n') {
                if let Ok(n) = line[1..].parse::<usize>() {
                    n
                } else {
                    continue;
                }
            } else if let Ok(n) = line.parse::<usize>() {
                n
            } else {
                continue;
            };

            let ans = match qtype {
                0 => {
                    type_str = "dfs";
                    format!("{:?}", preprocessed.dfs_next.get(q).copied())
                }
                1 => {
                    type_str = "subtree range";
                    format!("{:?}", preprocessed.subtree_ranges.get(q))
                }
                _ => {
                    type_str = "next branch";
                    format!("{:?}", "haha")
                }
            };

            println!("answer for {type_str} = {ans}");

            println!("Input a query:");
            std::io::stdout().flush()?;
        }

        Ok(())
    }

    #[test]
    fn test_preprocess() -> Result<(), Box<dyn std::error::Error>> {
        Ok(())
    }
}