platform_trees/lib.rs
1//! # platform-trees
2//!
3//! Generic traits for size-balanced binary trees and circular linked lists
4//! used throughout the [LinksPlatform](https://github.com/linksplatform) ecosystem.
5//!
6//! This crate provides trait-based abstractions that allow downstream crates
7//! (such as [`doublets`](https://crates.io/crates/doublets)) to implement
8//! their own storage-backed trees and lists while reusing the balancing,
9//! rotation, and list manipulation logic defined here.
10//!
11//! ## Traits overview
12//!
13//! | Trait | Description |
14//! |---|---|
15//! | [`LinkReference`] | Unsigned integer type usable as a node index (from `platform-num`) |
16//! | [`LinkedList`] | Base doubly-linked list with `get_previous`/`get_next` |
17//! | [`AbsoluteLinkedList`] | List with direct `first`/`last`/`size` access |
18//! | [`RelativeLinkedList`] | List with head-relative `first`/`last`/`size` |
19//! | [`AbsoluteCircularLinkedList`] | Circular list with absolute positioning |
20//! | [`RelativeCircularLinkedList`] | Circular list with head-relative positioning |
21//! | [`RecursiveSizeBalancedTree`] | Size-balanced BST with rotations and queries |
22//! | [`IterativeSizeBalancedTree`] | Iterative `attach`/`detach` over the recursive base |
23//!
24//! ## Quick start
25//!
26//! ```rust
27//! use platform_trees::{LinkedList, AbsoluteLinkedList, AbsoluteCircularLinkedList};
28//! use platform_num::LinkReference;
29//!
30//! // 1. Define your storage
31//! #[derive(Default, Clone, Copy)]
32//! struct Node { prev: usize, next: usize }
33//!
34//! struct MyList {
35//! nodes: Vec<Node>,
36//! first: usize,
37//! last: usize,
38//! size: usize,
39//! }
40//!
41//! // 2. Implement the required traits
42//! impl LinkedList<usize> for MyList {
43//! fn get_previous(&self, el: usize) -> usize { self.nodes[el].prev }
44//! fn get_next(&self, el: usize) -> usize { self.nodes[el].next }
45//! fn set_previous(&mut self, el: usize, p: usize) { self.nodes[el].prev = p; }
46//! fn set_next(&mut self, el: usize, n: usize) { self.nodes[el].next = n; }
47//! }
48//!
49//! impl AbsoluteLinkedList<usize> for MyList {
50//! fn get_first(&self) -> usize { self.first }
51//! fn get_last(&self) -> usize { self.last }
52//! fn get_size(&self) -> usize { self.size }
53//! fn set_first(&mut self, el: usize) { self.first = el; }
54//! fn set_last(&mut self, el: usize) { self.last = el; }
55//! fn set_size(&mut self, s: usize) { self.size = s; }
56//! }
57//!
58//! impl AbsoluteCircularLinkedList<usize> for MyList {}
59//!
60//! // 3. Use the provided methods
61//! let mut list = MyList {
62//! nodes: vec![Node::default(); 5],
63//! first: 0, last: 0, size: 0,
64//! };
65//! list.attach_as_first(1);
66//! list.attach_as_last(2);
67//! assert_eq!(list.get_size(), 2);
68//! assert_eq!(list.get_first(), 1);
69//! assert_eq!(list.get_last(), 2);
70//! ```
71
72mod lists;
73mod trees;
74
75pub use lists::{
76 AbsoluteCircularLinkedList, AbsoluteLinkedList, LinkedList, RelativeCircularLinkedList,
77 RelativeLinkedList,
78};
79pub use platform_num::LinkReference;
80
81pub use trees::{IterativeSizeBalancedTree, RecursiveSizeBalancedTree};