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 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443
//! The trees module.
//! This module contains:
//! * Traits that all implementations of trees should implement
//! * Specific implementations of trees
//!
//! The [`SomeWalker`] trait implements traversing a tree. This includes dealing with the borrow
//! checking problems of recursive structures (using [`recursive_reference`]), and rebalancing the tree.
//! Therefore, walkers can't guarantee that the tree won't change as you walk through them.
#[macro_use]
mod macros;
mod segment_algorithms;
pub mod avl;
pub mod basic_tree;
pub mod slice;
pub mod splay;
pub mod treap;
use crate::data::*;
use crate::locators;
/// Used to specify sidedness
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
#[allow(missing_docs)]
pub enum Side {
Left,
Right,
}
impl Side {
/// Flips the side
pub fn flip(self) -> Self {
match self {
Side::Left => Self::Right,
Side::Right => Self::Left,
}
}
}
/// This trait is the top-level trait that the different trees implement.
/// Every tree that implements this trait can be used directly by the functions
/// immediately in this trait.
/// More advanced use can be achieved by using walkers, which must be implemented.
pub trait SomeTree<D: Data>:
SomeEntry<D> + std::iter::FromIterator<D::Value> + IntoIterator<Item = D::Value> + Default
where
for<'a> &'a mut Self: SomeTreeRef<D>,
{
/// Compute the summary of a subsegment.
/// Requires `D::Value: Clone`.
///
/// Note: calling this on splay trees is inefficient
/// and panicks in debug builds.
/// (see documentation on splay tree's version of this function)
fn segment_summary_imm<L>(&self, locator: L) -> D::Summary
where
L: locators::Locator<D>,
D::Value: Clone;
/// Compute the summary of a subsegment.
/// Requires mutable access.
fn segment_summary<L>(&mut self, locator: L) -> D::Summary
where
L: locators::Locator<D>;
/// Apply an action on a subsegment.
fn act_segment<L>(&mut self, action: D::Action, locator: L)
where
L: locators::Locator<D>;
/// Returns a value representing a specific subsegment of the tree. This gives a nicer
/// Interface for tree operations: `tree.slice(3..50).act(action)` instead of
/// `tree.act_segment(3..50, action)`. see [`slice::Slice`].
fn slice<L: locators::Locator<D>>(&mut self, locator: L) -> slice::Slice<D, Self, L> {
slice::Slice::new(self, locator)
}
/// This is here just so that the signature for iter_locator can be written out. Don't use this.
type TreeData;
/// Iterating on values.
/// This iterator assumes you won't change the values using interior mutability. If you change the values,
/// The tree summaries will behave incorrectly.
///
/// See documentation in [`basic_tree::iterators`] as to why this function receives a `&mut self`
/// instead of `&Self` input, and why there isn't a mutable iterator.
///```
/// use grove::{SomeTree, basic_tree::BasicTree};
/// use grove::example_data::StdNum;
///
/// let mut tree: BasicTree<StdNum> = (20..80).collect();
/// let segment_iter = tree.iter_locator(3..13);
///
/// assert_eq!(segment_iter.cloned().collect::<Vec<_>>(), (23..33).collect::<Vec<_>>());
/// # tree.assert_correctness();
///```
fn iter_locator<'a, L: locators::Locator<D>>(
&'a mut self,
locator: L,
) -> basic_tree::iterators::IterLocator<'a, D, L, Self::TreeData>;
/// Iterates over the whole tree.
///```
/// use grove::{SomeTree, basic_tree::BasicTree};
/// use grove::example_data::StdNum;
///
/// let mut tree: BasicTree<StdNum> = (17..=89).collect();
///
/// assert_eq!(tree.iter().cloned().collect::<Vec<_>>(), (17..=89).collect::<Vec<_>>());
/// # tree.assert_correctness();
///```
fn iter(
&mut self,
) -> basic_tree::iterators::IterLocator<'_, D, std::ops::RangeFull, Self::TreeData> {
self.iter_locator(..)
}
/// Used for testing purposes.
/// Should panic if the invariants aren't satisfied.
fn assert_correctness(&self)
where
D::Summary: Eq;
}
/// This is a workaround for not having Generic Associated Types in Rust yet.
/// Really, the type [`Self::Walker`] should have been defined in [`SomeTree`] and
/// should have been generic in a lifetime parameter.
pub trait SomeTreeRef<D: Data> {
/// The walker type associated with this tree.
/// for example, if `Self = &'a AVLTreee<D>` then `Self::Walker = AVLWalker<'a>`.
/// The walker's lifetime comes from `Self`'s lifetime.
type Walker: SomeWalker<D>;
/// Creates a walker for the given tree.
fn walker(self) -> Self::Walker;
/// Finds any node that the locator `Accept`s.
/// If there isn't any, it finds the empty location where that node would be instead.
/// Returns a walker at the wanted position.
fn search<L>(self, locator: L) -> Self::Walker
where
L: locators::Locator<D>,
Self: Sized,
{
let mut walker = self.walker();
walker.search_subtree(locator);
walker
}
}
/// The Walker trait implements walking through a tree.
/// This includes dealing with the borrow checking problems of recursive structures (using Telescope),
/// and rebalancing the tree.
/// Therefore, walkers can't guarantee that the tree won't change as you walk through them.
///
/// The walker should be able to walk on any of the existing nodes, or any empty position just near them.
/// i.e., The walker can also be in the position of a son of an existing node, where there isn't
/// a node yet.
/// The method [`SomeEntry::is_empty()`] can tell whether you are at an empty position. Trying to move downward from an
/// empty position produces an error value.
pub trait SomeWalker<D: Data>: SomeEntry<D> {
/// Returns the current depth in the tree.
/// The convention is, the root is at depth zero
fn depth(&self) -> usize;
/// This function is here since only walkers can guarantee that the current value
/// is clean.
fn value(&self) -> Option<&D::Value>;
/// return `Err(())` if it is in an empty spot.
fn go_left(&mut self) -> Result<(), ()>;
/// returns `Err(())` if it is in an empty spot.
fn go_right(&mut self) -> Result<(), ()>;
/// If successful, returns whether or not the previous current value was the left son.
/// If already at the root of the tree, returns `Err(())`.
fn go_up(&mut self) -> Result<Side, ()>;
/// Goes to the root.
/// May restructure the tree while doing so. For example, in splay trees,
/// this splays the current node.
fn go_to_root(&mut self) {
while self.go_up().is_ok() {}
}
/// If the walker is at an empty position, return an error.
/// Goes to the next empty position.
///
/// May restructure the tree while doing so.
fn next_empty(&mut self) -> Result<(), ()> {
if self.is_empty() {
self.next_filled()?; // if already at the last empty node, returns error here.
}
// can't panic - already checked that position is nonempty
self.go_right().expect("Expected nonempty position");
while !self.is_empty() {
self.go_left().unwrap();
}
Ok(())
}
/// If the walker is at an empty position, return an error.
/// Goes to the previous empty position.
///
/// May restructure the tree while doing so.
fn previous_empty(&mut self) -> Result<(), ()> {
if self.is_empty() {
self.previous_filled()?; // if already at the first empty node, returns error here.
}
// can't panic - already checked that position is nonempty
self.go_left().expect("Expected nonempty position");
while !self.is_empty() {
self.go_right().unwrap();
}
Ok(())
}
/// Finds the next filled node.
/// If there isn't any, moves to root and return Err(()).
///
/// May restructure the tree while doing so.
fn next_filled(&mut self) -> Result<(), ()> {
if !self.is_empty() {
self.next_empty().unwrap();
}
loop {
match self.go_up() {
Ok(Side::Left) => break,
Ok(Side::Right) => (),
Err(_) => return Err(()), // there was no next node
}
}
Ok(())
}
/// Finds the previous filled node.
/// If there isn't any, moves to root and return Err(()).
///
/// May restructure the tree while doing so.
fn previous_filled(&mut self) -> Result<(), ()> {
if !self.is_empty() {
self.previous_empty().unwrap();
}
loop {
match self.go_up() {
Ok(Side::Right) => break,
Ok(Side::Left) => (),
Err(_) => return Err(()), // there was no next node
}
}
Ok(())
}
/// Finds any node that the locator `Accept`s. Looks only inside the current subtree.
/// If there isn't any, it finds the empty location where that node would be instead.
/// Returns a walker at the wanted position.
fn search_subtree<L: crate::Locator<D>>(&mut self, locator: L) {
use locators::LocResult;
while let Some(res) = locators::query_locator(self, &locator) {
match res {
LocResult::Accept => break,
LocResult::GoRight => self.go_right().unwrap(),
LocResult::GoLeft => self.go_left().unwrap(),
};
}
}
/// Returns a summary of all the values to the left of this point,
/// That are not children of this point.
fn far_left_summary(&self) -> D::Summary;
/// Returns a summary of all the values to the right of this point,
/// That are not children of this point.
fn far_right_summary(&self) -> D::Summary;
/// Returns a summary of all the values to the left of this point.
/// If the walker is in a non empty spot, this does not include the current node.
fn left_summary(&self) -> D::Summary {
let left = self.far_left_summary();
match self.left_subtree_summary() {
Some(subtree) => left + subtree,
None => left,
}
}
/// Returns a summary of all the values to the right of this point.
/// If the walker is in a non empty spot, this does not include the current node.
fn right_summary(&self) -> D::Summary {
let right = self.far_right_summary();
match self.right_subtree_summary() {
Some(subtree) => subtree + right,
None => right,
}
}
}
/// Methods that ask to read the contents of the current tree/subtree.
/// These methods are common to the trees themselves and to the walkers.
pub trait SomeEntry<D: Data> {
/// Lets you modify the value, and after you modified it, rebuilds the node.
/// If the current position is empty, returns [`None`].
fn with_value<F, R>(&mut self, f: F) -> Option<R>
where
F: FnOnce(&mut D::Value) -> R;
/// Returns [`true`] if the current tree/subtree is empty.
fn is_empty(&self) -> bool {
self.left_subtree_summary().is_none()
}
/// Returns a summary of just the current node.
/// Returns the empty summary if at an empty position.
fn node_summary(&self) -> D::Summary;
/// Returns the summary of all values in this node's subtree.
///```
/// use grove::{SomeTree, SomeEntry, basic_tree::BasicTree};
/// use grove::example_data::StdNum;
///
/// let tree: BasicTree<StdNum> = (1..=8).collect();
/// let summary = tree.subtree_summary();
///
/// assert_eq!(summary.size, 8);
/// assert_eq!(summary.sum, 36);
/// assert_eq!(summary.max, Some(8));
/// assert_eq!(summary.min, Some(1));
/// # tree.assert_correctness();
///```
fn subtree_summary(&self) -> D::Summary;
/// Returns the summary of the subtree of this node's left son.
fn left_subtree_summary(&self) -> Option<D::Summary>;
/// Returns the summary of the subtree of this node's right son.
fn right_subtree_summary(&self) -> Option<D::Summary>;
/// Applies the action on the current node.
fn act_node(&mut self, action: D::Action) -> Option<()>;
/// Applies the given action on this subtree.
fn act_subtree(&mut self, action: D::Action);
/// Applies the given action on this node's left son.
fn act_left_subtree(&mut self, action: D::Action) -> Option<()>;
/// Applies the given action on this node's right son.
fn act_right_subtree(&mut self, action: D::Action) -> Option<()>;
/// Used for testing purposes.
/// Should panic if the local invariants aren't satisfied.
fn assert_correctness_locally(&self)
where
D::Summary: Eq;
#[cfg(debug_assertions)]
/// This has to be specified in order for the `representation` method
/// to work
type EntryTreeData;
#[cfg(debug_assertions)]
/// Used for debugging. Prints a representation of the tree, like so:
/// `< < * * > * >`
/// Each pair of triangle brackets is a node, and `*` denotes empty trees.
/// The trees are printed in the layout they will have atfter all reversals have been
/// finished, but nodes which are yet to be reversed (`node.action.to_reverse() == true`)
/// are printed with an exclamation mark: `<! * * >`.
/// You can provide a custom printer for the alg_data field.
/// If the input `to_reverse` is true, it will print the tree in reverse.
fn representation<F>(&self, alg_print: &F, to_reverse: bool) -> String
where
F: Fn(&basic_tree::BasicNode<D, Self::EntryTreeData>) -> String;
}
/// Trait for trees that can be modified, i.e., values can be inserted and deleted.
///
/// This trait is a workaround for current rust type inference limitations.
/// It allows to write generic code for a tree type that has a modifiable walker.
/// Intuitively it should've been enough to require
/// `T: SomeTree<D>, for<'a> &'a mut T: SomeTreeRef<D>, for<'a> <&'a mut T as SomeTreeRef<D>>::Walker: ModifiableWalker`.
/// However, that doesn't work. Instead, use `for<'a> &'a mut T: ModifiableTreeRef<D>`.
pub trait ModifiableTreeRef<D: Data>: SomeTreeRef<D, Walker = Self::ModifiableWalker> {
/// Inner type that ideally shouldn't be used - just use `Self::Walker`.
type ModifiableWalker: ModifiableWalker<D>;
}
/// This is a trait for walkers that allow inserting and deleting values.
pub trait ModifiableWalker<D: Data>: SomeWalker<D> {
/// Inserts the value into the tree at the current empty position.
/// If the current position is not empty, returns [`None`].
/// May end up at any possible location, depending on the tree type.
fn insert(&mut self, value: D::Value) -> Option<()>;
/// Removes the current value from the tree, and returns it.
/// If currently at an empty position, returns [`None`].
/// May end up at any possible location, depending on the tree type.
fn delete(&mut self) -> Option<D::Value>;
}
/// Trait for trees that can concatenate.
/// I wanted this to be the same trait family as SplittableWalker, but the current rustc type solver didn't let me.
/// It's enough to only implement any one of the three methods - they're all implemented in terms of each other.
pub trait ConcatenableTree<D: Data>: SomeTree<D>
where
for<'a> &'a mut Self: SomeTreeRef<D>,
{
/// Concatenates the two inputs into one tree.
fn concatenate(mut left: Self, right: Self) -> Self {
left.concatenate_right(right);
left
}
/// Concatenates the other tree to the right of this tree.
fn concatenate_right(&mut self, mut other: Self) {
let left = std::mem::take(self);
other.concatenate_left(left);
*self = other;
}
/// Concatenates the other tree to the left of this tree.
fn concatenate_left(&mut self, other: Self) {
let right = std::mem::take(self);
*self = Self::concatenate(other, right);
}
}
/// Trait for trees that can be split and concatenated.
/// Require this kind of tree if you want to use reversal actions on segments of your tree.
pub trait SplittableTreeRef<D: Data>:
SomeTreeRef<D, Walker = Self::SplittableWalker> + Sized
{
/// Inner type that ideally shouldn't be used - just use the original tree type.
type T;
/// Inner type that ideally shouldn't be used - just use `Self::Walker`.
type SplittableWalker: SplittableWalker<D, T = Self::T>;
}
/// Walkers that can split a tree into two.
pub trait SplittableWalker<D: Data>: ModifiableWalker<D> {
/// Inner type that ideally shouldn't be used - just use the original tree type.
type T;
/// Split out everything to the right of the current position, if it is an empty position.
/// Otherwise returns [`None`].
fn split_right(&mut self) -> Option<Self::T>;
/// Split out everything to the left of the current position, if it is an empty position.
/// Otherwise returns [`None`].
fn split_left(&mut self) -> Option<Self::T>;
}