src/lalg/basis/r/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | #include "../../../util/func_fp/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | template <class T> | ||
| 9 | struct basis_r { | ||
| 10 | cu32 vec_len; | ||
| 11 | vvec<T> basis; | ||
| 12 | |||
| 13 | 30 | CEXPE basis_r(u32 vec_len) NE : vec_len{vec_len}, basis(vec_len, vec<T>(vec_len)) {} | |
| 14 | |||
| 15 | // maybe need setting a larger eps (such as 1e-4) first | ||
| 16 | 1780 | CEXP bool insert(vec<T> x) NE { | |
| 17 | 1780 | x.resize(vec_len); | |
| 18 | 1780 | bool status = false; | |
| 19 |
2/2✓ Branch 1 taken 412524 times.
✓ Branch 2 taken 467 times.
|
412991 | for (u32 i = (u32)basis.size() - 1; ~i; --i) { |
| 20 |
2/2✓ Branch 2 taken 80907 times.
✓ Branch 3 taken 331617 times.
|
412524 | if (is_zero(x[i])) continue; |
| 21 |
2/2✓ Branch 3 taken 330304 times.
✓ Branch 4 taken 1313 times.
|
331617 | if (!is_zero(basis[i][i])) { |
| 22 | 330304 | const T _ = x[i] / basis[i][i]; | |
| 23 | 330304 | x[i] = 0; | |
| 24 |
2/2✓ Branch 3 taken 117825263 times.
✓ Branch 4 taken 330304 times.
|
118155567 | flt_ (u32, j, 0, i) x[j] -= basis[i][j] * _; |
| 25 | } else { | ||
| 26 |
2/2✓ Branch 0 taken 358532 times.
✓ Branch 1 taken 1313 times.
|
359845 | flt_ (u32, j, 0, i) |
| 27 |
4/6✓ Branch 2 taken 358514 times.
✓ Branch 3 taken 18 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 358514 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 358532 times.
|
358532 | if (!is_zero(x[j]) && !is_zero(basis[j][j])) { |
| 28 | ✗ | const T _ = x[j] / basis[j][j]; | |
| 29 | ✗ | x[j] = 0; | |
| 30 | ✗ | flt_ (u32, k, 0, j) x[k] -= basis[j][k] * _; | |
| 31 | } | ||
| 32 |
2/2✓ Branch 1 taken 209775 times.
✓ Branch 2 taken 1313 times.
|
211088 | flt_ (u32, j, i + 1, (u32)basis.size()) |
| 33 |
5/6✓ Branch 3 taken 209774 times.
✓ Branch 4 taken 1 time.
✓ Branch 7 taken 209774 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 209774 times.
✓ Branch 10 taken 1 time.
|
209775 | if (!is_zero(basis[j][i]) && !is_zero(x[i])) { |
| 34 | 209774 | const T _ = basis[j][i] / x[i]; | |
| 35 | 209774 | basis[j][i] = 0; | |
| 36 |
2/2✓ Branch 3 taken 51880364 times.
✓ Branch 4 taken 209774 times.
|
52090138 | flt_ (u32, k, 0, i) basis[j][k] -= x[k] * _; |
| 37 | } | ||
| 38 | 1313 | basis[i] = x, status = true; | |
| 39 | 1313 | break; | |
| 40 | } | ||
| 41 | } | ||
| 42 | 1780 | return status; | |
| 43 | } | ||
| 44 | CEXP bool test(vec<T> x) CNE { | ||
| 45 | for (u32 i = (u32)basis.size() - 1; ~i; --i) { | ||
| 46 | if (is_zero(x[i])) continue; | ||
| 47 | if (!is_zero(basis[i][i])) { | ||
| 48 | const T _ = x[i] / basis[i][i]; | ||
| 49 | x[i] = 0; | ||
| 50 | flt_ (u32, j, 0, i) x[j] -= basis[i][j] * _; | ||
| 51 | } else return false; | ||
| 52 | } | ||
| 53 | return true; | ||
| 54 | } | ||
| 55 | ND CEXP u32 rank() CNE { | ||
| 56 | u32 res = 0; | ||
| 57 | flt_ (u32, i, 0, (u32)basis.size()) res += !is_zero(basis[i][i]); | ||
| 58 | return res; | ||
| 59 | } | ||
| 60 | // @return std::nullopt if x is linear independent with current basis, else | ||
| 61 | // return the solution | ||
| 62 | CEXP auto coord(vec<T> x) { | ||
| 63 | std::optional res{vec<T>(vec_len)}; | ||
| 64 | for (u32 i = basis.size() - 1; ~i; --i) | ||
| 65 | if (!is_zero(x[i])) { | ||
| 66 | if (is_zero(basis[i][i])) { | ||
| 67 | res = std::nullopt; | ||
| 68 | return res; | ||
| 69 | } | ||
| 70 | const T _ = x[i] / basis[i][i]; | ||
| 71 | res.value()[i] = _, x[i] = 0; | ||
| 72 | flt_ (u32, j, 0, i + 1) x[j] -= basis[i][j] * _; | ||
| 73 | } | ||
| 74 | return res; | ||
| 75 | } | ||
| 76 | }; | ||
| 77 | |||
| 78 | } // namespace tifa_libs | ||
| 79 |