treez 0.7.0

A collection of useful tree data structures.
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

use std::mem;

pub struct TreePrefix {
    _buf: Vec<isize>,
}

impl TreePrefix {
    pub fn init( num: usize ) -> TreePrefix {
        TreePrefix {
            _buf: vec![ 0isize; num + 1]
        }
    }
    pub fn add( & mut self, index: usize, val: isize ){
        assert!( index < self._buf.len() );
        let mut i = index;
        while i < self._buf.len() {
            self._buf[i] += val;
            i += self.lsb(i+1);
        }
    }
    pub fn set( & mut self, index: usize, val: isize ){
        assert!( index < self._buf.len() );
        let v = self.get( index );
        self.add( index, val - v );
    }
    pub fn get( & self, index: usize ) -> isize {
        assert!( index < self._buf.len() );
        self.get_interval( index, index + 1 )
    }
    pub fn get_interval( & self, index: usize, index_end: usize ) -> isize {
        assert!( index < self._buf.len() );
        assert!( index_end < self._buf.len() );

        let mut s = 0isize;
        let mut i = index_end;
        let mut j = index;
        if j > i {
            mem::swap( & mut i, & mut j );
        }
        while i > j {
            // println!("i:{}", i );
            s += self._buf[i-1];
            i -= self.lsb(i);
        }
        while j > i {
            // println!("j:{}", j );
            s -= self._buf[j-1];
            j -= self.lsb(j);
        }
        s
    }
    pub fn get_interval_start( & self, index: usize ) -> isize {
        let mut i = index;
        let mut s = 0isize;
        while i > 0 {
            s += self._buf[i-1];
            i -= self.lsb(i);
        }
        s
    }
    pub fn get_len( & mut self ) -> usize {
        self._buf.len() - 1
    }
    fn lsb( & self, v: usize ) -> usize {
        let a = !v + 1;
        let b = a & v;
        // println!( "v: {:0>8b}, a: {:0>8b}, b:{:0>8b}", v, a, b );
        b
    }
}