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//! | [`LinkType`] | Marker trait for unsigned integer types usable as node indices |
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::{
28//! LinkType, LinkedList, AbsoluteLinkedList, AbsoluteCircularLinkedList,
29//! };
30//!
31//! // 1. Define your storage
32//! #[derive(Default, Clone, Copy)]
33//! struct Node { prev: usize, next: usize }
34//!
35//! struct MyList {
36//! nodes: Vec<Node>,
37//! first: usize,
38//! last: usize,
39//! size: usize,
40//! }
41//!
42//! // 2. Implement the required traits
43//! impl LinkedList<usize> for MyList {
44//! fn get_previous(&self, el: usize) -> usize { self.nodes[el].prev }
45//! fn get_next(&self, el: usize) -> usize { self.nodes[el].next }
46//! fn set_previous(&mut self, el: usize, p: usize) { self.nodes[el].prev = p; }
47//! fn set_next(&mut self, el: usize, n: usize) { self.nodes[el].next = n; }
48//! }
49//!
50//! impl AbsoluteLinkedList<usize> for MyList {
51//! fn get_first(&self) -> usize { self.first }
52//! fn get_last(&self) -> usize { self.last }
53//! fn get_size(&self) -> usize { self.size }
54//! fn set_first(&mut self, el: usize) { self.first = el; }
55//! fn set_last(&mut self, el: usize) { self.last = el; }
56//! fn set_size(&mut self, s: usize) { self.size = s; }
57//! }
58//!
59//! impl AbsoluteCircularLinkedList<usize> for MyList {}
60//!
61//! // 3. Use the provided methods
62//! let mut list = MyList {
63//! nodes: vec![Node::default(); 5],
64//! first: 0, last: 0, size: 0,
65//! };
66//! list.attach_as_first(1);
67//! list.attach_as_last(2);
68//! assert_eq!(list.get_size(), 2);
69//! assert_eq!(list.get_first(), 1);
70//! assert_eq!(list.get_last(), 2);
71//! ```
72
73mod link_type;
74mod lists;
75mod trees;
76
77pub use link_type::LinkType;
78pub use lists::{
79 AbsoluteCircularLinkedList, AbsoluteLinkedList, LinkedList, RelativeCircularLinkedList,
80 RelativeLinkedList,
81};
82
83pub use trees::{IterativeSizeBalancedTree, RecursiveSizeBalancedTree};