nested/
lib.rs

Help
1//! A two dimensional collection whose purpose it to reduce heap allocations.
2//!
3//! This crate is intended to be used when:
4//! - you want a potentially large:
5//!   - `Vec<String>`
6//!   - `Vec<Vec<T>>`
7//!   - `Vec<C>` where `C` is heap allocated, dynamically sized and can implement `Collection` trait
8//! - you actually only need to use borrowed items (`&[T]` or `&str`)
9//!
10//! Instead of having n + 1 allocations, you'll only have 2.
11//!
12//! # Example
13//!
14//! ```rust
15//! use nested::Nested;
16//!
17//! let mut v = Nested::<String>::new();
18//!
19//! // you can either populate it one by one
20//! v.push("a");
21//! v.push("bb".to_string());
22//! v.push("hhh");
23//! v.extend(vec!["iiiiii".to_string(), "jjjj".to_string()]);
24//! assert_eq!(v.len(), 5);
25//! assert_eq!(&v[0], "a");
26//! assert_eq!(&v[1], "bb");
27//!
28//! // or you can directly collect it
29//! let mut v = ["a", "b", "c", "d", "e", "f", "g"].iter().collect::<Nested<String>>();
30//! assert_eq!(v.len(), 7);
31//!
32//! // it also provides basic operations
33//! let u = v.split_off(2);
34//! assert_eq!(u.get(0), Some("c"));
35//!
36//! v.truncate(1);
37//! assert_eq!(v.pop(), Some("a".to_string()));
38//! assert_eq!(v.pop(), None);
39//! ```
40use std::iter::{repeat, FromIterator};
41use std::ops::{Index, Range};
42
43/// A `Nested` item when `T: Collection`
44pub type Item<T> = <T as Index<Range<usize>>>::Output;
45/// A `Nested<String>`
46pub type ZString = Nested<String>;
47/// A `Nested<Vec<T>>`
48pub type ZVec<T> = Nested<Vec<T>>;
49
50/// A `Collection` trait to expose basic required fn for `Nested` to work properly
51pub trait Collection: Index<Range<usize>> {
52    fn new() -> Self;
53    fn with_capacity(cap: usize) -> Self;
54    fn len(&self) -> usize;
55    fn truncate(&mut self, len: usize);
56    fn extend_from_slice(&mut self, s: &<Self as Index<Range<usize>>>::Output);
57    fn split_off(&mut self, at: usize) -> Self;
58}
59
60impl<T: Clone> Collection for Vec<T> {
61    fn len(&self) -> usize {
62        self.len()
63    }
64    fn new() -> Self {
65        Vec::new()
66    }
67    fn with_capacity(cap: usize) -> Self {
68        Vec::with_capacity(cap)
69    }
70    fn truncate(&mut self, len: usize) {
71        self.truncate(len);
72    }
73    fn extend_from_slice(&mut self, s: &<Self as Index<Range<usize>>>::Output) {
74        Vec::extend_from_slice(self, s)
75    }
76    fn split_off(&mut self, at: usize) -> Self {
77        self.split_off(at)
78    }
79}
80
81impl Collection for String {
82    fn len(&self) -> usize {
83        self.len()
84    }
85    fn new() -> Self {
86        String::new()
87    }
88    fn with_capacity(cap: usize) -> Self {
89        String::with_capacity(cap)
90    }
91    fn truncate(&mut self, len: usize) {
92        self.truncate(len);
93    }
94    fn extend_from_slice(&mut self, s: &<Self as Index<Range<usize>>>::Output) {
95        self.push_str(s)
96    }
97    fn split_off(&mut self, at: usize) -> Self {
98        self.split_off(at)
99    }
100}
101
102/// A two dimensional collection with minimal allocation
103///
104/// `T` is the owning underlying container.
105///
106/// For instance, it behaves similarly to `Vec<Vec<T>>` or `Vec<String>` but
107/// only has 2 internal buffers.
108///
109/// It can be used:
110/// - on your own collection as long as it implements the `Collection` trait.
111/// - like a sparse vector
112/// - when you need to collect (move ownership) many `String`s or `Vec<T>`s
113#[derive(Debug, Clone, PartialEq, Hash, Eq)]
114pub struct Nested<T> {
115    indices: Vec<usize>,
116    data: T,
117}
118
119impl<T: Collection> Nested<T> {
120    /// Create a new `Nested`.
121    pub fn new() -> Self {
122        Nested {
123            indices: vec![0],
124            data: T::new(),
125        }
126    }
127
128    /// Creates a new `Nested` with given capacity.
129    ///
130    /// len: the expected item count
131    /// size: the expected total size taken by all items
132    pub fn with_capacity(len: usize, size: usize) -> Self {
133        let mut indices = Vec::with_capacity(len + 1);
134        indices.push(0);
135        Nested {
136            indices: indices,
137            data: T::with_capacity(size),
138        }
139    }
140
141    /// Pushes a new item
142    pub fn push<I: AsRef<Item<T>>>(&mut self, el: I) {
143        self.data.extend_from_slice(el.as_ref());
144        let len = self.data.len();
145        self.indices.push(len);
146    }
147
148    /// Removes the last element from a `Nested` and returns it, or None if it is empty.
149    pub fn pop(&mut self) -> Option<T> {
150        if self.indices.len() > 1 {
151            let l = self.indices[self.indices.len() - 2];
152            let data = self.data.split_off(l);
153            self.indices.pop();
154            Some(data)
155        } else {
156            None
157        }
158    }
159
160    /// Extend with `count` empty elements
161    pub fn extend_empty(&mut self, count: usize) {
162        let len = self.data.len();
163        self.indices.extend(repeat(len).take(count));
164    }
165
166    /// Returns the number of elements in the `Nested`.
167    #[inline]
168    pub fn len(&self) -> usize {
169        self.indices.len() - 1
170    }
171
172    /// Get the total length taken by the data
173    #[inline]
174    pub fn data_len(&self) -> usize {
175        self.data.len()
176    }
177
178    /// Returns true if self has a length of zero.
179    #[inline]
180    pub fn is_empty(&self) -> bool {
181        self.len() == 0
182    }
183
184    /// Shortens the `Nested`, keeping the first len elements and dropping the rest.
185    ///
186    /// If len is greater than the vector's current length, this has no effect.
187    ///
188    /// Note that this method has no effect on the allocated capacity of the vector.
189    pub fn truncate(&mut self, len: usize) {
190        if len + 1 >= self.indices.len() {
191            return;
192        }
193
194        let size = self.indices[len];
195        self.indices.truncate(len + 1);
196        self.data.truncate(size);
197    }
198
199    /// Truncates this `Nested`, removing all contents.
200    ///
201    /// While this means the `Nested` will have a length of zero, it does not touch its capacity.
202    #[inline]
203    pub fn clear(&mut self) {
204        self.indices.truncate(1);
205        self.data.truncate(0);
206    }
207
208    /// Returns a shared reference to the output at this location, if in bounds.
209    pub fn get(&self, index: usize) -> Option<&Item<T>> {
210        if index >= self.len() {
211            None
212        } else {
213            Some(&self[index])
214        }
215    }
216
217    /// Converts this `Nested` into its constituent parts.
218    pub fn into_parts(self) -> (Vec<usize>, T) {
219        (self.indices, self.data)
220    }
221
222    /// Returns a reference to the underlying indices.
223    ///
224    /// Each index represents the start of each logical vector beyond the first one.
225    pub fn indices(&self) -> &[usize] {
226        &self.indices
227    }
228
229    /// Returns a reference to the underlying data.
230    ///
231    /// The data is stored contiguously.
232    pub fn data(&self) -> &T {
233        &self.data
234    }
235
236    /// Returns an iterator over `Nested` elements.
237    pub fn iter(&self) -> Iter<T> {
238        Iter {
239            windows: self.indices.windows(2),
240            data: &self.data,
241        }
242    }
243
244    /// Splits the collection into two at the given index.
245    ///
246    /// Returns a newly allocated Self. self contains elements [0, at), and the returned Self
247    /// contains elements [at, len).
248    ///
249    /// Note that the capacity of self does not change.
250    pub fn split_off(&mut self, at: usize) -> Nested<T> {
251        if at == self.len() {
252            return Nested::new();
253        }
254        assert!(at < self.len());
255        let mut new_indices = self.indices.split_off(at + 1);
256        let offset = self.indices[at];
257        let new_data = self.data.split_off(offset);
258        for i in &mut new_indices {
259            *i -= offset;
260        }
261        new_indices.insert(0, 0);
262        Nested {
263            indices: new_indices,
264            data: new_data,
265        }
266    }
267}
268
269impl<T: Collection> Index<usize> for Nested<T> {
270    type Output = Item<T>;
271    fn index(&self, index: usize) -> &Self::Output {
272        assert!(index + 1 <= self.indices.len());
273        let lo = self.indices[index];
274        let hi = self.indices[index + 1];
275        &self.data.index(lo..hi)
276    }
277}
278
279impl<T: Collection, A: AsRef<Item<T>>> Extend<A> for Nested<T> {
280    fn extend<I>(&mut self, iter: I)
281    where
282        I: IntoIterator,
283        I::Item: AsRef<Item<T>>,
284    {
285        for i in iter.into_iter() {
286            self.push(i);
287        }
288    }
289}
290
291/// An iterator over `Nested` elements
292#[derive(Debug, Clone)]
293pub struct Iter<'a, T: 'a> {
294    windows: ::std::slice::Windows<'a, usize>,
295    data: &'a T,
296}
297
298impl<'a, T: Collection> Iterator for Iter<'a, T> {
299    type Item = &'a Item<T>;
300    fn next(&mut self) -> Option<Self::Item> {
301        self.windows.next().map(|w| self.data.index(w[0]..w[1]))
302    }
303    fn size_hint(&self) -> (usize, Option<usize>) {
304        self.windows.size_hint()
305    }
306}
307
308impl<'a, T: Collection> ExactSizeIterator for Iter<'a, T> {
309    fn len(&self) -> usize {
310        self.windows.len()
311    }
312}
313
314impl<'a, T: Collection> DoubleEndedIterator for Iter<'a, T> {
315    fn next_back(&mut self) -> Option<<Self as Iterator>::Item> {
316        self.windows
317            .next_back()
318            .map(|w| self.data.index(w[0]..w[1]))
319    }
320}
321
322impl<T: Collection, A: AsRef<Item<T>>> FromIterator<A> for Nested<T> {
323    fn from_iter<I: IntoIterator<Item = A>>(iter: I) -> Self {
324        let iter = iter.into_iter();
325        let mut v = match iter.size_hint() {
326            (0, None) => Nested::new(),
327            (_, Some(l)) | (l, None) => Nested::with_capacity(l, l * 4),
328        };
329        v.extend(iter);
330        v
331    }
332}
333
334#[cfg(test)]
335mod tests {
336    use super::*;
337
338    #[test]
339    fn test_string() {
340        let mut v = Nested::<String>::new();
341        v.push("aaa");
342        v.push("bbb".to_string());
343        assert_eq!(v.len(), 2);
344        assert_eq!(&v[0], "aaa");
345        assert_eq!(&v[1], "bbb");
346        v.truncate(1);
347        assert_eq!(v.len(), 1);
348        assert_eq!(&v[0], "aaa");
349        assert_eq!(v.get(1), None);
350        v.extend_empty(3);
351        assert_eq!(v.len(), 4);
352        assert_eq!(&v[2], "");
353    }
354
355    #[test]
356    fn test_vec() {
357        let mut v = Nested::<Vec<_>>::new();
358        v.push(&[1, 2, 3]);
359        v.push(vec![1, 2, 4]);
360        assert_eq!(v.len(), 2);
361        assert_eq!(&v[0], &[1, 2, 3]);
362        assert_eq!(&v[1], &[1, 2, 4]);
363        v.truncate(1);
364        assert_eq!(v.len(), 1);
365        assert_eq!(&v[0], &[1, 2, 3]);
366        assert_eq!(v.get(1), None);
367        v.extend_empty(3);
368        assert_eq!(v.len(), 4);
369        assert_eq!(&v[2], &[]);
370    }
371
372    #[test]
373    fn test_collect() {
374        let sce = vec![
375            "a".to_string(),
376            "b".to_string(),
377            "c".to_string(),
378            "d".to_string(),
379        ];
380        let v = sce.iter().collect::<Nested<String>>();
381        assert_eq!(v.len(), 4);
382        assert_eq!(&v[0], "a");
383        assert_eq!(&v[1], "b");
384        assert_eq!(&v[2], "c");
385        assert_eq!(&v[3], "d");
386
387        let sce = vec!["a", "b", "c", "d"];
388        let v2 = sce.iter().collect::<Nested<String>>();
389        assert_eq!(v, v2);
390    }
391
392    #[test]
393    fn test_iter() {
394        let sce = vec![
395            "a".to_string(),
396            "b".to_string(),
397            "c".to_string(),
398            "d".to_string(),
399        ];
400        let v = sce.iter().collect::<Nested<String>>();
401        let new_sce = v.iter().map(|s| s.to_string()).collect::<Vec<_>>();
402        assert_eq!(sce, new_sce);
403    }
404
405    #[test]
406    fn test_split_off() {
407        let mut v = ["a", "b", "c", "d"].iter().collect::<Nested<String>>();
408        assert_eq!(v.len(), 4);
409        let u = v.split_off(2);
410        assert_eq!(v.len(), 2);
411        assert_eq!(u.len(), 2);
412        assert!(v.iter().zip(["a", "b"].iter()).all(|(r, l)| l.eq(&r)));
413        assert!(u.iter().zip(["c", "d"].iter()).all(|(r, l)| l.eq(&r)));
414    }
415
416    #[test]
417    fn test_pop() {
418        let mut v = ["a", "b", "c", "d"].iter().collect::<Nested<String>>();
419        assert_eq!(v.len(), 4);
420        assert_eq!(v.pop(), Some("d".to_string()));
421        assert_eq!(v.len(), 3);
422        assert_eq!(v.pop(), Some("c".to_string()));
423        assert_eq!(v.len(), 2);
424        assert_eq!(v.pop(), Some("b".to_string()));
425        assert_eq!(v.len(), 1);
426        assert_eq!(v.pop(), Some("a".to_string()));
427        assert_eq!(v.len(), 0);
428        assert_eq!(v.pop(), None);
429        assert_eq!(v.len(), 0);
430    }
431}
nested/lib.rs

nested/
lib.rs
