succinct 0.5.2

Succinct data structures for 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

use std::mem;

use super::*;
use internal::errors::*;
use stream::*;

/// A Fibonacci code.
pub struct Fibonacci;

struct Fib {
    i_1: u64,
    i: u64,
}

impl Fib {
    fn new() -> Self {
        Fib {
            i_1: 1,
            i: 1,
        }
    }

    fn next(&mut self) -> Result<()> {
        if let Some(next) = self.i_1.checked_add(self.i) {
            self.i_1 = self.i;
            self.i = next;
            Ok(())
        } else {
            too_many_bits("Fibonacci")
        }
    }

    fn prev(&mut self) {
        self.i -= self.i_1;
        mem::swap(&mut self.i, &mut self.i_1);
    }
}

impl UniversalCode for Fibonacci {
    fn encode<W: BitWrite>(&self, sink: &mut W, mut value: u64) -> Result<()> {
        assert!(value != 0, "Fibonacci codes cannot handle 0.");
        let mut fib = Fib::new();

        // Having to compute fib.i when we really just need fib.i_1
        // means that this gives up on smaller numbers than it needs to.
        while fib.i <= value {
            try!(fib.next());
        }

        // Now fib.i_1 is the largest Fibonacci number <= value

        let mut stack = vec![true];
        while fib.i > 1 {
            if fib.i_1 <= value {
                value -= fib.i_1;
                stack.push(true);
            } else {
                stack.push(false);
            }

            fib.prev();
        }

        while let Some(bit) = stack.pop() {
            try!(sink.write_bit(bit));
        }

        Ok(())
    }

    fn decode<R: BitRead>(&self, source: &mut R) -> Result<Option<u64>> {
        let mut result  = 0;
        let mut fib = Fib::new();
        let mut previous = false;

        while let Some(bit) = try!(source.read_bit()) {
            if bit && previous {
                return Ok(Some(result));
            }

            if bit {
                result += fib.i;
            }

            try!(fib.next());
            previous = bit;
        }

        if result == 0 {
            Ok(None)
        } else {
            out_of_bits("Fibonacci::decode")
        }
    }
}

#[cfg(test)]
mod test {
    use std::collections::VecDeque;
    use quickcheck::quickcheck;
    use coding::*;
    use coding::properties;

    #[test]
    fn enc234() {
        let mut dv = VecDeque::<bool>::new();

        Fibonacci.encode(&mut dv, 2).unwrap();
        Fibonacci.encode(&mut dv, 3).unwrap();
        Fibonacci.encode(&mut dv, 4).unwrap();

        assert_eq!(Some(2), Fibonacci.decode(&mut dv).unwrap());
        assert_eq!(Some(3), Fibonacci.decode(&mut dv).unwrap());
        assert_eq!(Some(4), Fibonacci.decode(&mut dv).unwrap());
        assert_eq!(None::<u64>, Fibonacci.decode(&mut dv).unwrap());
    }

    #[test]
    fn qc() {
        fn prop(v: Vec<u64>) -> bool {
            properties::code_decode(&Fibonacci, v)
        }

        quickcheck(prop as fn(Vec<u64>) -> bool);
    }
}