fcsd/
intvec.rs

1use crate::utils;
2use byteorder::{LittleEndian, ReadBytesExt, WriteBytesExt};
3use std::io;
4
5#[derive(Clone)]
6pub struct IntVector {
7    chunks: Vec<u64>,
8    len: usize,
9    bits: usize,
10    mask: u64,
11}
12
13impl IntVector {
14    pub fn build(input: &[u64]) -> Self {
15        let len = input.len();
16        let bits = utils::needed_bits(*input.iter().max().unwrap());
17        let mask = (1 << bits) - 1;
18
19        let mut chunks = vec![0; Self::words_for(len * bits)];
20
21        for (i, &x) in input.iter().enumerate() {
22            let (q, m) = Self::decompose(i * bits);
23            chunks[q] &= !(mask << m);
24            chunks[q] |= (x & mask) << m;
25            if 64 < m + bits {
26                let diff = 64 - m;
27                chunks[q + 1] &= !(mask >> diff);
28                chunks[q + 1] |= (x & mask) >> diff;
29            }
30        }
31
32        Self {
33            chunks,
34            len,
35            bits,
36            mask,
37        }
38    }
39
40    #[inline(always)]
41    pub fn get(&self, i: usize) -> u64 {
42        let (q, m) = Self::decompose(i * self.bits);
43        if m + self.bits <= 64 {
44            (self.chunks[q] >> m) & self.mask
45        } else {
46            ((self.chunks[q] >> m) | (self.chunks[q + 1] << (64 - m))) & self.mask
47        }
48    }
49
50    #[inline(always)]
51    pub const fn len(&self) -> usize {
52        self.len
53    }
54
55    pub fn size_in_bytes(&self) -> usize {
56        8 + self.chunks.len() * 8 + 8 * 3
57    }
58
59    pub fn serialize_into<W: io::Write>(&self, mut writer: W) -> io::Result<()> {
60        writer.write_u64::<LittleEndian>(self.chunks.len() as u64)?;
61        for &x in &self.chunks {
62            writer.write_u64::<LittleEndian>(x)?;
63        }
64        writer.write_u64::<LittleEndian>(self.len as u64)?;
65        writer.write_u64::<LittleEndian>(self.bits as u64)?;
66        writer.write_u64::<LittleEndian>(self.mask as u64)?;
67        Ok(())
68    }
69
70    pub fn deserialize_from<R: io::Read>(mut reader: R) -> io::Result<Self> {
71        let chunks = {
72            let len = reader.read_u64::<LittleEndian>()? as usize;
73            let mut chunks = vec![0; len];
74            for x in chunks.iter_mut() {
75                *x = reader.read_u64::<LittleEndian>()?;
76            }
77            chunks
78        };
79        let len = reader.read_u64::<LittleEndian>()? as usize;
80        let bits = reader.read_u64::<LittleEndian>()? as usize;
81        let mask = reader.read_u64::<LittleEndian>()?;
82        Ok(Self {
83            chunks,
84            len,
85            bits,
86            mask,
87        })
88    }
89
90    #[inline(always)]
91    const fn words_for(bits: usize) -> usize {
92        (bits + 63) / 64
93    }
94
95    #[inline(always)]
96    const fn decompose(x: usize) -> (usize, usize) {
97        (x / 64, x % 64)
98    }
99}
fcsd/intvec.rs

fcsd/
intvec.rs
