cpp_map 0.1.1

//           Copyright 2021 Eadf (github.com/eadf)
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! A simple data structure emulating a C++ std::map. Probably not useful for anyone.
//!
//! I needed a data structure that could emulate a C++ std::map, and it's pointer based iterators.
//!
//! More specifically it needs to emulate the insertion position hint functionality as the keys I intend to
//! use are not entirely transitive. i.e., searching for insertion position from the head or tail makes a big difference.
//!
//! I also needed to be able to replace the key of an already inserted item w/o altering the order. - Don't ask.
//! Another gotcha is that insert(key, value) is a NOP if the key already exists, not even the new value will be used.
//!
//! The current implementation uses a double linked std::vec::Vec list, and it only supports sequential search.
//!
use std::cell::RefCell;
use std::cmp::Ordering;
use std::fmt::Debug;
use std::rc::Rc;

/// Indicates that an iterator has passed beyond the limits of the list.
pub const OUT_OF_BOUNDS: usize = usize::MAX;

#[derive(thiserror::Error, Debug)]
pub enum MapError {
    #[error("error: Some error with the linked list")]
    InternalError(String),
    #[error(transparent)]
    BorrowError(#[from] std::cell::BorrowError),
    #[error(transparent)]
    BorrowMutError(#[from] std::cell::BorrowMutError),
}

#[cfg(test)]
mod test;

#[derive(Clone, Debug)]
struct Node<K, V>
where
    K: Debug,
    V: Debug,
{
    prev_: usize,
    next_: usize,
    key_: K,
    value_: V,
}

/// A double linked min list.
/// The head (top/front) of the list is the first item. Sorted Order::Less than other items.
/// The tail (bottom/back) is the last item of the list. Sorted Order::Greater than other items.
#[derive(Clone, Debug)]
pub struct LinkedList<K, V>
where
    K: Debug,
    V: Debug,
{
    head_: usize,
    tail_: usize,
    nodes_: Vec<Option<Node<K, V>>>,
    id_pool_: Vec<usize>,
}

impl<K, V> Default for LinkedList<K, V>
where
    K: Debug,
    V: Debug,
{
    fn default() -> Self {
        Self {
            head_: OUT_OF_BOUNDS,
            tail_: OUT_OF_BOUNDS,
            nodes_: Vec::new(),
            id_pool_: Vec::new(),
        }
    }
}

#[derive(Clone, Debug)]
/// borrow checker work-around
struct EraseOperation {
    // (node index, next index)
    change_prev_: Option<(usize, usize)>,
    // the node to erase
    erase_: usize,
    // (node index, pre index)
    change_next_: Option<(usize, usize)>,
}

#[allow(dead_code)]
impl<'a, K: 'a, V: 'a> LinkedList<K, V>
where
    K: Debug + Ord + PartialOrd,
    V: Debug,
{
    /// Constructs a new, empty LinkedList<K,V> with the specified capacity.
    /// The LinkedList will be able to hold exactly capacity elements without reallocating.
    /// If capacity is 0, the list will not allocate.
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            head_: OUT_OF_BOUNDS,
            tail_: OUT_OF_BOUNDS,
            nodes_: Vec::with_capacity(capacity),
            id_pool_: Vec::with_capacity(capacity),
        }
    }

    pub fn iter(&self) -> ListIterator<'_, K, V> {
        ListIterator {
            list_: self,
            my_next_: self.head_,
        }
    }

    #[inline(always)]
    /// Returns the number of inserted elements
    pub fn len(&self) -> usize {
        self.nodes_.len() - self.id_pool_.len()
    }

    /// Returns the capacity or the vectors
    pub fn capacity(&self) -> (usize, usize) {
        (self.nodes_.capacity(), self.id_pool_.capacity())
    }

    #[inline(always)]
    /// Returns true if the list is empty
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Clears the list.
    /// Warning: any Pointer object referring to this list will be corrupted.
    pub fn clear(&mut self) {
        self.head_ = OUT_OF_BOUNDS;
        self.tail_ = OUT_OF_BOUNDS;
        self.nodes_.clear();
        self.id_pool_.clear();
    }

    /// Returns the next free index.
    /// This value will be invalid if any insert or remove operation is performed on the list.
    pub fn next_free_index(&self) -> usize {
        if self.id_pool_.is_empty() {
            self.nodes_.len()
        } else {
            // unwrap is safe after !is_empty() check
            *self.id_pool_.last().unwrap()
        }
    }

    #[inline(always)]
    /// Returns the item key at index
    pub fn get_k(&self, index: usize) -> Result<&K, MapError> {
        let rv = self
            .nodes_
            .get(index)
            .ok_or_else(|| MapError::InternalError("error, item not found".to_string()))?
            .as_ref()
            .ok_or_else(|| MapError::InternalError("error, item was not active".to_string()))?;
        Ok(&rv.key_)
    }

    #[inline(always)]
    /// Returns the item value at index
    pub fn get_v(&self, index: usize) -> Result<&V, MapError> {
        let rv = self
            .nodes_
            .get(index)
            .ok_or_else(|| MapError::InternalError("error, item not found".to_string()))?
            .as_ref()
            .ok_or_else(|| MapError::InternalError("error, item was not active".to_string()))?;
        Ok(&rv.value_)
    }

    #[inline(always)]
    /// Returns the item key and value at index
    ///
    /// # Examples
    ///
    /// ```
    /// # use cpp_map::LinkedList;
    /// let mut ll = LinkedList::<i8, i8>::default();
    /// ll.ordered_insert(1,1);
    /// assert!(ll.get(ll.head()).is_ok());
    /// assert_eq!(ll.get(ll.head()).unwrap(), (&1,&1));
    /// ll.ordered_insert(0,0);
    /// assert!(ll.get(ll.head()).is_ok());
    /// assert_eq!(ll.get(ll.head()).unwrap(), (&0,&0));
    /// assert!(ll.get(ll.tail()).is_ok());
    /// assert_eq!(ll.get(ll.tail()).unwrap(), (&1,&1));
    ///
    /// ```
    pub fn get(&self, index: usize) -> Result<(&K, &V), MapError> {
        if index == OUT_OF_BOUNDS {
            return Err(MapError::InternalError(format!(
                "Invalid pointer (moved past start/end). {}:{}",
                file!(),
                line!()
            )));
        }
        let rv = self
            .nodes_
            .get(index)
            .ok_or_else(|| MapError::InternalError("error, item not found".to_string()))?
            .as_ref()
            .ok_or_else(|| MapError::InternalError("error, item was not active".to_string()))?;
        Ok((&rv.key_, &rv.value_))
    }

    #[inline(always)]
    /// Returns the previous key item of item at index
    pub fn get_prev_k(&self, index: usize) -> Result<&K, MapError> {
        let prev = self
            .nodes_
            .get(index)
            .as_ref()
            .ok_or_else(|| MapError::InternalError("error, item not found".to_string()))?
            .as_ref()
            .ok_or_else(|| MapError::InternalError("error, item was None".to_string()))?
            .prev_;

        let node = self
            .nodes_
            .get(prev)
            .ok_or_else(|| MapError::InternalError("error, prev item not found".to_string()))?
            .as_ref();
        Ok(&node
            .ok_or_else(|| MapError::InternalError("error, item was not active".to_string()))?
            .key_)
    }

    /// Add an item at the front of the list
    /// Note that this ignores the order of items, use with care.
    fn push_front_(&mut self, key: K, value: V) -> Result<usize, MapError> {
        let insertion_index = if !self.id_pool_.is_empty() {
            self.id_pool_.pop().unwrap()
        } else {
            self.nodes_.len()
        };
        let new_node = if let Some(ref mut prev_head) = self.nodes_.get_mut(self.head_) {
            if let Some(prev_head) = prev_head {
                //println!("prev_head:{:?}", prev_head);
                // there were a previous head
                let new_node = Node {
                    next_: self.head_,
                    prev_: OUT_OF_BOUNDS,
                    key_: key,
                    value_: value,
                };
                self.head_ = insertion_index;
                prev_head.prev_ = insertion_index;
                new_node
            } else {
                return Err(MapError::InternalError(format!(
                    "Should not happen error™ at {}:{}",
                    file!(),
                    line!()
                )));
            }
        } else {
            // This will be the first element in the list
            //println!("no prev_head:{}", self.head);
            self.head_ = insertion_index;
            self.tail_ = insertion_index;
            Node {
                next_: OUT_OF_BOUNDS,
                prev_: OUT_OF_BOUNDS,
                key_: key,
                value_: value,
            }
        };
        //println!("push_front Pushed {:?} at index:{}", new_node, curr_len);
        Ok(self.replace_or_push_(insertion_index, new_node))
    }

    #[inline(always)]
    /// insert at position or append at back of the list
    /// Note that this ignores the order of items, use with care.
    fn replace_or_push_(&mut self, insertion_index: usize, new_node: Node<K, V>) -> usize {
        if insertion_index == self.nodes_.len() {
            self.nodes_.push(Some(new_node));
        } else {
            // get_mut will never fail
            let _ = self
                .nodes_
                .get_mut(insertion_index)
                .unwrap()
                .replace(new_node);
        }
        insertion_index
    }

    /// insert a new value before the element at index
    /// Note that this ignores the order of items, use with care.
    fn insert_before_(&mut self, index: usize, key: K, value: V) -> Result<usize, MapError> {
        if index == OUT_OF_BOUNDS {
            return self.push_front_(key, value);
        }

        let insertion_index = if !self.id_pool_.is_empty() {
            self.id_pool_.pop().unwrap()
        } else {
            self.nodes_.len()
        };

        let new_node = if let Some(ref mut next_node) = self.nodes_.get_mut(index) {
            if let Some(ref mut next_node) = next_node {
                //println!("next_node:{:?}", next_node);
                // there were a previous head
                let new_node = Node {
                    next_: index,
                    prev_: next_node.prev_,
                    key_: key,
                    value_: value,
                };
                next_node.prev_ = insertion_index;
                new_node
            } else {
                return Err(MapError::InternalError(format!(
                    "Should not happen error™ at {}:{}",
                    file!(),
                    line!()
                )));
            }
        } else {
            // This will be the first element in the list
            //println!("no prev_head:{}", self.head);
            self.head_ = insertion_index;
            self.tail_ = insertion_index;
            Node {
                next_: OUT_OF_BOUNDS,
                prev_: OUT_OF_BOUNDS,
                key_: key,
                value_: value,
            }
        };
        let prev_node = new_node.prev_;

        //println!("insert_before Pushed {:?} at index:{}", new_node, curr_len);
        {
            let _i = self.replace_or_push_(insertion_index, new_node);
            #[cfg(feature = "console_debug")]
            assert_eq!(insertion_index, _i);
        };

        if prev_node != OUT_OF_BOUNDS {
            if let Some(prev_node) = self.nodes_.get_mut(prev_node) {
                if let Some(prev_node) = prev_node {
                    prev_node.next_ = insertion_index;
                } else {
                    return Err(MapError::InternalError(format!(
                        "Should not happen error™ at {}:{}",
                        file!(),
                        line!()
                    )));
                }
            } else {
                // this case should have been handled by the initial push_front()
                return Err(MapError::InternalError(format!(
                    "Should not happen error™ at {}:{}",
                    file!(),
                    line!()
                )));
            }
        } else {
            // We just pushed at the first position
            self.head_ = insertion_index;
        }
        //println!("insert_before inserted at {}", insertion_index);
        Ok(insertion_index)
    }

    /// Add an item at the back of the list
    fn push_back_(&mut self, key: K, value: V) -> Result<usize, MapError> {
        let insertion_index = if !self.id_pool_.is_empty() {
            self.id_pool_.pop().unwrap()
        } else {
            self.nodes_.len()
        };
        let new_node = if let Some(prev_tail) = self.nodes_.get_mut(self.tail_) {
            if let Some(prev_tail) = prev_tail {
                //println!("prev_tail:{:?}", prev_tail);
                // there were a previous tail
                let new_node = Node {
                    next_: OUT_OF_BOUNDS,
                    prev_: self.tail_,
                    key_: key,
                    value_: value,
                };
                self.tail_ = insertion_index;
                prev_tail.next_ = insertion_index;
                new_node
            } else {
                return Err(MapError::InternalError(format!(
                    "Should not happen error™ at {}:{}",
                    file!(),
                    line!()
                )));
            }
        } else {
            // This will be the first element in the list
            //println!("no prev_tail:{}", self.tail);
            self.head_ = insertion_index;
            self.tail_ = insertion_index;
            Node {
                next_: OUT_OF_BOUNDS,
                prev_: OUT_OF_BOUNDS,
                key_: key,
                value_: value,
            }
        };
        //println!("push_back Pushed {:?} at index:{}", new_node, insertion_index);
        {
            let _insert_index = self.replace_or_push_(insertion_index, new_node);
            #[cfg(feature = "console_debug")]
            assert_eq!(_insert_index, insertion_index);
        }
        Ok(insertion_index)
    }

    #[inline(always)]
    /// Insert item at position defined by Order (lesser first)
    /// This is the same as 'ordered_insert_pos()' with self.head_ as position hint
    /// Insert item by Order (lesser first) with a position hint.
    ///
    /// Note that insert(key, value) is a NOP if the key already exists, not even the new value will be used.
    ///
    /// # Examples
    ///
    /// ```
    /// # use cpp_map::LinkedList;
    /// let mut ll = LinkedList::<i8, i8>::default();
    /// ll.ordered_insert(1,1);
    /// assert!(ll.get(ll.head()).is_ok());
    /// assert_eq!(ll.get(ll.head()).unwrap(), (&1,&1));
    /// ll.ordered_insert(0,0);
    /// assert!(ll.get(ll.head()).is_ok());
    /// assert_eq!(ll.get(ll.head()).unwrap(), (&0,&0));
    /// ll.ordered_insert(0,100); // <- this is a NOP
    /// assert!(ll.get(ll.head()).is_ok());
    /// assert_eq!(ll.get(ll.head()).unwrap(), (&0,&0));
    /// ```
    pub fn ordered_insert(&mut self, key: K, value: V) -> Result<usize, MapError> {
        self.ordered_insert_pos(key, value, self.head_)
    }

    /// Insert item by Order (lesser first) with a position hint.
    /// Note that insert(key, value) is a NOP if the key already exists, not even the new value will be used.
    /// # Examples
    ///
    /// ```
    /// # use cpp_map::LinkedList;
    /// let mut ll = LinkedList::<i8, i8>::default();
    /// ll.ordered_insert(1,1);
    /// ll.ordered_insert_pos(2,2,0);
    /// assert!(ll.get(ll.head()).is_ok());
    /// assert_eq!(ll.get(ll.head()).unwrap(), (&1,&1));
    /// assert!(ll.get(ll.tail()).is_ok());
    /// assert_eq!(ll.get(ll.tail()).unwrap(), (&2,&2));
    ///
    /// ```
    pub fn ordered_insert_pos(
        &mut self,
        key: K,
        value: V,
        position: usize,
    ) -> Result<usize, MapError> {
        if self.head_ == OUT_OF_BOUNDS {
            // list is empty, ignore position and insert
            return self.push_back_(key, value);
        }
        //println!("insert at position {}, key={:?} head={}", position, key, self.head_);
        let mut insert_before: Option<usize> = None;

        let (mut curr_index, first_node) = match self.nodes_.get(position) {
            Some(Some(first_node)) => (position, first_node),
            _ => (
                self.head_,
                self.nodes_
                    .get(self.head_)
                    .unwrap()
                    .as_ref()
                    .ok_or_else(|| {
                        MapError::InternalError(format!(
                            "head_ item was None {}:{}",
                            file!(),
                            line!()
                        ))
                    })?,
            ),
        };

        let cmp = key.cmp(&first_node.key_);
        //println!("curr_index:{}, first_node.key={:?}, cmp={:?}", curr_index, first_node.key, cmp);

        #[allow(clippy::collapsible_else_if)] // false positive?
        if (cmp == Ordering::Greater) || (cmp == Ordering::Equal) {
            //println!("search down, insert after equals");
            // we are searching down the list, stop at first Less
            while let Some(Some(sample)) = self.nodes_.get(curr_index) {
                // move past Ordering::Equal
                match key.cmp(&sample.key_) {
                    Ordering::Equal => {
                        return Ok(curr_index); // Insert with an already existing key is a 'nop'
                    }
                    Ordering::Less => {
                        insert_before = Some(curr_index);
                        break;
                    }
                    _ => {
                        curr_index = sample.next_;
                    }
                }
            }
        } else {
            if cmp == Ordering::Less {
                insert_before = Some(curr_index);
            }
            //println!("search up, insert after equals. tmp insert_before:{:?}", insert_before);
            // we are searching up the list, stop at first Equal or Greater
            while let Some(Some(sample)) = self.nodes_.get(curr_index) {
                match key.cmp(&sample.key_) {
                    Ordering::Equal => {
                        return Ok(curr_index); // Insert with an already existing key is a 'nop'
                    }
                    Ordering::Less => {
                        insert_before = Some(curr_index);
                        curr_index = sample.prev_;
                        //println!("continue: curr_index:{}", curr_index);
                    }
                    _ => {
                        //println!("break: insert_before:{:?}", insert_before);
                        break;
                    }
                }
            }
        }

        if let Some(insert_before) = insert_before {
            //println!("inserting before {}", insert_before);
            self.insert_before_(insert_before, key, value)
        } else {
            //println!("pushing at the back");
            self.push_back_(key, value)
        }
    }

    /// Returns the first element in the container whose key is not considered to go
    /// before position (i.e., either it is equivalent or goes after).
    /// If 'search_from_head' is true the search will be performed from the head otherwise from the tail.
    /// Returns None if no data is found
    /// # Examples
    ///
    /// ```
    /// # use cpp_map::LinkedList;
    /// let mut ll = LinkedList::<i8, i8>::default();
    /// ll.ordered_insert(1,1);
    /// ll.ordered_insert(2,2);
    /// ll.ordered_insert(3,3);
    /// let lb = ll.get(ll.lower_bound(2).unwrap().unwrap()).unwrap();
    /// assert_eq!(lb, (&2,&2));
    /// let lb = ll.get(ll.lower_bound(0).unwrap().unwrap()).unwrap();
    /// assert_eq!(lb, (&1,&1));
    /// let lb = ll.get(ll.lower_bound(1).unwrap().unwrap()).unwrap();
    /// assert_eq!(lb, (&1,&1));
    /// let lb = ll.get(ll.lower_bound(3).unwrap().unwrap()).unwrap();
    /// assert_eq!(lb, (&3,&3));
    /// assert!( ll.lower_bound(4).unwrap().is_none());
    /// ```
    pub fn lower_bound(&self, key: K) -> Result<Option<usize>, MapError> {
        #[cfg(feature = "console_debug")]
        {
            let mut iter = self.iter();
            let mut flips = 0_usize;
            let mut last_cmp = iter.next().map(|(first, _)| key.cmp(first));

            for (node, _) in iter {
                let cmp = Some(key.cmp(node));
                if cmp != last_cmp {
                    last_cmp = cmp;
                    flips += 1;
                }
            }
            if flips > 1 {
                println!("\nkey={:?}", key);
                for (n, _) in self.iter() {
                    println!("key.cmp({:?})=={:?}-{:?}", n, n.cmp(&key), key.cmp(n));
                }
            }
        }

        // sequential search from the rear
        if self.tail_ == OUT_OF_BOUNDS {
            return Ok(None);
        }
        let mut last_match: Option<usize> = None;
        let mut curr_index = self.tail_;
        while let Some(Some(sample)) = self.nodes_.get(curr_index) {
            if key.cmp(&sample.key_) != Ordering::Greater {
                //println!("ignoring :{:?} ", sample.key);
                last_match = Some(curr_index);
                curr_index = sample.prev_;
            } else {
                return Ok(last_match);
            }
        }
        Ok(last_match)
    }

    #[inline(always)]
    /// Pop the head item
    ///
    /// # Examples
    /// ```
    /// # use cpp_map::LinkedList;
    /// let mut ll = LinkedList::<i8, i8>::default();
    /// let _ = ll.ordered_insert(1, 0); // 0
    /// let _ = ll.ordered_insert(2, 1); // 1
    /// assert_eq!(ll.pop_front().unwrap().unwrap(), (1_i8,0_i8));
    /// assert_eq!(ll.pop_front().unwrap().unwrap(), (2_i8,1_i8));
    /// ```
    pub fn pop_front(&mut self) -> Result<Option<(K, V)>, MapError> {
        self.remove_(self.head_)
    }

    #[inline(always)]
    /// Pop the tail item
    ///
    /// # Examples
    /// ```
    /// # use cpp_map::LinkedList;
    /// let mut ll = LinkedList::<i8, i8>::default();
    /// let _ = ll.ordered_insert(1, 0); // 0
    /// let _ = ll.ordered_insert(2, 1); // 1
    /// assert_eq!(ll.pop_back().unwrap().unwrap(), (2_i8,1_i8));
    /// assert_eq!(ll.pop_back().unwrap().unwrap(), (1_i8,0_i8));
    /// ```
    pub fn pop_back(&mut self) -> Result<Option<(K, V)>, MapError> {
        self.remove_(self.tail_)
    }

    #[inline(always)]
    /// Peek the head key
    ///
    /// # Examples
    /// ```
    /// # use cpp_map::LinkedList;
    /// let mut ll = LinkedList::<i8, i8>::default();
    /// let _ = ll.ordered_insert(1, 0); // 0
    /// let _ = ll.ordered_insert(2, 1); // 1
    /// assert_eq!(ll.peek_front_k().unwrap(), &1_i8);
    /// ```
    pub fn peek_front_k(&self) -> Option<&K> {
        match self.nodes_.get(self.head_) {
            Some(Some(node)) => Some(&node.key_),
            _ => None,
        }
    }

    #[inline(always)]
    /// Peek the tail key
    ///
    /// # Examples
    /// ```
    /// # use cpp_map::LinkedList;
    /// let mut ll = LinkedList::<i8, i8>::default();
    /// let _ = ll.ordered_insert(1, 0); // 0
    /// let _ = ll.ordered_insert(2, 1); // 1
    /// assert_eq!(ll.peek_back_k().unwrap(), &2_i8);
    /// ```
    pub fn peek_back_k(&self) -> Option<&K> {
        match self.nodes_.get(self.tail_) {
            Some(Some(node)) => Some(&node.key_),
            _ => None,
        }
    }

    #[inline(always)]
    /// Return the tail index
    pub fn tail(&self) -> usize {
        self.tail_
    }

    #[inline(always)]
    /// Return the head index
    pub fn head(&self) -> usize {
        self.head_
    }

    #[inline(always)]
    /// Remove the item at index, return item value if found
    fn remove_(&mut self, index: usize) -> Result<Option<(K, V)>, MapError> {
        let rv = self.remove__(index)?;
        Ok(Some(rv.1))
    }

    /// Disconnect and remove the item at index, return item value if found
    fn remove__(&mut self, index: usize) -> Result<(usize, (K, V), usize), MapError> {
        if self.head_ == OUT_OF_BOUNDS {
            return Err(MapError::InternalError(format!(
                "Could not find element to remove {}:{}",
                file!(),
                line!()
            )));
        }
        //println!("remove {} before:{:?}", index, self);
        let rv = if self.head_ != OUT_OF_BOUNDS {
            // list was not empty
            let operation = if let Some(node) = self.nodes_.get(index) {
                let mut operation = EraseOperation {
                    change_prev_: None,
                    erase_: index,
                    change_next_: None,
                };
                if let Some(node) = node {
                    // Check node next
                    if let Some(next) = self.nodes_.get(node.next_) {
                        if next.is_some() {
                            // node had a next
                            operation.change_next_ = Some((node.next_, node.prev_));
                        } else {
                            return Err(MapError::InternalError(format!(
                                "Should not happen error™ at {}:{}",
                                file!(),
                                line!()
                            )));
                        }
                    }

                    // Check prev node
                    if let Some(prev) = self.nodes_.get(node.prev_) {
                        if prev.is_some() {
                            // node had a prev
                            operation.change_prev_ = Some((node.prev_, node.next_));
                        } else {
                            return Err(MapError::InternalError(format!(
                                "Should not happen error™ at {}:{}",
                                file!(),
                                line!()
                            )));
                        }
                    }
                    Some(operation)
                } else {
                    return Err(MapError::InternalError(format!(
                        "Should not happen error™ at {}:{}",
                        file!(),
                        line!()
                    )));
                }
            } else {
                // index was not found, todo: report error?
                None
            };
            if let Some(operation) = operation {
                Some(self.erase_node_(operation)?)
            } else {
                None
            }
        } else {
            // list was empty
            None
        };
        rv.ok_or_else(|| {
            MapError::InternalError(format!(
                "Could not find element to remove {}:{}",
                file!(),
                line!()
            ))
        })
    }

    /// do the actual erase now that we know how to do it (work around for the borrow checker).
    fn erase_node_(
        &mut self,
        operation: EraseOperation,
    ) -> Result<(usize, (K, V), usize), MapError> {
        //println!("erase_operation {:?}", operation);
        match (operation.change_prev_, operation.change_next_) {
            (Some((prev_i, new_next)), Some((next_i, new_prev))) => {
                #[cfg(feature = "console_debug")]
                {
                    assert_eq!(new_next, next_i);
                    assert_eq!(prev_i, new_prev);
                }
                match self.nodes_.get_mut(prev_i) {
                    Some(Some(node)) => {
                        node.next_ = new_next;
                    }
                    _ => {
                        return Err(MapError::InternalError(format!(
                            "Should not happen error™ at {}:{}",
                            file!(),
                            line!()
                        )))
                    }
                };
                match self.nodes_.get_mut(next_i) {
                    Some(Some(node)) => {
                        node.prev_ = new_prev;
                    }
                    _ => {
                        return Err(MapError::InternalError(format!(
                            "Should not happen error™ at {}:{}",
                            file!(),
                            line!()
                        )))
                    }
                };
            }
            (None, Some((new_head, new_head_prev))) => match self.nodes_.get_mut(new_head) {
                Some(Some(node)) => {
                    node.prev_ = new_head_prev;
                    self.head_ = new_head;
                }
                _ => {
                    return Err(MapError::InternalError(format!(
                        "Should not happen error™ at {}:{}",
                        file!(),
                        line!()
                    )))
                }
            },
            (Some((new_tail, new_tail_next)), None) => match self.nodes_.get_mut(new_tail) {
                Some(Some(node)) => {
                    node.next_ = new_tail_next;
                    self.tail_ = new_tail;
                }
                _ => {
                    return Err(MapError::InternalError(format!(
                        "Should not happen error™ at {}:{}",
                        file!(),
                        line!()
                    )))
                }
            },
            (None, None) => {
                self.head_ = OUT_OF_BOUNDS;
                self.tail_ = OUT_OF_BOUNDS
            }
        }
        match self.nodes_.get_mut(operation.erase_) {
            Some(old_head) => {
                // Replace the node with None
                if let Some(old_head) = old_head.take() {
                    self.id_pool_.push(operation.erase_);
                    return Ok((
                        old_head.prev_,
                        (old_head.key_, old_head.value_),
                        old_head.next_,
                    ));
                }

                return Err(MapError::InternalError(format!(
                    "Should not happen error™ at {}:{}",
                    file!(),
                    line!()
                )));
            }
            _ => {
                return Err(MapError::InternalError(format!(
                    "Should not happen error™, element to erase not found {} at {}:{}",
                    operation.erase_,
                    file!(),
                    line!()
                )))
            }
        }
    }
}

#[derive(Clone, Debug)]
/// A double ended iterator
pub struct ListIterator<'a, K: 'a, V: 'a>
where
    K: Debug,
    V: Debug,
{
    list_: &'a LinkedList<K, V>,
    my_next_: usize,
}

impl<'a, K: 'a, V: 'a> std::iter::Iterator for ListIterator<'a, K, V>
where
    K: Debug,
    V: Debug,
{
    type Item = (&'a K, &'a V);

    #[inline]
    /// Step the iterator forward one step
    fn next(&mut self) -> Option<(&'a K, &'a V)> {
        if self.my_next_ == OUT_OF_BOUNDS {
            return None;
        }
        //println!("Returning value at index:{}", self.my_next);
        if let Some(node) = self.list_.nodes_.get(self.my_next_)? {
            if self.my_next_ == self.list_.tail_ {
                self.my_next_ = OUT_OF_BOUNDS;
            } else {
                self.my_next_ = node.next_
            }
            Some((&node.key_, &node.value_))
        } else {
            self.my_next_ = OUT_OF_BOUNDS;
            None
        }
    }
}

impl<'a, K: 'a, V: 'a> DoubleEndedIterator for ListIterator<'a, K, V>
where
    K: Debug,
    V: Debug,
{
    #[inline]
    /// Step the iterator backward one step
    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
        if let Some(node) = self.list_.nodes_.get(self.my_next_)? {
            if self.my_next_ == self.list_.tail_ {
                self.my_next_ = OUT_OF_BOUNDS;
            } else {
                self.my_next_ = node.prev_
            }
            Some((&node.key_, &node.value_))
        } else {
            self.my_next_ = OUT_OF_BOUNDS;
            None
        }
    }
}

/// An effort to emulate a C++ std::map iterator in Rust.
/// It will have functionality like:
/// prev(), next(), get(), erase(), lower_bound(), replace_key()
pub struct PIterator<K, V>
where
    K: Debug,
    V: Debug,
{
    current: usize,
    list: Rc<RefCell<LinkedList<K, V>>>,
}

#[allow(dead_code)]
impl<K, V> PIterator<K, V>
where
    K: Clone + Debug + Unpin + Ord + PartialOrd,
    V: Clone + Debug + Unpin,
{
    /// Initiates the pointer with a list, set current to the head of the list.
    pub fn new(list: Rc<RefCell<LinkedList<K, V>>>) -> Result<Self, MapError> {
        let head = list.try_borrow()?.head_;
        Ok(Self {
            current: head,
            list,
        })
    }

    /// Initiates the pointer with a list, set index.
    pub fn new_2(list: Rc<RefCell<LinkedList<K, V>>>, current: usize) -> Self {
        Self { current, list }
    }

    #[inline(always)]
    /// Returns a clone of the key at current position
    pub fn get_k(&self) -> Result<K, MapError> {
        Ok(self.list.try_borrow()?.get(self.current)?.0.clone())
    }

    #[inline(always)]
    /// Returns a clone of the value at current position
    pub fn get_v(&self) -> Result<V, MapError> {
        Ok(self.list.try_borrow()?.get(self.current)?.1.clone())
    }

    #[allow(clippy::should_implement_trait)]
    #[inline(always)]
    /// Move to the next element.
    /// Note that this is NOT a Rust iterator next() method.
    /// Always check validity of the iterator with is_ok() after next()
    // todo: change the return value to Result<bool, MapError>
    pub fn next(&mut self) -> Result<(), MapError> {
        let list_borrow = self.list.try_borrow()?;
        match list_borrow.nodes_.get(self.current) {
            Some(Some(node)) => self.current = node.next_,
            // Some(None) nodes should be inaccessible
            Some(None) => {
                return Err(MapError::InternalError(format!(
                    "next() failed at index:{}. {}:{}",
                    self.current,
                    file!(),
                    line!()
                )));
            }
            None => self.current = OUT_OF_BOUNDS,
        }
        Ok(())
    }

    #[inline(always)]
    /// Move to the previous element
    /// Always check validity of the iterator with is_ok() after prev()
    // todo: change the return value to Result<bool, MapError>
    pub fn prev(&mut self) -> Result<(), MapError> {
        let list_borrow = self.list.try_borrow()?;
        match list_borrow.nodes_.get(self.current) {
            Some(Some(node)) => self.current = node.prev_,
            // Some(None) nodes should be inaccessible
            Some(None) => {
                return Err(MapError::InternalError(format!(
                    "prev() failed at index:{}. {}:{}",
                    self.current,
                    file!(),
                    line!()
                )));
            }
            None => self.current = OUT_OF_BOUNDS,
        }
        Ok(())
    }

    #[inline(always)]
    /// Move to the first element
    pub fn move_to_head(&mut self) -> Result<(), MapError> {
        self.current = self.list.try_borrow()?.head_;
        Ok(())
    }

    #[inline(always)]
    /// Move to the last element
    pub fn move_to_tail(&mut self) -> Result<(), MapError> {
        self.current = self.list.try_borrow()?.tail_;
        Ok(())
    }

    #[inline(always)]
    /// Return true if pointer has *NOT* moved past beginning or end of the list
    pub fn is_ok(&self) -> Result<bool, MapError> {
        Ok(self.current != OUT_OF_BOUNDS
            && matches!(
                self.list.try_borrow()?.nodes_.get(self.current),
                Some(Some(_))
            ))
    }

    #[inline(always)]
    /// Return true if pointer is at head position or if the list is empty
    pub fn is_at_head(&self) -> Result<bool, MapError> {
        Ok(self.current == self.list.try_borrow()?.head_)
    }

    #[inline(always)]
    /// Return true if pointer is at tail position or if the list is empty
    pub fn is_at_tail(&self) -> Result<bool, MapError> {
        Ok(self.current == self.list.try_borrow()?.tail_)
    }

    #[inline(always)]
    /// Replace current key. This will destroy the internal order of element if you
    /// replace an element with something out of order.
    pub fn replace_key(&mut self, key: K) -> Result<(), MapError> {
        let mut list = std::pin::Pin::new(self.list.try_borrow_mut()?);
        if let Some(Some(ref mut node)) = list.nodes_.get_mut(self.current) {
            node.key_ = key;
        }
        Ok(())
    }

    #[inline(always)]
    /// returns current index
    pub fn current(&self) -> usize {
        self.current
    }

    #[inline(always)]
    /// Remove the current element and return it. Move current to the old prev value if exist.
    /// Else pick old next index.
    /// Note: make sure that there are no other Pointer objects at this position.
    pub fn remove_current(&mut self) -> Result<(K, V), MapError> {
        let rv = self.list.try_borrow_mut()?.remove__(self.current)?;
        if rv.0 != OUT_OF_BOUNDS {
            self.current = rv.0;
        } else {
            self.current = rv.2;
        }
        Ok(rv.1)
    }

    #[inline(always)]
    /// Returns a new Pointer positioned at the lower bound item.
    /// Lower bound item is the first element in the container whose key is not considered to go
    /// before position (i.e., either it is equivalent or goes after).
    /// Returns a Pointer where is_ok() returns false if no data is found
    pub fn lower_bound(list: Rc<RefCell<LinkedList<K, V>>>, key: K) -> Result<Self, MapError> {
        let position = list.try_borrow()?.lower_bound(key)?;
        if let Some(position) = position {
            Ok(Self {
                list,
                current: position,
            })
        } else {
            // Return a Pointer that is out of bounds
            Ok(Self {
                list,
                current: OUT_OF_BOUNDS,
            })
        }
    }
}

impl<K, V> Debug for PIterator<K, V>
where
    K: Debug + Unpin + Ord + PartialOrd,
    V: Debug + Unpin,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        writeln!(f, "PIterator({})", self.current)
    }
}

impl<K, V> Clone for PIterator<K, V>
where
    K: Debug + Unpin + Ord + PartialOrd,
    V: Debug + Unpin,
{
    fn clone(&self) -> Self {
        Self {
            current: self.current,
            list: Rc::clone(&self.list),
        }
    }
}