blob: 6bce0cc6bd669f4e302a01ed2c6452ebfbf7697f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
#include "NAWOrderedArray.h"
#include "NAW.h"
#include <iostream>
#include <math.h>
NAWOrderedArray::NAWOrderedArray() { }
NAWOrderedArray::~NAWOrderedArray() { }
int NAWOrderedArray::find(const NAW& naw) const {
unsigned tail = 0, head = _nawCollectionSize; // range is tail to head non-inclusive
unsigned max_attempts = log2(_nawCollectionSize) + 1; // return -1 infinite loop failsafe
for (unsigned x = 0; x < max_attempts; x++) {
unsigned guess = (head + tail) / 2; // take middle index
int diff = _nawCollection[guess]->compareTo(naw);
if (diff > 0) head = guess; // lower half (too high)
else if (diff < 0) tail = guess; // upper half (too low)
else return guess; // index found if compareTo(...) -> 0
}
return -1; // infinite loop failsafe
}
int NAWOrderedArray::add(const NAW& naw) {
int i;
// find insert index
for (i = 0; i < _nawCollectionSize; i++) {
if (_nawCollection[i]->compareTo(naw) > 0) break;
}
// shift elements
for (int k = _nawCollectionSize; k >= i; k--) {
if (k == 0) continue;
// std::cout << "moving [" << k-1 << "] to [" << k << "]" << std::endl;
_nawCollection[k] = _nawCollection[k-1];
}
_nawCollectionSize++;
// std::cout << "inserting into [" << i << "]" << std::endl;
_nawCollection[i] = new NAW(naw);
return i;
}
int NAWOrderedArray::remove(const NAW& naw) {
int i = find(naw);
// shift elements
for (int k = i; k < _nawCollectionSize; k++)
_nawCollection[k] = _nawCollection[k + 1];
_nawCollectionSize--;
return i;
}
int NAWOrderedArray::replace(const NAW& cOld, const NAW& cNew) {
bool opdrachtBeschrijvingIsDuidelijk = false; // true om de array opnieuw te sorteren na vervangen
int i = find(cOld);
if (i < 0) return -1;
if (opdrachtBeschrijvingIsDuidelijk == false) {
_nawCollection[i] = new NAW(cNew);
} else {
remove(cOld);
add(cNew);
}
return i;
}
void NAWOrderedArray::showAll() const {
for (unsigned i = 0; i < _nawCollectionSize; i++)
std::cout << *_nawCollection[i] << std::endl;
}
|