loro_rle/
lib.rs

1//! Run length encoding library.
2//!
3//! There are many mergeable types. By merging them together we can get a more compact representation of the data.
4//! For example, in many cases, `[0..5, 5..10]` can be merged into `0..10`.
5//!
6//! # RleVec
7//!
8//! RleVec<T> is a vector that can be compressed using run-length encoding.
9//!
10//! A T value may be merged with its neighbors. When we push new element, the new value
11//! may be merged with the last element in the array. Each value has a length, so there
12//! are two types of indexes:
13//! 1. (merged) It refers to the index of the merged element.
14//! 2. (atom) The index of substantial elements. It refers to the index of the atom element.
15//!
16//! By default, we use atom index in RleVec.
17//! - len() returns the number of atom elements in the array.
18//! - get(index) returns the atom element at the index.
19//! - slice(from, to) returns a slice of atom elements from the index from to the index to.
20//!
21//!
22#![deny(clippy::undocumented_unsafe_blocks)]
23mod rle_trait;
24mod rle_vec;
25pub use crate::rle_trait::{
26    HasIndex, HasLength, Mergable, Rle, RleCollection, RlePush, Slice, Sliceable, ZeroElement,
27};
28pub use crate::rle_vec::{slice_vec_by, RleVec, RleVecWithLen};
29pub mod rle_impl;
30
31use num::Integer;
32
33#[derive(Clone)]
34pub struct SearchResult<'a, T, I: Integer> {
35    pub element: &'a T,
36    pub merged_index: usize,
37    pub offset: I,
38}
39
40pub struct SliceIterator<'a, T> {
41    vec: &'a [T],
42    cur_index: usize,
43    cur_offset: usize,
44    end_index: Option<usize>,
45    end_offset: Option<usize>,
46}
47
48impl<T> SliceIterator<'_, T> {
49    fn new_empty() -> Self {
50        Self {
51            vec: &[],
52            cur_index: 0,
53            cur_offset: 0,
54            end_index: None,
55            end_offset: None,
56        }
57    }
58}
59
60impl<'a, T: HasLength> Iterator for SliceIterator<'a, T> {
61    type Item = Slice<'a, T>;
62
63    fn next(&mut self) -> Option<Self::Item> {
64        if self.vec.is_empty() {
65            return None;
66        }
67
68        let end_index = self.end_index.unwrap_or(self.vec.len() - 1);
69        if self.cur_index == end_index {
70            let elem = &self.vec[self.cur_index];
71            let end = self.end_offset.unwrap_or_else(|| elem.atom_len());
72            if self.cur_offset == end {
73                return None;
74            }
75
76            let ans = Slice {
77                value: elem,
78                start: self.cur_offset,
79                end,
80            };
81            self.cur_offset = end;
82            return Some(ans);
83        }
84
85        let ans = Slice {
86            value: &self.vec[self.cur_index],
87            start: self.cur_offset,
88            end: self.vec[self.cur_index].atom_len(),
89        };
90
91        self.cur_index += 1;
92        self.cur_offset = 0;
93        Some(ans)
94    }
95}
loro_rle/lib.rs

loro_rle/
lib.rs
