osom_lib_trees/traits/
tree.rs

1use core::num::NonZeroU8;
2
3use super::{Compare, TreeQueryExactMutResult, TreeQueryExactResult, TreeQueryMutResult, TreeQueryResult};
4
5/// Abstract trait for tree-like data structures.
6pub trait Tree {
7    type TKey: Ord;
8    type TValue;
9
10    /// Searches the tree for the exact match.
11    fn query_exact<K>(&self, key: &K) -> TreeQueryExactResult<'_, Self::TKey, Self::TValue>
12    where
13        Self::TKey: Compare<K>;
14
15    /// The mutable version of [`Tree::query_exact`].
16    fn query_exact_mut<K>(&mut self, key: &K) -> TreeQueryExactMutResult<'_, Self::TKey, Self::TValue>
17    where
18        Self::TKey: Compare<K>;
19
20    /// Searches the tree for the key-value pairs less than the passed key.
21    /// These will be returned in descending order starting from the gratest found element.
22    ///
23    /// If `max_count` is `None`, all key-value pairs less than the passed key will be returned.
24    /// If `max_count` is `Some(n)`, at most `n` key-value pairs will be returned.
25    fn query_less_than<K>(
26        &self,
27        key: &K,
28        max_count: Option<NonZeroU8>,
29    ) -> impl TreeQueryResult<'_, Self::TKey, Self::TValue>
30    where
31        Self::TKey: Compare<K>;
32
33    /// The mutable version of [`Tree::query_less_than`].
34    fn query_less_than_mut<K>(
35        &mut self,
36        key: &K,
37        max_count: Option<NonZeroU8>,
38    ) -> impl TreeQueryMutResult<'_, Self::TKey, Self::TValue>
39    where
40        Self::TKey: Compare<K>;
41
42    /// Searches the tree for the key-value pairs less than or equal to the passed key.
43    /// These will be returned in descending order starting from the gratest found element.
44    ///
45    /// If `max_count` is `None`, all key-value pairs less than or equal to the passed key will be returned.
46    /// If `max_count` is `Some(n)`, at most `n` key-value pairs will be returned.
47    fn query_less_than_or_equal<K>(
48        &self,
49        key: &K,
50        max_count: Option<NonZeroU8>,
51    ) -> impl TreeQueryResult<'_, Self::TKey, Self::TValue>
52    where
53        Self::TKey: Compare<K>;
54
55    /// The mutable version of [`Tree::query_less_than_or_equal`].
56    fn query_less_than_or_equal_mut<K>(
57        &mut self,
58        key: &K,
59        max_count: Option<NonZeroU8>,
60    ) -> impl TreeQueryMutResult<'_, Self::TKey, Self::TValue>
61    where
62        Self::TKey: Compare<K>;
63
64    /// Searches the tree for the key-value pairs greater than the passed key.
65    /// These will be returned in ascending order starting from the smallest found element.
66    ///
67    /// If `max_count` is `None`, all key-value pairs greater than the passed key will be returned.
68    /// If `max_count` is `Some(n)`, at most `n` key-value pairs will be returned.
69    fn query_greater_than<K>(
70        &self,
71        key: &K,
72        max_count: Option<NonZeroU8>,
73    ) -> impl TreeQueryResult<'_, Self::TKey, Self::TValue>
74    where
75        Self::TKey: Compare<K>;
76
77    /// The mutable version of [`Tree::query_greater_than`].
78    fn query_greater_than_mut<K>(
79        &mut self,
80        key: &K,
81        max_count: Option<NonZeroU8>,
82    ) -> impl TreeQueryMutResult<'_, Self::TKey, Self::TValue>
83    where
84        Self::TKey: Compare<K>;
85
86    /// Searches the tree for the key-value pairs greater than or equal to the passed key.
87    /// These will be returned in ascending order starting from the smallest found element.
88    ///
89    /// If `max_count` is `None`, all key-value pairs greater than or equal to the passed key will be returned.
90    /// If `max_count` is `Some(n)`, at most `n` key-value pairs will be returned.
91    fn query_greater_than_or_equal<K>(
92        &self,
93        key: &K,
94        max_count: Option<NonZeroU8>,
95    ) -> impl TreeQueryResult<'_, Self::TKey, Self::TValue>
96    where
97        Self::TKey: Compare<K>;
98
99    /// The mutable version of [`Tree::query_greater_than_or_equal`].
100    fn query_greater_than_or_equal_mut<K>(
101        &mut self,
102        key: &K,
103        max_count: Option<NonZeroU8>,
104    ) -> impl TreeQueryMutResult<'_, Self::TKey, Self::TValue>
105    where
106        Self::TKey: Compare<K>;
107
108    /// Searches the tree for the key-value pairs in the range `(left, right)`,
109    /// i.e. with endpoints excluded.
110    fn query_range_exclusive<K>(&self, left: &K, right: &K) -> impl TreeQueryResult<'_, Self::TKey, Self::TValue>
111    where
112        Self::TKey: Compare<K>;
113
114    /// The mutable version of [`Tree::query_range_exclusive`].
115    fn query_range_exclusive_mut<K>(
116        &mut self,
117        left: &K,
118        right: &K,
119    ) -> impl TreeQueryMutResult<'_, Self::TKey, Self::TValue>
120    where
121        Self::TKey: Compare<K>;
122
123    /// Searches the tree for the key-value pairs in the range `[left, right]`,
124    /// i.e. with endpoints included.
125    fn query_range_inclusive<K>(&self, left: &K, right: &K) -> impl TreeQueryResult<'_, Self::TKey, Self::TValue>
126    where
127        Self::TKey: Compare<K>;
128
129    /// The mutable version of [`Tree::query_range_inclusive`].
130    fn query_range_inclusive_mut<K>(
131        &mut self,
132        left: &K,
133        right: &K,
134    ) -> impl TreeQueryMutResult<'_, Self::TKey, Self::TValue>
135    where
136        Self::TKey: Compare<K>;
137
138    /// Searches the tree for the key-value pairs in the range `[left, right)`,
139    /// i.e. with the left endpoint included and the right endpoint excluded.
140    fn query_range_left_inclusive<K>(&self, left: &K, right: &K) -> impl TreeQueryResult<'_, Self::TKey, Self::TValue>
141    where
142        Self::TKey: Compare<K>;
143
144    /// The mutable version of [`Tree::query_range_left_inclusive`].
145    fn query_range_left_inclusive_mut<K>(
146        &mut self,
147        left: &K,
148        right: &K,
149    ) -> impl TreeQueryMutResult<'_, Self::TKey, Self::TValue>
150    where
151        Self::TKey: Compare<K>;
152
153    /// Searches the tree for the key-value pairs in the range `(left, right]`,
154    /// i.e. with the right endpoint included and the left endpoint excluded.
155    fn query_range_right_inclusive<K>(&self, left: &K, right: &K) -> impl TreeQueryResult<'_, Self::TKey, Self::TValue>
156    where
157        Self::TKey: Compare<K>;
158
159    /// The mutable version of [`Tree::query_range_right_inclusive`].
160    fn query_range_right_inclusive_mut<K>(
161        &mut self,
162        left: &K,
163        right: &K,
164    ) -> impl TreeQueryMutResult<'_, Self::TKey, Self::TValue>
165    where
166        Self::TKey: Compare<K>;
167}
osom_lib_trees/traits/tree.rs

osom_lib_trees/traits/
tree.rs
