notriddle · Aug 26, 2020 · Aug 27, 2020 · Aug 27, 2020 · Aug 27, 2020 · Aug 27, 2020
diff --git a/.github/workflows/ci.yaml b/.github/workflows/ci.yaml
@@ -0,0 +1,30 @@
+on:
+  pull_request:
+  push:
+    branches: [master]
+
+jobs:
+  build_test:
+    runs-on: ubuntu-latest
+
+    steps:
+      - uses: actions/checkout@v2
+      - name: Test (debug)
+        uses: actions-rs/cargo@v1
+        with:
+          command: test
+      - name: Test (release)
+        uses: actions-rs/cargo@v1
+        with:
+          command: test
+          args: --release
+      - name: Check rustfmt
+        uses: actions-rs/cargo@v1
+        with:
+          command: fmt
+          args: -- --check
+      - name: Check clippy
+        uses: actions-rs/cargo@v1
+        with:
+          command: clippy
+          args: --tests -- -Dwarnings
diff --git a/.travis.yml b/.travis.yml
diff --git a/Cargo.toml b/Cargo.toml
@@ -1,8 +1,12 @@
 [package]
 name = "timsort"
-version = "0.1.0"
-authors = ["Michael Howell <michael@notriddle.com>"]
+version = "0.1.3"
+description = "Rust implementation of the modified MergeSort used in Python and Java"
+repository = "https://github.com/RustPython/rust-timsort"
+authors = ["Michael Howell <michael@notriddle.com>", "RustPython Team"]
+license = "MIT/Apache-2.0"
+edition = "2018"
 
 [dev-dependencies]
-rand = "0.3.9"
+rand = { version = "0.8", features = ["small_rng"] }
 
diff --git a/LICENSE-MIT b/LICENSE-MIT
@@ -1,4 +1,5 @@
 Copyright (c) 2015 Michael Howell
+Portions (c) 2020 RustPython Team
 
 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal

diff --git a/benches/bench.rs b/benches/bench.rs
@@ -3,24 +3,26 @@
 #![feature(test)]
 #![feature(unboxed_closures)]
 
-extern crate timsort;
 extern crate test;
-extern crate rand;
 
-use timsort::sort;
-use rand::{weak_rng, Rng};
+use rand::{distributions::Standard, prelude::SmallRng, seq::SliceRandom, Rng, SeedableRng};
 use std::mem;
 use test::Bencher;
+use timsort::sort;
+
+type BigSortable = (u64, u64, u64, u64);
 
-type BigSortable = (u64,u64,u64,u64);
+fn rng() -> impl Rng {
+    SmallRng::from_entropy()
+}
 
 macro_rules! bench_random(
     ($name: ident, $sortfun: ident, $typ: ty, $n: expr) => (
         #[bench]
         fn $name(b: &mut Bencher) {
-            let mut rng = weak_rng();
+            let mut rng = rng();
             b.iter(|| {
-                let mut v = rng.gen_iter::<$typ>().take($n).collect::<Vec<$typ>>();
+                let mut v = (&mut rng).sample_iter(Standard).take($n).collect::<Vec<$typ>>();
                 $sortfun(&mut v[..]);
             });
             b.bytes = $n * mem::size_of::<$typ>() as u64;
@@ -42,7 +44,7 @@ bench_random!(sort_big_random_large, sort, BigSortable, 10_000);
 
 #[bench]
 fn sort_sorted(b: &mut Bencher) {
-    let mut v: Vec<_> = (0 .. 10000isize).collect();
+    let mut v: Vec<_> = (0..10000isize).collect();
     b.iter(|| {
         sort(&mut v[..]);
     });
@@ -51,7 +53,7 @@ fn sort_sorted(b: &mut Bencher) {
 
 #[bench]
 fn sort_big_sorted(b: &mut Bencher) {
-    let mut v: Vec<_> = (0 .. 10000usize).map(|i| (i, i, i, i)).collect();
+    let mut v: Vec<_> = (0..10000usize).map(|i| (i, i, i, i)).collect();
     b.iter(|| {
         sort(&mut v[..]);
     });
@@ -61,14 +63,14 @@ fn sort_big_sorted(b: &mut Bencher) {
 #[bench]
 fn sort_few_unique(b: &mut Bencher) {
     let mut v = Vec::new();
-    for i in (0u32 .. 10) {
-        for _ in (0usize .. 100) {
+    for i in 0u32..10 {
+        for _ in 0usize..100 {
             v.push(i);
         }
     }
-    let mut rng = weak_rng();
-    b.iter(||{
-        rng.shuffle(&mut v[..]);
+    let mut rng = rng();
+    b.iter(|| {
+        v.shuffle(&mut rng);
         sort(&mut v[..]);
     });
     b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;
@@ -85,31 +87,41 @@ fn sort_equals(b: &mut Bencher) {
 
 #[bench]
 fn sort_huge(b: &mut Bencher) {
-    let mut rng = weak_rng();
+    let mut rng = rng();
     let n = 100_000;
-    let mut v = rng.gen_iter::<i64>().take(n).collect::<Vec<i64>>();
+    let mut v = (&mut rng)
+        .sample_iter(Standard)
+        .take(n)
+        .collect::<Vec<i64>>();
     b.iter(|| {
-        rng.shuffle(&mut v[..]);
+        v.shuffle(&mut rng);
         sort(&mut v[..]);
     });
     b.bytes = (n * mem::size_of::<i64>()) as u64;
 }
 
 #[bench]
 fn sort_partially_sorted(b: &mut Bencher) {
-    fn partially_sort<T: Ord+::std::fmt::Display>(v: &mut [T]) {
+    fn partially_sort<T: Ord + ::std::fmt::Display>(v: &mut [T]) {
         let s = v.len() / 100;
-        if s == 0 { return; }
+        if s == 0 {
+            return;
+        }
         let mut sorted = true;
         for c in v.chunks_mut(s) {
-            if sorted { sort(&mut c[..]); }
+            if sorted {
+                sort(&mut c[..]);
+            }
             sorted = !sorted;
         }
     }
-    let mut rng = weak_rng();
+    let mut rng = rng();
     let n = 10_000;
-    let mut v = rng.gen_iter::<i64>().take(n).collect::<Vec<i64>>();
-    rng.shuffle(&mut v[..]);
+    let mut v = (&mut rng)
+        .sample_iter(Standard)
+        .take(n)
+        .collect::<Vec<i64>>();
+    v.shuffle(&mut rng);
     partially_sort(&mut v[..]);
     b.iter(|| {
         let mut v2 = v.clone();
@@ -120,26 +132,26 @@ fn sort_partially_sorted(b: &mut Bencher) {
 
 #[bench]
 fn sort_strings(b: &mut Bencher) {
-    let mut rng = weak_rng();
+    let mut rng = rng();
     let n = 10_000usize;
     let mut v = Vec::with_capacity(n);
     let mut bytes = 0;
-    for _ in (0 .. n) {
-        let len = rng.gen_range(0, 60);
+    for _ in 0..n {
+        let len = rng.gen_range(0..=60);
         bytes += len;
         let mut s = String::with_capacity(len);
         if len == 0 {
             v.push(s);
             continue;
         }
-        for _ in (0 .. len) {
-            s.push(rng.gen_range(b'a', b'z') as char);
+        for _ in 0..len {
+            s.push(rng.gen_range(b'a'..=b'z') as char);
         }
         v.push(s);
     }
 
     b.iter(|| {
-        rng.shuffle(&mut v[..]);
+        v.shuffle(&mut rng);
         sort(&mut v[..]);
     });
     b.bytes = bytes as u64;

diff --git a/benches/bench_default.rs b/benches/bench_default.rs
@@ -3,28 +3,30 @@
 #![feature(test)]
 #![feature(unboxed_closures)]
 
-extern crate timsort;
 extern crate test;
-extern crate rand;
 
-use rand::{weak_rng, Rng};
+use rand::{distributions::Standard, rngs::SmallRng, seq::SliceRandom, Rng, SeedableRng};
 use std::mem;
 use test::Bencher;
 
+fn rng() -> impl Rng {
+    SmallRng::from_entropy()
+}
+
 #[inline]
 fn sort<T: Ord>(l: &mut [T]) {
     l.sort();
 }
 
-type BigSortable = (u64,u64,u64,u64);
+type BigSortable = (u64, u64, u64, u64);
 
 macro_rules! bench_random(
     ($name: ident, $sortfun: ident, $typ: ty, $n: expr) => (
         #[bench]
         fn $name(b: &mut Bencher) {
-            let mut rng = weak_rng();
+            let mut rng = rng();
             b.iter(|| {
-                let mut v = rng.gen_iter::<$typ>().take($n).collect::<Vec<$typ>>();
+                let mut v = (&mut rng).sample_iter(Standard).take($n).collect::<Vec<$typ>>();
                 $sortfun(&mut v[..]);
             });
             b.bytes = $n * mem::size_of::<$typ>() as u64;
@@ -46,7 +48,7 @@ bench_random!(sort_big_random_large, sort, BigSortable, 10_000);
 
 #[bench]
 fn sort_sorted(b: &mut Bencher) {
-    let mut v: Vec<_> = (0 .. 10000isize).collect();
+    let mut v: Vec<_> = (0..10000isize).collect();
     b.iter(|| {
         sort(&mut v[..]);
     });
@@ -55,7 +57,7 @@ fn sort_sorted(b: &mut Bencher) {
 
 #[bench]
 fn sort_big_sorted(b: &mut Bencher) {
-    let mut v: Vec<_> = (0 .. 10000usize).map(|i| (i, i, i, i)).collect();
+    let mut v: Vec<_> = (0..10000usize).map(|i| (i, i, i, i)).collect();
     b.iter(|| {
         sort(&mut v[..]);
     });
@@ -65,14 +67,14 @@ fn sort_big_sorted(b: &mut Bencher) {
 #[bench]
 fn sort_few_unique(b: &mut Bencher) {
     let mut v = Vec::new();
-    for i in (0u32 .. 10) {
-        for _ in (0usize .. 100) {
+    for i in 0u32..10 {
+        for _ in 0usize..100 {
             v.push(i);
         }
     }
-    let mut rng = weak_rng();
-    b.iter(||{
-        rng.shuffle(&mut v[..]);
+    let mut rng = rng();
+    b.iter(|| {
+        v.shuffle(&mut rng);
         sort(&mut v[..]);
     });
     b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;
@@ -89,31 +91,41 @@ fn sort_equals(b: &mut Bencher) {
 
 #[bench]
 fn sort_huge(b: &mut Bencher) {
-    let mut rng = weak_rng();
+    let mut rng = rng();
     let n = 100_000;
-    let mut v = rng.gen_iter::<i64>().take(n).collect::<Vec<i64>>();
+    let mut v = (&mut rng)
+        .sample_iter(Standard)
+        .take(n)
+        .collect::<Vec<i64>>();
     b.iter(|| {
-        rng.shuffle(&mut v[..]);
+        v.shuffle(&mut rng);
         sort(&mut v[..]);
     });
     b.bytes = (n * mem::size_of::<i64>()) as u64;
 }
 
 #[bench]
 fn sort_partially_sorted(b: &mut Bencher) {
-    fn partially_sort<T: Ord+::std::fmt::Display>(v: &mut [T]) {
+    fn partially_sort<T: Ord + ::std::fmt::Display>(v: &mut [T]) {
         let s = v.len() / 100;
-        if s == 0 { return; }
+        if s == 0 {
+            return;
+        }
         let mut sorted = true;
         for c in v.chunks_mut(s) {
-            if sorted { sort(&mut c[..]); }
+            if sorted {
+                sort(&mut c[..]);
+            }
             sorted = !sorted;
         }
     }
-    let mut rng = weak_rng();
+    let mut rng = rng();
     let n = 10_000;
-    let mut v = rng.gen_iter::<i64>().take(n).collect::<Vec<i64>>();
-    rng.shuffle(&mut v[..]);
+    let mut v = (&mut rng)
+        .sample_iter(Standard)
+        .take(n)
+        .collect::<Vec<i64>>();
+    v.shuffle(&mut rng);
     partially_sort(&mut v[..]);
     b.iter(|| {
         let mut v2 = v.clone();
@@ -124,26 +136,26 @@ fn sort_partially_sorted(b: &mut Bencher) {
 
 #[bench]
 fn sort_strings(b: &mut Bencher) {
-    let mut rng = weak_rng();
+    let mut rng = rng();
     let n = 10_000usize;
     let mut v = Vec::with_capacity(n);
     let mut bytes = 0;
-    for _ in (0 .. n) {
-        let len = rng.gen_range(0, 60);
+    for _ in 0..n {
+        let len = rng.gen_range(0..=60);
         bytes += len;
         let mut s = String::with_capacity(len);
         if len == 0 {
             v.push(s);
             continue;
         }
-        for _ in (0 .. len) {
-            s.push(rng.gen_range(b'a', b'z') as char);
+        for _ in 0..len {
+            s.push(rng.gen_range(b'a'..=b'z') as char);
         }
         v.push(s);
     }
 
     b.iter(|| {
-        rng.shuffle(&mut v[..]);
+        v.shuffle(&mut rng);
         sort(&mut v[..]);
     });
     b.bytes = bytes as u64;