content_tree/
metrics.rs

1use std::fmt::Debug;
2use std::ops::{AddAssign, SubAssign};
3
4use crate::ContentTraits;
5
6/// The index describes which fields we're tracking, and can query. Indexes let us convert
7/// cursors to positions and vice versa.
8
9pub trait TreeMetrics<E: ContentTraits> where Self: Debug + Copy + Clone + PartialEq + Eq {
10    type Update: Debug + Default + PartialEq + Eq;
11    type Value: Copy + Clone + Default + Debug + AddAssign + SubAssign + PartialEq + Eq + Sized;
12
13    fn increment_marker(marker: &mut Self::Update, entry: &E);
14    fn decrement_marker(marker: &mut Self::Update, entry: &E);
15
16    // TODO: Unused. Consider removing.
17    fn decrement_marker_by_val(marker: &mut Self::Update, val: &Self::Value);
18
19    fn update_offset_by_marker(offset: &mut Self::Value, by: &Self::Update);
20
21    fn increment_offset(offset: &mut Self::Value, by: &E);
22
23    const CAN_COUNT_ITEMS: bool = false;
24    // TODO: Unused. Consider removing.
25    fn count_items(_idx: Self::Value) -> usize { panic!("Index cannot count items") }
26}
27
28pub trait FindContent<E: ContentTraits + ContentLength>: TreeMetrics<E> {
29    fn index_to_content(offset: Self::Value) -> usize;
30}
31
32pub trait FindOffset<E: ContentTraits>: TreeMetrics<E> {
33    fn index_to_offset(offset: Self::Value) -> usize;
34}
35
36
37/// Content index - which just indexes based on the resulting size. Deletes are not counted.
38#[derive(Debug, Copy, Clone, Eq, PartialEq)]
39pub struct ContentMetrics;
40
41impl<E: ContentTraits + ContentLength> TreeMetrics<E> for ContentMetrics {
42    type Update = isize;
43    type Value = usize; // TODO: Move this to a template parameter.
44
45    fn increment_marker(marker: &mut Self::Update, entry: &E) {
46        *marker += entry.content_len() as isize;
47    }
48
49    fn decrement_marker(marker: &mut Self::Update, entry: &E) {
50        *marker -= entry.content_len() as isize;
51        // dbg!(&marker, entry);
52    }
53
54    fn decrement_marker_by_val(marker: &mut Self::Update, val: &Self::Value) {
55        *marker -= *val as isize;
56    }
57
58    fn update_offset_by_marker(offset: &mut Self::Value, by: &Self::Update) {
59        // :( I wish there were a better way to do this.
60        *offset = offset.wrapping_add(*by as Self::Value);
61    }
62
63    fn increment_offset(offset: &mut Self::Value, by: &E) {
64        *offset += by.content_len() as Self::Value;
65    }
66}
67
68impl<E: ContentTraits + ContentLength> FindContent<E> for ContentMetrics {
69    fn index_to_content(offset: Self::Value) -> usize { offset as usize }
70    // fn entry_to_num(entry: &E) -> usize { entry.content_len() }
71}
72
73/// Index based on the raw size of an element.
74#[derive(Debug, Copy, Clone, Eq, PartialEq)]
75pub struct RawPositionMetricsU32;
76
77impl<E: ContentTraits> TreeMetrics<E> for RawPositionMetricsU32 {
78    type Update = isize;
79    type Value = u32; // TODO: Move this to a template parameter.
80
81    fn increment_marker(marker: &mut Self::Update, entry: &E) {
82        *marker += entry.len() as isize;
83    }
84
85    fn decrement_marker(marker: &mut Self::Update, entry: &E) {
86        *marker -= entry.len() as isize;
87        // dbg!(&marker, entry);
88    }
89
90    fn decrement_marker_by_val(marker: &mut Self::Update, val: &Self::Value) {
91        *marker -= *val as isize;
92    }
93
94    fn update_offset_by_marker(offset: &mut Self::Value, by: &Self::Update) {
95        // :( I wish there were a better way to do this.
96        *offset = offset.wrapping_add(*by as u32);
97    }
98
99    fn increment_offset(offset: &mut Self::Value, by: &E) {
100        *offset += by.len() as u32;
101    }
102
103    const CAN_COUNT_ITEMS: bool = true;
104    fn count_items(idx: Self::Value) -> usize { idx as usize }
105}
106
107impl<E: ContentTraits> FindOffset<E> for RawPositionMetricsU32 {
108    fn index_to_offset(offset: Self::Value) -> usize { offset as usize }
109}
110
111/// Index based on the raw size of an element.
112#[derive(Debug, Copy, Clone, Eq, PartialEq)]
113pub struct RawPositionMetricsUsize;
114
115impl<E: ContentTraits> TreeMetrics<E> for RawPositionMetricsUsize {
116    type Update = isize;
117    type Value = usize;
118
119    fn increment_marker(marker: &mut Self::Update, entry: &E) {
120        *marker += entry.len() as isize;
121    }
122
123    fn decrement_marker(marker: &mut Self::Update, entry: &E) {
124        *marker -= entry.len() as isize;
125        // dbg!(&marker, entry);
126    }
127
128    fn decrement_marker_by_val(marker: &mut Self::Update, val: &Self::Value) {
129        *marker -= *val as isize;
130    }
131
132    fn update_offset_by_marker(offset: &mut Self::Value, by: &Self::Update) {
133        // :( I wish there were a better way to do this.
134        *offset = offset.wrapping_add(*by as Self::Value);
135    }
136
137    fn increment_offset(offset: &mut Self::Value, by: &E) {
138        *offset += by.len();
139    }
140
141    const CAN_COUNT_ITEMS: bool = true;
142    fn count_items(idx: Self::Value) -> usize { idx }
143}
144
145impl<E: ContentTraits> FindOffset<E> for RawPositionMetricsUsize {
146    fn index_to_offset(offset: Self::Value) -> usize { offset }
147}
148
149
150// Not sure why tuples of integers don't have AddAssign and SubAssign.
151#[derive(Debug, Copy, Clone, Default, Eq, PartialEq)]
152pub struct Pair<V: Copy + Clone + Default + AddAssign + SubAssign + PartialEq + Eq>(pub V, pub V);
153
154impl<V: Copy + Clone + Default + AddAssign + SubAssign + PartialEq + Eq> AddAssign for Pair<V> {
155    #[inline]
156    fn add_assign(&mut self, rhs: Self) {
157        self.0 += rhs.0;
158        self.1 += rhs.1;
159    }
160}
161
162impl<V: Copy + Clone + Default + AddAssign + SubAssign + PartialEq + Eq> SubAssign for Pair<V> {
163    #[inline]
164    fn sub_assign(&mut self, rhs: Self) {
165        self.0 -= rhs.0;
166        self.1 -= rhs.1;
167    }
168}
169
170/// Index based on both resulting size and raw insert position.
171///
172/// Item 0 is the raw offset position, and item 1 is the content position.
173#[derive(Debug, Copy, Clone, Eq, PartialEq)]
174pub struct FullMetricsU32;
175
176impl<E: ContentTraits + ContentLength> TreeMetrics<E> for FullMetricsU32 {
177    // In pair, len = 0, content = 1.
178    type Update = Pair<i32>;
179    type Value = Pair<u32>;
180
181    fn increment_marker(marker: &mut Self::Update, entry: &E) {
182        marker.0 += entry.len() as i32;
183        marker.1 += entry.content_len() as i32;
184    }
185
186    fn decrement_marker(marker: &mut Self::Update, entry: &E) {
187        marker.0 -= entry.len() as i32;
188        marker.1 -= entry.content_len() as i32;
189    }
190
191    fn decrement_marker_by_val(marker: &mut Self::Update, val: &Self::Value) {
192        marker.0 -= val.0 as i32;
193        marker.1 -= val.1 as i32;
194    }
195
196    fn update_offset_by_marker(offset: &mut Self::Value, by: &Self::Update) {
197        offset.0 = offset.0.wrapping_add(by.0 as u32);
198        offset.1 = offset.1.wrapping_add(by.1 as u32);
199    }
200
201    fn increment_offset(offset: &mut Self::Value, entry: &E) {
202        offset.0 += entry.len() as u32;
203        offset.1 += entry.content_len() as u32;
204    }
205
206    const CAN_COUNT_ITEMS: bool = true;
207    fn count_items(idx: Self::Value) -> usize { idx.0 as usize }
208}
209
210impl<E: ContentTraits + ContentLength> FindContent<E> for FullMetricsU32 {
211    fn index_to_content(offset: Self::Value) -> usize {
212        offset.1 as usize
213    }
214}
215
216impl<E: ContentTraits + ContentLength> FindOffset<E> for FullMetricsU32 {
217    fn index_to_offset(offset: Self::Value) -> usize {
218        offset.0 as usize
219    }
220}
221
222/// Index based on both resulting size and raw insert position.
223///
224/// Item 0 is the raw offset position, and item 1 is the content position.
225#[derive(Debug, Copy, Clone, Eq, PartialEq)]
226pub struct FullMetricsUsize;
227
228impl<E: ContentTraits + ContentLength> TreeMetrics<E> for FullMetricsUsize {
229    // In pair, len = 0, content = 1.
230    type Update = Pair<isize>;
231    type Value = Pair<usize>;
232
233    fn increment_marker(marker: &mut Self::Update, entry: &E) {
234        marker.0 += entry.len() as isize;
235        marker.1 += entry.content_len() as isize;
236    }
237
238    fn decrement_marker(marker: &mut Self::Update, entry: &E) {
239        marker.0 -= entry.len() as isize;
240        marker.1 -= entry.content_len() as isize;
241    }
242
243    fn decrement_marker_by_val(marker: &mut Self::Update, val: &Self::Value) {
244        marker.0 -= val.0 as isize;
245        marker.1 -= val.1 as isize;
246    }
247
248    fn update_offset_by_marker(offset: &mut Self::Value, by: &Self::Update) {
249        offset.0 = offset.0.wrapping_add(by.0 as usize);
250        offset.1 = offset.1.wrapping_add(by.1 as usize);
251    }
252
253    fn increment_offset(offset: &mut Self::Value, entry: &E) {
254        offset.0 += entry.len();
255        offset.1 += entry.content_len();
256    }
257
258    const CAN_COUNT_ITEMS: bool = true;
259    fn count_items(idx: Self::Value) -> usize { idx.0 }
260}
261
262impl<E: ContentTraits + ContentLength> FindContent<E> for FullMetricsUsize {
263    fn index_to_content(offset: Self::Value) -> usize {
264        offset.1
265    }
266}
267
268impl<E: ContentTraits + ContentLength> FindOffset<E> for FullMetricsUsize {
269    fn index_to_offset(offset: Self::Value) -> usize {
270        offset.0
271    }
272}
273
274
275
276pub trait ContentLength {
277    /// User specific content length. Used by content-tree for character counts.
278    fn content_len(&self) -> usize;
279    fn content_len_at_offset(&self, offset: usize) -> usize;
280    fn offset_len_at_content(&self, content: usize) -> usize { content }
281}
282
283/// This trait marks items as being able to toggle on and off. The motivation for this is CRDT
284/// items which want to stay in a list even after they've been deleted.
285pub trait Toggleable {
286    fn is_activated(&self) -> bool;
287    fn is_deactivated(&self) -> bool {
288        !self.is_activated()
289    }
290    fn mark_activated(&mut self);
291    fn mark_deactivated(&mut self);
292}
content_tree/metrics.rs

content_tree/
metrics.rs
