1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

//! Run length encoding library.
//!
//! There are many mergeable types. By merging them together we can get a more compact representation of the data.
//! For example, in many cases, `[0..5, 5..10]` can be merged into `0..10`.
//!
//! # RleVec
//!
//! RleVec<T> is a vector that can be compressed using run-length encoding.
//!
//! A T value may be merged with its neighbors. When we push new element, the new value
//! may be merged with the last element in the array. Each value has a length, so there
//! are two types of indexes:
//! 1. (merged) It refers to the index of the merged element.
//! 2. (atom) The index of substantial elements. It refers to the index of the atom element.
//!
//! By default, we use atom index in RleVec.
//! - len() returns the number of atom elements in the array.
//! - get(index) returns the atom element at the index.
//! - slice(from, to) returns a slice of atom elements from the index from to the index to.
//!
//!
#![deny(clippy::undocumented_unsafe_blocks)]
mod rle_trait;
mod rle_vec;
pub use crate::rle_trait::{
    HasIndex, HasLength, Mergable, Rle, RleCollection, RlePush, Slice, Sliceable, ZeroElement,
};
pub use crate::rle_vec::{slice_vec_by, RleVec, RleVecWithLen};
pub mod rle_impl;

use num::Integer;

#[derive(Clone)]
pub struct SearchResult<'a, T, I: Integer> {
    pub element: &'a T,
    pub merged_index: usize,
    pub offset: I,
}

pub struct SliceIterator<'a, T> {
    vec: &'a [T],
    cur_index: usize,
    cur_offset: usize,
    end_index: Option<usize>,
    end_offset: Option<usize>,
}

impl<'a, T> SliceIterator<'a, T> {
    fn new_empty() -> Self {
        Self {
            vec: &[],
            cur_index: 0,
            cur_offset: 0,
            end_index: None,
            end_offset: None,
        }
    }
}

impl<'a, T: HasLength> Iterator for SliceIterator<'a, T> {
    type Item = Slice<'a, T>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.vec.is_empty() {
            return None;
        }

        let end_index = self.end_index.unwrap_or(self.vec.len() - 1);
        if self.cur_index == end_index {
            let elem = &self.vec[self.cur_index];
            let end = self.end_offset.unwrap_or_else(|| elem.atom_len());
            if self.cur_offset == end {
                return None;
            }

            let ans = Slice {
                value: elem,
                start: self.cur_offset,
                end,
            };
            self.cur_offset = end;
            return Some(ans);
        }

        let ans = Slice {
            value: &self.vec[self.cur_index],
            start: self.cur_offset,
            end: self.vec[self.cur_index].atom_len(),
        };

        self.cur_index += 1;
        self.cur_offset = 0;
        Some(ans)
    }
}