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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
#include <iostream>
#include "IntDoubleLinkedList.h"
#include "IntDoubleLink.h"
IntDoubleLinkedList::IntDoubleLinkedList() { }
IntDoubleLinkedList::~IntDoubleLinkedList() { }
void IntDoubleLinkedList::initFirstElement(int value) {
this->head = new IntDoubleLink(value, nullptr, nullptr);
this->tail = this->head;
}
void IntDoubleLinkedList::insertAtStart(int value) {
this->size++;
if (this->size == 1) return initFirstElement(value);
// this->tail->prev is used as the new instance holder
this->tail->prev = new IntDoubleLink(value, nullptr, this->tail);
this->tail->prev->next = this->tail; // yes
this->tail = this->tail->prev;
}
void IntDoubleLinkedList::insertAtEnd(int value) {
this->size++;
if (this->size == 1) return initFirstElement(value);
this->head->next = new IntDoubleLink(value, this->head, nullptr);
this->head->next->prev = this->head;
this->head = this->head->next;
}
bool IntDoubleLinkedList::removeAtStart() {
// can't remove anything from an empty list
if (this->tail == nullptr) return false;
// clear list if last element remaining is deleted
if (this->tail->next == nullptr) {
head = tail = nullptr;
size = 0;
return true;
}
// delete and shift
IntDoubleLink* node = this->tail;
this->tail = this->tail->next;
delete node;
size--;
return true;
}
bool IntDoubleLinkedList::removeAtEnd() {
// can't remove anything from an empty list
if (this->head == nullptr) return false;
// clear list if last element remaining is deleted
if (this->head->prev == nullptr) {
head = tail = nullptr;
size = 0;
return true;
}
// delete and shift
IntDoubleLink* node = this->head;
this->head = this->head->prev;
delete node;
size--;
return true;
}
IntDoubleLink* IntDoubleLinkedList::getHead() { return this->head; }
IntDoubleLink* IntDoubleLinkedList::getTail() { return this->tail; }
int IntDoubleLinkedList::_indexOf(IntDoubleLink* s) {
int i = 0;
IntDoubleLink* c = tail;
while (c != nullptr) {
if (c == s) return i;
i++;
c = c->next;
}
return -1;
}
void IntDoubleLinkedList::rapidBubbleSort() {
// waarom moet hier v ook een pointer sterretje staan!?
IntDoubleLink *outer, *inner;
bool sorted;
for (outer = tail; outer != head; outer = outer->next) {
sorted = true; // check if array was modified during inner loop
for (inner = head->prev; inner != outer->prev; inner = inner->prev) {
// printf("inner [%d, %d]\n", _indexOf(inner), _indexOf(inner->next));
if (inner->value >= inner->next->value) {
std::swap(inner->value, inner->next->value);
sorted = false;
}
}
// printf("outer %d: ", _indexOf(outer)); // indexOf printing for loop debugging
// showAll();
if (sorted) break; // break if nothing changed (already sorted)
}
}
/*
* metingen van de duur van het sorteren...
*
* aantal waarden: duur in us:
* 1000 4718
* 2000 19976
* 5000 131068
* 10000 547875
* ...
*/
/*
* gemeten snelheid van dit algoritme: O(n^2)
* onderbouwing:
*
* aan de structuur van de zoekfunctie is niets veranderd, er zijn nog steeds
* twee for-lussen waar het aantal iteraties recht evenredig is met de
* arraygrotte. mijn zoekfunctie gebruikt geen getAt of setAt, dus er worden
* geen extra 'factoren' van n toegevoegd
*/
/*
* Vergelijking met bubblesort van week 3 deel 1
*
* hij draait wel een ordergrootte sneller dan in deel 1 :^)
*/
void IntDoubleLinkedList::insertAction(int code) {
while (head != actionCursor)
if (!removeAtEnd()) break;
insertAtEnd(code);
actionCursor = head;
}
int IntDoubleLinkedList::undo() {
if (actionCursor->prev != nullptr)
actionCursor = actionCursor->prev;
return actionCursor->value;
}
int IntDoubleLinkedList::redo() {
if (actionCursor->next != nullptr)
actionCursor = actionCursor->next;
return actionCursor->value;
}
int IntDoubleLinkedList::getCurrentAction() {
return actionCursor->value;
}
void IntDoubleLinkedList::showAll() {
std::cout << "[";
IntDoubleLink* node = this->tail;
while (node != nullptr) {
if (node == actionCursor) std::cout << "{"; // curly braces for highlighting actionCursor
std::cout << node->value;
if (node == actionCursor) std::cout << "}";
node = node->next;
if (node != nullptr) std::cout << ", ";
}
std::cout << "]" << std::endl;
}
|