bubble v0.0.1
Loading...
Searching...
No Matches
bubble.h
1
9#ifndef BUBBLE_H
10#define BUBBLE_H
11
12#ifdef __cplusplus
13#include <iostream>
14#include <vector>
15#include <optional>
16#include <ranges>
17#include <algorithm>
18#include <utility>
19#include <cassert>
20#include "avl_tree.h"
21#endif
22
26template <typename T, size_t _SIZE>
27class bubble {
28private:
29 std::vector<std::pair<T, std::optional<avl_tree<T>>>> list;
30 size_t _size;
31
32public:
36 explicit bubble() noexcept : _size(0) { }
37
42 template <size_t _NEW_SIZE>
43 bubble(const bubble<T, _NEW_SIZE> &t) : _size(0) {
44 try {
45 if(_NEW_SIZE != _SIZE) {
46 throw std::logic_error("Tried to copy bubbles with different sizes");
47 return;
48 }
49 this->_size = t.size();
50 this->list = {};
51 for(size_t i = 0; i<this->_size; i++){
52 this->list.push_back(std::pair<T, std::optional<avl_tree<T>>>(t.get_key(i), t.get_tree(i)));
53 }
54 }
55 catch (std::logic_error &e){
56 std::cerr << e.what() << '\n';
57 }
58 }
59
65 template <size_t _NEW_SIZE>
66 const bubble operator =(bubble<T, _NEW_SIZE> &t) {
67 try{
68 if(_NEW_SIZE != _SIZE) {
69 throw std::logic_error("Tried to copy two bubbles with different sizes");
70 }
71 this->_size = t.size();
72 this->list = {};
73 for(size_t i = 0; i<this->_size; i++){
74 this->list.push_back(std::pair<T, std::optional<avl_tree<T>>>(t.get_key(i), t.get_tree(i)));
75 }
76 }
77 catch (std::logic_error &e) {
78 std::cerr << e.what() << '\n';
79 return *(this);
80 }
81 return *(this);
82 }
83
89 template <typename... Args>
90 void insert(Args ...keys);
91
97 template <typename... Args>
98 void remove(Args ...keys);
99
106 bool search(const T& key);
107
113 T get_key(const size_t& index) const;
114
120 avl_tree<T> get_tree(const size_t& index) const;
121
125 class iterator;
126
131 iterator begin() noexcept { return iterator(this->list, 0); }
132
137 iterator end() noexcept { return iterator(this->list, _SIZE); }
138
143 size_t size() const;
144
149 size_t array_size() const;
150
156 bool empty() const;
157
163 std::pair<T, std::vector<T>> operator[] (const size_t& index) const {
164 assert(index < _SIZE && index >= 0);
165 if(this->list[index].second == std::nullopt) { return {std::make_pair(this->list[index].first, std::vector<T>())}; }
166 return std::make_pair(this->list[index].first, this->list[index].second.value().inorder());
167 }
168
172 friend std::ostream & operator << (std::ostream &out, const bubble<T, _SIZE> &t){
173 if(t._size == 0) { return out; }
174 for(auto && x : t.list) {
175 out << x.first << ": {";
176 if(x.second == std::nullopt){
177 out << "}" << '\n';
178 continue;
179 }
180 avl_tree<T> tmp_tree(x.second.value());
181 std::vector<T> ino = tmp_tree.inorder();
182 for(size_t i = 0; i<ino.size(); i++){
183 if(i == ino.size() - 1) {
184 out << ino[i];
185 }
186 else{
187 out << ino[i] << " ";
188 }
189 }
190 out << "}" << '\n';
191 }
192 return out;
193 }
194};
195
196template <typename T, size_t _SIZE>
197template <typename... Args>
198inline void bubble<T, _SIZE>::insert(Args ...keys) {
199 auto _insert = [&](const T&& key) -> void {
200 if(_size < _SIZE) {
201 this->list.push_back({key, std::nullopt});
202 _size++;
203 return;
204 }
205 if(_size == _SIZE) {
206 std::ranges::sort(this->list, [](const std::pair<T, std::optional<avl_tree<T>>> &a, const std::pair<T, std::optional<avl_tree<T>>> &b){
207 return a.first < b.first;
208 });
209 }
210
211 auto it = std::lower_bound(std::ranges::begin(this->list), std::ranges::end(this->list), key, [](const std::pair<T, std::optional<avl_tree<T>>> &pair, const T &key){ return pair.first < key; });
212
213 if(it != std::ranges::end(this->list)) {
214 int idx = std::distance(std::ranges::begin(this->list), it);
215 if(this->list[idx].first == key) { return; }
216
217 if(idx == 0){
218 if(this->list[0].second == std::nullopt) {
219 this->list[0].second = avl_tree<T>();
220 }
221 this->list[0].second.value().insert(key);
222 }
223 else{
224 if(this->list[idx - 1].second == std::nullopt) {
225 this->list[idx - 1].second = avl_tree<T>();
226 }
227 this->list[idx - 1].second.value().insert(key);
228 }
229 }
230 else {
231 if(this->list[this->list.size() - 1].second == std::nullopt){
232 this->list[this->list.size() - 1].second = avl_tree<T>();
233 }
234 this->list[this->list.size() - 1].second.value().insert(key);
235 }
236 _size++;
237 };
238 (std::invoke(_insert, std::forward<Args>(keys)), ...);
239}
240
241
242template <typename T, size_t _SIZE>
243template <typename... Args>
244void bubble<T, _SIZE>::remove(Args ...keys) {
245 auto _remove = [&](const T&& key) -> void{
246 if(this->_size == 0) { return; }
247 if(this->_size <= _SIZE) {
248 auto [begin, end] = std::ranges::remove_if(this->list, [&](const std::pair<T, std::optional<avl_tree<T>>> &t) { return t.first == key; });
249 list.erase(begin, end);
250 _size--;
251 }
252 else{
253 auto it = std::lower_bound(std::ranges::begin(this->list), std::ranges::end(this->list), key, [](const std::pair<T, std::optional<avl_tree<T>>> &pair, const T &key){ return pair.first < key; });
254 if(it != std::ranges::end(this->list)) {
255 size_t idx = std::ranges::distance(std::ranges::begin(this->list), it);
256
257 if(this->list[idx].first == key && this->list[idx].second != std::nullopt) {
258 T curr_root = this->list[idx].second.value().get_root();
259 this->list[idx].second.value().remove(curr_root);
260 this->list[idx].first = curr_root;
261 return;
262 }
263
264 if(idx == 0){
265 if(this->list[0].second == std::nullopt){
266 return;
267 }
268 this->list[0].second.value().remove(key);
269 }
270 else{
271 if(this->list[idx - 1].second == std::nullopt) {
272 return;
273 }
274 this->list[idx - 1].second.value().remove(key);
275 }
276 }
277 else {
278 if(this->list[this->list.size() - 1].second == std::nullopt) {
279 return;
280 }
281 this->list[this->list.size() - 1].second.value().remove(key);
282 }
283 _size--;
284 }
285 };
286 (std::invoke(_remove, std::forward<Args>(keys)), ...);
287}
288
289template <typename T, size_t _SIZE>
290bool bubble<T, _SIZE>::search(const T& key) {
291 if(this->_size == 0) { return false; }
292 auto it = std::lower_bound(std::ranges::begin(this->list), std::ranges::end(this->list), key, [](const std::pair<T, std::optional<avl_tree<T>>> &pair, const T &key){ return pair.first < key; });
293 if (it != std::ranges::end(this->list)){
294 size_t idx = std::ranges::distance(std::ranges::begin(this->list), it);
295 if(idx == 0){
296 if(this->list[0].first == key) { return true; }
297 if(this->list[0].second == std::nullopt) { return false; }
298 if(this->list[0].second.value().search(key) == true) { return true; }
299 }
300 else {
301 if(this->list[idx].first == key) { return true; }
302 if(this->list[idx - 1].second == std::nullopt) { return false; }
303 if(this->list[idx - 1].second.value().search(key) == true) { return true; }
304 }
305 }
306 else {
307 if(this->list[this->list.size() - 1].first == key) { return true; }
308 if(this->list[this->list.size() - 1].second == std::nullopt) { return false; }
309 if(this->list[this->list.size() - 1].second.value().search(key) == true) { return true; }
310 }
311 return false;
312}
313
314template <typename T, size_t _SIZE>
315T bubble<T, _SIZE>::get_key(const size_t &index) const {
316 assert(index >=0 && index < _SIZE);
317 return this->list[index].first;
318}
319
320template <typename T, size_t _SIZE>
321avl_tree<T> bubble<T, _SIZE>::get_tree(const size_t &index) const {
322 assert(index >=0 && index < _SIZE);
323 if(this->list[index].second == std::nullopt) {
324 return avl_tree<T>();
325 }
326 return avl_tree<T>(this->list[index].second.value());
327}
328
329template <typename T, size_t _SIZE>
330size_t bubble<T, _SIZE>::size() const {
331 return this->_size;
332}
333
334template <typename T, size_t _SIZE>
335bool bubble<T, _SIZE>::empty() const {
336 return this->_size == 0;
337}
338
339template <typename T, size_t _SIZE>
340size_t bubble<T, _SIZE>::array_size() const {
341 return _SIZE;
342}
343
344template <typename T, size_t _SIZE>
345class bubble<T, _SIZE>::iterator {
346private:
347 using bubble = std::vector<std::pair<T, std::optional<avl_tree<T>>>>;
348 bubble b;
349 int64_t index;
350 size_t _size;
351
352public:
353 explicit iterator(const bubble& v, const size_t& _index) noexcept : b(v), index(_index) {}
354
355 iterator& operator=(bubble current) {
356 this->_size = current.size();
357 this->b= {};
358 for(size_t i = 0; i<this->_size; i++){
359 this->b.push_back(std::pair<T, std::optional<avl_tree<T>>>(current.get_key(i), current.get_tree(i)));
360 }
361 return *(this);
362 }
363
364 iterator& operator++() {
365 if(this->index < _SIZE) {
366 this->index++;
367 }
368 return *(this);
369 }
370
371 iterator operator++(int) {
372 iterator it = *(this);
373 ++*(this);
374 return it;
375 }
376
377 iterator& operator--() {
378 if(this->index > 0) {
379 this->index--;
380 }
381 return *(this);
382 }
383
384 iterator operator--(int) {
385 iterator it = *(this);
386 --*(this);
387 return it;
388 }
389
390 bool operator!=(const iterator &it) {
391 return it.b[it.index].first != this->b[this->index].first;
392 }
393
394 bool operator==(const iterator &it) {
395 return it.b[it.index].first == this->b[this->index].first;
396 }
397
398 std::pair<T, std::optional<avl_tree<T>>>& operator*() {
399 return this->b[this->index];
400 }
401};
402
406template <typename T>
407bool operator==(const std::pair<T, std::optional<avl_tree<T>>> &a,
408 const std::pair<T, std::optional<avl_tree<T>>> &b){
409 if(a.first == b.first){
410 if(a.second == std::nullopt && b.second == std::nullopt){
411 return true;
412 }
413 else if((a.second != std::nullopt && b.second == std::nullopt) || (a.second == std::nullopt && b.second != std::nullopt)){
414 return false;
415 }
416 else{
417 std::vector v1 { a.second.value().inorder() };
418 std::vector v2 { b.second.value().inorder() };
419 return v1 == v2;
420 }
421 }
422 return false;
423}
424
425template <typename T>
426bool operator!=(const std::pair<T, std::optional<avl_tree<T>>> &a,
427 const std::pair<T, std::optional<avl_tree<T>>> &b){
428 if(a.first != b.first) { return true; }
429 else {
430 if(a.second == std::nullopt && b.second == std::nullopt) {
431 return false;
432 }
433 else if((a.second == std::nullopt && b.second != std::nullopt) || (a.second != std::nullopt && b.second == std::nullopt)){
434 return true;
435 }
436 else{
437 std::vector v1 { a.second.value().inorder() };
438 std::vector v2 { b.second.value().inorder() };
439 return v1 != v2;
440 }
441 }
442 return false;
443}
444
445template <typename T>
446bool operator<(const std::pair<T, std::optional<avl_tree<T>>> &a,
447 const std::pair<T, std::optional<avl_tree<T>>> &b){
448 if(a.first == b.first) {
449 if(a.second == std::nullopt && b.second != std::nullopt){
450 return true;
451 }
452 else if(a.second != std::nullopt && b.second == std::nullopt){
453 return false;
454 }
455 else{
456 std::vector v1 { a.second.value().inorder() };
457 std::vector v2 { b.second.value().inorder() };
458 return v1 < v2;
459 }
460 }
461 return a.first < b.first;
462}
463
464template <typename T>
465bool operator<=(const std::pair<T, std::optional<avl_tree<T>>> &a,
466 const std::pair<T, std::optional<avl_tree<T>>> &b){
467 if(a.first == b.first) {
468 if(a.second == std::nullopt && b.second != std::nullopt){
469 return true;
470 }
471 else if(a.second != std::nullopt && b.second == std::nullopt){
472 return false;
473 }
474 else{
475 std::vector v1 { a.second.value().inorder() };
476 std::vector v2 { b.second.value().inorder() };
477 return v1 <= v2;
478 }
479 }
480 return a.first <= b.first;
481}
482
483template <typename T>
484bool operator>(const std::pair<T, std::optional<avl_tree<T>>> &a,
485 const std::pair<T, std::optional<avl_tree<T>>> &b){
486 if(a.first == b.first) {
487 if(a.second == std::nullopt && b.second != std::nullopt){
488 return false;
489 }
490 else if(a.second != std::nullopt && b.second == std::nullopt){
491 return true;
492 }
493 else{
494 std::vector v1 { a.second.value().inorder() };
495 std::vector v2 { b.second.value().inorder() };
496 return v1 > v2;
497 }
498 }
499 return a.first > b.first;
500}
501
502
503template <typename T>
504bool operator>=(const std::pair<T, std::optional<avl_tree<T>>> &a,
505 const std::pair<T, std::optional<avl_tree<T>>> &b){
506 if(a.first == b.first) {
507 if(a.second == std::nullopt && b.second != std::nullopt){
508 return false;
509 }
510 else if(a.second != std::nullopt && b.second == std::nullopt){
511 return true;
512 }
513 else{
514 std::vector v1 { a.second.value().inorder() };
515 std::vector v2 { b.second.value().inorder() };
516 return v1 >= v2;
517 }
518 }
519 return a.first >= b.first;
520}
521
522#endif
avl_tree
Class for AVL tree.
Definition avl_tree.h:15
avl_tree::inorder
std::vector< T > inorder() const
inorder function.
Definition avl_tree.h:130
bubble::iterator
Definition bubble.h:345
bubble
Implementation of the bubble data structure, a data structure that is highly influenced from the fibo...
Definition bubble.h:27
bubble::operator[]
std::pair< T, std::vector< T > > operator[](const size_t &index) const
operator [] for bubble
Definition bubble.h:163
bubble::operator=
const bubble operator=(bubble< T, _NEW_SIZE > &t)
operator = for bubble class
Definition bubble.h:66
bubble::insert
void insert(Args ...keys)
insert function for bubble
Definition bubble.h:198
bubble::search
bool search(const T &key)
search function for bubble
Definition bubble.h:290
bubble::bubble
bubble(const bubble< T, _NEW_SIZE > &t)
copy constructor of bubble
Definition bubble.h:43
bubble::empty
bool empty() const
empty function for bubble
Definition bubble.h:335
bubble::remove
void remove(Args ...keys)
remove function for bubble
Definition bubble.h:244
bubble::begin
iterator begin() noexcept
begin iterator
Definition bubble.h:131
bubble::get_key
T get_key(const size_t &index) const
get_key function
Definition bubble.h:315
bubble::size
size_t size() const
size function for bubble
Definition bubble.h:330
bubble::end
iterator end() noexcept
end iterator
Definition bubble.h:137
bubble::bubble
bubble() noexcept
default constructor of bubble
Definition bubble.h:36
bubble::operator<<
friend std::ostream & operator<<(std::ostream &out, const bubble< T, _SIZE > &t)
operator << for bubble
Definition bubble.h:172
bubble::get_tree
avl_tree< T > get_tree(const size_t &index) const
get_tree function
Definition bubble.h:321
bubble::array_size
size_t array_size() const
array_size function for bubble
Definition bubble.h:340
Generated by doxygen 1.12.0