Basic Polynomial Algebra Subprograms (BPAS)  v. 1.652
interval.h
1 #ifndef _INTERVAL_H_
2 #define _INTERVAL_H_
3
5
6 /**
7  * Data Structure for interval [a, b].
8  */
9 class Interval {
10  public:
11  lfixq left;
12  lfixq right;
13 };
14
15 /**
17  * @res = @a + @b
18  **/
19 inline void intervalAddition(Interval* res, Interval* a, Interval* b) {
20  res->left = a->left + b->left;
21  res->right = a->right + b->right;
22 }
23
24 /**
25  * Interval multiplication
26  * @res = @a * @b
27  **/
28 void intervalMultiplication(Interval* res, Interval* a, Interval* b);
29
30 /** Interval lists for real roots of multivariate polynomials.
31  * i.e. []*..*[], .., []*..*[]
32  **/
33 class Intervals {
34  private:
35  int var; // Number of variates
36  Symbol* names; // Variable names
37  std::vector<Interval> roots; // Roots, using one dimension
38  // to present two dimensions
39  // []*..*[], .., []*..*[]
40  // Each root is in the ascending
41  // order of the weight of variates
42
43  public:
44  /**
45  * Construct intervals
46  *
47  * @param
48  **/
49  Intervals() : var(1) {
50  names = new Symbol[2];
51  names[0] = "1";
52  names[1] = "_1";
53  }
54  /**
55  * Construct intervals with number of variates
56  *
57  * @param v: Number of variates
58  **/
59  Intervals(int v) : var(v) {
60  names = new Symbol[var+1];
61  names[0] = "1";
62  for (int i = 1; i <= var; ++i) {
63  std::ostringstream convert;
64  convert << var - i + 1;
65  names[i] = "_";
66  names[i] += convert.str();
67  }
68  }
69  /**
70  * Copy construct
71  *
72  * @param b: Intervals
73  **/
74  Intervals (const Intervals& b) : var(b.var), roots(b.roots) {
75  names = new Symbol[var+1];
76  std::copy(b.names, b.names+var+1, names);
77  }
78  /**
79  * Destroy intervals
80  *
81  * @param
82  **/
84  delete [] names;
85  roots.clear();
86  }
87  /**
89  *
90  * @param b: Intervals
91  **/
92  inline Intervals& operator= (Intervals b) {
93  if (this != &b) {
94  delete [] names;
95  var = b.var;
96  roots = b.roots;
97  names = new Symbol[var+1];
98  std::copy(b.names, b.names+var+1, names);
99  }
100  return *this;
101  }
102  /**
103  * Get number of variables
104  *
105  * @param
106  **/
107  inline int numberOfVariables() {
108  return var;
109  }
110
111  /**
112  * Get the number of roots
113  *
114  * @param
115  **/
116  inline int numberOfIntervals() {
117  return roots.size() / var;
118  }
119
120  /**
121  * Push an interval to the end of the list
122  *
123  * @param pI: An interval
124  **/
125  inline void pushInterval(Interval pI) {
126  roots.push_back(pI);
127  }
128  /**
129  * Push an interval to the end of the list
130  *
131  * @param l: Interval's left
132  * @param r: Interval's right
133  **/
134  inline void pushInterval(lfixq l, lfixq r) {
135  Interval elem;
136  elem.left = l;
137  elem.right = r;
138  roots.push_back(elem);
139  }
140  inline void pushInterval(double l, double r) {
141  Interval elem;
142  elem.left = l;
143  elem.right = r;
144  roots.push_back(elem);
145  }
146  /**
147  * Pop the last interval
148  *
149  * @param
150  **/
151  inline void popInterval() {
152  if (roots.size())
153  roots.pop_back();
154  }
155  /**
156  * Clear all the intervals
157  *
158  * @param
159  **/
160  inline void clear() {
161  roots.clear();
162  }
163
164  /**
165  * Get a root of a variate
166  *
167  * @param k: Offset of roots
168  * @param l: Offset of variables in an ascending order
169  **/
170  inline Interval* interval(int k, int l=0) {
171  return &roots[k*var+l];
172  }
173  /**
174  * Get a root of variates
175  *
176  * @param k: Offset of roots
177  **/
178  inline Intervals root(int k) {
179  Intervals pIs(var);
180  for (int i = 0; i < var; ++i)
181  pIs.roots.push_back(roots[k*var+i]);
182  return pIs;
183  }
184  /**
185  * Set variable names
186  *
187  * @param xs: Variable names
188  **/
189  inline void setVariableNames (const std::vector<Symbol>& xs) {
190  int ns = xs.size();
191  if (ns >= var) {
192  names[0] = "9";
193  for (int i = var, j = 0; i > 0; --i, ++j)
194  names[i] = xs[j];
195  }
196  else
197  std::cout << "BPAS: warning, not enough variables to set in Intervals." << std::endl;
198  }
199  /**
200  * Copy the k-th root
201  *
202  * @param pIs: A list of roots
203  * @param k: Offset of roots
204  **/
205  void copyFrom(Intervals& pIs, int k);
206  /**
207  * Scale to 2^k
208  *
209  * @param k: The power of 2
210  **/
211  void scale(int k);
212  /**
213  * Scale to that over 2
214  *
215  * @param
216  **/
217  void transformLeft();
218  /**
219  * Scale to that plus 1 and then over 2
220  *
221  * @param
222  **/
223  void transformRight();
224  /**
225  * Negate each interval and re-sort
226  *
227  * @param
228  **/
229  void negate();
230  /**
231  * Merge another intervals into the end of the current one
232  *
233  * @param pIs: A list of intervals
234  **/
235  void concatenate(Intervals& pIs);
236
237  /**
238  * Overload stream operator <<
239  *
240  * @param out: Stream object
241  * @param a: Intervals
242  **/
243  friend std::ostream& operator<< (std::ostream &out, Intervals& a);
244  bool isExactEqual(Intervals& pIs);
245 };
246
247
248 /**
249  * Swap two intervals
250  **/
251 inline void swapInterval(Interval* a, Interval* b) {
252  Interval tmp;
253  tmp.left = a->left;
254  tmp.right = a->right;
255  a->left = b->left;
256  a->right = b->right;
257  b->left = tmp.left;
258  b->right = tmp.right;
259 }
260
261 #endif
Intervals root(int k)
Get a root of variates.
Definition: interval.h:178
int numberOfVariables()
Get number of variables.
Definition: interval.h:107
void setVariableNames(const std::vector< Symbol > &xs)
Set variable names.
Definition: interval.h:189
int numberOfIntervals()
Get the number of roots.
Definition: interval.h:116
Intervals(const Intervals &b)
Copy construct.
Definition: interval.h:74
Intervals(int v)
Construct intervals with number of variates.
Definition: interval.h:59
Data Structure for interval [a, b].
Definition: interval.h:9
Intervals()
Construct intervals.
Definition: interval.h:49
void clear()
Clear all the intervals.
Definition: interval.h:160
void pushInterval(lfixq l, lfixq r)
Push an interval to the end of the list.
Definition: interval.h:134
void pushInterval(Interval pI)
Push an interval to the end of the list.
Definition: interval.h:125
An encapsulation of a mathematical symbol.
Definition: Symbol.hpp:23
void popInterval()
Pop the last interval.
Definition: interval.h:151
Interval * interval(int k, int l=0)
Get a root of a variate.
Definition: interval.h:170
Interval lists for real roots of multivariate polynomials.
Definition: interval.h:33
~Intervals()
Destroy intervals.
Definition: interval.h:83