elias_fano/
lib.rs

1extern crate fixedbitset;
2
3mod utils;
4
5use utils::*;
6
7use fixedbitset::FixedBitSet;
8use std::error::Error;
9use std::fmt;
10
11#[derive(Debug)]
12pub struct EliasFano {
13    universe: u64,
14    n: u64,
15    lower_bits: u64,
16    higher_bits_length: u64,
17    mask: u64,
18    lower_bits_offset: u64,
19    bv_len: u64,
20    b: FixedBitSet,
21    cur_value: u64,
22    position: u64,
23    high_bits_pos: u64,
24}
25
26#[derive(Debug)]
27pub struct OutOfBoundsError;
28
29impl Error for OutOfBoundsError {
30    fn description(&self) -> &str {
31        "Index out of bounds"
32    }
33}
34
35impl fmt::Display for OutOfBoundsError {
36    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
37        write!(f, "Index out of range attempted to be accessed")
38    }
39}
40
41impl EliasFano {
42    pub fn new(universe: u64, n: u64) -> EliasFano {
43        let lower_bits = if universe > n { msb(universe / n) } else { 0 };
44        let higher_bits_length = n + (universe >> lower_bits) + 2;
45        let mask = (1_u64 << lower_bits) - 1;
46        let lower_bits_offset = higher_bits_length;
47        let bv_len = lower_bits_offset + n * (lower_bits as u64);
48        let b = FixedBitSet::with_capacity(bv_len as usize);
49
50        EliasFano {
51            universe,
52            n,
53            lower_bits,
54            higher_bits_length,
55            mask,
56            lower_bits_offset,
57            bv_len,
58            b,
59            cur_value: 0,
60            position: 0,
61            high_bits_pos: 0,
62        }
63    }
64
65    pub fn compress<'a, I>(&mut self, elems: I)
66    where
67        I: Iterator<Item = &'a u64>,
68    {
69        let mut last = 0_u64;
70
71        for (i, elem) in elems.enumerate() {
72            if i > 0 && *elem < last {
73                panic!("Sequence is not sorted");
74            }
75
76            if *elem > self.universe {
77                panic!("Element {} is greater than universe", elem);
78            }
79
80            let high = (elem >> self.lower_bits) + i as u64 + 1;
81            let low = elem & self.mask;
82
83            self.b.set(high as usize, true);
84
85            let offset = self.lower_bits_offset + (i as u64 * self.lower_bits);
86            set_bits(&mut self.b, offset, low, self.lower_bits);
87
88            last = *elem;
89
90            if i == 0 {
91                self.cur_value = *elem;
92                self.high_bits_pos = high;
93            }
94        }
95    }
96
97    pub fn visit(&mut self, position: u64) -> Result<u64, OutOfBoundsError> {
98        if position > self.size() {
99            return Err(OutOfBoundsError);
100        }
101
102        if self.position == position {
103            return Ok(self.value());
104        }
105
106        if position < self.position {
107            self.reset();
108        }
109
110        let skip = position - self.position;
111        let pos = (0..skip).fold(self.high_bits_pos, |pos, _| {
112            get_next_set(&self.b, (pos + 1) as usize)
113        });
114
115        self.high_bits_pos = (pos - 1) as u64;
116        self.position = position;
117        self.read_current_value();
118        Ok(self.value())
119    }
120
121    pub fn next(&mut self) -> Result<u64, OutOfBoundsError> {
122        self.position += 1;
123
124        if self.position >= self.size() {
125            return Err(OutOfBoundsError);
126        }
127
128        self.read_current_value();
129        Ok(self.value())
130    }
131
132    pub fn skip(&mut self, n: u64) -> Result<u64, OutOfBoundsError> {
133        let new_pos = self.position() + n;
134        self.visit(new_pos)
135    }
136
137    pub fn reset(&mut self) {
138        self.high_bits_pos = 0;
139        self.position = 0;
140        self.read_current_value();
141    }
142
143    pub fn position(&self) -> u64 {
144        self.position
145    }
146
147    pub fn value(&self) -> u64 {
148        self.cur_value
149    }
150
151    pub fn bit_size(&self) -> usize {
152        self.b.len()
153    }
154
155    pub fn size(&self) -> u64 {
156        self.n
157    }
158
159    fn read_current_value(&mut self) {
160        let pos = if self.high_bits_pos > 0 {
161            self.high_bits_pos + 1
162        } else {
163            self.high_bits_pos
164        };
165
166        self.high_bits_pos = get_next_set(&self.b, pos as usize) as u64;
167
168        let mut low = 0;
169        let offset = self.lower_bits_offset + self.position * self.lower_bits;
170
171        for i in 0..self.lower_bits {
172            if self.b.contains((offset + i + 1) as usize) {
173                low += 1;
174            }
175            low <<= 1;
176        }
177        low >>= 1;
178
179        self.cur_value =
180            (((self.high_bits_pos - self.position - 1) << self.lower_bits) | low) as u64;
181    }
182}
183
184impl fmt::Display for EliasFano {
185    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
186        write!(
187            f,
188            "
189    Universe: {:?}
190    Elements: {:?}
191    Lower_bits: {:?}
192    Higher_bits_length: {:?}
193    Mask: 0b{:?}
194    Lower_bits_offset: {:?}
195    Bitvector length: {:?}
196",
197            self.universe,
198            self.n,
199            self.lower_bits,
200            self.higher_bits_length,
201            self.mask,
202            self.lower_bits_offset,
203            self.bv_len,
204        )
205    }
206}
elias_fano/lib.rs

elias_fano/
lib.rs
