use core::borrow::Borrow;
use core::cmp::Ordering;
use std::ops::Deref;
pub trait NodeLike<T: Ord> {
#[allow(dead_code)]
fn with_capacity(capacity: usize) -> Self;
#[allow(dead_code)]
fn get_ith(&self, index: usize) -> Option<&T>;
#[allow(dead_code)]
fn halve(&mut self) -> Self;
#[allow(dead_code)]
fn need_to_split(&self, border: usize, value: &T) -> bool;
#[allow(dead_code)]
fn len(&self) -> usize;
#[allow(dead_code)]
fn capacity(&self) -> usize;
#[allow(dead_code)]
fn insert(&mut self, value: T) -> (bool, usize);
#[allow(dead_code)]
fn contains<Q: Ord + ?Sized>(&self, value: &Q) -> bool
where
T: Borrow<Q>;
#[allow(dead_code)]
fn try_select<Q: Ord + ?Sized>(&self, value: &Q) -> Option<usize>
where
T: Borrow<Q>;
#[allow(dead_code)]
fn rank<Q: Ord + ?Sized>(&self, bound: std::ops::Bound<&Q>, from_start: bool) -> Option<usize>
where
T: Borrow<Q>;
#[allow(dead_code)]
fn delete<Q: Ord + ?Sized>(&mut self, value: &Q) -> Option<(T, usize)>
where
T: Borrow<Q>;
#[allow(dead_code)]
fn replace(&mut self, idx: usize, value: T) -> Option<T>;
#[allow(dead_code)]
fn max(&self) -> Option<&T>;
#[allow(dead_code)]
fn min(&self) -> Option<&T>;
#[allow(dead_code)]
fn iter<'a>(&'a self) -> std::slice::Iter<'a, T> where T: 'a;
}
#[inline]
fn search<Q, T: Ord>(haystack: &[T], needle: &Q) -> Result<usize, usize>
where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
let mut j = haystack.len();
unsafe {
let mut i = 0;
let p = haystack.as_ptr().cast::<T>();
let mut m = j >> 1;
while i != j {
match (*p.add(m)).borrow().cmp(&needle) {
Ordering::Equal => return Ok(m),
Ordering::Less => {
i = m + 1;
m = (i + j) >> 1;
}
Ordering::Greater => {
j = m;
m = (i + j) >> 1;
}
}
}
Err(i)
}
}
enum Direction<'a, T> {
Forward(std::slice::Iter<'a, T>),
Backward(std::iter::Rev<std::slice::Iter<'a, T>>),
}
#[inline]
fn compute_positions_to_skip<Q, T: Ord>(haystack: &[T], bound: std::ops::Bound<&Q>, forward: bool) -> Option<usize>
where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
match bound {
std::ops::Bound::Unbounded => { None }
std::ops::Bound::Included(value) | std::ops::Bound::Excluded(value) => {
let mut positions_to_skip = -1;
let iter = if forward {
Direction::Forward(haystack.iter())
} else {
Direction::Backward(haystack.iter().rev())
};
match iter {
Direction::Forward(iter) => {
for item in iter {
match item.borrow().cmp(&value) {
Ordering::Less => positions_to_skip += 1,
Ordering::Equal => match bound {
std::ops::Bound::Included(_) => break,
std::ops::Bound::Excluded(_) => { positions_to_skip += 1; break },
_ => unreachable!(),
},
Ordering::Greater => break,
}
}
}
Direction::Backward(iter) => {
for item in iter {
match item.borrow().cmp(&value) {
Ordering::Greater => positions_to_skip += 1,
Ordering::Equal => match bound {
std::ops::Bound::Included(_) => break,
std::ops::Bound::Excluded(_) => { positions_to_skip += 1; break },
_ => unreachable!(),
},
Ordering::Less => break,
}
}
}
}
if positions_to_skip >= 0 {
Some(positions_to_skip as usize)
} else {
None
}
}
}
}
impl<T: Ord> NodeLike<T> for Vec<T> {
#[inline]
fn with_capacity(capacity: usize) -> Self {
Vec::with_capacity(capacity)
}
#[inline]
fn get_ith(&self, index: usize) -> Option<&T> {
self.get(index)
}
#[inline]
fn halve(&mut self) -> Self {
self.split_off(self.capacity() / 2)
}
#[inline]
fn need_to_split(&self, border: usize, _: &T) -> bool {
self.len() >= border
}
#[inline]
fn len(&self) -> usize {
self.len()
}
#[inline]
fn capacity(&self) -> usize {
self.capacity()
}
#[inline]
fn insert(&mut self, value: T) -> (bool, usize) {
match search(&self, &value) {
Ok(idx) => (false, idx),
Err(idx) => {
self.insert(idx, value);
(true, idx)
}
}
}
#[inline]
fn contains<Q>(&self, value: &Q) -> bool
where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
match search(&self, &value) {
Ok(_) => true,
Err(_) => false,
}
}
#[inline]
fn try_select<Q>(&self, value: &Q) -> Option<usize>
where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
match search(&self, &value) {
Ok(index) => Some(index),
Err(_) => None,
}
}
#[inline]
fn rank<Q>(&self, bound: std::ops::Bound<&Q>, from_start: bool) -> Option<usize>
where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
compute_positions_to_skip(&self, bound, from_start)
}
#[inline]
fn delete<Q>(&mut self, value: &Q) -> Option<(T, usize)>
where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
match search(&self, value) {
Ok(idx) => Some((self.remove(idx), idx)),
Err(_) => None,
}
}
#[inline]
fn replace(&mut self, idx: usize, value: T) -> Option<T> {
if let Some(old) = self.get_mut(idx) {
let old = std::mem::replace(old, value);
return Some(old);
}
None
}
#[inline]
fn max(&self) -> Option<&T> {
self.last()
}
#[inline]
fn min(&self) -> Option<&T> {
self.first()
}
#[inline]
fn iter<'a>(&'a self) -> std::slice::Iter<'a, T>
where T: 'a
{
self.deref().iter()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_search_bound() {
let vec = vec![1, 3, 5, 7, 9];
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Unbounded, true), None);
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Unbounded, false), None);
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Included(&1), true), None);
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Included(&5), true), Some(1));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Included(&9), true), Some(3));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Included(&0), true), None);
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Included(&10), true), Some(4));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&1), true), Some(0));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&5), true), Some(2));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&9), true), Some(4));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&0), true), None);
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&10), true), Some(4));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Included(&1), false), Some(3));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Included(&5), false), Some(1));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Included(&9), false), None);
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Included(&0), false), Some(4));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Included(&10), false), None);
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&1), false), Some(4));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&5), false), Some(2));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&9), false), Some(0));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&0), false), Some(4));
assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&10), false), None);
let empty: Vec<i32> = vec![];
assert_eq!(compute_positions_to_skip(&empty, std::ops::Bound::Included(&1), true), None);
assert_eq!(compute_positions_to_skip(&empty, std::ops::Bound::Excluded(&1), false), None);
}
}