diff options
Diffstat (limited to 'src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutation_iterator.h')
-rw-r--r-- | src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutation_iterator.h | 120 |
1 files changed, 120 insertions, 0 deletions
diff --git a/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutation_iterator.h b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutation_iterator.h new file mode 100644 index 00000000..0f91d41c --- /dev/null +++ b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutation_iterator.h @@ -0,0 +1,120 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): Siargey Kachanovich + * + * Copyright (C) 2019 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#ifndef PERMUTAHEDRAL_REPRESENTATION_PERMUTATION_ITERATOR_H_ +#define PERMUTAHEDRAL_REPRESENTATION_PERMUTATION_ITERATOR_H_ + +#include <cstdlib> // for std::size_t +#include <vector> + +#include <boost/range/iterator_range.hpp> + +namespace Gudhi { + +namespace coxeter_triangulation { + +typedef unsigned uint; + +/** \brief Class that allows the user to generate permutations. + * Based on the optimization of the Heap's algorithm by Sedgewick. + */ +class Permutation_iterator + : public boost::iterator_facade<Permutation_iterator, std::vector<uint> const, boost::forward_traversal_tag> { + using value_t = std::vector<uint>; + + private: + friend class boost::iterator_core_access; + + bool equal(Permutation_iterator const& other) const { return (is_end_ && other.is_end_); } + + value_t const& dereference() const { return value_; } + + void swap_two_indices(std::size_t i, std::size_t j) { + uint t = value_[i]; + value_[i] = value_[j]; + value_[j] = t; + } + + void elementary_increment() { + uint j = 0; + while (d_[j] == j + 1) { + d_[j] = 0; + ++j; + } + if (j == n_ - 1) { + is_end_ = true; + return; + } + uint k = j + 1; + uint x = (k % 2 ? d_[j] : 0); + swap_two_indices(k, x); + ++d_[j]; + } + + void elementary_increment_optim_3() { + if (ct_ != 0) { + --ct_; + swap_two_indices(1 + (ct_ % 2), 0); + } else { + ct_ = 5; + uint j = 2; + while (d_[j] == j + 1) { + d_[j] = 0; + ++j; + } + if (j == n_ - 1) { + is_end_ = true; + return; + } + uint k = j + 1; + uint x = (k % 2 ? d_[j] : 0); + swap_two_indices(k, x); + ++d_[j]; + } + } + + void increment() { + if (optim_3_) + elementary_increment_optim_3(); + else + elementary_increment(); + } + + public: + Permutation_iterator(const uint& n) : value_(n), is_end_(n == 0), optim_3_(n >= 3), n_(n), d_(n), ct_(5) { + for (uint i = 0; i < n; ++i) { + value_[i] = i; + d_[i] = 0; + } + if (n > 0) d_[n - 1] = -1; + } + + // Used for the creating an end iterator + Permutation_iterator() : is_end_(true), n_(0) {} + + void reinitialize() { + if (n_ > 0) is_end_ = false; + } + + private: + value_t value_; // the dereference value + bool is_end_; // is true when the current permutation is the final one + bool optim_3_; // true if n>=3. for n >= 3, the algorithm is optimized + + uint n_; + std::vector<uint> d_; // mix radix digits with radix [2 3 4 ... n-1 (sentinel=-1)] + uint ct_; // counter with values in {0,...,5} used in the n>=3 optimization. +}; + +} // namespace coxeter_triangulation + +} // namespace Gudhi + +#endif |