microsoft/qdk
Publicmirrored from https://github.com/microsoft/qdkAvailable
source/paulimer/src/bits/index_set.rs
240lines · modecode
| 1 | // Copyright (c) Microsoft Corporation. |
| 2 | // Licensed under the MIT License. |
| 3 | |
| 4 | use super::{BitVec, BitwiseNeutralElement, BorrowAsBitIterator, FromBits, OverlapWeight}; |
| 5 | use crate::bits::{are_supports_equal, Bitwise, BitwiseBinaryOps, Dot, IndexAssignable}; |
| 6 | use crate::NeutralElement; |
| 7 | use sorted_iter::{assume::AssumeSortedByItemExt, SortedIterator}; |
| 8 | use sorted_vec::SortedSet; |
| 9 | |
| 10 | #[must_use] |
| 11 | #[derive(PartialEq, Eq, Clone, Debug, Hash)] |
| 12 | pub struct IndexSet { |
| 13 | indexes: SortedSet<usize>, |
| 14 | } |
| 15 | |
| 16 | impl IndexSet { |
| 17 | pub fn new() -> IndexSet { |
| 18 | IndexSet { |
| 19 | indexes: SortedSet::new(), |
| 20 | } |
| 21 | } |
| 22 | |
| 23 | pub fn singleton(value: usize) -> Self { |
| 24 | IndexSet { |
| 25 | indexes: unsafe { SortedSet::from_sorted(vec![value]) }, |
| 26 | } |
| 27 | } |
| 28 | } |
| 29 | |
| 30 | impl Default for IndexSet { |
| 31 | fn default() -> Self { |
| 32 | Self::new() |
| 33 | } |
| 34 | } |
| 35 | |
| 36 | impl FromIterator<usize> for IndexSet { |
| 37 | fn from_iter<Iterator: IntoIterator<Item = usize>>(iterator: Iterator) -> Self { |
| 38 | let indexes = SortedSet::from_unsorted(iterator.into_iter().collect()); |
| 39 | IndexSet { indexes } |
| 40 | } |
| 41 | } |
| 42 | |
| 43 | impl IntoIterator for IndexSet { |
| 44 | type Item = usize; |
| 45 | type IntoIter = std::vec::IntoIter<Self::Item>; |
| 46 | |
| 47 | fn into_iter(self) -> Self::IntoIter { |
| 48 | self.indexes.into_vec().into_iter() |
| 49 | } |
| 50 | } |
| 51 | |
| 52 | impl Bitwise for IndexSet { |
| 53 | fn index(&self, index: usize) -> bool { |
| 54 | self.indexes.contains(&index) |
| 55 | } |
| 56 | |
| 57 | fn weight(&self) -> usize { |
| 58 | self.indexes.len() |
| 59 | } |
| 60 | |
| 61 | fn support(&self) -> impl SortedIterator<Item = usize> { |
| 62 | self.indexes.iter().copied().assume_sorted_by_item() |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | impl<Bits: Bitwise> BitwiseBinaryOps<Bits> for IndexSet { |
| 67 | fn assign(&mut self, other: &Bits) { |
| 68 | let indexes: Vec<usize> = other.support().collect(); |
| 69 | self.indexes = indexes.into(); |
| 70 | } |
| 71 | |
| 72 | fn bitxor_assign(&mut self, other: &Bits) { |
| 73 | for index in other.support() { |
| 74 | let found = self.indexes.find_or_insert(index); |
| 75 | if found.is_found() { |
| 76 | self.indexes.remove_index(found.index()); |
| 77 | } |
| 78 | } |
| 79 | } |
| 80 | |
| 81 | fn bitand_assign(&mut self, other: &Bits) { |
| 82 | let self_support = self.indexes.iter().copied().assume_sorted_by_item(); |
| 83 | let other_support = other.support(); |
| 84 | let indexes: Vec<usize> = self_support.intersection(other_support).collect(); |
| 85 | self.indexes = indexes.into(); |
| 86 | } |
| 87 | } |
| 88 | |
| 89 | impl IndexAssignable for IndexSet { |
| 90 | fn assign_index(&mut self, index: usize, to: bool) { |
| 91 | if to { |
| 92 | self.indexes.push(index); |
| 93 | } else { |
| 94 | self.indexes.remove_item(&index); |
| 95 | } |
| 96 | } |
| 97 | |
| 98 | fn negate_index(&mut self, index: usize) { |
| 99 | if self.indexes.contains(&index) { |
| 100 | self.indexes.remove_item(&index); |
| 101 | } else { |
| 102 | self.indexes.push(index); |
| 103 | } |
| 104 | } |
| 105 | |
| 106 | fn clear_bits(&mut self) { |
| 107 | self.indexes.clear(); |
| 108 | } |
| 109 | } |
| 110 | |
| 111 | impl<Bits: Bitwise> Dot<Bits> for IndexSet { |
| 112 | fn dot(&self, other: &Bits) -> bool { |
| 113 | debug_assert!(is_sorted(self.support())); |
| 114 | debug_assert!(is_sorted(other.support())); |
| 115 | let mut res = false; |
| 116 | for index in self.support() { |
| 117 | res ^= other.index(index); |
| 118 | } |
| 119 | res |
| 120 | } |
| 121 | } |
| 122 | |
| 123 | impl<T: IndexAssignable + BorrowAsBitIterator> Dot<IndexSet> for T { |
| 124 | fn dot(&self, other: &IndexSet) -> bool { |
| 125 | other.dot(self) |
| 126 | } |
| 127 | } |
| 128 | |
| 129 | impl<Bits: Bitwise> OverlapWeight<Bits> for IndexSet { |
| 130 | fn and_weight(&self, other: &Bits) -> usize { |
| 131 | let mut res = 0usize; |
| 132 | for index in self.support() { |
| 133 | if other.index(index) { |
| 134 | res += 1; |
| 135 | } |
| 136 | } |
| 137 | res |
| 138 | } |
| 139 | |
| 140 | fn or_weight(&self, other: &Bits) -> usize { |
| 141 | self.weight() + other.weight() - self.and_weight(other) |
| 142 | } |
| 143 | } |
| 144 | |
| 145 | impl<T: IndexAssignable + BorrowAsBitIterator> OverlapWeight<IndexSet> for T { |
| 146 | fn and_weight(&self, other: &IndexSet) -> usize { |
| 147 | other.and_weight(self) |
| 148 | } |
| 149 | |
| 150 | fn or_weight(&self, other: &IndexSet) -> usize { |
| 151 | other.or_weight(self) |
| 152 | } |
| 153 | } |
| 154 | |
| 155 | fn is_sorted<Items: Iterator<Item = usize>>(items: Items) -> bool { |
| 156 | items.into_iter().is_sorted() |
| 157 | } |
| 158 | |
| 159 | impl<T: IndexAssignable + BorrowAsBitIterator> BitwiseBinaryOps<IndexSet> for T { |
| 160 | #[allow(clippy::explicit_iter_loop)] |
| 161 | fn assign(&mut self, other: &IndexSet) { |
| 162 | self.clear_bits(); |
| 163 | for index in other.indexes.iter() { |
| 164 | self.assign_index(*index, true); |
| 165 | } |
| 166 | } |
| 167 | |
| 168 | fn bitxor_assign(&mut self, other: &IndexSet) { |
| 169 | for index in other.support() { |
| 170 | self.negate_index(index); |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | fn bitand_assign(&mut self, other: &IndexSet) { |
| 175 | let intersection: Vec<usize> = self.support().intersection(other.support()).collect(); |
| 176 | self.clear_bits(); |
| 177 | for k in intersection { |
| 178 | self.assign_index(k, true); |
| 179 | } |
| 180 | } |
| 181 | } |
| 182 | |
| 183 | impl<T: IndexAssignable + BorrowAsBitIterator> PartialEq<T> for IndexSet { |
| 184 | fn eq(&self, other: &T) -> bool { |
| 185 | are_supports_equal(self, other) |
| 186 | } |
| 187 | } |
| 188 | |
| 189 | impl<Other: Bitwise> FromBits<Other> for IndexSet { |
| 190 | fn from_bits(other: &Other) -> Self { |
| 191 | IndexSet { |
| 192 | indexes: other.support().collect::<Vec<usize>>().into(), |
| 193 | } |
| 194 | } |
| 195 | } |
| 196 | |
| 197 | impl NeutralElement for IndexSet { |
| 198 | type NeutralElementType = IndexSet; |
| 199 | |
| 200 | fn neutral_element(&self) -> Self::NeutralElementType { |
| 201 | IndexSet::new() |
| 202 | } |
| 203 | |
| 204 | fn default_size_neutral_element() -> Self::NeutralElementType { |
| 205 | IndexSet::new() |
| 206 | } |
| 207 | |
| 208 | fn neutral_element_of_size(_size: usize) -> Self::NeutralElementType { |
| 209 | IndexSet::new() |
| 210 | } |
| 211 | } |
| 212 | |
| 213 | impl BitwiseNeutralElement for IndexSet {} |
| 214 | |
| 215 | impl<'life, const WORD_COUNT: usize> From<&'life BitVec<WORD_COUNT>> for IndexSet { |
| 216 | fn from(value: &'life BitVec<WORD_COUNT>) -> Self { |
| 217 | unsafe { |
| 218 | IndexSet { |
| 219 | indexes: SortedSet::from_sorted(value.support().collect::<Vec<_>>()), |
| 220 | } |
| 221 | } |
| 222 | } |
| 223 | } |
| 224 | |
| 225 | pub fn remapped(bits: &IndexSet, support: &[usize]) -> IndexSet { |
| 226 | bits.support().map(|id| support[id]).collect() |
| 227 | } |
| 228 | |
| 229 | impl<T> From<T> for IndexSet |
| 230 | where |
| 231 | T: SortedIterator<Item = usize>, |
| 232 | { |
| 233 | fn from(value: T) -> Self { |
| 234 | unsafe { |
| 235 | IndexSet { |
| 236 | indexes: SortedSet::from_sorted(value.collect::<Vec<_>>()), |
| 237 | } |
| 238 | } |
| 239 | } |
| 240 | } |
| 241 | |