Created
September 27, 2016 07:52
-
-
Save flisboac/067ad8e2783b1595357015da22550912 to your computer and use it in GitHub Desktop.
A header-only circular doubly-linked list implementation in C++11. Don't know exactly how I came to need and implement it in the first place, but here it is, nonetheless.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #ifndef CIRCULAR_LIST_ | |
| #define CIRCULAR_LIST_ | |
| template <typename T> | |
| class circular_list { | |
| private: // static members | |
| struct node { | |
| public: // methods | |
| node() = default; | |
| node(const node& rhs) = default; | |
| node(node&& rhs) = default; | |
| node(T value_) : _value(value_), _next(this), _prev(this) {} | |
| ~node() { | |
| node* curr = this->_next; | |
| while (curr != nullptr && curr != this) { | |
| node* ptr = curr; | |
| curr = curr->_next; | |
| ptr->_next = nullptr; | |
| delete ptr; | |
| } | |
| } | |
| inline T& value() { return _value; } | |
| inline node* next() const { return _next; } | |
| inline node* previous() const { return _next; } | |
| inline node* insert_before(const T& value) { | |
| node* new_elem = new node(value); | |
| new_elem->_next = this; | |
| new_elem->_prev = this->_prev; | |
| this->_prev->_next = new_elem; | |
| this->_prev = new_elem; | |
| return new_elem; | |
| } | |
| inline node* insert_after(const T& value) { | |
| node* new_elem = new node(value); | |
| new_elem->_prev = this; | |
| new_elem->_next = this->_next; | |
| this->_next->_prev = new_elem; | |
| this->_next = new_elem; | |
| return new_elem; | |
| } | |
| inline node* erase_head() { | |
| node* new_head = nullptr; | |
| if (_next != this) { | |
| new_head = this->_next; | |
| new_head->_prev = this->_prev; | |
| this->_prev->_next = new_head; | |
| this->_next = this->_prev = nullptr; | |
| delete this; | |
| } | |
| return new_head; | |
| } | |
| inline node* erase_tail() { | |
| node* new_tail = nullptr; | |
| if (_prev != this) { | |
| new_tail = this->_prev; | |
| new_tail->_next = this->_next; | |
| this->_next->_prev = new_tail; | |
| this->_next = this->_prev = nullptr; | |
| delete this; | |
| } | |
| return new_tail; | |
| } | |
| private: // methods | |
| node* duplicate() { | |
| node* curr = this->_next; | |
| node* ret = new node(*this); | |
| node* head = ret; | |
| ret->_next = ret; | |
| // If the assumptions do not hold at runtime, all hell will break loose | |
| while (curr != this) { | |
| ret->_next = new node(curr->_next); | |
| ret->_next->_prev = ret; | |
| ret = ret->_next; | |
| curr = curr->_next; | |
| } | |
| head->_prev = ret; | |
| } | |
| private: // fields | |
| node *_next = this; | |
| node *_prev = this; | |
| T _value = T(); | |
| }; | |
| public: // static members | |
| class iterator { | |
| public: | |
| iterator() = default; | |
| iterator(const iterator& rhs) = default; | |
| iterator(iterator&& rhs) = default; | |
| iterator(node* head_, bool end_ = false) : _head(head_), _curr(head_), _end(end_) {} | |
| iterator& operator=(const iterator& rhs) = default; | |
| iterator& operator=(iterator& rhs) = default; | |
| T& operator*() { return _curr->value(); } | |
| T* operator->() { return &_curr->value(); } | |
| bool operator==(const iterator& rhs) { return this->_curr == rhs._curr && _end == rhs._end; } | |
| bool operator!=(const iterator& rhs) { return !(*this == rhs); } | |
| iterator operator++(int) { return ++(*this); } | |
| iterator& operator++() { | |
| node* next = _curr->next(); | |
| _end = next == _head; | |
| _curr = next; | |
| return *this; | |
| } | |
| iterator operator--(int) { return --(*this); } | |
| iterator& operator--() { | |
| _end = false; | |
| _curr = _curr->previous(); | |
| return *this; | |
| } | |
| private: | |
| node *_head = nullptr; | |
| node *_curr = nullptr; | |
| bool _end = false; | |
| }; | |
| public: // methods | |
| circular_list() = default; | |
| circular_list(const circular_list& rhs) : _head(rhs._head.duplicate()) {} | |
| circular_list(circular_list&& rhs) { rhs._head = _head; _head = nullptr; } | |
| ~circular_list() { delete _head; } | |
| bool empty() const { return _head == nullptr || _tail == nullptr; } | |
| size_t size() const { return _size; } | |
| void clear() { delete _head; _head = nullptr; _tail = nullptr; _size = 0; } | |
| T& front() { return _head->value(); } | |
| T& back() { return _tail->value(); } | |
| void push_back(const T& value) { | |
| if (_head == nullptr) { | |
| _head = new node(value); | |
| _tail = _head; | |
| } else { | |
| _head = _head->insert_before(value); | |
| } | |
| ++_size; | |
| } | |
| void push_front(const T& value) { | |
| if (_tail == nullptr) { | |
| _tail = new node(value); | |
| _head = _tail; | |
| } else { | |
| _tail = _tail->insert_after(value); | |
| } | |
| --_size; | |
| } | |
| void pop_back() { | |
| _head = _head->erase_head(); | |
| --_size; | |
| if (_head == nullptr) _tail = nullptr; | |
| } | |
| void pop_front() { | |
| _tail = _tail->erase_tail(); | |
| --_size; | |
| if (_tail == nullptr) _head = nullptr; | |
| } | |
| iterator begin() { return empty() ? end() : iterator(_head, false); } | |
| iterator end() { return iterator(_head, true); } | |
| private: // fields | |
| size_t _size = 0; | |
| node *_head = nullptr; | |
| node *_tail = nullptr; | |
| }; | |
| #endif /* CIRCULAR_LIST_ */ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment