use alloc::boxed::Box;
use core::ops::{Deref, DerefMut};
use intrusive_collections::{
intrusive_adapter,
rbtree::{RBTree, CursorMut},
RBTreeLink,
KeyAdapter,
};
#[derive(Debug)]
pub struct Wrapper<T: Ord> {
link: RBTreeLink,
inner: T,
}
intrusive_adapter!(pub WrapperAdapter<T> = Box<Wrapper<T>>: Wrapper<T> { link: RBTreeLink } where T: Ord);
impl<'a, T: Ord + 'a> KeyAdapter<'a> for WrapperAdapter<T> {
type Key = &'a T;
fn get_key(&self, value: &'a Wrapper<T>) -> Self::Key {
&value.inner
}
}
impl <T: Ord> Deref for Wrapper<T> {
type Target = T;
fn deref(&self) -> &T {
&self.inner
}
}
impl <T: Ord> DerefMut for Wrapper<T> {
fn deref_mut(&mut self) -> &mut T {
&mut self.inner
}
}
impl <T: Ord> Wrapper<T> {
pub(crate) fn new_link(value: T) -> Box<Self> {
Box::new(Wrapper {
link: RBTreeLink::new(),
inner: value,
})
}
pub(crate) fn into_inner(self) -> T {
self.inner
}
}
pub struct StaticArrayRBTree<T: Ord>(pub(crate) Inner<T>);
pub(crate) enum Inner<T: Ord> {
Array([Option<T>; 32]),
RBTree(RBTree<WrapperAdapter<T>>),
}
impl<T: Ord> Default for StaticArrayRBTree<T> {
fn default() -> Self {
Self::empty()
}
}
impl<T: Ord> StaticArrayRBTree<T> {
pub const fn empty() -> Self {
StaticArrayRBTree(Inner::Array([
None, None, None, None, None, None, None, None,
None, None, None, None, None, None, None, None,
None, None, None, None, None, None, None, None,
None, None, None, None, None, None, None, None,
]))
}
#[allow(dead_code)]
pub const fn new(arr: [Option<T>; 32]) -> Self {
StaticArrayRBTree(Inner::Array(arr))
}
}
impl<T: Ord + 'static> StaticArrayRBTree<T> {
pub fn insert(&mut self, value: T) -> Result<ValueRefMut<T>, T> {
match &mut self.0 {
Inner::Array(arr) => {
for elem in arr {
if elem.is_none() {
*elem = Some(value);
return Ok(ValueRefMut::Array(elem));
}
}
log::error!("Out of space in StaticArrayRBTree's inner array, failed to insert value.");
Err(value)
}
Inner::RBTree(tree) => {
Ok(ValueRefMut::RBTree(
tree.insert(Wrapper::new_link(value))
))
}
}
}
pub fn convert_to_heap_allocated(&mut self) {
let new_tree = match &mut self.0 {
Inner::Array(arr) => {
let mut tree = RBTree::new(WrapperAdapter::new());
for elem in arr {
if let Some(e) = elem.take() {
tree.insert(Wrapper::new_link(e));
}
}
tree
}
Inner::RBTree(_tree) => return,
};
*self = StaticArrayRBTree(Inner::RBTree(new_tree));
}
pub fn len(&self) -> usize {
match &self.0 {
Inner::Array(arr) => arr.iter().filter(|e| e.is_some()).count(),
Inner::RBTree(tree) => tree.iter().count(),
}
}
pub fn iter(&self) -> impl Iterator<Item = &T> {
let mut iter_a = None;
let mut iter_b = None;
match &self.0 {
Inner::Array(arr) => iter_a = Some(arr.iter().flatten()),
Inner::RBTree(tree) => iter_b = Some(tree.iter()),
}
iter_a.into_iter()
.flatten()
.chain(
iter_b.into_iter()
.flatten()
.map(|wrapper| &wrapper.inner)
)
}
}
pub enum RemovedValue<T: Ord> {
Array(Option<T>),
RBTree(Option<Box<Wrapper<T>>>),
}
impl<T: Ord> RemovedValue<T> {
#[allow(dead_code)]
pub fn as_ref(&self) -> Option<&T> {
match self {
Self::Array(opt) => opt.as_ref(),
Self::RBTree(opt) => opt.as_ref().map(|bw| &bw.inner),
}
}
}
pub enum ValueRefMut<'list, T: Ord> {
Array(&'list mut Option<T>),
RBTree(CursorMut<'list, WrapperAdapter<T>>),
}
impl <'list, T: Ord> ValueRefMut<'list, T> {
pub fn remove(&mut self) -> RemovedValue<T> {
match self {
Self::Array(ref mut arr_ref) => {
RemovedValue::Array(arr_ref.take())
}
Self::RBTree(ref mut cursor_mut) => {
RemovedValue::RBTree(cursor_mut.remove())
}
}
}
#[allow(dead_code)]
pub fn replace_with(&mut self, new_value: T) -> Result<Option<T>, T> {
match self {
Self::Array(ref mut arr_ref) => {
Ok(arr_ref.replace(new_value))
}
Self::RBTree(ref mut cursor_mut) => {
cursor_mut.replace_with(Wrapper::new_link(new_value))
.map(|removed| Some(removed.inner))
.map_err(|e| e.inner)
}
}
}
#[allow(dead_code)]
pub fn get(&self) -> Option<&T> {
match self {
Self::Array(ref arr_ref) => arr_ref.as_ref(),
Self::RBTree(ref cursor_mut) => cursor_mut.get().map(|w| w.deref()),
}
}
}