use super::ASCII_SIZE;
pub struct Sorting;
const INSERTION_CUTOFF: usize = 15;
fn char_at(s: &str, d: usize) -> i16 {
debug_assert!(d <= s.len());
if d == s.len() {
return -1;
}
s.as_bytes()[d] as i16
}
fn insertion(arr: &mut [&str], d: usize) {
for i in 0..arr.len() {
let mut j = i;
while j > 0 && less(arr[j], arr[j - 1], d) {
arr.swap(j, j - 1);
j -= 1;
}
}
}
fn less(v: &str, w: &str, d: usize) -> bool {
debug_assert_eq!(&v[0..d], &w[0..d]);
let v_bytes = v.as_bytes();
let w_bytes = w.as_bytes();
for i in d..(v.len().min(w.len())) {
if v_bytes[i] < w_bytes[i] {
return true;
}
if v_bytes[i] > w_bytes[i] {
return false;
}
}
v.len() < w.len()
}
fn msd_sort<'a>(arr: &mut [&'a str], d: usize, aux: &mut [&'a str]) {
if arr.len() <= INSERTION_CUTOFF {
insertion(arr, d);
return;
}
let mut count = vec![0; ASCII_SIZE + 2];
for str in arr.iter() {
count[char_at(str, d) as usize + 2] += 1;
}
for r in 0..(ASCII_SIZE + 1) {
count[r + 1] += count[r];
}
for str in arr.iter() {
let char = char_at(str, d) as usize + 1;
aux[count[char]] = str;
count[char] += 1;
}
arr.copy_from_slice(&aux[..arr.len()]);
for r in 0..ASCII_SIZE {
msd_sort(
&mut arr[count[r]..(count[r + 1] - 1)],
d + 1,
&mut aux[count[r]..(count[r + 1] - 1)],
);
}
}
fn quick_3_sort(arr: &mut [&str], d: usize) {
if arr.len() <= INSERTION_CUTOFF {
insertion(arr, d);
return;
}
let hi = arr.len();
let (mut lt, mut gt) = (0, hi);
let v = char_at(arr[0], d);
let mut i = 1;
while i <= gt {
let t = char_at(arr[i], d);
if t < v {
arr.swap(lt, i);
lt += 1;
i += 1;
} else if t > v {
arr.swap(i, gt);
gt -= 1;
} else {
i += 1;
}
}
quick_3_sort(&mut arr[0..(lt - 1)], d);
if v >= 0 {
quick_3_sort(&mut arr[lt..gt], d + 1);
}
quick_3_sort(&mut arr[(gt + 1)..hi], d);
}
impl Sorting {
pub fn lsd_sort(arr: &mut [&str]) {
if arr.is_empty() {
return;
}
let mut aux = vec![None; arr.len()];
let str_len = arr[0].len(); for d in (0..str_len).rev() {
let mut count = vec![0; ASCII_SIZE + 1];
for str in arr.iter() {
let char = str.as_bytes()[d] as usize;
count[char + 1] += 1;
}
for r in 0..ASCII_SIZE {
count[r + 1] += count[r];
}
for str in arr.iter() {
let char = str.as_bytes()[d] as usize;
aux[count[char]] = Some(*str);
count[char] += 1;
}
for i in 0..arr.len() {
arr[i] = aux[i].unwrap();
}
}
}
pub fn msd_sort(arr: &mut [&str]) {
let mut aux = arr.to_vec();
msd_sort(arr, 0, &mut aux);
}
pub fn quick_3_way_sort(arr: &mut [&str]) {
quick_3_sort(arr, 0);
}
}