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}