zerotrie/builder/nonconst/
store.rs

1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5//! This module contains internal collections for the non-const builder.
6
7use super::super::branch_meta::BranchMeta;
8use super::super::konst::ConstArrayBuilder;
9use alloc::collections::VecDeque;
10use alloc::vec::Vec;
11
12/// A trait applied to a data structure for building a [`ZeroTrie`](crate::ZeroTrie).
13pub(crate) trait TrieBuilderStore {
14    /// Create a new empty store.
15    fn atbs_new_empty() -> Self;
16
17    /// Return the length in bytes of the store.
18    fn atbs_len(&self) -> usize;
19
20    /// Push a byte to the front of the store.
21    fn atbs_push_front(&mut self, byte: u8);
22
23    /// Push multiple bytes to the front of the store.
24    fn atbs_extend_front(&mut self, other: &[u8]);
25
26    /// Read the store into a `Vec<u8>`.
27    fn atbs_to_bytes(&self) -> Vec<u8>;
28
29    /// Perform the operation `self[index] |= bits`
30    fn atbs_bitor_assign(&mut self, index: usize, bits: u8);
31
32    /// Swap the adjacent ranges `self[start..mid]` and `self[mid..limit]`.
33    ///
34    /// # Panics
35    ///
36    /// Panics if the specified ranges are invalid.
37    fn atbs_swap_ranges(&mut self, start: usize, mid: usize, limit: usize);
38
39    /// Remove and return the first element in the store, or `None` if empty.
40    fn atbs_pop_front(&mut self) -> Option<u8>;
41
42    /// Prepend `n` zeros to the front of the store.
43    fn atbs_prepend_n_zeros(&mut self, n: usize) {
44        let mut i = 0;
45        while i < n {
46            self.atbs_push_front(0);
47            i += 1;
48        }
49    }
50}
51
52impl TrieBuilderStore for VecDeque<u8> {
53    fn atbs_new_empty() -> Self {
54        VecDeque::new()
55    }
56    fn atbs_len(&self) -> usize {
57        self.len()
58    }
59    fn atbs_push_front(&mut self, byte: u8) {
60        self.push_front(byte);
61    }
62    fn atbs_extend_front(&mut self, other: &[u8]) {
63        self.reserve(other.len());
64        for b in other.iter().rev() {
65            self.push_front(*b);
66        }
67    }
68    fn atbs_to_bytes(&self) -> Vec<u8> {
69        let mut v = Vec::with_capacity(self.len());
70        let (a, b) = self.as_slices();
71        v.extend(a);
72        v.extend(b);
73        v
74    }
75    fn atbs_bitor_assign(&mut self, index: usize, bits: u8) {
76        self[index] |= bits;
77    }
78    /// # Panics
79    /// Panics if the specified ranges are invalid.
80    #[allow(clippy::panic)] // documented
81    fn atbs_swap_ranges(&mut self, mut start: usize, mut mid: usize, mut limit: usize) {
82        if start > mid || mid > limit {
83            panic!("Invalid args to atbs_swap_ranges(): start > mid || mid > limit");
84        }
85        if limit > self.len() {
86            panic!(
87                "Invalid args to atbs_swap_ranges(): limit out of range: {limit} > {}",
88                self.len()
89            );
90        }
91        // The following algorithm is an in-place swap of two adjacent ranges of potentially
92        // different lengths. Would make a good coding interview question.
93        loop {
94            if start == mid || mid == limit {
95                return;
96            }
97            let len0 = mid - start;
98            let len1 = limit - mid;
99            let mut i = start;
100            let mut j = limit - core::cmp::min(len0, len1);
101            while j < limit {
102                self.swap(i, j);
103                i += 1;
104                j += 1;
105            }
106            if len0 < len1 {
107                mid = start + len0;
108                limit -= len0;
109            } else {
110                start += len1;
111                mid = limit - len1;
112            }
113        }
114    }
115    fn atbs_pop_front(&mut self) -> Option<u8> {
116        self.pop_front()
117    }
118}
119
120/// A data structure that holds any number of [`BranchMeta`] items.
121pub(crate) struct NonConstLengthsStack {
122    data: Vec<BranchMeta>,
123}
124
125impl core::fmt::Debug for NonConstLengthsStack {
126    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
127        self.as_slice().fmt(f)
128    }
129}
130
131impl NonConstLengthsStack {
132    /// Creates a new empty [`NonConstLengthsStack`].
133    pub const fn new() -> Self {
134        Self { data: Vec::new() }
135    }
136
137    /// Returns whether the stack is empty.
138    pub fn is_empty(&self) -> bool {
139        self.data.is_empty()
140    }
141
142    /// Adds a [`BranchMeta`] to the stack.
143    pub fn push(&mut self, meta: BranchMeta) {
144        self.data.push(meta);
145    }
146
147    /// Returns a copy of the [`BranchMeta`] on the top of the stack, panicking if
148    /// the stack is empty.
149    #[allow(clippy::unwrap_used)] // "panic" is in the method name
150    pub fn peek_or_panic(&self) -> BranchMeta {
151        *self.data.last().unwrap()
152    }
153
154    /// Removes many [`BranchMeta`]s from the stack, returning them in a [`ConstArrayBuilder`].
155    pub fn pop_many_or_panic(&mut self, len: usize) -> ConstArrayBuilder<256, BranchMeta> {
156        debug_assert!(len <= 256);
157        let mut result = ConstArrayBuilder::new_empty([BranchMeta::default(); 256], 256);
158        let mut ix = 0;
159        loop {
160            if ix == len {
161                break;
162            }
163            let i = self.data.len() - ix - 1;
164            // Won't panic because len <= 256
165            result.const_push_front_or_panic(match self.data.get(i) {
166                Some(x) => *x,
167                None => unreachable!("Not enough items in the ConstLengthsStack"),
168            });
169            ix += 1;
170        }
171        self.data.truncate(self.data.len() - len);
172        result
173    }
174
175    /// Non-const function that returns the initialized elements as a slice.
176    fn as_slice(&self) -> &[BranchMeta] {
177        &self.data
178    }
179}
180
181#[cfg(test)]
182mod tests {
183    use super::*;
184
185    #[test]
186    fn test_swap_ranges() {
187        let s = b"..abcdefghijkl=";
188        let mut s = s.iter().copied().collect::<VecDeque<u8>>();
189        s.atbs_swap_ranges(2, 7, 14);
190        assert_eq!(s.atbs_to_bytes(), b"..fghijklabcde=");
191    }
192}
zerotrie/builder/nonconst/store.rs

zerotrie/builder/nonconst/
store.rs
