xor_list/XorList.h

//
// 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