LIBINT  2.6.0
intpart_iter.h
1 /*
2  * Copyright (C) 2004-2019 Edward F. Valeev
3  *
4  * This file is part of Libint.
5  *
6  * Libint is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * Libint is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public License
17  * along with Libint. If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 #ifndef _libint2_include_libint2_util_intpartiter_h_
22 #define _libint2_include_libint2_util_intpartiter_h_
23 
24 #include <array>
25 #include <cassert>
26 #include <cstdint>
27 #include <iterator>
28 #include <limits>
29 #include <numeric>
30 #include <stdexcept>
31 #include <type_traits>
32 #include <vector>
33 
34 namespace libint2 {
35 
36 namespace detail {
37 template <class C>
38 constexpr auto size(const C& c) -> decltype(c.size()) {
39  return c.size();
40 }
41 
42 template <class T, std::size_t N>
43 constexpr std::size_t size(const T (&array)[N]) noexcept {
44  return N;
45 }
46 
47 template <typename T>
49 template <typename T, size_t N>
50 struct has_static_size<std::array<T, N>> : std::true_type {};
51 template <typename T, size_t N>
52 struct has_static_size<T[N]> : std::true_type {};
53 template <typename T>
54 struct has_static_size : std::false_type {};
55 
56 template <typename T, typename A>
57 void resize(std::vector<T,A>& x, std::size_t n) {
58  x.resize(n);
59 }
60 
61 } // namespace detail
62 
71 template <typename Sequence,
72  typename = typename std::enable_if<std::numeric_limits<
73  typename Sequence::value_type>::is_integer>::type>
75  public:
76  typedef const Sequence& value_type;
77  typedef typename Sequence::value_type integer_type;
78  typedef typename std::make_unsigned<integer_type>::type unsigned_integer_type;
79  typedef typename Sequence::size_type size_type;
80 
83  template <typename Seq = Sequence>
85  unsigned_integer_type n,
86  typename std::enable_if<detail::has_static_size<Seq>::value>::type* = nullptr)
87  : n_(n) {
88  assert(n >= 0);
89  // initialize partition_
90  std::fill(std::begin(partition_), std::end(partition_), integer_type(0));
91  partition_[0] = n_;
92  }
93 
96  FixedOrderedIntegerPartitionIterator(unsigned_integer_type n, size_type k)
97  : n_(n) {
98  assert(n >= 0);
99  assert(k > 0);
100  // initialize partition_
101  detail::resize(partition_, k);
102  std::fill(std::begin(partition_), std::end(partition_), integer_type(0));
103  partition_[0] = n_;
104  }
105 
107  intmax_t range_size() const {
108  intmax_t result = 1;
109  const auto partition_size = detail::size(partition_);
110  for (intmax_t d = 1; d <= n_; ++d) {
111  result *= (partition_size + d - 1);
112  result /= d;
113  }
114  return result;
115  }
116 
117  value_type operator*() const { return partition_; }
118 
119  const Sequence* operator->() const { return &partition_; }
120 
122  operator bool() const { return this->last(); }
123 
125  bool last() const { return last(&partition_[0], detail::size(partition_)); }
126 
129  void next() { next(&partition_[0], detail::size(partition_)); }
130 
132  template <typename Seq>
133  static intmax_t rank(const Seq& part) {
134  auto k = detail::size(part);
135  decltype(k) count = 0;
136  intmax_t result = 0;
137  auto part_i = part[0];
138  for (decltype(k) i = 0; i != k;) {
139  if (part_i > 0) {
140  ++count;
141  --part_i;
142  intmax_t contrib_i = 1;
143  for (decltype(count) c = 0; c != count; ++c) {
144  contrib_i *= (i + c);
145  result /= (c + 1);
146  }
147  result += contrib_i;
148  }
149  if (part_i == 0) {
150  ++i;
151  part_i = part[i];
152  }
153  }
154  return result;
155  }
156 
157  private:
158  unsigned long n_;
159  Sequence partition_;
160 
161  static void first(integer_type* partition, size_type size) {
162  assert(size > 0);
163  const auto n =
164  std::accumulate(partition, partition + size, unsigned_integer_type(0));
165  std::fill(partition, partition + size, integer_type(0));
166  partition[0] = n;
167  }
168  static bool last(const integer_type* partition, size_type size) {
169  assert(size > 0);
170  const auto n = std::accumulate(partition, partition + size, 0u);
171  return partition[size - 1] == n;
172  }
173  static void next(integer_type* partition, size_type size) {
174  assert(size > 0);
175  if (size == 1) return;
176  if (last(partition + 1, size - 1)) {
177  assert(partition[0] != 0u);
178  --partition[0];
179  ++partition[1];
180  first(partition + 1, size - 1);
181  } else {
182  next(partition + 1, size - 1);
183  }
184  }
185 };
186 
187 } // namespace libint2
188 
189 #endif /* header guard */
intmax_t range_size() const
Definition: intpart_iter.h:107
static intmax_t rank(const Seq &part)
returns the rank (index) of partition part in the partition range
Definition: intpart_iter.h:133
bool last() const
Definition: intpart_iter.h:125
void next()
update to the next partition in the range
Definition: intpart_iter.h:129
Defaults definitions for various parameters assumed by Libint.
Definition: algebra.cc:24
Iterates over all partitions of a non-negative integer into nonnegative integers in reverse lexicog...
Definition: intpart_iter.h:74
FixedOrderedIntegerPartitionIterator(unsigned_integer_type n, typename std::enable_if< detail::has_static_size< Seq >::value >::type *=nullptr)
Definition: intpart_iter.h:84
Definition: intpart_iter.h:48
FixedOrderedIntegerPartitionIterator(unsigned_integer_type n, size_type k)
Definition: intpart_iter.h:96