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>

template<typename T>
struct XorListNode {
public:
    XorListNode() = delete;

    XorListNode(const T &val) {
        val_ = val;
    }

    XorListNode(const T &&val) {
        val_ = std::forward<XorListNode<T> >(val);
    }

    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) {}

    // Must downcast from _List_node_base to _List_node to get to value.
    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 Allocator::template rebind<XorListNode<T>>::other allocator_type;
    typedef __gnu_cxx::__alloc_traits<allocator_type> Allocator_traits;

public:
    // types:
    typedef T value_type;
    typedef typename Allocator_traits::pointer pointer;
    typedef typename Allocator_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_(allocator_type()) {}

    XorList(size_type count, const_reference value = T(), const Allocator &alloc = Allocator())
            : front_(nullptr), back_(nullptr), size_(0), allocator_(allocator_type()) {
        for (size_type i = 0; i < count; i++)
            push_back(value);
    }

    XorList(const XorList &other) {
        *this = other;
    }

    XorList(const XorList &&other) noexcept {
        *this = other;
    }

    ~XorList() {
        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);
        }
    }

    XorList &operator=(const XorList &other) {
        if (this == &other)
            return *this;

        this->~XorList();
        this->front_ = other.front_;
        this->back_ = other.back_;
        this->size_ = other.size_;
        this->allocator_ = other.allocator_;
    }

    XorList &operator=(const XorList &&other) noexcept {
        if (this == &other)
            return *this;

        this->~XorList();
        this->front_ = other.front_;
        this->back_ = other.back_;
        this->size_ = other.size_;
        this->allocator_ = other.allocator_;
    }

    value_type front() {
        return front_->val_;
    }

    value_type back() {
        return back_->val_;
    }

    iterator begin() {
        return iterator(front_, nullptr);
    }

    iterator end() {
        if (!back_)
            return iterator(nullptr, nullptr);
        return ++iterator(back_, back_->left(nullptr));
    }

    reverse_iterator rbegin() {
        return reverse_iterator(front_, nullptr);
    }

    reverse_iterator rend() {
        return ++reverse_iterator(back_, back_->left(nullptr));
    }

    size_type size() {
        return size_;
    }

    void push_back(const value_type &val) {
        XorListNode<T> *past_back = back_;
        back_ = reinterpret_cast<XorListNode<T> *>(allocator_.allocate(1));
        allocator_.construct(back_, std::forward<XorListNode<T> >(val));
        back_->assign_leftright(past_back, nullptr);
        if (past_back)
            past_back->assign_leftright(past_back->left(nullptr), back_);
        if (!front_)
            front_ = back_;
        size_++;
    }

    void push_back(const value_type &&val) {
        XorListNode<value_type> *past_back = back_;
        back_ = reinterpret_cast<XorListNode<T> *>(allocator_.allocate(1));
        allocator_.construct(back_, XorListNode<T>(std::forward<XorListNode<T> >(val)));
        back_->assign_leftright(past_back, nullptr);
        if (past_back)
            past_back->assign_leftright(past_back->left(nullptr), back_);
        if (!front_)
            front_ = back_;
        size_++;
    }

    void push_front(const value_type &val) {
        XorListNode<value_type> *past_front = front_;
        front_ = reinterpret_cast<XorListNode<T> *>(allocator_.allocate(1));
        allocator_.construct(front_, std::forward<XorListNode<T> >(val));
        front_->assign_leftright(nullptr, past_front);
        if (past_front)
            past_front->assign_leftright(front_, past_front->right(nullptr));
        if (!back_)
            back_ = front_;
        size_++;
    }

    void push_front(const value_type &&val) {
        XorListNode<value_type> *past_front = front_;
        front_ = reinterpret_cast<XorListNode<T> *>(allocator_.allocate(1));
        allocator_.construct(front_, std::forward<XorListNode<T> >(val));
        front_->assign_leftright(nullptr, past_front);
        if (past_front)
            past_front->assign_leftright(front_,  past_front->right(nullptr));
        if (!back_)
            back_ = front_;
        size_++;
    }

    void pop_back() {
        XorListNode<T> *past_back = back_;
        back_ = back_->left(nullptr);
        back_->assign_leftright(back_->left(past_back), nullptr);
        allocator_.destroy(past_back);
        allocator_.deallocate(past_back, 1);
    }

    void pop_front() {
        XorListNode<T> *past_front = front_;
        front_ = front_->right(nullptr);
        front_->assign_leftright(nullptr, front_->right(past_front));
        allocator_.destroy(past_front);
        allocator_.deallocate(past_front, 1);
    }

    void insert_before(iterator it, T &val) {
        XorListNode<T> *cur = *it;
        XorListNode<T> *prev = it.left_;
        XorListNode<T> *past = it.node_->right(prev);

        XorListNode<T> *new_node = reinterpret_cast<XorListNode<T> *>(allocator_.allocate(1));
        allocator_.construct(new_node, std::forward<XorListNode<T> >(val));
        new_node->assign_leftright(prev, cur);

        if (cur)
            cur->assign_leftright(new_node, past);

        if (prev)
            prev->assign_leftright(prev->left(cur), new_node);
    }

    void insert_before(iterator it, T &&val) {
        XorListNode<T> *cur = *it;
        XorListNode<T> *prev = it.left_;
        XorListNode<T> *past = it.node_->right(prev);

        XorListNode<T> *new_node = allocator_.allocate(1);
        allocator_.construct(new_node, std::forward<XorListNode<T> >(val));
        new_node->assign_leftright(prev, cur);

        if (cur)
            cur->assign_leftright(new_node, past);

        if (prev)
            prev->assign_leftright(prev->left(cur), new_node);
    }

    void insert_after(iterator it, T &val) {
        XorListNode<T> *cur = *it;
        XorListNode<T> *prev = it.left_;
        XorListNode<T> *past = it.node_->right(prev);

        XorListNode<T> *new_node = allocator_.allocate(1);
        allocator_.construct(new_node, std::forward<XorListNode<T> >(val));
        new_node->assign_leftright(cur, past);

        if (cur)
            cur->assign_leftright(prev, new_node);

        if (past)
            past->assign_leftright(new_node, past->right(cur));
    }

    void insert_after(iterator it, T &&val) {
        XorListNode<T> *cur = *it;
        XorListNode<T> *prev = it.left_;
        XorListNode<T> *past = it.node_->right(prev);

        XorListNode<T> *new_node = allocator_.allocate(1);
        allocator_.construct(new_node, std::forward<XorListNode<T> >(val));
        new_node->assign_leftright(cur, past);

        if (cur)
            cur->assign_leftright(prev, new_node);

        if (past)
            past->assign_leftright(new_node, past->right(cur));
    }

    void erase(iterator it) {
        XorListNode<T> *prev = it.left_;
        XorListNode<T> *cur = it.operator->();
        XorListNode<T> *past = it.node_->right(prev);

        if (prev)
            prev->assign_leftright(prev->left(cur), past);

        if (past)
            past->assign_leftright(prev, past->right(cur));

        if (cur)
            size_--;

        allocator_.destroy(cur);
        allocator_.deallocate(cur, 1);
    }

private:
    XorListNode<T> *front_;
    XorListNode<T> *back_; // Pointer to the LAST element

    size_type size_;
    allocator_type allocator_;

};

#endif //XOR_LIST_XORLIST_H