Line data Source code
1 : /**
2 : * @file ADTVector.cpp
3 : * @author Konstantinos Chousos
4 : * @brief Implementation of ADTVector using a dynamic array.
5 : * @version 0.1
6 : * @date 2023-10-30
7 : *
8 : * @copyright Copyright (c) 2023
9 : *
10 : */
11 : #include "cppdescent/ADTVector.hpp"
12 : #include "stdlib.h"
13 :
14 4091 : Vector::Vector(int size, DestroyFunc destroyValue)
15 4091 : : size(size), destroyValue(destroyValue) {
16 4091 : this->capacity = size < VECTOR_MIN_CAPACITY ? VECTOR_MIN_CAPACITY : size;
17 : // `calloc` is used instead of `new` so we can later call `realloc`.
18 4091 : this->array = (vectorNode*)calloc(this->capacity, sizeof(*this->array));
19 4091 : }
20 :
21 3265 : Vector::~Vector() {
22 3265 : if (this->destroyValue != nullptr) {
23 1628 : vectorNode* node = this->first();
24 3704 : while (node != nullptr) {
25 2076 : this->destroyValue(node->getValue());
26 2076 : node = this->next(node);
27 : }
28 : }
29 :
30 : // `free` is used because the array was initialzed with `calloc`.
31 3265 : free(this->array);
32 3265 : }
33 :
34 69317 : int Vector::getSize() {
35 69317 : return this->size;
36 : }
37 :
38 45631 : void Vector::insertLast(Pointer value) {
39 : /// If we are at the last element, we create a new array double the size.
40 45631 : if (this->capacity == this->size) {
41 322 : this->capacity *= 2;
42 322 : this->array = (vectorNode*)realloc(this->array,
43 322 : this->capacity * sizeof(*this->array));
44 : }
45 :
46 45631 : this->array[this->size].setValue(value);
47 45631 : this->size++;
48 45631 : }
49 :
50 11702 : int Vector::removeLast() {
51 11702 : if (this->size == 0)
52 11 : return -1;
53 :
54 11691 : if (this->destroyValue != nullptr)
55 231 : this->destroyValue(this->array[this->size - 1].getValue());
56 :
57 11691 : this->size--;
58 :
59 : // if the used part of the array is too small, decrease its size.
60 11691 : if (this->capacity > this->size * 4 &&
61 433 : this->capacity > 2 * VECTOR_MIN_CAPACITY) {
62 66 : this->capacity /= 2;
63 66 : this->array = (vectorNode*)realloc(this->array,
64 66 : this->capacity * sizeof(*this->array));
65 : }
66 11691 : return 0;
67 : }
68 :
69 541373 : Pointer Vector::getAt(int index) {
70 541373 : if (index < 0 || index >= this->size)
71 11 : return nullptr;
72 :
73 541362 : return this->array[index].getValue();
74 : }
75 :
76 259778 : int Vector::setAt(int index, Pointer value) {
77 259778 : if (index < 0 || index >= this->size)
78 11 : return -1;
79 :
80 259767 : if (value != this->array[index].getValue() && this->destroyValue != nullptr)
81 11 : this->destroyValue(this->array[index].getValue());
82 :
83 259767 : this->array[index].setValue(value);
84 259767 : return 0;
85 : }
86 :
87 13724 : Pointer Vector::find(Pointer value, CompareFunc compare) {
88 5529445 : for (int i = 0; i < this->size; i++)
89 5528144 : if (compare(this->array[i].getValue(), value) == 0)
90 12423 : return this->array[i].getValue();
91 :
92 1301 : return nullptr;
93 : }
94 :
95 11 : Pointer Vector::binaryFind(Pointer value, CompareFunc compare) {
96 11 : int l = 0;
97 11 : int r = this->getSize() - 1;
98 :
99 110 : while (l <= r) {
100 99 : int m = l + (r - l) / 2;
101 99 : int comparison = compare(this->array[m].getValue(), value);
102 :
103 : // Check if x is present at mid
104 99 : if (comparison == 0)
105 0 : return this->array[m].getValue();
106 :
107 : // If x greater, ignore left half
108 99 : if (comparison < 0)
109 99 : r = m - 1;
110 :
111 : // If x is smaller, ignore right half
112 : else
113 0 : l = m + 1;
114 : }
115 :
116 : // If we reach here, then element was not present
117 :
118 6611 : for (int i = 0; i < this->size; i++)
119 6611 : if (compare(this->array[i].getValue(), value) == 0)
120 11 : return this->array[i].getValue();
121 :
122 0 : return nullptr;
123 : }
124 :
125 231 : int Vector::findPos(Pointer value, CompareFunc compare) {
126 11671 : for (int i = 0; i < this->size; i++)
127 11660 : if (compare(this->array[i].getValue(), value) == 0)
128 220 : return i;
129 :
130 11 : return -1;
131 : }
132 :
133 3014 : DestroyFunc Vector::setDestroyValue(DestroyFunc destroyValue) {
134 3014 : DestroyFunc old = this->destroyValue;
135 3014 : this->destroyValue = destroyValue;
136 3014 : return old;
137 : }
138 :
139 1650 : vectorNode* Vector::first() {
140 1650 : if (this->size == 0)
141 1040 : return VECTOR_BOF;
142 : else
143 610 : return &this->array[0];
144 : }
145 :
146 22 : vectorNode* Vector::last() {
147 22 : if (this->size == 0)
148 11 : return VECTOR_BOF;
149 : else
150 11 : return &this->array[this->size - 1];
151 : }
152 :
153 13076 : vectorNode* Vector::next(vectorNode* node) {
154 13076 : if (node == &this->array[this->size - 1])
155 610 : return VECTOR_EOF;
156 : else
157 12466 : return node + 1;
158 : }
159 :
160 11000 : vectorNode* Vector::previous(vectorNode* node) {
161 11000 : if (node == &this->array[0])
162 11 : return VECTOR_EOF;
163 : else
164 10989 : return node - 1;
165 : }
166 :
167 22000 : Pointer Vector::nodeValue(vectorNode* node) {
168 22000 : return node->getValue();
169 : }
170 :
171 11011 : vectorNode* Vector::findNode(Pointer value, CompareFunc compare) {
172 5516511 : for (int i = 0; i < this->size; i++)
173 5516500 : if (compare(this->array[i].getValue(), value) == 0)
174 11000 : return &this->array[i]; // found
175 :
176 11 : return VECTOR_EOF; // not found
177 : }
178 :
179 220 : void Vector::swap(int pos1, int pos2) {
180 220 : Pointer temp = this->array[pos1].getValue();
181 220 : this->array[pos1].setValue(this->array[pos2].getValue());
182 220 : this->array[pos2].setValue(temp);
183 220 : }
|
