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