123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362 |
- //
- // Created by kikab on 06.05.2018.
- //
- #ifndef XOR_LIST_XORLIST_H
- #define XOR_LIST_XORLIST_H
- #include <forward_list>
- #include <bits/allocator.h>
- #include <ext/alloc_traits.h>
- #include <vector>
- #include <list>
- #include <memory>
- #include <utility>
- #include <iostream>
- #include <stdexcept>
- template<typename T>
- struct XorListNode {
- public:
- XorListNode() = delete;
- explicit XorListNode(const T &val) {
- val_ = val;
- }
- explicit XorListNode(T &&val) {
- val_ = std::move(val);//std::forward<T>(val);
- //std::cout << "move-constructor\n";
- }
- XorListNode *right(const XorListNode *left) const {
- return reinterpret_cast<XorListNode *>(xor_ptr_ ^ reinterpret_cast<uintptr_t>(left));
- }
- XorListNode *left(const XorListNode *right) const {
- return reinterpret_cast<XorListNode *>(xor_ptr_ ^ reinterpret_cast<uintptr_t>(right));
- }
- void assign_leftright(const XorListNode *left, const XorListNode *right) {
- xor_ptr_ = (reinterpret_cast<uintptr_t>(left) ^ reinterpret_cast<uintptr_t>(right));
- }
- T val_;
- private:
- uintptr_t xor_ptr_;
- };
- template<typename T>
- struct FwdXorListIterator {
- typedef FwdXorListIterator<T> Self;
- typedef XorListNode<T> Node;
- typedef ptrdiff_t difference_type;
- typedef std::bidirectional_iterator_tag iterator_category;
- typedef T value_type;
- typedef T *pointer;
- typedef T &reference;
- FwdXorListIterator() = delete;
- FwdXorListIterator(Node *x, Node *prev) : node_(x), left_(prev) {}
- reference operator*() const {
- return node_->val_;
- }
- pointer operator->() const {
- return &node_->val_;
- }
- Self &operator++() {
- Node *future_left_ = node_;
- node_ = node_->right(left_);
- left_ = future_left_;
- return *this;
- }
- Self operator++(int) {
- Self __tmp = *this;
- Node *future_left_ = node_;
- node_ = node_->right(left_);
- left_ = future_left_;
- return __tmp;
- }
- Self &operator--() {
- Node *future_right = node_;
- node_ = node_->left(node_->right(left_));
- left_ = node_->left(future_right);
- return *this;
- }
- Self operator--(int) {
- Self __tmp = *this;
- Node *future_right = node_;
- node_ = node_->left(node_->right(left_));
- left_ = node_->left(future_right);
- return __tmp;
- }
- bool operator==(const Self &x) const {
- return left_ == x.left_;
- }
- bool operator!=(const Self &x) const {
- return left_ != x.left_;
- }
- Node *node_;
- Node *left_;
- };
- template<typename T, typename Allocator = std::allocator<T> >
- class XorList {
- private:
- typedef typename __gnu_cxx::__alloc_traits<Allocator>::template
- rebind<T>::other T_alloc_type;
- typedef __gnu_cxx::__alloc_traits<T_alloc_type> T_alloc_traits;
- typedef typename T_alloc_traits::template rebind<XorListNode<T> >::other Node_alloc_type;
- typedef __gnu_cxx::__alloc_traits<Node_alloc_type> Node_alloc_traits;
- public:
- // types:
- typedef T value_type;
- typedef typename T_alloc_traits::pointer pointer;
- typedef typename T_alloc_traits::const_pointer const_pointer;
- typedef value_type &reference;
- typedef const value_type &const_reference;
- typedef FwdXorListIterator<T> iterator;
- typedef std::reverse_iterator<iterator> reverse_iterator;
- typedef std::size_t size_type;
- typedef std::ptrdiff_t difference_type;
- //typedef Allocator allocator_type;
- explicit XorList(const Allocator &alloc = Allocator())
- : front_(nullptr), back_(nullptr), size_(0), allocator_(Node_alloc_type(alloc)) {}
- explicit XorList(size_type count, const_reference value = T(), const Allocator &alloc = Allocator())
- : front_(nullptr), back_(nullptr), size_(0), allocator_(Node_alloc_type(alloc)) {
- for (size_type i = 0; i < count; i++)
- push_back(value);
- }
- XorList &operator=(const XorList &other) {
- if (this == &other)
- return *this;
- clear();
- allocator_ = Node_alloc_type(other.allocator_);
- front_ = back_ = nullptr;
- size_ = 0;
- for (const auto& i: other)
- push_back(i);
- std::cout << "Copy assignment\n";
- return *this;
- }
- XorList &operator=(XorList &&other) noexcept {
- if (this == &other)
- return *this;
- clear();
- this->front_ = other.front_;
- this->back_ = other.back_;
- this->size_ = other.size_;
- this->allocator_ = std::move(other.allocator_);
- other.front_ = other.back_ = nullptr;
- other.size_ = 0;
- std::cout << "Move assignment\n";
- return *this;
- }
- ~XorList() {
- clear();
- }
- template <typename xorlist_t>
- explicit XorList(xorlist_t &&other) noexcept : XorList() {
- *this = std::forward<xorlist_t>(other);
- }
- value_type front() const {
- return front_->val_;
- }
- value_type back() const {
- return back_->val_;
- }
- iterator begin() const {
- return iterator(front_, nullptr);
- }
- iterator end() const {
- if (!back_)
- return iterator(nullptr, nullptr);
- return ++iterator(back_, back_->left(nullptr));
- }
- reverse_iterator rbegin() const {
- return reverse_iterator(front_, nullptr);
- }
- reverse_iterator rend() const {
- return ++reverse_iterator(back_, back_->left(nullptr));
- }
- size_type size() const {
- return size_;
- }
- template<typename v_type>
- void push_back(v_type &&val) {
- insert_after(iterator(back_, back_ ? back_->left(nullptr) : nullptr), std::forward<v_type>(val));
- }
- template<typename v_type>
- void push_front(v_type &&val) {
- insert_before(iterator(front_, nullptr), std::forward<v_type>(val));
- }
- template<typename v_type>
- void insert_before(iterator it, v_type &&val) {
- _m_insert(it, std::forward<v_type>(val), BEFORE);
- }
- template<typename v_type>
- void insert_after(iterator it, v_type &&val) {
- _m_insert(it, std::forward<v_type>(val), AFTER);
- }
- void pop_back() {
- if (!back_)
- return;
- erase(iterator(back_, back_->left(nullptr)));
- }
- void pop_front() {
- if (!front_)
- return;
- erase(iterator(front_, nullptr));
- }
- void erase(iterator it) {
- XorListNode<T> *left = it.left_;
- XorListNode<T> *cur = it.node_;
- XorListNode<T> *right = it.node_->right(left);
- if (left)
- left->assign_leftright(left->left(cur), right);
- if (right)
- right->assign_leftright(left, right->right(cur));
- if (cur) {
- size_--;
- if (front_ == cur)
- front_ = cur->right(nullptr);
- if (back_ == cur)
- back_ = cur->left(nullptr);
- }
- allocator_.destroy(cur);
- allocator_.deallocate(cur, 1);
- }
- void clear() {
- XorListNode<T> *xleft = nullptr;
- XorListNode<T> *x = front_;
- while (x != back_) {
- XorListNode<T> *xnext = x->right(xleft);
- if (xnext) {
- allocator_.destroy(xleft);
- allocator_.deallocate(xleft, 1);
- }
- xleft = x;
- x = xnext;
- }
- if (xleft) {
- allocator_.destroy(xleft);
- allocator_.deallocate(xleft, 1);
- }
- if (x) {
- allocator_.destroy(x);
- allocator_.deallocate(x, 1);
- }
- size_ = 0;
- front_ = back_ = nullptr;
- }
- private:
- enum E_POSITION_TYPE {
- BEFORE,
- AFTER
- };
- template<typename v_type>
- void _m_insert(iterator it, v_type &&val, E_POSITION_TYPE pos) {
- XorListNode<T> *cur = it.node_;
- XorListNode<T> *left = it.left_;
- XorListNode<T> *new_node = reinterpret_cast<XorListNode<T> *>(allocator_.allocate(1));
- Node_alloc_traits::construct(allocator_, new_node, std::forward<v_type>(val));
- new_node->assign_leftright(nullptr, nullptr);
- if (!front_ || !back_) {
- front_ = back_ = new_node;
- size_ = 1;
- return;
- }
- XorListNode<T> *right = it.node_->right(left);
- if (pos == BEFORE) {
- new_node->assign_leftright(left, cur);
- cur->assign_leftright(new_node, right);
- if (left)
- left->assign_leftright(left->left(cur), new_node);
- if (cur == front_)
- front_ = new_node;
- }
- if (pos == AFTER) {
- new_node->assign_leftright(cur, right);
- cur->assign_leftright(left, new_node);
- if (right)
- right->assign_leftright(new_node, right->right(cur));
- if (cur == back_)
- back_ = new_node;
- }
- size_++;
- }
- private:
- XorListNode<T> *front_;
- XorListNode<T> *back_; // Pointer to the LAST element
- size_type size_;
- Node_alloc_type allocator_;
- };
- #endif //XOR_LIST_XORLIST_H
|