(index<- ) ./libextra/sort.rs
1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 //! Sorting methods
12
13
14 use std::cmp::{Eq, Ord};
15 use std::util::swap;
16 use std::vec;
17
18 type Le<'self, T> = &'self fn(v1: &T, v2: &T) -> bool;
19
20 /**
21 * Merge sort. Returns a new vector containing the sorted list.
22 *
23 * Has worst case O(n log n) performance, best case O(n), but
24 * is not space efficient. This is a stable sort.
25 */
26 pub fn merge_sort<T:Clone>(v: &[T], le: Le<T>) -> ~[T] {
27 type Slice = (uint, uint);
28
29 return merge_sort_(v, (0u, v.len()), le);
30
31 fn merge_sort_<T:Clone>(v: &[T], slice: Slice, le: Le<T>) -> ~[T] {
32 let begin = slice.first();
33 let end = slice.second();
34
35 let v_len = end - begin;
36 if v_len == 0 { return ~[]; }
37 if v_len == 1 { return ~[v[begin].clone()]; }
38
39 let mid = v_len / 2 + begin;
40 let a = (begin, mid);
41 let b = (mid, end);
42 return merge(|x,y| le(x,y), merge_sort_(v, a, |x,y| le(x,y)),
43 merge_sort_(v, b, |x,y| le(x,y)));
44 }
45
46 fn merge<T:Clone>(le: Le<T>, a: &[T], b: &[T]) -> ~[T] {
47 let mut rs = vec::with_capacity(a.len() + b.len());
48 let a_len = a.len();
49 let mut a_ix = 0;
50 let b_len = b.len();
51 let mut b_ix = 0;
52 while a_ix < a_len && b_ix < b_len {
53 if le(&a[a_ix], &b[b_ix]) {
54 rs.push(a[a_ix].clone());
55 a_ix += 1;
56 } else {
57 rs.push(b[b_ix].clone());
58 b_ix += 1;
59 }
60 }
61 rs.push_all(a.slice(a_ix, a_len));
62 rs.push_all(b.slice(b_ix, b_len));
63 rs
64 }
65 }
66
67 fn part<T>(arr: &mut [T], left: uint,
68 right: uint, pivot: uint, compare_func: Le<T>) -> uint {
69 arr.swap(pivot, right);
70 let mut storage_index: uint = left;
71 let mut i: uint = left;
72 while i < right {
73 if compare_func(&arr[i], &arr[right]) {
74 arr.swap(i, storage_index);
75 storage_index += 1;
76 }
77 i += 1;
78 }
79 arr.swap(storage_index, right);
80 return storage_index;
81 }
82
83 fn qsort<T>(arr: &mut [T], left: uint,
84 right: uint, compare_func: Le<T>) {
85 if right > left {
86 let pivot = (left + right) / 2u;
87 let new_pivot = part::<T>(arr, left, right, pivot, |x,y| compare_func(x,y));
88 if new_pivot != 0u {
89 // Need to do this check before recursing due to overflow
90 qsort::<T>(arr, left, new_pivot - 1u, |x,y| compare_func(x,y));
91 }
92 qsort::<T>(arr, new_pivot + 1u, right, compare_func);
93 }
94 }
95
96 /**
97 * Quicksort. Sorts a mut vector in place.
98 *
99 * Has worst case O(n^2) performance, average case O(n log n).
100 * This is an unstable sort.
101 */
102 pub fn quick_sort<T>(arr: &mut [T], compare_func: Le<T>) {
103 let len = arr.len();
104 if len == 0u { return; }
105 qsort::<T>(arr, 0u, len - 1u, compare_func);
106 }
107
108 fn qsort3<T:Clone + Ord + Eq>(arr: &mut [T], left: int, right: int) {
109 if right <= left { return; }
110 let v: T = arr[right].clone();
111 let mut i: int = left - 1;
112 let mut j: int = right;
113 let mut p: int = i;
114 let mut q: int = j;
115 loop {
116 i += 1;
117 while arr[i] < v { i += 1; }
118 j -= 1;
119 while v < arr[j] {
120 if j == left { break; }
121 j -= 1;
122 }
123 if i >= j { break; }
124 arr.swap(i as uint, j as uint);
125 if arr[i] == v {
126 p += 1;
127 arr.swap(p as uint, i as uint);
128 }
129 if v == arr[j] {
130 q -= 1;
131 arr.swap(j as uint, q as uint);
132 }
133 }
134 arr.swap(i as uint, right as uint);
135 j = i - 1;
136 i += 1;
137 let mut k: int = left;
138 while k < p {
139 arr.swap(k as uint, j as uint);
140 k += 1;
141 j -= 1;
142 if k == arr.len() as int { break; }
143 }
144 k = right - 1;
145 while k > q {
146 arr.swap(i as uint, k as uint);
147 k -= 1;
148 i += 1;
149 if k == 0 { break; }
150 }
151 qsort3::<T>(arr, left, j);
152 qsort3::<T>(arr, i, right);
153 }
154
155 /**
156 * Fancy quicksort. Sorts a mut vector in place.
157 *
158 * Based on algorithm presented by ~[Sedgewick and Bentley]
159 * (http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf).
160 * According to these slides this is the algorithm of choice for
161 * 'randomly ordered keys, abstract compare' & 'small number of key values'.
162 *
163 * This is an unstable sort.
164 */
165 pub fn quick_sort3<T:Clone + Ord + Eq>(arr: &mut [T]) {
166 if arr.len() <= 1 { return; }
167 let len = arr.len(); // FIXME(#5074) nested calls
168 qsort3(arr, 0, (len - 1) as int);
169 }
170
171 #[allow(missing_doc)]
172 pub trait Sort {
173 fn qsort(self);
174 }
175
176 impl<'self, T:Clone + Ord + Eq> Sort for &'self mut [T] {
177 fn qsort(self) { quick_sort3(self); }
178 }
179
180 static MIN_MERGE: uint = 64;
181 static MIN_GALLOP: uint = 7;
182 static INITIAL_TMP_STORAGE: uint = 128;
183
184 #[allow(missing_doc)]
185 pub fn tim_sort<T:Clone + Ord>(array: &mut [T]) {
186 let size = array.len();
187 if size < 2 {
188 return;
189 }
190
191 if size < MIN_MERGE {
192 let init_run_len = count_run_ascending(array);
193 binarysort(array, init_run_len);
194 return;
195 }
196
197 let mut ms = MergeState();
198 let min_run = min_run_length(size);
199
200 let mut idx = 0;
201 let mut remaining = size;
202 loop {
203 let run_len: uint = {
204 // This scope contains the slice `arr` here:
205 let arr = array.mut_slice(idx, size);
206 let mut run_len: uint = count_run_ascending(arr);
207
208 if run_len < min_run {
209 let force = if remaining <= min_run {remaining} else {min_run};
210 let slice = arr.mut_slice(0, force);
211 binarysort(slice, run_len);
212 run_len = force;
213 }
214
215 run_len
216 };
217
218 ms.push_run(idx, run_len);
219 ms.merge_collapse(array);
220
221 idx += run_len;
222 remaining -= run_len;
223 if remaining == 0 { break; }
224 }
225
226 ms.merge_force_collapse(array);
227 }
228
229 fn binarysort<T:Clone + Ord>(array: &mut [T], start: uint) {
230 let size = array.len();
231 let mut start = start;
232 assert!(start <= size);
233
234 if start == 0 { start += 1; }
235
236 while start < size {
237 let pivot = array[start].clone();
238 let mut left = 0;
239 let mut right = start;
240 assert!(left <= right);
241
242 while left < right {
243 let mid = (left + right) >> 1;
244 if pivot < array[mid] {
245 right = mid;
246 } else {
247 left = mid+1;
248 }
249 }
250 assert_eq!(left, right);
251 let n = start-left;
252
253 shift_vec(array, left+1, left, n);
254 array[left] = pivot;
255 start += 1;
256 }
257 }
258
259 // Reverse the order of elements in a slice, in place
260 fn reverse_slice<T>(v: &mut [T], start: uint, end:uint) {
261 let mut i = start;
262 while i < end / 2 {
263 v.swap(i, end - i - 1);
264 i += 1;
265 }
266 }
267
268 fn min_run_length(n: uint) -> uint {
269 let mut n = n;
270 let mut r = 0; // becomes 1 if any 1 bits are shifted off
271
272 while n >= MIN_MERGE {
273 r |= n & 1;
274 n >>= 1;
275 }
276 return n + r;
277 }
278
279 fn count_run_ascending<T:Clone + Ord>(array: &mut [T]) -> uint {
280 let size = array.len();
281 assert!(size > 0);
282 if size == 1 { return 1; }
283
284 let mut run = 2;
285 if array[1] < array[0] {
286 while run < size && array[run] < array[run-1] {
287 run += 1;
288 }
289 reverse_slice(array, 0, run);
290 } else {
291 while run < size && array[run] >= array[run-1] {
292 run += 1;
293 }
294 }
295
296 return run;
297 }
298
299 fn gallop_left<T:Clone + Ord>(key: &T,
300 array: &[T],
301 hint: uint)
302 -> uint {
303 let size = array.len();
304 assert!(size != 0 && hint < size);
305
306 let mut last_ofs = 0;
307 let mut ofs = 1;
308
309 if *key > array[hint] {
310 // Gallop right until array[hint+last_ofs] < key <= array[hint+ofs]
311 let max_ofs = size - hint;
312 while ofs < max_ofs && *key > array[hint+ofs] {
313 last_ofs = ofs;
314 ofs = (ofs << 1) + 1;
315 if ofs < last_ofs { ofs = max_ofs; } // uint overflow guard
316 }
317 if ofs > max_ofs { ofs = max_ofs; }
318
319 last_ofs += hint;
320 ofs += hint;
321 } else {
322 let max_ofs = hint + 1;
323 while ofs < max_ofs && *key <= array[hint-ofs] {
324 last_ofs = ofs;
325 ofs = (ofs << 1) + 1;
326 if ofs < last_ofs { ofs = max_ofs; } // uint overflow guard
327 }
328
329 if ofs > max_ofs { ofs = max_ofs; }
330
331 let tmp = last_ofs;
332 last_ofs = hint - ofs;
333 ofs = hint - tmp;
334 }
335 assert!((last_ofs < ofs || last_ofs+1 < ofs+1) && ofs <= size);
336
337 last_ofs += 1;
338 while last_ofs < ofs {
339 let m = last_ofs + ((ofs - last_ofs) >> 1);
340 if *key > array[m] {
341 last_ofs = m+1;
342 } else {
343 ofs = m;
344 }
345 }
346 assert_eq!(last_ofs, ofs);
347 return ofs;
348 }
349
350 fn gallop_right<T:Clone + Ord>(key: &T,
351 array: &[T],
352 hint: uint)
353 -> uint {
354 let size = array.len();
355 assert!(size != 0 && hint < size);
356
357 let mut last_ofs = 0;
358 let mut ofs = 1;
359
360 if *key >= array[hint] {
361 // Gallop right until array[hint+last_ofs] <= key < array[hint+ofs]
362 let max_ofs = size - hint;
363 while ofs < max_ofs && *key >= array[hint+ofs] {
364 last_ofs = ofs;
365 ofs = (ofs << 1) + 1;
366 if ofs < last_ofs { ofs = max_ofs; }
367 }
368 if ofs > max_ofs { ofs = max_ofs; }
369
370 last_ofs += hint;
371 ofs += hint;
372 } else {
373 // Gallop left until array[hint-ofs] <= key < array[hint-last_ofs]
374 let max_ofs = hint + 1;
375 while ofs < max_ofs && *key < array[hint-ofs] {
376 last_ofs = ofs;
377 ofs = (ofs << 1) + 1;
378 if ofs < last_ofs { ofs = max_ofs; }
379 }
380 if ofs > max_ofs { ofs = max_ofs; }
381
382 let tmp = last_ofs;
383 last_ofs = hint - ofs;
384 ofs = hint - tmp;
385 }
386
387 assert!((last_ofs < ofs || last_ofs+1 < ofs+1) && ofs <= size);
388
389 last_ofs += 1;
390 while last_ofs < ofs {
391 let m = last_ofs + ((ofs - last_ofs) >> 1);
392
393 if *key >= array[m] {
394 last_ofs = m + 1;
395 } else {
396 ofs = m;
397 }
398 }
399 assert_eq!(last_ofs, ofs);
400 return ofs;
401 }
402
403 struct RunState {
404 base: uint,
405 len: uint,
406 }
407
408 struct MergeState<T> {
409 min_gallop: uint,
410 runs: ~[RunState],
411 }
412
413 // Fixme (#3853) Move into MergeState
414 fn MergeState<T>() -> MergeState<T> {
415 MergeState {
416 min_gallop: MIN_GALLOP,
417 runs: ~[],
418 }
419 }
420
421 impl<T:Clone + Ord> MergeState<T> {
422 fn push_run(&mut self, run_base: uint, run_len: uint) {
423 let tmp = RunState{base: run_base, len: run_len};
424 self.runs.push(tmp);
425 }
426
427 fn merge_at(&mut self, n: uint, array: &mut [T]) {
428 let size = self.runs.len();
429 assert!(size >= 2);
430 assert!(n == size-2 || n == size-3);
431
432 let mut b1 = self.runs[n].base;
433 let mut l1 = self.runs[n].len;
434 let b2 = self.runs[n+1].base;
435 let l2 = self.runs[n+1].len;
436
437 assert!(l1 > 0 && l2 > 0);
438 assert_eq!(b1 + l1, b2);
439
440 self.runs[n].len = l1 + l2;
441 if n == size-3 {
442 self.runs[n+1].base = self.runs[n+2].base;
443 self.runs[n+1].len = self.runs[n+2].len;
444 }
445
446 let k = { // constrain lifetime of slice below
447 let slice = array.slice(b1, b1+l1);
448 gallop_right(&array[b2], slice, 0)
449 };
450 b1 += k;
451 l1 -= k;
452 if l1 != 0 {
453 let l2 = { // constrain lifetime of slice below
454 let slice = array.slice(b2, b2+l2);
455 gallop_left(&array[b1+l1-1],slice,l2-1)
456 };
457 if l2 > 0 {
458 if l1 <= l2 {
459 self.merge_lo(array, b1, l1, b2, l2);
460 } else {
461 self.merge_hi(array, b1, l1, b2, l2);
462 }
463 }
464 }
465 self.runs.pop();
466 }
467
468 fn merge_lo(&mut self, array: &mut [T], base1: uint, len1: uint,
469 base2: uint, len2: uint) {
470 assert!(len1 != 0 && len2 != 0 && base1+len1 == base2);
471
472 let mut tmp = array.slice(base1, base1 + len1).to_owned();
473
474 let mut c1 = 0;
475 let mut c2 = base2;
476 let mut dest = base1;
477 let mut len1 = len1;
478 let mut len2 = len2;
479
480 array.swap(dest, c2);
481 dest += 1; c2 += 1; len2 -= 1;
482
483 if len2 == 0 {
484 copy_vec(array, dest, tmp.slice(0, len1));
485 return;
486 }
487 if len1 == 1 {
488 shift_vec(array, dest, c2, len2);
489 swap(&mut tmp[c1], &mut array[dest+len2]);
490 return;
491 }
492
493 let mut min_gallop = self.min_gallop;
494 loop {
495 let mut count1 = 0;
496 let mut count2 = 0;
497 let mut break_outer = false;
498
499 loop {
500 assert!(len1 > 1 && len2 != 0);
501 if array[c2] < tmp[c1] {
502 array.swap(dest, c2);
503 dest += 1; c2 += 1; len2 -= 1;
504 count2 += 1; count1 = 0;
505 if len2 == 0 {
506 break_outer = true;
507 }
508 } else {
509 swap(&mut array[dest], &mut tmp[c1]);
510 dest += 1; c1 += 1; len1 -= 1;
511 count1 += 1; count2 = 0;
512 if len1 == 1 {
513 break_outer = true;
514 }
515 }
516 if break_outer || ((count1 | count2) >= min_gallop) {
517 break;
518 }
519 }
520 if break_outer { break; }
521
522 // Start to gallop
523 loop {
524 assert!(len1 > 1 && len2 != 0);
525
526 count1 = {
527 let tmp_view = tmp.slice(c1, c1+len1);
528 gallop_right(&array[c2], tmp_view, 0)
529 };
530 if count1 != 0 {
531 copy_vec(array, dest, tmp.slice(c1, c1+count1));
532 dest += count1; c1 += count1; len1 -= count1;
533 if len1 <= 1 { break_outer = true; break; }
534 }
535 array.swap(dest, c2);
536 dest += 1; c2 += 1; len2 -= 1;
537 if len2 == 0 { break_outer = true; break; }
538
539 count2 = {
540 let tmp_view = array.slice(c2, c2+len2);
541 gallop_left(&tmp[c1], tmp_view, 0)
542 };
543 if count2 != 0 {
544 shift_vec(array, dest, c2, count2);
545 dest += count2; c2 += count2; len2 -= count2;
546 if len2 == 0 { break_outer = true; break; }
547 }
548 swap(&mut array[dest], &mut tmp[c1]);
549 dest += 1; c1 += 1; len1 -= 1;
550 if len1 == 1 { break_outer = true; break; }
551 min_gallop -= 1;
552 if !(count1 >= MIN_GALLOP || count2 >= MIN_GALLOP) {
553 break;
554 }
555 }
556 if break_outer { break; }
557 if min_gallop < 0 { min_gallop = 0; }
558 min_gallop += 2; // Penalize for leaving gallop
559 }
560 self.min_gallop = if min_gallop < 1 { 1 } else { min_gallop };
561
562 if len1 == 1 {
563 assert!(len2 > 0);
564 shift_vec(array, dest, c2, len2);
565 swap(&mut array[dest+len2], &mut tmp[c1]);
566 } else if len1 == 0 {
567 fail!("Comparison violates its contract!");
568 } else {
569 assert_eq!(len2, 0);
570 assert!(len1 > 1);
571 copy_vec(array, dest, tmp.slice(c1, c1+len1));
572 }
573 }
574
575 fn merge_hi(&mut self, array: &mut [T], base1: uint, len1: uint,
576 base2: uint, len2: uint) {
577 assert!(len1 != 1 && len2 != 0 && base1 + len1 == base2);
578
579 let mut tmp = array.slice(base2, base2 + len2).to_owned();
580
581 let mut c1 = base1 + len1 - 1;
582 let mut c2 = len2 - 1;
583 let mut dest = base2 + len2 - 1;
584 let mut len1 = len1;
585 let mut len2 = len2;
586
587 array.swap(dest, c1);
588 dest -= 1; c1 -= 1; len1 -= 1;
589
590 if len1 == 0 {
591 copy_vec(array, dest-(len2-1), tmp.slice(0, len2));
592 return;
593 }
594 if len2 == 1 {
595 dest -= len1;
596 c1 -= len1;
597 shift_vec(array, dest+1, c1+1, len1);
598 swap(&mut array[dest], &mut tmp[c2]);
599 return;
600 }
601
602 let mut min_gallop = self.min_gallop;
603 loop {
604 let mut count1 = 0;
605 let mut count2 = 0;
606 let mut break_outer = false;
607
608 loop {
609 assert!(len1 != 0 && len2 > 1);
610 if tmp[c2] < array[c1] {
611 array.swap(dest, c1);
612 dest -= 1; c1 -= 1; len1 -= 1;
613 count1 += 1; count2 = 0;
614 if len1 == 0 {
615 break_outer = true;
616 }
617 } else {
618 swap(&mut array[dest], &mut tmp[c2]);
619 dest -= 1; c2 -= 1; len2 -= 1;
620 count2 += 1; count1 = 0;
621 if len2 == 1 {
622 break_outer = true;
623 }
624 }
625 if break_outer || ((count1 | count2) >= min_gallop) {
626 break;
627 }
628 }
629 if break_outer { break; }
630
631 // Start to gallop
632 loop {
633 assert!(len2 > 1 && len1 != 0);
634
635 { // constrain scope of tmp_view:
636 let tmp_view = array.mut_slice(base1, base1+len1);
637 count1 = len1 - gallop_right(
638 &tmp[c2], tmp_view, len1-1);
639 }
640
641 if count1 != 0 {
642 dest -= count1; c1 -= count1; len1 -= count1;
643 shift_vec(array, dest+1, c1+1, count1);
644 if len1 == 0 { break_outer = true; break; }
645 }
646
647 swap(&mut array[dest], &mut tmp[c2]);
648 dest -= 1; c2 -= 1; len2 -= 1;
649 if len2 == 1 { break_outer = true; break; }
650
651 let count2;
652 { // constrain scope of tmp_view
653 let tmp_view = tmp.mut_slice(0, len2);
654 count2 = len2 - gallop_left(&array[c1],
655 tmp_view,
656 len2-1);
657 }
658
659 if count2 != 0 {
660 dest -= count2; c2 -= count2; len2 -= count2;
661 copy_vec(array, dest+1, tmp.slice(c2+1, c2+1+count2));
662 if len2 <= 1 { break_outer = true; break; }
663 }
664 array.swap(dest, c1);
665 dest -= 1; c1 -= 1; len1 -= 1;
666 if len1 == 0 { break_outer = true; break; }
667 min_gallop -= 1;
668 if !(count1 >= MIN_GALLOP || count2 >= MIN_GALLOP) {
669 break;
670 }
671 }
672
673 if break_outer { break; }
674 if min_gallop < 0 { min_gallop = 0; }
675 min_gallop += 2; // Penalize for leaving gallop
676 }
677 self.min_gallop = if min_gallop < 1 { 1 } else { min_gallop };
678
679 if len2 == 1 {
680 assert!(len1 > 0);
681 dest -= len1;
682 c1 -= len1;
683 shift_vec(array, dest+1, c1+1, len1);
684 swap(&mut array[dest], &mut tmp[c2]);
685 } else if len2 == 0 {
686 fail!("Comparison violates its contract!");
687 } else {
688 assert_eq!(len1, 0);
689 assert!(len2 != 0);
690 copy_vec(array, dest-(len2-1), tmp.slice(0, len2));
691 }
692 }
693
694 fn merge_collapse(&mut self, array: &mut [T]) {
695 while self.runs.len() > 1 {
696 let mut n = self.runs.len()-2;
697 if n > 0 &&
698 self.runs[n-1].len <= self.runs[n].len + self.runs[n+1].len
699 {
700 if self.runs[n-1].len < self.runs[n+1].len { n -= 1; }
701 } else if self.runs[n].len <= self.runs[n+1].len {
702 /* keep going */
703 } else {
704 break;
705 }
706 self.merge_at(n, array);
707 }
708 }
709
710 fn merge_force_collapse(&mut self, array: &mut [T]) {
711 while self.runs.len() > 1 {
712 let mut n = self.runs.len()-2;
713 if n > 0 {
714 if self.runs[n-1].len < self.runs[n+1].len {
715 n -= 1;
716 }
717 }
718 self.merge_at(n, array);
719 }
720 }
721 }
722
723 #[inline]
724 fn copy_vec<T:Clone>(dest: &mut [T],
725 s1: uint,
726 from: &[T]) {
727 assert!(s1+from.len() <= dest.len());
728
729 for (i, v) in from.iter().enumerate() {
730 dest[s1+i] = (*v).clone();
731 }
732 }
733
734 #[inline]
735 fn shift_vec<T:Clone>(dest: &mut [T], s1: uint, s2: uint, len: uint) {
736 assert!(s1+len <= dest.len());
737
738 let tmp = dest.slice(s2, s2+len).to_owned();
739 copy_vec(dest, s1, tmp);
740 }
741
742 #[cfg(test)]
743 mod test_qsort3 {
744 use sort::*;
745
746
747 fn check_sort(v1: &mut [int], v2: &mut [int]) {
748 let len = v1.len();
749 quick_sort3::<int>(v1);
750 let mut i = 0;
751 while i < len {
752 assert_eq!(v2[i], v1[i]);
753 i += 1;
754 }
755 }
756
757 #[test]
758 fn test() {
759 {
760 let mut v1 = ~[3, 7, 4, 5, 2, 9, 5, 8];
761 let mut v2 = ~[2, 3, 4, 5, 5, 7, 8, 9];
762 check_sort(v1, v2);
763 }
764 {
765 let mut v1 = ~[1, 1, 1];
766 let mut v2 = ~[1, 1, 1];
767 check_sort(v1, v2);
768 }
769 {
770 let mut v1: ~[int] = ~[];
771 let mut v2: ~[int] = ~[];
772 check_sort(v1, v2);
773 }
774 { let mut v1 = ~[9]; let mut v2 = ~[9]; check_sort(v1, v2); }
775 {
776 let mut v1 = ~[9, 3, 3, 3, 9];
777 let mut v2 = ~[3, 3, 3, 9, 9];
778 check_sort(v1, v2);
779 }
780 }
781 }
782
783 #[cfg(test)]
784 mod test_qsort {
785 use sort::*;
786
787 fn check_sort(v1: &mut [int], v2: &mut [int]) {
788 let len = v1.len();
789 fn leual(a: &int, b: &int) -> bool { *a <= *b }
790 quick_sort::<int>(v1, leual);
791 let mut i = 0u;
792 while i < len {
793 // debug!(v2[i]);
794 assert_eq!(v2[i], v1[i]);
795 i += 1;
796 }
797 }
798
799 #[test]
800 fn test() {
801 {
802 let mut v1 = ~[3, 7, 4, 5, 2, 9, 5, 8];
803 let mut v2 = ~[2, 3, 4, 5, 5, 7, 8, 9];
804 check_sort(v1, v2);
805 }
806 {
807 let mut v1 = ~[1, 1, 1];
808 let mut v2 = ~[1, 1, 1];
809 check_sort(v1, v2);
810 }
811 {
812 let mut v1: ~[int] = ~[];
813 let mut v2: ~[int] = ~[];
814 check_sort(v1, v2);
815 }
816 { let mut v1 = ~[9]; let mut v2 = ~[9]; check_sort(v1, v2); }
817 {
818 let mut v1 = ~[9, 3, 3, 3, 9];
819 let mut v2 = ~[3, 3, 3, 9, 9];
820 check_sort(v1, v2);
821 }
822 }
823
824 // Regression test for #750
825 #[test]
826 fn test_simple() {
827 let mut names = ~[2, 1, 3];
828
829 let expected = ~[1, 2, 3];
830
831 do quick_sort(names) |x, y| { *x < *y };
832
833 let immut_names = names;
834
835 for (&a, &b) in expected.iter().zip(immut_names.iter()) {
836 debug!("%d %d", a, b);
837 assert_eq!(a, b);
838 }
839 }
840 }
841
842 #[cfg(test)]
843 mod tests {
844
845 use sort::*;
846
847 fn check_sort(v1: &[int], v2: &[int]) {
848 let len = v1.len();
849 pub fn le(a: &int, b: &int) -> bool { *a <= *b }
850 let f = le;
851 let v3 = merge_sort::<int>(v1, f);
852 let mut i = 0u;
853 while i < len {
854 debug!(v3[i]);
855 assert_eq!(v3[i], v2[i]);
856 i += 1;
857 }
858 }
859
860 #[test]
861 fn test() {
862 {
863 let v1 = ~[3, 7, 4, 5, 2, 9, 5, 8];
864 let v2 = ~[2, 3, 4, 5, 5, 7, 8, 9];
865 check_sort(v1, v2);
866 }
867 { let v1 = ~[1, 1, 1]; let v2 = ~[1, 1, 1]; check_sort(v1, v2); }
868 { let v1:~[int] = ~[]; let v2:~[int] = ~[]; check_sort(v1, v2); }
869 { let v1 = ~[9]; let v2 = ~[9]; check_sort(v1, v2); }
870 {
871 let v1 = ~[9, 3, 3, 3, 9];
872 let v2 = ~[3, 3, 3, 9, 9];
873 check_sort(v1, v2);
874 }
875 }
876
877 #[test]
878 fn test_merge_sort_mutable() {
879 pub fn le(a: &int, b: &int) -> bool { *a <= *b }
880 let v1 = ~[3, 2, 1];
881 let v2 = merge_sort(v1, le);
882 assert_eq!(v2, ~[1, 2, 3]);
883 }
884
885 #[test]
886 fn test_merge_sort_stability() {
887 // tjc: funny that we have to use parens
888 fn ile(x: &(&'static str), y: &(&'static str)) -> bool
889 {
890 // FIXME: #4318 Instead of to_ascii and to_str_ascii, could use
891 // to_ascii_move and to_str_move to not do a unnecessary clone.
892 // (Actually, could just remove the to_str_* call, but needs an deriving(Ord) on
893 // Ascii)
894 let x = x.to_ascii().to_lower().to_str_ascii();
895 let y = y.to_ascii().to_lower().to_str_ascii();
896 x <= y
897 }
898
899 let names1 = ~["joe bob", "Joe Bob", "Jack Brown", "JOE Bob",
900 "Sally Mae", "JOE BOB", "Alex Andy"];
901 let names2 = ~["Alex Andy", "Jack Brown", "joe bob", "Joe Bob",
902 "JOE Bob", "JOE BOB", "Sally Mae"];
903 let names3 = merge_sort(names1, ile);
904 assert_eq!(names3, names2);
905 }
906 }
907
908 #[cfg(test)]
909 mod test_tim_sort {
910
911 use sort::tim_sort;
912 use std::rand::Rng;
913 use std::rand;
914 use std::vec;
915
916 #[deriving(Clone)]
917 struct CVal {
918 val: float,
919 }
920
921 impl Ord for CVal {
922 fn lt(&self, other: &CVal) -> bool {
923 let mut rng = rand::rng();
924 if rng.gen::<float>() > 0.995 {
925 fail!("It's happening!!!");
926 }
927 (*self).val < other.val
928 }
929 fn le(&self, other: &CVal) -> bool { (*self).val <= other.val }
930 fn gt(&self, other: &CVal) -> bool { (*self).val > other.val }
931 fn ge(&self, other: &CVal) -> bool { (*self).val >= other.val }
932 }
933
934 fn check_sort(v1: &mut [int], v2: &mut [int]) {
935 let len = v1.len();
936 tim_sort::<int>(v1);
937 let mut i = 0u;
938 while i < len {
939 // debug!(v2[i]);
940 assert_eq!(v2[i], v1[i]);
941 i += 1u;
942 }
943 }
944
945 #[test]
946 fn test() {
947 {
948 let mut v1 = ~[3, 7, 4, 5, 2, 9, 5, 8];
949 let mut v2 = ~[2, 3, 4, 5, 5, 7, 8, 9];
950 check_sort(v1, v2);
951 }
952 {
953 let mut v1 = ~[1, 1, 1];
954 let mut v2 = ~[1, 1, 1];
955 check_sort(v1, v2);
956 }
957 {
958 let mut v1: ~[int] = ~[];
959 let mut v2: ~[int] = ~[];
960 check_sort(v1, v2);
961 }
962 { let mut v1 = ~[9]; let mut v2 = ~[9]; check_sort(v1, v2); }
963 {
964 let mut v1 = ~[9, 3, 3, 3, 9];
965 let mut v2 = ~[3, 3, 3, 9, 9];
966 check_sort(v1, v2);
967 }
968 }
969
970 #[test]
971 #[should_fail]
972 #[cfg(unix)]
973 fn crash_test() {
974 let mut rng = rand::rng();
975 let mut arr = do vec::from_fn(1000) |_i| {
976 CVal { val: rng.gen() }
977 };
978
979 tim_sort(arr);
980 fail!("Guarantee the fail");
981 }
982
983 #[deriving(Clone)]
984 struct DVal {
985 val: uint,
986 }
987
988 impl Ord for DVal {
989 fn lt(&self, _x: &DVal) -> bool { true }
990 fn le(&self, _x: &DVal) -> bool { true }
991 fn gt(&self, _x: &DVal) -> bool { true }
992 fn ge(&self, _x: &DVal) -> bool { true }
993 }
994
995 #[test]
996 fn test_bad_Ord_impl() {
997 let mut rng = rand::rng();
998 let mut arr = do vec::from_fn(500) |_i| {
999 DVal { val: rng.gen() }
1000 };
1001
1002 tim_sort(arr);
1003 }
1004 }
1005
1006 #[cfg(test)]
1007 mod big_tests {
1008
1009 use sort::*;
1010
1011 use std::rand::Rng;
1012 use std::rand;
1013 use std::vec;
1014
1015 #[test]
1016 fn test_unique() {
1017 let low = 5;
1018 let high = 10;
1019 tabulate_unique(low, high);
1020 }
1021
1022 #[test]
1023 fn test_managed() {
1024 let low = 5;
1025 let high = 10;
1026 tabulate_managed(low, high);
1027 }
1028
1029 fn multiplyVec<T:Clone>(arr: &[T], num: uint) -> ~[T] {
1030 let size = arr.len();
1031 let res = do vec::from_fn(num) |i| {
1032 arr[i % size].clone()
1033 };
1034 res
1035 }
1036
1037 fn makeRange(n: uint) -> ~[uint] {
1038 let one = do vec::from_fn(n) |i| { i };
1039 let mut two = one.clone();
1040 two.reverse();
1041 vec::append(two, one)
1042 }
1043
1044 fn tabulate_unique(lo: uint, hi: uint) {
1045 fn isSorted<T:Ord>(arr: &[T]) {
1046 for i in range(0u, arr.len() - 1) {
1047 if arr[i] > arr[i+1] {
1048 fail!("Array not sorted");
1049 }
1050 }
1051 }
1052
1053 let mut rng = rand::rng();
1054
1055 for i in range(lo, hi) {
1056 let n = 1 << i;
1057 let mut arr: ~[float] = do vec::from_fn(n) |_i| {
1058 rng.gen()
1059 };
1060
1061 tim_sort(arr); // *sort
1062 isSorted(arr);
1063
1064 arr.reverse();
1065 tim_sort(arr); // \sort
1066 isSorted(arr);
1067
1068 tim_sort(arr); // /sort
1069 isSorted(arr);
1070
1071 do 3.times {
1072 let i1 = rng.gen_integer_range(0u, n);
1073 let i2 = rng.gen_integer_range(0u, n);
1074 arr.swap(i1, i2);
1075 }
1076 tim_sort(arr); // 3sort
1077 isSorted(arr);
1078
1079 if n >= 10 {
1080 let size = arr.len();
1081 let mut idx = 1;
1082 while idx <= 10 {
1083 arr[size-idx] = rng.gen();
1084 idx += 1;
1085 }
1086 }
1087 tim_sort(arr); // +sort
1088 isSorted(arr);
1089
1090 do (n/100).times {
1091 let idx = rng.gen_integer_range(0u, n);
1092 arr[idx] = rng.gen();
1093 }
1094 tim_sort(arr);
1095 isSorted(arr);
1096
1097 let mut arr = if n > 4 {
1098 let part = arr.slice(0, 4);
1099 multiplyVec(part, n)
1100 } else { arr };
1101 tim_sort(arr); // ~sort
1102 isSorted(arr);
1103
1104 let mut arr = vec::from_elem(n, -0.5);
1105 tim_sort(arr); // =sort
1106 isSorted(arr);
1107
1108 let half = n / 2;
1109 let mut arr = makeRange(half).map(|i| *i as float);
1110 tim_sort(arr); // !sort
1111 isSorted(arr);
1112 }
1113 }
1114
1115 fn tabulate_managed(lo: uint, hi: uint) {
1116 fn isSorted<T:Ord>(arr: &[@T]) {
1117 for i in range(0u, arr.len() - 1) {
1118 if arr[i] > arr[i+1] {
1119 fail!("Array not sorted");
1120 }
1121 }
1122 }
1123
1124 let mut rng = rand::rng();
1125
1126 for i in range(lo, hi) {
1127 let n = 1 << i;
1128 let arr: ~[@float] = do vec::from_fn(n) |_i| {
1129 @rng.gen()
1130 };
1131 let mut arr = arr;
1132
1133 tim_sort(arr); // *sort
1134 isSorted(arr);
1135
1136 arr.reverse();
1137 tim_sort(arr); // \sort
1138 isSorted(arr);
1139
1140 tim_sort(arr); // /sort
1141 isSorted(arr);
1142
1143 do 3.times {
1144 let i1 = rng.gen_integer_range(0u, n);
1145 let i2 = rng.gen_integer_range(0u, n);
1146 arr.swap(i1, i2);
1147 }
1148 tim_sort(arr); // 3sort
1149 isSorted(arr);
1150
1151 if n >= 10 {
1152 let size = arr.len();
1153 let mut idx = 1;
1154 while idx <= 10 {
1155 arr[size-idx] = @rng.gen();
1156 idx += 1;
1157 }
1158 }
1159 tim_sort(arr); // +sort
1160 isSorted(arr);
1161
1162 do (n/100).times {
1163 let idx = rng.gen_integer_range(0u, n);
1164 arr[idx] = @rng.gen();
1165 }
1166 tim_sort(arr);
1167 isSorted(arr);
1168
1169 let mut arr = if n > 4 {
1170 let part = arr.slice(0, 4);
1171 multiplyVec(part, n)
1172 } else { arr };
1173 tim_sort(arr); // ~sort
1174 isSorted(arr);
1175
1176 let mut arr = vec::from_elem(n, @(-0.5));
1177 tim_sort(arr); // =sort
1178 isSorted(arr);
1179
1180 let half = n / 2;
1181 let mut arr = makeRange(half).map(|i| @(*i as float));
1182 tim_sort(arr); // !sort
1183 isSorted(arr);
1184 }
1185 }
1186 }
libextra/sort.rs:27:4-27:4 -ty- definition:
type Slice = (uint, uint);
references:-31: fn merge_sort_<T:Clone>(v: &[T], slice: Slice, le: Le<T>) -> ~[T] {
libextra/sort.rs:278:1-278:1 -fn- definition:
fn count_run_ascending<T:Clone + Ord>(array: &mut [T]) -> uint {
references:-206: let mut run_len: uint = count_run_ascending(arr);
192: let init_run_len = count_run_ascending(array);
libextra/sort.rs:413:38-413:38 -fn- definition:
// Fixme (#3853) Move into MergeState
fn MergeState<T>() -> MergeState<T> {
references:-197: let mut ms = MergeState();
libextra/sort.rs:82:1-82:1 -fn- definition:
fn qsort<T>(arr: &mut [T], left: uint,
references:-105: qsort::<T>(arr, 0u, len - 1u, compare_func);
92: qsort::<T>(arr, new_pivot + 1u, right, compare_func);
90: qsort::<T>(arr, left, new_pivot - 1u, |x,y| compare_func(x,y));
libextra/sort.rs:17:1-17:1 -ty- definition:
type Le<'self, T> = &'self fn(v1: &T, v2: &T) -> bool;
references:-84: right: uint, compare_func: Le<T>) {
26: pub fn merge_sort<T:Clone>(v: &[T], le: Le<T>) -> ~[T] {
68: right: uint, pivot: uint, compare_func: Le<T>) -> uint {
46: fn merge<T:Clone>(le: Le<T>, a: &[T], b: &[T]) -> ~[T] {
31: fn merge_sort_<T:Clone>(v: &[T], slice: Slice, le: Le<T>) -> ~[T] {
102: pub fn quick_sort<T>(arr: &mut [T], compare_func: Le<T>) {
libextra/sort.rs:101:4-101:4 -fn- definition:
*/
pub fn quick_sort<T>(arr: &mut [T], compare_func: Le<T>) {
references:-libextra/glob.rs:
133: sort::quick_sort(children, |p1, p2| p2.components.last() <= p1.components.last());
libextra/test.rs:
797: sort::quick_sort(filtered, lteq);
libextra/sort.rs:407:1-407:1 -struct- definition:
struct MergeState<T> {
references:-421: impl<T:Clone + Ord> MergeState<T> {
414: fn MergeState<T>() -> MergeState<T> {
415: MergeState {
libextra/sort.rs:228:1-228:1 -fn- definition:
fn binarysort<T:Clone + Ord>(array: &mut [T], start: uint) {
references:-193: binarysort(array, init_run_len);
211: binarysort(slice, run_len);
libextra/sort.rs:184:22-184:22 -fn- definition:
#[allow(missing_doc)]
pub fn tim_sort<T:Clone + Ord>(array: &mut [T]) {
references:-libextra/stats.rs:
204: sort::tim_sort(tmp);
210: sort::tim_sort(tmp);
255: sort::tim_sort(tmp);
libextra/test.rs:
458: sort::tim_sort(failures);
libextra/sort.rs:267:1-267:1 -fn- definition:
fn min_run_length(n: uint) -> uint {
references:-198: let min_run = min_run_length(size);
libextra/sort.rs:402:1-402:1 -struct- definition:
struct RunState {
references:-410: runs: ~[RunState],
423: let tmp = RunState{base: run_base, len: run_len};
libextra/sort.rs:164:4-164:4 -fn- definition:
*/
pub fn quick_sort3<T:Clone + Ord + Eq>(arr: &mut [T]) {
references:-177: fn qsort(self) { quick_sort3(self); }
libextra/sort.rs:734:10-734:10 -fn- definition:
#[inline]
fn shift_vec<T:Clone>(dest: &mut [T], s1: uint, s2: uint, len: uint) {
references:-544: shift_vec(array, dest, c2, count2);
564: shift_vec(array, dest, c2, len2);
253: shift_vec(array, left+1, left, n);
597: shift_vec(array, dest+1, c1+1, len1);
683: shift_vec(array, dest+1, c1+1, len1);
643: shift_vec(array, dest+1, c1+1, count1);
488: shift_vec(array, dest, c2, len2);
libextra/sort.rs:31:4-31:4 -fn- definition:
fn merge_sort_<T:Clone>(v: &[T], slice: Slice, le: Le<T>) -> ~[T] {
let begin = slice.first();
references:-42: return merge(|x,y| le(x,y), merge_sort_(v, a, |x,y| le(x,y)),
29: return merge_sort_(v, (0u, v.len()), le);
43: merge_sort_(v, b, |x,y| le(x,y)));
libextra/sort.rs:298:1-298:1 -fn- definition:
fn gallop_left<T:Clone + Ord>(key: &T,
references:-654: count2 = len2 - gallop_left(&array[c1],
541: gallop_left(&tmp[c1], tmp_view, 0)
455: gallop_left(&array[b1+l1-1],slice,l2-1)
libextra/sort.rs:259:54-259:54 -fn- definition:
// Reverse the order of elements in a slice, in place
fn reverse_slice<T>(v: &mut [T], start: uint, end:uint) {
references:-289: reverse_slice(array, 0, run);
libextra/sort.rs:349:1-349:1 -fn- definition:
fn gallop_right<T:Clone + Ord>(key: &T,
references:-448: gallop_right(&array[b2], slice, 0)
637: count1 = len1 - gallop_right(
528: gallop_right(&array[c2], tmp_view, 0)
libextra/sort.rs:107:1-107:1 -fn- definition:
fn qsort3<T:Clone + Ord + Eq>(arr: &mut [T], left: int, right: int) {
references:-152: qsort3::<T>(arr, i, right);
151: qsort3::<T>(arr, left, j);
168: qsort3(arr, 0, (len - 1) as int);
libextra/sort.rs:171:22-171:22 -trait- definition:
#[allow(missing_doc)]
pub trait Sort {
references:-176: impl<'self, T:Clone + Ord + Eq> Sort for &'self mut [T] {
libextra/sort.rs:723:10-723:10 -fn- definition:
#[inline]
fn copy_vec<T:Clone>(dest: &mut [T],
references:-661: copy_vec(array, dest+1, tmp.slice(c2+1, c2+1+count2));
739: copy_vec(dest, s1, tmp);
531: copy_vec(array, dest, tmp.slice(c1, c1+count1));
591: copy_vec(array, dest-(len2-1), tmp.slice(0, len2));
484: copy_vec(array, dest, tmp.slice(0, len1));
690: copy_vec(array, dest-(len2-1), tmp.slice(0, len2));
571: copy_vec(array, dest, tmp.slice(c1, c1+len1));
libextra/sort.rs:66:1-66:1 -fn- definition:
fn part<T>(arr: &mut [T], left: uint,
references:-87: let new_pivot = part::<T>(arr, left, right, pivot, |x,y| compare_func(x,y));
libextra/sort.rs:46:4-46:4 -fn- definition:
fn merge<T:Clone>(le: Le<T>, a: &[T], b: &[T]) -> ~[T] {
let mut rs = vec::with_capacity(a.len() + b.len());
references:-42: return merge(|x,y| le(x,y), merge_sort_(v, a, |x,y| le(x,y)),