generic_btree/generic_impl/
len_finder.rs

1use std::fmt::Debug;
2
3use thunderdome::Index;
4
5use crate::rle::HasLength;
6use crate::{BTreeTrait, FindResult, Query};
7
8/// A generic length finder
9pub struct LengthFinder {
10    pub left: usize,
11    pub slot: u8,
12    pub parent: Option<Index>,
13}
14
15impl LengthFinder {
16    #[inline(always)]
17    pub fn new() -> Self {
18        Self {
19            left: 0,
20            slot: 0,
21            parent: None,
22        }
23    }
24}
25
26impl Default for LengthFinder {
27    #[inline(always)]
28    fn default() -> Self {
29        Self::new()
30    }
31}
32
33pub trait UseLengthFinder<B: BTreeTrait> {
34    fn get_len(cache: &B::Cache) -> usize;
35}
36
37impl<Elem: HasLength + Debug, B: BTreeTrait<Elem = Elem> + UseLengthFinder<B>> Query<B>
38    for LengthFinder
39{
40    type QueryArg = usize;
41
42    #[inline(always)]
43    fn init(target: &Self::QueryArg) -> Self {
44        Self {
45            left: *target,
46            slot: 0,
47            parent: None,
48        }
49    }
50
51    #[inline(always)]
52    fn find_node(
53        &mut self,
54        _: &Self::QueryArg,
55        child_caches: &[crate::Child<B>],
56    ) -> crate::FindResult {
57        let mut last_left = self.left;
58        let is_internal = child_caches.first().unwrap().is_internal();
59        for (i, cache) in child_caches.iter().enumerate() {
60            let len = B::get_len(&cache.cache);
61            if self.left >= len {
62                last_left = self.left;
63                self.left -= len;
64            } else {
65                if is_internal {
66                    self.parent = Some(cache.arena.unwrap());
67                } else {
68                    self.slot = i as u8;
69                }
70                return FindResult::new_found(i, self.left);
71            }
72        }
73
74        self.left = last_left;
75        if is_internal {
76            self.parent = Some(child_caches.last().unwrap().arena.unwrap());
77        } else {
78            self.slot = child_caches.len() as u8 - 1;
79        }
80        FindResult::new_missing(child_caches.len() - 1, last_left)
81    }
82
83    #[inline(always)]
84    fn confirm_elem(
85        &mut self,
86        _: &Self::QueryArg,
87        elem: &<B as BTreeTrait>::Elem,
88    ) -> (usize, bool) {
89        (self.left, self.left < elem.rle_len())
90    }
91}
generic_btree/generic_impl/len_finder.rs

generic_btree/generic_impl/
len_finder.rs
