xensieve/
lib.rs

1use std::cmp::Ordering;
2use std::fmt;
3use std::ops::BitAnd;
4use std::ops::BitOr;
5use std::ops::BitXor;
6use std::ops::Not;
7
8mod parser;
9mod util;
10
11//------------------------------------------------------------------------------
12
13/// Container of integer values for the modulus and the shift of a Residual class.
14///
15/// # Fields
16/// * `modulus` - The modulus.
17/// * `shift` - The shift.
18///
19#[derive(Clone, Debug, Copy)]
20pub(crate) struct Residual {
21    modulus: u64,
22    shift: u64,
23}
24
25impl Residual {
26    pub(crate) fn new(modulus: u64, mut shift: u64) -> Self {
27        if modulus == 0 {
28            shift = 0;
29        } else {
30            shift %= modulus;
31        }
32        Self { modulus, shift }
33    }
34
35    /// Return `true` if the value is contained with this Sieve.
36    ///
37    pub(crate) fn contains(&self, value: i128) -> bool {
38        if self.modulus == 0 {
39            return false;
40        }
41        let pos: i128 = value - self.shift as i128;
42        pos % self.modulus as i128 == 0
43    }
44}
45
46impl fmt::Display for Residual {
47    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
48        // let n = if self.invert {String::from("!")} else {String::new()};
49        write!(f, "{}@{}", self.modulus, self.shift)
50    }
51}
52
53impl BitAnd for Residual {
54    type Output = Residual;
55
56    fn bitand(self, rhs: Self) -> Self::Output {
57        let (m, s) = util::intersection(self.modulus, rhs.modulus, self.shift, rhs.shift).unwrap();
58        Self::new(m, s)
59    }
60}
61
62impl PartialEq for Residual {
63    fn eq(&self, other: &Self) -> bool {
64        self.modulus == other.modulus && self.shift == other.shift
65    }
66}
67
68impl Eq for Residual {}
69
70impl PartialOrd for Residual {
71    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
72        Some(self.cmp(other))
73    }
74}
75
76impl Ord for Residual {
77    fn cmp(&self, other: &Self) -> Ordering {
78        self.modulus
79            .cmp(&other.modulus)
80            .then_with(|| self.shift.cmp(&other.shift))
81    }
82}
83
84//------------------------------------------------------------------------------
85
86/// A node in the graph of Residuals combined by logical operations.
87///
88#[derive(Clone, Debug)]
89pub(crate) enum SieveNode {
90    Unit(Residual),
91    Intersection(Box<SieveNode>, Box<SieveNode>),
92    Union(Box<SieveNode>, Box<SieveNode>),
93    SymmetricDifference(Box<SieveNode>, Box<SieveNode>),
94    Inversion(Box<SieveNode>),
95}
96
97impl fmt::Display for SieveNode {
98    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
99        let s: String = match self {
100            SieveNode::Unit(residual) => residual.to_string(),
101            SieveNode::Intersection(lhs, rhs) => {
102                let lhs_str = lhs.to_string();
103                let rhs_str = rhs.to_string();
104                format!("{lhs_str}&{rhs_str}")
105            }
106            SieveNode::Union(lhs, rhs) => {
107                let lhs_str = lhs.to_string();
108                let rhs_str = rhs.to_string();
109                format!("{lhs_str}|{rhs_str}")
110            }
111            SieveNode::SymmetricDifference(lhs, rhs) => {
112                let lhs_str = lhs.to_string();
113                let rhs_str = rhs.to_string();
114                format!("{lhs_str}^{rhs_str}")
115            }
116            SieveNode::Inversion(part) => {
117                let r = part.to_string();
118                format!("!({r})")
119            }
120        };
121        write!(f, "{}", s)
122    }
123}
124
125impl SieveNode {
126    /// Return `true` if the values is contained within this Sieve.
127    ///
128    pub fn contains(&self, value: i128) -> bool {
129        match self {
130            SieveNode::Unit(residual) => residual.contains(value),
131            SieveNode::Intersection(lhs, rhs) => lhs.contains(value) && rhs.contains(value),
132            SieveNode::Union(lhs, rhs) => lhs.contains(value) || rhs.contains(value),
133            SieveNode::SymmetricDifference(lhs, rhs) => lhs.contains(value) ^ rhs.contains(value),
134            SieveNode::Inversion(part) => !part.contains(value),
135        }
136    }
137}
138
139//------------------------------------------------------------------------------
140
141/// The representation of a Xenakis Sieve, constructed from a string notation of one or more Residual classes combined with logical operators. This Rust implementation follows the Python implementation in Ariza (2005), with significant performance and interface enhancements: https://direct.mit.edu/comj/article/29/2/40/93957
142#[derive(Clone, Debug)]
143pub struct Sieve {
144    root: SieveNode,
145}
146
147impl BitAnd for Sieve {
148    type Output = Sieve;
149
150    fn bitand(self, rhs: Self) -> Self::Output {
151        Sieve {
152            root: SieveNode::Intersection(Box::new(self.root), Box::new(rhs.root)),
153        }
154    }
155}
156
157impl BitAnd for &Sieve {
158    type Output = Sieve;
159
160    fn bitand(self, rhs: Self) -> Self::Output {
161        Sieve {
162            root: SieveNode::Intersection(Box::new(self.root.clone()), Box::new(rhs.root.clone())),
163        }
164    }
165}
166
167impl BitOr for Sieve {
168    type Output = Sieve;
169
170    fn bitor(self, rhs: Self) -> Self::Output {
171        Sieve {
172            root: SieveNode::Union(Box::new(self.root), Box::new(rhs.root)),
173        }
174    }
175}
176
177impl BitOr for &Sieve {
178    type Output = Sieve;
179
180    fn bitor(self, rhs: Self) -> Self::Output {
181        Sieve {
182            root: SieveNode::Union(Box::new(self.root.clone()), Box::new(rhs.root.clone())),
183        }
184    }
185}
186
187impl BitXor for Sieve {
188    type Output = Sieve;
189
190    fn bitxor(self, rhs: Self) -> Self::Output {
191        Sieve {
192            root: SieveNode::SymmetricDifference(Box::new(self.root), Box::new(rhs.root)),
193        }
194    }
195}
196
197impl BitXor for &Sieve {
198    type Output = Sieve;
199
200    fn bitxor(self, rhs: Self) -> Self::Output {
201        Sieve {
202            root: SieveNode::SymmetricDifference(
203                Box::new(self.root.clone()),
204                Box::new(rhs.root.clone()),
205            ),
206        }
207    }
208}
209
210impl Not for Sieve {
211    type Output = Sieve;
212
213    fn not(self) -> Self::Output {
214        Sieve {
215            root: SieveNode::Inversion(Box::new(self.root)),
216        }
217    }
218}
219
220impl Not for &Sieve {
221    type Output = Sieve;
222
223    fn not(self) -> Self::Output {
224        Sieve {
225            root: SieveNode::Inversion(Box::new(self.root.clone())),
226        }
227    }
228}
229
230impl fmt::Display for Sieve {
231    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
232        write!(f, "Sieve{{{}}}", self.root)
233    }
234}
235
236impl Sieve {
237    /// Construct a Xenakis Sieve from a string representation.
238    ///
239    /// ```
240    /// let s = xensieve::Sieve::new("3@0|5@1");
241    /// assert_eq!(s.iter_value(0..15).collect::<Vec<_>>(), vec![0, 1, 3, 6, 9, 11, 12])
242    /// ````
243    pub fn new(value: &str) -> Self {
244        let mut stack: Vec<Self> = Vec::new();
245        for token in parser::infix_to_postfix(value).expect("Parsing failure") {
246            match token.as_str() {
247                "!" => {
248                    let s = stack.pop().expect("Invalid syntax: missing operand");
249                    stack.push(!s);
250                }
251                "&" => {
252                    let right = stack.pop().expect("Invalid syntax: missing operand");
253                    let left = stack.pop().expect("Invalid syntax: missing operand");
254                    stack.push(left & right);
255                }
256                "^" => {
257                    let right = stack.pop().expect("Invalid syntax: missing operand");
258                    let left = stack.pop().expect("Invalid syntax: missing operand");
259                    stack.push(left ^ right);
260                }
261                "|" => {
262                    let right = stack.pop().expect("Invalid syntax: missing operand");
263                    let left = stack.pop().expect("Invalid syntax: missing operand");
264                    stack.push(left | right);
265                }
266                operand => {
267                    let (m, s) = parser::residual_to_ints(operand)
268                        .expect("Invalid syntax: cannot parse Residual");
269                    let r = Residual::new(m, s);
270                    let s = Self {
271                        root: SieveNode::Unit(r),
272                    };
273                    stack.push(s);
274                }
275            }
276        }
277        stack.pop().expect("Invalid syntax: no result")
278    }
279
280    /// Return `true` if the value is contained with this Sieve.
281    ///
282    /// ```
283    /// let s = xensieve::Sieve::new("3@0 & 5@0");
284    /// assert_eq!(s.contains(15), true);
285    /// assert_eq!(s.contains(16), false);
286    /// assert_eq!(s.contains(30), true);
287    /// ```
288    pub fn contains(&self, value: i128) -> bool {
289        self.root.contains(value)
290    }
291
292    /// For the iterator provided as an input, iterate the subset of values that are contained within the sieve.
293    /// ```
294    /// let s = xensieve::Sieve::new("3@0|4@0");
295    /// assert_eq!(s.iter_value(0..=12).collect::<Vec<_>>(), vec![0, 3, 4, 6, 8, 9, 12])
296    /// ````
297    pub fn iter_value(
298        &self,
299        iterator: impl Iterator<Item = i128>,
300    ) -> IterValue<impl Iterator<Item = i128>> {
301        // NOTE: do not want to clone self here...
302        IterValue {
303            iterator,
304            sieve_node: self.root.clone(),
305        }
306    }
307
308    /// For the iterator provided as an input, iterate the Boolean status of contained.
309    /// ```
310    /// let s = xensieve::Sieve::new("3@0|4@0");
311    /// assert_eq!(s.iter_state(0..=6).collect::<Vec<_>>(), vec![true, false, false, true, true, false, true])
312    /// ````
313    pub fn iter_state(
314        &self,
315        iterator: impl Iterator<Item = i128>,
316    ) -> IterState<impl Iterator<Item = i128>> {
317        IterState {
318            iterator,
319            sieve_node: self.root.clone(),
320        }
321    }
322
323    /// Iterate over integer intervals between values in the sieve.
324    /// ```
325    /// let s = xensieve::Sieve::new("3@0|4@0");
326    /// assert_eq!(s.iter_interval(0..=12).collect::<Vec<_>>(), vec![3, 1, 2, 2, 1, 3])
327    /// ````
328    pub fn iter_interval(
329        &self,
330        iterator: impl Iterator<Item = i128>,
331    ) -> IterInterval<impl Iterator<Item = i128>> {
332        IterInterval {
333            iterator,
334            sieve_node: self.root.clone(),
335            last: PositionLast::Init,
336        }
337    }
338}
339
340//------------------------------------------------------------------------------
341
342/// The iterator returned by `iter_value`.
343/// ```
344/// let s = xensieve::Sieve::new("3@0|4@0");
345/// let mut s_iter = s.iter_value(17..);
346/// assert_eq!(s_iter.next().unwrap(), 18);
347/// assert_eq!(s_iter.next().unwrap(), 20);
348/// ```
349pub struct IterValue<I>
350where
351    I: Iterator<Item = i128>,
352{
353    iterator: I,
354    sieve_node: SieveNode,
355}
356
357impl<I> Iterator for IterValue<I>
358where
359    I: Iterator<Item = i128>,
360{
361    type Item = i128;
362
363    fn next(&mut self) -> Option<Self::Item> {
364        self.iterator
365            .by_ref()
366            .find(|&p| self.sieve_node.contains(p))
367    }
368}
369
370//------------------------------------------------------------------------------
371
372/// The iterator returned by `iter_state`.
373/// ```
374/// let s = xensieve::Sieve::new("3@0|4@0");
375/// let mut s_iter = s.iter_state(17..);
376/// assert_eq!(s_iter.next().unwrap(), false);
377/// assert_eq!(s_iter.next().unwrap(), true);
378/// assert_eq!(s_iter.next().unwrap(), false);
379/// assert_eq!(s_iter.next().unwrap(), true);
380/// ```
381pub struct IterState<I>
382where
383    I: Iterator<Item = i128>,
384{
385    iterator: I,
386    sieve_node: SieveNode,
387}
388
389impl<I> Iterator for IterState<I>
390where
391    I: Iterator<Item = i128>,
392{
393    type Item = bool;
394
395    fn next(&mut self) -> Option<Self::Item> {
396        match self.iterator.next() {
397            Some(p) => Some(self.sieve_node.contains(p)),
398            None => None,
399        }
400    }
401}
402
403//------------------------------------------------------------------------------
404
405enum PositionLast {
406    Init,
407    Value(i128),
408}
409
410/// The iterator returned by `iter_interval`.
411/// ```
412/// let s = xensieve::Sieve::new("3@0|4@0");
413/// let mut s_iter = s.iter_interval(17..);
414/// assert_eq!(s_iter.next().unwrap(), 2);
415/// assert_eq!(s_iter.next().unwrap(), 1);
416/// assert_eq!(s_iter.next().unwrap(), 3);
417/// ```
418pub struct IterInterval<I>
419where
420    I: Iterator<Item = i128>,
421{
422    iterator: I,
423    sieve_node: SieveNode,
424    last: PositionLast,
425}
426
427impl<I> Iterator for IterInterval<I>
428where
429    I: Iterator<Item = i128>,
430{
431    type Item = i128;
432
433    fn next(&mut self) -> Option<Self::Item> {
434        for p in self.iterator.by_ref() {
435            // while let Some(p) = self.iterator.next() {
436            if self.sieve_node.contains(p) {
437                match self.last {
438                    PositionLast::Init => {
439                        // drop the first value
440                        self.last = PositionLast::Value(p);
441                        continue;
442                    }
443                    PositionLast::Value(last) => {
444                        let post = p - last;
445                        self.last = PositionLast::Value(p);
446                        return Some(post);
447                    }
448                }
449            }
450        }
451        None
452    }
453}
454
455//------------------------------------------------------------------------------
456
457#[cfg(test)]
458mod tests {
459    use super::*;
460
461    #[test]
462    fn test_residual_a() {
463        let r1 = Residual::new(3, 0);
464        assert_eq!(r1.to_string(), String::from("3@0"));
465    }
466
467    #[test]
468    fn test_residual_b() {
469        let r1 = Residual::new(0, 2);
470        assert_eq!(r1.to_string(), "0@0");
471    }
472
473    //--------------------------------------------------------------------------
474    #[test]
475    fn test_residual_to_string_a() {
476        let r1 = Residual::new(3, 0);
477        assert_eq!(r1.to_string(), "3@0");
478    }
479
480    #[test]
481    fn test_residual_to_string_b() {
482        let r1 = Residual::new(8, 3);
483        assert_eq!(r1.to_string(), "8@3");
484    }
485
486    #[test]
487    fn test_residual_to_string_c() {
488        let r1 = Residual::new(5, 8);
489        assert_eq!(r1.to_string(), "5@3");
490    }
491
492    #[test]
493    fn test_residual_to_string_d() {
494        let r1 = Residual::new(5, 9);
495        assert_eq!(r1.to_string(), "5@4");
496    }
497
498    #[test]
499    fn test_residual_to_string_e() {
500        let r1 = Residual::new(5, 10);
501        assert_eq!(r1.to_string(), "5@0");
502    }
503
504    //--------------------------------------------------------------------------
505
506    // #[test]
507    // fn test_residual_not_a() {
508    //     let r1 = Residual::new(5, 10);
509    //     assert_eq!(r1.to_string(), String::from("!5@0"));
510    //     let r2 = !r1;
511    //     assert_eq!(r2.to_string(), "5@0");
512    //     let r3 = !r2;
513    //     assert_eq!(r3.to_string(), "!5@0");
514    // }
515
516    #[test]
517    fn test_residual_eq_a() {
518        let r1 = Residual::new(5, 2);
519        let r2 = Residual::new(5, 3);
520        assert_eq!(r1 == r2, false);
521        assert_eq!(r1 != r2, true);
522    }
523
524    #[test]
525    fn test_residual_eq_b() {
526        let r1 = Residual::new(5, 2);
527        let r2 = Residual::new(5, 2);
528        assert_eq!(r1 == r2, true);
529        assert_eq!(r1 != r2, false);
530    }
531
532    #[test]
533    fn test_residual_ord_a() {
534        let r1 = Residual::new(5, 2);
535        let r2 = Residual::new(5, 3);
536        assert!(r1 < r2);
537    }
538
539    #[test]
540    fn test_residual_ord_b() {
541        let r1 = Residual::new(2, 3);
542        let r2 = Residual::new(5, 3);
543        assert!(r1 < r2);
544    }
545
546    #[test]
547    fn test_residual_ord_c() {
548        let r1 = Residual::new(5, 3);
549        let r2 = Residual::new(5, 3);
550        assert!(r1 == r2);
551    }
552
553    //--------------------------------------------------------------------------
554
555    #[test]
556    fn test_residual_bitand_a() {
557        let r1 = Residual::new(4, 0);
558        let r2 = Residual::new(3, 0);
559        assert_eq!((r1 & r2).to_string(), "12@0");
560    }
561
562    #[test]
563    fn test_residual_bitand_b() {
564        let r1 = Residual::new(4, 0);
565        let r2 = Residual::new(3, 1);
566        assert_eq!((r1 & r2).to_string(), "12@4");
567    }
568
569    #[test]
570    fn test_residual_bitand_c() {
571        let r1 = Residual::new(5, 2);
572        let r2 = Residual::new(10, 3);
573        assert_eq!((r1 & r2).to_string(), "0@0");
574    }
575
576    #[test]
577    fn test_residual_bitand_d() {
578        let r1 = Residual::new(3, 2);
579        let r2 = Residual::new(3, 1);
580        assert_eq!((r1 & r2).to_string(), "0@0");
581    }
582
583    //--------------------------------------------------------------------------
584
585    #[test]
586    fn test_residual_contains_a() {
587        let r1 = Residual::new(3, 0);
588        assert_eq!(r1.contains(-3), true);
589        assert_eq!(r1.contains(-2), false);
590        assert_eq!(r1.contains(-1), false);
591        assert_eq!(r1.contains(0), true);
592        assert_eq!(r1.contains(1), false);
593        assert_eq!(r1.contains(2), false);
594        assert_eq!(r1.contains(3), true);
595        assert_eq!(r1.contains(4), false);
596        assert_eq!(r1.contains(5), false);
597    }
598
599    #[test]
600    fn test_residual_contains_b() {
601        let r1 = Residual::new(0, 0);
602        assert_eq!(r1.contains(-2), false);
603        assert_eq!(r1.contains(-1), false);
604        assert_eq!(r1.contains(0), false);
605        assert_eq!(r1.contains(1), false);
606        assert_eq!(r1.contains(2), false);
607        assert_eq!(r1.contains(3), false);
608    }
609
610    #[test]
611    fn test_residual_contains_c() {
612        let r1 = Residual::new(3, 1);
613        assert_eq!(r1.contains(-3), false);
614        assert_eq!(r1.contains(-2), true);
615        assert_eq!(r1.contains(-1), false);
616        assert_eq!(r1.contains(0), false);
617        assert_eq!(r1.contains(1), true);
618        assert_eq!(r1.contains(2), false);
619        assert_eq!(r1.contains(3), false);
620        assert_eq!(r1.contains(4), true);
621    }
622
623    //--------------------------------------------------------------------------
624
625    #[test]
626    fn test_sieve_new_a() {
627        let s1 = Sieve::new("3@1");
628        assert_eq!(s1.to_string(), "Sieve{3@1}");
629    }
630
631    #[test]
632    fn test_sieve_new_b() {
633        let s1 = Sieve::new("3@4");
634        assert_eq!(s1.to_string(), "Sieve{3@1}");
635    }
636
637    #[test]
638    fn test_sieve_new_c() {
639        let s1 = Sieve::new("5@5");
640        assert_eq!(s1.to_string(), "Sieve{5@0}");
641    }
642
643    #[test]
644    fn test_sieve_new_d() {
645        let s1 = Sieve::new("0@5");
646        assert_eq!(s1.to_string(), "Sieve{0@0}");
647    }
648
649    #[test]
650    fn test_sieve_contains_a() {
651        let r1 = Residual::new(3, 0);
652        let s1 = SieveNode::Unit(r1);
653
654        let pos = vec![-3, -2, -1, 0, 1];
655        let val = vec![true, false, false, true, false];
656        for (p, b) in pos.iter().zip(val.iter()) {
657            assert_eq!(s1.contains(*p), *b);
658        }
659    }
660
661    #[test]
662    fn test_sieve_contains_b() {
663        let r1 = Residual::new(3, 0);
664        let r2 = Residual::new(3, 1);
665        let s1 = SieveNode::Union(Box::new(SieveNode::Unit(r1)), Box::new(SieveNode::Unit(r2)));
666
667        assert_eq!(s1.contains(-2), true);
668        assert_eq!(s1.contains(-1), false);
669        assert_eq!(s1.contains(0), true);
670        assert_eq!(s1.contains(1), true);
671        assert_eq!(s1.contains(2), false);
672        assert_eq!(s1.contains(3), true);
673        assert_eq!(s1.contains(4), true);
674    }
675
676    //--------------------------------------------------------------------------
677
678    #[test]
679    fn test_sieve_operators_a() {
680        let s1 = Sieve::new("3@1");
681        let s2 = Sieve::new("4@0");
682        let s3 = s1 | s2;
683
684        assert_eq!(s3.to_string(), "Sieve{3@1|4@0}");
685    }
686
687    #[test]
688    fn test_sieve_operators_b() {
689        let s1 = Sieve::new("3@1");
690        let s2 = Sieve::new("4@0");
691        let s3 = &s1 | &s2;
692
693        assert_eq!(s3.to_string(), "Sieve{3@1|4@0}");
694    }
695
696    #[test]
697    fn test_sieve_operators_c() {
698        let s1 = Sieve::new("3@1");
699        let s2 = Sieve::new("4@0");
700        let s3 = &s1 & &s2;
701
702        assert_eq!(s3.to_string(), "Sieve{3@1&4@0}");
703    }
704
705    #[test]
706    fn test_sieve_operators_d() {
707        let s1 = Sieve::new("3@1");
708        let s2 = Sieve::new("4@0");
709        let s3 = &s1 ^ &s2;
710
711        assert_eq!(s3.to_string(), "Sieve{3@1^4@0}");
712    }
713
714    #[test]
715    fn test_sieve_operators_e() {
716        let s1 = Sieve::new("3@1");
717        let s3 = !&s1;
718        assert_eq!(s3.to_string(), "Sieve{!(3@1)}");
719    }
720}
xensieve/lib.rs

xensieve/
lib.rs
