DoubleLinkedList.h

// DoubleLinkedList.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2014

#pragma once
#ifndef Ceda_cxUtils_DoubleLinkedList_H
#define Ceda_cxUtils_DoubleLinkedList_H

#include "CedaAssert.h"
#include "cxUtils.h"

namespace ceda
{

///////////////////////////////////////////////////////////////////////////////////////////////////
// DoubleLinkedList<T>

// Similar to LinkedList<T> but without the concept of deleting the nodes.

template <typename T>      // Is is assumed that T inherits from DoubleLinkedList<T>::NodeBase
class DoubleLinkedList
{
public:
    struct NodeBase
    {
        NodeBase() : prev_(nullptr), next_(nullptr) {}
        NodeBase(const NodeBase& other) : prev_(nullptr), next_(nullptr) {}
        NodeBase& operator=(const NodeBase& other)
        {
            if (this != &other)
            {
                prev_ = nullptr;
                next_ = nullptr;
            }
            return *this;
        }

        T* prev_;
        T* next_;
    };

    DoubleLinkedList() : first_(nullptr), last_(nullptr), size_(0) {}

    void clear()
    {
        first_ = nullptr;
        last_ = nullptr;
        size_ = 0;
    }

    ssize_t size() const { return size_; }
    bool empty() const { return size_ == 0; }

    // Returns true if the given node is an element of this list
    bool has_element(const T* node) const
    {
        cxAssert(node);
        const T* p = first_;
        while(p)
        {
            if (p == node) return true;
            p = p->next_;
        }
        return false;
    }

    // Remove the given node from this list.  The given node is not deleted by this function.
    void erase(T* p)
    {
        cxAssert(p);
        //cxAssert(has_element(p));     // slows down debug build too much to assert this

        if (p->prev_)
        {
            cxAssert(p->prev_->next_ == p);
            p->prev_->next_ = p->next_;    
        }
        else
        {
            cxAssert(first_ == p);
            first_ = p->next_;
        }

        if (p->next_)
        {
            cxAssert(p->next_->prev_ == p);
            p->next_->prev_ = p->prev_;
        }
        else
        {
            cxAssert(last_ == p);
            last_ = p->prev_;
        }

        p->prev_ = nullptr;
        p->next_ = nullptr;
        --size_;
    }

    // It is an error to call this function if the list is empty.  The node at the front of the 
    // list is removed but not deleted by this function.
    T* erase_front()
    {
        cxAssert(first_);
        cxAssert(last_);
        T* p = first_;
        if (first_ == last_)
        {
            cxAssert(size_ == 1);
            first_ = last_ = nullptr;
        }
        else
        {
            cxAssert(size_ > 1);
            first_ = first_->next_;
            cxAssert(first_);
            first_->prev_ = nullptr;
        }
        p->prev_ = nullptr;
        p->next_ = nullptr;
        --size_;
        return p;
    }

    // It is an error to call this function if the list is empty.  The node at the front of the 
    // list is removed but not deleted by this function.
    T* erase_back()
    {
        cxAssert(first_);
        cxAssert(last_);
        T* p = last_;
        if (first_ == last_)
        {
            cxAssert(size_ == 1);
            first_ = last_ = nullptr;
        }
        else
        {
            cxAssert(size_ > 1);
            last_ = last_->prev_;
            cxAssert(last_);
            last_->next_ = nullptr;
        }
        p->prev_ = nullptr;
        p->next_ = nullptr;
        --size_;
        return p;
    }

    // The given node must have been allocated on the heap.  This linked list takes ownership of 
    // the given node
    void push_back(T* p)
    {
        cxAssert(p);
        cxAssert(p->prev_ == nullptr);
        cxAssert(p->next_ == nullptr);
        if (last_) 
        {
            cxAssert(last_ != p);
            cxAssert(first_);
            cxAssert(last_->next_ == nullptr);
            last_->next_ = p;
            p->prev_ = last_;
        }
        else
        {
            cxAssert(first_ == nullptr);
            first_ = p;
        }
        last_ = p;
        ++size_;
    }

    // The given node must have been allocated on the heap.  This linked list takes ownership of 
    // the given node
    void push_front(T* p)
    {
        cxAssert(p);
        cxAssert(p->prev_ == nullptr);
        cxAssert(p->next_ == nullptr);
        if (first_) 
        {
            cxAssert(first_ != p);
            cxAssert(last_);
            cxAssert(first_->prev_ == nullptr);
            first_->prev_ = p;
            p->next_ = first_;
        }
        else
        {
            cxAssert(last_ == nullptr);
            last_ = p;
        }
        first_ = p;
        ++size_;
    }

    class const_iterator
    {
    public:
        const_iterator(T* node) : node_(node) {}

        operator const T*() const { return node_; }
        
        const T& operator*() const { cxAssert(node_); return *node_; }
        const T* operator->() const { cxAssert(node_); return node_; }

        const_iterator& operator++() { cxAssert(node_); node_ = node_->next_; return *this; }
        const const_iterator operator++(int) { const_iterator it = *this; ++(*this); return it; }

        const_iterator& operator--() { cxAssert(node_); node_ = node_->prev_; return *this; }
        const const_iterator operator--(int) { const_iterator it = *this; --(*this); return it; }

        bool operator==(const const_iterator& other) const { return node_ == other.node_; }
        bool operator!=(const const_iterator& other) const { return node_ != other.node_; }

    protected:
        T* node_;
    };

    class iterator : public const_iterator
    {
    public:
        iterator(T* node) : const_iterator(node) {}

        operator T*() const { return this->node_; }

        T& operator*() const { cxAssert(this->node_); return *this->node_; }
        T* operator->() const { cxAssert(this->node_); return this->node_; }

        iterator& operator++() { cxAssert(this->node_); this->node_ = this->node_->next_; return *this; }
        const iterator operator++(int) { iterator it = *this; ++(*this); return it; }

        iterator& operator--() { cxAssert(this->node_); this->node_ = this->node_->prev_; return *this; }
        const iterator operator--(int) { iterator it = *this; --(*this); return it; }
    };

    // Insert node p immediately before the given position
    void insert_before(iterator pos, T* p)
    {
        cxAssert(p);
        cxAssert(p->prev_ == nullptr);
        cxAssert(p->next_ == nullptr);

        if ((T*)pos)
        {
            // cxAssert(HasElement(pos));   // slows down debug build too much to assert this

            p->prev_ = pos->prev_;
            p->next_ = pos;
            if (pos->prev_) 
            {
                cxAssert(pos->prev_->next_ == pos);
                pos->prev_->next_ = p;
            }
            else
            {
                cxAssert(first_ == pos);
                first_ = p;        
            }
            pos->prev_ = p;
            ++size_;
        }
        else
        {
            PushBack(p);
        }
    }

    const_iterator begin() const { return const_iterator(first_); }
    const_iterator end() const { return const_iterator(nullptr); }

    iterator begin() { return iterator(first_); }
    iterator end() { return iterator(nullptr); }

    T* front() const { return first_; }
    T* back() const { return last_; }

private:
    T* first_;
    T* last_;
    ssize_t size_;
};

} // namespace ceda

#endif // include guard