Struct prefix_sum::PrefixSum

pub struct PrefixSum<T: Summable> { /* private fields */ }

Data type allowing O(1) interval modifications to an array.

Example

use prefix_sum::PrefixSum;

let mut sum = PrefixSum::new(6);
sum[2..=4] += 2;
sum[1..3] += 3;

sum[ ..3] -= 1;
sum[4.. ] += 10;

assert_eq!(vec![-1, 2, 4, 2, 12, 10], sum.build());

Implementations

impl<T: Summable> PrefixSum<T>

pub fn new(len: usize) -> PrefixSum<T>

Builds a new PrefixSum filled with zeroes.

This runs in linear time in the length.

pub fn from_vec(vec: Vec<T>) -> PrefixSum<T>

Returns a PrefixSum, such that calling build on the result would return the input.

This allocates if vec.len() == vec.capacity(). This runs in linear time in the length.

Examples

use prefix_sum::PrefixSum;

let sum = PrefixSum::from_vec(vec![1, 2, 3, 4]);
assert_eq!(sum.build(), vec![1, 2, 3, 4]);

When resized, new items will be zero.

use prefix_sum::PrefixSum;

let mut sum = PrefixSum::from_vec(vec![1, 2, 3, 4]);
sum.resize(5);
assert_eq!(sum.build(), vec![1, 2, 3, 4, 0]);

pub fn len(&self) -> usize

Returns the number of items in this prefix sum.

This runs in constant time.

pub fn resize(&mut self, len: usize)

Resize the prefix sum. Any changes done using intervals with no upper bound will affect the newly created values.

If the size is decreased, this is constant time. If the size is increased, this runs in amortized linear time in the number of items added.

Example

use prefix_sum::PrefixSum;

let mut sum = PrefixSum::new(3);
sum[ ..] += 2;
sum[1..] += 3;

sum[2] += 1;
assert_eq!(vec![2, 5, 6], sum.clone().build());

sum.resize(4);

assert_eq!(vec![2, 5, 6, 5], sum.build());

pub fn build(self) -> Vec<T>where
    T: Debug,

Build the vector containing the computed sums. This is linear time in the length.

pub fn iter(&self) -> Iter<'_, T> where
    T: Clone,

Create an iterator through the sums in this PrefixSum.

Trait Implementations

impl<T: Clone + Summable> Clone for PrefixSum<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug + Summable> Debug for PrefixSum<T>

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

Formats the value using the given formatter.

impl<T: Hash + Summable> Hash for PrefixSum<T>

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

Feeds this value into the given Hasher.

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

Feeds a slice of this type into the given Hasher.

impl<T: Summable> Index<Range<usize>> for PrefixSum<T>

type Output = PrefixSumRange<T>

The returned type after indexing.

fn index(&self, i: Range<usize>) -> &PrefixSumRange<T>

Performs the indexing (container[index]) operation.

impl<T: Summable> Index<RangeFrom<usize>> for PrefixSum<T>

type Output = UnboundedPrefixSumRange<T>

The returned type after indexing.

fn index(&self, i: RangeFrom<usize>) -> &UnboundedPrefixSumRange<T>

Performs the indexing (container[index]) operation.

impl<T: Summable> Index<RangeFull> for PrefixSum<T>

type Output = UnboundedPrefixSumRange<T>

The returned type after indexing.

fn index(&self, _i: RangeFull) -> &UnboundedPrefixSumRange<T>

Performs the indexing (container[index]) operation.

impl<T: Summable> Index<RangeInclusive<usize>> for PrefixSum<T>

type Output = PrefixSumRange<T>

The returned type after indexing.

fn index(&self, i: RangeInclusive<usize>) -> &PrefixSumRange<T>

Performs the indexing (container[index]) operation.

impl<T: Summable> Index<RangeTo<usize>> for PrefixSum<T>

type Output = PrefixSumRange<T>

The returned type after indexing.

fn index(&self, i: RangeTo<usize>) -> &PrefixSumRange<T>

Performs the indexing (container[index]) operation.

impl<T: Summable> Index<RangeToInclusive<usize>> for PrefixSum<T>

type Output = PrefixSumRange<T>

The returned type after indexing.

fn index(&self, i: RangeToInclusive<usize>) -> &PrefixSumRange<T>

Performs the indexing (container[index]) operation.

impl<T: Summable> Index<usize> for PrefixSum<T>

type Output = PrefixSumRange<T>

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<T: Summable> IndexMut<Range<usize>> for PrefixSum<T>

fn index_mut(&mut self, i: Range<usize>) -> &mut PrefixSumRange<T>

Performs the mutable indexing (container[index]) operation.

impl<T: Summable> IndexMut<RangeFrom<usize>> for PrefixSum<T>

fn index_mut(&mut self, i: RangeFrom<usize>) -> &mut UnboundedPrefixSumRange<T>

Performs the mutable indexing (container[index]) operation.

impl<T: Summable> IndexMut<RangeFull> for PrefixSum<T>

fn index_mut(&mut self, _i: RangeFull) -> &mut UnboundedPrefixSumRange<T>

Performs the mutable indexing (container[index]) operation.

impl<T: Summable> IndexMut<RangeInclusive<usize>> for PrefixSum<T>

fn index_mut(&mut self, i: RangeInclusive<usize>) -> &mut PrefixSumRange<T>

Performs the mutable indexing (container[index]) operation.

impl<T: Summable> IndexMut<RangeTo<usize>> for PrefixSum<T>

fn index_mut(&mut self, i: RangeTo<usize>) -> &mut PrefixSumRange<T>

Performs the mutable indexing (container[index]) operation.

impl<T: Summable> IndexMut<RangeToInclusive<usize>> for PrefixSum<T>

fn index_mut(&mut self, i: RangeToInclusive<usize>) -> &mut PrefixSumRange<T>

Performs the mutable indexing (container[index]) operation.

impl<T: Summable> IndexMut<usize> for PrefixSum<T>

fn index_mut(&mut self, i: usize) -> &mut PrefixSumRange<T>

Performs the mutable indexing (container[index]) operation.

impl<'a, T: Summable + Clone> IntoIterator for &'a PrefixSum<T>

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

type Item = T

The type of the elements being iterated over.

fn into_iter(self) -> Iter<'a, T>

Creates an iterator from a value.

impl<T: Summable> IntoIterator for PrefixSum<T>

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

type Item = T

The type of the elements being iterated over.

fn into_iter(self) -> IntoIter<T>

Creates an iterator from a value.

impl<T: PartialEq + Summable> PartialEq<PrefixSum<T>> for PrefixSum<T>

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

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq + Summable> Eq for PrefixSum<T>

impl<T: Summable> StructuralEq for PrefixSum<T>

impl<T: Summable> StructuralPartialEq for PrefixSum<T>