rsalgo 0.0.1-init.1

A collection of some algorithms and data-structures.
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

use super::search;

/// Get the number of inversion pairs.
///
/// # Examples
///
/// ```
/// assert_eq!(9, rsalgo::base::inversion_pairs_count(&[1, 3, 5, 3, 2, 4, 7, 9, 6, 6]));
/// ```
pub fn inversion_pairs_count<T: PartialEq + Ord + Clone>(slice: &[T]) -> usize {
    let mut ans = 0;
    let mut temp = vec![0; slice.len()];
    merge_sort(
        search::discretization(slice).as_mut_slice(),
        0,
        slice.len(),
        &mut temp,
        &mut ans,
    );
    ans
}

fn merge_sort(a: &mut [usize], l: usize, r: usize, temp: &mut [usize], pair: &mut usize) {
    if l + 1 >= r {
        return;
    }
    let mid = (l + r) / 2;
    merge_sort(a, l, mid, temp, pair);
    merge_sort(a, mid, r, temp, pair);
    let (mut ll, mut rr, mut cur) = (l, mid, 0);

    while ll < mid && rr < r {
        if a[ll] <= a[rr] {
            temp[cur] = a[ll];
            ll += 1;
        } else {
            *pair += mid - ll;
            temp[cur] = a[rr];
            rr += 1;
        }
        cur += 1;
    }

    while ll < mid {
        temp[cur] = a[ll];
        cur += 1;
        ll += 1;
    }

    while rr < r {
        temp[cur] = a[rr];
        cur += 1;
        rr += 1;
    }

    for i in l..r {
        a[i] = temp[i - l];
    }
}

#[cfg(test)]
mod tests {
    #[test]
    fn inversion_pairs_count() {
        assert_eq!(
            9,
            super::inversion_pairs_count(&[1, 3, 5, 3, 2, 4, 7, 9, 6, 6])
        );
    }
}