hi_sparse_bitset 0.9.0

Hierarchical sparse bitset. Incredibly high performance. Compact memory usage.
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

//! Cache used during traverse by [reduce] operations.
//!
//! [reduce]: crate::reduce()

use crate::ops::BitSetOp;
use crate::bitset_interface::{BitSetBase, LevelMasksIterExt};
use crate::reduce::{DynamicCacheImpl, FixedCacheImpl, NonCachedImpl, ReduceCacheImpl};

/// Cache is not used.
///
/// If reduced iterator contains other nested reduce operations - all of them
/// WILL NOT use cache as well.
///
/// # Example 1
///
/// ```
/// # use itertools::assert_equal;
/// # use hi_sparse_bitset::{reduce, reduce_w_cache};
/// # use hi_sparse_bitset::ops::{And, Or};
/// # use hi_sparse_bitset::cache::NoCache;
/// # type BitSet = hi_sparse_bitset::BitSet<hi_sparse_bitset::config::_128bit>;
/// let su1 = [BitSet::from([1,2]), BitSet::from([5,6])];
/// let union1 = reduce(Or, su1.iter()).unwrap();
///
/// let su2 = [BitSet::from([1,3]), BitSet::from([4,6])];
/// let union2 = reduce(Or, su2.iter()).unwrap();
///
/// let si = [union1, union2];
/// let intersection = reduce_w_cache(And, si.iter(), NoCache).unwrap();
///
/// // Not only `intersection` will be computed without cache,
/// // but also `union1` and `union2`.
/// assert_equal(intersection, [1,6]);
///
/// ```
///
/// # Example 2
///
/// ```
/// # use itertools::assert_equal;
/// # use hi_sparse_bitset::{reduce, reduce_w_cache};
/// # use hi_sparse_bitset::ops::{And, Or};
/// # use hi_sparse_bitset::cache::NoCache;
/// # type BitSet = hi_sparse_bitset::BitSet<hi_sparse_bitset::config::_128bit>;
/// let su1 = [BitSet::from([1,2]), BitSet::from([5,6])];
/// let union1 = reduce_w_cache(Or, su1.iter(), NoCache).unwrap();
///
/// let su2 = [BitSet::from([1,3]), BitSet::from([4,6])];
/// let union2 = reduce_w_cache(Or, su2.iter(), NoCache).unwrap();
///
/// let si = [union1, union2];
/// let intersection = reduce(And, si.iter()).unwrap();
///
/// // Only `union1` and `union2` will not use cache, `intersection`
/// // will be computed with cache.
/// assert_equal(intersection, [1,6]);
///
/// ```
///
/// [reduce]: crate::reduce()
#[derive(Default, Copy, Clone)]
pub struct NoCache;

/// Cache with fixed capacity.
///
/// This cache is noop to construct.
/// Should be your default choice.
///
/// N.B. Pay attention to stack-mem usage when working with
/// reduce on reduce on reduce ...
#[derive(Default, Copy, Clone)]
pub struct FixedCache<const N:usize>;

/// Dynamically built in-heap cache.
///
/// You want this, when your cache doesn't fit stack.
/// This can happened, when you work with enormously large number of sets,
/// and/or work with deep [reduce] operations. Alternatively, you
/// can use [NoCache].
///
/// [reduce]: crate::reduce()
#[derive(Default, Copy, Clone)]
pub struct DynamicCache;

pub trait ReduceCache: Default + 'static{
    /// usize::MAX - if unlimited.
    const MAX_LEN: usize;
    type Impl<Op, S>
        : ReduceCacheImpl<
            Sets = S,
            Conf = <S::Item as BitSetBase>::Conf
        >
    where
        Op: BitSetOp,
        S: Iterator + Clone,
        S::Item: LevelMasksIterExt;
}

impl ReduceCache for NoCache{
    const MAX_LEN: usize = usize::MAX;
    type Impl<Op, S> = NonCachedImpl<Op, S>
    where
        Op: BitSetOp,
        S: Iterator + Clone,
        S::Item: LevelMasksIterExt;
}

impl<const N: usize> ReduceCache for FixedCache<N>{
    const MAX_LEN: usize = N;
    type Impl<Op, S> = FixedCacheImpl<Op, S, N>
    where
        Op: BitSetOp,
        S: Iterator + Clone,
        S::Item: LevelMasksIterExt;
}

impl ReduceCache for DynamicCache{
    const MAX_LEN: usize = usize::MAX;
    type Impl<Op, S> = DynamicCacheImpl<Op, S>
    where
        Op: BitSetOp,
        S: Iterator + Clone,
        S::Item: LevelMasksIterExt;
}