use crate::core::util::error::lucene_error::Result;
use crate::core::util::intro_sorter::IntroSorter;
use crate::core::util::{Comparator, NaturalOrder, Sorter, TimSorter, TimSorterBase};
use std::collections::HashMap;
pub struct CollectionUtil;
impl CollectionUtil {
#[allow(dead_code)]
pub fn new_hashmap<K, V>(size: usize) -> HashMap<K, V> {
let capacity = ((size as f32) / 0.75f32 + 1f32) as usize;
HashMap::with_capacity(capacity)
}
pub fn intro_sort_with_comparator<T, C>(list: &mut [T], comp: C) -> Result<()>
where
C: Comparator<T>,
{
let size = list.len();
if size <= 1 {
return Ok(());
}
ListIntroSorter::new(list, comp).sort(0, size)?;
Ok(())
}
pub fn intro_sort<T>(list: &mut [T]) -> Result<()>
where
T: Ord,
{
let size = list.len();
if size <= 1 {
return Ok(());
}
Self::intro_sort_with_comparator(list, NaturalOrder::new())
}
pub fn tim_sort_with_comparator<T, C>(list: &mut [T], comp: C) -> Result<()>
where
C: Comparator<T>,
T: Copy,
{
let size = list.len();
if size <= 1 {
return Ok(());
}
ListTimSorter::new(list, comp, size / 64).sort(0, size)?;
Ok(())
}
pub fn tim_sort<T>(list: &mut [T]) -> Result<()>
where
T: Copy + Ord,
{
let size = list.len();
if size <= 1 {
return Ok(());
}
Self::tim_sort_with_comparator(list, NaturalOrder::new())
}
}
struct ListTimSorter<'a, T, C> {
arr: &'a mut [T],
tmp: Vec<T>,
max_temp_slots: usize,
comp: C,
pivot: usize,
}
impl<'a, T, C: Comparator<T>> ListTimSorter<'a, T, C>
where
T: Copy,
{
pub fn new(
arr: &'a mut [T],
comp: C,
max_temp_slots: usize,
) -> TimSorter<ListTimSorter<'a, T, C>> {
let sub = ListTimSorter {
arr,
tmp: Vec::new(),
max_temp_slots,
comp,
pivot: 0,
};
TimSorter::new(max_temp_slots, sub)
}
}
impl<T, C: Comparator<T>> Sorter for ListTimSorter<'_, T, C>
where
T: Copy,
{
fn compare(&mut self, i: usize, j: usize) -> Result<i32> {
self.comp.compare(&self.arr[i], &self.arr[j])
}
fn swap(&mut self, i: usize, j: usize) -> Result<()> {
self.arr.swap(i, j);
Ok(())
}
fn set_pivot(&mut self, i: usize) -> Result<()> {
self.pivot = i;
Ok(())
}
fn compare_pivot(&mut self, j: usize) -> Result<i32> {
self.compare(self.pivot, j)
}
}
impl<T, C: Comparator<T>> TimSorterBase for ListTimSorter<'_, T, C>
where
T: Copy,
{
fn copy(&mut self, src: usize, dest: usize) -> Result<()> {
self.arr[dest] = self.arr[src];
Ok(())
}
fn save(&mut self, start: usize, len: usize) -> Result<()> {
self.tmp.clear();
if self.tmp.capacity() == 0 {
self.tmp.reserve_exact(self.max_temp_slots);
}
self.tmp.extend_from_slice(&self.arr[start..start + len]);
Ok(())
}
fn restore(&mut self, src: usize, dest: usize) {
self.arr[dest] = self.tmp[src];
}
fn compare_saved(&self, i: usize, j: usize) -> Result<i32> {
self.comp.compare(&self.tmp[i], &self.arr[j])
}
}
struct ListIntroSorter<'a, T, C> {
pub list: &'a mut [T],
comp: C,
pivot: usize,
}
impl<'a, T, C> ListIntroSorter<'a, T, C> {
pub fn new(list: &'a mut [T], comp: C) -> ListIntroSorter<'a, T, C> {
ListIntroSorter {
list,
comp,
pivot: 0,
}
}
}
impl<T, C: Comparator<T>> Sorter for ListIntroSorter<'_, T, C> {
fn compare(&mut self, i: usize, j: usize) -> Result<i32> {
self.comp.compare(&self.list[i], &self.list[j])
}
fn swap(&mut self, i: usize, j: usize) -> Result<()> {
if self.pivot == i || self.pivot == j {
self.pivot = if self.pivot == i { j } else { i };
}
self.list.swap(i, j);
Ok(())
}
fn set_pivot(&mut self, i: usize) -> Result<()> {
self.pivot = i;
Ok(())
}
fn compare_pivot(&mut self, i: usize) -> Result<i32> {
self.comp.compare(&self.list[self.pivot], &self.list[i])
}
fn sort(&mut self, from: usize, to: usize) -> Result<()> {
IntroSorter::sort_range(self, from, to)?;
Ok(())
}
}
impl<T, C: Comparator<T>> IntroSorter for ListIntroSorter<'_, T, C> {}