irrList.h

Go to the documentation of this file.

// Copyright (C) 2002-2012 Nikolaus Gebhardt
// This file is part of the "Irrlicht Engine".
// For conditions of distribution and use, see copyright notice in irrlicht.h

#ifndef __IRR_LIST_H_INCLUDED__
#define __IRR_LIST_H_INCLUDED__

#include "irrTypes.h"
#include "irrAllocator.h"
#include "irrMath.h"

namespace irr
{
namespace core
{


template <class T>
class list
{
private:

    struct SKListNode
    {
        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; }

        #if defined (_MSC_VER) && (_MSC_VER < 1300)
            #pragma warning(disable:4284) // infix notation problem when using iterator operator ->
        #endif

        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
    }


private:

    SKListNode* First;
    SKListNode* Last;
    u32 Size;
    irrAllocator<SKListNode> allocator;

};


} // end namespace core
}// end namespace irr

#endif