bitstring_trees/tree/mut_borrowed/walk.rs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
use crate::{
tree::{
mut_gen::{
Borrowed,
WalkMut,
WalkMutPath,
},
InsertPosition,
Node,
TreeProperties,
WalkedDirection,
},
walk_mut::NodeOrTree,
};
use super::{
IterMutBorrowedInOrder,
IterMutBorrowedLeaf,
IterMutBorrowedLeafFull,
IterMutBorrowedPostOrder,
IterMutBorrowedPreOrder,
};
/// Walk borrowed mutable tree up and down
///
/// Some algorithms need to remember how they reached the current node via [`WalkedDirection`] as `D`.
///
/// When walking manually it might be useful to be able to store additional data via `A`.
pub struct WalkMutBorrowed<'r, TP: TreeProperties + 'r, D = (), A = ()> {
pub(in crate::tree) inner: WalkMut<'r, TP, Borrowed, D, A>,
}
impl<'r, TP, D, A> WalkMutBorrowed<'r, TP, D, A>
where
TP: TreeProperties,
{
/// Walk up to parent node or tree if not at tree
pub fn up(&mut self) -> Option<D> {
self.inner.up()
}
/// Walk up to parent node or tree if not at tree
pub fn up_with(&mut self) -> Option<(D, A)> {
self.inner.up_with()
}
/// Current node or tree
pub fn current(&self) -> NodeOrTree<Option<&Node<TP>>, &Node<TP>> {
self.inner.current()
}
/// Current mutable node or tree
///
/// If you need the result to outlive the destruction of the [`WalkMutBorrowed`] value, see [`into_current_mut`].
///
/// [`into_current_mut`]: WalkMutBorrowed::into_current_mut
pub fn current_mut(&mut self) -> NodeOrTree<Option<&mut Node<TP>>, &mut Node<TP>> {
self.inner.current_mut()
}
/// Extract mutable node or tree
///
/// Also see [`current_mut`]
///
/// [`current_mut`]: WalkMutBorrowed::current_mut
pub fn into_current_mut(self) -> NodeOrTree<Option<&'r mut Node<TP>>, &'r mut Node<TP>> {
self.inner.into_current_mut()
}
}
impl<'r, TP, D, A> WalkMutBorrowed<'r, TP, D, A>
where
TP: TreeProperties + 'r,
D: From<WalkedDirection>,
{
/// Walk down from tree to root node (if at tree and not empty)
pub fn down_root_with(&mut self, add: A) -> bool {
self.inner.down_root_with(add)
}
/// Walk down to left node if present and not currently at tree
pub fn down_left_with(&mut self, add: A) -> bool {
self.inner.down_left_with(add)
}
/// Walk down to right node if present and not currently at tree
pub fn down_right_with(&mut self, add: A) -> bool {
self.inner.down_right_with(add)
}
/// Walk down to specified node if present and not currently at tree
///
/// `false` picks left and `true` picks right.
pub fn down_with(&mut self, side: bool, add: A) -> bool {
self.inner.down_with(side, add)
}
}
impl<'r, TP, D> WalkMutBorrowed<'r, TP, D, ()>
where
TP: TreeProperties + 'r,
D: From<WalkedDirection>,
{
/// Walk down from tree to root node (if at tree and not empty)
pub fn down_root(&mut self) -> bool {
self.inner.down_root()
}
/// Walk down to left node if present and not currently at tree
pub fn down_left(&mut self) -> bool {
self.inner.down_left()
}
/// Walk down to right node if present and not currently at tree
pub fn down_right(&mut self) -> bool {
self.inner.down_right()
}
/// Walk down to specified node if present and not currently at tree
///
/// `false` picks left and `true` picks right.
pub fn down(&mut self, side: bool) -> bool {
self.inner.down(side)
}
}
impl<'r, TP, D> WalkMutBorrowed<'r, TP, D>
where
TP: TreeProperties + 'r,
D: From<WalkedDirection>,
{
/// Start iterator to walk to deepest node that is a prefix of the target key
///
/// While consuming the iterator the stack is updated with the position of the returned nodes.
///
/// When `self` was in a mismatching subtree (i.e. not a prefix of the target key) before
/// the iterator won't find anything.
pub fn path(&mut self, key: TP::Key) -> WalkMutBorrowedPath<'r, '_, TP, D> {
WalkMutBorrowedPath {
inner: self.inner.path(key),
}
}
/// Walk to node where we'd have to insert key at
///
/// Returns `None` if tree is empty.
pub fn goto_insert(&mut self, key: &TP::Key) -> Option<InsertPosition> {
self.inner.goto_insert(key)
}
}
impl<'r, TP> WalkMutBorrowed<'r, TP, WalkedDirection, ()>
where
TP: TreeProperties + 'r,
{
/// Convert into iterator traversing depth-first pre-order
pub fn into_iter_pre_order(self) -> IterMutBorrowedPreOrder<'r, TP> {
self.inner.into_iter_pre_order().into()
}
/// Tree traversal: depth-first pre-order
pub fn next_pre_order(&mut self) -> Option<&mut Node<TP>> {
self.inner.next_pre_order()
}
/// Convert into iterator traversing depth-first in-order
pub fn into_iter_in_order(self) -> IterMutBorrowedInOrder<'r, TP> {
self.inner.into_iter_in_order().into()
}
/// Tree traversal: depth-first in-order
pub fn next_in_order(&mut self) -> Option<&mut Node<TP>> {
self.inner.next_in_order()
}
/// Convert into iterator traversing depth-first post-order
pub fn into_iter_post_order(self) -> IterMutBorrowedPostOrder<'r, TP> {
self.inner.into_iter_post_order().into()
}
/// Tree traversal: depth-first post-order
pub fn next_post_order(&mut self) -> Option<&mut Node<TP>> {
self.inner.next_post_order()
}
/// Convert into iterator over all leafs
pub fn into_iter_leafs(self) -> IterMutBorrowedLeaf<'r, TP> {
self.inner.into_iter_leafs().into()
}
/// Convert into iterator over all leafs and uncovered parts
pub fn into_iter_full_leafs(self) -> IterMutBorrowedLeafFull<'r, TP> {
self.inner.into_iter_full_leafs().into()
}
/// Tree traversal: depth-first in-order leaf nodes only
pub fn next_leaf(&mut self) -> Option<&mut Node<TP>> {
self.inner.next_leaf()
}
}
/// Iterate over all nodes that are a prefix of target key in a [`WalkMutBorrowed`] stack
pub struct WalkMutBorrowedPath<'r, 'w, TP, D = ()>
where
TP: TreeProperties + 'r,
{
inner: WalkMutPath<'r, 'w, TP, Borrowed, D>,
}
impl<'r, 'w, TP, D> WalkMutBorrowedPath<'r, 'w, TP, D>
where
TP: TreeProperties + 'r,
D: From<WalkedDirection>,
{
/// Next step towards target node
#[allow(clippy::should_implement_trait)] // iterator doesn't allow using lifetime of itself in item
pub fn next(&mut self) -> Option<&mut Node<TP>> {
self.inner.next()
}
}
/*
impl<'r, 'w, TP, D> IntoIterator for WalkMutOwnedPath<'r, 'w, TP, D>
where
TP: TreeProperties + 'r,
D: From<WalkedDirection>,
{
type IntoIter = IterWalkMutOwnedPath<'r, 'w, TP, D>;
type Item = (
&'r TP::Key,
&'r mut TP::Value,
Option<&'r mut TP::LeafValue>,
);
fn into_iter(self) -> Self::IntoIter {
IterWalkMutOwnedPath::new(self)
}
}
*/