braid-core 0.1.4

Unified Braid Protocol implementation in Rust, including Braid-HTTP, Antimatter CRDT, and BraidFS.
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

use crate::vendor::rle::MergableSpan;

/// This is an iterator composer which wraps any iterator over a SplitableSpan to become an
/// iterator over those same items in run-length order.

#[derive(Debug, Clone)]
pub struct MergeIter<I: Iterator, const FWD: bool = true> {
    next: Option<I::Item>,
    iter: I
}

pub fn merge_items<I: Iterator>(iter: I) -> MergeIter<I, true> {
    MergeIter::new(iter)
}
pub fn merge_items_rev<I: Iterator>(iter: I) -> MergeIter<I, false> {
    MergeIter::new(iter)
}

impl<I: Iterator, const FWD: bool> MergeIter<I, FWD> {
    pub fn new(iter: I) -> Self {
        Self {
            next: None,
            iter
        }
    }

    pub fn into_inner(self) -> I {
        self.iter
    }
}

impl<I, X, const FWD: bool> Iterator for MergeIter<I, FWD>
where
    I: Iterator<Item = X>,
    X: MergableSpan
{
    type Item = X;

    fn next(&mut self) -> Option<Self::Item> {
        let mut this_val = match self.next.take() {
            Some(val) => val,
            None => {
                self.iter.next()?
            }
        };

        for val in &mut self.iter {
            if FWD && this_val.can_append(&val) {
                this_val.append(val);
            } else if !FWD && val.can_append(&this_val) {
                this_val.prepend(val);
            } else {
                self.next = Some(val);
                break;
            }
        }

        Some(this_val)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let (lower, upper) = self.iter.size_hint();
        (lower.min(1), upper)
    }
}

pub trait MergeableIterator<X: MergableSpan>: Iterator<Item = X> where Self: Sized {
    fn merge_spans(self) -> MergeIter<Self, true>;
    fn merge_spans_rev(self) -> MergeIter<Self, false>;
}

impl<X, I> MergeableIterator<X> for I
where I: Iterator<Item=X>, X: MergableSpan, Self: Sized
{
    fn merge_spans(self) -> MergeIter<Self> {
        MergeIter::new(self)
    }
    fn merge_spans_rev(self) -> MergeIter<Self, false> {
        MergeIter::new(self)
    }
}

#[cfg(test)]
mod test {
    use std::ops::Range;
    use super::merge_items;
    use crate::vendor::rle::{merge_items_rev, RleRun};

    #[test]
    fn test_merge_iter() {
        let empty: Vec<RleRun<u32>> = vec![];
        assert_eq!(merge_items(empty.into_iter()).collect::<Vec<_>>(), vec![]);

        let one = vec![RleRun { val: 5, len: 1 }];
        assert_eq!(merge_items(one.into_iter()).collect::<Vec<_>>(), vec![RleRun { val: 5, len: 1 }]);

        let two_split = vec![2u32..3, 5..10];
        assert_eq!(merge_items(two_split.iter().cloned()).collect::<Vec<_>>(), two_split);

        let two_merged = vec![2u32..5, 5..10];
        assert_eq!(merge_items(two_merged.iter().cloned()).collect::<Vec<_>>(), vec![2..10]);
    }

    #[test]
    fn test_merge_iter_rev() {
        // TODO: This is a bit of a crap test because it doesn't actually
        let empty: Vec<Range<u32>> = vec![];
        assert_eq!(merge_items_rev(empty.into_iter()).collect::<Vec<_>>(), vec![]);

        let one = vec![5..6];
        assert_eq!(merge_items_rev(one.into_iter()).collect::<Vec<_>>(), vec![5u32..6]);

        let two_split = vec![5u32..10, 2..3];
        assert_eq!(merge_items_rev(two_split.iter().cloned()).collect::<Vec<_>>(), two_split);

        let two_merged = vec![5u32..10, 2..5];
        assert_eq!(merge_items_rev(two_merged.iter().cloned()).collect::<Vec<_>>(), vec![2..10]);
    }
}