Loading...
Searching...
No Matches
unordered_set_column.h
Go to the documentation of this file.
1/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2 * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3 * Author(s): Hannah Schreiber
4 *
5 * Copyright (C) 2022-24 Inria
6 *
7 * Modification(s):
8 * - YYYY/MM Author: Description of the modification
9 */
10
18#ifndef PM_UNORDERED_SET_COLUMN_H
19#define PM_UNORDERED_SET_COLUMN_H
20
21#include <vector>
22#include <stdexcept>
23#include <type_traits>
24#include <set>
25#include <utility> //std::swap, std::move & std::exchange
26
27#include <boost/iterator/indirect_iterator.hpp>
28#if BOOST_VERSION >= 108100
29#include <boost/unordered/unordered_flat_set.hpp>
30#else
31#include <unordered_set>
32#endif
33
35
36namespace Gudhi {
37namespace persistence_matrix {
38
39//For unordered_set container. Outside of Unordered_set_column because of a msvc bug who can't compile properly
40//unordered_flat_set if the hash method is nested.
41template <class Cell>
42struct CellPointerHash {
43 size_t operator()(const Cell* c) const { return std::hash<Cell>()(*c); }
44};
45template <class Cell>
46struct CellPointerEq {
47 bool operator()(const Cell* c1, const Cell* c2) const { return *c1 == *c2; }
48};
49
63template <class Master_matrix>
64class Unordered_set_column : public Master_matrix::Row_access_option,
65 public Master_matrix::Column_dimension_option,
66 public Master_matrix::Chain_column_option
67{
68 public:
69 using Master = Master_matrix;
70 using index = typename Master_matrix::index;
71 using id_index = typename Master_matrix::id_index;
72 using dimension_type = typename Master_matrix::dimension_type;
73 using Field_element_type = typename Master_matrix::element_type;
74 using Cell = typename Master_matrix::Cell_type;
75 using Column_settings = typename Master_matrix::Column_settings;
76
77 private:
78 using Field_operators = typename Master_matrix::Field_operators;
79 using Cell_constructor = typename Master_matrix::Cell_constructor;
80
81 struct CellPointerComp {
82 bool operator()(const Cell* c1, const Cell* c2) const { return *c1 < *c2; }
83 };
84
85#if BOOST_VERSION >= 108100
86 using Column_type = boost::unordered_flat_set<Cell*, CellPointerHash<Cell>, CellPointerEq<Cell>>;
87#else
88 using Column_type = std::unordered_set<Cell*, CellPointerHash<Cell>, CellPointerEq<Cell>>;
89#endif
90
91 public:
92 using iterator = boost::indirect_iterator<typename Column_type::iterator>;
93 using const_iterator = boost::indirect_iterator<typename Column_type::const_iterator>;
94
95 Unordered_set_column(Column_settings* colSettings = nullptr);
96 template <class Container_type = typename Master_matrix::boundary_type>
97 Unordered_set_column(const Container_type& nonZeroRowIndices,
98 Column_settings* colSettings);
99 template <class Container_type = typename Master_matrix::boundary_type, class Row_container_type>
100 Unordered_set_column(index columnIndex,
101 const Container_type& nonZeroRowIndices,
102 Row_container_type* rowContainer,
103 Column_settings* colSettings);
104 template <class Container_type = typename Master_matrix::boundary_type>
105 Unordered_set_column(const Container_type& nonZeroChainRowIndices,
106 dimension_type dimension,
107 Column_settings* colSettings);
108 template <class Container_type = typename Master_matrix::boundary_type, class Row_container_type>
109 Unordered_set_column(index columnIndex,
110 const Container_type& nonZeroChainRowIndices,
111 dimension_type dimension,
112 Row_container_type* rowContainer,
113 Column_settings* colSettings);
115 Column_settings* colSettings = nullptr);
116 template <class Row_container_type>
118 index columnIndex,
119 Row_container_type* rowContainer,
120 Column_settings* colSettings = nullptr);
123
124 std::vector<Field_element_type> get_content(int columnLength = -1) const;
125 bool is_non_zero(id_index rowIndex) const;
126 bool is_empty() const;
127 std::size_t size() const;
128
129 template <class Map_type>
130 void reorder(const Map_type& valueMap, [[maybe_unused]] index columnIndex = -1);
131 void clear();
132 void clear(id_index rowIndex);
133
134 id_index get_pivot() const;
135 Field_element_type get_pivot_value() const;
136
137 iterator begin() noexcept;
138 const_iterator begin() const noexcept;
139 iterator end() noexcept;
140 const_iterator end() const noexcept;
141
142 template <class Cell_range>
143 Unordered_set_column& operator+=(const Cell_range& column);
144 Unordered_set_column& operator+=(Unordered_set_column& column);
145
146 Unordered_set_column& operator*=(unsigned int v);
147
148 // this = v * this + column
149 template <class Cell_range>
150 Unordered_set_column& multiply_target_and_add(const Field_element_type& val, const Cell_range& column);
151 Unordered_set_column& multiply_target_and_add(const Field_element_type& val, Unordered_set_column& column);
152 // this = this + column * v
153 template <class Cell_range>
154 Unordered_set_column& multiply_source_and_add(const Cell_range& column, const Field_element_type& val);
155 Unordered_set_column& multiply_source_and_add(Unordered_set_column& column, const Field_element_type& val);
156
157 friend bool operator==(const Unordered_set_column& c1, const Unordered_set_column& c2) {
158 if (&c1 == &c2) return true;
159 if (c1.column_.size() != c2.column_.size()) return false;
160
161 for (Cell* cell : c1.column_){
162 auto it = c2.column_.find(cell);
163 if (it == c2.column_.end()) return false;
164 if constexpr (!Master_matrix::Option_list::is_z2)
165 if ((*it)->get_element() != cell->get_element()) return false;
166 }
167 return true;
168 }
169 friend bool operator<(const Unordered_set_column& c1, const Unordered_set_column& c2) {
170 if (&c1 == &c2) return false;
171
172 using id_index = Unordered_set_column<Master_matrix>::id_index;
173 using rep_type = typename std::conditional<Master_matrix::Option_list::is_z2,
174 id_index,
175 std::pair<id_index, unsigned int>
176 >::type;
177
178 auto it1 = c1.column_.begin();
179 auto it2 = c2.column_.begin();
180 std::set<rep_type> cells1, cells2;
181 while (it1 != c1.column_.end() && it2 != c2.column_.end()) {
182 if constexpr (Master_matrix::Option_list::is_z2) {
183 cells1.insert((*it1)->get_row_index());
184 cells2.insert((*it2)->get_row_index());
185 } else {
186 cells1.emplace((*it1)->get_row_index(), (*it1)->get_element());
187 cells2.emplace((*it2)->get_row_index(), (*it2)->get_element());
188 }
189 ++it1;
190 ++it2;
191 }
192 while (it1 != c1.column_.end()) {
193 if constexpr (Master_matrix::Option_list::is_z2) {
194 cells1.insert((*it1)->get_row_index());
195 } else {
196 cells1.emplace((*it1)->get_row_index(), (*it1)->get_element());
197 }
198 ++it1;
199 }
200 while (it2 != c2.column_.end()) {
201 if constexpr (Master_matrix::Option_list::is_z2) {
202 cells2.insert((*it2)->get_row_index());
203 } else {
204 cells2.emplace((*it2)->get_row_index(), (*it2)->get_element());
205 }
206 ++it2;
207 }
208 return cells1 < cells2;
209 }
210
211 // Disabled with row access.
212 Unordered_set_column& operator=(const Unordered_set_column& other);
213
214 friend void swap(Unordered_set_column& col1, Unordered_set_column& col2) {
215 swap(static_cast<typename Master_matrix::Row_access_option&>(col1),
216 static_cast<typename Master_matrix::Row_access_option&>(col2));
217 swap(static_cast<typename Master_matrix::Column_dimension_option&>(col1),
218 static_cast<typename Master_matrix::Column_dimension_option&>(col2));
219 swap(static_cast<typename Master_matrix::Chain_column_option&>(col1),
220 static_cast<typename Master_matrix::Chain_column_option&>(col2));
221 col1.column_.swap(col2.column_);
222 std::swap(col1.operators_, col2.operators_);
223 std::swap(col1.cellPool_, col2.cellPool_);
224 }
225
226 private:
227 using ra_opt = typename Master_matrix::Row_access_option;
228 using dim_opt = typename Master_matrix::Column_dimension_option;
229 using chain_opt = typename Master_matrix::Chain_column_option;
230
231 Column_type column_;
232 Field_operators* operators_;
233 Cell_constructor* cellPool_;
234
235 void _delete_cell(typename Column_type::iterator& it);
236 Cell* _insert_cell(const Field_element_type& value, id_index rowIndex);
237 void _insert_cell(id_index rowIndex);
238 template <class Cell_range>
239 bool _add(const Cell_range& column);
240 template <class Cell_range>
241 bool _multiply_target_and_add(const Field_element_type& val, const Cell_range& column);
242 template <class Cell_range>
243 bool _multiply_source_and_add(const Cell_range& column, const Field_element_type& val);
244 template <class Cell_range, typename F1, typename F2>
245 bool _generic_add(const Cell_range& source, F1&& process_source, F2&& update_target);
246};
247
248template <class Master_matrix>
249inline Unordered_set_column<Master_matrix>::Unordered_set_column(Column_settings* colSettings)
250 : ra_opt(),
251 dim_opt(),
252 chain_opt(),
253 operators_(nullptr),
254 cellPool_(colSettings == nullptr ? nullptr : &(colSettings->cellConstructor))
255{
256 if (operators_ == nullptr && cellPool_ == nullptr) return; // to allow default constructor which gives a dummy column
257 if constexpr (!Master_matrix::Option_list::is_z2) {
258 operators_ = &(colSettings->operators);
259 }
260}
261
262template <class Master_matrix>
263template <class Container_type>
264inline Unordered_set_column<Master_matrix>::Unordered_set_column(
265 const Container_type& nonZeroRowIndices, Column_settings* colSettings)
266 : ra_opt(),
267 dim_opt(nonZeroRowIndices.size() == 0 ? 0 : nonZeroRowIndices.size() - 1),
268 chain_opt(),
269 column_(nonZeroRowIndices.size()),
270 operators_(nullptr),
271 cellPool_(&(colSettings->cellConstructor))
272{
273 static_assert(!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type,
274 "Constructor not available for chain columns, please specify the dimension of the chain.");
275
276 if constexpr (Master_matrix::Option_list::is_z2) {
277 for (id_index id : nonZeroRowIndices) {
278 _insert_cell(id);
279 }
280 } else {
281 operators_ = &(colSettings->operators);
282 for (const auto& p : nonZeroRowIndices) {
283 _insert_cell(operators_->get_value(p.second), p.first);
284 }
285 }
286}
287
288template <class Master_matrix>
289template <class Container_type, class Row_container_type>
290inline Unordered_set_column<Master_matrix>::Unordered_set_column(
291 index columnIndex,
292 const Container_type& nonZeroRowIndices,
293 Row_container_type* rowContainer,
294 Column_settings* colSettings)
295 : ra_opt(columnIndex, rowContainer),
296 dim_opt(nonZeroRowIndices.size() == 0 ? 0 : nonZeroRowIndices.size() - 1),
297 chain_opt([&] {
298 if constexpr (Master_matrix::Option_list::is_z2) {
299 return nonZeroRowIndices.begin() == nonZeroRowIndices.end() ? -1 : *std::prev(nonZeroRowIndices.end());
300 } else {
301 return nonZeroRowIndices.begin() == nonZeroRowIndices.end() ? -1 : std::prev(nonZeroRowIndices.end())->first;
302 }
303 }()),
304 column_(nonZeroRowIndices.size()),
305 operators_(nullptr),
306 cellPool_(&(colSettings->cellConstructor))
307{
308 static_assert(!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type,
309 "Constructor not available for chain columns, please specify the dimension of the chain.");
310
311 if constexpr (Master_matrix::Option_list::is_z2) {
312 for (id_index id : nonZeroRowIndices) {
313 _insert_cell(id);
314 }
315 } else {
316 operators_ = &(colSettings->operators);
317 for (const auto& p : nonZeroRowIndices) {
318 _insert_cell(operators_->get_value(p.second), p.first);
319 }
320 }
321}
322
323template <class Master_matrix>
324template <class Container_type>
325inline Unordered_set_column<Master_matrix>::Unordered_set_column(
326 const Container_type& nonZeroRowIndices,
327 dimension_type dimension,
328 Column_settings* colSettings)
329 : ra_opt(),
330 dim_opt(dimension),
331 chain_opt([&] {
332 if constexpr (Master_matrix::Option_list::is_z2) {
333 return nonZeroRowIndices.begin() == nonZeroRowIndices.end() ? -1 : *std::prev(nonZeroRowIndices.end());
334 } else {
335 return nonZeroRowIndices.begin() == nonZeroRowIndices.end() ? -1 : std::prev(nonZeroRowIndices.end())->first;
336 }
337 }()),
338 column_(nonZeroRowIndices.size()),
339 operators_(nullptr),
340 cellPool_(&(colSettings->cellConstructor))
341{
342 if constexpr (Master_matrix::Option_list::is_z2) {
343 for (id_index id : nonZeroRowIndices) {
344 _insert_cell(id);
345 }
346 } else {
347 operators_ = &(colSettings->operators);
348 for (const auto& p : nonZeroRowIndices) {
349 _insert_cell(operators_->get_value(p.second), p.first);
350 }
351 }
352}
353
354template <class Master_matrix>
355template <class Container_type, class Row_container_type>
356inline Unordered_set_column<Master_matrix>::Unordered_set_column(
357 index columnIndex,
358 const Container_type& nonZeroRowIndices,
359 dimension_type dimension,
360 Row_container_type* rowContainer,
361 Column_settings* colSettings)
362 : ra_opt(columnIndex, rowContainer),
363 dim_opt(dimension),
364 chain_opt([&] {
365 if constexpr (Master_matrix::Option_list::is_z2) {
366 return nonZeroRowIndices.begin() == nonZeroRowIndices.end() ? -1 : *std::prev(nonZeroRowIndices.end());
367 } else {
368 return nonZeroRowIndices.begin() == nonZeroRowIndices.end() ? -1 : std::prev(nonZeroRowIndices.end())->first;
369 }
370 }()),
371 column_(nonZeroRowIndices.size()),
372 operators_(nullptr),
373 cellPool_(&(colSettings->cellConstructor))
374{
375 if constexpr (Master_matrix::Option_list::is_z2) {
376 for (id_index id : nonZeroRowIndices) {
377 _insert_cell(id);
378 }
379 } else {
380 operators_ = &(colSettings->operators);
381 for (const auto& p : nonZeroRowIndices) {
382 _insert_cell(operators_->get_value(p.second), p.first);
383 }
384 }
385}
386
387template <class Master_matrix>
388inline Unordered_set_column<Master_matrix>::Unordered_set_column(const Unordered_set_column& column,
389 Column_settings* colSettings)
390 : ra_opt(),
391 dim_opt(static_cast<const dim_opt&>(column)),
392 chain_opt(static_cast<const chain_opt&>(column)),
393 column_(column.column_.bucket_count()),
394 operators_(colSettings == nullptr ? column.operators_ : nullptr),
395 cellPool_(colSettings == nullptr ? column.cellPool_ : &(colSettings->cellConstructor))
396{
397 static_assert(!Master_matrix::Option_list::has_row_access,
398 "Simple copy constructor not available when row access option enabled. Please specify the new column "
399 "index and the row container.");
400
401 if constexpr (!Master_matrix::Option_list::is_z2){
402 if (colSettings != nullptr) operators_ = &(colSettings->operators);
403 }
404
405 for (const Cell* cell : column.column_) {
406 if constexpr (Master_matrix::Option_list::is_z2) {
407 _insert_cell(cell->get_row_index());
408 } else {
409 _insert_cell(cell->get_element(), cell->get_row_index());
410 }
411 }
412}
413
414template <class Master_matrix>
415template <class Row_container_type>
416inline Unordered_set_column<Master_matrix>::Unordered_set_column(const Unordered_set_column& column,
417 index columnIndex,
418 Row_container_type* rowContainer,
419 Column_settings* colSettings)
420 : ra_opt(columnIndex, rowContainer),
421 dim_opt(static_cast<const dim_opt&>(column)),
422 chain_opt(static_cast<const chain_opt&>(column)),
423 column_(column.column_.bucket_count()),
424 operators_(colSettings == nullptr ? column.operators_ : nullptr),
425 cellPool_(colSettings == nullptr ? column.cellPool_ : &(colSettings->cellConstructor))
426{
427 if constexpr (!Master_matrix::Option_list::is_z2){
428 if (colSettings != nullptr) operators_ = &(colSettings->operators);
429 }
430
431 for (const Cell* cell : column.column_) {
432 if constexpr (Master_matrix::Option_list::is_z2) {
433 _insert_cell(cell->get_row_index());
434 } else {
435 _insert_cell(cell->get_element(), cell->get_row_index());
436 }
437 }
438}
439
440template <class Master_matrix>
441inline Unordered_set_column<Master_matrix>::Unordered_set_column(
442 Unordered_set_column&& column) noexcept
443 : ra_opt(std::move(static_cast<ra_opt&>(column))),
444 dim_opt(std::move(static_cast<dim_opt&>(column))),
445 chain_opt(std::move(static_cast<chain_opt&>(column))),
446 column_(std::move(column.column_)),
447 operators_(std::exchange(column.operators_, nullptr)),
448 cellPool_(std::exchange(column.cellPool_, nullptr))
449{}
450
451template <class Master_matrix>
452inline Unordered_set_column<Master_matrix>::~Unordered_set_column()
453{
454 for (auto* cell : column_) {
455 if constexpr (Master_matrix::Option_list::has_row_access) ra_opt::unlink(cell);
456 cellPool_->destroy(cell);
457 }
458}
459
460template <class Master_matrix>
461inline std::vector<typename Unordered_set_column<Master_matrix>::Field_element_type>
462Unordered_set_column<Master_matrix>::get_content(int columnLength) const
463{
464 if (columnLength < 0 && column_.size() > 0)
465 columnLength = (*std::max_element(column_.begin(), column_.end(), CellPointerComp()))->get_row_index() + 1;
466 else if (columnLength < 0)
467 return std::vector<Field_element_type>();
468
469 std::vector<Field_element_type> container(columnLength, 0);
470 for (auto it = column_.begin(); it != column_.end(); ++it) {
471 if ((*it)->get_row_index() < static_cast<id_index>(columnLength)) {
472 if constexpr (Master_matrix::Option_list::is_z2) {
473 container[(*it)->get_row_index()] = 1;
474 } else {
475 container[(*it)->get_row_index()] = (*it)->get_element();
476 }
477 }
478 }
479 return container;
480}
481
482template <class Master_matrix>
483inline bool Unordered_set_column<Master_matrix>::is_non_zero(id_index rowIndex) const
484{
485 Cell cell(rowIndex);
486 return column_.find(&cell) != column_.end();
487}
488
489template <class Master_matrix>
490inline bool Unordered_set_column<Master_matrix>::is_empty() const
491{
492 return column_.empty();
493}
494
495template <class Master_matrix>
496inline std::size_t Unordered_set_column<Master_matrix>::size() const
497{
498 return column_.size();
499}
500
501template <class Master_matrix>
502template <class Map_type>
503inline void Unordered_set_column<Master_matrix>::reorder(const Map_type& valueMap,
504 [[maybe_unused]] index columnIndex)
505{
506 static_assert(!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type,
507 "Method not available for chain columns.");
508
509 Column_type newSet;
510
511 for (Cell* cell : column_) {
512 if constexpr (Master_matrix::Option_list::has_row_access) {
513 ra_opt::unlink(cell);
514 if (columnIndex != static_cast<index>(-1)) cell->set_column_index(columnIndex);
515 }
516 cell->set_row_index(valueMap.at(cell->get_row_index()));
517 newSet.insert(cell);
518 if constexpr (Master_matrix::Option_list::has_row_access &&
519 Master_matrix::Option_list::has_intrusive_rows) // intrusive list
520 ra_opt::insert_cell(cell->get_row_index(), cell);
521 }
522
523 // when row is a set, all cells have to be deleted first, to avoid colliding when inserting
524 if constexpr (Master_matrix::Option_list::has_row_access && !Master_matrix::Option_list::has_intrusive_rows) { // set
525 for (Cell* cell : newSet) {
526 ra_opt::insert_cell(cell->get_row_index(), cell);
527 }
528 }
529
530 column_.swap(newSet);
531}
532
533template <class Master_matrix>
534inline void Unordered_set_column<Master_matrix>::clear()
535{
536 static_assert(!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type,
537 "Method not available for chain columns as a base element should not be empty.");
538
539 for (auto* cell : column_) {
540 if constexpr (Master_matrix::Option_list::has_row_access) ra_opt::unlink(cell);
541 cellPool_->destroy(cell);
542 }
543
544 column_.clear();
545}
546
547template <class Master_matrix>
548inline void Unordered_set_column<Master_matrix>::clear(id_index rowIndex)
549{
550 static_assert(!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type,
551 "Method not available for chain columns.");
552
553 auto cell = cellPool_->construct(rowIndex);
554 auto it = column_.find(cell);
555 if (it != column_.end()) {
556 _delete_cell(it);
557 }
558 cellPool_->destroy(cell);
559}
560
561template <class Master_matrix>
562inline typename Unordered_set_column<Master_matrix>::id_index
563Unordered_set_column<Master_matrix>::get_pivot() const
564{
565 static_assert(Master_matrix::isNonBasic,
566 "Method not available for base columns."); // could technically be, but is the notion usefull then?
567
568 if constexpr (Master_matrix::Option_list::is_of_boundary_type) {
569 if (column_.empty()) return -1;
570 // linear search could be avoided with storing the pivot. But even then, some modifications of the column requires
571 // the max, so not clear how much it is worth it.
572 return (*std::max_element(column_.begin(), column_.end(), CellPointerComp()))->get_row_index();
573 } else {
574 return chain_opt::get_pivot();
575 }
576}
577
578template <class Master_matrix>
579inline typename Unordered_set_column<Master_matrix>::Field_element_type
580Unordered_set_column<Master_matrix>::get_pivot_value() const
581{
582 static_assert(Master_matrix::isNonBasic,
583 "Method not available for base columns."); // could technically be, but is the notion usefull then?
584
585 if constexpr (Master_matrix::Option_list::is_z2) {
586 return 1;
587 } else {
588 if constexpr (Master_matrix::Option_list::is_of_boundary_type) {
589 if (column_.empty()) return 0;
590 return (*std::max_element(column_.begin(), column_.end(), CellPointerComp()))->get_element();
591 } else {
592 if (chain_opt::get_pivot() == static_cast<id_index>(-1)) return Field_element_type();
593 for (const Cell* cell : column_) {
594 if (cell->get_row_index() == chain_opt::get_pivot()) return cell->get_element();
595 }
596 return Field_element_type(); // should never happen if chain column is used properly
597 }
598 }
599}
600
601template <class Master_matrix>
602inline typename Unordered_set_column<Master_matrix>::iterator
603Unordered_set_column<Master_matrix>::begin() noexcept
604{
605 return column_.begin();
606}
607
608template <class Master_matrix>
609inline typename Unordered_set_column<Master_matrix>::const_iterator
610Unordered_set_column<Master_matrix>::begin() const noexcept
611{
612 return column_.begin();
613}
614
615template <class Master_matrix>
616inline typename Unordered_set_column<Master_matrix>::iterator
617Unordered_set_column<Master_matrix>::end() noexcept
618{
619 return column_.end();
620}
621
622template <class Master_matrix>
623inline typename Unordered_set_column<Master_matrix>::const_iterator
624Unordered_set_column<Master_matrix>::end() const noexcept
625{
626 return column_.end();
627}
628
629template <class Master_matrix>
630template <class Cell_range>
631inline Unordered_set_column<Master_matrix>&
632Unordered_set_column<Master_matrix>::operator+=(const Cell_range& column)
633{
634 static_assert((!Master_matrix::isNonBasic || std::is_same_v<Cell_range, Unordered_set_column>),
635 "For boundary columns, the range has to be a column of same type to help ensure the validity of the "
636 "base element."); // could be removed, if we give the responsability to the user.
637 static_assert((!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type),
638 "For chain columns, the given column cannot be constant.");
639
640 _add(column);
641
642 return *this;
643}
644
645template <class Master_matrix>
646inline Unordered_set_column<Master_matrix>&
647Unordered_set_column<Master_matrix>::operator+=(Unordered_set_column& column)
648{
649 if constexpr (Master_matrix::isNonBasic && !Master_matrix::Option_list::is_of_boundary_type) {
650 // assumes that the addition never zeros out this column.
651 if (_add(column)) {
652 chain_opt::swap_pivots(column);
653 dim_opt::swap_dimension(column);
654 }
655 } else {
656 _add(column);
657 }
658
659 return *this;
660}
661
662template <class Master_matrix>
663inline Unordered_set_column<Master_matrix>&
664Unordered_set_column<Master_matrix>::operator*=(unsigned int v)
665{
666 if constexpr (Master_matrix::Option_list::is_z2) {
667 if (v % 2 == 0) {
668 if constexpr (Master_matrix::isNonBasic && !Master_matrix::Option_list::is_of_boundary_type) {
669 throw std::invalid_argument("A chain column should not be multiplied by 0.");
670 } else {
671 clear();
672 }
673 }
674 } else {
675 Field_element_type val = operators_->get_value(v);
676
677 if (val == Field_operators::get_additive_identity()) {
678 if constexpr (Master_matrix::isNonBasic && !Master_matrix::Option_list::is_of_boundary_type) {
679 throw std::invalid_argument("A chain column should not be multiplied by 0.");
680 } else {
681 clear();
682 }
683 return *this;
684 }
685
686 if (val == Field_operators::get_multiplicative_identity()) return *this;
687
688 for (Cell* cell : column_) {
689 operators_->multiply_inplace(cell->get_element(), val);
690 if constexpr (Master_matrix::Option_list::has_row_access) ra_opt::update_cell(*cell);
691 }
692 }
693
694 return *this;
695}
696
697template <class Master_matrix>
698template <class Cell_range>
699inline Unordered_set_column<Master_matrix>&
700Unordered_set_column<Master_matrix>::multiply_target_and_add(const Field_element_type& val,
701 const Cell_range& column)
702{
703 static_assert((!Master_matrix::isNonBasic || std::is_same_v<Cell_range, Unordered_set_column>),
704 "For boundary columns, the range has to be a column of same type to help ensure the validity of the "
705 "base element."); // could be removed, if we give the responsability to the user.
706 static_assert((!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type),
707 "For chain columns, the given column cannot be constant.");
708
709 if constexpr (Master_matrix::Option_list::is_z2) {
710 if (val) {
711 _add(column);
712 } else {
713 clear();
714 _add(column);
715 }
716 } else {
717 _multiply_target_and_add(val, column);
718 }
719
720 return *this;
721}
722
723template <class Master_matrix>
724inline Unordered_set_column<Master_matrix>&
725Unordered_set_column<Master_matrix>::multiply_target_and_add(const Field_element_type& val,
726 Unordered_set_column& column)
727{
728 if constexpr (Master_matrix::isNonBasic && !Master_matrix::Option_list::is_of_boundary_type) {
729 // assumes that the addition never zeros out this column.
730 if constexpr (Master_matrix::Option_list::is_z2) {
731 if (val) {
732 if (_add(column)) {
733 chain_opt::swap_pivots(column);
734 dim_opt::swap_dimension(column);
735 }
736 } else {
737 throw std::invalid_argument("A chain column should not be multiplied by 0.");
738 }
739 } else {
740 if (_multiply_target_and_add(val, column)) {
741 chain_opt::swap_pivots(column);
742 dim_opt::swap_dimension(column);
743 }
744 }
745 } else {
746 if constexpr (Master_matrix::Option_list::is_z2) {
747 if (val) {
748 _add(column);
749 } else {
750 clear();
751 _add(column);
752 }
753 } else {
754 _multiply_target_and_add(val, column);
755 }
756 }
757
758 return *this;
759}
760
761template <class Master_matrix>
762template <class Cell_range>
763inline Unordered_set_column<Master_matrix>&
764Unordered_set_column<Master_matrix>::multiply_source_and_add(const Cell_range& column,
765 const Field_element_type& val)
766{
767 static_assert((!Master_matrix::isNonBasic || std::is_same_v<Cell_range, Unordered_set_column>),
768 "For boundary columns, the range has to be a column of same type to help ensure the validity of the "
769 "base element."); // could be removed, if we give the responsability to the user.
770 static_assert((!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type),
771 "For chain columns, the given column cannot be constant.");
772
773 if constexpr (Master_matrix::Option_list::is_z2) {
774 if (val) {
775 _add(column);
776 }
777 } else {
778 _multiply_source_and_add(column, val);
779 }
780
781 return *this;
782}
783
784template <class Master_matrix>
785inline Unordered_set_column<Master_matrix>&
786Unordered_set_column<Master_matrix>::multiply_source_and_add(Unordered_set_column& column,
787 const Field_element_type& val)
788{
789 if constexpr (Master_matrix::isNonBasic && !Master_matrix::Option_list::is_of_boundary_type) {
790 // assumes that the addition never zeros out this column.
791 if constexpr (Master_matrix::Option_list::is_z2) {
792 if (val) {
793 if (_add(column)) {
794 chain_opt::swap_pivots(column);
795 dim_opt::swap_dimension(column);
796 }
797 }
798 } else {
799 if (_multiply_source_and_add(column, val)) {
800 chain_opt::swap_pivots(column);
801 dim_opt::swap_dimension(column);
802 }
803 }
804 } else {
805 if constexpr (Master_matrix::Option_list::is_z2) {
806 if (val) {
807 _add(column);
808 }
809 } else {
810 _multiply_source_and_add(column, val);
811 }
812 }
813
814 return *this;
815}
816
817template <class Master_matrix>
818inline Unordered_set_column<Master_matrix>&
819Unordered_set_column<Master_matrix>::operator=(const Unordered_set_column& other)
820{
821 static_assert(!Master_matrix::Option_list::has_row_access, "= assignement not enabled with row access option.");
822
823 dim_opt::operator=(other);
824 chain_opt::operator=(other);
825
826 for (auto* cell : column_) {
827 if constexpr (Master_matrix::Option_list::has_row_access) ra_opt::unlink(cell);
828 cellPool_->destroy(cell);
829 }
830 column_.clear();
831
832 operators_ = other.operators_;
833 cellPool_ = other.cellPool_;
834
835 for (const Cell* cell : other.column_) {
836 if constexpr (Master_matrix::Option_list::is_z2) {
837 _insert_cell(cell->get_row_index());
838 } else {
839 _insert_cell(cell->get_element(), cell->get_row_index());
840 }
841 }
842
843 return *this;
844}
845
846template <class Master_matrix>
847inline void Unordered_set_column<Master_matrix>::_delete_cell(typename Column_type::iterator& it)
848{
849 if constexpr (Master_matrix::Option_list::has_row_access) ra_opt::unlink(*it);
850 cellPool_->destroy(*it);
851 auto tmp = it++;
852 // it = column_.erase(it);
853 column_.erase(tmp);
854}
855
856template <class Master_matrix>
857inline typename Unordered_set_column<Master_matrix>::Cell* Unordered_set_column<Master_matrix>::_insert_cell(
858 const Field_element_type& value, id_index rowIndex)
859{
860 if constexpr (Master_matrix::Option_list::has_row_access) {
861 Cell* newCell = cellPool_->construct(ra_opt::columnIndex_, rowIndex);
862 newCell->set_element(value);
863 column_.insert(newCell);
864 ra_opt::insert_cell(rowIndex, newCell);
865 return newCell;
866 } else {
867 Cell* newCell = cellPool_->construct(rowIndex);
868 newCell->set_element(value);
869 column_.insert(newCell);
870 return newCell;
871 }
872}
873
874template <class Master_matrix>
875inline void Unordered_set_column<Master_matrix>::_insert_cell(id_index rowIndex)
876{
877 if constexpr (Master_matrix::Option_list::has_row_access) {
878 Cell* newCell = cellPool_->construct(ra_opt::columnIndex_, rowIndex);
879 column_.insert(newCell);
880 ra_opt::insert_cell(rowIndex, newCell);
881 } else {
882 Cell* newCell = cellPool_->construct(rowIndex);
883 column_.insert(newCell);
884 }
885}
886
887template <class Master_matrix>
888template <class Cell_range>
889inline bool Unordered_set_column<Master_matrix>::_add(const Cell_range& column)
890{
891 return _generic_add(
892 column,
893 [&](const Cell& oldCell, Cell* newCell) {
894 if constexpr (!Master_matrix::Option_list::is_z2) newCell->set_element(oldCell.get_element());
895 },
896 [&](Cell* targetCell, const Cell& sourceCell) {
897 if constexpr (!Master_matrix::Option_list::is_z2)
898 operators_->add_inplace(targetCell->get_element(), sourceCell.get_element());
899 });
900}
901
902template <class Master_matrix>
903template <class Cell_range>
904inline bool Unordered_set_column<Master_matrix>::_multiply_target_and_add(const Field_element_type& val,
905 const Cell_range& column)
906{
907 if (val == 0u) {
908 if constexpr (Master_matrix::isNonBasic && !Master_matrix::Option_list::is_of_boundary_type) {
909 throw std::invalid_argument("A chain column should not be multiplied by 0.");
910 // this would not only mess up the base, but also the pivots stored.
911 } else {
912 clear();
913 for (const Cell& v : column) {
914 _insert_cell(v.get_element(), v.get_row_index());
915 }
916 return true;
917 }
918 }
919
920 // because the column is unordered, I don't see a way to do both operations in one go
921 // without garantees on the cell range...
922 operator*=(val);
923 return _add(column);
924}
925
926template <class Master_matrix>
927template <class Cell_range>
928inline bool Unordered_set_column<Master_matrix>::_multiply_source_and_add(const Cell_range& column,
929 const Field_element_type& val)
930{
931 if (val == 0u) {
932 return false;
933 }
934
935 return _generic_add(column,
936 [&](const Cell& oldCell, Cell* newCell) {
937 newCell->set_element(oldCell.get_element());
938 operators_->multiply_inplace(newCell->get_element(), val);
939 },
940 [&](Cell* targetCell, const Cell& sourceCell) {
941 operators_->multiply_and_add_inplace_back(sourceCell.get_element(), val, targetCell->get_element());
942 });
943}
944
945template <class Master_matrix>
946template <class Cell_range, typename F1, typename F2>
947inline bool Unordered_set_column<Master_matrix>::_generic_add(const Cell_range& source,
948 F1&& process_source,
949 F2&& update_target)
950{
951 bool pivotIsZeroed = false;
952
953 for (const Cell& cell : source) {
954 Cell* newCell;
955 if constexpr (Master_matrix::Option_list::has_row_access) {
956 newCell = cellPool_->construct(ra_opt::columnIndex_, cell.get_row_index());
957 } else {
958 newCell = cellPool_->construct(cell.get_row_index());
959 }
960 auto res = column_.insert(newCell);
961 if (res.second){
962 process_source(cell, newCell);
963 if constexpr (Master_matrix::Option_list::has_row_access) ra_opt::insert_cell(cell.get_row_index(), newCell);
964 } else {
965 cellPool_->destroy(newCell);
966 if constexpr (Master_matrix::Option_list::is_z2) {
967 if constexpr (Master_matrix::isNonBasic && !Master_matrix::Option_list::is_of_boundary_type) {
968 if (cell.get_row_index() == chain_opt::get_pivot()) pivotIsZeroed = true;
969 }
970 _delete_cell(res.first);
971 } else {
972 update_target(*res.first, cell);
973 if ((*res.first)->get_element() == Field_operators::get_additive_identity()) {
974 if constexpr (Master_matrix::isNonBasic && !Master_matrix::Option_list::is_of_boundary_type) {
975 if ((*res.first)->get_row_index() == chain_opt::get_pivot()) pivotIsZeroed = true;
976 }
977 _delete_cell(res.first);
978 } else {
979 if constexpr (Master_matrix::Option_list::has_row_access) ra_opt::update_cell(**res.first);
980 }
981 }
982 }
983 }
984
985 return pivotIsZeroed;
986}
987
988} // namespace persistence_matrix
989} // namespace Gudhi
990
999template <class Master_matrix>
1000struct std::hash<Gudhi::persistence_matrix::Unordered_set_column<Master_matrix> >
1001{
1002 std::size_t operator()(const Gudhi::persistence_matrix::Unordered_set_column<Master_matrix>& column) const {
1003 //can't use Gudhi::persistence_matrix::hash_column because unordered
1004 std::size_t seed = 0;
1005 for (const auto& cell : column) {
1006 seed ^= std::hash<unsigned int>()(cell.get_row_index() * static_cast<unsigned int>(cell.get_element()));
1007 }
1008 return seed;
1009 }
1010};
1011
1012#endif // PM_UNORDERED_SET_COLUMN_H
Contains the New_cell_constructor and Pool_cell_constructor structures.
Column class following the PersistenceMatrixColumn concept.
Definition unordered_set_column.h:67
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14