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