canadensis_bit_length_set/
lib.rs

1extern crate itertools;
2extern crate num_integer;
3
4mod operator;
5
6use std::cmp::Ordering;
7use std::collections::BTreeSet;
8use std::ops::{RangeToInclusive, Rem};
9use std::{iter, mem};
10
11use crate::operator::Operator;
12
13/// A non-empty set of possible lengths (in bits) for a data type
14///
15/// This is based on the Python version: <https://github.com/OpenCyphal/pydsdl/blob/master/pydsdl/_bit_length_set/_bit_length_set.py>
16#[derive(Debug, Clone)]
17pub struct BitLengthSet {
18    operator: Operator,
19}
20
21impl BitLengthSet {
22    /// Creates a bit length set with one length value in bits
23    pub fn single(length: u64) -> BitLengthSet {
24        let mut values = BTreeSet::new();
25        values.insert(length);
26        BitLengthSet {
27            operator: Operator::Leaf(values),
28        }
29    }
30    /// Creates a bit length set from an iterator of possible length values
31    ///
32    /// If the provided iterator does not yield any elements, this function returns None.
33    pub fn from_lengths<I>(values: I) -> Option<BitLengthSet>
34    where
35        I: IntoIterator<Item = u64>,
36    {
37        let value_set: BTreeSet<u64> = values.into_iter().collect();
38        if value_set.is_empty() {
39            None
40        } else {
41            Some(BitLengthSet {
42                operator: Operator::Leaf(value_set),
43            })
44        }
45    }
46
47    /// Creates a bit length set from a set of possible length values
48    ///
49    /// If the provided set is empty, this function returns None.
50    pub fn from_length_set(values: BTreeSet<u64>) -> Option<BitLengthSet> {
51        if values.is_empty() {
52            None
53        } else {
54            Some(BitLengthSet {
55                operator: Operator::Leaf(values),
56            })
57        }
58    }
59
60    /// Returns the minimum length value in this set
61    ///
62    /// # Examples
63    ///
64    /// ```
65    /// # use canadensis_bit_length_set::BitLengthSet;
66    /// let lengths = BitLengthSet::single(37);
67    /// assert_eq!(37, lengths.min_value());
68    /// ```
69    ///
70    /// ```
71    /// # use canadensis_bit_length_set::BitLengthSet;
72    /// let lengths = BitLengthSet::from_lengths([1, 10, 30]).unwrap();
73    /// assert_eq!(1, lengths.min_value());
74    /// ```
75    pub fn min_value(&self) -> u64 {
76        self.operator.min()
77    }
78    /// Returns the maximum length value in this set
79    ///
80    /// # Examples
81    ///
82    /// ```
83    /// # use canadensis_bit_length_set::BitLengthSet;
84    /// let lengths = BitLengthSet::single(37);
85    /// assert_eq!(37, lengths.max_value());
86    /// ```
87    ///
88    /// ```
89    /// # use canadensis_bit_length_set::BitLengthSet;
90    /// let lengths = BitLengthSet::from_lengths([1, 10, 30]).unwrap();
91    /// assert_eq!(30, lengths.max_value());
92    /// ```
93    pub fn max_value(&self) -> u64 {
94        self.operator.max()
95    }
96
97    /// Returns true if this set's minimum and maximum values are equal
98    ///
99    /// # Examples
100    ///
101    /// ```
102    /// # use canadensis_bit_length_set::BitLengthSet;
103    /// let lengths = BitLengthSet::single(37);
104    /// assert!(lengths.is_fixed_size());
105    /// ```
106    ///
107    /// ```
108    /// # use canadensis_bit_length_set::BitLengthSet;
109    /// let lengths = BitLengthSet::from_lengths([1, 10, 30]).unwrap();
110    /// assert!(!lengths.is_fixed_size());
111    /// ```
112    pub fn is_fixed_size(&self) -> bool {
113        self.min_value() == self.max_value()
114    }
115
116    /// Returns true if all values in this set are aligned to multiples of 8 bits
117    ///
118    /// # Examples
119    ///
120    /// ```
121    /// # use canadensis_bit_length_set::BitLengthSet;
122    /// assert!(BitLengthSet::single(0).is_byte_aligned());
123    /// assert!(BitLengthSet::single(8).is_byte_aligned());
124    /// assert!(BitLengthSet::single(16).is_byte_aligned());
125    ///
126    /// assert!(!BitLengthSet::single(1).is_byte_aligned());
127    /// assert!(!BitLengthSet::single(2).is_byte_aligned());
128    /// assert!(!BitLengthSet::single(4).is_byte_aligned());
129    /// assert!(!BitLengthSet::single(7).is_byte_aligned());
130    ///
131    /// assert!(!BitLengthSet::from_lengths([0, 1, 8, 16, 24]).unwrap().is_byte_aligned());
132    /// assert!(!BitLengthSet::from_lengths([8, 9]).unwrap().is_byte_aligned());
133    ///
134    /// assert!(BitLengthSet::from_lengths([0, 8, 16, 24]).unwrap().is_byte_aligned());
135    /// assert!(BitLengthSet::from_lengths([8, 16]).unwrap().is_byte_aligned());
136    /// ```
137    pub fn is_byte_aligned(&self) -> bool {
138        self.is_aligned(8)
139    }
140
141    /// Returns true if all values in this set are aligned to multiples of the specified number of
142    /// bits
143    ///
144    /// # Examples
145    ///
146    /// ```
147    /// # use canadensis_bit_length_set::BitLengthSet;
148    /// assert!(BitLengthSet::from_lengths([0, 3, 6, 15]).unwrap().is_aligned(3));
149    /// assert!(!BitLengthSet::from_lengths([0, 3, 6, 16]).unwrap().is_aligned(3));
150    ///
151    /// assert!(BitLengthSet::from_lengths([0, 17, 34, 68]).unwrap().is_aligned(17));
152    /// assert!(!BitLengthSet::from_lengths([0, 17, 34, 64]).unwrap().is_aligned(17));
153    /// ```
154    pub fn is_aligned(&self, bit_length: u64) -> bool {
155        let remainder = self % bit_length;
156        remainder.is_fixed_size() && remainder.min_value() == 0
157    }
158
159    /// Expands this bit length set and returns a set with all enclosed values
160    ///
161    /// For some bit length sets, especially when large sets are concatenated, this may be slow.
162    ///
163    /// # Examples
164    ///
165    /// ```
166    /// # use canadensis_bit_length_set::BitLengthSet;
167    /// # use std::collections::BTreeSet;
168    /// let lengths1 = BitLengthSet::from_lengths([0, 8, 24, 96]).unwrap();
169    /// let lengths2 = BitLengthSet::from_lengths([1, 2, 8]).unwrap();
170    ///
171    /// let union = lengths1.unite([lengths2]);
172    /// let expanded_union = union.expand();
173    ///
174    /// let expected: BTreeSet<u64> = [0, 1, 2, 8, 24, 96].iter().copied().collect();
175    /// assert_eq!(expected, expanded_union);
176    /// ```
177    pub fn expand(&self) -> BTreeSet<u64> {
178        self.operator.expand()
179    }
180
181    /// Converts this bit length set into a new set that aligns up all its values to a multiple
182    /// of the given alignment
183    ///
184    /// # Examples
185    ///
186    /// ```
187    /// # use canadensis_bit_length_set::BitLengthSet;
188    /// let lengths = BitLengthSet::from_lengths([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]).unwrap();
189    /// let padded = lengths.pad_to_alignment(8);
190    ///
191    /// let expected = BitLengthSet::from_lengths([0, 8, 16]).unwrap();
192    /// assert_eq!(padded.expand(), expected.expand());
193    /// ```
194    pub fn pad_to_alignment(self, alignment: u32) -> BitLengthSet {
195        BitLengthSet {
196            operator: Operator::Padding {
197                child: Box::new(self.operator),
198                alignment,
199            },
200        }
201    }
202
203    /// Converts this bit length set into a new set that represents a repetition of these values
204    /// a fixed number of times
205    ///
206    /// # Examples
207    ///
208    /// ## Single length
209    ///
210    /// ```
211    /// # use canadensis_bit_length_set::BitLengthSet;
212    /// let length = BitLengthSet::single(12);
213    /// let repeated = length.repeat(4);
214    ///
215    /// let expected = BitLengthSet::single(12 * 4);
216    /// assert_eq!(repeated.expand(), expected.expand());
217    /// ```
218    ///
219    /// ## Multiple lengths
220    ///
221    /// ```
222    /// # use canadensis_bit_length_set::BitLengthSet;
223    /// let lengths = BitLengthSet::from_lengths([0, 1, 8]).unwrap();
224    /// let repeated = lengths.repeat(4);
225    ///
226    /// let expected = BitLengthSet::from_lengths(
227    ///     [0, 1, 2, 3, 4, 8, 9, 10, 11, 16, 17, 18, 24, 25, 32]
228    /// ).unwrap();
229    /// assert_eq!(repeated.expand(), expected.expand());
230    /// ```
231    ///
232    pub fn repeat(self, count: u64) -> BitLengthSet {
233        BitLengthSet {
234            operator: Operator::Repeat {
235                child: Box::new(self.operator),
236                count,
237            },
238        }
239    }
240
241    /// Converts this bit length set into a new set that represents a repetition of these values
242    /// zero times up to an inclusive maximum count
243    ///
244    /// # Examples
245    ///
246    /// ## Single length
247    ///
248    /// ```
249    /// # use canadensis_bit_length_set::BitLengthSet;
250    /// let lengths = BitLengthSet::single(3);
251    /// let repeated = lengths.repeat_range(..=8);
252    ///
253    /// let expected = BitLengthSet::from_lengths([0, 3, 6, 9, 12, 15, 18, 21, 24]).unwrap();
254    /// assert_eq!(repeated.expand(), expected.expand());
255    /// ```
256    ///
257    /// ## Multiple lengths
258    ///
259    /// ```
260    /// # use canadensis_bit_length_set::BitLengthSet;
261    /// let lengths = BitLengthSet::from_lengths([1, 2, 4]).unwrap();
262    /// let repeated = lengths.repeat_range(..=2);
263    ///
264    /// let expected = BitLengthSet::from_lengths([0, 1, 2, 3, 4, 5, 6, 8]).unwrap();
265    /// assert_eq!(repeated.expand(), expected.expand());
266    /// ```
267    pub fn repeat_range(self, count: RangeToInclusive<u64>) -> BitLengthSet {
268        BitLengthSet {
269            operator: Operator::RangeRepeat {
270                child: Box::new(self.operator),
271                count,
272            },
273        }
274    }
275
276    /// Extends this bit length set, so that this set represents a concatenation of this set
277    /// followed by other sets
278    ///
279    /// # Examples
280    ///
281    /// ```
282    /// # use canadensis_bit_length_set::{BitLengthSet, bit_length};
283    ///
284    /// let combined = bit_length![0, 8].concatenate([bit_length![12]]);
285    /// let expected = bit_length![12, 20];
286    /// assert_eq!(combined.expand(), expected.expand());
287    /// ```
288    ///
289    /// ```
290    /// # use canadensis_bit_length_set::{BitLengthSet, bit_length};
291    ///
292    /// let combined = bit_length![0, 1, 3].concatenate([bit_length![5, 13]]);
293    /// let expected = bit_length![5, 6, 8, 13, 14, 16];
294    /// assert_eq!(combined.expand(), expected.expand());
295    /// ```
296    pub fn concatenate<I>(mut self, others: I) -> BitLengthSet
297    where
298        I: IntoIterator<Item = BitLengthSet>,
299    {
300        self.extend(others);
301        self
302    }
303
304    /// Converts this bit length set into a new set that is the union of this set and the provided
305    /// other sets
306    ///
307    /// This is uses to represent a union (or enum in Rust)
308    ///
309    /// # Examples
310    ///
311    /// ```
312    /// # use canadensis_bit_length_set::{BitLengthSet, bit_length};
313    ///
314    /// let combined = bit_length![0, 1, 3, 24].unite([bit_length![3, 8]]);
315    /// let expected = bit_length![0, 1, 3, 8, 24];
316    /// assert_eq!(combined.expand(), expected.expand());
317    /// ```
318    pub fn unite<I>(self, others: I) -> BitLengthSet
319    where
320        I: IntoIterator<Item = BitLengthSet>,
321    {
322        let other_operators = others.into_iter().map(|set| set.operator);
323        BitLengthSet {
324            operator: Operator::Union {
325                children: iter::once(self.operator).chain(other_operators).collect(),
326            },
327        }
328    }
329
330    /// Checks that the expanded form of this set has the same properties as calculated based on
331    /// the internal representation of this set
332    pub fn validate_numerically(&self) {
333        self.operator.validate_numerically()
334    }
335
336    /// Returns true if this set has the same structure of operators as another set
337    ///
338    /// If this function returns true, the expanded forms of self and other are equal. If this
339    /// function returns false, the expanded forms of self and other may or may not be equal.
340    fn structural_equal(&self, other: &Self) -> bool {
341        self.operator.structural_equal(&other.operator)
342    }
343}
344
345impl Default for BitLengthSet {
346    /// Returns the default bit length set, which contains the value 0
347    fn default() -> Self {
348        BitLengthSet::single(0)
349    }
350}
351
352impl Rem<u64> for BitLengthSet {
353    type Output = BitLengthSet;
354
355    /// Calculates the elementwise modulo of each value in this set
356    fn rem(self, rhs: u64) -> Self::Output {
357        // Delegate to version that takes &self
358        Rem::rem(&self, rhs)
359    }
360}
361
362impl Rem<u64> for &'_ BitLengthSet {
363    type Output = BitLengthSet;
364
365    /// Calculates the elementwise modulo of each value in this set
366    ///
367    /// # Examples
368    ///
369    /// ```
370    /// # use canadensis_bit_length_set::{BitLengthSet, bit_length};
371    ///
372    /// assert_eq!((bit_length![0] % 12345).expand(), bit_length![0].expand());
373    /// assert_eq!((bit_length![34] % 17).expand(), bit_length![0].expand());
374    /// assert_eq!((bit_length![8, 12, 16] % 8).expand(), bit_length![0, 4].expand());
375    /// assert_eq!((bit_length![0, 3, 8, 9, 27] % 8).expand(), bit_length![0, 1, 3].expand());
376    ///
377    /// ```
378    fn rem(self, rhs: u64) -> Self::Output {
379        let result = self.operator.modulo(rhs);
380        debug_assert!(!result.is_empty());
381        BitLengthSet {
382            operator: Operator::Leaf(result),
383        }
384    }
385}
386
387impl Extend<BitLengthSet> for BitLengthSet {
388    /// Extends this bit length set, so that this set represents a concatenation of this set
389    /// followed by other sets
390    ///
391    /// This is equivalent to [`concatenate`](#method.concatenate).
392    fn extend<T: IntoIterator<Item = BitLengthSet>>(&mut self, iter: T) {
393        let other_operators = iter.into_iter().map(|set| set.operator);
394        // Take out the operator from self and temporarily replace it with an invalid empty operator
395        let self_operator = mem::replace(&mut self.operator, Operator::Leaf(BTreeSet::default()));
396        self.operator = Operator::Concatenate {
397            children: iter::once(self_operator).chain(other_operators).collect(),
398        }
399    }
400}
401
402impl PartialEq<Self> for BitLengthSet {
403    fn eq(&self, other: &Self) -> bool {
404        // There may be a more optimized way to do this
405        if self.structural_equal(other) {
406            true
407        } else {
408            self.expand() == other.expand()
409        }
410    }
411}
412
413impl Eq for BitLengthSet {}
414
415impl PartialOrd for BitLengthSet {
416    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
417        Some(self.cmp(other))
418    }
419}
420
421impl Ord for BitLengthSet {
422    fn cmp(&self, other: &Self) -> Ordering {
423        // There may be a more optimized way to do this, without expanding the sets
424        self.expand().cmp(&other.expand())
425    }
426}
427
428/// A convenience macro for creating a `BitLengthSet`
429///
430/// This macro takes one or more arguments and evaluates to a `BitLengthSet` value.
431///
432/// # Examples
433///
434/// ```
435/// # use canadensis_bit_length_set::bit_length;
436/// bit_length![8];
437/// bit_length![0, 8, 10];
438/// bit_length![0, 8, 10,];
439/// ```
440///
441/// This macro will produce a compiler error if you attempt to call it with no arguments:
442///
443/// ```compile_fail
444/// # use canadensis_bit_length_set::bit_length;
445/// bit_length![];
446/// ```
447///
448#[macro_export]
449macro_rules! bit_length {
450    {$single:expr} => {
451        $crate::BitLengthSet::single($single)
452    };
453    {$first:expr, $($others:expr),+ $(,)?} => {
454        $crate::BitLengthSet::from_lengths([$first, $($others),+]).unwrap()
455    };
456}
canadensis_bit_length_set/lib.rs

canadensis_bit_length_set/
lib.rs
