oxilean_std/rbtree/
types.rs

1//! Auto-generated module
2//!
3//! 🤖 Generated with [SplitRS](https://github.com/cool-japan/splitrs)
4use super::functions::*;
5
6/// AVL tree rotation data.
7#[allow(dead_code)]
8#[derive(Debug, Clone, PartialEq)]
9pub enum AvlRotation {
10    LeftLeft,
11    RightRight,
12    LeftRight,
13    RightLeft,
14}
15#[allow(dead_code)]
16impl AvlRotation {
17    /// Number of single rotations needed.
18    pub fn num_rotations(&self) -> usize {
19        match self {
20            Self::LeftLeft | Self::RightRight => 1,
21            Self::LeftRight | Self::RightLeft => 2,
22        }
23    }
24    /// Description.
25    pub fn description(&self) -> &str {
26        match self {
27            Self::LeftLeft => "single right rotation",
28            Self::RightRight => "single left rotation",
29            Self::LeftRight => "left-right double rotation",
30            Self::RightLeft => "right-left double rotation",
31        }
32    }
33}
34/// Treap (randomized BST) node.
35#[allow(dead_code)]
36#[derive(Debug, Clone)]
37pub struct TreapNode {
38    pub key: i64,
39    pub priority: u64,
40    pub size: usize,
41}
42#[allow(dead_code)]
43impl TreapNode {
44    /// Create a treap node with a random priority.
45    pub fn new(key: i64, priority: u64) -> Self {
46        Self {
47            key,
48            priority,
49            size: 1,
50        }
51    }
52    /// Expected height of a treap is O(log n).
53    pub fn expected_height_description(n: usize) -> String {
54        let h = (n as f64).log2() * 2.0;
55        format!("Expected height ~{:.1} for n={}", h, n)
56    }
57}
58/// Splay tree amortized analysis.
59#[allow(dead_code)]
60#[derive(Debug, Clone)]
61pub struct SplayAnalysis {
62    pub sequence_length: usize,
63    pub access_sequence: Vec<i64>,
64    pub amortized_cost: f64,
65}
66#[allow(dead_code)]
67impl SplayAnalysis {
68    /// Splay tree analysis for a sequence.
69    pub fn new(seq: Vec<i64>) -> Self {
70        let n = seq.len();
71        let cost = if n == 0 {
72            0.0
73        } else {
74            (n as f64) * (n as f64).log2()
75        };
76        Self {
77            sequence_length: n,
78            access_sequence: seq,
79            amortized_cost: cost,
80        }
81    }
82    /// Total amortized cost.
83    pub fn total_cost(&self) -> f64 {
84        self.amortized_cost
85    }
86    /// Average cost per operation.
87    pub fn avg_cost(&self) -> f64 {
88        if self.sequence_length == 0 {
89            0.0
90        } else {
91            self.amortized_cost / self.sequence_length as f64
92        }
93    }
94}
95/// Order statistics tree data.
96#[allow(dead_code)]
97#[derive(Debug, Clone)]
98pub struct OrderStatisticsTree {
99    pub size: usize,
100    pub keys: Vec<i64>,
101}
102#[allow(dead_code)]
103impl OrderStatisticsTree {
104    /// Create an order statistics tree.
105    pub fn new(mut keys: Vec<i64>) -> Self {
106        keys.sort_unstable();
107        let size = keys.len();
108        Self { size, keys }
109    }
110    /// k-th smallest element (1-indexed).
111    pub fn kth_smallest(&self, k: usize) -> Option<i64> {
112        if k == 0 || k > self.size {
113            None
114        } else {
115            Some(self.keys[k - 1])
116        }
117    }
118    /// Rank of a key (number of elements <= key).
119    pub fn rank(&self, key: i64) -> usize {
120        self.keys.iter().filter(|&&k| k <= key).count()
121    }
122}
123/// B-tree node data (for database/storage contexts).
124#[allow(dead_code)]
125#[derive(Debug, Clone)]
126pub struct BTreeNodeData {
127    pub order: usize,
128    pub keys: Vec<i64>,
129    pub is_leaf: bool,
130    pub num_children: usize,
131}
132#[allow(dead_code)]
133impl BTreeNodeData {
134    /// Create a B-tree leaf node.
135    pub fn leaf(order: usize, keys: Vec<i64>) -> Self {
136        Self {
137            order,
138            keys: keys.clone(),
139            is_leaf: true,
140            num_children: 0,
141        }
142    }
143    /// Create an internal B-tree node.
144    pub fn internal(order: usize, keys: Vec<i64>, num_children: usize) -> Self {
145        Self {
146            order,
147            keys,
148            is_leaf: false,
149            num_children,
150        }
151    }
152    /// Is this node overfull (needs splitting)?
153    pub fn needs_split(&self) -> bool {
154        self.keys.len() >= 2 * self.order - 1
155    }
156    /// Is this node underfull (needs merging)?
157    pub fn needs_merge(&self) -> bool {
158        self.keys.len() < self.order - 1
159    }
160}
oxilean_std/rbtree/types.rs

oxilean_std/rbtree/
types.rs
