immutable_seq/
digit.rs

1use std::ops;
2
3use lazy::Lazy;
4use measure::Measure;
5use node;
6use node::Node;
7use node::Node::{Node2, Node3};
8use self::Digit::{One, Two, Three, Four};
9use self::IterDigit::{IZero, IOne, ITwo, IThree};
10
11/// A short sequence of 2-3-trees.
12#[derive(Debug)]
13pub enum Digit<T,M> {
14    One  (Lazy<Node<T,M>>),
15    Two  (Lazy<Node<T,M>>, Lazy<Node<T,M>>),
16    Three(Lazy<Node<T,M>>, Lazy<Node<T,M>>, Lazy<Node<T,M>>),
17    Four (Lazy<Node<T,M>>, Lazy<Node<T,M>>, Lazy<Node<T,M>>, Lazy<Node<T,M>>),
18}
19
20impl<T,M> Digit<T,M> {
21    /// Iterate of the items in the 2-3-trees in this digit.
22    pub fn iter<'a>(&'a self) -> Iter<'a, T, M> {
23        Iter::new(self)
24    }
25}
26
27impl<'a,T,M> From<&'a Node<T,M>> for Digit<T,M> {
28    fn from(node: &'a Node<T,M>) -> Digit<T,M> {
29        match *node {
30            Node2(_, ref x0, ref x1) =>
31                Two(x0.clone(), x1.clone()),
32            Node3(_, ref x0, ref x1, ref x2) =>
33                Three(x0.clone(), x1.clone(), x2.clone()),
34            _ => unreachable!(),
35        }
36    }
37}
38
39impl<T,M> Clone for Digit<T,M> {
40    fn clone(&self) -> Digit<T,M> {
41        match *self {
42            One(ref x0) =>
43                One(x0.clone()),
44            Two(ref x0, ref x1) =>
45                Two(x0.clone(), x1.clone()),
46            Three(ref x0, ref x1, ref x2) =>
47                Three(x0.clone(), x1.clone(), x2.clone()),
48            Four(ref x0, ref x1, ref x2, ref x3) =>
49                Four(x0.clone(), x1.clone(), x2.clone(), x3.clone()),
50        }
51    }
52}
53
54impl<T,M> Measure<M> for Digit<T,M>
55    where T: Measure<M>,
56          M: ops::Add<Output=M> + Copy {
57    fn measure(&self) -> M {
58        match *self {
59            One(ref x0) =>
60                x0.measure(),
61            Two(ref x0, ref x1) =>
62                x0.measure() + x1.measure(),
63            Three(ref x0, ref x1, ref x2) =>
64                x0.measure() + x1.measure() + x2.measure(),
65            Four(ref x0, ref x1, ref x2, ref x3) =>
66                x0.measure() + x1.measure() + x2.measure() + x3.measure(),
67        }
68    }
69}
70
71/// A suffix of a digit, used to track the state in `Iter`
72#[derive(Debug)]
73pub enum IterDigit<'a, T: 'a, M: 'a> {
74    IZero,
75    IOne  (&'a Lazy<Node<T,M>>),
76    ITwo  (&'a Lazy<Node<T,M>>, &'a Lazy<Node<T,M>>),
77    IThree(&'a Lazy<Node<T,M>>, &'a Lazy<Node<T,M>>, &'a Lazy<Node<T,M>>),
78}
79
80/// An iterator over the values in the leaves of the 2-3-trees in this digit
81#[derive(Debug)]
82pub struct Iter<'a, T: 'a, M: 'a> {
83    digit: IterDigit<'a,T,M>,
84    inner: node::Iter<'a,T,M>,
85}
86
87impl<'a, T, M> Iter<'a, T, M> {
88    fn new(digit: &'a Digit<T,M>) -> Iter<'a, T, M> {
89        match *digit {
90            One(ref x0) => Iter {
91                digit: IZero,
92                inner: x0.iter(),
93            },
94            Two(ref x0, ref x1) => Iter {
95                digit: IOne(x1),
96                inner: x0.iter(),
97            },
98            Three(ref x0, ref x1, ref x2) => Iter {
99                digit: ITwo(x1,x2),
100                inner: x0.iter(),
101            },
102            Four(ref x0, ref x1, ref x2, ref x3) => Iter {
103                digit: IThree(x1,x2,x3),
104                inner: x0.iter(),
105            },
106        }
107    }
108    /// An `Iter` that is empty (yield no values)
109    ///
110    /// This is helpful in  `finger_tree::Iter`.
111    pub fn empty() -> Iter<'a, T, M> {
112        Iter {
113            inner: node::Iter::empty(),
114            digit: IZero,
115        }
116    }
117}
118
119impl<'a, T:'a, M:'a> Iterator for Iter<'a, T, M> {
120    type Item = &'a T;
121    fn next(&mut self) -> Option<&'a T> {
122        loop {
123            match self.inner.next() {
124                Some(x) => return Some(x),
125                None => {}
126            };
127            match self.digit {
128                IZero => return None,
129                IOne(x0) => {
130                    self.digit = IZero;
131                    self.inner = x0.iter();
132                },
133                ITwo(x0,x1) => {
134                    self.digit = IOne(x1);
135                    self.inner = x0.iter();
136                },
137                IThree(x0,x1,x2) => {
138                    self.digit = ITwo(x1,x2);
139                    self.inner = x0.iter();
140                },
141            }
142        }
143    }
144}
145
146#[doc(hidden)]
147#[macro_export]
148macro_rules! digit {
149    ($e0: expr) => {
150        $crate::digit::Digit::One($e0)
151    };
152    ($e0: expr, $e1: expr) => {
153        $crate::digit::Digit::Two($e0, $e1)
154    };
155    ($e0: expr, $e1: expr, $e2: expr) => {
156        $crate::digit::Digit::Three($e0, $e1, $e2)
157    };
158    ($e0: expr, $e1: expr, $e2: expr, $e3: expr) => {
159        $crate::digit::Digit::Four($e0, $e1, $e2, $e3)
160    };
161}
162
163#[doc(hidden)]
164#[macro_export]
165macro_rules! opt_digit {
166    () => {
167        ::std::option::Option::None
168    };
169    ($($e: expr),+) => {
170        ::std::option::Option::Some(digit!($($e),*))
171    }
172}
173
174#[doc(hidden)]
175#[macro_export]
176macro_rules! build_digit {
177    ($($f0: expr, $f1: expr, $f2: expr),+) => {
178        digit!($($crate::node::node3($f0,$f1,$f2)),*)
179    };
180    ($e0: expr, $e1: expr $(, $f0: expr, $f1: expr, $f2: expr)*) => {
181        digit!($crate::node::node2($e0, $e1)
182               $(, $crate::node::node3($f0,$f1,$f2))*)
183    };
184    ($e0: expr, $e1: expr, $e2: expr, $e3: expr $(, $f0: expr, $f1: expr, $f2: expr)*) => {
185        digit!($crate::node::node2($e0, $e1),
186               $crate::node::node2($e2, $e3)
187               $(, $crate::node::node3($f0,$f1,$f2))*)
188    };
189}
190
191#[doc(hidden)]
192#[macro_export]
193macro_rules! add_digits {
194    ( ; $($e: expr),*) => {
195        build_digit!($($e),*)
196    };
197    ($d0: expr $(, $d: expr)* ; $($e: expr),*) => {
198        match $d0 {
199            One(x0) =>
200                add_digits!($($d),* ; $($e, )* x0),
201            Two(x0, x1) =>
202                add_digits!($($d),* ; $($e, )* x0, x1),
203            Three(x0, x1, x2) =>
204                add_digits!($($d),* ; $($e, )* x0, x1, x2),
205            Four(x0, x1, x2, x3) =>
206                add_digits!($($d),* ; $($e, )* x0, x1, x2, x3),
207        }
208    };
209    ($($e:expr),*) => {
210        add_digits!($($e),*;)
211    }
212}
213
214macro_rules! lookup {
215    ($pred: expr, $i: expr ; $n0: expr) => {
216        node::lookup($pred, $i, $n0)
217    };
218    ($pred: expr, $i: expr ; $n0: expr $(, $n: expr)*) => {{
219        let j = $i + $n0.measure();
220        if $pred(j) {
221            node::lookup($pred, $i, $n0)
222        } else {
223            lookup!($pred, j ; $($n),*)
224        }
225    }};
226}
227
228// macro_rules! lookup {
229//     ($node: expr, $func: expr, $i: expr ; $n0: expr) => {
230//         $node($func, $i, $n0)
231//     };
232//     ($node: expr, $func: expr, $i: expr ; $n0: expr $(, $n: expr)*) => {{
233//         let j = $i + $n0.measure();
234//         if $func(j) {
235//             $node($func, $i, $n0)
236//         } else {
237//             lookup!($node, $func, j ; $($n),*)
238//         }
239//     }};
240// }
241
242pub fn lookup<T,M,P>(pred: P, i: M, digit: &Digit<T,M>) -> (&T,M)
243    where T: Measure<M> + 'static,
244          M: ops::Add<Output=M> + Copy + 'static,
245          P: Fn(M) -> bool
246{
247    match *digit {
248        One(ref x0) =>
249            lookup!(pred, i ; x0),
250        Two(ref x0, ref x1) =>
251            lookup!(pred, i ; x0, x1),
252        Three(ref x0, ref x1, ref x2) =>
253            lookup!(pred, i ; x0, x1, x2),
254        Four(ref x0, ref x1, ref x2, ref x3) =>
255            lookup!(pred, i ; x0, x1, x2, x3),
256    }
257}
258
259macro_rules! adjust {
260    ($func: expr, $pred: expr, $i: expr $(, $b: expr)*; $n0: expr) => {
261        digit!($($b.clone() , )* node::adjust($func, $pred, $i, $n0))
262    };
263    ($func: expr, $pred: expr, $i: expr $(, $b: expr)* ; $n0: expr $(, $n: expr)*) => {{
264        let j = $i + $n0.measure();
265        if $pred(j) {
266            digit!($($b.clone() , )* node::adjust($func, $pred, $i, $n0) $(, $n.clone() )*)
267        } else {
268            adjust!($func, $pred, j $(, $b)* , $n0 ; $($n),*)
269        }
270    }};
271}
272
273pub fn adjust<T,M,P,F>(func: F, pred: P, i: M, digit: &Digit<T,M>) -> Digit<T,M>
274    where T: Measure<M> + 'static,
275          M: ops::Add<Output=M> + Copy + 'static,
276          P: Fn(M) -> bool,
277          F: FnOnce(&T) -> T
278{
279    match *digit {
280        One(ref x0) =>
281            adjust!(func, pred, i ; x0),
282        Two(ref x0, ref x1) =>
283            adjust!(func, pred, i ; x0, x1),
284        Three(ref x0, ref x1, ref x2) =>
285            adjust!(func, pred, i ; x0, x1, x2),
286        Four(ref x0, ref x1, ref x2, ref x3) =>
287            adjust!(func, pred, i ; x0, x1, x2, x3),
288    }
289}
290
291macro_rules! split_once {
292    ($pred: expr, $i: expr $(, $b: expr)* ; $n0: expr) => {
293        (opt_digit!($( $b.clone() ),*) , $n0, ::std::option::Option::None)
294    };
295    ($pred: expr, $i: expr $(, $b: expr)* ; $n0: expr $(, $n: expr)*) => {{
296        let j = $i + $n0.measure();
297        if $pred(j) {
298            (opt_digit!($( $b.clone() ),*) , $n0 , opt_digit!($( $n.clone() ),*))
299        } else {
300            split_once!($pred, j, $($b , )* $n0 ; $($n),*)
301        }
302    }};
303}
304
305pub fn split_once<'a,T,M,P>(pred: &P, i: M, digit: &'a Digit<T,M>)
306                    -> (Option<Digit<T,M>>,&'a Lazy<Node<T,M>>,Option<Digit<T,M>>)
307    where T: Measure<M> + 'static,
308          M: ops::Add<Output=M> + Copy + 'static,
309          P: Fn(M) -> bool
310{
311    match *digit {
312        One(ref x0) =>
313            split_once!(pred, i ; x0),
314        Two(ref x0, ref x1) =>
315            split_once!(pred, i ; x0, x1),
316        Three(ref x0, ref x1, ref x2) =>
317            split_once!(pred, i ; x0, x1, x2),
318        Four(ref x0, ref x1, ref x2, ref x3) =>
319            split_once!(pred, i ; x0, x1, x2, x3),
320    }
321}
322
323#[cfg(test)]
324mod test {
325    use super::*;
326    use node::leaf;
327
328    #[test]
329    fn test_digit_iter() {
330        let digit: Digit<u32,usize> = digit!(
331            leaf(0),
332            leaf(1),
333            leaf(2),
334            leaf(3));
335        let result:Vec<u32> = digit.iter().map(|x| *x).collect();
336        let expected:Vec<u32> = vec![0,1,2,3];
337        assert_eq!(result,expected);
338    }
339}
immutable_seq/digit.rs

immutable_seq/
digit.rs
