sp-im 0.3.0

// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.

use crate::vector::FocusMut;
use rand_core::{
  RngCore,
  SeedableRng,
};
use core::{
  cmp::Ordering,
  mem,
};

fn gen_range<R: RngCore>(rng: &mut R, min: usize, max: usize) -> usize {
  let range = max - min;
  min + (rng.next_u64() as usize % range)
}

// Ported from the Java version at:
//    http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf
// There are a couple of modifications made here to make it more performant on
// the tree structure of the Vector. Instead of moving of handling equal and
// nonequal items in a single pass we make two additional passes to find the
// exact partition places. This allows us to split the focus into
// three correctly sized parts for less than, equal to and greater than items.
// As a bonus this doesn't need to reorder the equal items to the center of the
// vector.
fn do_quicksort<A, F, R>(vector: FocusMut<'_, A>, cmp: &F, rng: &mut R)
where
  A: Clone,
  F: Fn(&A, &A) -> Ordering,
  R: RngCore, {
  if vector.len() <= 1 {
    return;
  }

  // We know there are at least 2 elements here
  let pivot_index = gen_range(rng, 0, vector.len());
  let (mut first, mut rest) = vector.split_at(1);

  if pivot_index > 0 {
    mem::swap(rest.index_mut(pivot_index - 1), first.index_mut(0));
  }
  // Pivot is now always in the first slice
  let pivot_item = first.index(0);

  // Find the exact place to put the pivot or pivot-equal items
  let mut less_count = 0;
  let mut equal_count = 0;

  for index in 0..rest.len() {
    let item = rest.index(index);
    let comp = cmp(item, pivot_item);
    match comp {
      Ordering::Less => less_count += 1,
      Ordering::Equal => equal_count += 1,
      Ordering::Greater => {}
    }
  }

  // If by accident we picked the minimum element as a pivot, we just call sort
  // again with the rest of the vector.
  if less_count == 0 {
    do_quicksort(rest, cmp, rng);
    return;
  }

  // We know here that there is at least one item before the pivot, so we move
  // the minimum to the beginning part of the vector. First, however we swap
  // the pivot to the start of the equal zone.
  less_count -= 1;
  equal_count += 1;
  let first_item = first.index_mut(0);
  mem::swap(first_item, rest.index_mut(less_count));
  for index in 0..rest.len() {
    if index == less_count {
      // This is the position we swapped the pivot to. We can't move it from its
      // position, and we know its not the minimum.
      continue;
    }
    let rest_item = rest.index_mut(index);
    if cmp(rest_item, first_item) == Ordering::Less {
      mem::swap(first_item, rest_item);
    }
  }

  // Split the vector up into less_than, equal to and greater than parts.
  let (remaining, mut greater_focus) = rest.split_at(less_count + equal_count);
  let (mut less_focus, mut equal_focus) = remaining.split_at(less_count);

  let mut less_position = 0;
  let mut equal_position = 0;
  let mut greater_position = 0;

  while less_position != less_focus.len()
    || greater_position != greater_focus.len()
  {
    // At start of this loop, equal_position always points to an equal item
    let mut equal_swap_side = None;
    let equal_item = equal_focus.index(equal_position);

    // Advance the less_position until we find an out of place item
    while less_position != less_focus.len() {
      let less_item = less_focus.index(less_position);
      match cmp(less_item, equal_item) {
        Ordering::Equal => {
          equal_swap_side = Some(Ordering::Less);
          break;
        }
        Ordering::Greater => {
          break;
        }
        _ => {}
      }
      less_position += 1;
    }

    // Advance the greater until we find an out of place item
    while greater_position != greater_focus.len() {
      let greater_item = greater_focus.index(greater_position);
      match cmp(greater_item, equal_item) {
        Ordering::Less => break,
        Ordering::Equal => {
          equal_swap_side = Some(Ordering::Greater);
          break;
        }
        _ => {}
      }
      greater_position += 1;
    }

    if let Some(swap_side) = equal_swap_side {
      // One of the sides is equal to the pivot, advance the pivot
      let item = if swap_side == Ordering::Less {
        less_focus.index_mut(less_position)
      }
      else {
        greater_focus.index_mut(greater_position)
      };

      // We are guaranteed not to hit the end of the equal focus
      while cmp(item, equal_focus.index(equal_position)) == Ordering::Equal {
        equal_position += 1;
      }

      // Swap the equal position and the desired side, it's important to note
      // that only the equals focus is guaranteed to have made progress so
      // we don't advance the side's index
      mem::swap(item, equal_focus.index_mut(equal_position));
    }
    else if less_position != less_focus.len()
      && greater_position != greater_focus.len()
    {
      // Both sides are out of place and not equal to the pivot, this can only
      // happen if there is a greater item in the lesser zone and a lesser
      // item in the greater zone. The solution is to swap both sides and
      // advance both side's indices.
      debug_assert_ne!(
        cmp(less_focus.index(less_position), equal_focus.index(equal_position)),
        Ordering::Equal
      );
      debug_assert_ne!(
        cmp(
          greater_focus.index(greater_position),
          equal_focus.index(equal_position)
        ),
        Ordering::Equal
      );
      mem::swap(
        less_focus.index_mut(less_position),
        greater_focus.index_mut(greater_position),
      );
      less_position += 1;
      greater_position += 1;
    }
  }

  // Now we have partitioned both sides correctly, we just have to recurse now
  do_quicksort(less_focus, cmp, rng);
  if !greater_focus.is_empty() {
    do_quicksort(greater_focus, cmp, rng);
  }
}

pub(crate) fn quicksort<A, F>(vector: FocusMut<'_, A>, cmp: &F)
where
  A: Clone,
  F: Fn(&A, &A) -> Ordering, {
  let mut rng = rand_xoshiro::Xoshiro256Plus::seed_from_u64(0);
  do_quicksort(vector, cmp, &mut rng);
}

#[cfg(test)]
mod test {
  use super::*;
  use crate::{
    test::is_sorted,
    vector::Vector,
  };

  quickcheck! {
    fn test_quicksort(input: Vector<i32>) -> bool {
      let mut vec = input.clone();
      let len = vec.len();
      if len > 1 {
        quicksort(vec.focus_mut(), &Ord::cmp);
      }
      is_sorted(vec)
    }
  }
}