use crate::test_framework::core::util::lucene_test_case::random;
use rand::Rng;
use rand::RngExt;
use crate::core::util::array_util::ArrayUtil;
use crate::core::util::error::lucene_error::{LuceneError, LuceneErrorKind, Result};
use crate::core::util::long_heap::LongHeap;
#[allow(dead_code)] struct TestLongHeap;
fn check_validity(heap: &LongHeap) {
let heap_array = heap.get_heap_array();
let size = heap.size();
for i in 2..=size {
let parent = i >> 1;
assert!(
heap_array[parent] <= heap_array[i],
"Heap property violated at index {}: parent={} > child={}",
i,
heap_array[parent],
heap_array[i]
);
}
}
#[test]
fn test_pq_basic() -> Result<()> {
let mut random = random();
test_pq_with_random(10_000, &mut random)
}
fn test_pq_with_random<R>(count: usize, random: &mut R) -> Result<()>
where
R: Rng + ?Sized,
{
let mut pq = LongHeap::new(count)?;
let mut sum: i64 = 0;
let mut sum2: i64 = 0;
for _ in 0..count {
let next = random.random();
sum = sum.wrapping_add(next);
pq.push(next)?;
check_validity(&pq);
}
let mut last = i64::MIN;
for _ in 0..count {
let next = pq.pop()?;
assert!(
next >= last,
"Heap out of order: current {} < last {}",
next,
last
);
last = next;
sum2 = sum2.wrapping_add(last);
}
assert_eq!(sum, sum2, "Sum mismatch after all pops");
Ok(())
}
#[test]
fn test_clear() -> Result<()> {
let mut pq = LongHeap::new(3)?;
pq.push(2)?;
pq.push(3)?;
pq.push(1)?;
assert_eq!(3, pq.size());
pq.clear();
assert_eq!(0, pq.size());
Ok(())
}
#[test]
fn test_exceed_bounds() -> Result<()> {
let mut pq = LongHeap::new(1)?;
pq.push(2)?;
pq.push(0)?;
assert_eq!(2, pq.size());
assert_eq!(0, pq.top());
Ok(())
}
#[test]
fn test_fixed_size() -> Result<()> {
let mut pq = LongHeap::new(3)?;
pq.insert_with_overflow(2)?;
pq.insert_with_overflow(3)?;
pq.insert_with_overflow(1)?;
pq.insert_with_overflow(5)?;
pq.insert_with_overflow(7)?;
pq.insert_with_overflow(1)?;
assert_eq!(3, pq.size());
assert_eq!(3, pq.top());
Ok(())
}
#[test]
fn test_duplicate_values() -> Result<()> {
let mut pq = LongHeap::new(3)?;
pq.push(2)?;
pq.push(3)?;
pq.push(1)?;
assert_eq!(1, pq.top());
pq.update_top(3);
assert_eq!(3, pq.size());
assert_eq!(&[0, 2, 3, 3], pq.get_heap_array());
Ok(())
}
#[test]
fn test_insertions() -> Result<()> {
let mut random = random();
let num_docs_in_pq = random.random_range(1..=100);
let mut pq = LongHeap::new(num_docs_in_pq)?;
let mut last_least: Option<i64> = None;
for _ in 0..(num_docs_in_pq * 10) {
let new_entry = random.random();
pq.insert_with_overflow(new_entry)?;
check_validity(&pq);
let new_least = pq.top();
if let Some(last) = last_least.filter(|&last| new_least != new_entry && new_least != last) {
assert!(new_least <= new_entry);
assert!(new_least >= last);
}
last_least = Some(new_least);
}
Ok(())
}
#[test]
fn test_invalid() -> Result<()> {
assert!(matches!(
(LongHeap::new(0)).as_ref().map_err(LuceneError::kind),
Err(LuceneErrorKind::IllegalArgument(_))
));
assert!(matches!(
(LongHeap::new(ArrayUtil::MAX_ARRAY_LENGTH))
.as_ref()
.map_err(LuceneError::kind),
Err(LuceneErrorKind::IllegalArgument(_))
));
Ok(())
}
#[test]
fn test_unbounded() -> Result<()> {
let mut random = random();
let initial_size = random.random_range(1..=10);
let mut pq = LongHeap::new(initial_size)?;
let num = random.random_range(1..=100);
let mut max_value = i64::MIN;
let mut count = 0;
for _ in 0..num {
let value: i64 = random.random();
if random.random_bool(0.5) {
pq.push(value)?;
count += 1;
} else {
let full = pq.size() >= initial_size;
if pq.insert_with_overflow(value)? && !full {
count += 1;
}
}
max_value = std::cmp::max(max_value, value);
}
assert_eq!(count, pq.size());
let mut last = i64::MIN;
while pq.size() > 0 {
let top = pq.top();
let next = pq.pop()?;
assert_eq!(top, next);
count -= 1;
assert!(next >= last);
last = next;
}
assert_eq!(0, count);
assert_eq!(max_value, last);
Ok(())
}