rle_vec/
lib.rs

1#![doc(html_root_url = "https://docs.rs/rle_vec/0.4.1")]
2
3//! This crate provides `RleVec`, a vector like structure that stores runs of identical values coded
4//! by the value and the number of repeats.
5//!
6//! If your data consists of long stretches of identical values is can be beneficial to only store
7//! the number of times each value occurs. This can result in significant space savings, but there
8//! is a cost. Accessing an arbitrary index requires a binary search over the stored runs resulting
9//! in a O(log n) complexity versus O(1) for a normal vector. Other complexities are in the table
10//! where n is equal to the number of runs, not the length of a comparable Vec.
11//!
12//! |        |push|index   |set with breaking a run|set without breaking a run|insert with breaking a run|insert without breaking a run|
13//! |--------|----|--------|-----------------------|--------------------------|--------------------------|-----------------------------|
14//! |`RleVec`|O(1)|O(log&nbsp;n)|O((log&nbsp;n)&nbsp;+&nbsp;2n)|O(log&nbsp;n)|O((log&nbsp;n)&nbsp;+&nbsp;2n)|O((log&nbsp;n)&nbsp;+&nbsp;n)|
15//! |`Vec`|O(1)|O(1)|O(1)*| |O(n)| |
16//!
17#[cfg(feature = "serde")]
18extern crate serde;
19#[cfg(feature = "serde")]
20#[macro_use]
21extern crate serde_derive;
22
23use std::io;
24use std::iter::FromIterator;
25use std::iter::{once, repeat};
26use std::cmp;
27use std::ops::Index;
28
29/// The `RleVec` struct handles like a normal vector and supports a subset from the `Vec` methods.
30///
31/// Not all methods implemented on `Vec` are implemented for `RleVec`. All methods returning a slice
32/// cannot work for `RleVec`.
33///
34/// # Examples:
35/// ```
36/// # use rle_vec::RleVec;
37/// let mut rle = RleVec::new();
38///
39/// rle.push(10);
40/// rle.push(10);
41/// rle.push(11);
42///
43/// assert_eq!(rle[1], 10);
44/// assert_eq!(rle[2], 11);
45///
46/// rle.insert(1, 10);
47/// assert_eq!(rle.runs_len(), 2);
48///
49/// rle.set(0, 1);
50/// assert_eq!(rle.runs_len(), 3);
51/// ```
52///
53/// `RleVec` can be constructed from `Iterators` and be iterated over just like a `Vec`.
54///
55/// ```
56/// # use rle_vec::RleVec;
57/// let v = vec![0,0,0,1,1,1,1,2,2,3,4,5,4,4,4];
58///
59/// let mut rle: RleVec<_> = v.into_iter().collect();
60///
61/// assert_eq!(rle.len(), 15);
62/// assert_eq!(rle.runs_len(), 7);
63///
64/// assert_eq!(rle.iter().nth(10), Some(&4));
65/// ```
66///
67/// An `RleVec` can be indexed like a regular vector, but not mutated. Use `RleVec::set` to change the
68/// value at an index.
69///
70/// ```
71/// # use rle_vec::RleVec;
72/// let v = vec![0,0,0,1,1,1,1,2,2,3];
73/// let mut rle: RleVec<_> = v.into_iter().collect();
74///
75/// rle.set(1,2);
76/// rle.insert(4,4);
77///
78/// assert_eq!(rle.iter().cloned().collect::<Vec<_>>(), vec![0,2,0,1,4,1,1,1,2,2,3]);
79///
80/// ```
81/// `RleVec::set` and `RleVec::insert` require `T: Clone`.
82///
83/// # Indexing
84///
85/// The `RleVec` type allows to access values by index, because it implements the
86/// `Index` trait. An example will be more explicit:
87///
88/// ```
89/// # use rle_vec::RleVec;
90/// let v = vec![0, 2, 4, 6];
91/// let rle: RleVec<_> = v.into_iter().collect();
92///
93/// println!("{}", rle[1]); // it will display '2'
94/// ```
95///
96/// However be careful: if you try to access an index which isn't in the `RleVec`,
97/// your software will panic! You cannot do this:
98///
99/// ```ignore
100/// # use rle_vec::RleVec;
101/// let v = vec![0, 2, 4, 6];
102/// let rle: RleVec<_> = v.into_iter().collect();
103///
104/// println!("{}", v[6]); // it will panic!
105/// ```
106///
107/// In conclusion: always check if the index you want to get really exists
108/// before doing it.
109///
110/// # Capacity and reallocation
111///
112/// The capacity of an `RleVec` is the amount of space allocated for any future runs that will be
113/// required for the `RleVec`. This is not to be confused with the *length*, which specifies the
114/// number of actual elements that can be indexed from the `RleVec`.  If a a run needs to be
115/// added to the `RleVec` and the number of runs exceeds its capacity, its capacity will
116/// automatically be increased, but its runs will have to be reallocated.
117///
118/// For example, an `RleVec` with capacity 10 and length 0 would be an empty vector with space
119/// for 10 more runs. Pushing 10 or fewer consecutively different elements onto the vector will
120/// not change its capacity or cause reallocation to occur. However, if the `RleVec`'s length is
121/// increased to 11, it will have to reallocate, which can be slow. For this reason, if you can
122/// predict the number of runs required in your `RleVec`, it is recommended to use
123/// `RleVec::with_capacity` whenever possible to specify how many runs the `RleVec` is expected
124/// to store.
125#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
126#[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
127pub struct RleVec<T> {
128    runs: Vec<InternalRun<T>>,
129}
130
131/// Represent a run inside the `RleVec`, can be obtained from the [`runs`](struct.RleVec.html#method.runs). A run is a serie of the same value.
132///
133/// # Example
134///
135/// ```
136/// # use rle_vec::{RleVec, Run};
137/// let rle = RleVec::from(&[1, 1, 1, 1, 2, 2, 3][..]);
138///
139/// let mut iterator = rle.runs();
140/// assert_eq!(iterator.next(), Some(Run{ len: 4, value: &1 }));
141/// assert_eq!(iterator.next(), Some(Run{ len: 2, value: &2 }));
142/// assert_eq!(iterator.next(), Some(Run{ len: 1, value: &3 }));
143/// ```
144#[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
145pub struct Run<T> {
146    /// The length of this run.
147    pub len: usize,
148    /// The value of this run.
149    pub value: T,
150}
151
152#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
153#[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
154struct InternalRun<T> {
155    end: usize,
156    value: T,
157}
158
159impl<T> RleVec<T> {
160    /// Constructs a new empty `RleVec<T>`.
161    ///
162    /// The rle_vector will not allocate until elements are pushed onto it.
163    ///
164    /// # Examples
165    ///
166    /// ```
167    /// # use rle_vec::RleVec;
168    /// let rle = RleVec::<i32>::new();
169    /// ```
170    pub fn new() -> RleVec<T> {
171        RleVec { runs: Vec::new() }
172    }
173
174    /// Constructs a new empty `RleVec<T>` with capacity for the number of runs.
175    ///
176    /// Choosing this value requires knowledge about the composition of the data that is going to be inserted.
177    ///
178    /// # Example
179    /// ```
180    /// # use rle_vec::RleVec;
181    /// let mut rle = RleVec::with_capacity(10);
182    ///
183    /// // The rle_vector contains no items, even though it has capacity for more
184    /// assert_eq!(rle.len(), 0);
185    ///
186    /// // These are all done without reallocating...
187    /// for i in 0..10 {
188    ///    rle.push(i);
189    /// }
190    ///
191    /// // The rle_vector contains 10 runs and 10 elements too...
192    /// assert_eq!(rle.len(), 10);
193    /// assert_eq!(rle.runs_len(), 10);
194    ///
195    /// // this definitely won't reallocate the runs
196    /// rle.push(10);
197    /// // while this may make the rle_vector reallocate
198    /// rle.push(11);
199    /// ```
200    pub fn with_capacity(capacity: usize) -> RleVec<T> {
201        RleVec { runs: Vec::with_capacity(capacity) }
202    }
203
204    /// Returns the number of elements in the rle_vector.
205    ///
206    /// # Example
207    /// ```
208    /// # use rle_vec::RleVec;
209    /// let mut rle = RleVec::new();
210    /// rle.push(1);
211    /// rle.push(1);
212    /// rle.push(2);
213    ///
214    /// assert_eq!(rle.len(), 3);
215    /// ```
216    pub fn len(&self) -> usize {
217        match self.runs.last() {
218            Some(run) => run.end + 1,
219            None => 0,
220        }
221    }
222
223    /// Returns `true` if the rle_vector contains no elements.
224    ///
225    /// # Example
226    /// ```
227    /// # use rle_vec::RleVec;
228    /// let mut rle = RleVec::new();
229    /// assert!(rle.is_empty());
230    ///
231    /// rle.push(1);
232    /// assert!(!rle.is_empty());
233    /// ```
234    pub fn is_empty(&self) -> bool {
235        self.runs.is_empty()
236    }
237
238    /// Clears the vector, removing all values.
239    ///
240    /// Note that this method has no effect on the allocated capacity of the vector.
241    ///
242    /// # Examples
243    /// ```
244    /// # use rle_vec::RleVec;
245    /// let mut rle = RleVec::from(&[1, 1, 1, 1, 2, 2, 3][..]);
246    ///
247    /// rle.clear();
248    /// assert!(rle.is_empty());
249    /// ```
250    pub fn clear(&mut self) {
251        self.runs.clear()
252    }
253
254    /// Returns the last value, or None if it is empty.
255    ///
256    /// # Example
257    /// ```
258    /// # use rle_vec::RleVec;
259    /// let rle = RleVec::from(&[10, 10, 40, 40, 30][..]);
260    /// assert_eq!(rle.last(), Some(&30));
261    ///
262    /// let rle = RleVec::<i32>::new();
263    /// assert_eq!(rle.last(), None);
264    /// ```
265    pub fn last(&self) -> Option<&T> {
266        match self.runs.last() {
267            Some(last) => Some(&last.value),
268            None => None,
269        }
270    }
271
272    /// Returns the last run, or None if it is empty.
273    ///
274    /// # Example
275    /// ```
276    /// # use rle_vec::{RleVec, Run};
277    /// let mut rle = RleVec::new();
278    ///
279    /// assert_eq!(rle.last_run(), None);
280    ///
281    /// rle.push(1);
282    /// rle.push(1);
283    /// rle.push(1);
284    /// rle.push(1);
285    ///
286    /// assert_eq!(rle.last_run(), Some(Run{ len: 4, value: &1 }));
287    ///
288    /// rle.push(2);
289    /// rle.push(2);
290    /// rle.push(3);
291    ///
292    /// assert_eq!(rle.last_run(), Some(Run{ len: 1, value: &3 }));
293    /// ```
294    pub fn last_run(&self) -> Option<Run<&T>> {
295        let previous_end = if self.runs.len() >= 2 {
296            self.runs[self.runs.len() - 2].end + 1
297        } else { 0 };
298
299        match self.runs.last() {
300            Some(last) => Some(Run {
301                len: last.end + 1 - previous_end,
302                value: &last.value
303            }),
304            None => None,
305        }
306    }
307
308    /// Returns the number of runs
309    ///
310    /// # Example
311    /// ```
312    /// # use rle_vec::RleVec;
313    /// let mut rle = RleVec::new();
314    /// assert_eq!(rle.runs_len(), 0);
315    ///
316    /// rle.push(1);
317    /// rle.push(1);
318    /// assert_eq!(rle.runs_len(), 1);
319    ///
320    /// rle.push(2);
321    /// rle.push(3);
322    /// assert_eq!(rle.runs_len(), 3);
323    /// ```
324    pub fn runs_len(&self) -> usize {
325        self.runs.len()
326    }
327
328    /// Returns the 0-based start coordinates of the runs
329    ///
330    /// # Example
331    /// ```
332    /// # use rle_vec::RleVec;
333    /// let mut rle = RleVec::new();
334    /// rle.push(1);
335    /// rle.push(1);
336    /// rle.push(2);
337    /// rle.push(2);
338    /// rle.push(3);
339    ///
340    /// let starts = rle.starts();
341    /// assert_eq!(starts, vec![0, 2, 4]);
342    /// ```
343    pub fn starts(&self) -> Vec<usize> {
344        if self.is_empty() { return Vec::new() }
345        once(0).chain(self.runs.iter().take(self.runs_len() - 1).map(|r| r.end + 1)).collect()
346    }
347
348    /// Returns the 0-based end coordinates of the runs
349    pub fn ends(&self) -> Vec<usize> {
350        self.runs.iter().map(|r| r.end).collect()
351    }
352
353    /// Returns an iterator over values. Comparable to a `Vec` iterator.
354    ///
355    /// # Example
356    /// ```
357    /// # use rle_vec::RleVec;
358    /// let mut rle = RleVec::new();
359    /// rle.push(1);
360    /// rle.push(1);
361    /// rle.push(2);
362    /// rle.push(3);
363    ///
364    /// let mut iterator = rle.iter();
365    ///
366    /// assert_eq!(iterator.next(), Some(&1));
367    /// assert_eq!(iterator.next(), Some(&1));
368    /// assert_eq!(iterator.next(), Some(&2));
369    /// assert_eq!(iterator.next(), Some(&3));
370    /// assert_eq!(iterator.next(), None);
371    /// ```
372    pub fn iter(&self) -> Iter<T> {
373        Iter {
374            rle: self,
375            run_index: 0,
376            index: 0,
377            run_index_back: self.runs.len().saturating_sub(1),
378            index_back: self.len(), // starts out of range
379        }
380    }
381
382    /// Returns an iterator that can be used to iterate over the runs.
383    ///
384    /// # Example
385    /// ```
386    /// # use rle_vec::{RleVec, Run};
387    /// let mut rle = RleVec::new();
388    /// rle.push(1);
389    /// rle.push(1);
390    /// rle.push(2);
391    /// rle.push(3);
392    ///
393    /// let mut iterator = rle.runs();
394    ///
395    /// assert_eq!(iterator.next(), Some(Run{ len: 2, value: &1 }));
396    /// assert_eq!(iterator.next(), Some(Run{ len: 1, value: &2 }));
397    /// assert_eq!(iterator.next(), Some(Run{ len: 1, value: &3 }));
398    /// assert_eq!(iterator.next(), None);
399    /// ```
400    pub fn runs(&self) -> Runs<T> {
401        Runs { rle: self, run_index: 0, last_end: 0 }
402    }
403
404    fn run_index(&self, index: usize) -> usize {
405        match self.runs.binary_search_by(|run| run.end.cmp(&index)) {
406            Ok(i) => i,
407            Err(i) if i < self.runs.len() => i,
408            _ => panic!("index out of bounds: the len is {} but the index is {}", self.len(), index)
409        }
410    }
411
412    fn index_info(&self, index: usize) -> (usize, usize, usize) {
413        match self.run_index(index) {
414            0 => (0, 0, self.runs[0].end),
415            index => (index, self.runs[index - 1].end + 1, self.runs[index].end),
416        }
417    }
418}
419
420impl<T: Eq> RleVec<T> {
421    /// Appends an element to the back of this rle_vector.
422    ///
423    /// # Panics
424    /// Panics if the number of elements in the vector overflows a usize.
425    ///
426    /// # Example
427    /// ```
428    /// # use rle_vec::RleVec;
429    /// let mut rle = RleVec::new();
430    /// rle.push(1);
431    /// assert_eq!(rle[0], 1);
432    /// ```
433    #[inline]
434    pub fn push(&mut self, value: T) {
435        self.push_n(1, value);
436    }
437
438    /// Appends the same element n times to the back of this rle_vec.
439    ///
440    /// # Panics
441    /// Panics if the number of elements in the vector overflows a usize.
442    ///
443    /// # Example
444    /// ```
445    /// # use rle_vec::RleVec;
446    /// let mut rle = RleVec::new();
447    ///
448    /// // Push 10 times a 2
449    /// rle.push_n(10, 2);
450    /// assert_eq!(rle[9], 2);
451    /// ```
452    pub fn push_n(&mut self, n: usize, value: T) {
453        if n == 0 { return; }
454
455        let end = match self.runs.last_mut() {
456            Some(ref mut last) if last.value == value => return last.end += n,
457            Some(last) => last.end + n,
458            None => n - 1,
459        };
460
461        self.runs.push(InternalRun { value, end });
462    }
463}
464
465impl<T: Clone> RleVec<T> {
466    /// Construct a `Vec<T>` from this `RleVec`.
467    ///
468    /// The values of the `RleVec` are cloned to produce the final `Vec`.
469    /// This can be usefull for debugging.
470    ///
471    /// # Example
472    /// ```
473    /// # use rle_vec::RleVec;
474    /// let slice = &[0, 0, 0, 1, 1, 99, 9];
475    /// let rle = RleVec::from(&slice[..]);
476    /// let vec = rle.to_vec();
477    ///
478    /// assert_eq!(vec.as_slice(), slice);
479    /// ```
480    pub fn to_vec(&self) -> Vec<T> {
481        let mut res = Vec::with_capacity(self.len());
482        let mut p = 0;
483        for r in &self.runs {
484            let n = r.end - p + 1;
485            res.extend(repeat(r.value.clone()).take(n));
486            p += n;
487        }
488        res
489    }
490}
491
492impl<T: Eq + Clone> RleVec<T> {
493    /// Modify the value at given index.
494    ///
495    /// This can result in the breaking of a run and therefore be an expensive operation.
496    /// If the value is equal to the value currently present the complexity is
497    /// **O(log n)**. But if the run needs to be broken the complexity increases to a worst case of
498    /// **O((log n) + n)**.
499    ///
500    /// # Example
501    /// ```
502    /// # use rle_vec::RleVec;
503    /// let mut rle = RleVec::from(&[1, 1, 1, 1, 2, 2, 3][..]);
504    ///
505    /// assert_eq!(rle[2], 1);
506    /// assert_eq!(rle.len(), 7);
507    /// assert_eq!(rle.runs_len(), 3);
508    ///
509    /// rle.set(2, 3);
510    /// assert_eq!(rle[2], 3);
511    /// assert_eq!(rle.len(), 7);
512    /// assert_eq!(rle.runs_len(), 5);
513    /// ```
514    pub fn set(&mut self, index: usize, value: T) {
515        let (mut p, start, end) = self.index_info(index);
516
517        if self.runs[p].value == value { return }
518
519        // a size 1 run is replaced with the new value or joined with next or previous
520        if end - start == 0 {
521            // can we join the previous run?
522            if p > 0 && self.runs[p - 1].value == value {
523                self.runs.remove(p);
524                self.runs[p - 1].end += 1;
525                p -= 1;
526            }
527            // can we join the next run?
528            if p < self.runs.len() - 1 && self.runs[p + 1].value == value {
529                self.runs.remove(p);
530                return;
531            }
532            // only one size-1 run in Rle replace its value
533            self.runs[p].value = value;
534            return;
535        }
536
537        // run size > 1, new value can split current run or maybe merge with previous or next
538        if index == start {
539            // compare to previous run
540            if p > 0 {
541                if self.runs[p - 1].value == value {
542                    self.runs[p - 1].end += 1;
543                } else {
544                    self.runs.insert(p, InternalRun { value, end: start });
545                }
546            } else {
547                self.runs.insert(0, InternalRun { value, end: 0 });
548            }
549        } else if index == end {
550            // decrease current run length
551            self.runs[p].end -= 1;
552
553            // compare to next run
554            if p < self.runs.len() - 1 && self.runs[p + 1].value == value {
555            } else {
556                self.runs.insert(p + 1, InternalRun { value, end });
557            }
558        } else {
559            // split current run
560            self.runs[p].end = index - 1;
561            let v = self.runs[p].value.clone();
562            // this might be more efficient using split_off, push and extend?
563            // this implementation has complexity O((log n) + 2n)
564            self.runs.insert(p + 1, InternalRun { value, end: index });
565            self.runs.insert(p + 2, InternalRun { value: v, end });
566        }
567    }
568
569    /// Removes and returns the element at position index, shifting all elements after it to the left.
570    ///
571    /// # Panics
572    /// Panics if index is out of bounds.
573    ///
574    /// # Examples
575    /// ```
576    /// # use rle_vec::RleVec;
577    /// let mut rle = RleVec::from(&[1, 1, 1, 1, 2, 1, 1, 4, 4][..]);
578    ///
579    /// assert_eq!(rle.remove(4), 2);
580    /// assert_eq!(rle.runs_len(), 2);
581    /// assert_eq!(rle.to_vec(), vec![1, 1, 1, 1, 1, 1, 4, 4]);
582    /// ```
583    pub fn remove(&mut self, index: usize) -> T {
584        let (p, start, end) = self.index_info(index);
585
586        for run in self.runs[p..].iter_mut() {
587            run.end -= 1;
588        }
589
590        // if size of the run is 1
591        if end - start == 0 {
592            let InternalRun { value, .. } = self.runs.remove(p); // `p + 1` become p
593            // if value before and after are equal
594            if p > 0 && self.runs_len() > 2 && self.runs[p - 1].value == self.runs[p].value {
595                let after_end = self.runs[p].end;
596                self.runs[p - 1].end = after_end;
597                self.runs.remove(p);
598            }
599            value
600        }
601        else { self.runs[p].value.clone() }
602    }
603
604    /// Insert a value at the given index.
605    ///
606    /// Because the positions of the values after the inserted value need to be changed,
607    /// the complexity of this function is **O((log n) + 2n)**.
608    ///
609    /// # Example
610    /// ```
611    /// # use rle_vec::RleVec;
612    /// let mut rle = RleVec::from(&[1, 1, 1, 1, 2, 2, 3][..]);
613    ///
614    /// assert_eq!(rle[2], 1);
615    /// assert_eq!(rle.runs_len(), 3);
616    ///
617    /// rle.insert(2, 3);
618    /// assert_eq!(rle[2], 3);
619    /// assert_eq!(rle.runs_len(), 5);
620    /// ```
621    pub fn insert(&mut self, index: usize, value: T) {
622        if index == self.len() {
623            return self.push(value);
624        }
625
626        let (p, start, end) = self.index_info(index);
627        // increment all run ends from position p
628        for run in self.runs[p..].iter_mut() {
629            run.end += 1;
630        }
631
632        if self.runs[p].value == value { return }
633
634        // inserting value can split current run or maybe merge with previous or next
635        if index == start {
636            // compare to previous run
637            if p > 0 && self.runs[p - 1].value == value {
638                self.runs[p - 1].end += 1;
639            } else {
640                self.runs.insert(p, InternalRun { value, end: index });
641            }
642        } else {
643            // split current run
644            self.runs[p].end = index - 1;
645            self.runs.insert(p + 1, InternalRun { value, end: index });
646            let value = self.runs[p].value.clone();
647            self.runs.insert(p + 2, InternalRun { value, end: end + 1 });
648        }
649    }
650}
651
652impl<T> Index<usize> for RleVec<T> {
653    type Output = T;
654
655    fn index(&self, index: usize) -> &T {
656        &self.runs[self.run_index(index)].value
657    }
658}
659
660impl<T: Clone> Into<Vec<T>> for RleVec<T> {
661    fn into(self) -> Vec<T> {
662        self.to_vec()
663    }
664}
665
666impl<'a, T: Eq + Clone> From<&'a [T]> for RleVec<T> {
667    fn from(slice: &'a [T]) -> Self {
668        if slice.is_empty() {
669            return RleVec::new()
670        }
671
672        let mut runs = Vec::new();
673        let mut last_value = slice[0].clone();
674        for (i, v) in slice[1..].iter().enumerate() {
675            if *v != last_value {
676                runs.push(InternalRun{
677                    end: i,
678                    value: last_value,
679                });
680                last_value = v.clone();
681            }
682        }
683
684        runs.push(InternalRun{
685            end: slice.len() - 1,
686            value: last_value,
687        });
688
689        RleVec { runs }
690    }
691}
692
693impl<T: Eq> FromIterator<T> for RleVec<T> {
694    fn from_iter<I>(iter: I) -> Self where I: IntoIterator<Item=T> {
695        let mut rle = RleVec::new();
696        rle.extend(iter);
697        rle
698    }
699}
700
701impl<T: Eq> FromIterator<Run<T>> for RleVec<T> {
702    fn from_iter<I>(iter: I) -> Self where I: IntoIterator<Item=Run<T>> {
703        let iter = iter.into_iter();
704        let (lower, _) = iter.size_hint();
705
706        let mut rle = RleVec::with_capacity(lower);
707        rle.extend(iter);
708        rle
709    }
710}
711
712impl<T> Default for RleVec<T> {
713    fn default() -> Self {
714        RleVec::new()
715    }
716}
717
718impl<T: Eq> Extend<T> for RleVec<T> {
719    fn extend<I>(&mut self, iter: I) where I: IntoIterator<Item=T> {
720        let mut iter = iter.into_iter();
721        if let Some(next_value) = iter.next() {
722            // In order te possibly longer use the last run for extending the run-end we do not use the
723            // push function to add values. This gives higher performance to extending the RleVec
724            // with data consisting of large runs.
725            let (pop, end) = if let Some(last_run) = self.runs.last() {
726                if last_run.value == next_value {
727                    (true, last_run.end + 1)
728                } else {
729                    (false, last_run.end + 1)
730                }
731            } else {
732                (false, 0)
733            };
734
735            let mut rle_last = if pop {
736                let mut run = self.runs.pop().unwrap();
737                run.end = end;
738                run
739            } else {
740                InternalRun { value: next_value, end }
741            };
742
743            for value in iter {
744                if value != rle_last.value {
745                    let next_end = rle_last.end;
746                    self.runs.push(rle_last);
747                    rle_last = InternalRun { value, end: next_end };
748                }
749                rle_last.end += 1;
750            }
751            self.runs.push(rle_last);
752        }
753    }
754}
755
756impl<T: Eq> Extend<Run<T>> for RleVec<T> {
757    fn extend<I>(&mut self, iter: I) where I: IntoIterator<Item=Run<T>> {
758        for Run{ len, value } in iter {
759            self.push_n(len, value)
760        }
761    }
762}
763
764impl io::Write for RleVec<u8> {
765    fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
766        self.extend(buf.iter().cloned());
767        Ok(buf.len())
768    }
769
770    fn write_all(&mut self, buf: &[u8]) -> io::Result<()> {
771        self.extend(buf.iter().cloned());
772        Ok( () )
773    }
774
775    fn flush(&mut self) -> io::Result<()> { Ok( () ) }
776}
777
778/// Immutable `RelVec` iterator over references of values.
779///
780/// Can be obtained from the [`iter`](struct.RleVec.html#method.iter) or the `into_iter` methods.
781///
782/// # Example
783/// ```
784/// # use rle_vec::RleVec;
785/// let rle = RleVec::from(&[1, 1, 1, 1, 2, 2, 3][..]);
786///
787/// let mut iterator = rle.iter();
788/// assert_eq!(iterator.next(), Some(&1));
789/// assert_eq!(iterator.next(), Some(&1));
790/// assert_eq!(iterator.next(), Some(&1));
791/// assert_eq!(iterator.next(), Some(&1));
792/// assert_eq!(iterator.next(), Some(&2));
793/// assert_eq!(iterator.next(), Some(&2));
794/// assert_eq!(iterator.next(), Some(&3));
795/// assert_eq!(iterator.next(), None);
796/// ```
797pub struct Iter<'a, T: 'a> {
798    rle: &'a RleVec<T>,
799    run_index: usize,
800    index: usize,
801    index_back: usize,
802    run_index_back: usize,
803}
804
805impl<'a, T: 'a> IntoIterator for &'a RleVec<T> {
806    type Item = &'a T;
807    type IntoIter = Iter<'a, T>;
808
809    fn into_iter(self) -> Self::IntoIter {
810        Iter {
811            rle: self,
812            run_index: 0,
813            index: 0,
814            run_index_back: self.runs.len().saturating_sub(1),
815            index_back: self.len(), // starts out of range
816        }
817    }
818}
819
820impl<'a, T: 'a> Iterator for Iter<'a, T> {
821    type Item = &'a T;
822
823    fn next(&mut self) -> Option<Self::Item> {
824        if self.index == self.index_back {
825            return None
826        }
827        let run = &self.rle.runs[self.run_index];
828        self.index += 1;
829        if self.index > run.end {
830            self.run_index += 1;
831        }
832        Some(&run.value)
833    }
834
835    fn size_hint(&self) -> (usize, Option<usize>) {
836        let len = self.rle.len() - self.index;
837        (len, Some(len))
838    }
839
840    fn count(self) -> usize {
841        // thanks to the ExactSizeIterator impl
842        self.len()
843    }
844
845    fn last(self) -> Option<Self::Item> {
846        if self.index == self.rle.len() {
847            return None
848        }
849        self.rle.last()
850    }
851
852    fn nth(&mut self, n: usize) -> Option<Self::Item> {
853        self.index = cmp::min(self.index + n, self.rle.len());
854        self.run_index = if self.index < self.rle.len() {
855            self.rle.run_index(self.index)
856        } else {
857            self.rle.runs.len() - 1
858        };
859        self.next()
860    }
861}
862
863impl<'a, T: 'a> ExactSizeIterator for Iter<'a, T> { }
864
865impl<'a, T: 'a> DoubleEndedIterator for Iter<'a, T> {
866    fn next_back(&mut self) -> Option<Self::Item> {
867        if self.index_back == self.index {
868            return None
869        }
870        self.index_back -= 1;
871        if self.run_index_back > 0 && self.index_back <= self.rle.runs[self.run_index_back - 1].end {
872            self.run_index_back -= 1;
873        }
874        Some(&self.rle.runs[self.run_index_back].value)
875    }
876}
877
878/// Immutable `RelVec` iterator over runs.
879///
880/// Can be obtained from the [`runs`](struct.RleVec.html#method.runs) method.
881/// Because internally runs are stored using the end values a new Run is
882/// allocated in each iteration.
883///
884/// # Example
885/// ```
886/// # use rle_vec::{RleVec, Run};
887/// let rle = RleVec::from(&[1, 1, 1, 1, 2, 2, 3][..]);
888///
889/// let mut iterator = rle.runs();
890/// assert_eq!(iterator.next(), Some(Run{ len: 4, value: &1 }));
891/// assert_eq!(iterator.next(), Some(Run{ len: 2, value: &2 }));
892/// assert_eq!(iterator.next(), Some(Run{ len: 1, value: &3 }));
893/// assert_eq!(iterator.next(), None);
894/// ```
895pub struct Runs<'a, T:'a> {
896    rle: &'a RleVec<T>,
897    run_index: usize,
898    last_end: usize,
899}
900
901impl<'a, T: 'a> Iterator for Runs<'a, T> {
902    type Item = Run<&'a T>;
903
904    fn next(&mut self) -> Option<Self::Item> {
905        if self.run_index == self.rle.runs.len() {
906            return None
907        }
908        let &InternalRun { ref value, end } = self.rle.runs.index(self.run_index);
909        let len = end - self.last_end + 1;
910        self.run_index += 1;
911        self.last_end = end + 1;
912        Some(Run { len, value })
913    }
914
915    fn size_hint(&self) -> (usize, Option<usize>) {
916        let len = self.rle.runs.len() - self.run_index;
917        (len, Some(len))
918    }
919
920    fn count(self) -> usize {
921        // thanks to the ExactSizeIterator impl
922        self.len()
923    }
924
925    fn last(self) -> Option<Self::Item> {
926        if self.run_index == self.rle.runs.len() {
927            return None
928        }
929        self.rle.last_run()
930    }
931
932    fn nth(&mut self, n: usize) -> Option<Self::Item> {
933        self.run_index = cmp::min(self.run_index + n, self.rle.runs.len());
934        self.last_end = if self.run_index != 0 {
935            self.rle.runs[self.run_index - 1].end + 1
936        } else { 0 };
937        self.next()
938    }
939}
940
941impl<'a, T: 'a> ExactSizeIterator for Runs<'a, T> { }
942
943#[cfg(test)]
944mod tests {
945    use super::*;
946
947    #[test]
948    fn rare_usage() {
949        // from slice
950
951        let rle: RleVec<i32> = RleVec::from(&[][..]);
952        assert_eq!(rle.to_vec(), vec![]);
953        let runs: Vec<_> = rle.runs().collect();
954        assert_eq!(runs, vec![]);
955
956        let rle: RleVec<i32> = RleVec::from(&[1][..]);
957        assert_eq!(rle.to_vec(), vec![1]);
958        let runs: Vec<_> = rle.runs().collect();
959        assert_eq!(runs, vec![Run{ len: 1, value: &1 }]);
960
961        let rle: RleVec<i32> = RleVec::from(&[1, 2][..]);
962        assert_eq!(rle.to_vec(), vec![1, 2]);
963        let runs: Vec<_> = rle.runs().collect();
964        assert_eq!(runs, vec![Run{ len: 1, value: &1 }, Run { len: 1, value: &2 }]);
965
966        let rle: RleVec<i32> = RleVec::from(&[1, 1][..]);
967        assert_eq!(rle.to_vec(), vec![1, 1]);
968        let runs: Vec<_> = rle.runs().collect();
969        assert_eq!(runs, vec![Run{ len: 2, value: &1 }]);
970
971        // from iter
972
973        let rle: RleVec<i32> = RleVec::from_iter(0..0);
974        assert_eq!(rle.to_vec(), vec![]);
975        let runs: Vec<_> = rle.runs().collect();
976        assert_eq!(runs, vec![]);
977
978        let rle: RleVec<i32> = RleVec::from_iter(1..2);
979        assert_eq!(rle.to_vec(), vec![1]);
980        let runs: Vec<_> = rle.runs().collect();
981        assert_eq!(runs, vec![Run{ len: 1, value: &1 }]);
982
983        let rle: RleVec<i32> = RleVec::from_iter(1..3);
984        assert_eq!(rle.to_vec(), vec![1, 2]);
985        let runs: Vec<_> = rle.runs().collect();
986        assert_eq!(runs, vec![Run{ len: 1, value: &1 }, Run { len: 1, value: &2 }]);
987
988        use std::iter::repeat;
989        let rle: RleVec<i32> = RleVec::from_iter(repeat(1).take(2));
990        assert_eq!(rle.to_vec(), vec![1, 1]);
991        let runs: Vec<_> = rle.runs().collect();
992        assert_eq!(runs, vec![Run{ len: 2, value: &1 }]);
993    }
994
995    #[test]
996    fn basic_usage() {
997        let mut rle = RleVec::<i64>::new();
998        rle.push(1);
999        rle.push(1);
1000        rle.push(1);
1001        rle.push(1);
1002        rle.push(2);
1003        rle.push(2);
1004        rle.push(2);
1005        rle.push(3);
1006        rle.push(3);
1007        rle.push(4);
1008        assert_eq!(rle.len(), 10);
1009        assert_eq!(rle.runs_len(), 4);
1010
1011        rle.push_n(3, 4);
1012        assert_eq!(rle.len(), 13);
1013        assert_eq!(rle.runs_len(), 4);
1014        assert_eq!(rle.last(), Some(&4));
1015        rle.push_n(3, 5);
1016        assert_eq!(rle.len(), 16);
1017        assert_eq!(rle.runs_len(), 5);
1018        assert_eq!(rle.last(), Some(&5));
1019        assert_eq!(rle.last_run(), Some(Run {value: &5, len: 3}));
1020        rle.clear();
1021        assert_eq!(rle.len(), 0);
1022        assert_eq!(rle.runs_len(), 0);
1023        assert_eq!(rle.last(), None);
1024        assert_eq!(rle.last_run(), None);
1025
1026        let mut rle = RleVec::default();
1027        rle.push(1);
1028        assert_eq!(rle.len(), 1);
1029    }
1030
1031    #[test]
1032    fn setting_values() {
1033        let mut rle = RleVec::<i64>::new();
1034        rle.push(1);
1035        rle.set(0, 10);
1036        assert_eq!(rle.len(), 1);
1037        assert_eq!(rle.runs_len(), 1);
1038        assert_eq!(rle[0], 10);
1039
1040        let mut rle = RleVec::from(&[1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5][..]);
1041        assert_eq!(rle.to_vec(), vec![1,1,1,1,2,2,2,3,3,4, 5]);
1042
1043        //set no change
1044        //run size > 1
1045        rle.set(0, 1);
1046        assert_eq!(rle.to_vec(), vec![1,1,1,1,2,2,2,3,3,4, 5]);
1047        rle.set(2, 1);
1048        assert_eq!(rle.to_vec(), vec![1,1,1,1,2,2,2,3,3,4, 5]);
1049        rle.set(4, 2);
1050        assert_eq!(rle.to_vec(), vec![1,1,1,1,2,2,2,3,3,4, 5]);
1051        rle.set(6, 2);
1052        assert_eq!(rle.to_vec(), vec![1,1,1,1,2,2,2,3,3,4, 5]);
1053        //run size == 1
1054        rle.set(9, 4);
1055        assert_eq!(rle.to_vec(), vec![1,1,1,1,2,2,2,3,3,4, 5]);
1056        rle.set(10, 5);
1057        assert_eq!(rle.to_vec(), vec![1,1,1,1,2,2,2,3,3,4, 5]);
1058
1059        //set change no joins
1060        //run size > 1
1061        rle.set(0, 2);
1062        assert_eq!(rle.to_vec(), vec![2,1,1,1,2,2,2,3,3,4, 5]);
1063        rle.set(2, 2);
1064        assert_eq!(rle.to_vec(), vec![2,1,2,1,2,2,2,3,3,4, 5]);
1065        rle.set(4, 3);
1066        assert_eq!(rle.to_vec(), vec![2,1,2,1,3,2,2,3,3,4, 5]);
1067        rle.set(8, 7);
1068        assert_eq!(rle.to_vec(), vec![2,1,2,1,3,2,2,3,7,4, 5]);
1069        //run size == 1
1070        rle.set(0, 3);
1071        assert_eq!(rle.to_vec(), vec![3,1,2,1,3,2,2,3,7,4, 5]);
1072        rle.set(3, 4);
1073        assert_eq!(rle.to_vec(), vec![3,1,2,4,3,2,2,3,7,4, 5]);
1074        rle.set(10, 7);
1075        assert_eq!(rle.to_vec(), vec![3,1,2,4,3,2,2,3,7,4, 7]);
1076        assert_eq!(rle.runs_len(), 10);
1077
1078        //set change, with join
1079        rle.set(0, 1);
1080        assert_eq!(rle.to_vec(), vec![1,1,2,4,3,2,2,3,7,4, 7]);
1081        assert_eq!(rle.runs_len(), 9);
1082        rle.set(5, 3);
1083        assert_eq!(rle.runs_len(), 9);
1084        rle.set(6, 3);
1085        assert_eq!(rle.to_vec(), vec![1,1,2,4,3,3,3,3,7,4, 7]);
1086        assert_eq!(rle.runs_len(), 7);
1087        rle.set(10, 4);
1088        assert_eq!(rle.to_vec(), vec![1,1,2,4,3,3,3,3,7,4, 4]);
1089        assert_eq!(rle.runs_len(), 6);
1090    }
1091
1092    #[test]
1093    fn removing_values() {
1094        let mut rle = RleVec::from(&[1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 4, 3, 3][..]);
1095        assert_eq!(rle.len(), 13);
1096        assert_eq!(rle.runs_len(), 5);
1097
1098        let value = rle.remove(5);
1099        assert_eq!(value, 2);
1100        assert_eq!(rle.len(), 12);
1101        assert_eq!(rle.runs_len(), 3);
1102        assert_eq!(rle.to_vec(), vec![1, 1, 1, 1, 1, 1, 1, 1, 4, 4, 3, 3]);
1103
1104        let value = rle.remove(7);
1105        assert_eq!(value, 1);
1106        assert_eq!(rle.len(), 11);
1107        assert_eq!(rle.runs_len(), 3);
1108        assert_eq!(rle.to_vec(), vec![1, 1, 1, 1, 1, 1, 1, 4, 4, 3, 3]);
1109
1110        let value = rle.remove(10);
1111        assert_eq!(value, 3);
1112        assert_eq!(rle.len(), 10);
1113        assert_eq!(rle.runs_len(), 3);
1114        assert_eq!(rle.to_vec(), vec![1, 1, 1, 1, 1, 1, 1, 4, 4, 3]);
1115    }
1116
1117    #[test]
1118    fn inserting_values() {
1119        let mut v = vec![0,0,0,1,1,1,1,1,1,1,3,3,1,0,99,99,9];
1120        let mut rle = RleVec::from(&v[..]);
1121        rle.insert(0,1);
1122        v.insert(0,1);
1123        assert_eq!((0..rle.len()).map(|i| rle[i]).collect::<Vec<_>>(), v);
1124        assert_eq!(rle.len(),18);
1125        rle.insert(18,9);
1126        v.insert(18,9);
1127        assert_eq!((0..rle.len()).map(|i| rle[i]).collect::<Vec<_>>(), v);
1128        rle.insert(19,10);
1129        v.insert(19,10);
1130        assert_eq!((0..rle.len()).map(|i| rle[i]).collect::<Vec<_>>(), v);
1131
1132        rle.insert(2,0);
1133        v.insert(2,0);
1134        assert_eq!((0..rle.len()).map(|i| rle[i]).collect::<Vec<_>>(), v);
1135        assert_eq!(rle.runs_len(), 9);
1136
1137        rle.insert(8,0);
1138        v.insert(8,0);
1139        assert_eq!((0..rle.len()).map(|i| rle[i]).collect::<Vec<_>>(), v);
1140        assert_eq!(rle.runs_len(), 11);
1141
1142        rle.insert(13,4);
1143        v.insert(13,4);
1144        assert_eq!((0..rle.len()).map(|i| rle[i]).collect::<Vec<_>>(), v);
1145        assert_eq!(rle.runs_len(), 12);
1146
1147        let v = vec![0,0,0,1,1,1,1,2,2,3];
1148        let mut rle: RleVec<_> = v.into_iter().collect();
1149        rle.set(1,2);
1150        assert_eq!(rle.iter().cloned().collect::<Vec<_>>(), vec![0,2,0,1,1,1,1,2,2,3]);
1151        rle.insert(4,4);
1152        assert_eq!(rle.iter().cloned().collect::<Vec<_>>(), vec![0,2,0,1,4,1,1,1,2,2,3]);
1153        rle.insert(7,1);
1154        assert_eq!(rle.iter().cloned().collect::<Vec<_>>(), vec![0,2,0,1,4,1,1,1,1,2,2,3]);
1155        rle.insert(8,8);
1156        assert_eq!(rle.iter().cloned().collect::<Vec<_>>(), vec![0,2,0,1,4,1,1,1,8,1,2,2,3]);
1157    }
1158
1159    #[test]
1160    fn from_slice() {
1161        let v = vec![0,0,0,1,1,1,1,1,1,1,3,3,1,0,99,99,9];
1162        let rle = RleVec::from(&v[..]);
1163        assert_eq!((0..v.len()).map(|i| rle[i]).collect::<Vec<_>>(), v);
1164        assert_eq!(rle.len(),17);
1165
1166        let v2: Vec<_> = rle.into();
1167        assert_eq!(v2,v);
1168    }
1169
1170    #[test]
1171    fn iterators() {
1172        let v = vec![0,0,0,1,1,1,1,1,1,1,3,3,123,0,90,90,99];
1173        let rle = v.iter().cloned().collect::<RleVec<_>>();
1174        assert_eq!((0..v.len()).map(|i| rle[i]).collect::<Vec<_>>(), v);
1175        assert_eq!(rle.len(), 17);
1176
1177        assert_eq!(rle.iter().cloned().collect::<Vec<_>>(), v);
1178        assert_eq!(RleVec::<i64>::new().iter().next(), None);
1179
1180        let v2 = (0..100).collect::<Vec<usize>>();
1181        let rle2 = v2.iter().cloned().collect::<RleVec<_>>();
1182        assert_eq!(rle2.iter().cloned().collect::<Vec<_>>(), v2);
1183        assert_eq!(rle2.iter().skip(0).cloned().collect::<Vec<_>>(), v2);
1184
1185        assert_eq!(rle2.iter().nth(0), Some(&0));
1186        assert_eq!(rle2.iter().nth(5), Some(&5));
1187        assert_eq!(rle2.iter().nth(99), Some(&99));
1188        assert_eq!(rle2.iter().nth(100), None);
1189        let mut it = rle2.iter();
1190        it.nth(0);
1191        assert_eq!(it.nth(0), Some(&1));
1192
1193        assert_eq!(rle.iter().nth(3), Some(&1));
1194        assert_eq!(rle.iter().nth(14), Some(&90));
1195        assert_eq!(rle.iter().nth(15), Some(&90));
1196
1197        assert_eq!(rle.iter().skip(2).next(), Some(&0));
1198        assert_eq!(rle.iter().skip(3).next(), Some(&1));
1199
1200        assert_eq!(rle.iter().max(), Some(&123));
1201        assert_eq!(rle.iter().min(), Some(&0));
1202        assert_eq!(rle.iter().skip(13).max(), Some(&99));
1203        assert_eq!(rle.iter().skip(13).min(), Some(&0));
1204        assert_eq!(rle.iter().skip(13).take(2).max(), Some(&90));
1205        assert_eq!(rle.iter().skip(13).take(2).min(), Some(&0));
1206
1207        assert_eq!(rle.iter().count(), 17);
1208        assert_eq!(rle.iter().skip(10).last(), Some(&99));
1209        assert_eq!(rle.iter().skip(30).last(), None);
1210
1211        //runiters
1212        assert_eq!(rle.runs().map(|r| r.value).collect::<Vec<_>>(), vec![&0,&1,&3,&123,&0,&90,&99]);
1213        assert_eq!(rle.runs().map(|r| r.len).collect::<Vec<_>>(), vec![3,7,2,1,1,2,1]);
1214
1215        let mut copy = RleVec::new();
1216        for r in rle.runs() {
1217            copy.push_n(r.len, r.value.clone());
1218        }
1219        assert_eq!(copy.iter().cloned().collect::<Vec<_>>(), v);
1220        let copy2: RleVec<i32> = rle.runs().map(|r| Run { value: r.value.clone(), len: r.len }).collect();
1221        assert_eq!(copy2.iter().cloned().collect::<Vec<_>>(), v);
1222    }
1223
1224    #[test]
1225    fn back_iterators() {
1226        let rle = RleVec::from(&[0,1,1,3,3,9,99][..]);
1227
1228        // only next_back()
1229        let mut iter = rle.iter();
1230        assert_eq!(iter.next_back(), Some(&99));
1231        assert_eq!(iter.next_back(), Some(&9));
1232        assert_eq!(iter.next_back(), Some(&3));
1233        assert_eq!(iter.next_back(), Some(&3));
1234        assert_eq!(iter.next_back(), Some(&1));
1235        assert_eq!(iter.next_back(), Some(&1));
1236        assert_eq!(iter.next_back(), Some(&0));
1237        assert_eq!(iter.next_back(), None);
1238
1239        // next_back() combine with next()
1240        let mut iter = rle.iter();
1241        assert_eq!(iter.next_back(), Some(&99));
1242        assert_eq!(iter.next(),      Some(&0));
1243        assert_eq!(iter.next(),      Some(&1));
1244        assert_eq!(iter.next_back(), Some(&9));
1245        assert_eq!(iter.next_back(), Some(&3));
1246        assert_eq!(iter.next_back(), Some(&3));
1247        assert_eq!(iter.next(),      Some(&1));
1248        assert_eq!(iter.next_back(), None);
1249        assert_eq!(iter.next(),      None);
1250
1251        // rare usages of next_back() combine with next()
1252        let rle = RleVec::from(&[0][..]);
1253        let mut iter = rle.iter();
1254        assert_eq!(iter.next_back(), Some(&0));
1255        assert_eq!(iter.next(),      None);
1256
1257        let rle = RleVec::<i32>::from(&[][..]);
1258        let mut iter = rle.iter();
1259        assert_eq!(iter.next_back(), None);
1260        assert_eq!(iter.next(),      None);
1261    }
1262
1263    #[test]
1264    fn run_iters() {
1265        let rle = RleVec::from(&[1,1,1,1,1,2,2,2,2,3,3,3,5,5,5,5][..]);
1266
1267        let mut iterator = rle.runs();
1268
1269        assert_eq!(iterator.next(), Some(Run{ len: 5, value: &1 }));
1270        assert_eq!(iterator.next(), Some(Run{ len: 4, value: &2 }));
1271        assert_eq!(iterator.next(), Some(Run{ len: 3, value: &3 }));
1272        assert_eq!(iterator.next(), Some(Run{ len: 4, value: &5 }));
1273        assert_eq!(iterator.next(), None);
1274        assert_eq!(iterator.next(), None);
1275
1276        let mut iterator = rle.runs();
1277
1278        assert_eq!(iterator.nth(0), Some(Run{ len: 5, value: &1 }));
1279        assert_eq!(iterator.nth(0), Some(Run{ len: 4, value: &2 }));
1280        assert_eq!(iterator.nth(0), Some(Run{ len: 3, value: &3 }));
1281        assert_eq!(iterator.nth(0), Some(Run{ len: 4, value: &5 }));
1282        assert_eq!(iterator.nth(0), None);
1283
1284        let mut iterator = rle.runs();
1285
1286        assert_eq!(iterator.nth(0), Some(Run{ len: 5, value: &1 }));
1287        assert_eq!(iterator.nth(1), Some(Run{ len: 3, value: &3 }));
1288        assert_eq!(iterator.nth(0), Some(Run{ len: 4, value: &5 }));
1289        assert_eq!(iterator.nth(0), None);
1290
1291        assert_eq!(rle.runs().count(), 4);
1292        assert_eq!(rle.runs().last(), Some(Run{ len: 4, value: &5 }));
1293        assert_eq!(rle.runs().skip(10).last(), None);
1294
1295    }
1296
1297    #[test]
1298    fn starts_ends() {
1299        let v = vec![0,0,0,1,1,1,1,1,1,1,3,3,1,0,99,99,9];
1300        let rle = v.iter().cloned().collect::<RleVec<_>>();
1301        assert_eq!(rle.starts(), vec![0,3,10,12,13,14,16]);
1302        assert_eq!(rle.ends(),   vec![2,9,11,12,13,15,16]);
1303
1304        let rle = RleVec::<i64>::new();
1305        assert!(rle.starts().is_empty());
1306        assert!(rle.ends().is_empty());
1307    }
1308
1309    #[test]
1310    fn write_trait() {
1311        use std::io::Write;
1312        let data_in = vec![1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3];
1313        let mut rle = RleVec::new();
1314        rle.write_all(data_in.as_slice()).unwrap();
1315        assert_eq!(rle.runs_len(),3);
1316        assert_eq!(rle.len(),11);
1317
1318        rle.write(&data_in[6..]).unwrap();
1319        assert_eq!(rle.runs_len(),5);
1320        assert_eq!(rle.len(),16);
1321
1322        rle.write(&[3,3,3]).unwrap();
1323        assert_eq!(rle.runs_len(),5);
1324        assert_eq!(rle.len(),19);
1325    }
1326}
rle_vec/lib.rs

rle_vec/
lib.rs
