codd 0.1.0

codd is a minimal in-memory database with relational algebraic expressions as queries.
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

/// Moves an ordered `slice` forward until `cmp` is true on the elements of `slice`.
///
/// **Note**: `gallop` is directly borrowed from [`datafrog`].
///
/// [`datafrog`]: https://github.com/rust-lang/datafrog
#[inline(always)]
pub(crate) fn gallop<T>(mut slice: &[T], mut cmp: impl FnMut(&T) -> bool) -> &[T] {
    if !slice.is_empty() && cmp(&slice[0]) {
        let mut step = 1;
        while step < slice.len() && cmp(&slice[step]) {
            slice = &slice[step..];
            step <<= 1;
        }

        step >>= 1;
        while step > 0 {
            if step < slice.len() && cmp(&slice[step]) {
                slice = &slice[step..];
            }
            step >>= 1;
        }

        slice = &slice[1..];
    }
    slice
}

/// Applies `result` on elements of `slice`.
#[inline(always)]
pub(crate) fn project_helper<T>(slice: &[T], mut result: impl FnMut(&T)) {
    let slice = &slice[..];
    for tuple in slice {
        result(tuple);
    }
}

/// Applies `result` on every pair of `left` and `right` slices.
#[inline(always)]
pub(crate) fn product_helper<L, R>(left: &[L], right: &[R], mut result: impl FnMut(&L, &R)) {
    let left = &left[..];
    let right = &right[..];

    for l in left {
        for r in right {
            result(&l, &r);
        }
    }
}

/// For two slices `left` and `right` that are sorted by the first element of their tuples,
/// applies `result` on those pairs of `left` and `right` that agree on their first
/// element as the key.
///
/// **Note**: `join_helper` is directly borrowed from [`datafrog`].
///
/// [`datafrog`]: https://github.com/rust-lang/datafrog
#[inline(always)]
pub(crate) fn join_helper<Key: Ord, L, R>(
    left: &[(Key, L)],
    right: &[(Key, R)],
    mut result: impl FnMut(&Key, &L, &R),
) {
    let mut slice1 = &left[..];
    let mut slice2 = &right[..];

    while !slice1.is_empty() && !slice2.is_empty() {
        use std::cmp::Ordering;

        match slice1[0].0.cmp(&slice2[0].0) {
            Ordering::Less => slice1 = gallop(slice1, |x| x.0 < slice2[0].0),
            Ordering::Equal => {
                let count1 = slice1.iter().take_while(|x| x.0 == slice1[0].0).count();
                let count2 = slice2.iter().take_while(|x| x.0 == slice2[0].0).count();

                for index1 in 0..count1 {
                    for item in slice2.iter().take(count2) {
                        result(&slice1[0].0, &slice1[index1].1, &item.1);
                    }
                }

                slice1 = &slice1[count1..];
                slice2 = &slice2[count2..];
            }
            Ordering::Greater => slice2 = gallop(slice2, |x| x.0 < slice1[0].0),
        }
    }
}

/// For two sorted slices `left` and `right`, applies `result` on those elements of `left` and `right`
/// that are equal.
#[inline(always)]
pub(crate) fn intersect_helper<T: Ord>(left: &[T], right: &[T], mut result: impl FnMut(&T)) {
    let mut left = &left[..];
    let mut right = &right[..];

    while !left.is_empty() && !right.is_empty() {
        use std::cmp::Ordering;

        match left[0].cmp(&right[0]) {
            Ordering::Less => left = gallop(left, |x| x < &right[0]),
            Ordering::Equal => {
                result(&left[0]);
                left = &left[1..];
                right = &right[1..];
            }
            Ordering::Greater => right = gallop(right, |x| x < &left[0]),
        }
    }
}

/// For two sorted slices `left` and `right`, applies `result` on those elements of `left` that appear
/// in none of the slices of `right`.
#[inline(always)]
pub(crate) fn diff_helper<T: Ord>(left: &[T], right: &[&[T]], mut result: impl FnMut(&T)) {
    let left = &left[..];
    let mut right = right.iter().map(|sl| &sl[..]).collect::<Vec<&[T]>>();

    for tuple in left {
        let mut to_add = true;
        for mut to_find in &mut right {
            use std::cmp::Ordering;

            if !to_find.is_empty() {
                match tuple.cmp(&to_find[0]) {
                    Ordering::Less => {}
                    Ordering::Equal => {
                        to_add = false;
                    }
                    Ordering::Greater => {
                        let mut temp = gallop(to_find, |x| x < tuple);
                        to_find = &mut temp;
                        if !to_find.is_empty() && tuple == &to_find[0] {
                            to_add = false;
                        }
                    }
                }
            }
        }

        if to_add {
            result(tuple);
        }
    }
}