Struct rle_vec::RleVec

pub struct RleVec<T> { /* fields omitted */ }

The RleVec struct handles like a normal vector and supports a subset from the Vec methods.

Not all methods implemented on Vec are implemented for RleVec. All methods returning a slice cannot work for RleVec.

Examples:

let mut rle = RleVec::new();

rle.push(10);
rle.push(10);
rle.push(11);

assert_eq!(rle[1], 10);
assert_eq!(rle[2], 11);

rle.insert(1, 10);
assert_eq!(rle.runs_len(), 2);

rle.set(0, 1);
assert_eq!(rle.runs_len(), 3);

RleVec can be constructed from Iterators and be iterated over just like a Vec.

let v = vec![0,0,0,1,1,1,1,2,2,3,4,5,4,4,4];

let mut rle: RleVec<_> = v.into_iter().collect();

assert_eq!(rle.len(), 15);
assert_eq!(rle.runs_len(), 7);

assert_eq!(rle.iter().nth(10), Some(&4));

An RleVec can be indexed like a regular vector, but not mutated. Use RleVec::set to change the value at an index.

let v = vec![0,0,0,1,1,1,1,2,2,3];
let mut rle: RleVec<_> = v.into_iter().collect();

rle.set(1,2);
rle.insert(4,4);

assert_eq!(rle.iter().cloned().collect::<Vec<_>>(), vec![0,2,0,1,4,1,1,1,2,2,3]);

RleVec::set and RleVec::insert require T: Clone.

Indexing

The RleVec type allows to access values by index, because it implements the Index trait. An example will be more explicit:

let v = vec![0, 2, 4, 6];
let rle: RleVec<_> = v.into_iter().collect();

println!("{}", rle[1]); // it will display '2'

However be careful: if you try to access an index which isn't in the RleVec, your software will panic! You cannot do this:

let v = vec![0, 2, 4, 6];
let rle: RleVec<_> = v.into_iter().collect();

println!("{}", v[6]); // it will panic!

In conclusion: always check if the index you want to get really exists before doing it.

Capacity and reallocation

The capacity of an RleVec is the amount of space allocated for any future runs that will be required for the RleVec. This is not to be confused with the length, which specifies the number of actual elements that can be indexed from the RleVec. If a a run needs to be added to the RleVec and the number of runs exceeds its capacity, its capacity will automatically be increased, but its runs will have to be reallocated.

For example, an RleVec with capacity 10 and length 0 would be an empty vector with space for 10 more runs. Pushing 10 or fewer consecutively different elements onto the vector will not change its capacity or cause reallocation to occur. However, if the RleVec's length is increased to 11, it will have to reallocate, which can be slow. For this reason, if you can predict the number of runs required in your RleVec, it is recommended to use RleVec::with_capacity whenever possible to specify how many runs the RleVec is expected to store.

Methods

impl<T> RleVec<T>

Important traits for RleVec<u8>

impl Write for RleVec<u8>

pub fn new() -> RleVec<T>

Constructs a new empty RleVec<T>.

The rle_vector will not allocate until elements are pushed onto it.

Examples

let rle = RleVec::<i32>::new();

Important traits for RleVec<u8>

impl Write for RleVec<u8>

pub fn with_capacity(capacity: usize) -> RleVec<T>

Constructs a new empty RleVec<T> with capacity for the number of runs.

Choosing this value requires knowledge about the composition of the data that is going to be inserted.

Example

let mut rle = RleVec::with_capacity(10);

// The rle_vector contains no items, even though it has capacity for more
assert_eq!(rle.len(), 0);

// These are all done without reallocating...
for i in 0..10 {
   rle.push(i);
}

// The rle_vector contains 10 runs and 10 elements too...
assert_eq!(rle.len(), 10);
assert_eq!(rle.runs_len(), 10);

// this definitely won't reallocate the runs
rle.push(10);
// while this may make the rle_vector reallocate
rle.push(11);

pub fn len(&self) -> usize

Returns the number of elements in the rle_vector.

Example

let mut rle = RleVec::new();
rle.push(1);
rle.push(1);
rle.push(2);

assert_eq!(rle.len(), 3);

pub fn is_empty(&self) -> bool

Returns true if the rle_vector contains no elements.

Example

let mut rle = RleVec::new();
assert!(rle.is_empty());

rle.push(1);
assert!(!rle.is_empty());

pub fn clear(&mut self)

Clears the vector, removing all values.

Note that this method has no effect on the allocated capacity of the vector.

Examples

let mut rle = RleVec::from(&[1, 1, 1, 1, 2, 2, 3][..]);

rle.clear();
assert!(rle.is_empty());

pub fn last(&self) -> Option<&T>

Returns the last value, or None if it is empty.

Example

let rle = RleVec::from(&[10, 10, 40, 40, 30][..]);
assert_eq!(rle.last(), Some(&30));

let rle = RleVec::<i32>::new();
assert_eq!(rle.last(), None);

pub fn last_run(&self) -> Option<Run<&T>>

Returns the last run, or None if it is empty.

Example

let mut rle = RleVec::new();

assert_eq!(rle.last_run(), None);

rle.push(1);
rle.push(1);
rle.push(1);
rle.push(1);

assert_eq!(rle.last_run(), Some(Run{ len: 4, value: &1 }));

rle.push(2);
rle.push(2);
rle.push(3);

assert_eq!(rle.last_run(), Some(Run{ len: 1, value: &3 }));

pub fn runs_len(&self) -> usize

Returns the number of runs

Example

let mut rle = RleVec::new();
assert_eq!(rle.runs_len(), 0);

rle.push(1);
rle.push(1);
assert_eq!(rle.runs_len(), 1);

rle.push(2);
rle.push(3);
assert_eq!(rle.runs_len(), 3);

pub fn starts(&self) -> Vec<usize>

Returns the 0-based start coordinates of the runs

Example

let mut rle = RleVec::new();
rle.push(1);
rle.push(1);
rle.push(2);
rle.push(2);
rle.push(3);

let starts = rle.starts();
assert_eq!(starts, vec![0, 2, 4]);

pub fn ends(&self) -> Vec<usize>

Returns the 0-based end coordinates of the runs

Important traits for Iter<'a, T>

impl<'a, T: 'a> Iterator for Iter<'a, T> type Item = &'a T;

pub fn iter(&self) -> Iter<T>

Returns an iterator over values. Comparable to a Vec iterator.

Example

let mut rle = RleVec::new();
rle.push(1);
rle.push(1);
rle.push(2);
rle.push(3);

let mut iterator = rle.iter();

assert_eq!(iterator.next(), Some(&1));
assert_eq!(iterator.next(), Some(&1));
assert_eq!(iterator.next(), Some(&2));
assert_eq!(iterator.next(), Some(&3));
assert_eq!(iterator.next(), None);

Important traits for Runs<'a, T>

impl<'a, T: 'a> Iterator for Runs<'a, T> type Item = Run<&'a T>;

pub fn runs(&self) -> Runs<T>

Returns an iterator that can be used to iterate over the runs.

Example

let mut rle = RleVec::new();
rle.push(1);
rle.push(1);
rle.push(2);
rle.push(3);

let mut iterator = rle.runs();

assert_eq!(iterator.next(), Some(Run{ len: 2, value: &1 }));
assert_eq!(iterator.next(), Some(Run{ len: 1, value: &2 }));
assert_eq!(iterator.next(), Some(Run{ len: 1, value: &3 }));
assert_eq!(iterator.next(), None);

impl<T: Eq> RleVec<T>

pub fn push(&mut self, value: T)

Appends an element to the back of this rle_vector.

Panics

Panics if the number of elements in the vector overflows a usize.

Example

let mut rle = RleVec::new();
rle.push(1);
assert_eq!(rle[0], 1);

pub fn push_n(&mut self, n: usize, value: T)

Appends the same element n times to the back of this rle_vec.

Panics

Panics if the number of elements in the vector overflows a usize.

Example

let mut rle = RleVec::new();

// Push 10 times a 2
rle.push_n(10, 2);
assert_eq!(rle[9], 2);

impl<T: Clone> RleVec<T>

pub fn to_vec(&self) -> Vec<T>

Construct a Vec<T> from this RleVec.

The values of the RleVec are cloned to produce the final Vec. This can be usefull for debugging.

Example

let slice = &[0, 0, 0, 1, 1, 99, 9];
let rle = RleVec::from(&slice[..]);
let vec = rle.to_vec();

assert_eq!(vec.as_slice(), slice);

impl<T: Eq + Clone> RleVec<T>

pub fn set(&mut self, index: usize, value: T)

Modify the value at given index.

This can result in the breaking of a run and therefore be an expensive operation. If the value is equal to the value currently present the complexity is O(log n). But if the run needs to be broken the complexity increases to a worst case of O((log n) + n).

Example

let mut rle = RleVec::from(&[1, 1, 1, 1, 2, 2, 3][..]);

assert_eq!(rle[2], 1);
assert_eq!(rle.len(), 7);
assert_eq!(rle.runs_len(), 3);

rle.set(2, 3);
assert_eq!(rle[2], 3);
assert_eq!(rle.len(), 7);
assert_eq!(rle.runs_len(), 5);

pub fn remove(&mut self, index: usize) -> T

Removes and returns the element at position index, shifting all elements after it to the left.

Panics

Panics if index is out of bounds.

Examples

let mut rle = RleVec::from(&[1, 1, 1, 1, 2, 1, 1, 4, 4][..]);

assert_eq!(rle.remove(4), 2);
assert_eq!(rle.runs_len(), 2);
assert_eq!(rle.to_vec(), vec![1, 1, 1, 1, 1, 1, 4, 4]);

pub fn insert(&mut self, index: usize, value: T)

Insert a value at the given index.

Because the positions of the values after the inserted value need to be changed, the complexity of this function is O((log n) + 2n).

Example

let mut rle = RleVec::from(&[1, 1, 1, 1, 2, 2, 3][..]);

assert_eq!(rle[2], 1);
assert_eq!(rle.runs_len(), 3);

rle.insert(2, 3);
assert_eq!(rle[2], 3);
assert_eq!(rle.runs_len(), 5);

Trait Implementations

impl<T: Debug> Debug for RleVec<T>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T: Clone> Clone for RleVec<T>

Important traits for RleVec<u8>

impl Write for RleVec<u8>

fn clone(&self) -> RleVec<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Eq> Eq for RleVec<T>

impl<T: PartialEq> PartialEq for RleVec<T>

fn eq(&self, other: &RleVec<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &RleVec<T>) -> bool

This method tests for !=.

impl<T: Ord> Ord for RleVec<T>

fn cmp(&self, other: &RleVec<T>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

impl<T: PartialOrd> PartialOrd for RleVec<T>

fn partial_cmp(&self, other: &RleVec<T>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &RleVec<T>) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &RleVec<T>) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &RleVec<T>) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &RleVec<T>) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T: Hash> Hash for RleVec<T>

fn hash<__HT: Hasher>(&self, state: &mut __HT)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where     H: Hasher,

Feeds a slice of this type into the given [Hasher].

impl<T> Index<usize> for RleVec<T>

type Output = T

The returned type after indexing.

fn index(&self, index: usize) -> &T

Performs the indexing (container[index]) operation.

impl<T: Clone> Into<Vec<T>> for RleVec<T>

fn into(self) -> Vec<T>

Performs the conversion.

impl<'a, T: Eq + Clone> From<&'a [T]> for RleVec<T>

fn from(slice: &'a [T]) -> Self

Performs the conversion.

impl<T: Eq> FromIterator<T> for RleVec<T>

fn from_iter<I>(iter: I) -> Self where     I: IntoIterator<Item = T>,

Creates a value from an iterator.

impl<T: Eq> FromIterator<Run<T>> for RleVec<T>

fn from_iter<I>(iter: I) -> Self where     I: IntoIterator<Item = Run<T>>,

Creates a value from an iterator.

impl<T> Default for RleVec<T>

fn default() -> Self

Returns the "default value" for a type.

impl<T: Eq> Extend<T> for RleVec<T>

fn extend<I>(&mut self, iter: I) where     I: IntoIterator<Item = T>,

Extends a collection with the contents of an iterator.

impl<T: Eq> Extend<Run<T>> for RleVec<T>

fn extend<I>(&mut self, iter: I) where     I: IntoIterator<Item = Run<T>>,

Extends a collection with the contents of an iterator.

impl Write for RleVec<u8>

fn write(&mut self, buf: &[u8]) -> Result<usize>

Write a buffer into this object, returning how many bytes were written.

fn write_all(&mut self, buf: &[u8]) -> Result<()>

Attempts to write an entire buffer into this write.

fn flush(&mut self) -> Result<()>

Flush this output stream, ensuring that all intermediately buffered contents reach their destination.

fn write_fmt(&mut self, fmt: Arguments) -> Result<(), Error>

Writes a formatted string into this writer, returning any error encountered.

fn by_ref(&mut self) -> &mut Self

Creates a "by reference" adaptor for this instance of Write.

impl<'a, T: 'a> IntoIterator for &'a RleVec<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.