use crate::core::util::error::lucene_error::{LuceneError, Result};
pub trait Sorter {
fn compare(&mut self, _i: usize, _j: usize) -> Result<i32> {
Err(LuceneError::illegal_state(
"compare() must be implemented if it needs to be used",
))
}
fn swap(&mut self, _i: usize, _j: usize) -> Result<()> {
Err(LuceneError::illegal_state(
"swap() must be implemented if it needs to be used",
))
}
fn set_pivot(&mut self, _i: usize) -> Result<()> {
Err(LuceneError::illegal_state(
"set_pivot() must be implemented if it needs to be used",
))
}
fn compare_pivot(&mut self, _i: usize) -> Result<i32> {
Err(LuceneError::illegal_state(
"compare_pivot() must be implemented if it needs to be used",
))
}
fn sort(&mut self, _from: usize, _to: usize) -> Result<()> {
Err(LuceneError::illegal_state(
"sort() must be implemented if it needs to be used",
))
}
fn merge_in_place(&mut self, mut from: usize, mid: usize, mut to: usize) -> Result<()> {
if from == mid || mid == to || self.compare(mid - 1, mid)? <= 0 {
return Ok(());
} else if to == 2 + from {
self.swap(mid - 1, mid)?;
return Ok(());
}
while self.compare(from, mid)? <= 0 {
from += 1;
}
while self.compare(mid - 1, to - 1)? <= 0 {
to -= 1;
}
let (first_cut, second_cut, _len11, len22) = if mid - from > to - mid {
let len11 = (mid - from) >> 1;
let first_cut = from + len11;
let second_cut = self.lower(mid, to, first_cut)?;
let len22 = second_cut - mid;
(first_cut, second_cut, len11, len22)
} else {
let len22 = (to - mid) >> 1;
let second_cut = mid + len22;
let first_cut = self.upper(from, mid, second_cut)?;
let len11 = first_cut - from;
(first_cut, second_cut, len11, len22)
};
self.rotate(first_cut, mid, second_cut)?;
let new_mid = first_cut + len22;
self.merge_in_place(from, first_cut, new_mid)?;
self.merge_in_place(new_mid, second_cut, to)?;
Ok(())
}
fn lower(&mut self, mut from: usize, to: usize, val: usize) -> Result<usize> {
let mut len = to - from;
while len > 0 {
let half = len >> 1;
let mid = from + half;
if self.compare(mid, val)? < 0 {
from = mid + 1;
len = len - half - 1;
} else {
len = half;
}
}
Ok(from)
}
fn upper(&mut self, mut from: usize, to: usize, val: usize) -> Result<usize> {
let mut len = to - from;
while len > 0 {
let half = len >> 1;
let mid = from + half;
if self.compare(val, mid)? < 0 {
len = half;
} else {
from = mid + 1;
len = len - half - 1;
}
}
Ok(from)
}
fn lower2(&mut self, from: usize, to: usize, val: usize) -> Result<usize> {
let mut f = to.saturating_sub(1);
let mut t = to;
while f > from {
if self.compare(f, val)? < 0 {
return self.lower(f, t, val);
}
let delta = t - f;
t = f;
f = f.saturating_sub(delta << 1);
}
self.lower(from, t, val)
}
fn upper2(&mut self, from: usize, to: usize, val: usize) -> Result<usize> {
let mut f = from as i32;
let mut t = f + 1;
while t < to as i32 {
if self.compare(t as usize, val)? > 0 {
return self.upper(f as usize, t as usize, val);
}
let delta = t - f;
f = t;
t += delta << 1;
}
self.upper(f as usize, to, val)
}
fn reverse(&mut self, mut from: usize, to: usize) -> Result<()> {
let mut to = to.checked_sub(1);
while let Some(last) = to {
if from >= last {
break;
}
self.swap(from, last)?;
from += 1;
to = last.checked_sub(1);
}
Ok(())
}
fn rotate(&mut self, lo: usize, mid: usize, hi: usize) -> Result<()> {
debug_assert!(lo <= mid && mid <= hi);
if lo == mid || mid == hi {
return Ok(());
}
self.do_rotate(lo, mid, hi)
}
fn do_rotate(&mut self, mut lo: usize, mut mid: usize, hi: usize) -> Result<()> {
if mid + mid == hi + lo {
while mid < hi {
self.swap(lo, mid)?;
lo += 1;
mid += 1;
}
} else {
self.reverse(lo, mid)?;
self.reverse(mid, hi)?;
self.reverse(lo, hi)?;
}
Ok(())
}
fn binary_sort(&mut self, from: usize, to: usize) -> Result<()> {
self.binary_sort_with_start(from, to, from + 1)
}
fn binary_sort_with_start(&mut self, from: usize, to: usize, mut i: usize) -> Result<()> {
while i < to {
self.set_pivot(i)?;
let mut l = from;
let mut h = i;
while l < h {
let mid = l + ((h - l - 1) >> 1);
let cmp = self.compare_pivot(mid)?;
if cmp < 0 {
h = mid;
} else {
l = mid + 1;
}
}
let mut j = i;
while j > l {
self.swap(j - 1, j)?;
j -= 1;
}
i += 1;
}
Ok(())
}
fn insertion_sort(&mut self, from: usize, to: usize) -> Result<()> {
let mut i = from + 1;
while i < to {
let mut current = i;
i += 1;
loop {
let previous = current - 1;
if self.compare(previous, current)? > 0 {
self.swap(previous, current)?;
if previous == from {
break;
}
current = previous;
} else {
break;
}
}
}
Ok(())
}
fn heap_sort(&mut self, from: usize, to: usize) -> Result<()> {
if to <= from || to - from <= 1 {
return Ok(());
}
self.heapify(from, to)?;
let mut end = to - 1;
while end > from {
self.swap(from, end)?;
self.sift_down(from, from, end)?;
end -= 1;
}
Ok(())
}
fn heapify(&mut self, from: usize, to: usize) -> Result<()> {
for i in (from..=Self::heap_parent(from, to - 1)).rev() {
self.sift_down(i, from, to)?;
}
Ok(())
}
fn sift_down(&mut self, mut i: usize, from: usize, to: usize) -> Result<()> {
let mut left_child = Self::heap_child(from, i);
while left_child < to {
let right_child = left_child + 1;
if self.compare(i, left_child)? < 0 {
if right_child < to && self.compare(left_child, right_child)? < 0 {
self.swap(i, right_child)?;
i = right_child;
} else {
self.swap(i, left_child)?;
i = left_child;
}
} else if right_child < to && self.compare(i, right_child)? < 0 {
self.swap(i, right_child)?;
i = right_child;
} else {
break;
}
left_child = Self::heap_child(from, i);
}
Ok(())
}
fn heap_parent(from: usize, i: usize) -> usize {
((i - 1 - from) >> 1) + from
}
fn heap_child(from: usize, i: usize) -> usize {
((i - from) << 1) + 1 + from
}
}
pub fn check_range(from: usize, to: usize) -> Result<()> {
if to < from {
return Err(LuceneError::illegal_argument(format!(
"'to' must be >= 'from', got from= {from} and to= {to}"
)));
}
Ok(())
}
pub(crate) const BINARY_SORT_THRESHOLD: usize = 20;
pub(crate) const INSERTION_SORT_THRESHOLD: usize = 16;