orx_selfref_col/references/

array_left_most.rs

use super::{
    NodePtr,
    iter::{ArrayLeftMostPtrIter, ArrayLeftMostPtrIterMut},
    refs::Refs,
};
use crate::variant::Variant;
use core::fmt::Debug;

/// A constant number of left-aligned references.
///
/// It differs from [`RefsArray`] due to its additional requirement that:
/// * all Some references are to the left of all None references.
///
/// [`RefsArray`]: crate::RefsArray
pub struct RefsArrayLeftMost<const N: usize, V>
where
    V: Variant,
{
    array: [Option<NodePtr<V>>; N],
    len: usize,
}

impl<const N: usize, V: Variant> Clone for RefsArrayLeftMost<N, V> {
    fn clone(&self) -> Self {
        Self {
            array: self.array,
            len: self.len,
        }
    }
}

impl<const N: usize, V: Variant> Debug for RefsArrayLeftMost<N, V> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_tuple("RefsArrayLeftMost")
            .field(&self.array)
            .finish()
    }
}

impl<const N: usize, V> Refs for RefsArrayLeftMost<N, V>
where
    V: Variant,
{
    #[inline(always)]
    fn empty() -> Self {
        Self {
            array: [const { None }; N],
            len: 0,
        }
    }

    #[inline(always)]
    fn is_empty(&self) -> bool {
        self.len == 0
    }

    #[inline(always)]
    fn clear(&mut self) {
        self.array
            .iter_mut()
            .take(self.len)
            .for_each(|x| _ = x.take());
        self.len = 0;
    }

    #[inline(always)]
    fn remove_at(&mut self, ref_idx: usize) {
        self.array[ref_idx] = None;
        for i in (ref_idx + 1)..self.len {
            self.array[i - 1] = self.array[i].take();
        }
        self.len -= 1;
    }

    #[inline(always)]
    fn remove(&mut self, ptr: usize) -> Option<usize> {
        let x = self.array.iter().enumerate().find(|x| match x.1 {
            Some(x) => unsafe { x.ptr() as usize == ptr },
            None => false,
        });
        match x {
            Some((ref_idx, _)) => {
                self.remove_at(ref_idx);
                Some(ref_idx)
            }
            None => None,
        }
    }
}

impl<const N: usize, V: Variant> RefsArrayLeftMost<N, V> {
    /// Returns the number of references.
    pub fn len(&self) -> usize {
        self.len
    }

    /// Returns true if the number of references is zero.
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns a reference to the node pointer at the `ref_idx` position of the references array.
    pub fn get(&self, ref_idx: usize) -> Option<NodePtr<V>> {
        match ref_idx < N {
            true => self.array[ref_idx],
            false => None,
        }
    }

    /// Returns the optional node pointers as a slice such that:
    /// * length of the slice is equal to `self.len()`,
    /// * all elements of the slice are of `Some` variant, and hence,
    /// * can be safely unwrapped to access the node pointer.
    pub fn as_slice(&self) -> &[Option<NodePtr<V>>] {
        &self.array[..self.len]
    }

    /// Creates an iterator over node pointers of the references collection.
    pub fn iter(&self) -> ArrayLeftMostPtrIter<'_, V> {
        let slice = &self.array[..self.len];
        ArrayLeftMostPtrIter::new(slice.iter())
    }

    /// Creates a mutable iterator over node pointers of the references collection.
    pub fn iter_mut(&mut self) -> ArrayLeftMostPtrIterMut<'_, V> {
        let slice = &mut self.array[..self.len];
        ArrayLeftMostPtrIterMut::new(slice.iter_mut())
    }

    /// Returns whether or not the collection has room for another reference.
    pub fn has_room(&self) -> bool {
        self.len < N
    }

    /// Pushes the node references to the end of the references collection.
    ///
    /// # Panics
    ///
    /// Panics if the array already has `N` references; i.e., when `self.has_room()` is false.
    pub fn push(&mut self, node_ptr: NodePtr<V>) {
        self.assert_has_room_for::<1>();
        self.array[self.len] = Some(node_ptr);
        self.len += 1;
    }

    /// Inserts the reference with the given `node_ptr` to the given `position` of the references collection.
    pub fn insert(&mut self, position: usize, node_ptr: NodePtr<V>) {
        for q in (position..self.len).rev() {
            self.array[q + 1] = self.array[q];
        }
        self.array[position] = Some(node_ptr);
        self.len += 1;
    }

    /// Inserts the reference with the given `node_ptr` just before the given `pivot_ptr` the reference if it exists;
    /// and returns the position that the new reference is inserted to.
    ///
    /// Does nothing leaving the children unchanged if the `pivot_ptr` reference does not exists, and returns None.
    pub fn push_before(&mut self, pivot_ptr: NodePtr<V>, node_ptr: NodePtr<V>) -> Option<usize> {
        self.assert_has_room_for::<1>();
        let position = self.iter().position(|x| *x == pivot_ptr);
        if let Some(p) = position {
            self.insert(p, node_ptr);
        }
        position
    }

    /// Inserts the reference with the given `node_ptr` just after the given `pivot_ptr` the reference if it exists;
    /// and returns the position that the new reference is inserted to.
    ///
    /// Does nothing leaving the children unchanged if the `pivot_ptr` reference does not exists, and returns None.
    pub fn push_after(&mut self, pivot_ptr: NodePtr<V>, node_ptr: NodePtr<V>) -> Option<usize> {
        self.assert_has_room_for::<1>();
        let position = self.iter().position(|x| *x == pivot_ptr);
        if let Some(p) = position {
            self.insert(p + 1, node_ptr);
        }
        position
    }

    /// Replaces the node reference `old_node_ptr` with the `new_node_ptr` and returns
    /// the position of the reference.
    ///
    /// Does nothing and returns None if the `old_node_ptr` is absent.
    pub fn replace_with(
        &mut self,
        old_node_ptr: NodePtr<V>,
        new_node_ptr: NodePtr<V>,
    ) -> Option<usize> {
        let position = self.iter().position(|x| *x == old_node_ptr);
        if let Some(p) = position {
            self.array[p] = Some(new_node_ptr);
        }
        position
    }

    /// If both pointers `ptr_a` and `ptr_b` exist as children, this method swaps their positions
    /// and returns `(pos_a, pos_b)` where `pos_a` (`pos_b`) is the original (before the swap) position
    /// of the child `ptr_a` (`ptr_b`).
    ///
    /// Does nothing and returns None if either of the pointers is absent.
    pub fn swap(&mut self, ptr_a: NodePtr<V>, ptr_b: NodePtr<V>) -> Option<(usize, usize)> {
        let (pos_a, pos_b) = {
            let mut a = None;
            let mut b = None;
            for (i, x) in self.array[..self.len].iter().enumerate() {
                match *x {
                    x if x == Some(ptr_a) => {
                        a = Some(i);
                        if b.is_some() {
                            break;
                        }
                    }
                    x if x == Some(ptr_b) => {
                        b = Some(i);
                        if a.is_some() {
                            break;
                        }
                    }
                    _ => {}
                }
            }
            match (a, b) {
                (Some(a), Some(b)) => Some((a, b)),
                _ => None,
            }
        }?;
        self.array[pos_a] = Some(ptr_b);
        self.array[pos_b] = Some(ptr_a);
        Some((pos_a, pos_b))
    }

    // helpers
    fn assert_has_room_for<const P: usize>(&self) {
        assert!(
            self.len + P <= N,
            "Pushing the {}-th reference to array-backed references with maximum of {} elements.",
            N + P,
            N
        );
    }
}