int-interval-stack 0.3.0

Integer half-open interval stack structures for overlap multiplicity.
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

use int_interval::traits::{COStartLenConstruct, IntPrimitive};
use rayon::iter::{IndexedParallelIterator, IntoParallelIterator, ParallelIterator};

use super::*;

#[inline]
fn window_count<I>(from: I::CoordType, to: I::CoordType, len: I::MeasureType) -> Option<usize>
where
    I: IntCO + COStartLenConstruct,
    I::MeasureType: TryInto<usize>,
{
    if len == I::MeasureType::zero() {
        return None;
    }

    let domain = I::try_new(from, to)?;
    let remaining = domain.len().checked_sub(len)?;
    let count = remaining.checked_add(I::MeasureType::one())?;

    count.try_into().ok()
}

#[inline]
fn start_at<I>(from: I::CoordType, index: usize) -> Option<I::CoordType>
where
    I: IntCO + COStartLenConstruct,
{
    if index == 0 {
        return Some(from);
    }

    let offset = I::MeasureType::checked_from(index)?;

    I::checked_from_start_len(from, offset).map(|interval| interval.end_excl())
}

#[inline]
fn window_at<'a, I>(
    stack: &'a IntCOStack<I>,
    from: I::CoordType,
    len: I::MeasureType,
    index: usize,
) -> Option<StackWindow<'a, I>>
where
    I: IntCO + COStartLenConstruct + Copy,
{
    let start = start_at::<I>(from, index)?;
    let interval = I::checked_from_start_len(start, len)?;

    Some(StackWindow::new(stack, interval))
}

impl<I> IntCOStack<I>
where
    I: IntCO + COStartLenConstruct + Copy,
    I::MeasureType: TryInto<usize>,
{
    /// Iterates over all fixed-length windows fully contained in `[from, to)`.
    ///
    /// Window starts advance by one coordinate unit:
    ///
    /// ```text
    /// [from,     from + len)
    /// [from + 1, from + 1 + len)
    /// ...
    /// ```
    ///
    /// Returns an empty iterator when:
    ///
    /// - `from >= to`;
    /// - `len == 0`;
    /// - `len` is greater than the measure of `[from, to)`;
    /// - the window count cannot be represented as `usize`.
    #[inline]
    pub fn iter_windows(
        &self,
        from: I::CoordType,
        to: I::CoordType,
        len: I::MeasureType,
    ) -> impl DoubleEndedIterator<Item = StackWindow<'_, I>> + ExactSizeIterator {
        let count = window_count::<I>(from, to, len).unwrap_or(0);

        (0..count).map(move |index| {
            window_at(self, from, len, index)
                .expect("validated window index must produce a representable window")
        })
    }

    /// Iterates in parallel over all fixed-length windows fully contained in
    /// `[from, to)`.
    ///
    /// The valid window-start range is represented as an indexed integer
    /// range, allowing Rayon to split the work directly without a serial
    /// producer or `par_bridge`.
    #[inline]
    pub fn par_iter_windows(
        &self,
        from: I::CoordType,
        to: I::CoordType,
        len: I::MeasureType,
    ) -> impl IndexedParallelIterator<Item = StackWindow<'_, I>>
    where
        I: Send + Sync,
    {
        let count = window_count::<I>(from, to, len).unwrap_or(0);

        (0..count).into_par_iter().map(move |index| {
            window_at(self, from, len, index)
                .expect("validated window index must produce a representable window")
        })
    }
}

#[cfg(test)]
mod test_support;

#[cfg(test)]
mod tests_for_window_count;

#[cfg(test)]
mod tests_for_start_at;

#[cfg(test)]
mod tests_for_window_at;

#[cfg(test)]
mod tests_for_iter_windows;