1 /*
2 * Copyright (C) 2010 Regents of the University of Michigan
3 *
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 3 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #include "IntArray.h"
19 #include "Error.h"
20 #include "Hash.h"
21 #include "Sort.h"
22
23 #include <string.h>
24
25 int IntArray::alloc = 4;
26
IntArray(int start_size)27 IntArray::IntArray(int start_size)
28 {
29 count = start_size;
30 size = (count + alloc) / alloc * alloc;
31 items = new int [size];
32 }
33
IntArray(const IntArray & source)34 IntArray::IntArray(const IntArray & source)
35 {
36 count = source.count;
37 size = source.size;
38 items = new int [size];
39
40 for (int i = 0; i < count; i++)
41 items[i] = source.items[i];
42 }
43
~IntArray()44 IntArray::~IntArray()
45 {
46 delete [] items;
47 }
48
Grow(int new_size)49 void IntArray::Grow(int new_size)
50 {
51 if (new_size > size)
52 {
53 if ((new_size >> 1) >= size)
54 size = (new_size + alloc) / alloc * alloc;
55 else
56 {
57 size = alloc;
58 while (size <= new_size)
59 size *= 2;
60 }
61
62 int * new_items = new int [size];
63 for (int i = 0; i < count; i++)
64 new_items[i] = items[i];
65 delete [] items;
66 items = new_items;
67 }
68 }
69
Append(int value)70 int IntArray::Append(int value)
71 {
72 Grow(count + 1);
73 items[count++] = value;
74 return count;
75 }
76
Append(const IntArray & rhs)77 int IntArray::Append(const IntArray & rhs)
78 {
79 Grow(count + rhs.count);
80 for (int i = 0; i < rhs.count; i++)
81 items[count + i] = rhs.items[i];
82 count += rhs.count;
83 return count;
84 }
85
Set(int value)86 void IntArray::Set(int value)
87 {
88 for (int i = 0; i < count; i++)
89 items[i] = value;
90 }
91
SetSequence(int start,int increment)92 void IntArray::SetSequence(int start, int increment)
93 {
94 for (int i = 0; i < count; i++, start += increment)
95 items[i] = start;
96 }
97
Delete(int index)98 int IntArray::Delete(int index)
99 {
100 count--;
101 if (count - index)
102 memmove(items + index, items + index + 1, sizeof(int) *(count - index));
103 return count;
104 }
105
InsertAt(int index,int value)106 void IntArray::InsertAt(int index, int value)
107 {
108 Grow(count + 1);
109 if (count - index)
110 memmove(items + index + 1, items + index, sizeof(int) *(count - index));
111 items[index] = value;
112 count++;
113 }
114
operator =(const IntArray & rhs)115 IntArray & IntArray::operator = (const IntArray & rhs)
116 {
117 Grow(rhs.count);
118 count = rhs.count;
119 for (int i = 0; i < count; i++)
120 items[i] = rhs.items[i];
121 return *this;
122 }
123
Sum(int start,int end) const124 int IntArray::Sum(int start, int end) const
125 {
126 int result = 0;
127
128 for (int i = start; i <= end; i++)
129 result += items[i];
130
131 return result;
132 }
133
dSum(int start,int end) const134 double IntArray::dSum(int start, int end) const
135 {
136 double result = 0;
137
138 for (int i = start; i <= end; i++)
139 result += items[i];
140
141 return result;
142 }
143
Max(int start,int end) const144 int IntArray::Max(int start, int end) const
145 {
146 if (start >= count) return 0;
147
148 int result = items[start];
149
150 for (int i = start + 1; i <= end; i++)
151 if (result < items[i])
152 result = items[i];
153
154 return result;
155 }
156
Min(int start,int end) const157 int IntArray::Min(int start, int end) const
158 {
159 if (start >= count) return 0;
160
161 int result = items[start];
162
163 for (int i = start + 1; i <= end; i++)
164 if (result > items[i])
165 result = items[i];
166
167 return result;
168 }
169
Find(int value) const170 int IntArray::Find(int value) const
171 {
172 for (int i = 0; i < count; i++)
173 if (value == items[i])
174 return i;
175 return -1;
176 }
177
BinarySearch(int value) const178 int IntArray::BinarySearch(int value) const
179 {
180 int start = 0;
181 int stop = count - 1;
182
183 while (start <= stop)
184 {
185 int mid = (start + stop) / 2;
186
187 if (items[mid] == value)
188 return mid;
189
190 if (items[mid] > value)
191 stop = mid - 1;
192 else
193 start = mid + 1;
194 }
195
196 return -1;
197 }
198
Zero()199 void IntArray::Zero()
200 {
201 for (int i = 0; i < count; i++)
202 items[i] = 0;
203 }
204
Compare(int * a,int * b)205 int IntArray::Compare(int * a, int * b)
206 {
207 return *a - *b;
208 }
209
Sort()210 void IntArray::Sort()
211 {
212 QuickSort(items, count, sizeof(int), COMPAREFUNC Compare);
213 }
214
Sort(IntArray & freeRider)215 void IntArray::Sort(IntArray & freeRider)
216 {
217 QuickSort2(items, freeRider.items, count, sizeof(int), COMPAREFUNC Compare);
218 }
219
220
Reverse()221 void IntArray::Reverse()
222 {
223 for (int i = 0, j = count - 1; i < j; i++, j--)
224 Swap(i, j);
225 }
226
CountIfGreater(int threshold) const227 int IntArray::CountIfGreater(int threshold) const
228 {
229 int result = 0;
230
231 for (int i = 0; i < count; i++)
232 if (items[i] > threshold)
233 result++;
234
235 return result;
236 }
237
CountIfGreaterOrEqual(int treshold) const238 int IntArray::CountIfGreaterOrEqual(int treshold) const
239 {
240 int result = 0;
241
242 for (int i = 0; i < count; i++)
243 if (items[i] >= treshold)
244 result++;
245
246 return result;
247 }
248
Add(int term)249 void IntArray::Add(int term)
250 {
251 for (int i = 0; i < count; i++)
252 items[i] += term;
253 }
254
Multiply(int factor)255 void IntArray::Multiply(int factor)
256 {
257 for (int i = 0; i < count; i++)
258 items[i] *= factor;
259 }
260
Divide(int denominator)261 void IntArray::Divide(int denominator)
262 {
263 for (int i = 0; i < count; i++)
264 items[i] /= denominator;
265 }
266
Stack(const IntArray & a)267 void IntArray::Stack(const IntArray & a)
268 {
269 int end = count;
270
271 Dimension(count + a.count);
272
273 for (int i = 0; i < a.count; i++)
274 items[i + end] = a[i];
275 }
276
operator ==(const IntArray & rhs) const277 bool IntArray::operator == (const IntArray & rhs) const
278 {
279 if (count != rhs.count)
280 return false;
281
282 for (int i = 0; i < rhs.count; i++)
283 if (items[i] != rhs.items[i])
284 return false;
285
286 return true;
287 }
288
operator !=(const IntArray & rhs) const289 bool IntArray::operator != (const IntArray & rhs) const
290 {
291 return !(*this == rhs);
292 }
293
294 // Check if all values are in ascending or descending order
295 //
296
isAscending()297 bool IntArray::isAscending()
298 {
299 for (int i = 1; i < count; i++)
300 if (items[i] < items[i - 1])
301 return false;
302 return true;
303 }
304
isDescending()305 bool IntArray::isDescending()
306 {
307 for (int i = 1; i < count; i++)
308 if (items[i] > items[i - 1])
309 return false;
310 return true;
311 }
312
Add(const IntArray & v)313 void IntArray::Add(const IntArray & v)
314 {
315 if (Length() != v.Length())
316 error("IntArray::Add - vectors have different lengths\n"
317 "IntArrays - Left[%d] += Right[%d] ",
318 Length(), v.Length());
319
320 for (int i = 0; i < Length(); i++)
321 items[i] += v[i];
322 }
323
InnerProduct(IntArray & v)324 int IntArray::InnerProduct(IntArray & v)
325 {
326 if (Length() != v.Length())
327 error("IntArray::InnerProduct - vectors have different dimensions\n"
328 "IntArrays - Left[%d] * Right[%d] ",
329 Length(), v.Length());
330
331 int sum = 0;
332 for (int i = 0; i < Length(); i++)
333 sum += items[i] * v[i];
334
335 return sum;
336 }
337
Swap(IntArray & rhs)338 void IntArray::Swap(IntArray & rhs)
339 {
340 int * temp = rhs.items;
341 rhs.items = items;
342 items = temp;
343
344 int swap = rhs.count;
345 rhs.count = count;
346 count = swap;
347
348 swap = rhs.size;
349 rhs.size = size;
350 size = swap;
351 }
352
Print(FILE * output)353 void IntArray::Print(FILE * output)
354 {
355 Print(output, "Array of Integers");
356 }
357
Print(FILE * output,const char * label)358 void IntArray::Print(FILE * output, const char * label)
359 {
360 fprintf(output, "%s [%d elements]: ", label, count);
361
362 for (int i = 0; i < count; i++)
363 fprintf(output, "%d ", items[i]);
364
365 fprintf(output, "\n");
366 }
367
PushIfNew(int value)368 void IntArray::PushIfNew(int value)
369 {
370 for (int i = 0; i < count; i++)
371 if (items[i] == value)
372 return;
373
374 Push(value);
375 }
376
Product()377 int IntArray::Product()
378 {
379 int product = 1;
380
381 for (int i = 0; i < count; i++)
382 product *= items[i];
383
384 return product;
385 }
386
DoubleProduct()387 double IntArray::DoubleProduct()
388 {
389 double product = 1.0;
390
391 for (int i = 0; i < count; i++)
392 product *= items[i];
393
394 return product;
395 }
396
Hash(int initval)397 int IntArray::Hash(int initval)
398 {
399 return hash((unsigned char *) items, sizeof(int) * count, initval);
400 }
401
SumProduct(const IntArray & weight) const402 int IntArray::SumProduct(const IntArray & weight) const
403 {
404 if (count != weight.count)
405 error("IntArray::SumProduct called with different sized arrays\n");
406
407 int sum = 0;
408 for (int i = 0; i < count; i++)
409 sum += items[i] * weight[i];
410
411 return sum;
412 }
413
dSumProduct(const IntArray & weight) const414 double IntArray::dSumProduct(const IntArray & weight) const
415 {
416 if (count != weight.count)
417 error("IntArray::dSumProduct called with different sized arrays\n");
418
419 double sum = 0.0;
420 for (int i = 0; i < count; i++)
421 sum += items[i] * weight[i];
422
423 return sum;
424 }
425
426