GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored from https://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
4fa10c30a716d7fc2f67a0a385f3da565daa1237

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/source/paulimer/src/bits

source/paulimer/src/bits/bitmatrix.rs

1139lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4use super::bitvec::WORD_COUNT_DEFAULT;
5use super::{BitwiseNeutralElement, OverlapWeight};
6use crate::bits::bitblock::{BitAccessor, BitBlock};
7use crate::bits::{
8 BitVec, BitView, Bitwise, BitwiseBinaryOps, Dot, IndexAssignable, MutableBitView,
9};
10use crate::NeutralElement;
11use sorted_iter::assume::AssumeSortedByItemExt;
12use sorted_iter::SortedIterator;
13use std::cmp::PartialEq;
14use std::hash::Hash;
15use std::iter::FromIterator;
16use std::mem::size_of;
17use std::ops::{Add, AddAssign, BitAnd, BitAndAssign, BitXor, BitXorAssign, Mul};
18use std::ops::{Index, Range};
19use std::str::FromStr;
20
21#[must_use]
22#[derive(Debug, Eq)]
23pub struct BitMatrix<const WORD_COUNT: usize = WORD_COUNT_DEFAULT> {
24 blocks: Vec<BitBlock<WORD_COUNT>>,
25 rows: Vec<*mut BitBlock<WORD_COUNT>>,
26 columncount: usize,
27}
28
29impl<const WORD_COUNT: usize> Hash for BitMatrix<WORD_COUNT> {
30 fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
31 self.blocks.hash(state);
32 }
33}
34
35unsafe impl Sync for BitMatrix {}
36
37pub type Row<'life, const WORD_COUNT: usize = WORD_COUNT_DEFAULT> = BitView<'life, WORD_COUNT>; // should we use View in the name to indicate that it is a view and not a copy of a row ?
38pub type MutableRow<'life, const WORD_COUNT: usize = WORD_COUNT_DEFAULT> =
39 MutableBitView<'life, WORD_COUNT>; // should we use View in the name to indicate that it is a view and not a copy of a row ?
40
41#[derive(Clone, Debug, Hash)]
42pub struct Column<'life, const WORD_COUNT: usize = WORD_COUNT_DEFAULT> {
43 // TODO(VK) should we use View in the name to indicate that it is a view and not a copy of a column ?
44 rows: &'life [*mut BitBlock<WORD_COUNT>],
45 accessor: BitAccessor<WORD_COUNT>,
46 block_index: usize,
47}
48
49impl<const WORD_COUNT: usize> BitMatrix<WORD_COUNT> {
50 pub fn with_shape(rows: usize, columns: usize) -> Self {
51 Self::zeros(rows, columns)
52 }
53
54 pub fn zeros(rows: usize, columns: usize) -> Self {
55 Self::with_value(false, (rows, columns))
56 }
57
58 pub fn ones(rows: usize, columns: usize) -> Self {
59 Self::with_value(true, (rows, columns))
60 }
61
62 pub fn identity(dimension: usize) -> Self {
63 let mut res = Self::zeros(dimension, dimension);
64 for index in 0..dimension {
65 res.set((index, index), true);
66 }
67 res
68 }
69
70 pub fn from_row_iter<'life>(
71 iter: impl ExactSizeIterator<Item = BitView<'life, WORD_COUNT>>,
72 columns: usize,
73 ) -> Self {
74 let rows = iter.len();
75 let mut matrix = Self::zeros(rows, columns);
76 for (row_from, mut row_to) in std::iter::zip(iter, matrix.row_iterator_mut(0..rows)) {
77 row_to.assign(&row_from);
78 }
79 matrix
80 }
81
82 pub fn from_iter<Row, Rows>(iter: Rows, columncount: usize) -> Self
83 where
84 Row: IntoIterator<Item = bool>,
85 Rows: IntoIterator<Item = Row>,
86 {
87 // TODO(AEP): Expanding first into Vec<bool> is
88 // inefficient. Instead, append to Vec<BitBlock::<WORD_COUNT_DEFAULT>> as necessary.
89 let mut rows = Vec::<Vec<bool>>::new();
90 let mut rowcount = 0;
91 for row in iter {
92 rows.push(row.into_iter().collect());
93 rowcount += 1;
94 }
95 let mut matrix = BitMatrix::with_shape(rowcount, columncount);
96 for (row_index, row) in rows.iter().enumerate() {
97 for (column_index, value) in row.iter().take(columncount).enumerate() {
98 matrix.set((row_index, column_index), *value);
99 }
100 }
101 matrix
102 }
103
104 fn with_value(value: bool, shape: (usize, usize)) -> Self {
105 let (rowcount, columncount) = shape;
106 let rowstride = Self::rowstride_of(columncount);
107 let buffer = vec![BitBlock::<WORD_COUNT>::all(value); rowcount * rowstride];
108 Self::from_blocks(buffer, shape)
109 }
110
111 fn from_blocks(mut buffer: Vec<BitBlock<WORD_COUNT>>, shape: (usize, usize)) -> Self {
112 let rows = Self::rows_of(buffer.as_mut_slice(), shape.0);
113 Self::from_blocks_and_rows(buffer, shape, rows)
114 }
115
116 fn from_blocks_and_rows(
117 buffer: Vec<BitBlock<WORD_COUNT>>,
118 shape: (usize, usize),
119 rows: Vec<*mut BitBlock<WORD_COUNT>>,
120 ) -> Self {
121 let matrix = Self {
122 blocks: buffer,
123 rows,
124 columncount: shape.1,
125 };
126 debug_assert!(matrix.is_aligned());
127 matrix
128 }
129
130 #[must_use]
131 pub fn is_zero(&self) -> bool {
132 let zero = BitBlock::<WORD_COUNT>::zeros();
133 for block in &self.blocks {
134 if *block != zero {
135 return false;
136 }
137 }
138 true
139 }
140
141 fn is_aligned(&self) -> bool {
142 let alignment = (self.blocks.as_ptr() as usize) % size_of::<BitBlock<WORD_COUNT>>();
143 if alignment != 0 {
144 return false;
145 }
146 for row in &self.rows {
147 let alignment = (*row as usize) % size_of::<BitBlock<WORD_COUNT>>();
148 if alignment != 0 {
149 return false;
150 }
151 }
152 true
153 }
154
155 fn rowstride(&self) -> usize {
156 Self::rowstride_of(self.columncount)
157 }
158
159 fn rowstride_of(columncount: usize) -> usize {
160 let rowstride = columncount / BitBlock::<WORD_COUNT>::BITS;
161 let adjustment = !columncount.is_multiple_of(BitBlock::<WORD_COUNT>::BITS);
162 rowstride + usize::from(adjustment)
163 }
164
165 fn rows_of(
166 blocks: &mut [BitBlock<WORD_COUNT>],
167 rowcount: usize,
168 ) -> Vec<*mut BitBlock<WORD_COUNT>> {
169 let mut rows = Vec::<*mut BitBlock<WORD_COUNT>>::new();
170 let rowstride = if rowcount == 0 {
171 0
172 } else {
173 blocks.len() / rowcount
174 };
175 if rowstride == 0 {
176 rows = vec![blocks.as_mut_ptr(); rowcount];
177 } else {
178 for row in blocks.chunks_exact_mut(rowstride) {
179 rows.push(row.as_mut_ptr());
180 }
181 }
182 rows
183 }
184
185 #[must_use]
186 pub fn rowcount(&self) -> usize {
187 self.rows.len()
188 }
189
190 #[must_use]
191 pub fn columncount(&self) -> usize {
192 self.columncount
193 }
194
195 #[must_use]
196 pub fn shape(&self) -> (usize, usize) {
197 (self.rowcount(), self.columncount())
198 }
199
200 #[must_use]
201 pub fn row(&self, index: usize) -> Row<'_, WORD_COUNT> {
202 Row::<WORD_COUNT> {
203 blocks: unsafe {
204 std::slice::from_raw_parts((*self.rows[index]).array(), self.block_count())
205 },
206 }
207 }
208
209 #[must_use]
210 pub fn rows(&self) -> impl ExactSizeIterator<Item = Row<'_, WORD_COUNT>> {
211 self.row_iterator(0..self.rowcount())
212 }
213
214 pub fn row_iterator(
215 &self,
216 index_iterator: impl ExactSizeIterator<Item = usize>,
217 ) -> impl ExactSizeIterator<Item = Row<'_, WORD_COUNT>> {
218 index_iterator.map(|index| self.row(index))
219 }
220
221 pub fn row_iterator_mut(
222 &mut self,
223 index_iterator: impl ExactSizeIterator<Item = usize>,
224 ) -> impl ExactSizeIterator<Item = MutableRow<'_, WORD_COUNT>> {
225 index_iterator.map(|index| self.build_mutable_row(index))
226 }
227
228 pub fn row_mut(&mut self, index: usize) -> MutableRow<'_, WORD_COUNT> {
229 self.build_mutable_row(index)
230 }
231
232 #[inline]
233 fn block_count(&self) -> usize {
234 let mut block_count = self.columncount() / BitBlock::<WORD_COUNT_DEFAULT>::BITS;
235 if !self
236 .columncount()
237 .is_multiple_of(BitBlock::<WORD_COUNT_DEFAULT>::BITS)
238 {
239 block_count += 1;
240 }
241 block_count
242 }
243
244 fn build_mutable_row(&self, index: usize) -> MutableRow<'_, WORD_COUNT> {
245 let ptr = self.rows[index];
246 MutableRow::<WORD_COUNT> {
247 blocks: unsafe {
248 std::slice::from_raw_parts_mut((*ptr).array_mut(), self.block_count())
249 },
250 }
251 }
252
253 pub fn rows_mut(
254 &mut self,
255 index: usize,
256 index2: usize,
257 ) -> (MutableRow<'_, WORD_COUNT>, MutableRow<'_, WORD_COUNT>) {
258 (
259 self.build_mutable_row(index),
260 self.build_mutable_row(index2),
261 )
262 }
263
264 pub fn rows2_mut(
265 &mut self,
266 index: (usize, usize),
267 ) -> (MutableRow<'_, WORD_COUNT>, MutableRow<'_, WORD_COUNT>) {
268 (
269 self.build_mutable_row(index.0),
270 self.build_mutable_row(index.1),
271 )
272 }
273
274 #[must_use]
275 pub fn rows2(&self, index: (usize, usize)) -> (Row<'_, WORD_COUNT>, Row<'_, WORD_COUNT>) {
276 (self.row(index.0), self.row(index.1))
277 }
278
279 /// # Safety
280 /// Does not check if all indexes are distinct
281 pub unsafe fn rows4_mut(
282 &mut self,
283 index: (usize, usize, usize, usize),
284 ) -> (
285 MutableRow<'_, WORD_COUNT>,
286 MutableRow<'_, WORD_COUNT>,
287 MutableRow<'_, WORD_COUNT>,
288 MutableRow<'_, WORD_COUNT>,
289 ) {
290 (
291 self.build_mutable_row(index.0),
292 self.build_mutable_row(index.1),
293 self.build_mutable_row(index.2),
294 self.build_mutable_row(index.3),
295 )
296 }
297
298 /// TODO(VK): Maybe use <https://doc.rust-lang.org/std/primitive.slice.html#method.get_many_mut> when it becomes stable
299 /// # Safety
300 /// Does not check if all indexes are distinct
301 pub unsafe fn rows8_mut(
302 &mut self,
303 index: crate::Tuple8<usize>,
304 ) -> crate::Tuple8<MutableRow<'_, WORD_COUNT>> {
305 (
306 self.build_mutable_row(index.0),
307 self.build_mutable_row(index.1),
308 self.build_mutable_row(index.2),
309 self.build_mutable_row(index.3),
310 self.build_mutable_row(index.4),
311 self.build_mutable_row(index.5),
312 self.build_mutable_row(index.6),
313 self.build_mutable_row(index.7),
314 )
315 }
316
317 #[must_use]
318 pub fn column(&self, index: usize) -> Column<'_, WORD_COUNT> {
319 let block_index = index / BitBlock::<WORD_COUNT_DEFAULT>::BITS;
320 let bit_index = index % BitBlock::<WORD_COUNT_DEFAULT>::BITS;
321 Column::<WORD_COUNT> {
322 rows: &self.rows,
323 accessor: BitAccessor::for_index(bit_index),
324 block_index,
325 }
326 }
327
328 #[must_use]
329 pub fn columns(&self) -> impl ExactSizeIterator<Item = Column<'_, WORD_COUNT>> {
330 let indexes = 0..self.columncount();
331 indexes.map(|index| self.column(index))
332 }
333
334 /// # Panics
335 ///
336 /// Will panic if index out of range
337 pub fn set(&mut self, index: (usize, usize), to: bool) {
338 assert!(index.0 < self.rowcount() && index.1 < self.columncount());
339 unsafe { self.set_unchecked(index, to) };
340 }
341
342 /// # Safety
343 /// Dose not check if index is out of bounds
344 pub unsafe fn set_unchecked(&mut self, index: (usize, usize), to: bool) {
345 let (block, bit_index) = self.block_index_of_mut(index);
346 block.set(bit_index, to);
347 }
348
349 /// # Panics
350 ///
351 /// Will panic if index out of range
352 #[must_use]
353 pub fn get(&self, index: (usize, usize)) -> bool {
354 assert!(index.0 < self.rowcount() && index.1 < self.columncount());
355 unsafe { self.get_unchecked(index) }
356 }
357
358 /// # Safety
359 /// Does not check if index is out of bounds
360 #[must_use]
361 pub unsafe fn get_unchecked(&self, index: (usize, usize)) -> bool {
362 let (block, bit_index) = self.block_index_of(index);
363 block.get_unchecked(bit_index)
364 }
365
366 pub fn echelonize(&mut self) -> Vec<usize> {
367 let mut pivot = pivot_of(self, (0, 0));
368 let mut rank_profile = Vec::<usize>::with_capacity(self.columncount());
369
370 for row_index in 0..self.rowcount() {
371 if pivot.1 >= self.columncount() {
372 break;
373 }
374 self.swap_rows(pivot.0, row_index);
375 pivot.0 = row_index;
376 rank_profile.push(pivot.1);
377 reduce(self, pivot);
378 pivot = pivot_of(self, (pivot.0 + 1, pivot.1 + 1));
379 }
380 rank_profile
381 }
382
383 #[must_use]
384 pub fn rank(&self) -> usize {
385 self.clone().echelonize().len()
386 }
387
388 pub fn transposed(&self) -> Self {
389 let mut res = Self::with_shape(self.columncount(), self.rowcount());
390 for i in 0..self.rowcount() {
391 for j in 0..self.columncount() {
392 res.set((j, i), self[(i, j)]);
393 }
394 }
395 res
396 }
397
398 pub fn submatrix(&self, rows: &[usize], columns: &[usize]) -> Self {
399 let mut res = Self::with_shape(rows.len(), columns.len());
400 for (row_index, &row) in rows.iter().enumerate() {
401 for (column_index, &column) in columns.iter().enumerate() {
402 res.set((row_index, column_index), self[(row, column)]);
403 }
404 }
405 res
406 }
407
408 /// # Panics
409 ///
410 /// Will panic if matrix is not invertible
411 pub fn inverted(&self) -> BitMatrix<WORD_COUNT> {
412 assert!(self.columncount() == self.rowcount());
413 let (_, t, _, profile) = rref_with_transforms(self.clone());
414 assert!(profile.len() == self.rowcount());
415 debug_assert_eq!(
416 self * &t,
417 BitMatrix::<WORD_COUNT>::identity(self.rowcount())
418 );
419 t
420 }
421
422 pub fn swap_rows(&mut self, left_row_index: usize, right_row_index: usize) {
423 self.rows.swap(left_row_index, right_row_index);
424 }
425
426 pub fn swap_columns(&mut self, left_column_index: usize, right_column_index: usize) {
427 for row_index in 0..self.rowcount() {
428 let left_bit = self.get((row_index, left_column_index));
429 let right_bit = self.get((row_index, right_column_index));
430 self.set((row_index, left_column_index), right_bit);
431 self.set((row_index, right_column_index), left_bit);
432 }
433 }
434
435 pub fn permute_rows(&mut self, permutation: &[usize]) {
436 let old_rows = self.rows.clone();
437 for index in 0..permutation.len() {
438 self.rows[index] = old_rows[permutation[index]];
439 }
440 }
441
442 pub fn add_into_row(&mut self, to_index: usize, from_index: usize) {
443 let mut to_block = self.rows[to_index];
444 let mut from_block = self.rows[from_index];
445 for _ in 0..self.rowstride() {
446 unsafe {
447 BitwiseBinaryOps::bitxor_assign(&mut *to_block, &*from_block);
448 to_block = to_block.add(1);
449 from_block = from_block.add(1);
450 }
451 }
452 }
453
454 // TODO(VK): check if we also need dot_transposed
455 /// # Panics
456 ///
457 /// Will panic if matrix dimensions are incompatible
458 pub fn dot(&self, rhs: &BitMatrix<WORD_COUNT>) -> BitMatrix<WORD_COUNT> {
459 assert_eq!(self.columncount(), rhs.rowcount());
460 let mut rows = Vec::with_capacity(self.rowcount());
461 for output_row in 0..self.rowcount() {
462 let mut row = BitVec::<WORD_COUNT>::zeros(rhs.columncount());
463 for column_index in 0..self.columncount() {
464 if self[(output_row, column_index)] {
465 // TODO(AEP): This is needlessly slow. Make it fast.
466 for into_column_index in 0..rhs.columncount() {
467 row.assign_index(
468 into_column_index,
469 row.index(into_column_index)
470 ^ rhs.get((column_index, into_column_index)),
471 );
472 }
473 }
474 }
475 rows.push(row);
476 }
477 Self::from_iter(rows.iter(), rhs.columncount())
478 }
479
480 fn block_index_of_mut(&mut self, index: (usize, usize)) -> (&mut BitBlock<WORD_COUNT>, usize) {
481 let column_block = index.1 / BitBlock::<WORD_COUNT_DEFAULT>::BITS;
482 let column_remainder = index.1 % BitBlock::<WORD_COUNT_DEFAULT>::BITS;
483 let bit_index = column_remainder % BitBlock::<WORD_COUNT_DEFAULT>::BITS;
484 unsafe {
485 let block = self.rows[index.0].add(column_block);
486 (&mut *block, bit_index)
487 }
488 }
489
490 fn block_index_of(&self, index: (usize, usize)) -> (&BitBlock<WORD_COUNT>, usize) {
491 let column_block = index.1 / BitBlock::<WORD_COUNT_DEFAULT>::BITS;
492 let column_remainder = index.1 % BitBlock::<WORD_COUNT_DEFAULT>::BITS;
493 let bit_index = column_remainder % BitBlock::<WORD_COUNT_DEFAULT>::BITS;
494 unsafe {
495 let block = self.rows[index.0].add(column_block);
496 (&*block, bit_index)
497 }
498 }
499}
500
501unsafe impl<const WORD_COUNT: usize> Send for BitMatrix<WORD_COUNT> {}
502
503impl<const WORD_COUNT: usize> Clone for BitMatrix<WORD_COUNT> {
504 fn clone(&self) -> Self {
505 let mut blocks = self.blocks.clone();
506 let mut rows = Vec::<*mut BitBlock<WORD_COUNT>>::new();
507 let offset = unsafe { blocks.as_mut_ptr().offset_from(self.blocks.as_ptr()) };
508 for row in &self.rows {
509 rows.push(unsafe { row.offset(offset) });
510 }
511 BitMatrix::from_blocks_and_rows(blocks, self.shape(), rows)
512 }
513}
514
515impl<const WORD_COUNT: usize> Index<[usize; 2]> for BitMatrix<WORD_COUNT> {
516 type Output = bool;
517
518 fn index(&self, index: [usize; 2]) -> &Self::Output {
519 &self[(index[0], index[1])]
520 }
521}
522
523impl<const WORD_COUNT: usize> Index<(usize, usize)> for BitMatrix<WORD_COUNT> {
524 type Output = bool;
525
526 fn index(&self, index: (usize, usize)) -> &Self::Output {
527 if self.get(index) {
528 return &true;
529 }
530 &false
531 }
532}
533
534impl<const WORD_COUNT: usize> PartialEq for BitMatrix<WORD_COUNT> {
535 fn eq(&self, other: &Self) -> bool {
536 if self.shape() != other.shape() {
537 return false;
538 }
539 for irow in 0..self.rowcount() {
540 for icol in 0..self.columncount() {
541 if self[(irow, icol)] != other[(irow, icol)] {
542 return false;
543 }
544 }
545 }
546 true
547 }
548}
549
550impl<const WORD_COUNT: usize> AddAssign<&BitMatrix<WORD_COUNT>> for BitMatrix<WORD_COUNT> {
551 fn add_assign(&mut self, other: &BitMatrix<WORD_COUNT>) {
552 assert_eq!(self.shape(), other.shape());
553 for index in 0..self.rowcount() {
554 self.row_mut(index).bitxor_assign(&other.row(index));
555 }
556 }
557}
558
559impl<const WORD_COUNT: usize> Add for &BitMatrix<WORD_COUNT> {
560 type Output = BitMatrix<WORD_COUNT>;
561
562 fn add(self, other: Self) -> Self::Output {
563 let mut clone = (*self).clone();
564 clone += other;
565 clone
566 }
567}
568
569impl<const WORD_COUNT: usize> BitXor for &BitMatrix<WORD_COUNT> {
570 type Output = BitMatrix<WORD_COUNT>;
571
572 fn bitxor(self, other: Self) -> Self::Output {
573 self.add(other)
574 }
575}
576
577impl<const WORD_COUNT: usize> BitXorAssign<&BitMatrix<WORD_COUNT>> for BitMatrix<WORD_COUNT> {
578 fn bitxor_assign(&mut self, other: &BitMatrix<WORD_COUNT>) {
579 self.add_assign(other);
580 }
581}
582
583impl<const WORD_COUNT: usize> BitAndAssign<&BitMatrix<WORD_COUNT>> for BitMatrix<WORD_COUNT> {
584 fn bitand_assign(&mut self, other: &Self) {
585 assert_eq!(self.shape(), other.shape());
586 for index in 0..self.rowcount() {
587 self.row_mut(index).bitand_assign(&other.row(index));
588 }
589 }
590}
591
592impl<const WORD_COUNT: usize> BitAnd for &BitMatrix<WORD_COUNT> {
593 type Output = BitMatrix<WORD_COUNT>;
594
595 fn bitand(self, other: Self) -> Self::Output {
596 let mut clone = (*self).clone();
597 clone &= other;
598 clone
599 }
600}
601
602impl<const WORD_COUNT: usize> Mul for &BitMatrix<WORD_COUNT> {
603 type Output = BitMatrix<WORD_COUNT>;
604
605 fn mul(self, other: Self) -> Self::Output {
606 assert_eq!(self.columncount(), other.rowcount());
607
608 let mut result = BitMatrix::<WORD_COUNT>::with_shape(self.rowcount(), other.columncount());
609
610 for i in 0..self.rowcount() {
611 for j in 0..other.columncount() {
612 let mut val = false;
613 for k in 0..self.columncount() {
614 val ^= self[[i, k]] && other[[k, j]];
615 }
616 result.set((i, j), val);
617 }
618 }
619
620 result
621 }
622}
623
624impl<const WORD_COUNT: usize> std::fmt::Display for BitMatrix<WORD_COUNT> {
625 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
626 for row_index in 0..self.rowcount() {
627 for column_index in 0..self.columncount() {
628 let value = i32::from(self.get((row_index, column_index)));
629 write!(f, "{value:?}")?;
630 }
631 writeln!(f)?;
632 }
633 Ok(())
634 }
635}
636
637impl<const WORD_COUNT: usize> FromStr for BitMatrix<WORD_COUNT> {
638 type Err = usize;
639
640 fn from_str(s: &str) -> Result<Self, Self::Err> {
641 let mut rows = Vec::<BitVec>::new();
642 let mut column_count = 0;
643 for row_string in s.split(&['|', '[', ']', '(', ')', ';', '\n']) {
644 if !row_string.is_empty() {
645 let mut res = Vec::<bool>::new();
646 for char in row_string.chars() {
647 match char {
648 '0' | '.' | '▫' | '□' => res.push(false),
649 '1' | '▪' | '■' => res.push(true),
650 ' ' | '-' | ',' => {}
651 _ => return Err(0),
652 }
653 }
654 if !res.is_empty() {
655 column_count = column_count.max(res.len());
656 rows.push(res.into_iter().collect());
657 }
658 }
659 }
660 Ok(BitMatrix::from_iter(rows.iter(), column_count))
661 }
662}
663
664/// # Panics
665///
666/// Should not panic. TODO: refactor so clippy does not complain
667pub fn row_stacked<'t, Matrices, const WORD_COUNT: usize>(
668 matrices: Matrices,
669) -> BitMatrix<WORD_COUNT>
670where
671 Matrices: IntoIterator<Item = &'t BitMatrix<WORD_COUNT>>,
672{
673 let mut buffer = Vec::<BitBlock<WORD_COUNT>>::new();
674 let mut columncount: Option<usize> = None;
675 let mut rowcount = 0;
676 for matrix in matrices {
677 debug_assert!(columncount.is_none() || columncount.unwrap() == matrix.columncount());
678 buffer.append(&mut matrix.blocks.clone());
679 columncount = Some(matrix.columncount());
680 rowcount += matrix.rowcount();
681 }
682 BitMatrix::<WORD_COUNT>::from_blocks(buffer, (rowcount, *columncount.get_or_insert(0)))
683}
684
685pub fn directly_summed<'t, Matrices>(matrices: Matrices) -> BitMatrix
686where
687 Matrices: IntoIterator<Item = &'t BitMatrix>,
688{
689 let mut rowcount = 0;
690 let mut columncount = 0;
691 let vec_matrices = Vec::from_iter(matrices);
692 for matrix in &vec_matrices {
693 rowcount += matrix.rowcount();
694 columncount += matrix.columncount();
695 }
696 let mut sum = BitMatrix::zeros(rowcount, columncount);
697 let mut sum_row_offset = 0;
698 let mut sum_column_offset = 0;
699 for matrix in &vec_matrices {
700 for row_index in 0..matrix.rowcount() {
701 for column_index in 0..matrix.columncount() {
702 sum.set(
703 (row_index + sum_row_offset, column_index + sum_column_offset),
704 matrix[(row_index, column_index)],
705 );
706 }
707 }
708 sum_row_offset += matrix.rowcount();
709 sum_column_offset += matrix.columncount();
710 }
711 sum
712}
713
714fn pivot_of<const WORD_COUNT: usize>(
715 matrix: &BitMatrix<WORD_COUNT>,
716 starting_at: (usize, usize),
717) -> (usize, usize) {
718 let (mut row_index, mut column_index) = starting_at;
719 if row_index >= matrix.rowcount() || column_index >= matrix.columncount() {
720 return (row_index, column_index);
721 }
722 while !matrix.get((row_index, column_index)) {
723 row_index += 1;
724 if row_index == matrix.rowcount() {
725 column_index += 1;
726 row_index = starting_at.0;
727 if column_index == matrix.columncount() {
728 break;
729 }
730 }
731 }
732 (row_index, column_index)
733}
734
735struct ReductionData<const WORD_COUNT: usize> {
736 column_accessor: BitAccessor<WORD_COUNT>,
737 blocks_per_row: usize,
738 rowstride: usize,
739 base_block: *const BitBlock<WORD_COUNT>,
740 from_block: *mut BitBlock<WORD_COUNT>,
741}
742
743impl<const WORD_COUNT: usize> ReductionData<WORD_COUNT> {
744 pub fn for_pivot(pivot: (usize, usize), within: &BitMatrix<WORD_COUNT>) -> Self {
745 let start_block_offset = pivot.1 / BitBlock::<WORD_COUNT>::BITS;
746 let bit_index = pivot.1 % BitBlock::<WORD_COUNT>::BITS;
747 let from_block = unsafe { within.rows.get_unchecked(pivot.0).add(start_block_offset) };
748 let base_block = unsafe { within.blocks.as_ptr().add(start_block_offset) };
749 let rowstride = within.rowstride();
750
751 ReductionData {
752 column_accessor: BitAccessor::for_index(bit_index),
753 blocks_per_row: rowstride - start_block_offset,
754 rowstride,
755 from_block,
756 base_block,
757 }
758 }
759}
760
761fn reduce<const WORD_COUNT: usize>(matrix: &mut BitMatrix<WORD_COUNT>, from: (usize, usize)) {
762 let data = ReductionData::for_pivot(from, matrix);
763 let mut to_block = data.from_block;
764 to_block = reduce_backward_until(data.base_block, to_block, &data);
765 to_block = unsafe { to_block.add(data.rowstride * matrix.rowcount()) };
766 let until_block = unsafe { data.from_block.add(data.rowstride) };
767 reduce_backward_until(until_block, to_block, &data);
768}
769
770fn reduce_backward_until<const WORD_COUNT: usize>(
771 until_block: *const BitBlock<WORD_COUNT>,
772 mut to_block: *mut BitBlock<WORD_COUNT>,
773 data: &ReductionData<WORD_COUNT>,
774) -> *mut BitBlock<WORD_COUNT> {
775 while until_block != to_block {
776 to_block = unsafe { to_block.sub(data.rowstride) };
777 let column_value = unsafe { data.column_accessor.array_value_of((*to_block).array()) };
778 if column_value {
779 add_into_block(to_block, data.from_block, data.blocks_per_row);
780 }
781 }
782 to_block
783}
784
785fn add_into_block<const WORD_COUNT: usize>(
786 mut to_block: *mut BitBlock<WORD_COUNT>,
787 mut from_block: *const BitBlock<WORD_COUNT>,
788 block_count: usize,
789) {
790 for _ in 0..block_count {
791 unsafe {
792 *to_block ^= &*from_block;
793 to_block = to_block.add(1);
794 from_block = from_block.add(1);
795 }
796 }
797}
798
799/// # Returns
800/// Row reduced echelon form R of `matrix` , transformation matrix T and , inverse transpose of T,
801/// and row rank profile.
802/// T * `matrix` equals R
803pub fn rref_with_transforms<const WORD_COUNT: usize>(
804 mut matrix: BitMatrix<WORD_COUNT>,
805) -> (
806 BitMatrix<WORD_COUNT>,
807 BitMatrix<WORD_COUNT>,
808 BitMatrix<WORD_COUNT>,
809 Vec<usize>,
810) {
811 let num_rows = matrix.rowcount();
812 let mut transform = BitMatrix::identity(num_rows);
813 let mut transform_inv_t = BitMatrix::identity(num_rows);
814 let mut pivot = pivot_of(&matrix, (0, 0));
815 let mut rank_profile = Vec::<usize>::with_capacity(matrix.columncount());
816
817 for row_index in 0..matrix.rowcount() {
818 if pivot.1 >= matrix.columncount() {
819 break;
820 }
821
822 matrix.swap_rows(pivot.0, row_index);
823 transform_inv_t.swap_rows(pivot.0, row_index);
824 transform.swap_rows(pivot.0, row_index);
825
826 pivot.0 = row_index;
827 rank_profile.push(pivot.1);
828 reduce_with_transforms(&mut matrix, &mut transform, &mut transform_inv_t, pivot);
829 pivot = pivot_of(&matrix, (pivot.0 + 1, pivot.1 + 1));
830 }
831 (matrix, transform, transform_inv_t, rank_profile)
832}
833
834fn reduce_with_transforms<const WORD_COUNT: usize>(
835 matrix: &mut BitMatrix<WORD_COUNT>,
836 transform: &mut BitMatrix<WORD_COUNT>,
837 transform_inv_t: &mut BitMatrix<WORD_COUNT>,
838 from: (usize, usize),
839) {
840 let rowcount = matrix.rowcount();
841 for row_index in 0..from.0 {
842 xor_if_column_with_transforms(
843 from.1,
844 matrix,
845 transform,
846 transform_inv_t,
847 row_index,
848 from.0,
849 );
850 }
851 for row_index in from.0 + 1..rowcount {
852 xor_if_column_with_transforms(
853 from.1,
854 matrix,
855 transform,
856 transform_inv_t,
857 row_index,
858 from.0,
859 );
860 }
861}
862
863fn xor_if_column_with_transforms<const WORD_COUNT: usize>(
864 column_index: usize,
865 matrix: &mut BitMatrix<WORD_COUNT>,
866 transform: &mut BitMatrix<WORD_COUNT>,
867 transform_inv_t: &mut BitMatrix<WORD_COUNT>,
868 row_index: usize,
869 from_row_index: usize,
870) {
871 if matrix[(row_index, column_index)] {
872 matrix.add_into_row(row_index, from_row_index);
873 transform.add_into_row(row_index, from_row_index);
874 transform_inv_t.add_into_row(from_row_index, row_index);
875 }
876}
877
878pub fn kernel_basis_matrix<const WORD_COUNT: usize>(
879 matrix: &BitMatrix<WORD_COUNT>,
880) -> BitMatrix<WORD_COUNT> {
881 let num_cols = matrix.columncount();
882 let mut rr = matrix.clone();
883 let rank_profile = rr.echelonize();
884 let rank_profile_complement = crate::setwise::complement(&rank_profile, num_cols);
885 let res_row_count = num_cols - rank_profile.len();
886 let mut res = BitMatrix::zeros(res_row_count, num_cols);
887 for (index, elt) in rank_profile.into_iter().enumerate() {
888 for (row_pos, col_src) in rank_profile_complement
889 .iter()
890 .enumerate()
891 .take(res_row_count)
892 {
893 res.set((row_pos, elt), rr[(index, *col_src)]);
894 }
895 }
896 for (index, position) in rank_profile_complement.into_iter().enumerate() {
897 res.set((index, position), true);
898 }
899 res
900}
901
902pub fn full_rank_row_completion_with_inv<const WORD_COUNT: usize>(
903 _matrix: &BitMatrix<WORD_COUNT>,
904) -> (BitMatrix<WORD_COUNT>, BitMatrix<WORD_COUNT>) {
905 // let _num_cols = matrix.columncount();
906 // let rr = matrix.clone();
907 // let rr2 = matrix.clone();
908 // (rr,rr2);
909 todo!()
910}
911
912impl<const WORD_COUNT: usize> Bitwise for Column<'_, WORD_COUNT> {
913 fn weight(&self) -> usize {
914 self.into_iter().filter(|bit| *bit).count()
915 }
916
917 fn support(&self) -> impl SortedIterator<Item = usize> {
918 Box::new(
919 self.into_iter()
920 .enumerate()
921 .filter(|pair| pair.1)
922 .map(|pair| pair.0),
923 )
924 .assume_sorted_by_item()
925 }
926
927 fn index(&self, index: usize) -> bool {
928 let block = unsafe { &*self.rows[index].add(self.block_index) };
929 self.accessor.array_value_of(block.array())
930 }
931}
932
933impl<const WORD_COUNT: usize> Dot for Column<'_, WORD_COUNT> {
934 fn dot(&self, other: &Self) -> bool {
935 assert_eq!(self.rows.len(), other.rows.len());
936 let mut result = false;
937 for index in 0..self.rows.len() {
938 result ^= self.index(index) & other.index(index);
939 }
940 result
941 }
942}
943
944impl<const WORD_COUNT: usize> OverlapWeight for Column<'_, WORD_COUNT> {
945 fn and_weight(&self, other: &Self) -> usize {
946 assert_eq!(self.rows.len(), other.rows.len());
947 let mut result = 0usize;
948 for index in 0..self.rows.len() {
949 if self.index(index) & other.index(index) {
950 result += 1;
951 }
952 }
953 result
954 }
955
956 fn or_weight(&self, other: &Self) -> usize {
957 assert_eq!(self.rows.len(), other.rows.len());
958 let mut result = 0usize;
959 for index in 0..self.rows.len() {
960 if self.index(index) | other.index(index) {
961 result += 1;
962 }
963 }
964 result
965 }
966}
967
968impl<const WORD_COUNT: usize> PartialEq for Column<'_, WORD_COUNT> {
969 fn eq(&self, other: &Self) -> bool {
970 if self.rows.len() != other.rows.len() {
971 return false;
972 }
973 for index in 0..self.rows.len() {
974 if self.index(index) != other.index(index) {
975 return false;
976 }
977 }
978 true
979 }
980}
981
982impl<const WORD_COUNT: usize> Eq for Column<'_, WORD_COUNT> {}
983
984impl<const WORD_COUNT: usize> Column<'_, WORD_COUNT> {
985 #[must_use]
986 pub fn slice(&self, range: Range<usize>) -> Self {
987 Column {
988 rows: &self.rows[range],
989 accessor: self.accessor.clone(),
990 block_index: self.block_index,
991 }
992 }
993
994 #[must_use]
995 pub fn len(&self) -> usize {
996 self.rows.len()
997 }
998
999 #[must_use]
1000 pub fn is_empty(&self) -> bool {
1001 self.len() == 0
1002 }
1003}
1004
1005// impl<'life,const WORD_COUNT: usize> IntoIterator for Column<'life,WORD_COUNT> {
1006// type Item = bool;
1007// type IntoIter = ColumnIterator<'life,WORD_COUNT>;
1008// fn into_iter(self) -> Self::IntoIter {
1009// ColumnIterator {
1010// column: self,
1011// row_index: 0,
1012// }
1013// }
1014// }
1015
1016impl<'life, const WORD_COUNT: usize> IntoIterator for &'life Column<'_, WORD_COUNT> {
1017 type Item = bool;
1018 type IntoIter = ColumnIterator<'life, WORD_COUNT>;
1019 fn into_iter(self) -> Self::IntoIter {
1020 ColumnIterator {
1021 column: self,
1022 row_index: 0,
1023 }
1024 }
1025}
1026
1027impl<const WORD_COUNT: usize> Column<'_, WORD_COUNT> {
1028 #[must_use]
1029 pub fn iter(&self) -> ColumnIterator<'_, WORD_COUNT> {
1030 <&Self as IntoIterator>::into_iter(self)
1031 }
1032}
1033
1034pub struct ColumnIterator<'life, const WORD_COUNT: usize = WORD_COUNT_DEFAULT> {
1035 column: &'life Column<'life, WORD_COUNT>,
1036 row_index: usize,
1037}
1038
1039impl<const WORD_COUNT: usize> Iterator for ColumnIterator<'_, WORD_COUNT> {
1040 type Item = bool;
1041
1042 fn next(&mut self) -> Option<Self::Item> {
1043 if self.row_index >= self.column.rows.len() {
1044 return None;
1045 }
1046 let output = self.column.index(self.row_index);
1047 self.row_index += 1;
1048 Some(output)
1049 }
1050}
1051
1052impl<const WORD_COUNT: usize> NeutralElement for Column<'_, WORD_COUNT> {
1053 type NeutralElementType = BitVec<WORD_COUNT>;
1054
1055 fn neutral_element(&self) -> Self::NeutralElementType {
1056 BitVec::<WORD_COUNT>::zeros(self.rows.len())
1057 }
1058
1059 fn default_size_neutral_element() -> Self::NeutralElementType {
1060 Self::NeutralElementType::default_size_neutral_element()
1061 }
1062
1063 fn neutral_element_of_size(size: usize) -> Self::NeutralElementType {
1064 Self::NeutralElementType::neutral_element_of_size(size)
1065 }
1066}
1067
1068impl<const WORD_COUNT: usize> BitwiseNeutralElement for Column<'_, WORD_COUNT> {}
1069
1070impl<'life, const WORD_COUNT: usize> BitwiseBinaryOps<Column<'life, WORD_COUNT>>
1071 for BitVec<WORD_COUNT>
1072{
1073 fn assign(&mut self, other: &Column<'life, WORD_COUNT>) {
1074 for (index, val) in other.into_iter().enumerate() {
1075 self.assign_index(index, val);
1076 }
1077 }
1078
1079 fn bitxor_assign(&mut self, other: &Column<'life, WORD_COUNT>) {
1080 for (index, val) in other.into_iter().enumerate() {
1081 if val {
1082 self.negate_index(index);
1083 }
1084 }
1085 }
1086
1087 fn bitand_assign(&mut self, other: &Column<'life, WORD_COUNT>) {
1088 for (index, val) in other.into_iter().enumerate() {
1089 if !val {
1090 self.assign_index(index, false);
1091 }
1092 }
1093 }
1094}
1095
1096impl<'life1, const WORD_COUNT_1: usize, const WORD_COUNT_2: usize>
1097 BitwiseBinaryOps<Column<'life1, WORD_COUNT_1>> for MutableBitView<'_, WORD_COUNT_2>
1098{
1099 fn assign(&mut self, other: &Column<'life1, WORD_COUNT_1>) {
1100 for (index, val) in other.into_iter().enumerate() {
1101 self.assign_index(index, val);
1102 }
1103 }
1104
1105 fn bitxor_assign(&mut self, other: &Column<'life1, WORD_COUNT_1>) {
1106 for (index, val) in other.into_iter().enumerate() {
1107 if val {
1108 self.negate_index(index);
1109 }
1110 }
1111 }
1112
1113 fn bitand_assign(&mut self, other: &Column<'life1, WORD_COUNT_1>) {
1114 for (index, val) in other.into_iter().enumerate() {
1115 if !val {
1116 self.assign_index(index, false);
1117 }
1118 }
1119 }
1120}
1121
1122pub fn is_zero_padded_identity(row_iterator: impl ExactSizeIterator<Item: Bitwise>) -> bool {
1123 row_iterator
1124 .into_iter()
1125 .enumerate()
1126 .all(|(row_index, row)| row.is_one_bit(row_index))
1127}
1128
1129pub fn is_zero_padded_symmetric<'life, const WORD_COUNT: usize>(
1130 row_iterator: impl ExactSizeIterator<Item = BitView<'life, WORD_COUNT>>,
1131 column_count: usize,
1132) -> bool {
1133 let matrix = BitMatrix::from_row_iter(row_iterator, column_count);
1134 matrix == matrix.transposed()
1135}
1136
1137pub fn are_zero_rows(mut row_iterator: impl Iterator<Item: Bitwise>) -> bool {
1138 row_iterator.all(|row| row.is_zero())
1139}