fenwick-tree 0.1.0

An implementation of a binary indexed tree (Fenwick tree) data structure in Rust.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

use std::error::Error;
use std::fmt::{Display, Formatter, Result as FmtResult};
use std::ops::Bound;

/// An error in calculating a partial sum.
#[derive(Debug, PartialEq, Eq)]
pub enum SumError {
    // Range is not within the range of the tree.
    OutOfRange {
        bounds: (Bound<usize>, Bound<usize>),
        len: usize,
    },
}

/// An error in adding a delta to a tree element.
#[derive(Debug, PartialEq, Eq)]
pub enum AddError {
    /// Index is greater than the size of the tree.
    IndexOutOfRange { index: usize, size: usize },
}

impl Display for SumError {
    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
        match *self {
            SumError::OutOfRange { bounds, len } => {
                write!(f, "Bounds {:#?} are not in range (0..{})", bounds, len)
            }
        }
    }
}

impl Display for AddError {
    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
        match *self {
            AddError::IndexOutOfRange { index, size } => {
                write!(f, "Index `{}` is greater than the size `{}`", index, size)
            }
        }
    }
}

impl Error for SumError {
    fn source(&self) -> Option<&(dyn Error + 'static)> {
        None
    }
}

impl Error for AddError {
    fn source(&self) -> Option<&(dyn Error + 'static)> {
        None
    }
}