downstream 1.23.0

downstream provides efficient, constant-space implementations of stream curation algorithms
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

use super::{AssignStorageSiteTrait, HasIngestCapacityTrait, SteadyAlgo, TiltedAlgo};
use crate::_auxlib as aux;

/// Does this algorithm have the capacity to ingest a data item at logical time
/// T?
///
/// @template Uint Unsigned integer type for operands.
/// @param S The number of buffer sites available.
/// @param T Queried logical time.
/// @returns Whether there is capacity to ingest at time T.
#[allow(non_snake_case)]
pub fn has_ingest_capacity<Uint: aux::UnsignedTrait>(S: Uint, T: Uint) -> bool {
    let _0: Uint = Uint::zero();
    let _1: Uint = Uint::one();
    let _2: Uint = _1 + _1;
    let _3: Uint = _2 + _1;
    if S < _3 || S % _3 != _0 {
        return false;
    }
    let third_S: Uint = S / _3;
    let two_thirds_S: Uint = _2 * third_S;
    let t_div_3: Uint = T / _3;
    let has_capacity_1st = SteadyAlgo::has_ingest_capacity(
        two_thirds_S,
        t_div_3 * _2 + aux::from_bool::<Uint>(T % _3 > _0),
    );
    let has_capacity_2nd = T < _2 || TiltedAlgo::has_ingest_capacity(third_S, (T - _2) / _3);

    has_capacity_1st && has_capacity_2nd
}

/// Site selection for hybrid steady/tilted curation.
///
/// What buffer site should the T'th data item be stored to?
///
/// @template Uint Unsigned integer type for operands and return value.
/// @param S Buffer size.
///     Must be divisible by 3, with S/3 being a power of two.
/// @param T Current logical time.
/// @returns The selected storage site, if any.
///     Returns S if no site should be selected (i.e., discard).
#[allow(non_snake_case)]
pub fn _assign_storage_site<Uint: aux::UnsignedTrait>(S: Uint, T: Uint) -> Uint {
    debug_assert!(has_ingest_capacity(S, T));

    let _1: Uint = Uint::one();
    let _2: Uint = _1 + _1;
    let _3: Uint = _2 + _1;
    let third_S: Uint = S / _3;
    let two_thirds_S: Uint = _2 * third_S;
    let remainder: Uint = T % _3;
    if remainder < _2 {
        let adj_T: Uint = (T / _3) * _2 + remainder;
        let site: Uint = SteadyAlgo::_assign_storage_site(two_thirds_S, adj_T);
        if site == two_thirds_S {
            S
        } else {
            site
        }
    } else {
        let adj_T: Uint = T / _3;
        let site: Uint = TiltedAlgo::_assign_storage_site(third_S, adj_T);
        if site == third_S {
            S
        } else {
            two_thirds_S + site
        }
    }
}

/// Site selection for hybrid steady/tilted curation.
///
/// What buffer site should the T'th data item be stored to?
///
/// @template Uint Unsigned integer type for operands and return value.
/// @param S Buffer size.
///     Must be divisible by 3, with S/3 being a power of two.
/// @param T Current logical time.
/// @returns The selected storage site, if any.
///     Returns None if no site should be selected (i.e., discard).
#[allow(non_snake_case)]
pub fn assign_storage_site<Uint: aux::UnsignedTrait>(S: Uint, T: Uint) -> Option<Uint> {
    let k: Uint = _assign_storage_site(S, T);
    if k == S {
        None
    } else {
        Some(k)
    }
}

pub struct Algo;

#[allow(non_snake_case)]
impl crate::dstream::HasIngestCapacityTrait for Algo {
    fn has_ingest_capacity<Uint: aux::UnsignedTrait>(S: Uint, T: Uint) -> bool {
        has_ingest_capacity::<Uint>(S, T)
    }
}

#[allow(non_snake_case)]
impl crate::dstream::AssignStorageSiteTrait for Algo {
    fn _assign_storage_site<Uint: aux::UnsignedTrait>(S: Uint, T: Uint) -> Uint {
        _assign_storage_site::<Uint>(S, T)
    }

    fn assign_storage_site<Uint: aux::UnsignedTrait>(S: Uint, T: Uint) -> Option<Uint> {
        assign_storage_site::<Uint>(S, T)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_smoke_has_ingest_capacity() {
        has_ingest_capacity::<u32>(12, 5);
    }

    #[test]
    fn test_smoke_assign_storage_site() {
        assign_storage_site::<u32>(12, 5);
    }

    #[test]
    fn test_smoke_impl_assign_storage_site() {
        _assign_storage_site::<u32>(12, 5);
    }
}