glr 0.2.0

RNGLR parser generator
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

use std::ops::BitOrAssign;
use std::{fmt, iter, mem, slice};

#[derive(Clone, Default)]
pub struct BitSet(Vec<u32>);

impl BitSet {
    pub fn new() -> Self {
        Self(Vec::new())
    }

    pub fn contains(&self, x: u32) -> bool {
        self.0
            .get((x / u32::BITS) as usize)
            .map_or(false, |&u| u & 1 << (x % u32::BITS) != 0)
    }

    pub fn insert(&mut self, x: u32) {
        let i: usize = (x / u32::BITS) as usize;
        self.0
            .extend(iter::repeat(0).take((i + 1).saturating_sub(self.0.len())));
        self.0[i] |= 1 << (x % u32::BITS);
    }

    pub fn len(&self) -> u32 {
        self.0.iter().copied().map(u32::count_ones).sum()
    }

    pub fn clear(&mut self) {
        self.0.fill(0);
    }

    pub fn iter(&self) -> Iter<iter::Copied<slice::Iter<u32>>> {
        Iter::new(self.0.iter().copied())
    }
}

impl BitOrAssign<&Self> for BitSet {
    fn bitor_assign(&mut self, rhs: &Self) {
        for (a, &b) in self.0.iter_mut().zip(rhs.0.iter()) {
            *a |= b;
        }
        self.0
            .extend_from_slice(rhs.0.get(self.0.len()..).unwrap_or(&[]));
    }
}

impl BitOrAssign<Self> for BitSet {
    fn bitor_assign(&mut self, mut rhs: Self) {
        if rhs.0.len() > self.0.len() {
            mem::swap(self, &mut rhs);
        }
        *self |= &rhs;
    }
}

impl FromIterator<u32> for BitSet {
    fn from_iter<T: IntoIterator<Item = u32>>(iter: T) -> Self {
        let mut set = Self::new();
        for x in iter {
            set.insert(x);
        }
        set
    }
}

#[derive(Debug)]
pub struct Iter<I> {
    offset: u32,
    head: u32,
    tail: I,
}

impl<I: Iterator<Item = u32>> Iter<I> {
    fn new(mut iter: I) -> Self {
        Self {
            offset: 0,
            head: iter.next().unwrap_or(0),
            tail: iter,
        }
    }
}

impl<I: Iterator<Item = u32>> Iterator for Iter<I> {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        while self.head == 0 {
            self.head = self.tail.next()?;
            self.offset += u32::BITS;
        }
        let i = self.offset + self.head.trailing_zeros();
        self.head &= self.head - 1;
        Some(i)
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        match self.tail.size_hint() {
            (_, Some(h)) => (0, Some((1 + h) * u32::BITS as usize)),
            _ => (0, None),
        }
    }
}

impl<'a> IntoIterator for &'a BitSet {
    type Item = u32;
    type IntoIter = Iter<iter::Copied<slice::Iter<'a, u32>>>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl fmt::Debug for BitSet {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.debug_set().entries(self).finish()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn try_insert() {
        let mut s = BitSet::new();
        s.insert(3);
        s.insert(64);
        assert_eq!(s.0.len(), 3);

        assert!(s.contains(3));
        assert!(s.contains(64));

        let mut iter = s.iter();
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), Some(64));
        assert_eq!(iter.next(), None);
    }
}