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

use std::collections::btree_map;
use std::iter::{self, FromIterator};
use super::util;
use super::{BitmapIterator, Treemap, Bitmap};

struct To64Iter<'a> {
    key: u32,
    iterator: BitmapIterator<'a>,
}

impl<'a> Iterator for To64Iter<'a> {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        self.iterator.next().map(|n| util::join(self.key, n))
    }
}

fn to64iter<'a>(t: (&'a u32, &'a Bitmap)) -> To64Iter<'a> {
    To64Iter {
        key: *t.0,
        iterator: t.1.iter(),
    }
}

type InnerIter<'a> = iter::FlatMap<btree_map::Iter<'a, u32, Bitmap>,
                                   To64Iter<'a>,
                                   fn((&'a u32, &'a Bitmap)) -> To64Iter<'a>>;

pub struct TreemapIterator<'a> {
    iter: InnerIter<'a>,
}

impl<'a> TreemapIterator<'a> {
    fn new(treemap: &'a Treemap) -> Self {
        let iter = treemap.map
                       .iter()
                       .flat_map(to64iter as _);

        TreemapIterator { iter }
    }
}

impl<'a> Iterator for TreemapIterator<'a> {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        self.iter.next()
    }
}

impl Treemap {
    /// Returns an iterator over each value stored in the bitmap.
    /// Returned values are ordered in ascending order.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::u64;
    /// use croaring::Treemap;
    ///
    /// let mut treemap = Treemap::create();
    /// treemap.add(4);
    /// treemap.add(3);
    /// treemap.add(2);
    /// treemap.add(2);
    /// treemap.add(u64::MAX);
    /// let mut iterator = treemap.iter();
    ///
    /// assert_eq!(iterator.next(), Some(2));
    /// assert_eq!(iterator.next(), Some(3));
    /// assert_eq!(iterator.next(), Some(4));
    /// assert_eq!(iterator.next(), Some(u64::MAX));
    /// assert_eq!(iterator.next(), None);
    /// ```
    pub fn iter(&self) -> TreemapIterator {
        TreemapIterator::new(self)
    }
}

impl FromIterator<u64> for Treemap {
    /// Convenience method for creating treemap from an iterator.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::{u32, u64};
    /// use croaring::Treemap;
    ///
    /// let treemap: Treemap = (1..3).chain(u64::from(u32::MAX)+1..u64::from(u32::MAX)+10).collect();
    ///
    /// assert!(!treemap.is_empty());
    /// assert!(treemap.contains(1));
    /// assert!(treemap.contains(2));
    /// assert!(treemap.contains(u64::from(u32::MAX)+1));
    /// assert!(treemap.contains(u64::from(u32::MAX)+5));
    /// assert_eq!(treemap.cardinality(), 11);
    /// ```
    fn from_iter<I: IntoIterator<Item = u64>>(iter: I) -> Self {
        let mut result = Self::create();
        result.extend(iter);
        result
    }
}

impl Extend<u64> for Treemap {
    fn extend<T: IntoIterator<Item=u64>>(&mut self, iter: T) {
        for item in iter {
            self.add(item);
        }
    }
}