Skip to content

Instantly share code, notes, and snippets.

@Amanieu
Created April 1, 2021 07:30
Show Gist options
  • Save Amanieu/fd7b7b1e06019dadacd0a8937caf8f55 to your computer and use it in GitHub Desktop.
Save Amanieu/fd7b7b1e06019dadacd0a8937caf8f55 to your computer and use it in GitHub Desktop.
/// 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
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment