elias_fano_rust/
builders.rs

1use super::*;
2
3impl EliasFano {
4
5    #[inline]
6    pub fn new(universe: u64, number_of_elements: usize) -> Result<EliasFano, String> {
7        if number_of_elements == 0 {
8            return Ok(EliasFano{
9                universe: universe,
10                low_bit_count: 0,
11                low_bit_mask:  0,
12                number_of_elements: 0,
13                high_bits: SimpleSelect::new(),
14                low_bits: vec![],
15                last_high_value: 0,
16                last_value: 0,
17                last_index: 0,
18                current_number_of_elements: 0,
19            });
20        }
21        // Compute the size of the low bits.
22        let low_bit_count = if universe >= number_of_elements as u64 {
23            (universe as f64 / number_of_elements as f64).log2().floor() as u64
24        } else {
25            0
26        };
27
28        // saturate at the max we can handle
29        if low_bit_count > 64 {
30            return Err(format!(concat!(
31                    "The lowbits are too big, we only support 64 bits for the low parts.",
32                    "The value were universe {} number_of_elements {}"
33                ),
34                universe, number_of_elements
35            ));
36        }
37
38        // add 2 to do the ceil and have brenchless primitives.
39        let low_size = get_vec_size(low_bit_count, number_of_elements);
40
41        Ok(EliasFano {
42            universe,
43            low_bit_count,
44            // Pre-rendered mask to execute a fast version of the mod operation.
45            low_bit_mask: shr(0xffffffffffffffff, 64 - low_bit_count),
46            high_bits: SimpleSelect::with_capacity(2 * number_of_elements),
47            number_of_elements: number_of_elements as u64,
48            low_bits: vec![0; low_size as usize],
49            last_high_value: 0,
50            last_value: 0,
51            last_index: 0,
52            current_number_of_elements: 0,
53        })
54    }
55
56    /// Create a new elias-fano from an iterable of **sorted values**.
57    ///    low_bits: Vec<u64>,
58
59    /// # Arguments
60    ///
61    /// * values: &[u64] - Vector of sorted integers to encode.
62    /// * max: u64 - The maximum value within the vector.
63    /// ```
64    /// # use elias_fano_rust::EliasFano;
65    /// let vector = [5, 8, 8, 15, 32];
66    /// let ef = EliasFano::from_iter(vector.iter().cloned(), *vector.last().unwrap(), vector.len()).unwrap();
67    /// ```
68    #[inline]
69    pub fn from_iter(
70        values: impl Iterator<Item = u64>,
71        universe: u64,
72        number_of_elements: usize,
73    ) -> Result<EliasFano, String> {
74        let mut result = EliasFano::new(universe, number_of_elements)?;
75
76        result.build_low_high_bits(values)?;
77
78        Ok(result)
79    }
80
81    /// Create a new elias-fano from a vector of **sorted values**.
82    ///
83    /// # Arguments
84    ///
85    /// * values: &[u64] - Vector of sorted integers to encode.
86    /// * max: u64 - The maximum value within the vector.
87    ///
88    /// ```
89    /// # use elias_fano_rust::EliasFano;
90    /// let vector = [5, 8, 8, 15, 32];
91    /// let ef = EliasFano::from_vec(&vector).unwrap();
92    /// ```
93    #[inline]
94    pub fn from_vec(values: &[u64]) -> Result<EliasFano, String> {
95        EliasFano::from_iter(
96            values.iter().cloned(),
97            *values.last().unwrap_or(&0),
98            values.len(),
99        )
100    }
101
102    #[inline]
103    pub fn unchecked_push(&mut self, value: u64) {
104        self.last_value = value;
105        self.current_number_of_elements += 1;
106
107        // split into high and low bits
108        let (high, low) = self.extract_high_low_bits(value);
109
110        // The following for loop and push
111        // are used to encode in inverted unary code for the high bits
112        // of the data structure.
113        for _ in self.last_high_value..high {
114            self.high_bits.push(false);
115        }
116        self.high_bits.push(true);
117
118        #[cfg(not(feature = "unsafe"))]
119        safe_write(&mut self.low_bits, self.last_index, low, self.low_bit_count);
120        #[cfg(feature = "unsafe")]
121        unsafe_write(&mut self.low_bits, self.last_index, low, self.low_bit_count);
122
123        self.last_high_value = high;
124        self.last_index += 1;
125    }
126
127    #[inline]
128    pub fn push(&mut self, value: u64) -> Result<(), String> {
129        if self.last_value > value {
130            return Err(format!(
131                concat!(
132                    "Cannot initialize from an unsorted set of values! ",
133                    "Previous value was {} but given value is {}.",
134                ),
135                self.last_value, value
136            ));
137        }
138        if self.current_number_of_elements >= self.number_of_elements {
139            return Err(format!(
140                concat!(
141                    "Cannot push anymore values inside of the Elias-Fano ",
142                    "because it already reached the maximum number of elements ",
143                    "that was passed during the initialization {}."
144                ),
145                self.number_of_elements
146            ));
147        }
148        self.unchecked_push(value);
149        Ok(())
150    }
151}
elias_fano_rust/builders.rs

elias_fano_rust/
builders.rs
