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