1 /* 2 * Copyright © 2004 Ondra Kamenik 3 * Copyright © 2019 Dynare Team 4 * 5 * This file is part of Dynare. 6 * 7 * Dynare is free software: you can redistribute it and/or modify 8 * it under the terms of the GNU General Public License as published by 9 * the Free Software Foundation, either version 3 of the License, or 10 * (at your option) any later version. 11 * 12 * Dynare is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with Dynare. If not, see <http://www.gnu.org/licenses/>. 19 */ 20 21 // Integer sequence. 22 23 /* Here we define an auxiliary abstraction for a sequence of integers. The 24 basic functionality is to hold an ordered sequence of integers with 25 constant length. We prefer using this simple class rather than 26 std::vector<int> since it is more efficient for our purposes. 27 28 The class is used in index of a tensor, in symmetry definition, in 29 Kronecker product dimensions, or as a class of an equivalence. The 30 latter case is not ordered, but we always order equivalence classes in 31 order to ensure unique representativeness. For almost all cases we 32 need the integer sequence to be ordered (sort), or monotonize (indices 33 of folded tensors), or partially monotonize (indices of folded tensors 34 not fully symmetric), or calculate a product of all members or only of 35 a part (used in Kronecker product dimensions). When we calculate 36 offsets in folded tensors, we need to obtain a number of the same 37 items in the front (getPrefixLength()), and also to add some integer 38 number to all items. 39 40 Also, we need to construct a subsequence of a sequence. */ 41 42 #ifndef INT_SEQUENCE_H 43 #define INT_SEQUENCE_H 44 45 #include <vector> 46 #include <algorithm> 47 #include <initializer_list> 48 #include <utility> 49 50 /* The implementation of IntSequence is straightforward. It has a pointer 51 ‘data’, an ‘offset’ integer indicating the beginning of the data relatively 52 to the pointer and a ‘length’ of the sequence. 53 54 WARNING: IntSequence(n) and IntSequence{n} are not the same (parentheses 55 versus braces). The former initializes a sequence of length n, while the 56 latter constructs a sequence of a single element equal to n. This is similar 57 to the behaviour of std::vector. */ 58 59 class Symmetry; 60 class IntSequence 61 { 62 int *data; 63 int length; 64 bool destroy{true}; 65 public: 66 // Constructor allocating a given length of (uninitialized) data IntSequence(int l)67 explicit IntSequence(int l) 68 : data{new int[l]}, length{l} 69 { 70 } 71 // Constructor allocating and then initializing all members to a given number IntSequence(int l,int n)72 IntSequence(int l, int n) 73 : data{new int[l]}, length{l} 74 { 75 std::fill_n(data, length, n); 76 } 77 /* Constructor using an initializer list (gives the contents of the 78 IntSequence, similarly to std::vector) */ IntSequence(std::initializer_list<int> init)79 IntSequence(std::initializer_list<int> init) 80 : data{new int[init.size()]}, 81 length{static_cast<int>(init.size())} 82 { 83 std::copy(init.begin(), init.end(), data); 84 } 85 // Copy constructor IntSequence(const IntSequence & s)86 IntSequence(const IntSequence &s) 87 : data{new int[s.length]}, length{s.length} 88 { 89 std::copy_n(s.data, length, data); 90 } 91 // Move constructor IntSequence(IntSequence && s)92 IntSequence(IntSequence &&s) 93 : data{std::exchange(s.data, nullptr)}, length{std::exchange(s.length, 0)}, 94 destroy{std::exchange(s.destroy, false)} 95 { 96 } 97 // Subsequence constructor (which shares the data pointer) IntSequence(IntSequence & s,int i1,int i2)98 IntSequence(IntSequence &s, int i1, int i2) 99 : data{s.data+i1}, length{i2-i1}, destroy{false} 100 { 101 } 102 // Subsequence constructor (without pointer sharing) IntSequence(const IntSequence & s,int i1,int i2)103 IntSequence(const IntSequence &s, int i1, int i2) 104 : data{new int[i2-i1]}, length{i2-i1} 105 { 106 std::copy_n(s.data+i1, length, data); 107 } 108 /* Unfolds a given integer sequence with respect to a given symmetry. If for 109 example the sequence is (a,b) and the symmetry is (2,3), then the 110 result is (a,a,b,b,b). */ 111 IntSequence unfold(const Symmetry &sy) const; 112 113 /* Constructs a symmetry from the integer sequence (supposed to be ordered) as 114 a symmetry counting successively equal items. For instance the sequence 115 (a,a,a,b,c,c,d,d,d,d) produces symmetry (3,1,2,4). */ 116 Symmetry getSymmetry() const; 117 118 IntSequence &operator=(const IntSequence &s); 119 IntSequence &operator=(IntSequence &&s); ~IntSequence()120 virtual ~IntSequence() 121 { 122 if (destroy) 123 delete[] data; 124 } 125 bool operator==(const IntSequence &s) const; 126 bool operator !=(const IntSequence & s) const127 operator!=(const IntSequence &s) const 128 { 129 return !operator==(s); 130 } 131 int & operator [](int i)132 operator[](int i) 133 { 134 return data[i]; 135 } 136 int operator [](int i) const137 operator[](int i) const 138 { 139 return data[i]; 140 } 141 int size() const142 size() const 143 { 144 return length; 145 } 146 147 /* We provide two orderings. The first operator<() is the linear 148 lexicographic ordering, the second less() is the non-linear Cartesian 149 ordering. */ 150 bool operator<(const IntSequence &s) const; 151 bool operator <=(const IntSequence & s) const152 operator<=(const IntSequence &s) const 153 { 154 return (operator==(s) || operator<(s)); 155 } 156 bool lessEq(const IntSequence &s) const; 157 bool less(const IntSequence &s) const; 158 159 // Inserts an element into an ordered sequence 160 IntSequence insert(int i) const; 161 // Inserts an element at a given position 162 /* For appending at the end, use pos = size() */ 163 IntSequence insert(int i, int pos) const; 164 165 // In-place sort the sequence in increasing order 166 void sort(); 167 168 /* Monotonize the sequence: if an item is less then its predecessor, it is 169 equalized. */ 170 void monotone(); 171 172 /* Partially monotonize the sequence. The partitioning is done by a 173 symmetry. So the subsequence given by the symmetry classes are 174 monotonized. For example, if the symmetry is y²u³, and the 175 IntSequence is (5,3,1,6,4), the result is (5,5,1,6,6). */ 176 void pmonotone(const Symmetry &s); 177 178 179 // Returns the sum of all elements. Useful for symmetries 180 int sum() const; 181 182 /* This returns product of elements between indices i1 (included) and i2 183 (excluded). Useful for Kronecker product dimensions. */ 184 int mult(int i1, int i2) const; 185 186 // Returns the product of all elements 187 int mult() const188 mult() const 189 { 190 return mult(0, length); 191 } 192 void add(int i); 193 void add(int f, const IntSequence &s); 194 195 /* Return the number of identical elements at the beginning of the sequence. */ 196 int getPrefixLength() const; 197 198 /* This returns a number of distinct items in the sequence. It supposes that 199 the sequence is ordered. Returns zero on the empty sequence. */ 200 int getNumDistinct() const; 201 202 /* This returns a maximum of the sequence. If the sequence is empty, it 203 returns the least possible int value. */ 204 int getMax() const; 205 206 bool isPositive() const; 207 bool isConstant() const; 208 bool isSorted() const; 209 210 void print() const; 211 /* ⎛sum(this)⎞ 212 Computes multinomial coefficient: ⎝ this ⎠ 213 (where the lower line consists of the sequence of integers stored by ‘this’) 214 215 WARNING: this operation is destructive; make a copy if you want to keep 216 the original sequence */ 217 int noverseq(); 218 }; 219 220 #endif 221