oxihuman_core/
finger_tree.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5//! Finger tree sequence stub — simulates O(1) push/pop at both ends with
6//! amortised O(log n) split/concat, represented here as a thin deque wrapper.
7
8use std::collections::VecDeque;
9
10/// A finger tree sequence.
11pub struct FingerTree<T> {
12    data: VecDeque<T>,
13}
14
15impl<T: Clone> FingerTree<T> {
16    /// Create an empty finger tree.
17    pub fn new() -> Self {
18        Self {
19            data: VecDeque::new(),
20        }
21    }
22
23    /// Push an element onto the left (front).
24    pub fn push_left(&mut self, value: T) {
25        self.data.push_front(value);
26    }
27
28    /// Push an element onto the right (back).
29    pub fn push_right(&mut self, value: T) {
30        self.data.push_back(value);
31    }
32
33    /// Pop an element from the left (front).
34    pub fn pop_left(&mut self) -> Option<T> {
35        self.data.pop_front()
36    }
37
38    /// Pop an element from the right (back).
39    pub fn pop_right(&mut self) -> Option<T> {
40        self.data.pop_back()
41    }
42
43    /// Peek at the leftmost element.
44    pub fn peek_left(&self) -> Option<&T> {
45        self.data.front()
46    }
47
48    /// Peek at the rightmost element.
49    pub fn peek_right(&self) -> Option<&T> {
50        self.data.back()
51    }
52
53    /// Concatenate another finger tree onto the right of this one.
54    pub fn concat(&mut self, other: FingerTree<T>) {
55        for item in other.data {
56            self.data.push_back(item);
57        }
58    }
59
60    /// Split the tree at index `at`, returning the right portion.
61    pub fn split_at(&mut self, at: usize) -> FingerTree<T> {
62        let right: VecDeque<T> = self.data.split_off(at);
63        FingerTree { data: right }
64    }
65
66    /// Number of elements in the tree.
67    pub fn len(&self) -> usize {
68        self.data.len()
69    }
70
71    /// True if the tree is empty.
72    pub fn is_empty(&self) -> bool {
73        self.data.is_empty()
74    }
75
76    /// Collect all elements into a Vec.
77    pub fn to_vec(&self) -> Vec<T> {
78        self.data.iter().cloned().collect()
79    }
80}
81
82impl<T: Clone> Default for FingerTree<T> {
83    fn default() -> Self {
84        Self::new()
85    }
86}
87
88/// Create a new empty finger tree.
89pub fn new_finger_tree<T: Clone>() -> FingerTree<T> {
90    FingerTree::new()
91}
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96
97    #[test]
98    fn test_push_left() {
99        let mut ft: FingerTree<i32> = FingerTree::new();
100        ft.push_left(1);
101        ft.push_left(2);
102        assert_eq!(ft.peek_left(), Some(&2)); /* last pushed left is front */
103    }
104
105    #[test]
106    fn test_push_right() {
107        let mut ft: FingerTree<i32> = FingerTree::new();
108        ft.push_right(1);
109        ft.push_right(2);
110        assert_eq!(ft.peek_right(), Some(&2)); /* last pushed right is back */
111    }
112
113    #[test]
114    fn test_pop_left() {
115        let mut ft: FingerTree<i32> = FingerTree::new();
116        ft.push_right(10);
117        assert_eq!(ft.pop_left(), Some(10)); /* pop from left */
118    }
119
120    #[test]
121    fn test_pop_right() {
122        let mut ft: FingerTree<i32> = FingerTree::new();
123        ft.push_right(5);
124        assert_eq!(ft.pop_right(), Some(5)); /* pop from right */
125    }
126
127    #[test]
128    fn test_concat() {
129        let mut left: FingerTree<i32> = FingerTree::new();
130        let mut right: FingerTree<i32> = FingerTree::new();
131        left.push_right(1);
132        right.push_right(2);
133        left.concat(right);
134        assert_eq!(left.len(), 2); /* two elements after concat */
135    }
136
137    #[test]
138    fn test_split_at() {
139        let mut ft: FingerTree<i32> = FingerTree::new();
140        for i in 0..6 {
141            ft.push_right(i);
142        }
143        let right = ft.split_at(3);
144        assert_eq!(ft.len(), 3); /* left half */
145        assert_eq!(right.len(), 3); /* right half */
146    }
147
148    #[test]
149    fn test_to_vec() {
150        let mut ft: FingerTree<i32> = FingerTree::new();
151        ft.push_right(1);
152        ft.push_right(2);
153        ft.push_right(3);
154        assert_eq!(ft.to_vec(), vec![1, 2, 3]); /* ordered correctly */
155    }
156
157    #[test]
158    fn test_len_and_is_empty() {
159        let ft: FingerTree<i32> = FingerTree::new();
160        assert!(ft.is_empty()); /* new tree is empty */
161        let mut ft2 = ft;
162        ft2.push_right(1);
163        assert_eq!(ft2.len(), 1);
164    }
165
166    #[test]
167    fn test_default() {
168        let ft: FingerTree<i32> = FingerTree::default();
169        assert!(ft.is_empty()); /* default is empty */
170    }
171
172    #[test]
173    fn test_new_helper() {
174        let ft = new_finger_tree::<u8>();
175        assert!(ft.is_empty()); /* helper works */
176    }
177}
oxihuman_core/finger_tree.rs

oxihuman_core/
finger_tree.rs
