bitstring_trees/tree/mut_owned/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 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312
use crate::{
tree::{
mut_gen::{
Owned,
WalkMut,
WalkMutPath,
},
InsertPosition,
Node,
TreeProperties,
WalkedDirection,
},
walk_mut::NodeOrTree,
};
use super::{
IterMutOwnedInOrder,
IterMutOwnedLeaf,
IterMutOwnedLeafFull,
IterMutOwnedPostOrder,
IterMutOwnedPreOrder,
};
/// Walk owned 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 WalkMutOwned<'r, TP: TreeProperties + 'r, D = (), A = ()> {
pub(in crate::tree) inner: WalkMut<'r, TP, Owned, D, A>,
}
impl<'r, TP, D, A> WalkMutOwned<'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 [`WalkMutOwned`] value, see [`into_current_mut`].
///
/// [`into_current_mut`]: WalkMutOwned::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`]: WalkMutOwned::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> WalkMutOwned<'r, TP, WalkedDirection, ()>
where
TP: TreeProperties + 'r,
{
/// Delete current node (or tree)
///
/// Afterwards the current node is the previous parent node, which was replaced by the sibling,
/// or the (empty) tree when removing the last node.
///
/// Returns what [`up_with`] would have returned.
///
/// [`up_with`]: WalkMutOwned::up_with
pub fn delete_current(&mut self) -> Option<WalkedDirection> {
self.inner.delete_current()
}
}
impl<'r, TP, A> WalkMutOwned<'r, TP, WalkedDirection, A>
where
TP: TreeProperties + 'r,
{
/// Delete current node (or tree)
///
/// Afterwards the current node is the previous parent node, which was replaced by the sibling,
/// or the (empty) tree when removing the last node.
///
/// Returns what [`up_with`] would have returned.
///
/// [`up_with`]: WalkMutOwned::up_with
pub fn delete_current_with(&mut self) -> Option<(WalkedDirection, A)> {
self.inner.delete_current_with()
}
/// Remove empty leaf nodes if possible
///
/// A node is considered "empty" if the passed function considers its value empty.
///
/// Calls this if the current value might just have become empty.
///
/// Empty leafs can only be removed if the parent node is empty too, or
/// both siblings are empty leafs (then the parent becomes a leaf node).
///
/// * if current node isn't empty nothing changes
/// * if current node is an empty leaf node:
/// * parent and sibling shouldn't have both been empty, as previous [`compact_if_empty`] calls would have cleaned that up
/// * if parent is empty: remove leaf and parent, replace parent with sibling. `current` points to sibling afterwards.
/// * if sibling is an empty leaf: make parent a leaf, `current` points to parent afterwards.
/// * otherwise no tree changes, but `current` points to parent afterwards.
/// * if current node has an empty leaf child node, remove that child node and current node.
/// I.e. replace current node with other child; `current` points to that child afterwards.
/// Other child node shouldn't be an empty leaf, as previous [`compact_if_empty`] calls would have cleaned that up.
/// * if current points to tree or root node, clear tree if it is an empty node
///
/// [`compact_if_empty`]: Self::compact_if_empty
pub fn compact_if_empty<F>(&mut self, is_empty: F)
where
F: Fn(&TP::Value) -> bool,
{
self.inner.compact_if_empty(is_empty)
}
}
impl<'r, TP, D, A> WalkMutOwned<'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> WalkMutOwned<'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> WalkMutOwned<'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) -> WalkMutOwnedPath<'r, '_, TP, D> {
WalkMutOwnedPath {
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, D> WalkMutOwned<'r, TP, D>
where
TP: TreeProperties + 'r,
D: From<WalkedDirection>,
{
/// Insert new (possibly inner) node with exact key in tree, walk to it and return reference to it
pub fn insert(&mut self, key: TP::Key) -> &mut Node<TP> {
self.inner.insert(key)
}
}
impl<'r, TP> WalkMutOwned<'r, TP, WalkedDirection, ()>
where
TP: TreeProperties + 'r,
{
/// Convert into iterator traversing depth-first pre-order
pub fn into_iter_pre_order(self) -> IterMutOwnedPreOrder<'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) -> IterMutOwnedInOrder<'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) -> IterMutOwnedPostOrder<'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) -> IterMutOwnedLeaf<'r, TP> {
self.inner.into_iter_leafs().into()
}
/// Convert into iterator over all leafs and uncovered parts
pub fn into_iter_full_leafs(self) -> IterMutOwnedLeafFull<'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 [`WalkMutOwned`] stack
pub struct WalkMutOwnedPath<'r, 'w, TP, D = ()>
where
TP: TreeProperties + 'r,
{
inner: WalkMutPath<'r, 'w, TP, Owned, D>,
}
impl<'r, 'w, TP, D> WalkMutOwnedPath<'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)
}
}
*/