loro_rle/
rle_trait.rs

1use std::fmt::Debug;
2
3use num::{traits::AsPrimitive, FromPrimitive, Integer};
4use smallvec::{Array, SmallVec};
5
6use crate::SearchResult;
7
8pub trait Mergable<Cfg = ()> {
9    fn is_mergable(&self, _other: &Self, _conf: &Cfg) -> bool
10    where
11        Self: Sized,
12    {
13        false
14    }
15
16    fn merge(&mut self, _other: &Self, _conf: &Cfg)
17    where
18        Self: Sized,
19    {
20        unreachable!()
21    }
22}
23
24/// NOTE: [Sliceable] implementation should be coherent with [Mergable]:
25///
26/// - For all k, a.slice(0,k).merge(a.slice(k, a.len())) == a
27pub trait Sliceable {
28    fn slice(&self, from: usize, to: usize) -> Self;
29}
30
31#[derive(Debug, Clone, Copy)]
32pub struct Slice<'a, T> {
33    pub value: &'a T,
34    pub start: usize,
35    pub end: usize,
36}
37
38impl<T: Sliceable> Slice<'_, T> {
39    pub fn into_inner(&self) -> T {
40        self.value.slice(self.start, self.end)
41    }
42}
43
44#[allow(clippy::len_without_is_empty)]
45pub trait HasLength {
46    /// It is the length of the content, i.e. the length when no [Mergable::merge] ever happen.
47    ///
48    /// However, when the content is deleted, [HasLength::content_len] is expected to be zero in some [crate::RleTree] use cases
49    fn content_len(&self) -> usize;
50
51    /// It is the length of the atom element underneath, i.e. the length when no [Mergable::merge] ever happen.
52    ///
53    /// It is the same as [HasLength::atom_len] in the most of the cases.
54    /// However, oppose to [HasLength::atom_len], when the content is deleted, [HasLength::content_len] should not change
55    fn atom_len(&self) -> usize {
56        self.content_len()
57    }
58}
59
60pub trait Rle<Cfg = ()>: HasLength + Sliceable + Mergable<Cfg> + Debug + Clone {}
61
62pub trait ZeroElement {
63    fn zero_element() -> Self;
64}
65
66impl<T: Default> ZeroElement for T {
67    fn zero_element() -> Self {
68        Default::default()
69    }
70}
71
72impl<T: HasLength + Sliceable + Mergable<Cfg> + Debug + Clone, Cfg> Rle<Cfg> for T {}
73
74pub trait HasIndex: HasLength {
75    type Int: GlobalIndex;
76    fn get_start_index(&self) -> Self::Int;
77
78    #[inline]
79    fn get_end_index(&self) -> Self::Int {
80        self.get_start_index() + Self::Int::from_usize(self.atom_len()).unwrap()
81    }
82}
83
84pub trait GlobalIndex:
85    Debug + Integer + Copy + Default + FromPrimitive + AsPrimitive<usize>
86{
87}
88
89impl<T: Debug + Integer + Copy + Default + FromPrimitive + AsPrimitive<usize>> GlobalIndex for T {}
90
91impl HasLength for String {
92    fn content_len(&self) -> usize {
93        self.len()
94    }
95}
96
97impl<T> HasLength for Vec<T> {
98    fn content_len(&self) -> usize {
99        self.len()
100    }
101}
102
103impl<T: Clone> Sliceable for Vec<T> {
104    fn slice(&self, from: usize, to: usize) -> Self {
105        self[from..to].to_vec()
106    }
107}
108
109impl Sliceable for String {
110    fn slice(&self, from: usize, to: usize) -> Self {
111        self[from..to].to_string()
112    }
113}
114
115pub trait RlePush<T> {
116    fn push_rle_element(&mut self, element: T);
117}
118
119pub trait RleCollection<T: HasIndex> {
120    fn start(&self) -> <T as HasIndex>::Int;
121    fn end(&self) -> <T as HasIndex>::Int;
122    fn sum_atom_len(&self) -> <T as HasIndex>::Int;
123    fn search_atom_index(&self, index: <T as HasIndex>::Int) -> usize;
124    fn get_by_atom_index(
125        &self,
126        index: <T as HasIndex>::Int,
127    ) -> Option<SearchResult<'_, T, <T as HasIndex>::Int>>;
128}
129
130impl<T: Mergable> RlePush<T> for Vec<T> {
131    fn push_rle_element(&mut self, element: T) {
132        match self.last_mut() {
133            Some(last) if last.is_mergable(&element, &()) => {
134                last.merge(&element, &());
135            }
136            _ => {
137                self.push(element);
138            }
139        }
140    }
141}
142
143impl<T: Mergable + HasIndex + HasLength> RleCollection<T> for Vec<T> {
144    fn search_atom_index(&self, index: <T as HasIndex>::Int) -> usize {
145        let mut start = 0;
146        let mut end = self.len() - 1;
147        while start < end {
148            let mid = (start + end) / 2;
149            match self[mid].get_start_index().cmp(&index) {
150                std::cmp::Ordering::Equal => {
151                    start = mid;
152                    break;
153                }
154                std::cmp::Ordering::Less => {
155                    start = mid + 1;
156                }
157                std::cmp::Ordering::Greater => {
158                    end = mid;
159                }
160            }
161        }
162
163        if index < self[start].get_start_index() {
164            start -= 1;
165        }
166        start
167    }
168
169    fn get_by_atom_index(
170        &self,
171        index: <T as HasIndex>::Int,
172    ) -> Option<SearchResult<'_, T, <T as HasIndex>::Int>> {
173        if index > self.end() {
174            return None;
175        }
176
177        let merged_index = self.search_atom_index(index);
178        let value = &self[merged_index];
179        Some(SearchResult {
180            merged_index,
181            element: value,
182            offset: index - self[merged_index].get_start_index(),
183        })
184    }
185
186    fn start(&self) -> <T as HasIndex>::Int {
187        self.first()
188            .map(|x| x.get_start_index())
189            .unwrap_or_default()
190    }
191
192    fn end(&self) -> <T as HasIndex>::Int {
193        self.last().map(|x| x.get_end_index()).unwrap_or_default()
194    }
195
196    fn sum_atom_len(&self) -> <T as HasIndex>::Int {
197        self.end() - self.start()
198    }
199}
200
201impl<A: Array> RlePush<A::Item> for SmallVec<A>
202where
203    A::Item: Mergable,
204{
205    fn push_rle_element(&mut self, element: A::Item) {
206        match self.last_mut() {
207            Some(last) if last.is_mergable(&element, &()) => {
208                last.merge(&element, &());
209            }
210            _ => {
211                self.push(element);
212            }
213        }
214    }
215}
loro_rle/rle_trait.rs

loro_rle/
rle_trait.rs
