generic_btree/
rle.rs

1use core::ops::RangeBounds;
2use std::ops::Range;
3
4/// For better performance, it's advised to impl split
5pub trait Sliceable: HasLength + Sized {
6    #[must_use]
7    fn _slice(&self, range: Range<usize>) -> Self;
8
9    #[must_use]
10    #[inline(always)]
11    fn slice(&self, range: impl RangeBounds<usize>) -> Self {
12        let start = match range.start_bound() {
13            std::ops::Bound::Included(x) => *x,
14            std::ops::Bound::Excluded(x) => x + 1,
15            std::ops::Bound::Unbounded => 0,
16        };
17
18        let end = match range.end_bound() {
19            std::ops::Bound::Included(x) => x + 1,
20            std::ops::Bound::Excluded(x) => *x,
21            std::ops::Bound::Unbounded => self.rle_len(),
22        };
23
24        self._slice(start..end)
25    }
26
27    /// slice in-place
28    #[inline(always)]
29    fn slice_(&mut self, range: impl RangeBounds<usize>) {
30        *self = self.slice(range);
31    }
32
33    #[must_use]
34    fn split(&mut self, pos: usize) -> Self {
35        let right = self.slice(pos..);
36        self.slice_(..pos);
37        right
38    }
39
40    /// Update the slice in the given range.
41    /// This method may split `self` into two or three parts.
42    /// If so, it will make `self` the leftmost part and return the next split parts.
43    ///
44    /// # Example
45    ///
46    /// If `self.rle_len() == 10`, `self.update(1..5)` will split self into three parts and update the middle part.
47    /// It returns the middle and the right part.
48    fn update_with_split(
49        &mut self,
50        range: impl RangeBounds<usize>,
51        f: impl FnOnce(&mut Self),
52    ) -> (Option<Self>, Option<Self>) {
53        let start = match range.start_bound() {
54            std::ops::Bound::Included(x) => *x,
55            std::ops::Bound::Excluded(x) => x + 1,
56            std::ops::Bound::Unbounded => 0,
57        };
58
59        let end = match range.end_bound() {
60            std::ops::Bound::Included(x) => x + 1,
61            std::ops::Bound::Excluded(x) => *x,
62            std::ops::Bound::Unbounded => self.rle_len(),
63        };
64
65        if start >= end {
66            return (None, None);
67        }
68
69        match (start == 0, end == self.rle_len()) {
70            (true, true) => {
71                f(self);
72                (None, None)
73            }
74            (true, false) => {
75                let right = self.split(end);
76                f(self);
77                (Some(right), None)
78            }
79            (false, true) => {
80                let mut right = self.split(start);
81                f(&mut right);
82                (Some(right), None)
83            }
84            (false, false) => {
85                let right = self.split(end);
86                let mut middle = self.split(start);
87                f(&mut middle);
88                (Some(middle), Some(right))
89            }
90        }
91    }
92}
93
94pub trait Mergeable {
95    /// Whether self can merge rhs with self on the left.
96    ///
97    /// Note: This is not symmetric.
98    fn can_merge(&self, rhs: &Self) -> bool;
99    fn merge_right(&mut self, rhs: &Self);
100    fn merge_left(&mut self, left: &Self);
101}
102
103pub trait HasLength {
104    fn rle_len(&self) -> usize;
105}
106
107pub trait TryInsert {
108    fn try_insert(&mut self, pos: usize, elem: Self) -> Result<(), Self>
109    where
110        Self: Sized;
111}
112
113pub trait CanRemove {
114    fn can_remove(&self) -> bool;
115}
116
117impl CanRemove for () {
118    fn can_remove(&self) -> bool {
119        true
120    }
121}
122impl CanRemove for usize {
123    fn can_remove(&self) -> bool {
124        *self == 0
125    }
126}
127impl CanRemove for isize {
128    fn can_remove(&self) -> bool {
129        *self == 0
130    }
131}
132impl CanRemove for u32 {
133    fn can_remove(&self) -> bool {
134        *self == 0
135    }
136}
137impl CanRemove for i32 {
138    fn can_remove(&self) -> bool {
139        *self == 0
140    }
141}
generic_btree/rle.rs

generic_btree/
rle.rs
