regex_dfa_gen/
set.rs

1use std::ops::Range;
2use std::fmt::Debug;
3pub type CharRange = Range<char>;
4
5pub const CHAR_MAX : char = 127 as char;
6pub const CHAR_MIN : char = 0 as char;
7
8pub fn add1(c : char) -> char {
9    (c as u8 + 1) as char
10}
11pub fn sub1(c : char) -> char {
12    (c as u8 + 1) as char
13}
14
15#[inline(always)]
16fn range_is_empty<T: Eq>(range: &Range<T>) -> bool {
17    range.start == range.end
18}
19
20
21fn inter_split<T: Ord + Copy>(ran1: Range<T>, ran2 : Range<T>) -> Option<SplitResult<T>> {
22    use SplitResult::*;
23    let start1 = ran1.start;
24    let end1 = ran1.end;
25    let start2 = ran2.start;
26    let end2 = ran2.end;
27
28    if start1 <= start2 {
29        if end1 <= start2 {None}
30        else if start2 < end1 && end1 <= end2 {
31            Some(FirstSecond(
32                start1..start2,
33                start2..end1,
34                end1..end2,
35            ))
36        }
37        else if end2 < end1 {
38            Some(DoubleFirst(
39                start1..start2,
40                start2..end2,
41                end2..end1,
42            ))
43        }
44        else {None}
45    } else {
46        if end2 <= start1 {None}
47        else if start1 < end2 && end2 <= end1 {
48            Some(FirstSecond(
49                end2..end1,
50                start1..end2,
51                start2..start1,
52            ))
53        }
54        else if  end1 < end2 {
55            Some(DoubleSecend(
56                start2..start1,
57                start1..end1,
58                end1..end2,
59            ))
60        }
61        else {None}
62    }
63}
64
65#[derive(Debug, Eq, PartialEq)]
66enum SplitResult<T> {
67    FirstSecond(Range<T>, Range<T>, Range<T>),
68    DoubleFirst(Range<T>, Range<T>, Range<T>),
69    DoubleSecend(Range<T>, Range<T>, Range<T>),
70}
71#[derive(Debug, Clone)]
72pub struct RangeMap<K, V>(pub Vec<(Range<K>, Vec<V>)>);
73
74impl<K: Copy + Ord, V: Clone> RangeMap<K, V> {
75    pub fn new() -> Self {
76        Self(Vec::new())
77    }
78
79    pub fn insert(&mut self, range: Range<K>, value : V) {
80        use SplitResult::*;
81        if range_is_empty(&range) {return;}
82
83        let mut iter = self.0.iter_mut();
84        let mut tmpvec : Vec<(Range<K>, Vec<V>)> = Vec::new();
85        let mut tmp_range :Option<Range<K>> = None;
86        let mut range = Some(range.clone());
87
88        while let Some((r, vec)) = iter.next() {
89            match range.clone().and_then(|ran| inter_split(r.clone(), ran)) {
90                Some(FirstSecond(f, inter, s)) => {
91                    // println!("FirstSecond {:?} {:?} {:?}", f, inter, s);
92                    if !range_is_empty(&f) { tmpvec.push((f, vec.clone())); }
93                    if !range_is_empty(&inter) {
94                        vec.push(value.clone());
95                        tmpvec.push((inter, vec.clone()));
96                    }
97                    if !range_is_empty(&s) {
98                        range = Some(s);
99                    } else {
100                        range = None;
101                    }
102                }
103                Some(DoubleFirst(f1, inter, f2)) => {
104                    // println!("DoubleFirst {:?} {:?} {:?}", f1, inter, f2);
105                    if !range_is_empty(&f1) { tmpvec.push((f1, vec.clone())); }
106                    if !range_is_empty(&inter) {
107                        let mut v = vec.clone();
108                        v.push(value.clone());
109                        tmpvec.push((inter, v));
110                    }
111                    if !range_is_empty(&f2) {
112                        tmpvec.push((f2, vec.clone()));
113                    }
114                    range = None;
115                }
116                Some(DoubleSecend(s1, inter, s2)) => {
117                    // println!("DoubleSecend {:?} {:?} {:?}", s1, inter, s2);
118                    vec.push(value.clone());
119                    tmpvec.push((inter, vec.clone()));
120                    if !range_is_empty(&s1) {
121                        range = Some(s1);
122                    }
123                    if !range_is_empty(&s2) {
124                        tmp_range = Some(s2);
125                    }
126                }
127                None => { tmpvec.push((r.clone(), vec.clone())); },
128            }
129        }
130        if let Some(r) = range {
131            tmpvec.push((r, vec![value.clone()]));
132        }
133        self.0 = tmpvec;
134        if let Some(r) = tmp_range {
135            // println!("enter {:?}", self.0);
136            self.insert(r, value);
137            // println!("exit {:?}", self.0);
138        }
139    }
140}
141
142#[cfg(test)]
143mod test {
144    use super::*;
145    use std::assert_eq;
146    
147    #[test]
148    fn test1() {
149        use SplitResult::*;
150        assert_eq!{
151            inter_split('A'..'D', 'B'..'E'),
152            Some(
153                FirstSecond('A'..'B', 'B'..'D', 'D'..'E')
154            )
155        }
156        assert_eq!{
157            inter_split('A'..'E', 'E'..'Z'),
158            None
159        }
160        assert_eq!{
161            inter_split('A'..'Z', 'E'..'Z'),
162            Some(
163                FirstSecond('A'..'E', 'E'..'Z', 'Z'..'Z')
164            )
165        }
166        assert_eq!{
167            inter_split('A'..'Z', 'E'..'G'),
168            Some(
169                DoubleFirst('A'..'E', 'E'..'G', 'G'..'Z')
170            )
171        }
172
173        assert_eq!{
174            inter_split('B'..'E', 'A'..'D'),
175            Some(
176                FirstSecond('D'..'E', 'B'..'D', 'A'..'B')
177            )
178        }
179    }
180
181    #[test]
182    fn test2() {
183        let mut maps = RangeMap::<char, isize>::new();
184        maps.insert('A'..'Z', 1);
185        maps.insert('A'..'E', 2);
186        maps.insert('C'..'G', 3);
187        assert_eq!{
188            maps.0,
189            vec![
190                ('A'..'C', vec![1, 2]),
191                ('C'..'E', vec![1, 2, 3]),
192                ('E'..'G', vec![1, 3]), 
193                ('G'..'Z', vec![1])
194            ]
195        }
196    }
197    #[test]
198    fn test3() {
199        let mut maps = RangeMap::<char, isize>::new();
200        maps.insert('D'..'E', 1);
201        maps.insert('A'..'Z', 2);
202        maps.insert('D'..'E', 3);
203        assert_eq!{
204            maps.0,
205            vec![
206                ('D'..'E', vec![1, 2, 3]),
207                ('A'..'D', vec![2]),
208                ('E'..'Z', vec![2]), 
209            ]
210        }
211    }
212    #[test]
213    fn test4() {
214        let mut maps = RangeMap::<char, isize>::new();
215        maps.insert('D'..'E', 1);
216        maps.insert('A'..'E', 2);
217        maps.insert('B'..'Z', 3);
218        assert_eq!{
219            maps.0,
220            vec![
221                ('D'..'E', vec![1, 2, 3]),
222                ('A'..'B', vec![2]),
223                ('B'..'D', vec![2, 3]), 
224                ('E'..'Z', vec![3]), 
225            ]
226        }
227    }
228}
229
230pub fn show_char_range(ch : CharRange) -> String {
231    if ch.end as u8 - ch.start as u8 == 1 {
232        format!("{}", ch.start)
233    } else {
234        format!("[{}-{}]", ch.start, (ch.end as u8 - 1) as char)
235    }
236}
regex_dfa_gen/set.rs

regex_dfa_gen/
set.rs
