btree_cursor.rs

/// A cursor over a `BTreeMap`.
///
/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
///
/// Cursors always rest between two elements in the tree, and index in a logically circular way.
/// To accommodate this, there is a "ghost" non-element that yields `None` between the last and
/// first elements of the tree.
///
/// When created, cursors start at the front of the tree, or the "ghost" non-element if the tree is empty.
#[unstable(feature = "btree_cursors", issue = "none")]
pub struct Cursor<'a, K: 'a, V: 'a> {
    current: Option<Handle<NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>, marker::KV>>,
    root: Option<&'a node::Root<K, V>>,
}

#[unstable(feature = "btree_cursors", issue = "none")]
impl<K, V> Clone for Cursor<'_, K, V> {
    fn clone(&self) -> Self {
        let Cursor { current, root } = *self;
        Cursor { current, root }
    }
}

enum CursorMutInner<'a, K: 'a, V: 'a> {
    Elem(Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>),
    Ghost(&'a mut node::Root<K, V>),
    EmptyTree(&'a mut Option<node::Root<K, V>>),
}

/// A cursor over a `BTreeMap` with editing operations.
///
/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
/// safely mutate the tree during iteration. This is because the lifetime of its yielded
/// references is tied to its own lifetime, instead of just the underlying tree. This means
/// cursors cannot yield multiple elements at once.
///
/// Cursors always rest between two elements in the tree, and index in a logically circular way.
/// To accommodate this, there is a "ghost" non-element that yields `None` between the last and
/// first elements of the tree.
#[unstable(feature = "btree_cursors", issue = "none")]
pub struct CursorMut<'a, K: 'a, V: 'a> {
    inner: CursorMutInner<'a, K, V>,
    length: &'a mut usize,
}

impl<'a, K, V> Cursor<'a, K, V> {
    /// Moves the cursor to the next element of the `BTreeMap`.
    ///
    /// If the cursor is pointing to the "ghost" non-element then this will move it to
    /// the first element of the `BTreeMap`. If it is pointing to the last
    /// element of the `BTreeMap` then this will move it to the "ghost" non-element.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn move_next(&mut self) {
        match self.current.take() {
            None => {
                self.current = self.root.as_ref().and_then(|root| {
                    root.as_ref().first_leaf_edge().forget_node_type().right_kv().ok()
                });
            }
            Some(current) => {
                self.current = current.next_leaf_edge().next_kv().ok();
            }
        }
    }

    /// Moves the cursor to the previous element of the `BTreeMap`.
    ///
    /// If the cursor is pointing to the "ghost" non-element then this will move it to
    /// the last element of the `BTreeMap`. If it is pointing to the first
    /// element of the `BTreeMap` then this will move it to the "ghost" non-element.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn move_prev(&mut self) {
        match self.current.take() {
            None => {
                self.current = self.root.as_ref().and_then(|root| {
                    root.as_ref().last_leaf_edge().forget_node_type().left_kv().ok()
                });
            }
            Some(current) => {
                self.current = current.next_back_leaf_edge().next_back_kv().ok();
            }
        }
    }

    /// Returns a reference to the key of the element that the cursor is
    /// currently pointing to.
    ///
    /// This returns `None` if the cursor is currently pointing to the
    /// "ghost" non-element.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn key(&self) -> Option<&'a K> {
        self.current.as_ref().map(|current| current.into_kv().0)
    }

    /// Returns a reference to the value of the element that the cursor is
    /// currently pointing to.
    ///
    /// This returns `None` if the cursor is currently pointing to the
    /// "ghost" non-element.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn value(&self) -> Option<&'a V> {
        self.current.as_ref().map(|current| current.into_kv().1)
    }
    /*
    /// Returns a reference to the next element.
    ///
    /// If the cursor is pointing to the "ghost" non-element then this returns
    /// the first element of the `LinkedList`. If it is pointing to the last
    /// element of the `LinkedList` then this returns `None`.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn peek_next(&self) -> Option<(&'a K, &'a V)> {
        unsafe {
            let next = match self.current {
                None => self.list.head,
                Some(current) => current.as_ref().next,
            };
            next.map(|next| &(*next.as_ptr()).element)
        }
    }

    /// Returns a reference to the previous element.
    ///
    /// If the cursor is pointing to the "ghost" non-element then this returns
    /// the last element of the `LinkedList`. If it is pointing to the first
    /// element of the `LinkedList` then this returns `None`.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn peek_prev(&self) -> Option<&'a T> {
        unsafe {
            let prev = match self.current {
                None => self.list.tail,
                Some(current) => current.as_ref().prev,
            };
            prev.map(|prev| &(*prev.as_ptr()).element)
        }
    }*/
}

impl<'a, K, V> CursorMut<'a, K, V> {
    /// Moves the cursor to the next element of the `BTreeMap`.
    ///
    /// If the cursor is pointing to the "ghost" non-element then this will move it to
    /// the first element of the `BTreeMap`. If it is pointing to the last
    /// element of the `BTreeMap` then this will move it to the "ghost" non-element.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn move_next(&mut self) {
        match unsafe { ptr::read(&self.inner) } {
            CursorMutInner::Ghost(root) => {
                if let Ok(first) = root.as_mut().first_leaf_edge().forget_node_type().right_kv() {
                    self.inner = CursorMutInner::Elem(first);
                }
            }
            CursorMutInner::Elem(current) => {
                self.inner = match current.next_leaf_edge().next_kv() {
                    Ok(next) => CursorMutInner::Elem(next),
                    Err(root) => CursorMutInner::Ghost(root.into_root_mut()),
                }
            }
            CursorMutInner::EmptyTree(_) => {}
        }
    }

    /// Moves the cursor to the previous element of the `BTreeMap`.
    ///
    /// If the cursor is pointing to the "ghost" non-element then this will move it to
    /// the last element of the `BTreeMap`. If it is pointing to the first
    /// element of the `BTreeMap` then this will move it to the "ghost" non-element.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn move_prev(&mut self) {
        match unsafe { ptr::read(&self.inner) } {
            CursorMutInner::Ghost(root) => {
                if let Ok(last) = root.as_mut().last_leaf_edge().forget_node_type().left_kv() {
                    self.inner = CursorMutInner::Elem(last);
                }
            }
            CursorMutInner::Elem(current) => {
                self.inner = match current.next_back_leaf_edge().next_back_kv() {
                    Ok(next) => CursorMutInner::Elem(next),
                    Err(root) => CursorMutInner::Ghost(root.into_root_mut()),
                }
            }
            CursorMutInner::EmptyTree(_) => {}
        }
    }

    /// Returns a reference to the key of the element that the cursor is
    /// currently pointing to.
    ///
    /// This returns `None` if the cursor is currently pointing to the
    /// "ghost" non-element.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn key(&self) -> Option<&K> {
        match &self.inner {
            CursorMutInner::Elem(current) => Some(current.reborrow().into_kv().0),
            _ => None,
        }
    }

    /// Returns a reference to the value of the element that the cursor is
    /// currently pointing to.
    ///
    /// This returns `None` if the cursor is currently pointing to the
    /// "ghost" non-element.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn value(&self) -> Option<&V> {
        match &self.inner {
            CursorMutInner::Elem(current) => Some(current.reborrow().into_kv().1),
            _ => None,
        }
    }

    /// Returns a mutable reference to the value of the element that the cursor
    /// is currently pointing to.
    ///
    /// This returns `None` if the cursor is currently pointing to the
    /// "ghost" non-element.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn value_mut(&mut self) -> Option<&mut V> {
        match &mut self.inner {
            CursorMutInner::Elem(current) => Some(current.kv_mut().1),
            _ => None,
        }
    }
    /*
    /// Returns a reference to the next element.
    ///
    /// If the cursor is pointing to the "ghost" non-element then this returns
    /// the first element of the `LinkedList`. If it is pointing to the last
    /// element of the `LinkedList` then this returns `None`.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn peek_next(&mut self) -> Option<&mut T> {
        unsafe {
            let next = match self.current {
                None => self.list.head,
                Some(current) => current.as_ref().next,
            };
            next.map(|next| &mut (*next.as_ptr()).element)
        }
    }

    /// Returns a reference to the previous element.
    ///
    /// If the cursor is pointing to the "ghost" non-element then this returns
    /// the last element of the `LinkedList`. If it is pointing to the first
    /// element of the `LinkedList` then this returns `None`.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn peek_prev(&mut self) -> Option<&mut T> {
        unsafe {
            let prev = match self.current {
                None => self.list.tail,
                Some(current) => current.as_ref().prev,
            };
            prev.map(|prev| &mut (*prev.as_ptr()).element)
        }
    }*/

    /// Returns a read-only cursor pointing to the current element.
    ///
    /// The lifetime of the returned `Cursor` is bound to that of the
    /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
    /// `CursorMut` is frozen for the lifetime of the `Cursor`.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn as_cursor(&self) -> Cursor<'_, K, V> {
        unimplemented!()
        //Cursor { tree: self.tree, current: self.current.as_ref().map(|current| current.reborrow()) }
    }
}

// Now the tree editing operations
impl<'a, K: Ord, V> CursorMut<'a, K, V> {
    /// Inserts a new element into the `LinkedList` after the current one.
    ///
    /// If the cursor is pointing at the "ghost" non-element then the new element is
    /// inserted at the front of the `LinkedList`.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn insert_after_unchecked(&mut self, key: K, value: V) {
        *self.length += 1;
        let handle = match unsafe { ptr::read(&self.inner) } {
            CursorMutInner::Elem(current) => current.next_leaf_edge(),
            CursorMutInner::Ghost(root) => root.as_mut().first_leaf_edge(),
            CursorMutInner::EmptyTree(root) => {
                let root = BTreeMap::ensure_is_owned(root);
                self.inner = CursorMutInner::Ghost(root);
                match self.inner {
                    CursorMutInner::Ghost(ref root) => unsafe {
                        ptr::read(root).as_mut().first_leaf_edge()
                    },
                    _ => unreachable!(),
                }
            }
        };
        VacantEntry { key, handle, length: &mut self.length, _marker: PhantomData }.insert(value);
    }

    /// Inserts a new element into the `LinkedList` before the current one.
    ///
    /// If the cursor is pointing at the "ghost" non-element then the new element is
    /// inserted at the end of the `LinkedList`.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn insert_before_unchecked(&mut self, key: K, value: V) {
        *self.length += 1;
        let handle = match unsafe { ptr::read(&self.inner) } {
            CursorMutInner::Elem(current) => current.next_back_leaf_edge(),
            CursorMutInner::Ghost(root) => root.as_mut().last_leaf_edge(),
            CursorMutInner::EmptyTree(root) => {
                let root = BTreeMap::ensure_is_owned(root);
                self.inner = CursorMutInner::Ghost(root);
                match self.inner {
                    CursorMutInner::Ghost(ref root) => unsafe {
                        ptr::read(root).as_mut().last_leaf_edge()
                    },
                    _ => unreachable!(),
                }
            }
        };
        VacantEntry { key, handle, length: &mut self.length, _marker: PhantomData }.insert(value);
    }

    /// Removes the current element from the `LinkedList`.
    ///
    /// The element that was removed is returned, and the cursor is
    /// moved to point to the next element in the `LinkedList`.
    ///
    /// If the cursor is currently pointing to the "ghost" non-element then no element
    /// is removed and `None` is returned.
    #[unstable(feature = "btree_cursors", issue = "none")]
    pub fn remove_current(&mut self) -> Option<(K, V)> {
        *self.length -= 1;
        if let CursorMutInner::Elem(handle) = unsafe { ptr::read(&self.inner) } {
            let (k, v, edge) = handle.remove_kv_tracking();
            self.inner = match edge.next_kv() {
                Ok(handle) => CursorMutInner::Elem(handle),
                Err(root) => CursorMutInner::Ghost(root.into_root_mut()),
            };
            Some((k, v))
        } else {
            None
        }
    }
}