sdsl/interface/
int_vector.rs

1use crate::backend::sdsl_c;
2use crate::meta;
3use anyhow::{format_err, Result};
4
5use crate::interface::common::{self, Code, Id};
6
7/// A generic vector for integers of width $ [1..64] $ bits.
8///
9/// This generic vector class can be used to generate a vector that contains integers of fixed width $ [1..64] $.
10///
11/// # Arguments
12/// * `WIDTH` - Width of an integer. If set to `0` it is variable during runtime, otherwise fixed at compile time.
13///
14/// # Example
15/// ```ignore
16/// let mut iv = sdsl::int_vectors::IntVector::<0>::new(5, 42, Some(64))?;
17/// iv.bit_resize(2 * iv.width() as usize);
18///
19/// let result: Vec<_> = iv.iter().collect();
20/// let expected = vec![42, 42];
21/// assert_eq!(result, expected);
22/// ```
23///
24/// For further examples see [here](https://github.com/sdsl-rs/sdsl-rs/blob/master/examples/src/int_vectors/int_vector.rs).
25pub struct IntVector<const WIDTH: u8> {
26    ptr: common::VoidPtr,
27    interface: Interface,
28}
29
30impl<const WIDTH: u8> IntVector<WIDTH> {
31    /// Construct a new integer vector.
32    /// # Arguments
33    /// * `size` - Number of elements.
34    /// * `default_value` - Default values for elements initialization.
35    /// * `width` - The width of each integer. Must be specified if `WIDTH == 0`.
36    pub fn new(size: usize, default_value: usize, width: Option<u8>) -> Result<Self> {
37        assert!(
38            (WIDTH == 0 && width.is_some()) || (WIDTH != 0 && width.is_none()),
39            "Width argument must be specified iff WIDTH const generic value is 0."
40        );
41        let width = match width {
42            Some(width) => width,
43            None => WIDTH,
44        };
45
46        let id = Self::id()?;
47        let interface = Interface::new(&id)?;
48        let ptr = (interface.create)(size, default_value, width);
49
50        Ok(Self { ptr, interface })
51    }
52
53    /// Load vector from file.
54    /// # Arguments
55    /// * `path` - File path.
56    pub fn from_file(path: &std::path::PathBuf) -> Result<Self> {
57        assert!(
58            WIDTH == 0,
59            "Generic const WIDTH must be zero when loading from file."
60        );
61        let int_vector = Self::new(1, 0, Some(64))?;
62
63        let path = path
64            .to_str()
65            .ok_or(format_err!("Failed to convert PathBuf into str."))?;
66        let path = std::ffi::CString::new(path)?;
67
68        (int_vector.interface.io.load_from_file)(int_vector.ptr, path.as_ptr());
69        Ok(int_vector)
70    }
71
72    /// Get the i-th element of the vector.
73    /// # Arguments
74    /// * `index` - An index in range $ [0, \mathrm{len}()) $.
75    pub fn get(&self, index: usize) -> usize {
76        (self.interface.get)(self.ptr, index)
77    }
78
79    /// Set the i-th element of the vector.
80    /// # Arguments
81    /// * `index` - An index in range $ [0, \mathrm{len}()) $.
82    /// * `value` - New element value.
83    pub fn set(&mut self, index: usize, value: usize) {
84        (self.interface.set)(self.ptr, index, value)
85    }
86
87    /// Returns true if the vector is empty, otherwise returns false.
88    pub fn is_empty(&self) -> bool {
89        (self.interface.is_empty)(self.ptr)
90    }
91
92    /// Resize the vector in terms of elements.
93    /// # Arguments
94    /// * `size` - Target number of elements.
95    pub fn resize(&mut self, size: usize) {
96        (self.interface.resize)(self.ptr, size)
97    }
98
99    /// Resize the total vector in terms of bits.
100    /// # Arguments
101    /// * `size` - The size to resize the vector in terms of bits.
102    pub fn bit_resize(&mut self, size: usize) {
103        (self.interface.bit_resize)(self.ptr, size)
104    }
105
106    /// The number of elements in the vector.
107    pub fn len(&self) -> usize {
108        (self.interface.len)(self.ptr)
109    }
110
111    /// Maximum size of the vector.
112    pub fn max_size(&self) -> usize {
113        (self.interface.max_size)(self.ptr)
114    }
115
116    /// The number of bits in the vector.
117    pub fn bit_size(&self) -> usize {
118        (self.interface.bit_size)(self.ptr)
119    }
120
121    /// Returns the size of the occupied bits of the vector.
122    ///
123    /// The capacity of a vector is greater or equal to the
124    /// `bit_size()`.
125    pub fn capacity(&self) -> usize {
126        (self.interface.capacity)(self.ptr)
127    }
128
129    /// Constant pointer to the raw data of the vector.
130    pub fn data(&self) -> common::VoidPtr {
131        // TODO: Tie pointer lifetime to self.
132        (self.interface.data)(self.ptr)
133    }
134
135    /// Returns the width of the integers which are accessed via the `get(...)` method.
136    pub fn width(&self) -> u8 {
137        (self.interface.width)(self.ptr)
138    }
139
140    /// Sets the width of the integers which are accessed via the `get(...)` method, if `WIDTH` equals 0.
141    ///
142    /// This function does not bit resize each element in the vector.
143    /// Rather, after using this function, the raw data of the vector will be interpreted differently.
144    /// # Arguments
145    /// * `width` - New width of the integers.
146    pub fn set_width(&mut self, width: usize) -> Result<()> {
147        if WIDTH != 0 {
148            Err(format_err!(
149                "WIDTH is non-zero. Width is therefore immutable."
150            ))
151        } else {
152            Ok((self.interface.set_width)(self.ptr, width))
153        }
154    }
155
156    /// Returns an iterator over the vector values.
157    pub fn iter(&self) -> common::VectorIterator<usize, Self> {
158        common::VectorIterator::new(&self, self.len())
159    }
160}
161
162impl<const WIDTH: u8> common::util::Util for IntVector<WIDTH> {
163    fn util(&self) -> &common::util::Interface {
164        &self.interface.util
165    }
166}
167
168impl<const WIDTH: u8> common::io::IO for IntVector<WIDTH> {
169    fn io(&self) -> &common::io::Interface {
170        &self.interface.io
171    }
172}
173
174impl<const WIDTH: u8> common::Ptr for IntVector<WIDTH> {
175    fn ptr(&self) -> &common::VoidPtr {
176        &self.ptr
177    }
178}
179
180impl<'a, const WIDTH: u8> common::Id for IntVector<WIDTH> {
181    fn id() -> Result<String> {
182        let meta = Box::new(meta::int_vector::IntVectorMeta::new()) as Box<dyn meta::common::Meta>;
183        let parameters_c_code = Self::parameters_c_code()?;
184        let id = sdsl_c::specification::get_id(&meta.c_code(&parameters_c_code)?)?;
185        Ok(id)
186    }
187}
188
189impl<'a, const WIDTH: u8> common::Code for IntVector<WIDTH> {
190    fn c_code() -> Result<String> {
191        let meta = Box::new(meta::int_vector::IntVectorMeta::new()) as Box<dyn meta::common::Meta>;
192        let parameters_c_code = Self::parameters_c_code()?;
193        Ok(meta.c_code(&parameters_c_code)?)
194    }
195
196    fn parameters_c_code() -> Result<Vec<String>> {
197        Ok(vec![WIDTH.to_string()])
198    }
199}
200
201impl<const WIDTH: u8> common::IterGet<usize> for IntVector<WIDTH> {
202    fn iter_get(&self, index: usize) -> usize {
203        (self.interface.get)(self.ptr, index)
204    }
205}
206
207impl<const WIDTH: u8> Drop for IntVector<WIDTH> {
208    fn drop(&mut self) {
209        (self.interface.drop)(self.ptr)
210    }
211}
212
213impl<const WIDTH: u8> Clone for IntVector<WIDTH> {
214    fn clone(&self) -> Self {
215        Self {
216            ptr: (self.interface.clone)(self.ptr),
217            interface: self.interface.clone(),
218        }
219    }
220}
221
222impl<const WIDTH: u8> std::fmt::Debug for IntVector<WIDTH> {
223    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
224        f.debug_list().entries(self.iter()).finish()
225    }
226}
227
228impl<const WIDTH: u8> IntoIterator for IntVector<WIDTH> {
229    type Item = usize;
230    type IntoIter = common::VectorIntoIterator<usize, IntVector<WIDTH>>;
231
232    fn into_iter(self) -> Self::IntoIter {
233        let len = self.len();
234        common::VectorIntoIterator::new(self, len)
235    }
236}
237
238#[derive(Clone)]
239struct Interface {
240    create: extern "C" fn(usize, usize, u8) -> common::VoidPtr,
241    drop: extern "C" fn(common::VoidPtr),
242    clone: extern "C" fn(common::VoidPtr) -> common::VoidPtr,
243    is_empty: extern "C" fn(common::VoidPtr) -> bool,
244
245    resize: extern "C" fn(common::VoidPtr, usize),
246    bit_resize: extern "C" fn(common::VoidPtr, usize),
247    len: extern "C" fn(common::VoidPtr) -> usize,
248    max_size: extern "C" fn(common::VoidPtr) -> usize,
249    bit_size: extern "C" fn(common::VoidPtr) -> usize,
250    capacity: extern "C" fn(common::VoidPtr) -> usize,
251
252    data: extern "C" fn(common::VoidPtr) -> common::VoidPtr,
253    width: extern "C" fn(common::VoidPtr) -> u8,
254    set_width: extern "C" fn(common::VoidPtr, usize),
255
256    get: extern "C" fn(common::VoidPtr, usize) -> usize,
257    set: extern "C" fn(common::VoidPtr, usize, usize),
258
259    pub io: common::io::Interface,
260    util: common::util::Interface,
261    _lib: std::sync::Arc<sharedlib::Lib>,
262}
263
264impl Interface {
265    pub fn new(id: &str) -> Result<Self> {
266        let lib = sdsl_c::LIB.clone();
267        let builder = sdsl_c::FunctionBuilder::new(Some("int_vector"), id, lib.clone());
268
269        Ok(Self {
270            create: builder.get("create")?,
271            drop: builder.get("destroy")?,
272            clone: builder.get("copy")?,
273            is_empty: builder.get("empty")?,
274
275            resize: builder.get("resize")?,
276            bit_resize: builder.get("bit_resize")?,
277            len: builder.get("size")?,
278            max_size: builder.get("max_size")?,
279            bit_size: builder.get("bit_size")?,
280            capacity: builder.get("capacity")?,
281
282            get: builder.get("get_element")?,
283            set: builder.get("set_element")?,
284
285            data: builder.get("data")?,
286            width: builder.get("width")?,
287            set_width: builder.get("set_width")?,
288
289            io: common::io::Interface::new(&id)?,
290            util: common::util::Interface::new(&id)?,
291            _lib: lib.clone(),
292        })
293    }
294}
295
296/// Create a **IntVector** from a list of elements.
297///
298/// Elements at construction have 64 bit widths.
299///
300/// # Example
301/// ```ignore
302/// let mut iv = sdsl::int_vector! {1, 12, 3};
303/// sdsl::util::bit_compress(&mut iv);
304/// let result = iv.width();
305/// let expected = 4;
306/// assert_eq!(result, expected);
307/// ```
308#[macro_export(local_inner_macros)]
309macro_rules! int_vector {
310    (@single $($x:tt)*) => (());
311    (@count $($rest:expr),*) => (<[()]>::len(&[$(int_vector!(@single $rest)),*]));
312
313    ($($key:expr,)+) => { int_vector!($($key),+) };
314    ($($key:expr),*) => {
315        {
316            let _size = int_vector!(@count $($key),*);
317            let mut _vec = sdsl::int_vectors::IntVector::<0>::new(_size, 0, Some(64))?;
318            let mut i = 0;
319            $(
320                _vec.set(i, $key);
321                i += 1;
322            )*
323            _vec
324        }
325    };
326}
sdsl/interface/int_vector.rs

sdsl/interface/
int_vector.rs
