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.

Implementations

impl<T> RleVec<T>

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();

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

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);

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: Clone> Clone for RleVec<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

impl<T> Default for RleVec<T>

fn default() -> Self

Returns the "default value" for a type.

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

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.

pub fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

pub fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

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.

pub fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

pub fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

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

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

Performs the conversion.

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: 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: Hash> Hash for RleVec<T>

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

Feeds this value into the given Hasher.

pub 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, Global>> for RleVec<T>

fn into(self) -> Vec<T>

Performs the conversion.

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.

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

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

This method returns an Ordering between self and other.

#[must_use]pub fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use]pub fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use]pub fn clamp(self, min: Self, max: Self) -> Self

Restrict a value to a certain interval.

impl<T: PartialEq> PartialEq<RleVec<T>> 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: PartialOrd> PartialOrd<RleVec<T>> 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.

#[must_use]pub fn lt(&self, other: &Rhs) -> bool

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

#[must_use]pub fn le(&self, other: &Rhs) -> bool

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

#[must_use]pub fn gt(&self, other: &Rhs) -> bool

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

#[must_use]pub fn ge(&self, other: &Rhs) -> bool

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

impl<T> StructuralEq for RleVec<T>

impl<T> StructuralPartialEq for RleVec<T>

impl Write for RleVec<u8>

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

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

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

Attempts to write an entire buffer into this writer.

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

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

pub fn write_vectored(&mut self, bufs: &[IoSlice<'_>]) -> Result<usize, Error>

Like write, except that it writes from a slice of buffers.

pub fn is_write_vectored(&self) -> bool

🔬 This is a nightly-only experimental API. (can_vector)

Determines if this Writer has an efficient write_vectored implementation.

pub fn write_all_vectored(
    &mut self,
    bufs: &mut [IoSlice<'_>]
) -> Result<(), Error>

🔬 This is a nightly-only experimental API. (write_all_vectored)

Attempts to write multiple buffers into this writer.

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

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

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

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