croaring 2.6.0

Rust wrapper for CRoaring
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

use super::util;
use crate::bitmap::BitmapIterator;
use crate::{Bitmap, Treemap};
use alloc::collections::btree_map;
use core::iter;

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>((key, bitmap): (&'a u32, &'a Bitmap)) -> To64Iter<'a> {
    assert!(!bitmap.is_empty(), "empty bitmap at {key}");
    To64Iter {
        key: *key,
        iterator: bitmap.iter(),
    }
}

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

/// Iterator over values stored in the treemap
///
/// Values are ordered in ascending order
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::new();
    /// 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);
    /// ```
    #[must_use]
    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::new();
        result.extend(iter);
        result
    }
}

impl Extend<u64> for Treemap {
    fn extend<T: IntoIterator<Item = u64>>(&mut self, iter: T) {
        // Potentially reduce outer map lookups by optimistically
        // assuming that adjacent values will belong to the same inner bitmap.
        let mut last_bitmap: Option<(u32, &mut Bitmap)> = None;
        for item in iter {
            let (high, low) = util::split(item);
            if let Some((last_high, ref mut last_bitmap)) = last_bitmap {
                if last_high == high {
                    last_bitmap.add(low);
                    continue;
                }
            }
            let bitmap = self.get_or_create(high);
            bitmap.add(low);
            last_bitmap = Some((high, bitmap));
        }
    }
}