list_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_LIST_COLUMN_H
19#define PM_LIST_COLUMN_H
20
21#include <vector>
22#include <stdexcept>
23#include <type_traits>
24#include <list>
25#include <utility> //std::swap, std::move & std::exchange
26
27#include <boost/iterator/indirect_iterator.hpp>
28
29#include <gudhi/Persistence_matrix/allocators/entry_constructors.h>
30#include <gudhi/Persistence_matrix/columns/column_utilities.h>
31
32namespace Gudhi {
33namespace persistence_matrix {
34
46template <class Master_matrix>
47class List_column : public Master_matrix::Row_access_option,
48 public Master_matrix::Column_dimension_option,
49 public Master_matrix::Chain_column_option
50{
51 public:
52 using Master = Master_matrix;
53 using Index = typename Master_matrix::Index;
54 using ID_index = typename Master_matrix::ID_index;
55 using Dimension = typename Master_matrix::Dimension;
56 using Field_element = typename Master_matrix::Element;
57 using Entry = typename Master_matrix::Matrix_entry;
58 using Column_settings = typename Master_matrix::Column_settings;
59
60 private:
61 using Field_operators = typename Master_matrix::Field_operators;
62 using Column_support = std::list<Entry*>;
63 using Entry_constructor = typename Master_matrix::Entry_constructor;
64
65 public:
66 using iterator = boost::indirect_iterator<typename Column_support::iterator>;
67 using const_iterator = boost::indirect_iterator<typename Column_support::const_iterator>;
68 using reverse_iterator = boost::indirect_iterator<typename Column_support::reverse_iterator>;
69 using const_reverse_iterator = boost::indirect_iterator<typename Column_support::const_reverse_iterator>;
70
71 List_column(Column_settings* colSettings = nullptr);
72 template <class Container = typename Master_matrix::Boundary>
73 List_column(const Container& nonZeroRowIndices, Column_settings* colSettings);
74 template <class Container = typename Master_matrix::Boundary, class Row_container>
75 List_column(Index columnIndex,
76 const Container& nonZeroRowIndices,
77 Row_container* rowContainer,
78 Column_settings* colSettings);
79 template <class Container = typename Master_matrix::Boundary>
80 List_column(const Container& nonZeroChainRowIndices, Dimension dimension, Column_settings* colSettings);
81 template <class Container = typename Master_matrix::Boundary, class Row_container>
82 List_column(Index columnIndex,
83 const Container& nonZeroChainRowIndices,
84 Dimension dimension,
85 Row_container* rowContainer,
86 Column_settings* colSettings);
87 List_column(const List_column& column, Column_settings* colSettings = nullptr);
88 template <class Row_container>
89 List_column(const List_column& column,
90 Index columnIndex,
91 Row_container* rowContainer,
92 Column_settings* colSettings = nullptr);
93 List_column(List_column&& column) noexcept;
94 ~List_column();
95
96 std::vector<Field_element> get_content(int columnLength = -1) const;
97 bool is_non_zero(ID_index rowIndex) const;
98 bool is_empty() const;
99 std::size_t size() const;
100
101 template <class Row_index_map>
102 void reorder(const Row_index_map& valueMap,
103 [[maybe_unused]] Index columnIndex = Master_matrix::template get_null_value<Index>());
104 void clear();
105 void clear(ID_index rowIndex);
106
107 ID_index get_pivot() const;
108 Field_element get_pivot_value() const;
109
110 iterator begin() noexcept;
111 const_iterator begin() const noexcept;
112 iterator end() noexcept;
113 const_iterator end() const noexcept;
114 reverse_iterator rbegin() noexcept;
115 const_reverse_iterator rbegin() const noexcept;
116 reverse_iterator rend() noexcept;
117 const_reverse_iterator rend() const noexcept;
118
119 template <class Entry_range>
120 List_column& operator+=(const Entry_range& column);
121 List_column& operator+=(List_column& column);
122
123 List_column& operator*=(unsigned int v);
124
125 // this = v * this + column
126 template <class Entry_range>
127 List_column& multiply_target_and_add(const Field_element& val, const Entry_range& column);
128 List_column& multiply_target_and_add(const Field_element& val, List_column& column);
129 // this = this + column * v
130 template <class Entry_range>
131 List_column& multiply_source_and_add(const Entry_range& column, const Field_element& val);
132 List_column& multiply_source_and_add(List_column& column, const Field_element& val);
133
134 void push_back(const Entry& entry);
135
136 friend bool operator==(const List_column& c1, const List_column& c2) {
137 if (&c1 == &c2) return true;
138
139 auto it1 = c1.column_.begin();
140 auto it2 = c2.column_.begin();
141 if (c1.column_.size() != c2.column_.size()) return false;
142 while (it1 != c1.column_.end() && it2 != c2.column_.end()) {
143 if constexpr (Master_matrix::Option_list::is_z2) {
144 if ((*it1)->get_row_index() != (*it2)->get_row_index()) return false;
145 } else {
146 if ((*it1)->get_row_index() != (*it2)->get_row_index() || (*it1)->get_element() != (*it2)->get_element())
147 return false;
148 }
149 ++it1;
150 ++it2;
151 }
152 return true;
153 }
154
155 friend bool operator<(const List_column& c1, const List_column& c2) {
156 if (&c1 == &c2) return false;
157
158 auto it1 = c1.column_.begin();
159 auto it2 = c2.column_.begin();
160 while (it1 != c1.column_.end() && it2 != c2.column_.end()) {
161 if ((*it1)->get_row_index() != (*it2)->get_row_index()) return (*it1)->get_row_index() < (*it2)->get_row_index();
162 if constexpr (!Master_matrix::Option_list::is_z2) {
163 if ((*it1)->get_element() != (*it2)->get_element()) return (*it1)->get_element() < (*it2)->get_element();
164 }
165 ++it1;
166 ++it2;
167 }
168 return it2 != c2.column_.end();
169 }
170
171 // Disabled with row access.
172 List_column& operator=(const List_column& other);
173
174 friend void swap(List_column& col1, List_column& col2) {
175 swap(static_cast<typename Master_matrix::Row_access_option&>(col1),
176 static_cast<typename Master_matrix::Row_access_option&>(col2));
177 swap(static_cast<typename Master_matrix::Column_dimension_option&>(col1),
178 static_cast<typename Master_matrix::Column_dimension_option&>(col2));
179 swap(static_cast<typename Master_matrix::Chain_column_option&>(col1),
180 static_cast<typename Master_matrix::Chain_column_option&>(col2));
181 col1.column_.swap(col2.column_);
182 std::swap(col1.operators_, col2.operators_);
183 std::swap(col1.entryPool_, col2.entryPool_);
184 }
185
186 private:
187 using RA_opt = typename Master_matrix::Row_access_option;
188 using Dim_opt = typename Master_matrix::Column_dimension_option;
189 using Chain_opt = typename Master_matrix::Chain_column_option;
190
191 Column_support column_;
192 Field_operators* operators_;
193 Entry_constructor* entryPool_;
194
195 template <class Column, class Entry_iterator, typename F1, typename F2, typename F3, typename F4>
196 friend void _generic_merge_entry_to_column(Column& targetColumn,
197 Entry_iterator& itSource,
198 typename Column::Column_support::iterator& itTarget,
199 F1&& process_target,
200 F2&& process_source,
201 F3&& update_target1,
202 F4&& update_target2,
203 bool& pivotIsZeroed);
204 template <class Column, class Entry_range, typename F1, typename F2, typename F3, typename F4, typename F5>
205 friend bool _generic_add_to_column(const Entry_range& source,
206 Column& targetColumn,
207 F1&& process_target,
208 F2&& process_source,
209 F3&& update_target1,
210 F4&& update_target2,
211 F5&& finish_target);
212 template <class Column, class Entry_range>
213 friend bool _add_to_column(const Entry_range& source, Column& targetColumn);
214 template <class Column, class Entry_range>
215 friend bool _multiply_target_and_add_to_column(const typename Column::Field_element& val,
216 const Entry_range& source,
217 Column& targetColumn);
218 template <class Column, class Entry_range>
219 friend bool _multiply_source_and_add_to_column(const typename Column::Field_element& val,
220 const Entry_range& source,
221 Column& targetColumn);
222
223 void _delete_entry(typename Column_support::iterator& it);
224 Entry* _insert_entry(const Field_element& value,
225 ID_index rowIndex,
226 const typename Column_support::iterator& position);
227 void _insert_entry(ID_index rowIndex, const typename Column_support::iterator& position);
228 void _update_entry(const Field_element& value, ID_index rowIndex, const typename Column_support::iterator& position);
229 void _update_entry(ID_index rowIndex, const typename Column_support::iterator& position);
230 template <class Entry_range>
231 bool _add(const Entry_range& column);
232 template <class Entry_range>
233 bool _multiply_target_and_add(const Field_element& val, const Entry_range& column);
234 template <class Entry_range>
235 bool _multiply_source_and_add(const Entry_range& column, const Field_element& val);
236};
237
238template <class Master_matrix>
239inline List_column<Master_matrix>::List_column(Column_settings* colSettings)
240 : RA_opt(),
241 Dim_opt(),
242 Chain_opt(),
243 operators_(nullptr),
244 entryPool_(colSettings == nullptr ? nullptr : &(colSettings->entryConstructor))
245{
246 if (operators_ == nullptr && entryPool_ == nullptr)
247 return; // to allow default constructor which gives a dummy column
248 if constexpr (!Master_matrix::Option_list::is_z2) {
249 operators_ = &(colSettings->operators);
250 }
251}
252
253template <class Master_matrix>
254template <class Container>
255inline List_column<Master_matrix>::List_column(const Container& nonZeroRowIndices, Column_settings* colSettings)
256 : RA_opt(),
257 Dim_opt(nonZeroRowIndices.size() == 0 ? 0 : nonZeroRowIndices.size() - 1),
258 Chain_opt(),
259 column_(nonZeroRowIndices.size()),
260 operators_(nullptr),
261 entryPool_(&(colSettings->entryConstructor))
262{
263 static_assert(!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type,
264 "Constructor not available for chain columns, please specify the dimension of the chain.");
265
266 auto it = column_.begin();
267 if constexpr (Master_matrix::Option_list::is_z2) {
268 for (ID_index id : nonZeroRowIndices) {
269 _update_entry(id, it++);
270 }
271 } else {
272 operators_ = &(colSettings->operators);
273 for (const auto& p : nonZeroRowIndices) {
274 _update_entry(operators_->get_value(p.second), p.first, it++);
275 }
276 }
277}
278
279template <class Master_matrix>
280template <class Container, class Row_container>
281inline List_column<Master_matrix>::List_column(Index columnIndex,
282 const Container& nonZeroRowIndices,
283 Row_container* rowContainer,
284 Column_settings* colSettings)
285 : RA_opt(columnIndex, rowContainer),
286 Dim_opt(nonZeroRowIndices.size() == 0 ? 0 : nonZeroRowIndices.size() - 1),
287 Chain_opt([&] {
288 if constexpr (Master_matrix::Option_list::is_z2) {
289 return nonZeroRowIndices.begin() == nonZeroRowIndices.end()
290 ? Master_matrix::template get_null_value<ID_index>()
291 : *std::prev(nonZeroRowIndices.end());
292 } else {
293 return nonZeroRowIndices.begin() == nonZeroRowIndices.end()
294 ? Master_matrix::template get_null_value<ID_index>()
295 : std::prev(nonZeroRowIndices.end())->first;
296 }
297 }()),
298 column_(nonZeroRowIndices.size()),
299 operators_(nullptr),
300 entryPool_(&(colSettings->entryConstructor))
301{
302 static_assert(!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type,
303 "Constructor not available for chain columns, please specify the dimension of the chain.");
304
305 auto it = column_.begin();
306 if constexpr (Master_matrix::Option_list::is_z2) {
307 for (ID_index id : nonZeroRowIndices) {
308 _update_entry(id, it++);
309 }
310 } else {
311 operators_ = &(colSettings->operators);
312 for (const auto& p : nonZeroRowIndices) {
313 _update_entry(operators_->get_value(p.second), p.first, it++);
314 }
315 }
316}
317
318template <class Master_matrix>
319template <class Container>
320inline List_column<Master_matrix>::List_column(const Container& nonZeroRowIndices,
321 Dimension dimension,
322 Column_settings* colSettings)
323 : RA_opt(),
324 Dim_opt(dimension),
325 Chain_opt([&] {
326 if constexpr (Master_matrix::Option_list::is_z2) {
327 return nonZeroRowIndices.begin() == nonZeroRowIndices.end()
328 ? Master_matrix::template get_null_value<ID_index>()
329 : *std::prev(nonZeroRowIndices.end());
330 } else {
331 return nonZeroRowIndices.begin() == nonZeroRowIndices.end()
332 ? Master_matrix::template get_null_value<ID_index>()
333 : std::prev(nonZeroRowIndices.end())->first;
334 }
335 }()),
336 column_(nonZeroRowIndices.size()),
337 operators_(nullptr),
338 entryPool_(&(colSettings->entryConstructor))
339{
340 auto it = column_.begin();
341 if constexpr (Master_matrix::Option_list::is_z2) {
342 for (ID_index id : nonZeroRowIndices) {
343 _update_entry(id, it++);
344 }
345 } else {
346 operators_ = &(colSettings->operators);
347 for (const auto& p : nonZeroRowIndices) {
348 _update_entry(operators_->get_value(p.second), p.first, it++);
349 }
350 }
351}
352
353template <class Master_matrix>
354template <class Container, class Row_container>
355inline List_column<Master_matrix>::List_column(Index columnIndex,
356 const Container& nonZeroRowIndices,
357 Dimension dimension,
358 Row_container* rowContainer,
359 Column_settings* colSettings)
360 : RA_opt(columnIndex, rowContainer),
361 Dim_opt(dimension),
362 Chain_opt([&] {
363 if constexpr (Master_matrix::Option_list::is_z2) {
364 return nonZeroRowIndices.begin() == nonZeroRowIndices.end()
365 ? Master_matrix::template get_null_value<ID_index>()
366 : *std::prev(nonZeroRowIndices.end());
367 } else {
368 return nonZeroRowIndices.begin() == nonZeroRowIndices.end()
369 ? Master_matrix::template get_null_value<ID_index>()
370 : std::prev(nonZeroRowIndices.end())->first;
371 }
372 }()),
373 column_(nonZeroRowIndices.size()),
374 operators_(nullptr),
375 entryPool_(&(colSettings->entryConstructor))
376{
377 auto it = column_.begin();
378 if constexpr (Master_matrix::Option_list::is_z2) {
379 for (ID_index id : nonZeroRowIndices) {
380 _update_entry(id, it++);
381 }
382 } else {
383 operators_ = &(colSettings->operators);
384 for (const auto& p : nonZeroRowIndices) {
385 _update_entry(operators_->get_value(p.second), p.first, it++);
386 }
387 }
388}
389
390template <class Master_matrix>
391inline List_column<Master_matrix>::List_column(const List_column& column, Column_settings* colSettings)
392 : RA_opt(),
393 Dim_opt(static_cast<const Dim_opt&>(column)),
394 Chain_opt(static_cast<const Chain_opt&>(column)),
395 column_(column.column_.size()),
396 operators_(colSettings == nullptr ? column.operators_ : nullptr),
397 entryPool_(colSettings == nullptr ? column.entryPool_ : &(colSettings->entryConstructor))
398{
399 static_assert(!Master_matrix::Option_list::has_row_access,
400 "Simple copy constructor not available when row access option enabled. Please specify the new column "
401 "index and the row container.");
402
403 if constexpr (!Master_matrix::Option_list::is_z2) {
404 if (colSettings != nullptr) operators_ = &(colSettings->operators);
405 }
406
407 auto it = column_.begin();
408 for (const Entry* entry : column.column_) {
409 if constexpr (Master_matrix::Option_list::is_z2) {
410 _update_entry(entry->get_row_index(), it++);
411 } else {
412 _update_entry(entry->get_element(), entry->get_row_index(), it++);
413 }
414 }
415}
416
417template <class Master_matrix>
418template <class Row_container>
419inline List_column<Master_matrix>::List_column(const List_column& column,
420 Index columnIndex,
421 Row_container* rowContainer,
422 Column_settings* colSettings)
423 : RA_opt(columnIndex, rowContainer),
424 Dim_opt(static_cast<const Dim_opt&>(column)),
425 Chain_opt(static_cast<const Chain_opt&>(column)),
426 column_(column.column_.size()),
427 operators_(colSettings == nullptr ? column.operators_ : nullptr),
428 entryPool_(colSettings == nullptr ? column.entryPool_ : &(colSettings->entryConstructor))
429{
430 if constexpr (!Master_matrix::Option_list::is_z2) {
431 if (colSettings != nullptr) operators_ = &(colSettings->operators);
432 }
433
434 auto it = column_.begin();
435 for (const Entry* entry : column.column_) {
436 if constexpr (Master_matrix::Option_list::is_z2) {
437 _update_entry(entry->get_row_index(), it++);
438 } else {
439 _update_entry(entry->get_element(), entry->get_row_index(), it++);
440 }
441 }
442}
443
444template <class Master_matrix>
445inline List_column<Master_matrix>::List_column(List_column&& column) noexcept
446 : RA_opt(std::move(static_cast<RA_opt&>(column))),
447 Dim_opt(std::move(static_cast<Dim_opt&>(column))),
448 Chain_opt(std::move(static_cast<Chain_opt&>(column))),
449 column_(std::move(column.column_)),
450 operators_(std::exchange(column.operators_, nullptr)),
451 entryPool_(std::exchange(column.entryPool_, nullptr))
452{}
453
454template <class Master_matrix>
455inline List_column<Master_matrix>::~List_column()
456{
457 for (auto* entry : column_) {
458 if constexpr (Master_matrix::Option_list::has_row_access) RA_opt::unlink(entry);
459 entryPool_->destroy(entry);
460 }
461}
462
463template <class Master_matrix>
464inline std::vector<typename List_column<Master_matrix>::Field_element> List_column<Master_matrix>::get_content(
465 int columnLength) const
466{
467 if (columnLength < 0 && column_.size() > 0)
468 columnLength = column_.back()->get_row_index() + 1;
469 else if (columnLength < 0)
470 return std::vector<Field_element>();
471
472 std::vector<Field_element> container(columnLength, 0);
473 for (auto it = column_.begin(); it != column_.end() && (*it)->get_row_index() < static_cast<ID_index>(columnLength);
474 ++it) {
475 if constexpr (Master_matrix::Option_list::is_z2) {
476 container[(*it)->get_row_index()] = 1;
477 } else {
478 container[(*it)->get_row_index()] = (*it)->get_element();
479 }
480 }
481 return container;
482}
483
484template <class Master_matrix>
485inline bool List_column<Master_matrix>::is_non_zero(ID_index rowIndex) const
486{
487 // could be changed to dichotomic search as column is ordered by row index,
488 // but I am not sure if it is really worth it as there is no random access
489 // and the columns should not be that long anyway.
490 for (const Entry* entry : column_)
491 if (entry->get_row_index() == rowIndex) return true;
492
493 return false;
494}
495
496template <class Master_matrix>
497inline bool List_column<Master_matrix>::is_empty() const
498{
499 return column_.empty();
500}
501
502template <class Master_matrix>
503inline std::size_t List_column<Master_matrix>::size() const
504{
505 return column_.size();
506}
507
508template <class Master_matrix>
509template <class Row_index_map>
510inline void List_column<Master_matrix>::reorder(const Row_index_map& valueMap, [[maybe_unused]] Index columnIndex)
511{
512 static_assert(!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type,
513 "Method not available for chain columns.");
514
515 for (auto it = column_.begin(); it != column_.end(); ++it) {
516 Entry* entry = *it;
517 if constexpr (Master_matrix::Option_list::has_row_access) {
518 RA_opt::unlink(entry);
519 if (columnIndex != Master_matrix::template get_null_value<Index>()) entry->set_column_index(columnIndex);
520 }
521 entry->set_row_index(valueMap.at(entry->get_row_index()));
522 if constexpr (Master_matrix::Option_list::has_intrusive_rows && Master_matrix::Option_list::has_row_access)
523 RA_opt::insert_entry(entry->get_row_index(), entry);
524 }
525
526 // all entries have to be deleted first, to avoid problem with insertion when row is a set
527 if constexpr (!Master_matrix::Option_list::has_intrusive_rows && Master_matrix::Option_list::has_row_access) {
528 for (auto it = column_.begin(); it != column_.end(); ++it) {
529 Entry* entry = *it;
530 RA_opt::insert_entry(entry->get_row_index(), entry);
531 }
532 }
533
534 column_.sort([](const Entry* c1, const Entry* c2) { return *c1 < *c2; });
535}
536
537template <class Master_matrix>
538inline void List_column<Master_matrix>::clear()
539{
540 static_assert(!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type,
541 "Method not available for chain columns as a base element should not be empty.");
542
543 for (auto* entry : column_) {
544 if constexpr (Master_matrix::Option_list::has_row_access) RA_opt::unlink(entry);
545 entryPool_->destroy(entry);
546 }
547
548 column_.clear();
549}
550
551template <class Master_matrix>
552inline void List_column<Master_matrix>::clear(ID_index rowIndex)
553{
554 static_assert(!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type,
555 "Method not available for chain columns.");
556
557 auto it = column_.begin();
558 while (it != column_.end() && (*it)->get_row_index() != rowIndex) it++;
559 if (it != column_.end()) _delete_entry(it);
560}
561
562template <class Master_matrix>
563inline typename List_column<Master_matrix>::ID_index List_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 useful then?
567
568 if constexpr (Master_matrix::Option_list::is_of_boundary_type) {
569 if (column_.empty()) return Master_matrix::template get_null_value<ID_index>();
570 return column_.back()->get_row_index();
571 } else {
572 return Chain_opt::get_pivot();
573 }
574}
575
576template <class Master_matrix>
577inline typename List_column<Master_matrix>::Field_element List_column<Master_matrix>::get_pivot_value() const
578{
579 static_assert(Master_matrix::isNonBasic,
580 "Method not available for base columns."); // could technically be, but is the notion useful then?
581
582 if constexpr (Master_matrix::Option_list::is_z2) {
583 return 1;
584 } else {
585 if constexpr (Master_matrix::Option_list::is_of_boundary_type) {
586 if (column_.empty()) return 0;
587 return column_.back()->get_element();
588 } else {
589 if (Chain_opt::get_pivot() == Master_matrix::template get_null_value<ID_index>()) return Field_element();
590 for (const Entry* entry : column_) {
591 if (entry->get_row_index() == Chain_opt::get_pivot()) return entry->get_element();
592 }
593 return Field_element(); // should never happen if chain column is used properly
594 }
595 }
596}
597
598template <class Master_matrix>
599inline typename List_column<Master_matrix>::iterator List_column<Master_matrix>::begin() noexcept
600{
601 return column_.begin();
602}
603
604template <class Master_matrix>
605inline typename List_column<Master_matrix>::const_iterator List_column<Master_matrix>::begin() const noexcept
606{
607 return column_.begin();
608}
609
610template <class Master_matrix>
611inline typename List_column<Master_matrix>::iterator List_column<Master_matrix>::end() noexcept
612{
613 return column_.end();
614}
615
616template <class Master_matrix>
617inline typename List_column<Master_matrix>::const_iterator List_column<Master_matrix>::end() const noexcept
618{
619 return column_.end();
620}
621
622template <class Master_matrix>
623inline typename List_column<Master_matrix>::reverse_iterator List_column<Master_matrix>::rbegin() noexcept
624{
625 return column_.rbegin();
626}
627
628template <class Master_matrix>
629inline typename List_column<Master_matrix>::const_reverse_iterator List_column<Master_matrix>::rbegin() const noexcept
630{
631 return column_.rbegin();
632}
633
634template <class Master_matrix>
635inline typename List_column<Master_matrix>::reverse_iterator List_column<Master_matrix>::rend() noexcept
636{
637 return column_.rend();
638}
639
640template <class Master_matrix>
641inline typename List_column<Master_matrix>::const_reverse_iterator List_column<Master_matrix>::rend() const noexcept
642{
643 return column_.rend();
644}
645
646template <class Master_matrix>
647template <class Entry_range>
648inline List_column<Master_matrix>& List_column<Master_matrix>::operator+=(const Entry_range& column)
649{
650 static_assert((!Master_matrix::isNonBasic || std::is_same_v<Entry_range, List_column>),
651 "For boundary columns, the range has to be a column of same type to help ensure the validity of the "
652 "base element."); // could be removed, if we give the responsibility to the user.
653 static_assert((!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type),
654 "For chain columns, the given column cannot be constant.");
655
656 _add(column);
657
658 return *this;
659}
660
661template <class Master_matrix>
662inline List_column<Master_matrix>& List_column<Master_matrix>::operator+=(List_column& column)
663{
664 if constexpr (Master_matrix::isNonBasic && !Master_matrix::Option_list::is_of_boundary_type) {
665 // assumes that the addition never zeros out this column.
666 if (_add(column)) {
667 Chain_opt::swap_pivots(column);
668 Dim_opt::swap_dimension(column);
669 }
670 } else {
671 _add(column);
672 }
673
674 return *this;
675}
676
677template <class Master_matrix>
678inline List_column<Master_matrix>& List_column<Master_matrix>::operator*=(unsigned int v)
679{
680 if constexpr (Master_matrix::Option_list::is_z2) {
681 if (v % 2 == 0) {
682 if constexpr (Master_matrix::isNonBasic && !Master_matrix::Option_list::is_of_boundary_type) {
683 throw std::invalid_argument("A chain column should not be multiplied by 0.");
684 } else {
685 clear();
686 }
687 }
688 } else {
689 Field_element val = operators_->get_value(v);
690
691 if (val == 0u) {
692 if constexpr (Master_matrix::isNonBasic && !Master_matrix::Option_list::is_of_boundary_type) {
693 throw std::invalid_argument("A chain column should not be multiplied by 0.");
694 } else {
695 clear();
696 }
697 return *this;
698 }
699
700 if (val == 1u) return *this;
701
702 for (Entry* entry : column_) {
703 operators_->multiply_inplace(entry->get_element(), val);
704 if constexpr (Master_matrix::Option_list::has_row_access) RA_opt::update_entry(*entry);
705 }
706 }
707
708 return *this;
709}
710
711template <class Master_matrix>
712template <class Entry_range>
713inline List_column<Master_matrix>& List_column<Master_matrix>::multiply_target_and_add(const Field_element& val,
714 const Entry_range& column)
715{
716 static_assert((!Master_matrix::isNonBasic || std::is_same_v<Entry_range, List_column>),
717 "For boundary columns, the range has to be a column of same type to help ensure the validity of the "
718 "base element."); // could be removed, if we give the responsibility to the user.
719 static_assert((!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type),
720 "For chain columns, the given column cannot be constant.");
721
722 if constexpr (Master_matrix::Option_list::is_z2) {
723 if (val) {
724 _add(column);
725 } else {
726 clear();
727 _add(column);
728 }
729 } else {
730 _multiply_target_and_add(val, column);
731 }
732
733 return *this;
734}
735
736template <class Master_matrix>
737inline List_column<Master_matrix>& List_column<Master_matrix>::multiply_target_and_add(const Field_element& val,
738 List_column& column)
739{
740 if constexpr (Master_matrix::isNonBasic && !Master_matrix::Option_list::is_of_boundary_type) {
741 // assumes that the addition never zeros out this column.
742 if constexpr (Master_matrix::Option_list::is_z2) {
743 if (val) {
744 if (_add(column)) {
745 Chain_opt::swap_pivots(column);
746 Dim_opt::swap_dimension(column);
747 }
748 } else {
749 throw std::invalid_argument("A chain column should not be multiplied by 0.");
750 }
751 } else {
752 if (_multiply_target_and_add(val, column)) {
753 Chain_opt::swap_pivots(column);
754 Dim_opt::swap_dimension(column);
755 }
756 }
757 } else {
758 if constexpr (Master_matrix::Option_list::is_z2) {
759 if (val) {
760 _add(column);
761 } else {
762 clear();
763 _add(column);
764 }
765 } else {
766 _multiply_target_and_add(val, column);
767 }
768 }
769
770 return *this;
771}
772
773template <class Master_matrix>
774template <class Entry_range>
775inline List_column<Master_matrix>& List_column<Master_matrix>::multiply_source_and_add(const Entry_range& column,
776 const Field_element& val)
777{
778 static_assert((!Master_matrix::isNonBasic || std::is_same_v<Entry_range, List_column>),
779 "For boundary columns, the range has to be a column of same type to help ensure the validity of the "
780 "base element."); // could be removed, if we give the responsibility to the user.
781 static_assert((!Master_matrix::isNonBasic || Master_matrix::Option_list::is_of_boundary_type),
782 "For chain columns, the given column cannot be constant.");
783
784 if constexpr (Master_matrix::Option_list::is_z2) {
785 if (val) {
786 _add(column);
787 }
788 } else {
789 _multiply_source_and_add(column, val);
790 }
791
792 return *this;
793}
794
795template <class Master_matrix>
796inline List_column<Master_matrix>& List_column<Master_matrix>::multiply_source_and_add(List_column& column,
797 const Field_element& val)
798{
799 if constexpr (Master_matrix::isNonBasic && !Master_matrix::Option_list::is_of_boundary_type) {
800 // assumes that the addition never zeros out this column.
801 if constexpr (Master_matrix::Option_list::is_z2) {
802 if (val) {
803 if (_add(column)) {
804 Chain_opt::swap_pivots(column);
805 Dim_opt::swap_dimension(column);
806 }
807 }
808 } else {
809 if (_multiply_source_and_add(column, val)) {
810 Chain_opt::swap_pivots(column);
811 Dim_opt::swap_dimension(column);
812 }
813 }
814 } else {
815 if constexpr (Master_matrix::Option_list::is_z2) {
816 if (val) {
817 _add(column);
818 }
819 } else {
820 _multiply_source_and_add(column, val);
821 }
822 }
823
824 return *this;
825}
826
827template <class Master_matrix>
828inline void List_column<Master_matrix>::push_back(const Entry& entry)
829{
830 static_assert(Master_matrix::Option_list::is_of_boundary_type, "`push_back` is not available for Chain matrices.");
831
832 GUDHI_CHECK(entry.get_row_index() > get_pivot(), "The new row index has to be higher than the current pivot.");
833
834 if constexpr (Master_matrix::Option_list::is_z2) {
835 _insert_entry(entry.get_row_index(), column_.end());
836 } else {
837 _insert_entry(entry.get_element(), entry.get_row_index(), column_.end());
838 }
839}
840
841template <class Master_matrix>
842inline List_column<Master_matrix>& List_column<Master_matrix>::operator=(const List_column& other)
843{
844 static_assert(!Master_matrix::Option_list::has_row_access, "= assignment not enabled with row access option.");
845
846 Dim_opt::operator=(other);
847 Chain_opt::operator=(other);
848
849 auto tmpPool = entryPool_;
850 entryPool_ = other.entryPool_;
851
852 while (column_.size() > other.column_.size()) {
853 if (column_.back() != nullptr) {
854 if constexpr (Master_matrix::Option_list::has_row_access) RA_opt::unlink(column_.back());
855 tmpPool->destroy(column_.back());
856 }
857 column_.pop_back();
858 }
859
860 column_.resize(other.column_.size(), nullptr);
861 auto it = column_.begin();
862 for (const Entry* entry : other.column_) {
863 if (*it != nullptr) {
864 if constexpr (Master_matrix::Option_list::has_row_access) RA_opt::unlink(*it);
865 tmpPool->destroy(*it);
866 }
867 if constexpr (Master_matrix::Option_list::is_z2) {
868 _update_entry(entry->get_row_index(), it++);
869 } else {
870 _update_entry(entry->get_element(), entry->get_row_index(), it++);
871 }
872 }
873
874 operators_ = other.operators_;
875
876 return *this;
877}
878
879template <class Master_matrix>
880inline void List_column<Master_matrix>::_delete_entry(typename Column_support::iterator& it)
881{
882 if constexpr (Master_matrix::Option_list::has_row_access) RA_opt::unlink(*it);
883 entryPool_->destroy(*it);
884 it = column_.erase(it);
885}
886
887template <class Master_matrix>
888inline typename List_column<Master_matrix>::Entry* List_column<Master_matrix>::_insert_entry(
889 const Field_element& value,
890 ID_index rowIndex,
891 const typename Column_support::iterator& position)
892{
893 if constexpr (Master_matrix::Option_list::has_row_access) {
894 Entry* newEntry = entryPool_->construct(RA_opt::columnIndex_, rowIndex);
895 newEntry->set_element(value);
896 column_.insert(position, newEntry);
897 RA_opt::insert_entry(rowIndex, newEntry);
898 return newEntry;
899 } else {
900 Entry* newEntry = entryPool_->construct(rowIndex);
901 newEntry->set_element(value);
902 column_.insert(position, newEntry);
903 return newEntry;
904 }
905}
906
907template <class Master_matrix>
908inline void List_column<Master_matrix>::_insert_entry(ID_index rowIndex,
909 const typename Column_support::iterator& position)
910{
911 if constexpr (Master_matrix::Option_list::has_row_access) {
912 Entry* newEntry = entryPool_->construct(RA_opt::columnIndex_, rowIndex);
913 column_.insert(position, newEntry);
914 RA_opt::insert_entry(rowIndex, newEntry);
915 } else {
916 Entry* newEntry = entryPool_->construct(rowIndex);
917 column_.insert(position, newEntry);
918 }
919}
920
921template <class Master_matrix>
922inline void List_column<Master_matrix>::_update_entry(const Field_element& value,
923 ID_index rowIndex,
924 const typename Column_support::iterator& position)
925{
926 if constexpr (Master_matrix::Option_list::has_row_access) {
927 *position = entryPool_->construct(RA_opt::columnIndex_, rowIndex);
928 (*position)->set_element(value);
929 RA_opt::insert_entry(rowIndex, *position);
930 } else {
931 *position = entryPool_->construct(rowIndex);
932 (*position)->set_element(value);
933 }
934}
935
936template <class Master_matrix>
937inline void List_column<Master_matrix>::_update_entry(ID_index rowIndex,
938 const typename Column_support::iterator& position)
939{
940 if constexpr (Master_matrix::Option_list::has_row_access) {
941 *position = entryPool_->construct(RA_opt::columnIndex_, rowIndex);
942 RA_opt::insert_entry(rowIndex, *position);
943 } else {
944 *position = entryPool_->construct(rowIndex);
945 }
946}
947
948template <class Master_matrix>
949template <class Entry_range>
950inline bool List_column<Master_matrix>::_add(const Entry_range& column)
951{
952 if (column.begin() == column.end()) return false;
953 if (column_.empty()) { // chain should never enter here.
954 column_.resize(column.size());
955 auto it = column_.begin();
956 for (const Entry& entry : column) {
957 if constexpr (Master_matrix::Option_list::is_z2) {
958 _update_entry(entry.get_row_index(), it++);
959 } else {
960 _update_entry(entry.get_element(), entry.get_row_index(), it++);
961 }
962 }
963 return true;
964 }
965
966 return _add_to_column(column, *this);
967}
968
969template <class Master_matrix>
970template <class Entry_range>
971inline bool List_column<Master_matrix>::_multiply_target_and_add(const Field_element& val, const Entry_range& column)
972{
973 return _multiply_target_and_add_to_column(val, column, *this);
974}
975
976template <class Master_matrix>
977template <class Entry_range>
978inline bool List_column<Master_matrix>::_multiply_source_and_add(const Entry_range& column, const Field_element& val)
979{
980 return _multiply_source_and_add_to_column(val, column, *this);
981}
982
983} // namespace persistence_matrix
984} // namespace Gudhi
985
994template <class Master_matrix>
995struct std::hash<Gudhi::persistence_matrix::List_column<Master_matrix> > {
996 std::size_t operator()(const Gudhi::persistence_matrix::List_column<Master_matrix>& column) const {
997 return Gudhi::persistence_matrix::hash_column(column);
998 }
999};
1000
1001#endif // PM_LIST_COLUMN_H
Gudhi::persistence_matrix::List_column
Column class following the PersistenceMatrixColumn concept.
Definition: list_column.h:50
column_utilities.h
Contains helper methods for column addition and column hasher.
entry_constructors.h
Contains different versions of Gudhi::persistence_matrix::Entry factories.
Gudhi::persistence_matrix::Chain_column_option
Chain_column_extra_properties Chain_column_option
If PersistenceMatrixOptions::is_of_boundary_type is false, and, PersistenceMatrixOptions::has_column_...
Definition: PersistenceMatrixColumn.h:45
Gudhi::persistence_matrix::Row_access_option
Row_access Row_access_option
If PersistenceMatrixOptions::has_row_access is true, then Row_access. Otherwise Dummy_row_access....
Definition: PersistenceMatrixColumn.h:28
Gudhi::persistence_matrix::Column_dimension_option
Column_dimension_holder Column_dimension_option
If PersistenceMatrixOptions::has_column_pairings or PersistenceMatrixOptions::has_vine_update or Pers...
Definition: PersistenceMatrixColumn.h:36
Gudhi
Gudhi namespace.
Definition: SimplicialComplexForAlpha.h:14
std
STL namespace.