Line data Source code
1 : #ifndef HASHBROWNS_DYNAMIC_ARRAY_H
2 : #define HASHBROWNS_DYNAMIC_ARRAY_H
3 :
4 : #include "core/data_structure.h"
5 : #include "core/memory_manager.h"
6 : #include <algorithm>
7 : #include <initializer_list>
8 : #include <iostream>
9 : #include <iterator>
10 : #include <stdexcept>
11 : #include <utility>
12 :
13 : namespace hashbrowns {
14 :
15 : /**
16 : * @brief Growth strategy enumeration for dynamic array resizing
17 : */
18 : enum class GrowthStrategy {
19 : MULTIPLICATIVE_2_0, // Growth factor of 2.0
20 : MULTIPLICATIVE_1_5, // Growth factor of 1.5
21 : FIBONACCI, // Fibonacci sequence growth
22 : ADDITIVE // Fixed increment growth
23 : };
24 :
25 : // Stream operator for GrowthStrategy enum
26 : inline std::ostream& operator<<(std::ostream& os, GrowthStrategy strategy) {
27 : switch (strategy) {
28 : case GrowthStrategy::MULTIPLICATIVE_2_0:
29 : return os << "MULTIPLICATIVE_2_0";
30 : case GrowthStrategy::MULTIPLICATIVE_1_5:
31 : return os << "MULTIPLICATIVE_1_5";
32 : case GrowthStrategy::FIBONACCI:
33 : return os << "FIBONACCI";
34 : case GrowthStrategy::ADDITIVE:
35 : return os << "ADDITIVE";
36 : default:
37 : return os << "UNKNOWN";
38 : }
39 : }
40 :
41 : /**
42 : * @brief High-performance dynamic array with configurable growth strategies
43 : *
44 : * This implementation showcases advanced C++ techniques:
45 : * - Template metaprogramming with SFINAE
46 : * - Custom allocator support
47 : * - STL-compatible iterators
48 : * - Exception safety guarantees
49 : * - Move semantics and perfect forwarding
50 : * - Multiple growth strategies for performance analysis
51 : *
52 : * @tparam T Element type
53 : * @tparam Allocator Allocator type (defaults to TrackedAllocator)
54 : */
55 : template<typename T, typename Allocator = TrackedAllocator<T>>
56 : class DynamicArray : public DataStructure {
57 : public:
58 : // Type aliases for STL compatibility
59 : using value_type = T;
60 : using allocator_type = Allocator;
61 : using size_type = std::size_t;
62 : using difference_type = std::ptrdiff_t;
63 : using reference = T&;
64 : using const_reference = const T&;
65 : using pointer = typename std::allocator_traits<Allocator>::pointer;
66 : using const_pointer = typename std::allocator_traits<Allocator>::const_pointer;
67 :
68 : // Forward declare iterator classes
69 : template<typename ValueType>
70 : class iterator_impl;
71 :
72 : using iterator = iterator_impl<T>;
73 : using const_iterator = iterator_impl<const T>;
74 : using reverse_iterator = std::reverse_iterator<iterator>;
75 : using const_reverse_iterator = std::reverse_iterator<const_iterator>;
76 :
77 : private:
78 : pointer data_;
79 : size_type size_;
80 : size_type capacity_;
81 : GrowthStrategy growth_strategy_;
82 : Allocator allocator_;
83 :
84 : // Fibonacci growth state
85 : mutable size_type fib_prev_ = 1;
86 : mutable size_type fib_curr_ = 1;
87 :
88 : public:
89 : /**
90 : * @brief Construct empty array with specified growth strategy
91 : * @param strategy Growth strategy to use for resizing
92 : * @param alloc Allocator instance
93 : */
94 49 : explicit DynamicArray(GrowthStrategy strategy = GrowthStrategy::MULTIPLICATIVE_2_0,
95 : const Allocator& alloc = Allocator())
96 54 : : data_(nullptr), size_(0), capacity_(0), growth_strategy_(strategy), allocator_(alloc) {}
97 :
98 : /**
99 : * @brief Construct array with initial capacity
100 : * @param initial_capacity Initial capacity to reserve
101 : * @param strategy Growth strategy to use
102 : * @param alloc Allocator instance
103 : */
104 1 : explicit DynamicArray(size_type initial_capacity,
105 : GrowthStrategy strategy = GrowthStrategy::MULTIPLICATIVE_2_0,
106 : const Allocator& alloc = Allocator())
107 1 : : data_(nullptr), size_(0), capacity_(0), growth_strategy_(strategy), allocator_(alloc) {
108 1 : reserve(initial_capacity);
109 1 : }
110 :
111 : /**
112 : * @brief Construct from initializer list
113 : * @param init Initializer list of elements
114 : * @param strategy Growth strategy to use
115 : * @param alloc Allocator instance
116 : */
117 1 : DynamicArray(std::initializer_list<T> init,
118 : GrowthStrategy strategy = GrowthStrategy::MULTIPLICATIVE_2_0,
119 : const Allocator& alloc = Allocator())
120 1 : : data_(nullptr), size_(0), capacity_(0), growth_strategy_(strategy), allocator_(alloc) {
121 1 : reserve(init.size());
122 6 : for (const auto& item : init) {
123 5 : push_back(item);
124 : }
125 1 : }
126 :
127 : /**
128 : * @brief Copy constructor
129 : */
130 5 : DynamicArray(const DynamicArray& other)
131 5 : : data_(nullptr), size_(0), capacity_(0), growth_strategy_(other.growth_strategy_),
132 14 : allocator_(std::allocator_traits<Allocator>::select_on_container_copy_construction(other.allocator_)) {
133 5 : reserve(other.size_);
134 407 : for (size_type i = 0; i < other.size_; ++i) {
135 402 : push_back(other.data_[i]);
136 : }
137 5 : }
138 :
139 : /**
140 : * @brief Move constructor
141 : */
142 4 : DynamicArray(DynamicArray&& other) noexcept
143 4 : : data_(other.data_), size_(other.size_), capacity_(other.capacity_),
144 4 : growth_strategy_(other.growth_strategy_), allocator_(std::move(other.allocator_)),
145 8 : fib_prev_(other.fib_prev_), fib_curr_(other.fib_curr_) {
146 4 : other.data_ = nullptr;
147 4 : other.size_ = 0;
148 4 : other.capacity_ = 0;
149 4 : }
150 :
151 : /**
152 : * @brief Destructor
153 : */
154 90 : ~DynamicArray() {
155 60 : clear();
156 60 : deallocate();
157 163 : }
158 :
159 : /**
160 : * @brief Copy assignment operator
161 : */
162 1 : DynamicArray& operator=(const DynamicArray& other) {
163 1 : if (this != &other) {
164 1 : DynamicArray temp(other);
165 1 : swap(temp);
166 1 : }
167 1 : return *this;
168 : }
169 :
170 : /**
171 : * @brief Move assignment operator
172 : */
173 1 : DynamicArray& operator=(DynamicArray&& other) noexcept {
174 1 : if (this != &other) {
175 1 : clear();
176 1 : deallocate();
177 :
178 1 : data_ = other.data_;
179 1 : size_ = other.size_;
180 1 : capacity_ = other.capacity_;
181 1 : growth_strategy_ = other.growth_strategy_;
182 1 : allocator_ = std::move(other.allocator_);
183 1 : fib_prev_ = other.fib_prev_;
184 1 : fib_curr_ = other.fib_curr_;
185 :
186 1 : other.data_ = nullptr;
187 1 : other.size_ = 0;
188 1 : other.capacity_ = 0;
189 : }
190 1 : return *this;
191 : }
192 :
193 : // DataStructure interface implementation
194 746 : void insert(int key, const std::string& value) override {
195 : if constexpr (std::is_same_v<T, std::pair<int, std::string>>) {
196 746 : push_back(std::make_pair(key, value));
197 : } else {
198 0 : throw std::invalid_argument("DynamicArray<T> does not support key-value insertion unless T is std::pair<int, std::string>");
199 : }
200 746 : }
201 :
202 522 : bool search(int key, std::string& value) const override {
203 : if constexpr (std::is_same_v<T, std::pair<int, std::string>>) {
204 11726 : auto it = std::find_if(begin(), end(), [key](const auto& pair) {
205 11204 : return pair.first == key;
206 : });
207 522 : if (it != end()) {
208 521 : value = it->second;
209 521 : return true;
210 : }
211 : }
212 1 : return false;
213 : }
214 :
215 521 : bool remove(int key) override {
216 : if constexpr (std::is_same_v<T, std::pair<int, std::string>>) {
217 3284 : auto it = std::find_if(begin(), end(), [key](const auto& pair) {
218 2763 : return pair.first == key;
219 : });
220 521 : if (it != end()) {
221 521 : erase(it);
222 521 : return true;
223 : }
224 : }
225 0 : return false;
226 : }
227 :
228 450 : size_t size() const override { return size_; }
229 6 : bool empty() const override { return size_ == 0; }
230 :
231 62 : void clear() override {
232 1221 : for (size_type i = 0; i < size_; ++i) {
233 1159 : std::allocator_traits<Allocator>::destroy(allocator_, &data_[i]);
234 : }
235 62 : size_ = 0;
236 62 : }
237 :
238 7 : size_t memory_usage() const override {
239 7 : return capacity_ * sizeof(T) + sizeof(*this);
240 : }
241 :
242 3 : std::string type_name() const override { return "DynamicArray"; }
243 3 : std::string insert_complexity() const override { return "O(1) amortized"; }
244 3 : std::string search_complexity() const override { return "O(n)"; }
245 3 : std::string remove_complexity() const override { return "O(n)"; }
246 :
247 : // Array-specific interface
248 912 : void push_back(const T& value) {
249 912 : emplace_back(value);
250 912 : }
251 :
252 767 : void push_back(T&& value) {
253 767 : emplace_back(std::move(value));
254 767 : }
255 :
256 : template<typename... Args>
257 1679 : reference emplace_back(Args&&... args) {
258 1679 : if (size_ == capacity_) {
259 212 : grow();
260 : }
261 1679 : std::allocator_traits<Allocator>::construct(allocator_, &data_[size_], std::forward<Args>(args)...);
262 1679 : return data_[size_++];
263 : }
264 :
265 3 : void pop_back() {
266 3 : if (empty()) {
267 1 : throw std::out_of_range("pop_back() called on empty array");
268 : }
269 2 : --size_;
270 2 : std::allocator_traits<Allocator>::destroy(allocator_, &data_[size_]);
271 2 : }
272 :
273 2 : reference at(size_type index) {
274 2 : if (index >= size_) {
275 1 : throw std::out_of_range("Index out of range");
276 : }
277 1 : return data_[index];
278 : }
279 :
280 1 : const_reference at(size_type index) const {
281 1 : if (index >= size_) {
282 0 : throw std::out_of_range("Index out of range");
283 : }
284 1 : return data_[index];
285 : }
286 :
287 1318 : reference operator[](size_type index) { return data_[index]; }
288 1 : const_reference operator[](size_type index) const { return data_[index]; }
289 :
290 1 : reference front() { return data_[0]; }
291 1 : const_reference front() const { return data_[0]; }
292 1 : reference back() { return data_[size_ - 1]; }
293 1 : const_reference back() const { return data_[size_ - 1]; }
294 :
295 1 : T* data() noexcept { return data_; }
296 1 : const T* data() const noexcept { return data_; }
297 :
298 4 : size_type capacity() const noexcept { return capacity_; }
299 :
300 10 : void reserve(size_type new_capacity) {
301 10 : if (new_capacity > capacity_) {
302 10 : reallocate(new_capacity);
303 : }
304 10 : }
305 :
306 1 : void shrink_to_fit() {
307 1 : if (size_ < capacity_) {
308 1 : reallocate(size_);
309 : }
310 1 : }
311 :
312 1 : void resize(size_type new_size) {
313 1 : if (new_size > capacity_) {
314 1 : reserve(new_size);
315 : }
316 :
317 1 : if (new_size > size_) {
318 9 : for (size_type i = size_; i < new_size; ++i) {
319 8 : std::allocator_traits<Allocator>::construct(allocator_, &data_[i]);
320 : }
321 0 : } else if (new_size < size_) {
322 0 : for (size_type i = new_size; i < size_; ++i) {
323 0 : std::allocator_traits<Allocator>::destroy(allocator_, &data_[i]);
324 : }
325 : }
326 1 : size_ = new_size;
327 1 : }
328 :
329 1 : void resize(size_type new_size, const T& value) {
330 1 : if (new_size > capacity_) {
331 0 : reserve(new_size);
332 : }
333 :
334 1 : if (new_size > size_) {
335 0 : for (size_type i = size_; i < new_size; ++i) {
336 0 : std::allocator_traits<Allocator>::construct(allocator_, &data_[i], value);
337 : }
338 1 : } else if (new_size < size_) {
339 6 : for (size_type i = new_size; i < size_; ++i) {
340 5 : std::allocator_traits<Allocator>::destroy(allocator_, &data_[i]);
341 : }
342 : }
343 1 : size_ = new_size;
344 1 : }
345 :
346 : // Iterator interface
347 537 : iterator begin() { return iterator(data_); }
348 538 : const_iterator begin() const { return const_iterator(data_); }
349 521 : const_iterator cbegin() const { return const_iterator(data_); }
350 :
351 1055 : iterator end() { return iterator(data_ + size_); }
352 1048 : const_iterator end() const { return const_iterator(data_ + size_); }
353 1 : const_iterator cend() const { return const_iterator(data_ + size_); }
354 :
355 1 : reverse_iterator rbegin() { return reverse_iterator(end()); }
356 1 : const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
357 1 : const_reverse_iterator crbegin() const { return const_reverse_iterator(end()); }
358 :
359 6 : reverse_iterator rend() { return reverse_iterator(begin()); }
360 6 : const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
361 6 : const_reverse_iterator crend() const { return const_reverse_iterator(begin()); }
362 :
363 521 : iterator erase(const_iterator pos) {
364 521 : return erase(pos, pos + 1);
365 : }
366 :
367 521 : iterator erase(const_iterator first, const_iterator last) {
368 521 : auto diff = last - first;
369 521 : auto index = first - cbegin();
370 :
371 : // Move elements
372 8961 : for (size_type i = index; i + diff < size_; ++i) {
373 8440 : data_[i] = std::move(data_[i + diff]);
374 : }
375 :
376 : // Destroy moved-from elements
377 1042 : for (size_type i = size_ - diff; i < size_; ++i) {
378 521 : std::allocator_traits<Allocator>::destroy(allocator_, &data_[i]);
379 : }
380 :
381 521 : size_ -= diff;
382 521 : return iterator(data_ + index);
383 : }
384 :
385 : // Utility methods
386 2 : void swap(DynamicArray& other) noexcept {
387 2 : std::swap(data_, other.data_);
388 2 : std::swap(size_, other.size_);
389 2 : std::swap(capacity_, other.capacity_);
390 2 : std::swap(growth_strategy_, other.growth_strategy_);
391 2 : std::swap(allocator_, other.allocator_);
392 2 : std::swap(fib_prev_, other.fib_prev_);
393 2 : std::swap(fib_curr_, other.fib_curr_);
394 2 : }
395 :
396 2 : GrowthStrategy growth_strategy() const { return growth_strategy_; }
397 1 : void set_growth_strategy(GrowthStrategy strategy) { growth_strategy_ = strategy; }
398 :
399 : private:
400 212 : void grow() {
401 212 : size_type new_capacity = calculate_growth();
402 212 : reallocate(new_capacity);
403 212 : }
404 :
405 212 : size_type calculate_growth() const {
406 212 : if (capacity_ == 0) return 1;
407 :
408 174 : switch (growth_strategy_) {
409 11 : case GrowthStrategy::MULTIPLICATIVE_1_5: {
410 11 : size_type new_cap = capacity_ + (capacity_ + 1) / 2; // Ceiling division
411 11 : return std::max(new_cap, capacity_ + 1);
412 : }
413 143 : case GrowthStrategy::MULTIPLICATIVE_2_0:
414 143 : return capacity_ * 2;
415 10 : case GrowthStrategy::FIBONACCI: {
416 10 : size_type next_fib = fib_prev_ + fib_curr_;
417 10 : fib_prev_ = fib_curr_;
418 10 : fib_curr_ = next_fib;
419 10 : return std::max(capacity_ + 1, next_fib);
420 : }
421 10 : case GrowthStrategy::ADDITIVE:
422 10 : return capacity_ + 10; // Fixed increment for testing
423 0 : default:
424 0 : return capacity_ * 2;
425 : }
426 : }
427 :
428 223 : void reallocate(size_type new_capacity) {
429 223 : pointer new_data = std::allocator_traits<Allocator>::allocate(allocator_, new_capacity);
430 :
431 : // Move construct existing elements
432 2297 : for (size_type i = 0; i < size_; ++i) {
433 2074 : std::allocator_traits<Allocator>::construct(allocator_, &new_data[i], std::move(data_[i]));
434 2074 : std::allocator_traits<Allocator>::destroy(allocator_, &data_[i]);
435 : }
436 :
437 223 : deallocate();
438 223 : data_ = new_data;
439 223 : capacity_ = new_capacity;
440 223 : }
441 :
442 284 : void deallocate() {
443 284 : if (data_) {
444 223 : std::allocator_traits<Allocator>::deallocate(allocator_, data_, capacity_);
445 223 : data_ = nullptr;
446 : }
447 284 : }
448 : };
449 :
450 : /**
451 : * @brief STL-compatible iterator implementation
452 : */
453 : template<typename T, typename Allocator>
454 : template<typename ValueType>
455 : class DynamicArray<T, Allocator>::iterator_impl {
456 : public:
457 : using iterator_category = std::random_access_iterator_tag;
458 : using value_type = std::remove_cv_t<ValueType>;
459 : using difference_type = std::ptrdiff_t;
460 : using pointer = ValueType*;
461 : using reference = ValueType&;
462 :
463 : private:
464 : pointer ptr_;
465 :
466 : public:
467 : iterator_impl() : ptr_(nullptr) {}
468 4872 : explicit iterator_impl(pointer ptr) : ptr_(ptr) {}
469 :
470 : // Copy constructor from non-const to const
471 : template<typename U, typename = std::enable_if_t<std::is_same_v<U, value_type> && std::is_const_v<ValueType>>>
472 521 : iterator_impl(const iterator_impl<U>& other) : ptr_(other.get_ptr()) {}
473 :
474 19437 : reference operator*() const { return *ptr_; }
475 521 : pointer operator->() const { return ptr_; }
476 :
477 13904 : iterator_impl& operator++() { ++ptr_; return *this; }
478 1 : iterator_impl operator++(int) { iterator_impl temp(*this); ++ptr_; return temp; }
479 :
480 1432 : iterator_impl& operator--() { --ptr_; return *this; }
481 1 : iterator_impl operator--(int) { iterator_impl temp(*this); --ptr_; return temp; }
482 :
483 1 : iterator_impl& operator+=(difference_type n) { ptr_ += n; return *this; }
484 1 : iterator_impl& operator-=(difference_type n) { ptr_ -= n; return *this; }
485 :
486 622 : iterator_impl operator+(difference_type n) const { return iterator_impl(ptr_ + n); }
487 29 : iterator_impl operator-(difference_type n) const { return iterator_impl(ptr_ - n); }
488 :
489 2264 : difference_type operator-(const iterator_impl& other) const { return ptr_ - other.ptr_; }
490 :
491 1 : reference operator[](difference_type n) const { return ptr_[n]; }
492 :
493 23 : bool operator==(const iterator_impl& other) const { return ptr_ == other.ptr_; }
494 1470 : bool operator!=(const iterator_impl& other) const { return ptr_ != other.ptr_; }
495 225 : bool operator<(const iterator_impl& other) const { return ptr_ < other.ptr_; }
496 1 : bool operator<=(const iterator_impl& other) const { return ptr_ <= other.ptr_; }
497 1 : bool operator>(const iterator_impl& other) const { return ptr_ > other.ptr_; }
498 1 : bool operator>=(const iterator_impl& other) const { return ptr_ >= other.ptr_; }
499 :
500 : friend iterator_impl operator+(difference_type n, const iterator_impl& it) {
501 : return iterator_impl(it.ptr_ + n);
502 : }
503 :
504 : // Allow access to ptr_ for conversions
505 521 : pointer get_ptr() const { return ptr_; }
506 : };
507 :
508 : // Non-member functions
509 : template<typename T, typename Allocator>
510 : void swap(DynamicArray<T, Allocator>& lhs, DynamicArray<T, Allocator>& rhs) noexcept {
511 : lhs.swap(rhs);
512 : }
513 :
514 : template<typename T, typename Allocator>
515 3 : bool operator==(const DynamicArray<T, Allocator>& lhs, const DynamicArray<T, Allocator>& rhs) {
516 3 : return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
517 : }
518 :
519 : template<typename T, typename Allocator>
520 2 : bool operator!=(const DynamicArray<T, Allocator>& lhs, const DynamicArray<T, Allocator>& rhs) {
521 2 : return !(lhs == rhs);
522 : }
523 :
524 : } // namespace hashbrowns
525 :
526 : #endif // HASHBROWNS_DYNAMIC_ARRAY_H
|
