8513258596

Committed 01 Apr 2024 08:21PM UTC coverage: 84.047% (-0.06%) from 84.105%

Build # 8513258596

Build Type

push

github

Committed by

web-flow

Commit Message

Update fuzz tests and have run them in CI (#75)

Run Details

5769 of 6864 relevant lines covered (84.05%)

6757922.29 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.2

/src/sort.rs

// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.

use crate::vector::FocusMut;
use rand_core::{RngCore, SeedableRng};
use std::cmp::Ordering;
use std::mem;

fn gen_range<R: RngCore>(rng: &mut R, min: usize, max: usize) -> usize {
    let range = max - min;
    min + (rng.next_u64() as usize % range)
}

// Ported from the Java version at:
//    http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf
// There are a couple of modifications made here to make it more performant on the tree structure of
// the Vector. Instead of moving of handling equal and nonequal items in a single pass we make two
// additional passes to find the exact partition places. This allows us to split the focus into
// three correctly sized parts for less than, equal to and greater than items. As a bonus this
// doesn't need to reorder the equal items to the center of the vector.
fn do_quicksort<A, F, R>(vector: FocusMut<'_, A>, cmp: &F, rng: &mut R)
where
    A: Clone,
    F: Fn(&A, &A) -> Ordering,
    R: RngCore,
{
    if vector.len() <= 1 {
        return;
    }

    // We know there are at least 2 elements here
    let pivot_index = gen_range(rng, 0, vector.len());
    let (mut first, mut rest) = vector.split_at(1);

    if pivot_index > 0 {
        mem::swap(rest.index_mut(pivot_index - 1), first.index_mut(0));
    }
    // Pivot is now always in the first slice
    let pivot_item = first.index(0);

    // Find the exact place to put the pivot or pivot-equal items
    let mut less_count = 0;
    let mut equal_count = 0;

    for index in 0..rest.len() {
        let item = rest.index(index);
        let comp = cmp(item, pivot_item);
        match comp {
            Ordering::Less => less_count += 1,
            Ordering::Equal => equal_count += 1,
            Ordering::Greater => {}
        }
    }

    // If by accident we picked the minimum element as a pivot, we just call sort again with the
    // rest of the vector.
    if less_count == 0 {
        do_quicksort(rest, cmp, rng);
        return;
    }

    // We know here that there is at least one item before the pivot, so we move the minimum to the
    // beginning part of the vector. First, however we swap the pivot to the start of the equal
    // zone.
    less_count -= 1;
    equal_count += 1;
    let first_item = first.index_mut(0);
    mem::swap(first_item, rest.index_mut(less_count));
    for index in 0..rest.len() {
        if index == less_count {
            // This is the position we swapped the pivot to. We can't move it from its position, and
            // we know its not the minimum.
            continue;
        }
        let rest_item = rest.index_mut(index);
        if cmp(rest_item, first_item) == Ordering::Less {
            mem::swap(first_item, rest_item);
        }
    }

    // Split the vector up into less_than, equal to and greater than parts.
    let (remaining, mut greater_focus) = rest.split_at(less_count + equal_count);
    let (mut less_focus, mut equal_focus) = remaining.split_at(less_count);

    let mut less_position = 0;
    let mut equal_position = 0;
    let mut greater_position = 0;

    while less_position != less_focus.len() || greater_position != greater_focus.len() {
        // At start of this loop, equal_position always points to an equal item
        let mut equal_swap_side = None;
        let equal_item = equal_focus.index(equal_position);

        // Advance the less_position until we find an out of place item
        while less_position != less_focus.len() {
            let less_item = less_focus.index(less_position);
            match cmp(less_item, equal_item) {
                Ordering::Equal => {
                    equal_swap_side = Some(Ordering::Less);
                    break;
                }
                Ordering::Greater => {
                    break;
                }
                _ => {}
            }
            less_position += 1;
        }

        // Advance the greater until we find an out of place item
        while greater_position != greater_focus.len() {
            let greater_item = greater_focus.index(greater_position);
            match cmp(greater_item, equal_item) {
                Ordering::Less => break,
                Ordering::Equal => {
                    equal_swap_side = Some(Ordering::Greater);
                    break;
                }
                _ => {}
            }
            greater_position += 1;
        }

        if let Some(swap_side) = equal_swap_side {
            // One of the sides is equal to the pivot, advance the pivot
            let item = if swap_side == Ordering::Less {
                less_focus.index_mut(less_position)
            } else {
                greater_focus.index_mut(greater_position)
            };

            // We are guaranteed not to hit the end of the equal focus
            while cmp(item, equal_focus.index(equal_position)) == Ordering::Equal {
                equal_position += 1;
            }

            // Swap the equal position and the desired side, it's important to note that only the
            // equals focus is guaranteed to have made progress so we don't advance the side's index
            mem::swap(item, equal_focus.index_mut(equal_position));
        } else if less_position != less_focus.len() && greater_position != greater_focus.len() {
            // Both sides are out of place and not equal to the pivot, this can only happen if there
            // is a greater item in the lesser zone and a lesser item in the greater zone. The
            // solution is to swap both sides and advance both side's indices.
            debug_assert_ne!(
                cmp(
                    less_focus.index(less_position),
                    equal_focus.index(equal_position)
                ),
                Ordering::Equal
            );
            debug_assert_ne!(
                cmp(
                    greater_focus.index(greater_position),
                    equal_focus.index(equal_position)
                ),
                Ordering::Equal
            );
            mem::swap(
                less_focus.index_mut(less_position),
                greater_focus.index_mut(greater_position),
            );
            less_position += 1;
            greater_position += 1;
        }
    }

    // Now we have partitioned both sides correctly, we just have to recurse now
    do_quicksort(less_focus, cmp, rng);
    if !greater_focus.is_empty() {
        do_quicksort(greater_focus, cmp, rng);
    }
}

pub(crate) fn quicksort<A, F>(vector: FocusMut<'_, A>, cmp: &F)
where
    A: Clone,
    F: Fn(&A, &A) -> Ordering,
{
    let mut rng = rand_xoshiro::Xoshiro256Plus::seed_from_u64(0);
    do_quicksort(vector, cmp, &mut rng);
}

#[cfg(test)]
mod test {
    use super::*;
    use crate::test::is_sorted;
    use crate::vector::proptest::vector;
    use ::proptest::num::i32;
    use ::proptest::proptest;

    proptest! {
        #[test]
        fn test_quicksort(ref input in vector(i32::ANY, 0..10000)) {
            let mut vec = input.clone();
            let len = vec.len();
            if len > 1 {
                quicksort(vec.focus_mut(), &Ord::cmp);
            }
            assert!(is_sorted(vec));
        }
    }
}

1	// This Source Code Form is subject to the terms of the Mozilla Public
2	// License, v. 2.0. If a copy of the MPL was not distributed with this
3	// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4
5	use crate::vector::FocusMut;
6	use rand_core::{RngCore, SeedableRng};
7	use std::cmp::Ordering;
8	use std::mem;
9
10	fn gen_range<R: RngCore>(rng: &mut R, min: usize, max: usize) -> usize {	1,250,648✔
11	let range = max - min;	1,250,648✔
12	min + (rng.next_u64() as usize % range)	1,250,648✔
13	}	1,250,648✔
14
15	// Ported from the Java version at:
16	// http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf
17	// There are a couple of modifications made here to make it more performant on the tree structure of
18	// the Vector. Instead of moving of handling equal and nonequal items in a single pass we make two
19	// additional passes to find the exact partition places. This allows us to split the focus into
20	// three correctly sized parts for less than, equal to and greater than items. As a bonus this
21	// doesn't need to reorder the equal items to the center of the vector.
22	fn do_quicksort<A, F, R>(vector: FocusMut<'_, A>, cmp: &F, rng: &mut R)	1,952,607✔
23	where
24	A: Clone,
25	F: Fn(&A, &A) -> Ordering,
26	R: RngCore,
27	{
28	if vector.len() <= 1 {	1,952,607✔
29	return;
30	}
31
32	// We know there are at least 2 elements here
33	let pivot_index = gen_range(rng, 0, vector.len());	1,250,648✔
34	let (mut first, mut rest) = vector.split_at(1);	1,250,648✔
35
36	if pivot_index > 0 {	1,250,648✔
37	mem::swap(rest.index_mut(pivot_index - 1), first.index_mut(0));	979,735✔
38	}
39	// Pivot is now always in the first slice
40	let pivot_item = first.index(0);	1,250,648✔
41
42	// Find the exact place to put the pivot or pivot-equal items
43	let mut less_count = 0;	1,250,648✔
44	let mut equal_count = 0;	1,250,648✔
45
46	for index in 0..rest.len() {	37,886,402✔
47	let item = rest.index(index);	36,635,754✔
48	let comp = cmp(item, pivot_item);	36,635,754✔
49	match comp {	36,635,754✔
50	Ordering::Less => less_count += 1,	18,375,655✔
51	Ordering::Equal => equal_count += 1,	3✔
52	Ordering::Greater => {}
53	}
54	}
55
56	// If by accident we picked the minimum element as a pivot, we just call sort again with the
57	// rest of the vector.
58	if less_count == 0 {	1,250,648✔
59	do_quicksort(rest, cmp, rng);	274,549✔
60	return;
61	}
62
63	// We know here that there is at least one item before the pivot, so we move the minimum to the
64	// beginning part of the vector. First, however we swap the pivot to the start of the equal
65	// zone.
66	less_count -= 1;	976,099✔
67	equal_count += 1;	976,099✔
68	let first_item = first.index_mut(0);	976,099✔
69	mem::swap(first_item, rest.index_mut(less_count));	976,099✔
70	for index in 0..rest.len() {	36,631,906✔
71	if index == less_count {	35,655,807✔
72	// This is the position we swapped the pivot to. We can't move it from its position, and
73	// we know its not the minimum.
74	continue;
75	}
76	let rest_item = rest.index_mut(index);	34,679,708✔
77	if cmp(rest_item, first_item) == Ordering::Less {	34,679,708✔
78	mem::swap(first_item, rest_item);	1,892,850✔
79	}
80	}
81
82	// Split the vector up into less_than, equal to and greater than parts.
83	let (remaining, mut greater_focus) = rest.split_at(less_count + equal_count);	976,099✔
84	let (mut less_focus, mut equal_focus) = remaining.split_at(less_count);	976,099✔
85
86	let mut less_position = 0;	976,099✔
87	let mut equal_position = 0;	976,099✔
88	let mut greater_position = 0;	976,099✔
89
90	while less_position != less_focus.len() \|\| greater_position != greater_focus.len() {	7,456,117✔
91	// At start of this loop, equal_position always points to an equal item
92	let mut equal_swap_side = None;	6,480,018✔
93	let equal_item = equal_focus.index(equal_position);	6,480,018✔
94
95	// Advance the less_position until we find an out of place item
96	while less_position != less_focus.len() {	18,107,226✔
97	let less_item = less_focus.index(less_position);	17,399,556✔
98	match cmp(less_item, equal_item) {	17,399,556✔
99	Ordering::Equal => {
100	equal_swap_side = Some(Ordering::Less);	×
101	break;	×
102	}
103	Ordering::Greater => {
104	break;
105	}
106	_ => {}
107	}
108	less_position += 1;	11,627,208✔
109	}
110
111	// Advance the greater until we find an out of place item
112	while greater_position != greater_focus.len() {	17,987,820✔
113	let greater_item = greater_focus.index(greater_position);	17,280,152✔
114	match cmp(greater_item, equal_item) {	17,280,152✔
115	Ordering::Less => break,
116	Ordering::Equal => {
117	equal_swap_side = Some(Ordering::Greater);	2✔
118	break;	2✔
119	}
120	_ => {}
121	}
122	greater_position += 1;	11,507,802✔
123	}
124
125	if let Some(swap_side) = equal_swap_side {	6,480,018✔
126	// One of the sides is equal to the pivot, advance the pivot
127	let item = if swap_side == Ordering::Less {	2✔
128	less_focus.index_mut(less_position)	×
129	} else {
130	greater_focus.index_mut(greater_position)	2✔
131	};
132
133	// We are guaranteed not to hit the end of the equal focus
134	while cmp(item, equal_focus.index(equal_position)) == Ordering::Equal {	4✔
135	equal_position += 1;	2✔
136	}
137
138	// Swap the equal position and the desired side, it's important to note that only the
139	// equals focus is guaranteed to have made progress so we don't advance the side's index
140	mem::swap(item, equal_focus.index_mut(equal_position));	2✔
141	} else if less_position != less_focus.len() && greater_position != greater_focus.len() {	12,252,364✔
142	// Both sides are out of place and not equal to the pivot, this can only happen if there
143	// is a greater item in the lesser zone and a lesser item in the greater zone. The
144	// solution is to swap both sides and advance both side's indices.
145	debug_assert_ne!(	5,772,348✔
146	cmp(	5,772,348✔
147	less_focus.index(less_position),	5,772,348✔
148	equal_focus.index(equal_position)	5,772,348✔
149	),
150	Ordering::Equal
151	);
152	debug_assert_ne!(	5,772,348✔
153	cmp(	5,772,348✔
154	greater_focus.index(greater_position),	5,772,348✔
155	equal_focus.index(equal_position)	5,772,348✔
156	),
157	Ordering::Equal
158	);
159	mem::swap(	5,772,348✔
160	less_focus.index_mut(less_position),	5,772,348✔
161	greater_focus.index_mut(greater_position),	5,772,348✔
162	);
163	less_position += 1;	5,772,348✔
164	greater_position += 1;	5,772,348✔
165	}
166	}
167
168	// Now we have partitioned both sides correctly, we just have to recurse now
169	do_quicksort(less_focus, cmp, rng);	976,099✔
170	if !greater_focus.is_empty() {	976,099✔
171	do_quicksort(greater_focus, cmp, rng);	701,445✔
172	}
173	}	1,952,607✔
174
175	pub(crate) fn quicksort<A, F>(vector: FocusMut<'_, A>, cmp: &F)	514✔
176	where
177	A: Clone,
178	F: Fn(&A, &A) -> Ordering,
179	{
180	let mut rng = rand_xoshiro::Xoshiro256Plus::seed_from_u64(0);	514✔
181	do_quicksort(vector, cmp, &mut rng);	514✔
182	}	514✔
183
184	#[cfg(test)]
185	mod test {
186	use super::*;
187	use crate::test::is_sorted;
188	use crate::vector::proptest::vector;
189	use ::proptest::num::i32;
190	use ::proptest::proptest;
191
192	proptest! {
193	#[test]
194	fn test_quicksort(ref input in vector(i32::ANY, 0..10000)) {
195	let mut vec = input.clone();
196	let len = vec.len();
197	if len > 1 {
198	quicksort(vec.focus_mut(), &Ord::cmp);
199	}
200	assert!(is_sorted(vec));
201	}
202	}
203	}

jneem / imbl / 8513258596

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous