/// Bucket sort
///
/// * `arr` - Collection of value to be sorted in place.
/// * `hasher` - Function hashing to map elements to correspoding buckets.
///
/// Ref: https://codereview.stackexchange.com/a/145124
pub fn bucket_sort<H, F, T>(arr: &mut [T], hasher: F)
where
    H: Ord,
    F: Fn(&T) -> H,
    T: Ord + Clone,
{
    // 1. Create buckets.
    let mut buckets: Vec<Bucket<H, T>> = Vec::new();

    // 2. Iterate all elements.
    for value in arr.iter() {
        // 2.1 Create hasher mapping to certain bucket.
        let hash = hasher(&value);

        // 2.2 Search if the bucket with same hash exists.
        let value = value.clone();
        match buckets.binary_search_by(|bucket| bucket.hash.cmp(&hash)) {
            // If exists, push the value to the bucket.
            Ok(index) => buckets[index].values.push(value),
            // If none, create and new bucket and insert value in.
            Err(index) => buckets.insert(index, Bucket::new(hash, value)),
        }
    }

    // 3. Iterate all buckets and flatten their internal collections.
    let ret = buckets
        .into_iter()
        .flat_map(|mut bucket| {
            bucket.values.sort(); // We use built-in sorting here.
            bucket.values
        })
        .collect::<Vec<T>>();

    // 4. Clone back to original array.
    arr.clone_from_slice(&ret);
}

/// Bucket to store elements.
struct Bucket<H, T> {
    hash: H,
    values: Vec<T>,
}

impl<H, T> Bucket<H, T> {
    /// Create a new bucket and insert its first value.
    ///
    /// * `hash` - Hash value generated by hasher param of `bucket_sort`.
    /// * `value` - Value to be put in the bucket.
    pub fn new(hash: H, value: T) -> Bucket<H, T> {
        Bucket {
            hash,
            values: vec![value],
        }
    }
}

#[cfg(test)]
mod base {
    use super::*;
    fn bucket_sort_(arr: &mut [i32]) {
        bucket_sort(arr, |int| int / 4);
    }
    base_cases!(bucket_sort_);
}

#[cfg(test)]
mod stability {
    use super::*;
    fn bucket_sort_(arr: &mut [(i32, i32)]) {
        bucket_sort(arr, |t| t.0 / 4);
    }
    stability_cases!(bucket_sort_);
}