KviPointerList.h

Go to the documentation of this file.

#ifndef _KVI_POINTERLIST_H_
#define _KVI_POINTERLIST_H_
//===============================================================================
//
//   File : KviPointerList.h
//   Creation date : Tue Jul 6 1999 14:52:20 by Szymon Stefanek
//
//   This file is part of the KVIrc IRC client distribution
//   Copyright (C) 1999-2010 Szymon Stefanek (pragma at kvirc dot net)
//
//   This program is FREE software. You can redistribute it and/or
//   modify it under the terms of the GNU General Public License
//   as published by the Free Software Foundation; either version 2
//   of the License, or (at your option) any later version.
//
//   This program is distributed in the HOPE that it will be USEFUL,
//   but WITHOUT ANY WARRANTY; without even the implied warranty of
//   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
//   See the GNU General Public License for more details.
//
//   You should have received a copy of the GNU General Public License
//   along with this program. If not, write to the Free Software Foundation,
//   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
//
//===============================================================================
//
//   C++ Template based double linked pointer list class
//   Original ss_list.h Created on 10 Dec 2001
//   Copyright (C) 2001-2010 Szymon Stefanek (pragma at kvirc dot net)
//   Added to KVIrc on 02 Jan 2008.
//
//===============================================================================

#include "kvi_settings.h"

template <typename T>
class KviPointerList;
template <typename T>
class KviPointerListIterator;

#ifndef NULL
#define NULL 0
#endif

class KviPointerListNode
{
public:
        KviPointerListNode * m_pPrev;
        void * m_pData;
        KviPointerListNode * m_pNext;
};

template <typename T>
class KviPointerListIterator
{
protected:
        KviPointerList<T> * m_pList;
        KviPointerListNode * m_pNode;

public:
        KviPointerListIterator(const KviPointerListIterator<T> & src)
        {
                m_pList = src.m_pList;
                m_pNode = src.m_pNode;
        }

        KviPointerListIterator(KviPointerList<T> & l)
        {
                m_pList = (KviPointerList<T> *)&l;
                m_pNode = m_pList->m_pHead;
        }

        KviPointerListIterator(KviPointerList<T> & l, KviPointerListNode * pNode)
        {
                m_pList = (KviPointerList<T> *)&l;
                m_pNode = pNode;
        }

        void operator=(const KviPointerListIterator<T> & src)
        {
                m_pList = src.m_pList;
                m_pNode = src.m_pNode;
        }

public:
        bool moveFirst()
        {
                m_pNode = m_pList->m_pHead;
                return m_pNode != NULL;
        }

        bool moveLast()
        {
                m_pNode = m_pList->m_pTail;
                return m_pNode != NULL;
        }

        bool moveNext()
        {
                if(!m_pNode)
                        return false;
                m_pNode = m_pNode->m_pNext;
                return m_pNode != NULL;
        }

        bool operator++()
        {
                if(!m_pNode)
                        return false;
                m_pNode = m_pNode->m_pNext;
                return m_pNode != NULL;
        }

        bool movePrev()
        {
                if(!m_pNode)
                        return false;
                m_pNode = m_pNode->m_pPrev;
                return m_pNode != NULL;
        }

        bool operator--()
        {
                if(!m_pNode)
                        return false;
                m_pNode = m_pNode->m_pPrev;
                return m_pNode != NULL;
        }

        T * current()
        {
                return m_pNode ? (T *)(m_pNode->m_pData) : NULL;
        }

        T * operator*()
        {
                return m_pNode ? (T *)(m_pNode->m_pData) : NULL;
        }

        bool isValid()
        {
                return m_pNode != NULL;
        }
};

template <typename T>
class KviPointerList
{
        friend class KviPointerListIterator<T>;

protected:
        bool m_bAutoDelete; //< do we automatically delete items when they are removed ?

        KviPointerListNode * m_pHead; //< our list head pointer (NULL if there are no items in the list)
        KviPointerListNode * m_pTail; //< our list tail
        KviPointerListNode * m_pAux;  //< our iteration pointer

        unsigned int m_uCount; //< the count of items in the list
protected:
        void insertBeforeSafe(KviPointerListNode * ref, const T * d)
        {
                m_pAux = ref;
                KviPointerListNode * n = new KviPointerListNode;
                n->m_pPrev = m_pAux->m_pPrev;
                n->m_pNext = m_pAux;
                if(m_pAux->m_pPrev)
                {
                        m_pAux->m_pPrev->m_pNext = n;
                }
                else
                {
                        m_pHead = n;
                }
                m_pAux->m_pPrev = n;
                n->m_pData = (void *)d;
                m_uCount++;
        }

        void grabFirstAndPrepend(KviPointerList<T> * src)
        {
                KviPointerListNode * pNewHead = src->m_pHead;
                if(!pNewHead)
                        return;

                if(pNewHead->m_pNext)
                {
                        src->m_pHead = pNewHead->m_pNext;
                        src->m_pHead->m_pPrev = NULL;
                }
                else
                {
                        src->m_pHead = NULL;
                        src->m_pTail = NULL;
                }

                if(m_pHead)
                {
                        m_pHead->m_pPrev = pNewHead;
                        pNewHead->m_pNext = m_pHead;
                        m_pHead = pNewHead;
                }
                else
                {
                        m_pHead = pNewHead;
                        m_pTail = pNewHead;
                        m_pHead->m_pNext = NULL;
                }
                m_uCount++;
                src->m_uCount--;
        }

        void removeCurrentSafe()
        {
                if(m_pAux->m_pPrev)
                        m_pAux->m_pPrev->m_pNext = m_pAux->m_pNext;
                else
                        m_pHead = m_pAux->m_pNext;
                if(m_pAux->m_pNext)
                        m_pAux->m_pNext->m_pPrev = m_pAux->m_pPrev;
                else
                        m_pTail = m_pAux->m_pPrev;
                const T * pAuxData = (const T *)(m_pAux->m_pData);
                delete m_pAux;
                m_pAux = NULL;
                m_uCount--;
                if(m_bAutoDelete)
                        delete pAuxData; // this can cause recursion, so do it at the end
        }

public:
        void merge(KviPointerList<T> * src)
        {
                m_pAux = m_pHead;
                KviPointerListNode * n = src->m_pHead;
                m_uCount += src->m_uCount;
                while(m_pAux && n)
                {
                        if(kvi_compare((const T *)(m_pAux->m_pData), (const T *)(n->m_pData)) > 0)
                        {
                                // our element is greater, n->m_pData goes first
                                KviPointerListNode * pNext = n->m_pNext;
                                n->m_pPrev = m_pAux->m_pPrev; // his prev becomes
                                n->m_pNext = m_pAux;
                                if(m_pAux->m_pPrev)
                                        m_pAux->m_pPrev->m_pNext = n;
                                else
                                        m_pHead = n;
                                m_pAux->m_pPrev = n;
                                n = pNext;
                        }
                        else
                        {
                                // that element is greater
                                m_pAux = m_pAux->m_pNext;
                        }
                }
                if(n)
                {
                        // last items to append
                        if(m_pTail)
                        {
                                m_pTail->m_pNext = n;
                                n->m_pPrev = m_pTail;
                        }
                        else
                        {
                                m_pHead = n;
                                m_pTail = n;
                                n->m_pPrev = NULL;
                        }
                        m_pTail = src->m_pTail;
                }

                src->m_pHead = NULL;
                src->m_pTail = NULL;
                src->m_uCount = 0;
        }

        void swap(KviPointerList<T> * src)
        {
                KviPointerListNode * n = m_pHead;
                m_pHead = src->m_pHead;
                src->m_pHead = n;
                n = m_pTail;
                m_pTail = src->m_pTail;
                src->m_pTail = n;
                unsigned int uCount = m_uCount;
                m_uCount = src->m_uCount;
                src->m_uCount = uCount;
        }

        void sort()
        {
                if(m_uCount < 2)
                        return;

                KviPointerList<T> carry;
                KviPointerList<T> tmp[64];
                KviPointerList * fill = &tmp[0];
                KviPointerList * counter;

                do
                {
                        carry.grabFirstAndPrepend(this);

                        for(counter = &tmp[0]; counter != fill && !counter->isEmpty(); ++counter)
                        {
                                counter->merge(&carry);
                                carry.swap(counter);
                        }
                        carry.swap(counter);
                        if(counter == fill)
                                ++fill;
                } while(m_uCount > 0);

                for(counter = &tmp[1]; counter != fill; ++counter)
                        counter->merge(counter - 1);
                swap(fill - 1);
        }

        void inSort(T * t)
        {
                KviPointerListNode * x = m_pHead;
                while(x && (kvi_compare(((T *)x->m_pData), t) > 0))
                        x = x->m_pNext;
                if(!x)
                        append(t);
                else
                        insertBeforeSafe(x, t);
        }

        bool isEmpty() const
        {
                return (m_pHead == NULL);
        }

        unsigned int count() const
        {
                return m_uCount;
        }

        T * first()
        {
                if(!m_pHead)
                {
                        m_pAux = NULL;
                        return NULL;
                }
                m_pAux = m_pHead;
                return (T *)(m_pAux->m_pData);
        }

        T * takeFirst()
        {
                if(!m_pHead)
                        return NULL;
                T * pData = (T *)m_pHead->m_pData;
                if(m_pHead->m_pNext)
                {
                        m_pHead = m_pHead->m_pNext;
                        delete m_pHead->m_pPrev;
                        m_pHead->m_pPrev = NULL;
                }
                else
                {
                        delete m_pHead;
                        m_pHead = NULL;
                        m_pTail = NULL;
                }
                m_pAux = NULL;
                m_uCount--;
                return pData;
        }

        T * takeLast()
        {
                if(!m_pTail)
                        return NULL;
                T * pData = (T *)m_pTail->m_pData;
                if(m_pTail->m_pPrev)
                {
                        m_pTail = m_pTail->m_pPrev;
                        delete m_pTail->m_pNext;
                        m_pTail->m_pNext = NULL;
                }
                else
                {
                        delete m_pTail;
                        m_pHead = NULL;
                        m_pTail = NULL;
                }
                m_pAux = NULL;
                m_uCount--;
                return pData;
        }

        KviPointerListIterator<T> iteratorAtFirst()
        {
                return KviPointerListIterator<T>(*this, m_pHead);
        }

        T * last()
        {
                if(!m_pTail)
                {
                        m_pAux = NULL;
                        return NULL;
                }
                m_pAux = m_pTail;
                return (T *)(m_pAux->m_pData);
        }

        KviPointerListIterator<T> iteratorAtLast()
        {
                return KviPointerListIterator<T>(*this, m_pTail);
        }

        T * current()
        {
                return (T *)(m_pAux->m_pData);
        }

        T * safeCurrent()
        {
                return m_pAux ? (T *)(m_pAux->m_pData) : NULL;
        }

        KviPointerListIterator<T> iteratorAtCurrent()
        {
                return KviPointerListIterator<T>(*this, m_pAux);
        }

        T * next()
        {
                if(!m_pAux)
                        return NULL;
                m_pAux = m_pAux->m_pNext;
                if(m_pAux)
                        return (T *)(m_pAux->m_pData);
                return NULL;
        }

        T * prev()
        {
                if(!m_pAux)
                        return NULL;
                m_pAux = m_pAux->m_pPrev;
                if(m_pAux)
                        return (T *)(m_pAux->m_pData);
                return NULL;
        }

        T * at(int idx)
        {
                T * t = first();
                int cnt = 0;
                while(t)
                {
                        if(idx == cnt)
                                return t;
                        t = next();
                        cnt++;
                }
                return 0;
        }

        KviPointerListIterator<T> iteratorAt(int idx)
        {
                KviPointerListNode * n = m_pHead;
                int cnt = 0;
                while(n)
                {
                        if(idx == cnt)
                                return KviPointerListIterator<T>(*this, n);
                        n = n->m_pNext;
                        cnt++;
                }
                return KviPointerListIterator<T>(*this, NULL);
        }

        int findRef(const T * d)
        {
                int ret = 0;
                for(T * t = first(); t; t = next())
                {
                        if(t == d)
                                return ret;
                        ret++;
                }
                return -1;
        }

        KviPointerListIterator<T> iteratorAtRef(const T * d)
        {
                KviPointerListNode * n = m_pHead;
                while(n)
                {
                        if(n->m_pData == d)
                                return KviPointerListIterator<T>(*this, n);
                        n = n->m_pNext;
                }
                return KviPointerListIterator<T>(*this, NULL);
        }

        void append(const T * d)
        {
                if(!m_pHead)
                {
                        m_pHead = new KviPointerListNode;
                        m_pHead->m_pPrev = NULL;
                        m_pHead->m_pNext = NULL;
                        m_pHead->m_pData = (void *)d;
                        m_pTail = m_pHead;
                }
                else
                {
                        m_pTail->m_pNext = new KviPointerListNode;
                        m_pTail->m_pNext->m_pPrev = m_pTail;
                        m_pTail->m_pNext->m_pNext = NULL;
                        m_pTail->m_pNext->m_pData = (void *)d;
                        m_pTail = m_pTail->m_pNext;
                }
                m_uCount++;
        }

        void append(KviPointerList<T> * l)
        {
                for(T * t = l->first(); t; t = l->next())
                        append(t);
        }

        void prepend(KviPointerList<T> * l)
        {
                for(T * t = l->last(); t; t = l->prev())
                        prepend(t);
        }

        void prepend(const T * d)
        {
                if(!m_pHead)
                {
                        m_pHead = new KviPointerListNode;
                        m_pHead->m_pPrev = NULL;
                        m_pHead->m_pNext = NULL;
                        m_pHead->m_pData = (void *)d;
                        m_pTail = m_pHead;
                }
                else
                {
                        m_pHead->m_pPrev = new KviPointerListNode;
                        m_pHead->m_pPrev->m_pNext = m_pHead;
                        m_pHead->m_pPrev->m_pPrev = NULL;
                        m_pHead->m_pPrev->m_pData = (void *)d;
                        m_pHead = m_pHead->m_pPrev;
                        m_uCount++;
                }
        }

        void insert(int iIndex, const T * d)
        {
                m_pAux = m_pHead;
                while(m_pAux && iIndex > 0)
                {
                        iIndex--;
                        m_pAux = m_pAux->m_pNext;
                }
                if(m_pAux)
                        insertBeforeSafe(m_pAux, d);
                else
                        append(d);
        }

        bool removeFirst()
        {
                if(!m_pHead)
                        return false;
                const T * pAuxData;
                if(m_pHead->m_pNext)
                {
                        m_pHead = m_pHead->m_pNext;
                        pAuxData = (const T *)(m_pHead->m_pPrev->m_pData);
                        delete m_pHead->m_pPrev;
                        m_pHead->m_pPrev = NULL;
                }
                else
                {
                        pAuxData = (const T *)(m_pHead->m_pData);
                        delete m_pHead;
                        m_pHead = NULL;
                        m_pTail = NULL;
                }
                m_pAux = NULL;
                m_uCount--;
                if(m_bAutoDelete)
                        delete pAuxData;
                return true;
        }

        bool removeLast()
        {
                if(!m_pTail)
                        return false;
                const T * pAuxData;
                if(m_pTail->m_pPrev)
                {
                        m_pTail = m_pTail->m_pPrev;
                        pAuxData = (const T *)(m_pTail->m_pNext->m_pData);
                        delete m_pTail->m_pNext;
                        m_pTail->m_pNext = NULL;
                }
                else
                {
                        pAuxData = (const T *)(m_pTail->m_pData);
                        delete m_pTail;
                        m_pHead = NULL;
                        m_pTail = NULL;
                }
                m_pAux = NULL;
                m_uCount--;
                if(m_bAutoDelete)
                        delete pAuxData;
                return true;
        }

        bool remove(int iIndex)
        {
                m_pAux = m_pHead;
                while(m_pAux && iIndex > 0)
                {
                        iIndex--;
                        m_pAux = m_pAux->m_pNext;
                }
                if(!m_pAux)
                        return false;
                removeCurrentSafe();
                return true;
        }

        void setAutoDelete(bool bAutoDelete)
        {
                m_bAutoDelete = bAutoDelete;
        }

        bool autoDelete()
        {
                return m_bAutoDelete;
        };

        void clear()
        {
                while(m_pHead)
                        removeFirst();
        }

        bool removeCurrent()
        {
                if(!m_pAux)
                        return false;
                removeCurrentSafe();
                return true;
        }

        bool removeRef(const T * d)
        {
                if(findRef(d) == -1)
                        return false;
                removeCurrentSafe();
                return true;
        }

        void insertAfter(const T * ref, const T * d)
        {
                if(findRef(ref) == -1)
                {
                        append(d);
                        return;
                }
                KviPointerListNode * n = new KviPointerListNode;
                n->m_pPrev = m_pAux;
                n->m_pNext = m_pAux->m_pNext;
                if(m_pAux->m_pNext)
                        m_pAux->m_pNext->m_pPrev = n;
                else
                        m_pTail = n;
                m_pAux->m_pNext = n;
                n->m_pData = (void *)d;
                m_uCount++;
        }

        void insertBefore(const T * ref, const T * d)
        {
                if(findRef(ref) == -1)
                {
                        prepend(d);
                        return;
                }
                KviPointerListNode * n = new KviPointerListNode;
                n->m_pPrev = m_pAux->m_pPrev;
                n->m_pNext = m_pAux;
                if(m_pAux->m_pPrev)
                        m_pAux->m_pPrev->m_pNext = n;
                else
                        m_pHead = n;
                m_pAux->m_pPrev = n;
                n->m_pData = (void *)d;
                m_uCount++;
        }

        void invert()
        {
                if(!m_pHead)
                        return;
                KviPointerListNode * oldHead = m_pHead;
                KviPointerListNode * oldTail = m_pTail;
                KviPointerListNode * n = m_pHead;
                while(n)
                {
                        KviPointerListNode * next = n->m_pNext;
                        n->m_pNext = n->m_pPrev;
                        n->m_pPrev = next;
                        n = next;
                }
                m_pTail = oldHead;
                m_pHead = oldTail;
        }

        void copyFrom(KviPointerList<T> * l)
        {
                clear();
                for(T * t = l->first(); t; t = l->next())
                        append(t);
        }

        KviPointerList<T> & operator=(KviPointerList<T> & l)
        {
                copyFrom(&l);
                return *this;
        }

        KviPointerList<T>(bool bAutoDelete = true)
        {
                m_bAutoDelete = bAutoDelete;
                m_pHead = NULL;
                m_pTail = NULL;
                m_uCount = 0;
                m_pAux = NULL;
        };

        virtual ~KviPointerList<T>()
        {
                clear();
        };
};

#define KviPointerListBase KviPointerList

// BROKEN MSVC LINKER
#ifdef COMPILE_ON_WINDOWS
#include "KviCString.h"
template class KVILIB_API KviPointerList<KviCString>;
#endif

// Provide a default implementation of kvi_compare()
template <typename T>
int kvi_compare(const T * p1, const T * p2)
{
        return p1 > p2; // just compare pointers
}

#endif //_KVI_POINTERLIST_H_