libStatGen Software 1
IntArray.cpp
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
25int IntArray::alloc = 4;
26
27IntArray::IntArray(int start_size)
28{
29 count = start_size;
30 size = (count + alloc) / alloc * alloc;
31 items = new int [size];
32}
33
34IntArray::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
44IntArray::~IntArray()
45{
46 delete [] items;
47}
48
49void 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
70int IntArray::Append(int value)
71{
72 Grow(count + 1);
73 items[count++] = value;
74 return count;
75}
76
77int 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
86void IntArray::Set(int value)
87{
88 for (int i = 0; i < count; i++)
89 items[i] = value;
90}
91
92void IntArray::SetSequence(int start, int increment)
93{
94 for (int i = 0; i < count; i++, start += increment)
95 items[i] = start;
96}
97
98int 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
106void 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
115IntArray & 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
124int 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
134double 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
144int 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
157int 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
170int 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
178int 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
199void IntArray::Zero()
200{
201 for (int i = 0; i < count; i++)
202 items[i] = 0;
203}
204
205int IntArray::Compare(int * a, int * b)
206{
207 return *a - *b;
208}
209
210void IntArray::Sort()
211{
212 QuickSort(items, count, sizeof(int), COMPAREFUNC Compare);
213}
214
215void IntArray::Sort(IntArray & freeRider)
216{
217 QuickSort2(items, freeRider.items, count, sizeof(int), COMPAREFUNC Compare);
218}
219
220
221void IntArray::Reverse()
222{
223 for (int i = 0, j = count - 1; i < j; i++, j--)
224 Swap(i, j);
225}
226
227int 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
238int 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
249void IntArray::Add(int term)
250{
251 for (int i = 0; i < count; i++)
252 items[i] += term;
253}
254
255void IntArray::Multiply(int factor)
256{
257 for (int i = 0; i < count; i++)
258 items[i] *= factor;
259}
260
261void IntArray::Divide(int denominator)
262{
263 for (int i = 0; i < count; i++)
264 items[i] /= denominator;
265}
266
267void 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
277bool 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
289bool 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
297bool 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
305bool 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
313void 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
324int 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
338void 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
353void IntArray::Print(FILE * output)
354{
355 Print(output, "Array of Integers");
356}
357
358void 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
368void 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
377int 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
387double 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
397int IntArray::Hash(int initval)
398{
399 return hash((unsigned char *) items, sizeof(int) * count, initval);
400}
401
402int 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
414double 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