rstim 0.4.0

Stim-aligned stabilizer circuit simulator and detector error model toolkit
Documentation
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ReferenceSampleTree {
    pub prefix_bits: Vec<bool>,
    pub suffix_children: Vec<ReferenceSampleTree>,
    pub repetitions: u64,
}

impl Default for ReferenceSampleTree {
    fn default() -> Self {
        Self {
            prefix_bits: Vec::new(),
            suffix_children: Vec::new(),
            repetitions: 0,
        }
    }
}

impl ReferenceSampleTree {
    pub fn empty(&self) -> bool {
        if self.repetitions == 0 {
            return true;
        }
        if !self.prefix_bits.is_empty() {
            return false;
        }
        self.suffix_children.iter().all(Self::empty)
    }

    pub fn size(&self) -> usize {
        let mut body_size = self.prefix_bits.len();
        for child in &self.suffix_children {
            body_size = body_size
                .checked_add(child.size())
                .expect("reference sample tree size overflow");
        }
        let repetitions = usize::try_from(self.repetitions)
            .expect("reference sample tree repetitions do not fit in usize");
        body_size
            .checked_mul(repetitions)
            .expect("reference sample tree size overflow")
    }

    pub fn decompress_into(&self, output: &mut Vec<bool>) {
        for _ in 0..self.repetitions {
            output.extend(self.prefix_bits.iter().copied());
            for child in &self.suffix_children {
                child.decompress_into(output);
            }
        }
    }

    pub fn simplified(&self) -> Self {
        let mut flat = Vec::new();
        self.flatten_and_simplify_into(&mut flat);
        match flat.len() {
            0 => Self::default(),
            1 => flat.pop().expect("single simplified tree"),
            _ => {
                let first_is_payload =
                    flat[0].repetitions == 1 && flat[0].suffix_children.is_empty();
                if first_is_payload {
                    let mut iter = flat.into_iter();
                    let mut result = iter.next().expect("first simplified tree");
                    result.suffix_children = iter.collect();
                    result
                } else {
                    Self {
                        prefix_bits: Vec::new(),
                        suffix_children: flat,
                        repetitions: 1,
                    }
                }
            }
        }
    }

    pub fn try_factorize(&mut self, period_factor: usize) {
        if period_factor == 0
            || !self.prefix_bits.is_empty()
            || self.suffix_children.len() % period_factor != 0
        {
            return;
        }

        let period_len = self.suffix_children.len() / period_factor;
        for k in period_len..self.suffix_children.len() {
            if self.suffix_children[k - period_len] != self.suffix_children[k] {
                return;
            }
        }

        self.suffix_children.truncate(period_len);
        self.repetitions = self
            .repetitions
            .checked_mul(period_factor as u64)
            .expect("reference sample tree repetitions overflow");
    }

    fn flatten_and_simplify_into(&self, out: &mut Vec<Self>) {
        if self.repetitions == 0 {
            return;
        }

        let mut flattened = Vec::new();
        if !self.prefix_bits.is_empty() {
            flattened.push(Self {
                prefix_bits: self.prefix_bits.clone(),
                suffix_children: Vec::new(),
                repetitions: 1,
            });
        }
        for child in &self.suffix_children {
            child.flatten_and_simplify_into(&mut flattened);
        }

        let mut fused: Vec<Self> = Vec::new();
        for src in flattened {
            if let Some(dst) = fused.last_mut() {
                if dst.prefix_bits == src.prefix_bits
                    && dst.suffix_children == src.suffix_children
                {
                    dst.repetitions = dst
                        .repetitions
                        .checked_add(src.repetitions)
                        .expect("reference sample tree repetitions overflow");
                    continue;
                }
                if src.repetitions == 1 && dst.repetitions == 1 && dst.suffix_children.is_empty()
                {
                    dst.prefix_bits.extend(src.prefix_bits);
                    dst.suffix_children = src.suffix_children;
                    continue;
                }
            }
            fused.push(src);
        }

        if self.repetitions == 1 {
            out.extend(fused);
        } else if fused.len() == 1 {
            let mut only = fused.pop().expect("single fused tree");
            only.repetitions = only
                .repetitions
                .checked_mul(self.repetitions)
                .expect("reference sample tree repetitions overflow");
            out.push(only);
        } else if fused.is_empty() {
        } else if fused[0].suffix_children.is_empty() && fused[0].repetitions == 1 {
            let mut iter = fused.into_iter();
            let mut result = iter.next().expect("first fused tree");
            result.repetitions = self.repetitions;
            result.suffix_children = iter.collect();
            out.push(result);
        } else {
            out.push(Self {
                prefix_bits: Vec::new(),
                suffix_children: fused,
                repetitions: self.repetitions,
            });
        }
    }
}