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

//! Informs whether symbols are terminal or nonterminal.

use std::iter;

use bit_vec;
use bit_vec::BitVec;

use grammar::{ContextFree, ContextFreeRef};
use rule::GrammarRule;
use symbol::Symbol;

/// A set of symbols in the form of a bit vector.
pub struct SymbolBitSet {
    bit_vec: BitVec,
}

/// An iterator over a symbol set.
pub struct Iter<'a> {
    iter: iter::Enumerate<bit_vec::Iter<'a>>,
}

impl SymbolBitSet {
    /// Constructs a `SymbolBitSet`.
    pub fn new<'a, G>(grammar: &'a G, elem: bool) -> Self
        where G: ContextFree,
              &'a G: ContextFreeRef<'a, Target = G>
    {
        SymbolBitSet { bit_vec: BitVec::from_elem(grammar.num_syms(), elem) }
    }

    /// Gathers information about whether symbols are terminal or nonterminal.
    /// Constructs a set of terminal symbols.
    ///
    /// Constructs a data structure in O(n) time.
    pub fn terminal_set<'a, G>(grammar: &'a G) -> Self
        where G: ContextFree,
              &'a G: ContextFreeRef<'a, Target = G>
    {
        let mut set = SymbolBitSet::new(grammar, true);
        for rule in grammar.rules() {
            set.set(rule.lhs(), false);
        }
        set
    }

    /// Gathers information about whether symbols are terminal or nonterminal.
    /// Constructs a set of terminal symbols.
    ///
    /// Constructs a data structure in O(n) time.
    pub fn terminal_or_nulling_set<'a, G>(grammar: &'a G) -> Self
        where G: ContextFree,
              &'a G: ContextFreeRef<'a, Target = G>
    {
        let mut set = SymbolBitSet::new(grammar, true);
        for rule in grammar.rules() {
            set.set(rule.lhs(), false);
        }
        for rule in grammar.rules() {
            if rule.rhs().is_empty() {
                set.set(rule.lhs(), true);
            }
        }
        set
    }

    /// Set the entry for a symbol.
    pub fn set(&mut self, sym: Symbol, value: bool) {
        self.bit_vec.set(sym.into(), value);
    }

    /// Checks whether a given symbol is in this set.
    pub fn has_sym(&self, sym: Symbol) -> bool {
        self.bit_vec[sym.into()]
    }

    /// Converts into a bit vector.
    pub fn into_bit_vec(self) -> BitVec {
        self.bit_vec
    }

    /// Iterates over symbols in the set.
    pub fn iter(&self) -> Iter {
        Iter { iter: self.bit_vec.iter().enumerate() }
    }
}

impl<'a> Iterator for Iter<'a> {
    type Item = Symbol;
    fn next(&mut self) -> Option<Self::Item> {
        for (id, is_present) in &mut self.iter {
            if is_present {
                return Some(Symbol::from(id));
            }
        }
        None
    }
}