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