pvec/
lib.rs

1//! Persistent vectors with efficient clone, append and split
2//! operations with idiomatic Rust interface.
3//!
4//! # Provided vector types
5//! There are three public vector types available at pvec-rs:
6//! * [RbVec](crate::core::RbVec): based on RbTree with naive
7//! append and split operations. This type is not recommended
8//! for use, as it is here solely for comparison in benchmarks.
9//! * [RrbVec](crate::core::RrbVec): based on RrbTree that
10//! enables efficient append and split operations.
11//! * [PVec](crate::PVec): a persistent vector that starts out
12//! as the standard [vec](std::vec::Vec), and transitions to
13//! [RrbVec](crate::core::RrbVec) on the first clone. The cost
14//! of its operations is identical to the representation
15//! it is backed by.
16//!
17//! All vector types in the list expose exactly the same set of
18//! operations with identical API. The difference is only in the
19//! cost of operations.
20//!
21//! # Features
22//! [RbVec](crate::core::RbVec) and [RrbVec](crate::core::RrbVec)
23//! both use [Rc](https://doc.rust-lang.org/std/rc/struct.Rc.html)
24//! for garbage collection. The library provides an option to
25//! compile all vectors using [Arc](https://doc.rust-lang.org/std/sync/struct.Arc.html)
26//! if needed, especially when passing instances between threads. To compile the
27//! library with [Arc](https://doc.rust-lang.org/std/sync/struct.Arc.html), use
28//! the `arc` feature flag.
29//!
30//! All types implement [Rayon's IntoParallelIterator trait](https://docs.rs/rayon/1.3.0/rayon/iter/trait.IntoParallelIterator.html),
31//! that enables the conversion into a parallel iterator. As dependency on
32//! Rayon is optional, you will need to explicitly request the parallel
33//! iterator implementation by passing both the `arc` and `rayon_iter`
34//! feature flags.
35//!
36//! By default, the tree-based vectors have nodes that are 32 elements wide. The
37//! maximum number of child nodes is also referred to as the branching factor.
38//! This value can be changed to 4 if necessary, by specifying the `small_branch`
39//! feature flag. Though, the default value of 32 is recommended
40//! for optimal performance.
41
42#![warn(missing_docs)]
43
44#[cfg(all(feature = "arc", feature = "rayon_iter"))]
45extern crate rayon;
46
47#[macro_use]
48#[cfg(feature = "serde_serializer")]
49extern crate serde_json;
50
51use std::fmt::Debug;
52use std::ops;
53
54pub mod core;
55pub mod iter;
56
57use crate::core::RrbVec;
58
59#[cfg(not(feature = "small_branch"))]
60const BRANCH_FACTOR: usize = 32;
61
62#[cfg(feature = "small_branch")]
63const BRANCH_FACTOR: usize = 4;
64
65#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
66enum Representation<T> {
67    Flat(Vec<T>),
68    Tree(RrbVec<T>),
69}
70
71impl<T: Clone + Debug> Representation<T> {
72    #[inline(always)]
73    fn as_flat(&self) -> &Vec<T> {
74        match self {
75            Representation::Flat(ref vec) => vec,
76            Representation::Tree(..) => unreachable!(),
77        }
78    }
79
80    #[inline(always)]
81    fn as_mut_flat(&mut self) -> &mut Vec<T> {
82        match self {
83            Representation::Flat(ref mut vec) => vec,
84            Representation::Tree(..) => unreachable!(),
85        }
86    }
87
88    #[inline(always)]
89    fn as_mut_tree(&mut self) -> &mut RrbVec<T> {
90        match self {
91            Representation::Flat(..) => unreachable!(),
92            Representation::Tree(ref mut tree) => tree,
93        }
94    }
95
96    #[inline(always)]
97    fn is_flat(&self) -> bool {
98        match self {
99            Representation::Flat(..) => true,
100            Representation::Tree(..) => false,
101        }
102    }
103
104    #[inline(always)]
105    fn spill(vec: &Vec<T>) -> Representation<T> {
106        Representation::Tree(RrbVec::from(vec))
107    }
108}
109
110/// A persistent vector that is backed by the flat
111/// representation - the standard vector, or the
112/// tree-based vector when cloned.
113#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
114pub struct PVec<T>(Representation<T>);
115
116impl<T: Clone + Debug> PVec<T> {
117    /// Constructs a new, empty vector backed by the
118    /// standard vector internally.     
119    pub fn new() -> Self {
120        PVec(Representation::Flat(Vec::with_capacity(BRANCH_FACTOR)))
121    }
122
123    /// Constructs a new, empty vector backed by the
124    /// [RrbVec](crate::core::RrbVec).
125    pub fn new_with_tree() -> Self {
126        PVec(Representation::Tree(RrbVec::new()))
127    }
128
129    /// Adds an element to the back of a collection.
130    pub fn push(&mut self, item: T) {
131        match self.0 {
132            Representation::Flat(ref mut vec) => vec.push(item),
133            Representation::Tree(ref mut vec) => vec.push(item),
134        }
135    }
136
137    /// Removes the last element from a vector and
138    /// returns it, or None if it is empty.
139    pub fn pop(&mut self) -> Option<T> {
140        match self.0 {
141            Representation::Flat(ref mut vec) => vec.pop(),
142            Representation::Tree(ref mut vec) => vec.pop(),
143        }
144    }
145
146    /// Returns a reference to an element at the given
147    /// position or None if out of bounds.
148    pub fn get(&self, index: usize) -> Option<&T> {
149        match self.0 {
150            Representation::Flat(ref vec) => vec.get(index),
151            Representation::Tree(ref vec) => vec.get(index),
152        }
153    }
154
155    /// Returns a mutable reference to an element at the given
156    /// position or None if out of bounds.
157    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
158        match self.0 {
159            Representation::Flat(ref mut vec) => vec.get_mut(index),
160            Representation::Tree(ref mut vec) => vec.get_mut(index),
161        }
162    }
163
164    /// Returns the number of elements in the vector.
165    pub fn len(&self) -> usize {
166        match self.0 {
167            Representation::Flat(ref vec) => vec.len(),
168            Representation::Tree(ref vec) => vec.len(),
169        }
170    }
171
172    /// Returns true if the vector has a length of 0.
173    pub fn is_empty(&self) -> bool {
174        self.len() == 0
175    }
176
177    /// Moves all the elements of `that` into `Self` by concatenating
178    /// the underlying tree structures, leaving `other` empty.
179    /// Note, if either of vectors is tree-based, the resulting
180    /// vector will end-up being tree-based as well.
181    pub fn append(&mut self, that: &mut PVec<T>) {
182        let this = &mut self.0;
183        let that = &mut that.0;
184
185        let this_is_flat = this.is_flat();
186        let that_is_flat = that.is_flat();
187
188        if this_is_flat && that_is_flat {
189            this.as_mut_flat().append(that.as_mut_flat());
190        } else if this_is_flat {
191            let mut vec = RrbVec::from(this.as_flat());
192            vec.append(that.as_mut_tree());
193
194            *this = Representation::Tree(vec);
195        } else if that_is_flat {
196            let mut vec = RrbVec::from(that.as_flat());
197            this.as_mut_tree().append(&mut vec);
198        } else {
199            this.as_mut_tree().append(that.as_mut_tree());
200        }
201    }
202
203    /// Splits the collection into two at the given index.
204    ///
205    /// Returns a vector containing the elements in the range [at, len).
206    /// After the call, the original vector will be left
207    /// containing the elements [0, at).
208    pub fn split_off(&mut self, mid: usize) -> Self {
209        let representation = match self.0 {
210            Representation::Flat(ref mut vec) => Representation::Flat(vec.split_off(mid)),
211            Representation::Tree(ref mut vec) => Representation::Tree(vec.split_off(mid)),
212        };
213
214        PVec(representation)
215    }
216}
217
218impl<T: Clone + Debug> Default for PVec<T> {
219    fn default() -> Self {
220        PVec::new()
221    }
222}
223
224impl<T: Clone + Debug> Clone for PVec<T> {
225    fn clone(&self) -> Self {
226        let representation = match self.0 {
227            Representation::Flat(ref vec) => Representation::spill(vec),
228            Representation::Tree(ref vec) => Representation::Tree(vec.clone()),
229        };
230
231        PVec(representation)
232    }
233}
234
235impl<T: Clone + Debug> ops::Index<usize> for PVec<T> {
236    type Output = T;
237
238    fn index(&self, index: usize) -> &T {
239        self.get(index).unwrap_or_else(|| {
240            panic!(
241                "index `{}` out of bounds in PVec of length `{}`",
242                index,
243                self.len()
244            )
245        })
246    }
247}
248
249impl<T: Clone + Debug> ops::IndexMut<usize> for PVec<T> {
250    fn index_mut(&mut self, index: usize) -> &mut T {
251        let len = self.len();
252        self.get_mut(index).unwrap_or_else(|| {
253            panic!(
254                "index `{}` out of bounds in PVec of length `{}`",
255                index, len
256            )
257        })
258    }
259}
260
261#[cfg(test)]
262#[macro_use]
263mod test {
264    use super::PVec;
265
266    #[test]
267    fn interleaving_append_split_off_operations() {
268        let mut vec_one = PVec::new();
269        let mut value = 0;
270
271        for size in 1..(32 * 8 + 32) {
272            let mut vec_two = PVec::new();
273            for _ in 0..size {
274                vec_two.push(value);
275                value += 1;
276            }
277
278            vec_one.append(&mut vec_two);
279
280            let mid = vec_one.len() / 2;
281            let mut right = vec_one.split_off(mid);
282
283            vec_one.append(&mut right);
284            value = vec_one.len();
285        }
286
287        for i in 0..value {
288            assert_eq!(vec_one.get(i).cloned(), Some(i));
289        }
290    }
291}
pvec/lib.rs

pvec/
lib.rs
