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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

use crate::*;
use std::{
    num::Wrapping,
    ops::{Bound, RangeBounds},
};

/// Check a set of peers the actual redundancy across all peers.
/// This can tell if there is bad distribution.
/// Note this function is only used for verification in tests at this time.
pub fn check_redundancy(peers: Vec<DhtArc>) -> u32 {
    use std::collections::HashSet;
    #[derive(Clone, Copy, Debug)]
    enum Side {
        Left,
        Right,
    }
    #[derive(Clone, Copy, Debug)]
    struct Arm {
        id: usize,
        side: Side,
        pos: u32,
    }
    let left = |arc: &DhtArc| match arc.range().start_bound() {
        Bound::Included(arm) => *arm,
        _ => unreachable!(),
    };
    let right = |arc: &DhtArc| match arc.range().end_bound() {
        Bound::Included(arm) => *arm,
        _ => unreachable!(),
    };

    // Turn each arc into a side with a unique id that is
    // shared by both sides.
    let mut id = 0;
    let mut sides = |arc: &DhtArc| {
        let i = id;
        let l = Arm {
            id: i,
            side: Side::Left,
            pos: left(arc),
        };
        let r = Arm {
            id: i,
            side: Side::Right,
            pos: right(arc),
        };
        id += 1;
        vec![l, r]
    };

    // Record and remove any full redundancy arcs as we only
    // need to measure that stack of partial coverage.
    let mut full_r = 0;
    let peers: Vec<_> = peers
        .into_iter()
        .filter(|a| {
            if (a.coverage() - 1.0).abs() < ERROR_MARGIN {
                full_r += 1;
                false
            } else {
                // Also remove any bounds that don't include some coverage.
                matches!(a.range().start_bound(), Bound::Included(_))
            }
        })
        .collect();

    // If we are empty at this stage then return any full coverage.
    if peers.is_empty() {
        return full_r;
    }

    // Turn the rest of the partial arcs into their sides.
    let mut peers = peers
        .into_iter()
        .flat_map(|p| sides(&p).into_iter())
        .collect::<Vec<_>>();

    // Sort the sides by their positions.
    peers.sort_unstable_by_key(|p| p.pos);

    // Fold over the sides tracking the stack of arcs that have been entered but not exited.
    // The minimal stack height at any given point is the minimum redundancy on the network.
    let stack_fold = |(mut stack, r, mut started, mut last_remove): (
        HashSet<usize>,
        usize,
        bool,
        Option<u32>,
    ),
                      arm: &Arm| {
        let mut connected = false;
        let mut this_remove = None;
        match arm.side {
            Side::Left => {
                // We must have added at least one arc otherwise
                // our minimum stack height will always be one.
                started = true;

                // Check if we are inserting an arc just one location
                // past a remove because that actually counts as covered.
                connected = last_remove
                    .as_ref()
                    .map(|l| (Wrapping(arm.pos) - Wrapping(*l)).0 <= 1)
                    .unwrap_or(false);

                // Add this id to the stack.
                stack.insert(arm.id);
            }
            Side::Right => {
                // Set the last removed.
                this_remove = Some(arm.pos);

                // Remove this id.
                stack.remove(&arm.id);
            }
        }
        // Get the current stack height.
        let len = stack.len();

        // If we have started and the length has dropped then set a
        // lower redundancy.
        let mut r = if len < r && started {
            // Only record removes that actually change the r level.
            last_remove = this_remove;
            len
        } else {
            r
        };

        // If this was actually a connected insert then undo the last remove.
        if connected {
            r += 1
        }
        (stack, r, started, last_remove)
    };

    // Run through the list once to find the stack remaining at the end of the run.
    let (stack, _, started, last_removed) = peers
        .iter()
        .fold((HashSet::new(), usize::MAX, false, None), stack_fold);

    // Now use that as the starting stack for the "real" run.
    let (_, r, _, _) = peers
        .iter()
        .fold((stack, usize::MAX, started, last_removed), stack_fold);

    // Our redundancy is whatever partial + any full redundancy
    r as u32 + full_r
}