catvec/
lib.rs

1use std::{
2    ops::{Bound, RangeBounds},
3    sync::Arc,
4};
5
6use btree::Tree;
7use tap::Tap;
8
9mod btree;
10
11/// A persistent, efficiently concatenable and sliceable vector. The const-generic type parameter ORD is the maximum fanout factor; a value from 32 to 128 usually works well.
12#[derive(Clone)]
13pub struct CatVec<T: Clone, const ORD: usize> {
14    inner: Box<Tree<T, ORD>>,
15}
16
17impl<T: Clone + PartialEq, const ORD: usize> PartialEq<CatVec<T, ORD>> for CatVec<T, ORD> {
18    fn eq(&self, other: &Self) -> bool {
19        let first_length: usize = self.len();
20        let second_length: usize = other.len();
21
22        let do_lengths_match: bool = first_length == second_length;
23
24        if do_lengths_match {
25            let do_all_indexes_match: bool = (0..first_length).all(|index| {
26                let first_index: Option<&T> = self.get(index);
27                let second_index: Option<&T> = other.get(index);
28
29                first_index.expect("Failed to unrwap first index") == second_index.expect("Failed to unrwap second index")
30            });
31
32            do_all_indexes_match
33        } else {
34            do_lengths_match
35        }
36    }
37}
38
39impl<T: Clone + Eq, const ORD: usize> Eq for CatVec<T, ORD> {}
40
41
42impl<T: Clone, V: AsRef<[T]>, const ORD: usize> From<V> for CatVec<T, ORD> {
43    fn from(v: V) -> Self {
44        v.as_ref()
45            .iter()
46            .fold(CatVec::new(), |a, b| a.tap_mut(|a| a.push_back(b.clone())))
47    }
48}
49
50impl<T: Clone, const ORD: usize> From<CatVec<T, ORD>> for Vec<T> {
51    fn from(cv: CatVec<T, ORD>) -> Self {
52        let mut result = Vec::with_capacity(cv.len());
53        for i in 0..cv.len() {
54            result.push(cv.get(i).unwrap().clone());
55        }
56        result
57    }
58}
59
60impl<T: Clone + std::fmt::Debug, const ORD: usize> std::fmt::Debug for CatVec<T, ORD> {
61    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
62        let v: Vec<_> = self.clone().into();
63        std::fmt::Debug::fmt(&v, f)
64    }
65}
66
67impl<T: Clone + std::fmt::Debug, const ORD: usize> CatVec<T, ORD> {
68    /// Debug graphviz.
69    pub fn debug_graphviz(&self) {
70        Arc::new(*self.inner.clone()).eprint_graphviz();
71    }
72}
73
74impl<T: Clone, const ORD: usize> CatVec<T, ORD> {
75    /// Creates a new empty CatVec.
76    pub fn new() -> Self {
77        Self {
78            inner: Tree::new().into(),
79        }
80    }
81
82    /// Gets a reference to the element at a particular position.
83    pub fn get(&self, i: usize) -> Option<&T> {
84        self.inner.get(i)
85    }
86
87    /// Gets a mutable reference to the element at a particular position.
88    pub fn get_mut(&mut self, i: usize) -> Option<&mut T> {
89        self.inner.get_mut(i)
90    }
91
92    /// Slices a subset of the vector. "Zooms into" a part of the vector.
93    pub fn slice_into(&mut self, range: impl RangeBounds<usize>) {
94        let start = match range.start_bound() {
95            Bound::Excluded(i) => Some(*i + 1),
96            Bound::Included(i) => Some(*i),
97            Bound::Unbounded => None,
98        };
99        let end = match range.end_bound() {
100            Bound::Excluded(i) => Some(*i),
101            Bound::Included(i) => Some(*i + 1),
102            Bound::Unbounded => None,
103        };
104        if let Some(end) = end {
105            self.inner.take_head(end)
106        }
107        if let Some(start) = start {
108            self.inner.drop_head(start)
109        }
110    }
111
112    /// Concatenates this vector with another one. Consumes the other vector.
113    pub fn append(&mut self, other: Self) {
114        self.inner.concat(*other.inner)
115    }
116
117    /// Inserts the given element at the given position, shifting all elements after that rightwards.
118    pub fn insert(&mut self, idx: usize, val: T) {
119        self.inner.insert(idx, val);
120    }
121
122    /// Pushes to the back of the vector.
123    pub fn push_back(&mut self, val: T) {
124        let len = self.len();
125        self.insert(len, val)
126    }
127
128    /// Length of vector.
129    pub fn len(&self) -> usize {
130        self.inner.len()
131    }
132
133    /// Check invariant.
134    pub fn check_invariants(&self) {
135        self.inner.check_invariants();
136    }
137}
138
139impl<T: Clone, const ORD: usize> Default for CatVec<T, ORD> {
140    fn default() -> Self {
141        Self::new()
142    }
143}
catvec/lib.rs

catvec/
lib.rs
