use std::cmp::Ordering;
use crate::core::util::array_tim_sorter::ArrayTimSorter;
use crate::core::util::bit_util::BitUtil;
use crate::core::util::bkd::BKDUtil;
use crate::core::util::error::lucene_error::{LuceneError, Result};
use crate::core::util::selector::Selector;
use crate::core::util::{
ArrayIntroSorter, Comparator, IntroSelector, IntroSelectorBase, IntroSelectorBaseDefault,
NaturalOrder, Sorter, ToInt,
};
pub struct ArrayUtil;
impl ArrayUtil {
pub const MAX_ARRAY_LENGTH: usize = i32::MAX as usize;
const MIN_RADIX: i32 = 2;
const MAX_RADIX: i32 = 36;
pub fn parse_int_default(chars: &[char], offset: usize, len: usize) -> Result<i32> {
Self::parse_int(chars, offset, len, 10)
}
pub fn parse_int(chars: &[char], mut offset: usize, mut len: usize, radix: i32) -> Result<i32> {
if !(ArrayUtil::MIN_RADIX..=ArrayUtil::MAX_RADIX).contains(&radix) {
return Err(LuceneError::number_format("Invalid radix"));
}
if len == 0 {
return Err(LuceneError::number_format("chars length is 0"));
}
let mut i = 0;
let negative = chars[offset + i] == '-';
if negative {
i += 1;
if i == len {
return Err(LuceneError::number_format("chars length is 0"));
}
}
if negative {
offset += 1;
len -= 1;
}
Self::parse(chars, offset, len, radix, negative)
}
pub fn parse(
chars: &[char],
offset: usize,
len: usize,
radix: i32,
negative: bool,
) -> Result<i32> {
let max = i32::MIN / radix;
let mut result = 0;
for i in 0..len {
let digit = chars[offset + i]
.to_digit(radix as u32)
.ok_or_else(|| LuceneError::number_format("Unable to parse"))?;
if max > result {
return Err(LuceneError::number_format("Unable to parse"));
}
let next = result
.checked_mul(radix)
.and_then(|x| x.checked_sub(digit as i32));
match next {
Some(next) => {
if next > result {
return Err(LuceneError::number_format("Unable to parse"));
}
result = next;
},
None => return Err(LuceneError::number_format("Unable to parse")),
}
}
if !negative {
result = -result;
if result < 0 {
return Err(LuceneError::number_format("Unable to parse"));
}
}
Ok(result)
}
#[inline]
pub fn oversize(min_target_size: usize, bytes_per_element: usize) -> Result<usize> {
if min_target_size == 0 {
return Ok(0);
}
let max_array_length = (isize::MAX as usize)
.checked_div(bytes_per_element)
.map(|v| Self::MAX_ARRAY_LENGTH.min(v))
.unwrap_or(Self::MAX_ARRAY_LENGTH);
if min_target_size > max_array_length {
return Err(LuceneError::illegal_argument(format!(
"requested vector size {min_target_size} exceeds maximum vector length \
{max_array_length} for elements of {bytes_per_element} bytes"
)));
}
let mut extra = min_target_size >> 3;
if extra < 3 {
extra = 3;
}
Ok(
min_target_size
.checked_add(extra)
.unwrap_or(max_array_length)
.min(max_array_length),
)
}
pub fn grow_exact<T, F>(vec: &mut Vec<T>, new_length: usize, init: F) -> Result<()>
where
F: FnMut() -> T,
{
let current_length = vec.len();
match new_length.cmp(¤t_length) {
Ordering::Greater => {
vec.reserve_exact(new_length - current_length);
vec.resize_with(new_length, init);
},
Ordering::Equal => {
return Ok(());
},
Ordering::Less => {
return Err(LuceneError::array_index_out_of_bounds(format!(
"new_length: {new_length} is less than current_length: {current_length}"
)));
},
}
Ok(())
}
pub fn grow_capacity<T>(vec: &mut Vec<T>, min_size: usize) -> Result<()> {
Self::oversize(min_size, size_of::<T>())?;
vec.reserve(min_size.saturating_sub(vec.len()));
Ok(())
}
pub fn grow_with<T, F>(vec: &mut Vec<T>, min_size: usize, init: F) -> Result<()>
where
F: FnMut() -> T,
{
if vec.len() < min_size {
Self::grow_capacity(vec, min_size)?;
vec.resize_with(min_size, init);
}
Ok(())
}
pub fn grow_no_copy<T, F>(vec: &mut Vec<T>, min_size: usize, init: F) -> Result<()>
where
F: FnMut() -> T,
{
let current_size = vec.len();
if current_size < min_size {
let new_capacity = Self::oversize(min_size, size_of::<T>())?;
if vec.capacity() >= min_size {
vec.resize_with(min_size, init);
} else {
let mut replacement = Vec::with_capacity(new_capacity);
replacement.resize_with(min_size, init);
*vec = replacement;
}
}
Ok(())
}
pub fn hash_code(array: &[char], start: usize, end: usize) -> i32 {
let mut code: i32 = 0;
for i in (start..end).rev() {
code = code.wrapping_mul(31).wrapping_add(array[i] as i32);
}
code
}
pub fn do_intro_sort<T, C>(a: &mut [T], from_index: usize, to_index: usize, comp: C) -> Result<()>
where
C: Comparator<T>,
{
if to_index.saturating_sub(from_index) <= 1 {
return Ok(());
}
ArrayIntroSorter::new(a, comp).sort(from_index, to_index)
}
pub fn intro_sort_with_comparator<T, C>(a: &mut [T], comp: C) -> Result<()>
where
C: Comparator<T>,
{
Self::do_intro_sort(a, 0, a.len(), comp)
}
pub fn intro_sort_with_range<T>(a: &mut [T], from_index: usize, to_index: usize) -> Result<()>
where
T: Ord,
{
if to_index <= 1 + from_index {
return Ok(());
}
Self::do_intro_sort(a, from_index, to_index, NaturalOrder::new())
}
pub fn intro_sort<T>(a: &mut [T]) -> Result<()>
where
T: Ord,
{
Self::intro_sort_with_range(a, 0, a.len())
}
pub fn do_tim_sort<T, C>(a: &mut [T], from_index: usize, to_index: usize, comp: C) -> Result<()>
where
T: Copy,
C: Comparator<T>,
{
if to_index <= 1 + from_index {
return Ok(());
}
let max_temp_slots = a.len() / 64;
debug_assert!(max_temp_slots <= i32::MAX as usize);
ArrayTimSorter::new(a, comp, max_temp_slots).sort(from_index, to_index)
}
pub fn tim_sort_with_comparator<T, C>(a: &mut [T], comp: C) -> Result<()>
where
T: Copy,
C: Comparator<T>,
{
let len = a.len();
Self::do_tim_sort(a, 0, len, comp)
}
pub fn tim_sort_with_range<T>(a: &mut [T], from_index: usize, to_index: usize) -> Result<()>
where
T: Copy + Ord,
{
if to_index <= 1 + from_index {
return Ok(());
}
Self::do_tim_sort(a, from_index, to_index, NaturalOrder::new())
}
pub fn tim_sort<T>(a: &mut [T]) -> Result<()>
where
T: Copy + Ord,
{
let len = a.len();
Self::tim_sort_with_range(a, 0, len)
}
pub fn select<T, C>(arr: &mut [T], from: usize, to: usize, k: usize, comparator: &C) -> Result<()>
where
C: Comparator<T>,
{
let sub_selector = IntroSelectorImpl::new(arr, comparator);
let mut selector = IntroSelector::new(sub_selector);
Selector::select(&mut selector, from, to, k)?;
Ok(())
}
pub fn copy_array<T>(array: &[T]) -> Vec<T>
where
T: Clone,
{
Self::copy_of_sub_array(array, 0, array.len())
}
pub fn copy_of_sub_array<T>(array: &[T], from: usize, to: usize) -> Vec<T>
where
T: Clone,
{
debug_assert!(to >= from && to <= array.len());
array[from..to].to_vec()
}
pub fn get_unsigned_comparator(num_bytes: usize) -> ByteArrayComparatorEnum {
if num_bytes == BitUtil::LONG_BYTES {
return ByteArrayComparatorEnum::U64(U64byteArrayComparator);
} else if num_bytes == BitUtil::INT_BYTES {
return ByteArrayComparatorEnum::U32(U32byteArrayComparator);
}
ByteArrayComparatorEnum::Byte(ByteByteArrayComparator { num_bytes })
}
}
struct IntroSelectorImpl<'a, T, C> {
pivot: usize,
arr: &'a mut [T],
comparator: &'a C,
}
impl<'a, T, C> IntroSelectorImpl<'a, T, C> {
fn new(arr: &'a mut [T], comparator: &'a C) -> IntroSelectorImpl<'a, T, C> {
IntroSelectorImpl {
pivot: 0,
arr,
comparator,
}
}
}
impl<T, C> IntroSelectorBaseDefault for IntroSelectorImpl<'_, T, C>
where
C: Comparator<T>,
{
fn set_pivot(&mut self, i: usize) -> Result<()> {
self.pivot = i;
Ok(())
}
fn compare_pivot(&mut self, j: usize) -> Result<i32> {
self.comparator.compare(&self.arr[self.pivot], &self.arr[j])
}
}
impl<T, C> IntroSelectorBase for IntroSelectorImpl<'_, T, C> where C: Comparator<T> {}
impl<T, C> Selector for IntroSelectorImpl<'_, T, C>
where
C: Comparator<T>,
{
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.arr.swap(i, j);
Ok(())
}
}
pub trait ByteArrayComparator {
fn compare(&self, a: &[u8], a_i: usize, b: &[u8], b_i: usize) -> i32;
}
#[derive(Clone)]
pub enum ByteArrayComparatorEnum {
U64(U64byteArrayComparator),
U32(U32byteArrayComparator),
Byte(ByteByteArrayComparator),
CommonPrefixLength8(CommonPrefixLength8),
CommonPrefixLength4(CommonPrefixLength4),
CommonPrefixLength(CommonPrefixLengthN),
}
impl ByteArrayComparator for ByteArrayComparatorEnum {
fn compare(&self, a: &[u8], a_i: usize, b: &[u8], b_i: usize) -> i32 {
match self {
ByteArrayComparatorEnum::U64(c) => c.compare(a, a_i, b, b_i),
ByteArrayComparatorEnum::U32(c) => c.compare(a, a_i, b, b_i),
ByteArrayComparatorEnum::Byte(c) => c.compare(a, a_i, b, b_i),
ByteArrayComparatorEnum::CommonPrefixLength8(c) => c.compare(a, a_i, b, b_i),
ByteArrayComparatorEnum::CommonPrefixLength4(c) => c.compare(a, a_i, b, b_i),
ByteArrayComparatorEnum::CommonPrefixLength(c) => c.compare(a, a_i, b, b_i),
}
}
}
#[derive(Clone)]
pub struct U64byteArrayComparator;
impl ByteArrayComparator for U64byteArrayComparator {
fn compare(&self, a: &[u8], a_i: usize, b: &[u8], b_i: usize) -> i32 {
(BitUtil::get_i64_be(a, a_i) as u64)
.cmp(&(BitUtil::get_i64_be(b, b_i) as u64))
.to_int()
}
}
#[derive(Clone)]
pub struct U32byteArrayComparator;
impl ByteArrayComparator for U32byteArrayComparator {
fn compare(&self, a: &[u8], a_i: usize, b: &[u8], b_i: usize) -> i32 {
(BitUtil::get_i32_be(a, a_i) as u32)
.cmp(&(BitUtil::get_i32_be(b, b_i) as u32))
.to_int()
}
}
#[derive(Clone)]
pub struct ByteByteArrayComparator {
num_bytes: usize,
}
impl ByteArrayComparator for ByteByteArrayComparator {
fn compare(&self, a: &[u8], a_i: usize, b: &[u8], b_i: usize) -> i32 {
debug_assert!(a.len() >= a_i + self.num_bytes);
debug_assert!(b.len() >= b_i + self.num_bytes);
a[a_i..a_i + self.num_bytes]
.cmp(&b[b_i..b_i + self.num_bytes])
.to_int()
}
}
#[derive(Clone)]
pub struct CommonPrefixLength8;
impl ByteArrayComparator for CommonPrefixLength8 {
fn compare(&self, a: &[u8], a_i: usize, b: &[u8], b_i: usize) -> i32 {
BKDUtil::common_prefix_length8(a, a_i, b, b_i)
}
}
#[derive(Clone)]
pub struct CommonPrefixLength4;
impl ByteArrayComparator for CommonPrefixLength4 {
fn compare(&self, a: &[u8], a_i: usize, b: &[u8], b_i: usize) -> i32 {
BKDUtil::common_prefix_length4(a, a_i, b, b_i)
}
}
#[derive(Clone)]
pub struct CommonPrefixLengthN {
pub(crate) num_bytes: usize,
}
impl ByteArrayComparator for CommonPrefixLengthN {
fn compare(&self, a: &[u8], a_i: usize, b: &[u8], b_i: usize) -> i32 {
BKDUtil::common_prefix_length_n(a, a_i, b, b_i, self.num_bytes)
}
}