irrList.hpp

// Copyright (C) 2002-2012 Nikolaus Gebhardt
// This file is part of the "Irrlicht Engine".
// For conditions of distribution and use, see copyright notice in nirtcpp/nirtcpp.hpp
 
#ifndef NIRT_LIST_HPP_INCLUDED
#define NIRT_LIST_HPP_INCLUDED
 
#include <nirtcpp/core/engine/nirt_types.hpp>
#include <nirtcpp/core/engine/irrAllocator.hpp>
#include <nirtcpp/core/engine/irrMath.hpp>
 
namespace nirt
{
namespace core
{
 
 
template <class T>
class list
{
private:
 
    class SKListNode
    {
    public:
        SKListNode(const T& e) : Next(0), Prev(0), Element(e) {}
 
        SKListNode* Next;
        SKListNode* Prev;
        T Element;
    };
 
public:
    class ConstIterator;
 
    class Iterator
    {
    public:
        Iterator() : Current(0) {}
 
        Iterator& operator ++()    { Current = Current->Next; return *this; }
        Iterator& operator --()    { Current = Current->Prev; return *this; }
        Iterator  operator ++(s32) { Iterator tmp = *this; Current = Current->Next; return tmp; }
        Iterator  operator --(s32) { Iterator tmp = *this; Current = Current->Prev; return tmp; }
 
        Iterator& operator +=(s32 num)
        {
            if(num > 0)
            {
                while (num-- && this->Current != 0) ++(*this);
            }
            else
            {
                while(num++ && this->Current != 0) --(*this);
            }
            return *this;
        }
 
        Iterator  operator + (s32 num) const { Iterator tmp = *this; return tmp += num; }
        Iterator& operator -=(s32 num) { return (*this)+=(-num); }
        Iterator  operator - (s32 num) const { return (*this)+ (-num); }
 
        bool operator ==(const Iterator&      other) const { return Current == other.Current; }
        bool operator !=(const Iterator&      other) const { return Current != other.Current; }
        bool operator ==(const ConstIterator& other) const { return Current == other.Current; }
        bool operator !=(const ConstIterator& other) const { return Current != other.Current; }
 
        T & operator * () { return Current->Element; }
        T * operator ->() { return &Current->Element; }
 
    private:
        explicit Iterator(SKListNode* begin) : Current(begin) {}
 
        SKListNode* Current;
 
        friend class list<T>;
        friend class ConstIterator;
    };
 
    class ConstIterator
    {
    public:
 
        ConstIterator() : Current(0) {}
        ConstIterator(const Iterator& iter) : Current(iter.Current)  {}
 
        ConstIterator& operator ++()    { Current = Current->Next; return *this; }
        ConstIterator& operator --()    { Current = Current->Prev; return *this; }
        ConstIterator  operator ++(s32) { ConstIterator tmp = *this; Current = Current->Next; return tmp; }
        ConstIterator  operator --(s32) { ConstIterator tmp = *this; Current = Current->Prev; return tmp; }
 
        ConstIterator& operator +=(s32 num)
        {
            if(num > 0)
            {
                while(num-- && this->Current != 0) ++(*this);
            }
            else
            {
                while(num++ && this->Current != 0) --(*this);
            }
            return *this;
        }
 
        ConstIterator  operator + (s32 num) const { ConstIterator tmp = *this; return tmp += num; }
        ConstIterator& operator -=(s32 num) { return (*this)+=(-num); }
        ConstIterator  operator - (s32 num) const { return (*this)+ (-num); }
 
        bool operator ==(const ConstIterator& other) const { return Current == other.Current; }
        bool operator !=(const ConstIterator& other) const { return Current != other.Current; }
        bool operator ==(const Iterator&      other) const { return Current == other.Current; }
        bool operator !=(const Iterator&      other) const { return Current != other.Current; }
 
        const T & operator * () { return Current->Element; }
        const T * operator ->() { return &Current->Element; }
 
        ConstIterator & operator =(const Iterator & iterator) { Current = iterator.Current; return *this; }
 
    private:
        explicit ConstIterator(SKListNode* begin) : Current(begin) {}
 
        SKListNode* Current;
 
        friend class Iterator;
        friend class list<T>;
    };
 
    list()
        : First(0), Last(0), Size(0) {}
 
 
    list(const list<T>& other) : First(0), Last(0), Size(0)
    {
        *this = other;
    }
 
 
    ~list()
    {
        clear();
    }
 
 
    void operator=(const list<T>& other)
    {
        if(&other == this)
        {
            return;
        }
 
        clear();
 
        SKListNode* node = other.First;
        while(node)
        {
            push_back(node->Element);
            node = node->Next;
        }
    }
 
 
 
    u32 size() const
    {
        return Size;
    }
    u32 getSize() const
    {
        return Size;
    }
 
 
 
    void clear()
    {
        while(First)
        {
            SKListNode * next = First->Next;
            allocator.destruct(First);
            allocator.deallocate(First);
            First = next;
        }
 
        //First = 0; handled by loop
        Last = 0;
        Size = 0;
    }
 
 
 
    bool empty() const
    {
        return (First == 0);
    }
 
 
 
    void push_back(const T& element)
    {
        SKListNode* node = allocator.allocate(1);
        allocator.construct(node, element);
 
        ++Size;
 
        if (First == 0)
            First = node;
 
        node->Prev = Last;
 
        if (Last != 0)
            Last->Next = node;
 
        Last = node;
    }
 
 
 
    void push_front(const T& element)
    {
        SKListNode* node = allocator.allocate(1);
        allocator.construct(node, element);
 
        ++Size;
 
        if (First == 0)
        {
            Last = node;
            First = node;
        }
        else
        {
            node->Next = First;
            First->Prev = node;
            First = node;
        }
    }
 
 
 
    Iterator begin()
    {
        return Iterator(First);
    }
 
 
 
    ConstIterator begin() const
    {
        return ConstIterator(First);
    }
 
 
 
    Iterator end()
    {
        return Iterator(0);
    }
 
 
 
    ConstIterator end() const
    {
        return ConstIterator(0);
    }
 
 
 
    Iterator getLast()
    {
        return Iterator(Last);
    }
 
 
 
    ConstIterator getLast() const
    {
        return ConstIterator(Last);
    }
 
 
 
    void insert_after(const Iterator& it, const T& element)
    {
        SKListNode* node = allocator.allocate(1);
        allocator.construct(node, element);
 
        node->Next = it.Current->Next;
 
        if (it.Current->Next)
            it.Current->Next->Prev = node;
 
        node->Prev = it.Current;
        it.Current->Next = node;
        ++Size;
 
        if (it.Current == Last)
            Last = node;
    }
 
 
 
    void insert_before(const Iterator& it, const T& element)
    {
        SKListNode* node = allocator.allocate(1);
        allocator.construct(node, element);
 
        node->Prev = it.Current->Prev;
 
        if (it.Current->Prev)
            it.Current->Prev->Next = node;
 
        node->Next = it.Current;
        it.Current->Prev = node;
        ++Size;
 
        if (it.Current == First)
            First = node;
    }
 
 
 
    Iterator erase(Iterator& it)
    {
        // suggest changing this to a const Iterator& and
        // working around line: it.Current = 0 (possibly with a mutable, or just let it be garbage?)
 
        Iterator returnIterator(it);
        ++returnIterator;
 
        if(it.Current == First)
        {
            First = it.Current->Next;
        }
        else
        {
            it.Current->Prev->Next = it.Current->Next;
        }
 
        if(it.Current == Last)
        {
            Last = it.Current->Prev;
        }
        else
        {
            it.Current->Next->Prev = it.Current->Prev;
        }
 
        allocator.destruct(it.Current);
        allocator.deallocate(it.Current);
        it.Current = 0;
        --Size;
 
        return returnIterator;
    }
 
 
    void swap(list<T>& other)
    {
        core::swap(First, other.First);
        core::swap(Last, other.Last);
        core::swap(Size, other.Size);
        core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation
    }
 
    using value_type = T;
    using size_type = u32;
 
private:
 
    SKListNode* First;
    SKListNode* Last;
    u32 Size;
    irrAllocator<SKListNode> allocator;
 
};
 
 
} // end namespace core
}// end namespace nirt
 
#endif