1#![forbid(unsafe_code)]
2#![cfg_attr(docsrs, feature(doc_cfg))]
3#![cfg_attr(docsrs, doc(cfg_hide(doc)))]
4
5use std::{
6 ops::{Bound, RangeBounds},
7 pin::pin,
8};
9
10use futures_util::{Stream, TryStream, TryStreamExt};
11use genawaiter_try_stream::{Co, try_stream};
12use object_rainbow::{
13 Equivalent, Fetch, Inline, InlineOutput, ListHashes, Parse, ParseInline, ParseSliceRefless,
14 ReflessObject, Tagged, ToOutput, Topological, Traversible, assert_impl,
15 object_marker::ObjectMarker,
16};
17use object_rainbow_array_map::ArrayMap;
18use object_rainbow_point::{IntoPoint, Point};
19
20#[cfg(feature = "serde")]
21mod serde;
22
23type TriePoint<Tr> = Point<(Tr, Vec<u8>)>;
24
25#[derive(ToOutput, InlineOutput, Tagged, ListHashes, Topological, Parse, ParseInline, Clone)]
26#[topology(recursive, inline)]
27pub struct Trie<T> {
28 value: Option<T>,
29 #[tags(skip)]
30 #[parse(unchecked)]
31 #[topology(unchecked)]
32 children: ArrayMap<TriePoint<Self>>,
33}
34
35assert_impl!(
36 impl<T, E> Inline<E> for Trie<T>
37 where
38 E: 'static + Clone + Send + Sync,
39 Option<T>: Inline<E>,
40 {
41 }
42);
43
44impl<T> Default for Trie<T> {
45 fn default() -> Self {
46 Self::new()
47 }
48}
49
50impl<T> Trie<T> {
51 pub const fn new() -> Self {
52 Self {
53 value: None,
54 children: ArrayMap::new(),
55 }
56 }
57}
58
59trait TrieChildren<Tr = Self>: Sized {
60 fn c_get_mut(&mut self, key: u8) -> Option<&mut TriePoint<Tr>>;
61 fn c_get(&self, key: u8) -> Option<&TriePoint<Tr>>;
62 fn c_contains(&self, key: u8) -> bool;
63 fn c_insert(&mut self, key: u8, point: TriePoint<Tr>);
64 fn c_empty(&self) -> bool;
65 fn c_len(&self) -> usize;
66 fn c_remove(&mut self, key: u8) -> Option<TriePoint<Tr>>;
67 fn c_range<'a>(
68 &'a self,
69 min_inclusive: u8,
70 max_inclusive: u8,
71 ) -> impl Iterator<Item = (u8, &'a TriePoint<Tr>)>
72 where
73 Tr: 'a;
74 fn c_pop_first(&mut self) -> Option<(u8, TriePoint<Tr>)>;
75 fn c_iter_mut<'a>(&'a mut self) -> impl Iterator<Item = (u8, &'a mut TriePoint<Tr>)>
76 where
77 Tr: 'a;
78}
79
80impl<T> TrieChildren for Trie<T> {
81 fn c_get_mut(&mut self, key: u8) -> Option<&mut TriePoint<Self>> {
82 self.children.get_mut(key)
83 }
84
85 fn c_get(&self, key: u8) -> Option<&TriePoint<Self>> {
86 self.children.get(key)
87 }
88
89 fn c_contains(&self, key: u8) -> bool {
90 self.children.contains(key)
91 }
92
93 fn c_insert(&mut self, key: u8, point: TriePoint<Self>) {
94 self.children.insert(key, point);
95 }
96
97 fn c_empty(&self) -> bool {
98 self.children.is_empty()
99 }
100
101 fn c_len(&self) -> usize {
102 self.children.len()
103 }
104
105 fn c_remove(&mut self, key: u8) -> Option<TriePoint<Self>> {
106 self.children.remove(key)
107 }
108
109 fn c_range<'a>(
110 &'a self,
111 min_inclusive: u8,
112 max_inclusive: u8,
113 ) -> impl Iterator<Item = (u8, &'a TriePoint<Self>)>
114 where
115 Self: 'a,
116 {
117 self.children.range(min_inclusive..=max_inclusive)
118 }
119
120 fn c_pop_first(&mut self) -> Option<(u8, TriePoint<Self>)> {
121 self.children.pop_first()
122 }
123
124 fn c_iter_mut<'a>(&'a mut self) -> impl Iterator<Item = (u8, &'a mut TriePoint<Self>)>
125 where
126 Self: 'a,
127 {
128 self.children.iter_mut()
129 }
130}
131
132fn common_length(a: &[u8], b: &[u8]) -> usize {
133 a.iter().zip(b).take_while(|(a, b)| a == b).count()
134}
135
136impl<T: 'static + Send + Sync + Clone> Trie<T>
137where
138 Option<T>: Traversible + InlineOutput,
139{
140 pub async fn get(&self, key: &[u8]) -> object_rainbow::Result<Option<T>> {
141 let Some((first, key)) = key.split_first() else {
142 return Ok(self.value.clone());
143 };
144 let Some(point) = self.c_get(*first) else {
145 return Ok(None);
146 };
147 let (trie, prefix) = point.fetch().await?;
148 let Some(key) = key.strip_prefix(prefix.as_slice()) else {
149 return Ok(None);
150 };
151 Box::pin(trie.get(key)).await
152 }
153
154 fn internal_state_check(&self) {
155 assert!(!self.is_empty());
156 assert!(self.value.is_some() || self.children.len() > 1);
157 }
158
159 async fn from_f<O>(
160 f: impl AsyncFnOnce(&mut Self) -> object_rainbow::Result<O>,
161 ) -> object_rainbow::Result<(Self, O)> {
162 let mut trie = Self::default();
163 let o = f(&mut trie).await?;
164 trie.internal_state_check();
165 Ok((trie, o))
166 }
167
168 async fn update_point<O>(
169 point: &mut TriePoint<Self>,
170 key: &[u8],
171 f: impl AsyncFnOnce(&mut Self) -> object_rainbow::Result<O>,
172 ) -> object_rainbow::Result<O> {
173 let (trie, prefix) = &mut *point.fetch_mut().await?;
174 let o = if let Some(key) = key.strip_prefix(prefix.as_slice()) {
175 Box::pin(trie.update(key, f)).await?
176 } else {
177 let (new, o) = Self::from_f(f).await?;
178 if let Some(suffix) = prefix.strip_prefix(key) {
179 let child = std::mem::replace(trie, new);
180 let (first, suffix) = suffix.split_first().expect("must be at least 1");
181 let mut overlay = Self::new();
182 overlay.c_insert(*first, (child, suffix.into()).point());
183 trie.append(&mut overlay).await?;
184 prefix.truncate(key.len());
185 } else {
186 let common = common_length(prefix, key);
187 let child = std::mem::take(trie);
188 let mut overlay = Self::new();
189 overlay.c_insert(
190 prefix[common],
191 (child, prefix[common + 1..].to_vec()).point(),
192 );
193 overlay.c_insert(key[common], (new, key[common + 1..].to_vec()).point());
194 trie.append(&mut overlay).await?;
195 prefix.truncate(common);
196 }
197 o
198 };
199 trie.internal_state_check();
200 Ok(o)
201 }
202
203 async fn update<O>(
204 &mut self,
205 key: &[u8],
206 f: impl AsyncFnOnce(&mut Self) -> object_rainbow::Result<O>,
207 ) -> object_rainbow::Result<O> {
208 let Some((first, key)) = key.split_first() else {
209 return f(self).await;
210 };
211 if let Some(point) = self.c_get_mut(*first) {
212 Self::update_point(point, key, f).await
213 } else {
214 let (new, o) = Self::from_f(f).await?;
215 self.c_insert(*first, (new, key.into()).point());
216 Ok(o)
217 }
218 }
219
220 pub async fn insert(&mut self, key: &[u8], value: T) -> object_rainbow::Result<Option<T>> {
221 self.update(key, async |trie| Ok(trie.value.replace(value)))
222 .await
223 }
224
225 pub fn is_empty(&self) -> bool {
226 self.c_empty() && self.value.is_none()
227 }
228
229 pub async fn remove(&mut self, key: &[u8]) -> object_rainbow::Result<Option<T>> {
230 let Some((first, key)) = key.split_first() else {
231 return Ok(self.value.take());
232 };
233 let (item, is_empty) = {
234 let Some(point) = self.c_get_mut(*first) else {
235 return Ok(None);
236 };
237 let (trie, prefix) = &mut *point.fetch_mut().await?;
238 let Some(key) = key.strip_prefix(prefix.as_slice()) else {
239 return Ok(None);
240 };
241 let item = Box::pin(trie.remove(key)).await?;
242 if trie.value.is_none()
243 && trie.c_len() < 2
244 && let Some((first, point)) = trie.c_pop_first()
245 {
246 let (child, suffix) = point.fetch().await?;
247 prefix.push(first);
248 prefix.extend_from_slice(&suffix);
249 assert!(trie.is_empty());
250 *trie = child;
251 }
252 (item, trie.is_empty())
253 };
254 if is_empty {
255 self.c_remove(*first);
256 }
257 Ok(item)
258 }
259
260 pub async fn append(&mut self, other: &mut Self) -> object_rainbow::Result<()> {
261 if let Some(value) = other.value.take() {
262 self.value = Some(value);
263 }
264 {
265 let mut futures = futures_util::stream::FuturesUnordered::new();
266 for (key, point) in self.c_iter_mut() {
267 if let Some(other) = other.c_remove(key) {
268 futures.push(async move {
269 let (mut other, key) = other.fetch().await?;
270 Self::update_point(point, &key, async |trie| trie.append(&mut other).await)
271 .await
272 });
273 }
274 }
275 while futures.try_next().await?.is_some() {}
276 }
277 while let Some((key, point)) = other.c_pop_first() {
278 assert!(!self.c_contains(key));
279 self.c_insert(key, point);
280 }
281 assert!(other.c_empty());
282 Ok(())
283 }
284
285 async fn yield_all(
286 &self,
287 context: &mut Vec<u8>,
288 co: &Co<(Vec<u8>, T), object_rainbow::Error>,
289 ) -> object_rainbow::Result<()> {
290 if let Some(value) = self.value.clone() {
291 co.yield_((context.clone(), value)).await;
292 }
293 let len = context.len();
294 for (first, point) in self.c_range(u8::MIN, u8::MAX) {
295 {
296 context.push(first);
297 let (trie, prefix) = point.fetch().await?;
298 context.extend_from_slice(&prefix);
299 Box::pin(trie.yield_all(context, co)).await?;
300 }
301 context.truncate(len);
302 }
303 Ok(())
304 }
305
306 async fn prefix_yield(
307 &self,
308 context: &mut Vec<u8>,
309 key: &[u8],
310 co: &Co<(Vec<u8>, T), object_rainbow::Error>,
311 ) -> object_rainbow::Result<()> {
312 let Some((first, key)) = key.split_first() else {
313 self.yield_all(context, co).await?;
314 return Ok(());
315 };
316 let Some(point) = self.c_get(*first) else {
317 return Ok(());
318 };
319 let len = context.len();
320 'done: {
321 context.push(*first);
322 let (trie, prefix) = point.fetch().await?;
323 context.extend_from_slice(&prefix);
324 if prefix.starts_with(key) {
325 trie.yield_all(context, co).await?;
326 break 'done;
327 }
328 let Some(key) = key.strip_prefix(prefix.as_slice()) else {
329 break 'done;
330 };
331 Box::pin(trie.prefix_yield(context, key, co)).await?;
332 }
333 context.truncate(len);
334 Ok(())
335 }
336
337 async fn range_yield(
338 &self,
339 context: &mut Vec<u8>,
340 range_start: Bound<&[u8]>,
341 range_end: Bound<&[u8]>,
342 co: &Co<(Vec<u8>, T), object_rainbow::Error>,
343 ) -> object_rainbow::Result<()> {
344 if (range_start, range_end).contains(b"".as_slice())
345 && let Some(value) = self.value.clone()
346 {
347 co.yield_((context.clone(), value)).await;
348 }
349 let min = match range_start {
350 Bound::Included(x) | Bound::Excluded(x) => x.first().copied().unwrap_or(0),
351 Bound::Unbounded => 0,
352 };
353 let max = match range_end {
354 Bound::Included(x) => x.first().copied().unwrap_or(0),
355 Bound::Excluded(x) => {
356 if let Some(min) = x.first().copied() {
357 if x.len() == 1 {
358 if let Some(min) = min.checked_sub(1) {
359 min
360 } else {
361 return Ok(());
362 }
363 } else {
364 min
365 }
366 } else {
367 return Ok(());
368 }
369 }
370 Bound::Unbounded => 255,
371 };
372 let len = context.len();
373 for (first, point) in self.c_range(min, max) {
374 'done: {
375 context.push(first);
376 let (trie, prefix) = point.fetch().await?;
377 context.extend_from_slice(&prefix);
378 let extra = &context[context.len() - prefix.len() - 1..];
379 let start_bound = match range_start {
380 Bound::Included(x) => {
381 if x <= extra {
382 Bound::Unbounded
383 } else if let Some(suffix) = x.strip_prefix(extra) {
384 Bound::Included(suffix)
385 } else {
386 break 'done;
387 }
388 }
389 Bound::Excluded(x) => {
390 if x < extra {
391 Bound::Unbounded
392 } else if let Some(suffix) = x.strip_prefix(extra) {
393 Bound::Excluded(suffix)
394 } else {
395 break 'done;
396 }
397 }
398 Bound::Unbounded => Bound::Unbounded,
399 };
400 let end_bound = match range_end {
401 Bound::Included(x) => {
402 if x < extra {
403 break 'done;
404 } else if let Some(suffix) = x.strip_prefix(extra) {
405 Bound::Included(suffix)
406 } else {
407 Bound::Unbounded
408 }
409 }
410 Bound::Excluded(x) => {
411 if x <= extra {
412 break 'done;
413 } else if let Some(suffix) = x.strip_prefix(extra) {
414 Bound::Excluded(suffix)
415 } else {
416 Bound::Unbounded
417 }
418 }
419 Bound::Unbounded => Bound::Unbounded,
420 };
421 Box::pin(trie.range_yield(context, start_bound, end_bound, co)).await?;
422 }
423 context.truncate(len);
424 }
425 Ok(())
426 }
427
428 pub fn prefix_stream(
429 &self,
430 prefix: &[u8],
431 ) -> impl Send + Stream<Item = object_rainbow::Result<(Vec<u8>, T)>> {
432 try_stream(async |co| self.prefix_yield(&mut Vec::new(), prefix, &co).await)
433 }
434
435 pub fn range_stream<'a, B: AsRef<[u8]>>(
436 &'a self,
437 range: impl 'a + Send + Sync + RangeBounds<B>,
438 ) -> impl Send + Stream<Item = object_rainbow::Result<(Vec<u8>, T)>> {
439 try_stream(async move |co| {
440 self.range_yield(
441 &mut Vec::new(),
442 range.start_bound().map(AsRef::as_ref),
443 range.end_bound().map(AsRef::as_ref),
444 &co,
445 )
446 .await
447 })
448 }
449
450 pub async fn count(&self) -> object_rainbow::Result<u64> {
451 self.range_stream::<&[u8]>(..)
452 .try_fold(0u64, async |ctr, _| Ok(ctr.saturating_add(1)))
453 .await
454 }
455
456 pub async fn from_stream<K: AsRef<[u8]>>(
457 stream: impl TryStream<Ok = (K, T), Error = object_rainbow::Error>,
458 ) -> object_rainbow::Result<Self> {
459 let mut trie = Self::default();
460 let mut stream = pin!(stream.into_stream());
461 while let Some((key, value)) = stream.try_next().await? {
462 trie.insert(key.as_ref(), value).await?;
463 }
464 Ok(trie)
465 }
466}
467
468#[derive(ToOutput, InlineOutput, Tagged, ListHashes, Topological, Parse, ParseInline)]
469pub struct TrieMap<K, V> {
470 key: ObjectMarker<K>,
471 trie: Trie<V>,
472}
473
474assert_impl!(
475 impl<K, V, E> Inline<E> for TrieMap<K, V>
476 where
477 K: ReflessObject,
478 Option<V>: Inline<E>,
479 E: 'static + Send + Sync + Clone,
480 {
481 }
482);
483
484impl<K, V: Clone> Clone for TrieMap<K, V> {
485 fn clone(&self) -> Self {
486 Self {
487 key: self.key,
488 trie: self.trie.clone(),
489 }
490 }
491}
492
493impl<K, V> Default for TrieMap<K, V> {
494 fn default() -> Self {
495 Self::new()
496 }
497}
498
499impl<K, V> TrieMap<K, V> {
500 pub const fn new() -> Self {
501 Self {
502 key: ObjectMarker::new(),
503 trie: Trie::new(),
504 }
505 }
506}
507
508impl<K: ReflessObject, V: 'static + Send + Sync + Clone> TrieMap<K, V>
509where
510 Option<V>: Traversible + InlineOutput,
511{
512 pub async fn get(&self, key: &K) -> object_rainbow::Result<Option<V>> {
513 self.trie.get(&key.vec()).await
514 }
515
516 pub async fn insert(&mut self, key: &K, value: V) -> object_rainbow::Result<Option<V>> {
517 self.trie.insert(&key.vec(), value).await
518 }
519
520 pub fn is_empty(&self) -> bool {
521 self.trie.is_empty()
522 }
523
524 pub async fn remove(&mut self, key: &K) -> object_rainbow::Result<Option<V>> {
525 self.trie.remove(&key.vec()).await
526 }
527
528 pub async fn append(&mut self, other: &mut Self) -> object_rainbow::Result<()> {
529 self.trie.append(&mut other.trie).await
530 }
531
532 pub fn prefix_stream(
533 &self,
534 prefix: &[u8],
535 ) -> impl Send + Stream<Item = object_rainbow::Result<(K, V)>> {
536 self.trie
537 .prefix_stream(prefix)
538 .and_then(async |(key, value)| Ok((K::parse_slice_refless(&key)?, value)))
539 }
540
541 pub fn range_stream<'a>(
542 &'a self,
543 range: impl 'a + Send + Sync + RangeBounds<&'a K>,
544 ) -> impl Send + Stream<Item = object_rainbow::Result<(K, V)>> {
545 self.trie
546 .range_stream((
547 range.start_bound().map(|b| b.vec()),
548 range.end_bound().map(|b| b.vec()),
549 ))
550 .and_then(async |(key, value)| Ok((K::parse_slice_refless(&key)?, value)))
551 }
552
553 pub async fn from_stream(
554 stream: impl TryStream<Ok = (K, V), Error = object_rainbow::Error>,
555 ) -> object_rainbow::Result<Self> {
556 Ok(Self {
557 key: Default::default(),
558 trie: Trie::from_stream(stream.map_ok(|(key, value)| (key.vec(), value))).await?,
559 })
560 }
561}
562
563#[derive(ToOutput, InlineOutput, Tagged, ListHashes, Topological, Parse, ParseInline)]
564pub struct TrieSet<T> {
565 map: TrieMap<T, ()>,
566}
567
568assert_impl!(
569 impl<T, E> Inline<E> for TrieSet<T>
570 where
571 T: ReflessObject,
572 E: 'static + Send + Sync + Clone,
573 {
574 }
575);
576
577impl<T> Clone for TrieSet<T> {
578 fn clone(&self) -> Self {
579 Self {
580 map: self.map.clone(),
581 }
582 }
583}
584
585impl<T> Default for TrieSet<T> {
586 fn default() -> Self {
587 Self::new()
588 }
589}
590
591impl<T> TrieSet<T> {
592 pub const fn new() -> Self {
593 Self {
594 map: TrieMap::new(),
595 }
596 }
597}
598
599impl<T: ReflessObject> TrieSet<T> {
600 pub async fn contains(&self, value: &T) -> object_rainbow::Result<bool> {
601 Ok(self.map.get(value).await?.is_some())
602 }
603
604 pub async fn insert(&mut self, value: &T) -> object_rainbow::Result<bool> {
605 Ok(self.map.insert(value, ()).await?.is_none())
606 }
607
608 pub fn is_empty(&self) -> bool {
609 self.map.is_empty()
610 }
611
612 pub async fn remove(&mut self, value: &T) -> object_rainbow::Result<bool> {
613 Ok(self.map.remove(value).await?.is_some())
614 }
615
616 pub async fn append(&mut self, other: &mut Self) -> object_rainbow::Result<()> {
617 self.map.append(&mut other.map).await
618 }
619
620 pub fn prefix_stream(
621 &self,
622 prefix: &[u8],
623 ) -> impl Send + Stream<Item = object_rainbow::Result<T>> {
624 self.map.prefix_stream(prefix).map_ok(|(value, ())| value)
625 }
626
627 pub fn range_stream<'a>(
628 &'a self,
629 range: impl 'a + Send + Sync + RangeBounds<&'a T>,
630 ) -> impl Send + Stream<Item = object_rainbow::Result<T>> {
631 self.map.range_stream(range).map_ok(|(value, ())| value)
632 }
633
634 pub async fn from_stream(
635 stream: impl TryStream<Ok = T, Error = object_rainbow::Error>,
636 ) -> object_rainbow::Result<Self> {
637 Ok(Self {
638 map: TrieMap::from_stream(stream.map_ok(|value| (value, ()))).await?,
639 })
640 }
641}
642
643impl<T> Equivalent<TrieMap<T, ()>> for TrieSet<T> {
644 fn into_equivalent(self) -> TrieMap<T, ()> {
645 self.map
646 }
647
648 fn from_equivalent(map: TrieMap<T, ()>) -> Self {
649 Self { map }
650 }
651}
652
653#[cfg(test)]
654mod test {
655 use macro_rules_attribute::apply;
656 use object_rainbow::ParseSlice;
657 use smol::stream::StreamExt;
658 use smol_macros::test;
659
660 use crate::{Trie, TrieSet};
661
662 #[apply(test!)]
663 async fn test() -> object_rainbow::Result<()> {
664 let mut trie = Trie::<u8>::default();
665 trie.insert(b"abc", 1).await?;
666 assert_eq!(trie.get(b"abc").await?.unwrap(), 1);
667 trie.insert(b"abd", 2).await?;
668 assert_eq!(trie.get(b"abd").await?.unwrap(), 2);
669 trie.insert(b"ab", 3).await?;
670 assert_eq!(trie.get(b"ab").await?.unwrap(), 3);
671 trie.insert(b"a", 4).await?;
672 assert_eq!(trie.get(b"a").await?.unwrap(), 4);
673 trie.insert(b"abce", 5).await?;
674 assert_eq!(trie.get(b"abce").await?.unwrap(), 5);
675 assert_eq!(
676 trie.prefix_stream(b"")
677 .try_collect::<_, _, Vec<_>>()
678 .await?,
679 [
680 (b"a".into(), 4),
681 (b"ab".into(), 3),
682 (b"abc".into(), 1),
683 (b"abce".into(), 5),
684 (b"abd".into(), 2),
685 ],
686 );
687 assert_eq!(
688 trie.prefix_stream(b"a")
689 .try_collect::<_, _, Vec<_>>()
690 .await?,
691 [
692 (b"a".into(), 4),
693 (b"ab".into(), 3),
694 (b"abc".into(), 1),
695 (b"abce".into(), 5),
696 (b"abd".into(), 2),
697 ],
698 );
699 assert_eq!(
700 trie.prefix_stream(b"ab")
701 .try_collect::<_, _, Vec<_>>()
702 .await?,
703 [
704 (b"ab".into(), 3),
705 (b"abc".into(), 1),
706 (b"abce".into(), 5),
707 (b"abd".into(), 2),
708 ],
709 );
710 assert_eq!(
711 trie.range_stream::<&[u8]>(..)
712 .try_collect::<_, _, Vec<_>>()
713 .await?,
714 [
715 (b"a".into(), 4),
716 (b"ab".into(), 3),
717 (b"abc".into(), 1),
718 (b"abce".into(), 5),
719 (b"abd".into(), 2),
720 ],
721 );
722 assert_eq!(
723 trie.range_stream(..=b"abc".as_slice())
724 .try_collect::<_, _, Vec<_>>()
725 .await?,
726 [(b"a".into(), 4), (b"ab".into(), 3), (b"abc".into(), 1)],
727 );
728 assert_eq!(
729 trie.range_stream(..b"abc".as_slice())
730 .try_collect::<_, _, Vec<_>>()
731 .await?,
732 [(b"a".into(), 4), (b"ab".into(), 3)],
733 );
734 assert_eq!(
735 trie.range_stream(b"ab".as_slice()..)
736 .try_collect::<_, _, Vec<_>>()
737 .await?,
738 [
739 (b"ab".into(), 3),
740 (b"abc".into(), 1),
741 (b"abce".into(), 5),
742 (b"abd".into(), 2),
743 ],
744 );
745 assert_eq!(
746 trie.range_stream(b"ab".as_slice()..=b"abce".as_slice())
747 .try_collect::<_, _, Vec<_>>()
748 .await?,
749 [(b"ab".into(), 3), (b"abc".into(), 1), (b"abce".into(), 5)],
750 );
751 assert_eq!(trie.remove(b"a").await?.unwrap(), 4);
752 assert_eq!(trie.remove(b"ab").await?.unwrap(), 3);
753 assert_eq!(trie.remove(b"abc").await?.unwrap(), 1);
754 assert_eq!(trie.remove(b"abce").await?.unwrap(), 5);
755 assert_eq!(trie.remove(b"abd").await?.unwrap(), 2);
756 assert!(trie.is_empty());
757 Ok(())
758 }
759
760 #[apply(test!)]
761 async fn reparse() -> object_rainbow::Result<()> {
762 let mut trie = Trie::<u8>::default();
763 trie.insert(b"abc", 123).await?;
764 trie = trie.reparse()?;
765 assert_eq!(trie.get(b"abc").await?.unwrap(), 123);
766 Ok(())
767 }
768
769 #[apply(test!)]
770 async fn test_apple_apricot() -> object_rainbow::Result<()> {
771 let mut trie = Trie::<u8>::default();
772 trie.insert(b"apple", 1).await?;
773 trie.insert(b"apricot", 2).await?;
774 assert_eq!(trie.get(b"apple").await?, Some(1));
775 assert_eq!(trie.get(b"apricot").await?, Some(2));
776 Ok(())
777 }
778
779 #[apply(test!)]
780 async fn append() -> object_rainbow::Result<()> {
781 let mut enormita = TrieSet::new();
782 enormita.insert(&b"Magia Baiser".to_vec()).await?;
783 enormita.insert(&b"Leopard".to_vec()).await?;
784 enormita.insert(&b"Nero Alice".to_vec()).await?;
785 let mut rd = TrieSet::new();
786 rd.insert(&b"Lord Enorme".to_vec()).await?;
787 rd.insert(&b"Loco Musica".to_vec()).await?;
788 rd.insert(&b"Leberblume".to_vec()).await?;
789 enormita.append(&mut rd).await?;
790 assert!(enormita.contains(&b"Magia Baiser".to_vec()).await?);
791 assert!(enormita.contains(&b"Leopard".to_vec()).await?);
792 assert!(enormita.contains(&b"Nero Alice".to_vec()).await?);
793 assert!(enormita.contains(&b"Lord Enorme".to_vec()).await?);
794 assert!(enormita.contains(&b"Loco Musica".to_vec()).await?);
795 assert!(enormita.contains(&b"Leberblume".to_vec()).await?);
796 assert!(rd.is_empty());
797 Ok(())
798 }
799}