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; }

                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
        }

        typedef T value_type;
        typedef u32 size_type;

private:

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

};


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

#endif