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
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

use std::iter::ExactSizeIterator;
use std::thread;
use std::sync::mpsc;
use std::time::Duration;
use std::num::Wrapping;

/// This trait provides  the `sleepsort` functionality
pub trait Sleepsort: IntoIterator + Sized
    where
        Self::Item: SleepsortItem + PartialOrd + Send + 'static
{
    /// **Sleepsort** is an unstable time-based variation of **Countingsort** that
    /// works by assigning every value to a thread and putting that thread to sleep
    /// for a time that is determined by that value:
    ///
    /// ```text
    /// for i in values:
    ///     spawn a thread that sleeps i seconds
    ///     output i
    /// ```
    ///
    /// Unlike many other implementations, this one does not just print the values in
    /// order, but actually collects them, and is able to sort negative signed
    /// integers. Using it for other types is easily possible by simply implementing
    /// the [`SleepsortItem`] trait.
    fn sleepsort(self) -> SleepsortIter<Self::Item> {
        self.sleepsort_with_speed(SleepsortSpeed::Default)
    }

    /// [`sleepsort`](Sleepsort::sleepsort) with a custom speed. See
    /// [`SleepsortSpeed`] for more information.
    fn sleepsort_with_speed(self, speed: SleepsortSpeed)
        -> SleepsortIter<Self::Item>
    {
        let buffer: Vec<_> = self.into_iter().collect();
        let len = buffer.len();
        let (tx, rx) = mpsc::sync_channel(len);

        for item in buffer {
            let tx = tx.clone();
            thread::spawn(move || {
                thread::sleep(speed.adjust_duration(item.key()));
                tx.send(item).unwrap();
            });
        }

        SleepsortIter { rx: rx.into_iter(), len }
    }
}

/// Marks a trait that can be [`sleepsort`](Sleepsort::sleepsort)ed.
pub trait SleepsortItem: PartialOrd + Send + 'static {
    /// Determine how long the thread should sleep for this particular value.
    fn key(&self) -> Duration;
}

/// An iterator over a [`sleepsort`](Sleepsort::sleepsort)ed collection.
#[derive(Debug)]
pub struct SleepsortIter<I> {
    rx: mpsc::IntoIter<I>,
    len: usize
}

/// Adjusts how long [`sleepsort`](Sleepsort::sleepsort) threads sleep.
#[derive(Copy, Clone, Debug)]
pub enum SleepsortSpeed {
    /// Do not change sleep duration.
    Default,

    /// Shorten sleep duration by dividing it by the given value. Too short
    /// durations will cause incorrect results.
    Faster(u32),

    /// Lengthen sleep duration by multiplying it with the given value. Use this if
    /// incorrect results are produced.
    Slower(u32)
}


impl<T> Sleepsort for T
    where
        T: IntoIterator + Sized,
        T::Item: SleepsortItem + PartialOrd + Send + 'static
{}

impl SleepsortItem for u8 {
    fn key(&self) -> Duration {
        Duration::from_secs(u64::from(*self))
    }
}

impl SleepsortItem for u16 {
    fn key(&self) -> Duration {
        Duration::from_secs(u64::from(*self))
    }
}

impl SleepsortItem for u32 {
    fn key(&self) -> Duration {
        Duration::from_secs(u64::from(*self))
    }
}

impl SleepsortItem for u64 {
    fn key(&self) -> Duration {
        Duration::from_secs(*self)
    }
}

impl SleepsortItem for i8 {
    fn key(&self) -> Duration {
        let Wrapping(seconds) =
            Wrapping(*self as u8) + Wrapping(i8::max_value() as u8 + 1);
        Duration::from_secs(u64::from(seconds))
    }
}

impl SleepsortItem for i16 {
    fn key(&self) -> Duration {
        let Wrapping(seconds) =
            Wrapping(*self as u16) + Wrapping(i16::max_value() as u16 + 1);
        Duration::from_secs(u64::from(seconds))
    }
}

impl SleepsortItem for i32 {
    fn key(&self) -> Duration {
        let Wrapping(seconds) =
            Wrapping(*self as u32) + Wrapping(i32::max_value() as u32 + 1);
        Duration::from_secs(u64::from(seconds))
    }
}

impl SleepsortItem for i64 {
    fn key(&self) -> Duration {
        let Wrapping(seconds) =
            Wrapping(*self as u64) + Wrapping(i64::max_value() as u64 + 1);
        Duration::from_secs(seconds)
    }
}

impl<I> Iterator for SleepsortIter<I>
    where
        I: SleepsortItem
{
    type Item = I;

    fn next(&mut self) -> Option<Self::Item> {
        self.rx.next()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.len();
        (len, Some(len))
    }
}

impl<I> ExactSizeIterator for SleepsortIter<I>
    where
    I: SleepsortItem
{
    fn len(&self) -> usize {
        self.len
    }
}


impl SleepsortSpeed {
    fn adjust_duration(self, dur: Duration) -> Duration {
        use SleepsortSpeed::*;

        match self {
            Default => dur,
            Faster(div) => dur / div,
            Slower(mul) => dur * mul
        }
    }
}