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
127
128
129
130
131
132
133
134
135
136
137
138

use crate::octet::Octet;
use std::cmp::Ordering;
use std::mem::size_of;

#[derive(Clone, Debug, PartialEq, PartialOrd, Eq, Ord, Hash)]
pub struct SparseBinaryVec {
    // Kept sorted by the usize (key). Only ones are stored, zeros are implicit
    elements: Vec<u16>,
}

impl SparseBinaryVec {
    pub fn with_capacity(capacity: usize) -> SparseBinaryVec {
        // Matrix width can never exceed maximum L
        debug_assert!(capacity < 65536);
        SparseBinaryVec {
            elements: Vec::with_capacity(capacity),
        }
    }

    // Returns the internal index into self.elements matching key i, or the index
    // at which it can be inserted (maintaining sorted order)
    fn key_to_internal_index(&self, i: u16) -> Result<usize, usize> {
        self.elements.binary_search(&i)
    }

    pub fn size_in_bytes(&self) -> usize {
        size_of::<Self>() + size_of::<u16>() * self.elements.len()
    }

    pub fn len(&self) -> usize {
        self.elements.len()
    }

    pub fn get_by_raw_index(&self, i: usize) -> (usize, Octet) {
        (self.elements[i] as usize, Octet::one())
    }

    // Returns true, if a new column was added
    pub fn add_assign(&mut self, other: &SparseBinaryVec) -> bool {
        // Fast path for a single value that's being eliminated
        if other.elements.len() == 1 {
            let other_index = &other.elements[0];
            match self.key_to_internal_index(*other_index) {
                Ok(index) => {
                    // Adding 1 + 1 = 0 in GF(256), so remove this
                    self.elements.remove(index);
                }
                Err(index) => {
                    self.elements.insert(index, *other_index);
                    return true;
                }
            };
            return false;
        }

        let mut result = Vec::with_capacity(self.elements.len() + other.elements.len());
        let mut self_iter = self.elements.iter();
        let mut other_iter = other.elements.iter();
        let mut self_next = self_iter.next();
        let mut other_next = other_iter.next();

        let mut column_added = false;
        loop {
            if let Some(self_index) = self_next {
                if let Some(other_index) = other_next {
                    match self_index.cmp(&other_index) {
                        Ordering::Less => {
                            result.push(*self_index);
                            self_next = self_iter.next();
                        }
                        Ordering::Equal => {
                            // Adding 1 + 1 = 0 in GF(256), so skip this index
                            self_next = self_iter.next();
                            other_next = other_iter.next();
                        }
                        Ordering::Greater => {
                            column_added = true;
                            result.push(*other_index);
                            other_next = other_iter.next();
                        }
                    }
                } else {
                    result.push(*self_index);
                    self_next = self_iter.next();
                }
            } else if let Some(other_index) = other_next {
                column_added = true;
                result.push(*other_index);
                other_next = other_iter.next();
            } else {
                break;
            }
        }
        self.elements = result;

        return column_added;
    }

    pub fn remove(&mut self, i: usize) -> Option<Octet> {
        match self.key_to_internal_index(i as u16) {
            Ok(index) => {
                self.elements.remove(index);
                Some(Octet::one())
            }
            Err(_) => None,
        }
    }

    pub fn retain<P: Fn(&(usize, Octet)) -> bool>(&mut self, predicate: P) {
        self.elements
            .retain(|entry| predicate(&(*entry as usize, Octet::one())));
    }

    pub fn get(&self, i: usize) -> Option<Octet> {
        match self.key_to_internal_index(i as u16) {
            Ok(_) => Some(Octet::one()),
            Err(_) => None,
        }
    }

    pub fn keys_values(&self) -> impl Iterator<Item = (usize, Octet)> + '_ {
        self.elements
            .iter()
            .map(|entry| (*entry as usize, Octet::one()))
    }

    pub fn insert(&mut self, i: usize, value: Octet) {
        debug_assert!(i < 65536);
        if value == Octet::zero() {
            self.remove(i);
        } else {
            match self.key_to_internal_index(i as u16) {
                Ok(_) => {}
                Err(index) => self.elements.insert(index, i as u16),
            }
        }
    }
}