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.
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.
13 use core::cmp::{Eq, Ord};
18 type Le<'self, T> = &'self fn(v1: &T, v2: &T) -> bool;
21 * Merge sort. Returns a new vector containing the sorted list.
23 * Has worst case O(n log n) performance, best case O(n), but
24 * is not space efficient. This is a stable sort.
26 pub fn merge_sort<T:Copy>(v: &const [T], le: Le<T>) -> ~[T] {
27 type Slice = (uint, uint);
29 return merge_sort_(v, (0u, len(v)), le);
31 fn merge_sort_<T:Copy>(v: &const [T], slice: Slice, le: Le<T>)
33 let begin = slice.first();
34 let end = slice.second();
36 let v_len = end - begin;
37 if v_len == 0 { return ~[]; }
38 if v_len == 1 { return ~[v[begin]]; }
40 let mid = v_len / 2 + begin;
43 return merge(le, merge_sort_(v, a, le), merge_sort_(v, b, le));
46 fn merge<T:Copy>(le: Le<T>, a: &[T], b: &[T]) -> ~[T] {
47 let mut rs = vec::with_capacity(len(a) + len(b));
52 while a_ix < a_len && b_ix < b_len {
53 if le(&a[a_ix], &b[b_ix]) {
56 } else { rs.push(b[b_ix]); b_ix += 1; }
58 rs.push_all(vec::slice(a, a_ix, a_len));
59 rs.push_all(vec::slice(b, b_ix, b_len));
64 fn part<T>(arr: &mut [T], left: uint,
65 right: uint, pivot: uint, compare_func: Le<T>) -> uint {
66 arr[pivot] <-> arr[right];
67 let mut storage_index: uint = left;
68 let mut i: uint = left;
70 let a: &mut T = &mut arr[i];
71 let b: &mut T = &mut arr[right];
72 if compare_func(a, b) {
73 arr[i] <-> arr[storage_index];
78 arr[storage_index] <-> arr[right];
82 fn qsort<T>(arr: &mut [T], left: uint,
83 right: uint, compare_func: Le<T>) {
85 let pivot = (left + right) / 2u;
86 let new_pivot = part::<T>(arr, left, right, pivot, compare_func);
88 // Need to do this check before recursing due to overflow
89 qsort::<T>(arr, left, new_pivot - 1u, compare_func);
91 qsort::<T>(arr, new_pivot + 1u, right, compare_func);
96 * Quicksort. Sorts a mut vector in place.
98 * Has worst case O(n^2) performance, average case O(n log n).
99 * This is an unstable sort.
101 pub fn quick_sort<T>(arr: &mut [T], compare_func: Le<T>) {
102 if len::<T>(arr) == 0u { return; }
103 qsort::<T>(arr, 0u, len::<T>(arr) - 1u, compare_func);
106 fn qsort3<T:Copy + Ord + Eq>(arr: &mut [T], left: int, right: int) {
107 if right <= left { return; }
108 let v: T = arr[right];
109 let mut i: int = left - 1;
110 let mut j: int = right;
115 while arr[i] < v { i += 1; }
118 if j == left { break; }
132 arr[i] <-> arr[right];
135 let mut k: int = left;
140 if k == len::<T>(arr) as int { break; }
149 qsort3::<T>(arr, left, j);
150 qsort3::<T>(arr, i, right);
154 * Fancy quicksort. Sorts a mut vector in place.
156 * Based on algorithm presented by ~[Sedgewick and Bentley]
157 * (http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf).
158 * According to these slides this is the algorithm of choice for
159 * 'randomly ordered keys, abstract compare' & 'small number of key values'.
161 * This is an unstable sort.
163 pub fn quick_sort3<T:Copy + Ord + Eq>(arr: &mut [T]) {
164 if arr.len() <= 1 { return; }
165 qsort3(arr, 0, (arr.len() - 1) as int);
172 impl<'self, T:Copy + Ord + Eq> Sort for &'self mut [T] {
173 fn qsort(self) { quick_sort3(self); }
176 static MIN_MERGE: uint = 64;
177 static MIN_GALLOP: uint = 7;
178 static INITIAL_TMP_STORAGE: uint = 128;
180 pub fn tim_sort<T:Copy + Ord>(array: &mut [T]) {
181 let size = array.len();
186 if size < MIN_MERGE {
187 let init_run_len = count_run_ascending(array);
188 binarysort(array, init_run_len);
192 let mut ms = MergeState();
193 let min_run = min_run_length(size);
196 let mut remaining = size;
198 let arr = vec::mut_slice(array, idx, size);
199 let mut run_len: uint = count_run_ascending(arr);
201 if run_len < min_run {
202 let force = if remaining <= min_run {remaining} else {min_run};
203 let slice = vec::mut_slice(arr, 0, force);
204 binarysort(slice, run_len);
208 ms.push_run(idx, run_len);
209 ms.merge_collapse(array);
212 remaining -= run_len;
213 if remaining == 0 { break; }
216 ms.merge_force_collapse(array);
219 fn binarysort<T:Copy + Ord>(array: &mut [T], start: uint) {
220 let size = array.len();
221 let mut start = start;
222 assert!(start <= size);
224 if start == 0 { start += 1; }
227 let pivot = array[start];
229 let mut right = start;
230 assert!(left <= right);
233 let mid = (left + right) >> 1;
234 if pivot < array[mid] {
240 assert!(left == right);
243 copy_vec(array, left+1, array, left, n);
249 // Reverse the order of elements in a slice, in place
250 fn reverse_slice<T>(v: &mut [T], start: uint, end:uint) {
253 util::swap(&mut v[i], &mut v[end - i - 1]);
258 fn min_run_length(n: uint) -> uint {
260 let mut r = 0; // becomes 1 if any 1 bits are shifted off
262 while n >= MIN_MERGE {
269 fn count_run_ascending<T:Copy + Ord>(array: &mut [T]) -> uint {
270 let size = array.len();
272 if size == 1 { return 1; }
275 if array[1] < array[0] {
276 while run < size && array[run] < array[run-1] {
279 reverse_slice(array, 0, run);
281 while run < size && array[run] >= array[run-1] {
289 fn gallop_left<T:Copy + Ord>(key: &const T,
293 let size = array.len();
294 assert!(size != 0 && hint < size);
296 let mut last_ofs = 0;
299 if *key > array[hint] {
300 // Gallop right until array[hint+last_ofs] < key <= array[hint+ofs]
301 let max_ofs = size - hint;
302 while ofs < max_ofs && *key > array[hint+ofs] {
304 ofs = (ofs << 1) + 1;
305 if ofs < last_ofs { ofs = max_ofs; } // uint overflow guard
307 if ofs > max_ofs { ofs = max_ofs; }
312 let max_ofs = hint + 1;
313 while ofs < max_ofs && *key <= array[hint-ofs] {
315 ofs = (ofs << 1) + 1;
316 if ofs < last_ofs { ofs = max_ofs; } // uint overflow guard
319 if ofs > max_ofs { ofs = max_ofs; }
322 last_ofs = hint - ofs;
325 assert!((last_ofs < ofs || last_ofs+1 < ofs+1) && ofs <= size);
328 while last_ofs < ofs {
329 let m = last_ofs + ((ofs - last_ofs) >> 1);
336 assert!(last_ofs == ofs);
340 fn gallop_right<T:Copy + Ord>(key: &const T,
344 let size = array.len();
345 assert!(size != 0 && hint < size);
347 let mut last_ofs = 0;
350 if *key >= array[hint] {
351 // Gallop right until array[hint+last_ofs] <= key < array[hint+ofs]
352 let max_ofs = size - hint;
353 while ofs < max_ofs && *key >= array[hint+ofs] {
355 ofs = (ofs << 1) + 1;
356 if ofs < last_ofs { ofs = max_ofs; }
358 if ofs > max_ofs { ofs = max_ofs; }
363 // Gallop left until array[hint-ofs] <= key < array[hint-last_ofs]
364 let max_ofs = hint + 1;
365 while ofs < max_ofs && *key < array[hint-ofs] {
367 ofs = (ofs << 1) + 1;
368 if ofs < last_ofs { ofs = max_ofs; }
370 if ofs > max_ofs { ofs = max_ofs; }
373 last_ofs = hint - ofs;
377 assert!((last_ofs < ofs || last_ofs+1 < ofs+1) && ofs <= size);
380 while last_ofs < ofs {
381 let m = last_ofs + ((ofs - last_ofs) >> 1);
383 if *key >= array[m] {
389 assert!(last_ofs == ofs);
398 struct MergeState<T> {
403 // Fixme (#3853) Move into MergeState
404 fn MergeState<T>() -> MergeState<T> {
406 min_gallop: MIN_GALLOP,
411 impl<T:Copy + Ord> MergeState<T> {
412 fn push_run(&mut self, run_base: uint, run_len: uint) {
413 let tmp = RunState{base: run_base, len: run_len};
417 fn merge_at(&mut self, n: uint, array: &mut [T]) {
418 let size = self.runs.len();
420 assert!(n == size-2 || n == size-3);
422 let mut b1 = self.runs[n].base;
423 let mut l1 = self.runs[n].len;
424 let b2 = self.runs[n+1].base;
425 let l2 = self.runs[n+1].len;
427 assert!(l1 > 0 && l2 > 0);
428 assert!(b1 + l1 == b2);
430 self.runs[n].len = l1 + l2;
432 self.runs[n+1].base = self.runs[n+2].base;
433 self.runs[n+1].len = self.runs[n+2].len;
436 let slice = vec::mut_slice(array, b1, b1+l1);
437 let k = gallop_right(&const array[b2], slice, 0);
441 let slice = vec::mut_slice(array, b2, b2+l2);
442 let l2 = gallop_left(
443 &const array[b1+l1-1],slice,l2-1);
446 self.merge_lo(array, b1, l1, b2, l2);
448 self.merge_hi(array, b1, l1, b2, l2);
455 fn merge_lo(&mut self, array: &mut [T], base1: uint, len1: uint,
456 base2: uint, len2: uint) {
457 assert!(len1 != 0 && len2 != 0 && base1+len1 == base2);
460 for uint::range(base1, base1+len1) |i| {
466 let mut dest = base1;
470 array[dest] <-> array[c2];
471 dest += 1; c2 += 1; len2 -= 1;
474 copy_vec(array, dest, tmp, 0, len1);
478 copy_vec(array, dest, array, c2, len2);
479 array[dest+len2] <-> tmp[c1];
483 let mut min_gallop = self.min_gallop;
487 let mut break_outer = false;
490 assert!(len1 > 1 && len2 != 0);
491 if array[c2] < tmp[c1] {
492 array[dest] <-> array[c2];
493 dest += 1; c2 += 1; len2 -= 1;
494 count2 += 1; count1 = 0;
499 array[dest] <-> tmp[c1];
500 dest += 1; c1 += 1; len1 -= 1;
501 count1 += 1; count2 = 0;
506 if break_outer || ((count1 | count2) >= min_gallop) {
510 if break_outer { break; }
514 assert!(len1 > 1 && len2 != 0);
516 let tmp_view = vec::const_slice(tmp, c1, c1+len1);
517 count1 = gallop_right(&const array[c2], tmp_view, 0);
519 copy_vec(array, dest, tmp, c1, count1);
520 dest += count1; c1 += count1; len1 -= count1;
521 if len1 <= 1 { break_outer = true; break; }
523 array[dest] <-> array[c2];
524 dest += 1; c2 += 1; len2 -= 1;
525 if len2 == 0 { break_outer = true; break; }
527 let tmp_view = vec::const_slice(array, c2, c2+len2);
528 count2 = gallop_left(&const tmp[c1], tmp_view, 0);
530 copy_vec(array, dest, array, c2, count2);
531 dest += count2; c2 += count2; len2 -= count2;
532 if len2 == 0 { break_outer = true; break; }
534 array[dest] <-> tmp[c1];
535 dest += 1; c1 += 1; len1 -= 1;
536 if len1 == 1 { break_outer = true; break; }
538 if !(count1 >= MIN_GALLOP || count2 >= MIN_GALLOP) {
542 if break_outer { break; }
543 if min_gallop < 0 { min_gallop = 0; }
544 min_gallop += 2; // Penalize for leaving gallop
546 self.min_gallop = if min_gallop < 1 { 1 } else { min_gallop };
550 copy_vec(array, dest, array, c2, len2);
551 array[dest+len2] <-> tmp[c1];
552 } else if len1 == 0 {
553 fail!(~"Comparison violates its contract!");
557 copy_vec(array, dest, tmp, c1, len1);
561 fn merge_hi(&mut self, array: &mut [T], base1: uint, len1: uint,
562 base2: uint, len2: uint) {
563 assert!(len1 != 1 && len2 != 0 && base1 + len1 == base2);
566 for uint::range(base2, base2+len2) |i| {
570 let mut c1 = base1 + len1 - 1;
571 let mut c2 = len2 - 1;
572 let mut dest = base2 + len2 - 1;
576 array[dest] <-> array[c1];
577 dest -= 1; c1 -= 1; len1 -= 1;
580 copy_vec(array, dest-(len2-1), tmp, 0, len2);
586 copy_vec(array, dest+1, array, c1+1, len1);
587 array[dest] <-> tmp[c2];
591 let mut min_gallop = self.min_gallop;
595 let mut break_outer = false;
598 assert!(len1 != 0 && len2 > 1);
599 if tmp[c2] < array[c1] {
600 array[dest] <-> array[c1];
601 dest -= 1; c1 -= 1; len1 -= 1;
602 count1 += 1; count2 = 0;
607 array[dest] <-> tmp[c2];
608 dest -= 1; c2 -= 1; len2 -= 1;
609 count2 += 1; count1 = 0;
614 if break_outer || ((count1 | count2) >= min_gallop) {
618 if break_outer { break; }
622 assert!(len2 > 1 && len1 != 0);
624 let tmp_view = vec::mut_slice(array, base1, base1+len1);
625 count1 = len1 - gallop_right(
626 &const tmp[c2], tmp_view, len1-1);
629 dest -= count1; c1 -= count1; len1 -= count1;
630 copy_vec(array, dest+1, array, c1+1, count1);
631 if len1 == 0 { break_outer = true; break; }
634 array[dest] <-> tmp[c2];
635 dest -= 1; c2 -= 1; len2 -= 1;
636 if len2 == 1 { break_outer = true; break; }
640 let tmp_view = vec::mut_slice(tmp, 0, len2);
641 count2 = len2 - gallop_left(&const array[c1],
644 // Make tmp_view go out of scope to appease borrowck.
648 dest -= count2; c2 -= count2; len2 -= count2;
649 copy_vec(array, dest+1, tmp, c2+1, count2);
650 if len2 <= 1 { break_outer = true; break; }
652 array[dest] <-> array[c1];
653 dest -= 1; c1 -= 1; len1 -= 1;
654 if len1 == 0 { break_outer = true; break; }
656 if !(count1 >= MIN_GALLOP || count2 >= MIN_GALLOP) {
661 if break_outer { break; }
662 if min_gallop < 0 { min_gallop = 0; }
663 min_gallop += 2; // Penalize for leaving gallop
665 self.min_gallop = if min_gallop < 1 { 1 } else { min_gallop };
671 copy_vec(array, dest+1, array, c1+1, len1);
672 array[dest] <-> tmp[c2];
673 } else if len2 == 0 {
674 fail!(~"Comparison violates its contract!");
678 copy_vec(array, dest-(len2-1), tmp, 0, len2);
682 fn merge_collapse(&mut self, array: &mut [T]) {
683 while self.runs.len() > 1 {
684 let mut n = self.runs.len()-2;
686 self.runs[n-1].len <= self.runs[n].len + self.runs[n+1].len
688 if self.runs[n-1].len < self.runs[n+1].len { n -= 1; }
689 } else if self.runs[n].len <= self.runs[n+1].len {
694 self.merge_at(n, array);
698 fn merge_force_collapse(&mut self, array: &mut [T]) {
699 while self.runs.len() > 1 {
700 let mut n = self.runs.len()-2;
702 if self.runs[n-1].len < self.runs[n+1].len {
706 self.merge_at(n, array);
712 fn copy_vec<T:Copy>(dest: &mut [T],
717 assert!(s1+len <= dest.len() && s2+len <= from.len());
720 for uint::range(s2, s2+len) |i| {
724 for slice.eachi |i, v| {
735 fn check_sort(v1: &mut [int], v2: &mut [int]) {
736 let len = vec::len::<int>(v1);
737 quick_sort3::<int>(v1);
741 assert!((v2[i] == v1[i]));
749 let mut v1 = ~[3, 7, 4, 5, 2, 9, 5, 8];
750 let mut v2 = ~[2, 3, 4, 5, 5, 7, 8, 9];
754 let mut v1 = ~[1, 1, 1];
755 let mut v2 = ~[1, 1, 1];
759 let mut v1: ~[int] = ~[];
760 let mut v2: ~[int] = ~[];
763 { let mut v1 = ~[9]; let mut v2 = ~[9]; check_sort(v1, v2); }
765 let mut v1 = ~[9, 3, 3, 3, 9];
766 let mut v2 = ~[3, 3, 3, 9, 9];
779 fn check_sort(v1: &mut [int], v2: &mut [int]) {
780 let len = vec::len::<int>(v1);
781 fn leual(a: &int, b: &int) -> bool { *a <= *b }
782 quick_sort::<int>(v1, leual);
786 assert!((v2[i] == v1[i]));
794 let mut v1 = ~[3, 7, 4, 5, 2, 9, 5, 8];
795 let mut v2 = ~[2, 3, 4, 5, 5, 7, 8, 9];
799 let mut v1 = ~[1, 1, 1];
800 let mut v2 = ~[1, 1, 1];
804 let mut v1: ~[int] = ~[];
805 let mut v2: ~[int] = ~[];
808 { let mut v1 = ~[9]; let mut v2 = ~[9]; check_sort(v1, v2); }
810 let mut v1 = ~[9, 3, 3, 3, 9];
811 let mut v2 = ~[3, 3, 3, 9, 9];
816 // Regression test for #750
819 let mut names = ~[2, 1, 3];
821 let expected = ~[1, 2, 3];
823 do quick_sort(names) |x, y| { int::le(*x, *y) };
825 let immut_names = names;
827 let pairs = vec::zip_slice(expected, immut_names);
828 for vec::each(pairs) |p| {
830 debug!("%d %d", a, b);
843 fn check_sort(v1: &[int], v2: &[int]) {
844 let len = vec::len::<int>(v1);
845 pub fn le(a: &int, b: &int) -> bool { *a <= *b }
847 let v3 = merge_sort::<int>(v1, f);
851 assert!((v3[i] == v2[i]));
859 let v1 = ~[3, 7, 4, 5, 2, 9, 5, 8];
860 let v2 = ~[2, 3, 4, 5, 5, 7, 8, 9];
863 { let v1 = ~[1, 1, 1]; let v2 = ~[1, 1, 1]; check_sort(v1, v2); }
864 { let v1:~[int] = ~[]; let v2:~[int] = ~[]; check_sort(v1, v2); }
865 { let v1 = ~[9]; let v2 = ~[9]; check_sort(v1, v2); }
867 let v1 = ~[9, 3, 3, 3, 9];
868 let v2 = ~[3, 3, 3, 9, 9];
874 fn test_merge_sort_mutable() {
875 pub fn le(a: &int, b: &int) -> bool { *a <= *b }
876 let mut v1 = ~[3, 2, 1];
877 let v2 = merge_sort(v1, le);
878 assert!(v2 == ~[1, 2, 3]);
882 fn test_merge_sort_stability() {
883 // tjc: funny that we have to use parens
884 fn ile(x: &(&'static str), y: &(&'static str)) -> bool
886 // FIXME: #4318 Instead of to_ascii and to_str_ascii, could use
887 // to_ascii_consume and to_str_consume to not do a unnecessary copy.
888 // (Actually, could just remove the to_str_* call, but needs an deriving(Ord) on
890 let x = x.to_ascii().to_lower().to_str_ascii();
891 let y = y.to_ascii().to_lower().to_str_ascii();
895 let names1 = ~["joe bob", "Joe Bob", "Jack Brown", "JOE Bob",
896 "Sally Mae", "JOE BOB", "Alex Andy"];
897 let names2 = ~["Alex Andy", "Jack Brown", "joe bob", "Joe Bob",
898 "JOE Bob", "JOE BOB", "Sally Mae"];
899 let names3 = merge_sort(names1, ile);
900 assert!(names3 == names2);
907 use core::rand::RngUtil;
914 fn lt(&self, other: &CVal) -> bool {
915 let rng = rand::rng();
916 if rng.gen::<float>() > 0.995 { fail!(~"It's happening!!!"); }
917 (*self).val < other.val
919 fn le(&self, other: &CVal) -> bool { (*self).val <= other.val }
920 fn gt(&self, other: &CVal) -> bool { (*self).val > other.val }
921 fn ge(&self, other: &CVal) -> bool { (*self).val >= other.val }
924 fn check_sort(v1: &mut [int], v2: &mut [int]) {
925 let len = vec::len::<int>(v1);
930 assert!((v2[i] == v1[i]));
938 let mut v1 = ~[3, 7, 4, 5, 2, 9, 5, 8];
939 let mut v2 = ~[2, 3, 4, 5, 5, 7, 8, 9];
943 let mut v1 = ~[1, 1, 1];
944 let mut v2 = ~[1, 1, 1];
948 let mut v1: ~[int] = ~[];
949 let mut v2: ~[int] = ~[];
952 { let mut v1 = ~[9]; let mut v2 = ~[9]; check_sort(v1, v2); }
954 let mut v1 = ~[9, 3, 3, 3, 9];
955 let mut v2 = ~[3, 3, 3, 9, 9];
964 let rng = rand::rng();
965 let mut arr = do vec::from_fn(1000) |_i| {
966 CVal { val: rng.gen() }
970 fail!(~"Guarantee the fail");
973 struct DVal { val: uint }
976 fn lt(&self, _x: &DVal) -> bool { true }
977 fn le(&self, _x: &DVal) -> bool { true }
978 fn gt(&self, _x: &DVal) -> bool { true }
979 fn ge(&self, _x: &DVal) -> bool { true }
983 fn test_bad_Ord_impl() {
984 let rng = rand::rng();
985 let mut arr = do vec::from_fn(500) |_i| {
986 DVal { val: rng.gen() }
996 use core::rand::RngUtil;
1002 tabulate_unique(low, high);
1009 tabulate_managed(low, high);
1012 fn multiplyVec<T:Copy>(arr: &const [T], num: uint) -> ~[T] {
1013 let size = arr.len();
1014 let res = do vec::from_fn(num) |i| {
1020 fn makeRange(n: uint) -> ~[uint] {
1021 let one = do vec::from_fn(n) |i| { i };
1022 let mut two = copy one;
1024 vec::append(two, one)
1027 fn tabulate_unique(lo: uint, hi: uint) {
1028 fn isSorted<T:Ord>(arr: &const [T]) {
1029 for uint::range(0, arr.len()-1) |i| {
1030 if arr[i] > arr[i+1] {
1031 fail!(~"Array not sorted");
1036 let rng = rand::rng();
1038 for uint::range(lo, hi) |i| {
1040 let mut arr: ~[float] = do vec::from_fn(n) |_i| {
1044 tim_sort(arr); // *sort
1048 tim_sort(arr); // \sort
1051 tim_sort(arr); // /sort
1055 let i1 = rng.gen_uint_range(0, n);
1056 let i2 = rng.gen_uint_range(0, n);
1057 arr[i1] <-> arr[i2];
1059 tim_sort(arr); // 3sort
1063 let size = arr.len();
1066 arr[size-idx] = rng.gen();
1070 tim_sort(arr); // +sort
1074 let idx = rng.gen_uint_range(0, n);
1075 arr[idx] = rng.gen();
1080 let mut arr = if n > 4 {
1081 let part = vec::slice(arr, 0, 4);
1082 multiplyVec(part, n)
1084 tim_sort(arr); // ~sort
1087 let mut arr = vec::from_elem(n, -0.5);
1088 tim_sort(arr); // =sort
1092 let mut arr = makeRange(half).map(|i| *i as float);
1093 tim_sort(arr); // !sort
1098 fn tabulate_managed(lo: uint, hi: uint) {
1099 fn isSorted<T:Ord>(arr: &const [@T]) {
1100 for uint::range(0, arr.len()-1) |i| {
1101 if arr[i] > arr[i+1] {
1102 fail!(~"Array not sorted");
1107 let rng = rand::rng();
1109 for uint::range(lo, hi) |i| {
1111 let arr: ~[@float] = do vec::from_fn(n) |_i| {
1116 tim_sort(arr); // *sort
1120 tim_sort(arr); // \sort
1123 tim_sort(arr); // /sort
1127 let i1 = rng.gen_uint_range(0, n);
1128 let i2 = rng.gen_uint_range(0, n);
1129 arr[i1] <-> arr[i2];
1131 tim_sort(arr); // 3sort
1135 let size = arr.len();
1138 arr[size-idx] = @rng.gen();
1142 tim_sort(arr); // +sort
1146 let idx = rng.gen_uint_range(0, n);
1147 arr[idx] = @rng.gen();
1152 let mut arr = if n > 4 {
1153 let part = vec::slice(arr, 0, 4);
1154 multiplyVec(part, n)
1156 tim_sort(arr); // ~sort
1159 let mut arr = vec::from_elem(n, @(-0.5));
1160 tim_sort(arr); // =sort
1164 let mut arr = makeRange(half).map(|i| @(*i as float));
1165 tim_sort(arr); // !sort
1170 struct LVal<'self> {
1172 key: &'self fn(@uint),
1175 #[unsafe_destructor]
1176 impl<'self> Drop for LVal<'self> {
1177 fn finalize(&self) {
1178 let x = unsafe { task::local_data::local_data_get(self.key) };
1182 task::local_data::local_data_set(self.key, @(y+1));
1185 _ => fail!(~"Expected key to work"),
1190 impl<'self> Ord for LVal<'self> {
1191 fn lt<'a>(&self, other: &'a LVal<'self>) -> bool {
1192 (*self).val < other.val
1194 fn le<'a>(&self, other: &'a LVal<'self>) -> bool {
1195 (*self).val <= other.val
1197 fn gt<'a>(&self, other: &'a LVal<'self>) -> bool {
1198 (*self).val > other.val
1200 fn ge<'a>(&self, other: &'a LVal<'self>) -> bool {
1201 (*self).val >= other.val