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