eC_TList_doubleLinked.h

/*
* Copyright (C) TES Electronic Solutions GmbH,
* All Rights Reserved.
* Contact: info@guiliani.de
*
* This file is part of the Guiliani HMI framework
* for the development of graphical user interfaces on embedded systems.
*/
 
#ifndef EC_TL__H_
#define EC_TL__H_
 
//Iterator implementation
#include "eC_TList_Iterators.h"
#include <cassert>
 
// memory-mapping
#include "eC_CustomMemoryMapping.h"
 
template <class T>
class ListNode
{
public:
    ListNode() : m_tValue()
    {
        m_pkNext = NULL;
        m_pkPrevious = NULL;
    }
 
    //-------------------------------------
    ~ListNode() {}
 
    //-------------------------------------
 
    ListNode* m_pkNext;
 
    ListNode* m_pkPrevious;
 
    T m_tValue;
};
 
 
//----------------------------------------------------------------------------
 
 
template <class T>
class eC_TListDoubleLinked
{
    typedef ListNode<T> Node; 
 
    friend class eC_TSafeIterator<T>; 
 
public:
    typedef eC_TIterator<T> Iterator;
 
    typedef eC_TSafeIterator<T> SafeIterator;
 
    typedef bool(*compare)(T lhs, T rhs);
 
    eC_TListDoubleLinked();
 
    eC_TListDoubleLinked(const eC_TListDoubleLinked<T>& copy);
 
    ~eC_TListDoubleLinked();
 
    eC_UInt GetQuantity() const;
 
    eC_Bool IsEmpty() const;
 
    void Add(const T &tValue);
 
    void AddAtEnd(const T &tValue);
 
    void AddBefore(const T &tValue2Add, Iterator & kIter);
 
    void AddAfter(const T &tValue2Add, Iterator & kIter);
 
    eC_Bool AddUnique(const T &tValue);
 
    eC_Bool AddUniqueAtEnd(const T &tValue);
 
    void AddSorted(const T &tValue);
 
    eC_Bool AddUniqueSorted(const T &tValue);
 
    eC_Bool Remove(SafeIterator & kIter);
 
    eC_Bool Remove(const T &tValue);
 
    eC_Bool RemoveFront(T& rtValue);
 
    eC_Bool RemoveEnd(T& rtValue);
 
    void RemoveAll();
 
    void RemoveAll(const T &tValue);
 
    eC_Bool MoveBefore(Iterator & kIter1, Iterator & kIter2);
 
    eC_Bool MoveBefore(Iterator &kStartIter, Iterator &kEndIter, Iterator &kIter);
 
    eC_Bool MoveAfter(Iterator & kIter1, Iterator & kIter2);
 
    eC_Bool MoveAfter(Iterator &kStartIter, Iterator &kEndIter, Iterator &kIter);
 
    eC_Bool Swap(Iterator & kIter1, Iterator & kIter2);
 
    void ReverseOrder();
 
    eC_Bool Contains(const T &tValue) const;
 
    eC_Bool Empty() const;
 
    void Sort(eC_Bool bIsQuicksort = true, compare comp = NULL);
 
    eC_Bool GetFirst(T& rtValue) const;
 
    eC_Bool GetNext(T& rtValue) const;
 
    eC_TIterator<T> GetBegin() const
    {
        eC_TIterator<T> kIter(m_pkFront);
        return kIter;
    }
 
    eC_TSafeIterator<T> GetBeginSafe()
    {
        eC_TSafeIterator<T> kIter;
        kIter.m_pNode = m_pkFront;
        if (m_pkFront != NULL)
        {
            kIter.m_pSaveNextNode = m_pkFront->m_pkNext;
            kIter.m_pSavePrevNode = m_pkFront->m_pkPrevious;
        }
        kIter.SetList(this);
        return kIter;
    }
 
    eC_TIterator<T> GetEnd() const
    {
        eC_TIterator<T> kIter(m_pkLast);
        return kIter;
    }
 
    eC_TSafeIterator<T> GetEndSafe()
    {
        eC_TSafeIterator<T> kIter;
        kIter.m_pNode = m_pkLast;
        if (m_pkLast != NULL)
        {
            kIter.m_pSaveNextNode = m_pkLast->m_pkNext;
            kIter.m_pSavePrevNode = m_pkLast->m_pkPrevious;
        }
        kIter.SetList(this);
        return kIter;
    }
 
    eC_TIterator<T> GetFind(const T &tValue) const
    {
        eC_TIterator<T> kIter;
        Node* pkSearch = m_pkFront;
 
        while (pkSearch)
        {
            if (pkSearch->m_tValue == tValue)
            {
                kIter.m_pNode = pkSearch;
                return kIter;
            }
 
            pkSearch = pkSearch->m_pkNext;
        }
 
        kIter.m_pNode = NULL;
        return kIter;
    }
 
    eC_TSafeIterator<T> GetFindSafe(const T &tValue)
    {
        eC_TSafeIterator<T> kIter;
        Node* pkSearch = m_pkFront;
 
        while (pkSearch)
        {
            if (pkSearch->m_tValue == tValue)
            {
                kIter.m_pNode = pkSearch;
                kIter.m_pSaveNextNode = pkSearch->m_pkNext;
                kIter.m_pSavePrevNode = pkSearch->m_pkPrevious;
                kIter.SetList(this);
                return kIter;
            }
 
            pkSearch = pkSearch->m_pkNext;
        }
 
        kIter.m_pNode = NULL;
        kIter.SetList(this);
        return kIter;
    }
 
    eC_TIterator<T> GetAt(eC_UInt uiPos) const
    {
        Node* pkRet = m_pkFront;
 
        while (pkRet != NULL && uiPos > 0)
        {
            pkRet = pkRet->m_pkNext;
            --uiPos;
        }
 
        return eC_TIterator<T>(pkRet);
    }
 
    eC_TSafeIterator<T> GetAtSafe(eC_UInt uiPos)
    {
        eC_TSafeIterator<T> kIter;
        if ((m_pkFront != NULL) && (uiPos < GetQuantity()))
        {
            Node* pkRet = m_pkFront;
 
            while (pkRet != NULL && uiPos > 0)
            {
                pkRet = pkRet->m_pkNext;
                --uiPos;
            }
 
            kIter.m_pNode = pkRet;
            if (pkRet != NULL)
            {
                kIter.m_pSaveNextNode = pkRet->m_pkNext;
                kIter.m_pSavePrevNode = pkRet->m_pkPrevious;
            }
        }
        kIter.SetList(this);
        return kIter;
    }
 
    eC_TListDoubleLinked<T>& operator=(const eC_TListDoubleLinked<T>& copy)
    {
        // Avoid copying ourselves
        if (&copy == this) return *this;
 
        //Delete old stuff;
        RemoveAll();
 
        Iterator iter = copy.GetBegin();
 
        while (iter.IsInsideList())
        {
            AddAtEnd(*iter);
            ++iter;
        }
 
        return *this;
    }
 
    //-------------------------------------
 
private:
    Node * m_pkFront;
    Node* m_pkLast;
 
    mutable Node* m_pkIterator;
 
    eC_UInt m_uiQuantity;
 
    eC_TSafeIterator<T>** m_ppIterRegister;  //pointer to array where safe iterators are registerd
    eC_UInt m_uiIterRegisterCnt;
    eC_UInt m_uiIterRegisterSize;
 
    eC_Bool Remove(Node* tNode);
 
    void SortArraysUsingQuickSort(Node** ppkArray, eC_Int iFirst, eC_Int iLast, compare comp = NULL);
 
    void SortArraysUsingMergeSort(Node** ppkMerged, eC_UInt uiQuantity, compare comp = NULL);
 
    void RegisterIterator(eC_TSafeIterator<T>*);
    void UnregisterIterator(eC_TSafeIterator<T>*);
    void UpdateIterators(Node*, Update_t) const;
};
 
//----------------------------------------------------------------------------
 
// "(List)" in backets is required when passing a dereferenced pointer to
// the list to the macro, e.g.:
//   CDevice::eC_TListDoubleLinked<CSomething*>* pSomethingList;
//   FOR_ALL_FORWARD(SomethingIter, *pSomethingList)
#define FOR_ALL_FORWARD(Iterator,List) for ((Iterator) = (List).GetBegin(); \
          (Iterator).IsInsideList(); ++(Iterator))
 
#define FOR_ALL_BACKWARD(Iterator,List) for ((Iterator) = (List).GetEnd(); \
          (Iterator).IsInsideList(); --(Iterator))
 
#define FOR_ALL_FORWARD_SAFE(Iterator,List) for ((Iterator) = (List).GetBeginSafe(); \
          (Iterator).IsValid() || (Iterator).IsNextValid(); ++(Iterator))
 
#define FOR_ALL_BACKWARD_SAFE(Iterator,List) for ((Iterator) = (List).GetEndSafe(); \
          (Iterator).IsValid() || (Iterator).IsPreviousValid(); --(Iterator))
 
//----------------------------------------------------------------------------
 
template <class T>
eC_TListDoubleLinked<T>::eC_TListDoubleLinked() :
    m_pkFront(NULL),
    m_pkLast(NULL),
    m_pkIterator(NULL),
    m_uiQuantity(0),
    m_ppIterRegister(NULL),
    m_uiIterRegisterCnt(0),
    m_uiIterRegisterSize(0)
{
}
 
template<class T>
eC_TListDoubleLinked<T>::eC_TListDoubleLinked(const eC_TListDoubleLinked<T>& copy) :
    m_pkFront(NULL),
    m_pkLast(NULL),
    m_pkIterator(NULL),
    m_uiQuantity(0),
    m_ppIterRegister(NULL),
    m_uiIterRegisterCnt(0),
    m_uiIterRegisterSize(0)
{
    operator=(copy);
}
 
//----------------------------------------------------------------------------
template <class T>
eC_TListDoubleLinked<T>::~eC_TListDoubleLinked()
{
    RemoveAll();
    // Unregister all safe iterators.
    for (eC_UInt i = 0; i < m_uiIterRegisterCnt; i++)
    {
        (m_ppIterRegister[i])->SetList(NULL);
    }
 
    delete[] m_ppIterRegister;
}
 
//----------------------------------------------------------------------------
template <class T>
eC_UInt eC_TListDoubleLinked<T>::GetQuantity() const
{
    return m_uiQuantity;
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::IsEmpty() const
{
    return m_uiQuantity == 0;
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::GetFirst(T& rtValue) const
{
    if (m_pkFront)
    {
        rtValue = m_pkFront->m_tValue;
        m_pkIterator = m_pkFront->m_pkNext;
        return true;
    }
    else
    {
        m_pkIterator = 0;
        return false;
    }
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::GetNext(T& rtValue) const
{
    if (m_pkIterator)
    {
        rtValue = m_pkIterator->m_tValue;
        m_pkIterator = m_pkIterator->m_pkNext;
        return true;
    }
    else
    {
        return false;
    }
}
 
//----------------------------------------------------------------------------
//adds an element tValue at front of list
template <class T>
void eC_TListDoubleLinked<T>::Add(const T &tValue)
{
    Node * pkNewNode = new Node();
    pkNewNode->m_tValue = tValue;
 
    // next of new element is formerly front element
    // (front element could be NULL)
    pkNewNode->m_pkNext = m_pkFront;
 
 
    if (m_pkFront)  //list is not empty
    {
        // previous of formerly front is new node
        // last element will remain the same
        m_pkFront->m_pkPrevious = pkNewNode;
    }
    else
    {
        // list was empty, so new element is first element and last element
        m_pkLast = pkNewNode;
    }
 
    // new first element already has no previous when it was constructed
    // new front is new node
    m_pkFront = pkNewNode;
 
    m_uiQuantity++;
 
    // Update SafeIterators which are registered, which are pointing at formerly
    // first element (they need to know new element)
    UpdateIterators(pkNewNode, ADDED);
}
 
//----------------------------------------------------------------------------
template <class T>
void eC_TListDoubleLinked<T>::AddAtEnd(const T &tValue)
{
    Node * pkNode = new Node();
    pkNode->m_tValue = tValue;
    pkNode->m_pkPrevious = m_pkLast;
 
    //list is not empty
    if (m_pkLast)
    {
        //next of last node is new node
        m_pkLast->m_pkNext = pkNode;
    }
    else
    {
        //list was empty, so new node is First and Last
        m_pkFront = pkNode;
    }
 
    //last element has no next
    pkNode->m_pkNext = 0;
 
    m_pkLast = pkNode;
    m_uiQuantity++;
 
    // Update SafeIterators, if pointing at last Element (needs to know new Element)
    UpdateIterators(pkNode, ADDED);
}
 
//----------------------------------------------------------------------------
template <class T>
void eC_TListDoubleLinked<T>::AddBefore(const T &tValue2Add, Iterator & kIter)
{
    Node * pNodeInList = kIter.GetNode();
 
    // If kIter is illegal call Add()
    if (NULL == pNodeInList)
        return Add(tValue2Add);
 
    Node* pkNode = new Node();
    pkNode->m_tValue = tValue2Add;
 
    Node* pkNodePre = pNodeInList->m_pkPrevious;
    pkNode->m_pkNext = pNodeInList;
 
    if (pkNodePre)
    {
        pkNode->m_pkPrevious = pkNodePre;
        pkNodePre->m_pkNext = pkNode;
    }
    else
    {
        m_pkFront = pkNode;
        pkNode->m_pkPrevious = 0;
    }
 
    pNodeInList->m_pkPrevious = pkNode;
    m_uiQuantity++;
 
    // Update SafeIterators, if pointing at last Element (needs to know new element)
    UpdateIterators(pkNode, ADDED);
}
 
//----------------------------------------------------------------------------
template <class T>
void eC_TListDoubleLinked<T>::AddAfter(const T &tValue2Add, Iterator & kIter)
{
    Node * pNodeInList = kIter.GetNode();
 
    // If kIter is illegal call call AddAtEnd()
    if (NULL == pNodeInList)
        return AddAtEnd(tValue2Add);
 
    Node* pkNode = new Node();
    pkNode->m_tValue = tValue2Add;
 
    Node* pkNodeNext = pNodeInList->m_pkNext;
    pkNode->m_pkPrevious = pNodeInList;
 
    if (pkNodeNext)
    {
        pkNodeNext->m_pkPrevious = pkNode;
        pkNode->m_pkNext = pkNodeNext;
    }
    else
    {
        m_pkLast = pkNode;
        pkNode->m_pkNext = 0;
    }
 
    pNodeInList->m_pkNext = pkNode;
    m_uiQuantity++;
    // Update SafeIterators, if pointing at last Element (needs to know new element)
    UpdateIterators(pkNode, ADDED);
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::AddUnique(const T &tValue)
{
    if (Contains(tValue))
    {
        return false;
    }
 
    Add(tValue);
    return true;
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::AddUniqueAtEnd(const T &tValue)
{
    if (Contains(tValue))
    {
        return false;
    }
 
    AddAtEnd(tValue);
    return true;
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::AddUniqueSorted(const T &tValue)
{
    if (Contains(tValue))
    {
        return false;
    }
 
    AddSorted(tValue);
    return true;
}
 
//----------------------------------------------------------------------------
template <class T>
void eC_TListDoubleLinked<T>::AddSorted(const T &tValue)
{
    Node * pkSortIter = 0;
 
    //not Empty, set Iterater at the end
    if ((pkSortIter = m_pkLast) != 0)
    {
        //if tValue > Value of last element
        if (tValue > pkSortIter->m_tValue)
        {
            AddAtEnd(tValue);
            return;
        }
 
        //if not added at end
        pkSortIter = m_pkFront;
 
        //if tValue <= Value of first element
        if (!(tValue > pkSortIter->m_tValue))
        {
            Add(tValue);
            return;
        }
 
        //not added at front and not added at end
        //search for right position
        while (tValue > pkSortIter->m_tValue)
        {
            //Iterate trough list
            pkSortIter = pkSortIter->m_pkNext;
        }
 
        //node behind new Node
        Node* pkNextNode = pkSortIter;
        //node in front of new Node
        Node* pkPrevNode = pkNextNode->m_pkPrevious;
 
        Node* pkNewNode = new Node();
        pkNewNode->m_pkNext = pkNextNode;
        pkNewNode->m_tValue = tValue;
 
        if (pkPrevNode)
        {
            pkPrevNode->m_pkNext = pkNewNode;
        }
 
        pkNextNode->m_pkPrevious = pkNewNode;
        pkNewNode->m_pkPrevious = pkPrevNode;
        m_uiQuantity++;
 
        // Update SafeIterators, if pointing at Previous or next Element  (needs to know new Element)
        UpdateIterators(pkNewNode, ADDED);
    }
    else
    {
        // list is empty -> add at front
        Add(tValue);
    }
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::Remove(SafeIterator &kIter)
{
    eC_Bool bResult = Remove(kIter.GetNode());
 
    //after removing iterator it is invalid
    kIter.m_pNode = NULL;
    return bResult;
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::Remove(const T &tValue)
{
    //finds node with specified value and passes it to Remove()
    return Remove((GetFind(tValue)).m_pNode);
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::Remove(Node* ptNode)
{
    // list is not empty and node is not 0
    if (ptNode && m_pkFront)
    {
        Node * pkSave = NULL;
 
        // special case: remove first element
        if (m_pkFront == ptNode)
        {
            // save the node that we want to delete
            pkSave = m_pkFront;
            // update front
            m_pkFront = m_pkFront->m_pkNext;
 
            // there is another element in list
            if (m_pkFront != NULL)
            {
                // new front has no previous element
                m_pkFront->m_pkPrevious = NULL;
            }
            else
            {
                // last remaining element of the list is getting deleted
                m_pkLast = NULL;
            }
 
        }
        else if (m_pkLast == ptNode)
 
        {
            // special case: removing last element in list
            // the list can still have several elements afterwards
 
            // save formerly last element
            pkSave = m_pkLast;
            // new last element is the element before the formerly last
            m_pkLast = m_pkLast->m_pkPrevious;
 
            // there is another element in list
            if (m_pkLast != NULL)
            {
                // next of new last element is NULL
                m_pkLast->m_pkNext = NULL;
            }
            else
            {
                // last remaining element of the list is getting deleted
                m_pkFront = NULL;
            }
 
        }
        else
        {
            // case: not first and not last element
            pkSave = ptNode;
 
            ptNode->m_pkPrevious->m_pkNext = ptNode->m_pkNext;
            ptNode->m_pkNext->m_pkPrevious = ptNode->m_pkPrevious;
        }
 
        m_uiQuantity--;
        UpdateIterators(pkSave, REMOVED);
 
        // deleting node after removing it from data structure of list
        delete pkSave;
        pkSave = NULL;
 
        return true;
    }
 
    return false; // nothing removed
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::RemoveFront(T& rtValue)
{
    if (m_pkFront)
    {
        // output parameter, only valid if function returns true
        rtValue = m_pkFront->m_tValue;
 
        Node* pkSave = m_pkFront;
        m_pkFront = m_pkFront->m_pkNext;
 
        if (m_pkFront)
        {
            m_pkFront->m_pkPrevious = NULL;
        }
        else
        {
            // front was last element
            m_pkLast = NULL;
        }
 
        m_uiQuantity--;
        UpdateIterators(pkSave, REMOVED);
 
        delete pkSave;
        pkSave = NULL;
 
        return true;
    }
 
    return false;
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::RemoveEnd(T& rtValue)
{
    if (m_pkLast)
    {
        // output parameter, only valid if function returns true
        rtValue = m_pkLast->m_tValue;
 
        Node* pkSave = m_pkLast;
 
        // First and only element
        if (m_pkLast == m_pkFront)
        {
            m_pkLast = NULL;
            m_pkFront = NULL;
        }
        else
        {
            // Last element is not first element
            m_pkLast = m_pkLast->m_pkPrevious;
            m_pkLast->m_pkNext = NULL;
        }
 
        m_uiQuantity--;
        UpdateIterators(pkSave, REMOVED);
 
        delete pkSave;
        pkSave = NULL;
 
        return true;
    }
 
    return false;
}
 
//----------------------------------------------------------------------------
template <class T>
void eC_TListDoubleLinked<T>::RemoveAll()
{
    Node * pkIterator = m_pkFront;
 
    // while not at end of list
    while (pkIterator)
    {
        // save pointer to next
        Node * pkNode = pkIterator->m_pkNext;
        // delete current
        delete pkIterator;
        // next iteration working on current next
        pkIterator = pkNode;
    }
 
    m_pkFront = NULL;
    m_pkLast = NULL;
    m_uiQuantity = 0;
    UpdateIterators(pkIterator, KILL);
}
 
//---------------------------------------------------------------------------
template <class T>
void eC_TListDoubleLinked<T>::RemoveAll(const T &tValue)
{
    Node * pkIteratorNode = m_pkFront;
 
    while (pkIteratorNode)
    {
        Node * pkNextNode = pkIteratorNode->m_pkNext;
 
        if (tValue == pkIteratorNode->m_tValue)
        {
            Remove(pkIteratorNode);
        }
 
        pkIteratorNode = pkNextNode;
    }
}
 
//----------------------------------------------------------------------------
template <class T>
void eC_TListDoubleLinked<T>::ReverseOrder()
{
    Node * pkReverse = NULL;
 
    m_pkLast = m_pkFront;
 
    while (m_pkFront)
    {
        Node * pkNode = m_pkFront;
        m_pkFront = m_pkFront->m_pkNext;
        pkNode->m_pkNext = pkReverse;
 
        if (pkReverse)
        {
            pkReverse->m_pkPrevious = pkNode;
        }
 
        pkReverse = pkNode;
    }
 
    m_pkFront = pkReverse;
 
    if (m_pkFront)
    {
        m_pkFront->m_pkPrevious = NULL;
    }
 
    UpdateIterators(0, REVERSE_ORDER);
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::Contains(const T &tValue) const
{
    Node * pkSearch = m_pkFront;
 
    while (pkSearch)
    {
        if (pkSearch->m_tValue == tValue)
        {
            return true;
        }
 
        pkSearch = pkSearch->m_pkNext;
    }
 
    return false;
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::Empty() const
{
    return !m_pkFront;
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::MoveBefore(Iterator &kIter1, Iterator &kIter2)
{
    if (!(kIter1.GetNode() && kIter2.GetNode()))
    {
        return false;
    }
 
    if (kIter1.GetNode()->m_pkNext == kIter2.GetNode())
    {
        return false;
    }
 
    // adjust former previous of iter1
    ListNode<T>* oldPrevious1 = kIter1.GetNode()->m_pkPrevious;
    if (oldPrevious1 != NULL)
        oldPrevious1->m_pkNext = kIter1.GetNode()->m_pkNext;
    else
        m_pkFront = kIter1.GetNode()->m_pkNext;
 
    // adjust former next of iter1
    ListNode<T>* oldNext1 = kIter1.GetNode()->m_pkNext;
    if (oldNext1 != NULL)
        oldNext1->m_pkPrevious = kIter1.GetNode()->m_pkPrevious;
    else
        m_pkLast = kIter1.GetNode()->m_pkPrevious;
 
    // adjust former previous of iter2
    ListNode<T>* oldPrevious2 = kIter2.GetNode()->m_pkPrevious;
    if (oldPrevious2 != NULL)
        oldPrevious2->m_pkNext = kIter1.GetNode();
    else
        m_pkFront = kIter1.GetNode();
 
    // new previous
    kIter1.GetNode()->m_pkPrevious = oldPrevious2;
 
    // new next
    kIter1.GetNode()->m_pkNext = kIter2.GetNode();
    kIter2.GetNode()->m_pkPrevious = kIter1.GetNode();
 
    return true;
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::MoveBefore(Iterator &kStartIter, Iterator &kEndIter, Iterator &kIter)
{
    if (!(kStartIter.GetNode() && kEndIter.GetNode() && kIter.GetNode()))
    {
        return false;
    }
 
    if (kEndIter.GetNode()->m_pkNext == kIter.GetNode())
    {
        return false;
    }
 
    // adjust former previous of start
    ListNode<T>* oldPreviousStart = kStartIter.GetNode()->m_pkPrevious;
    if (oldPreviousStart != NULL)
        oldPreviousStart->m_pkNext = kEndIter.GetNode()->m_pkNext;
    else
        m_pkFront = kEndIter.GetNode()->m_pkNext;
 
    // adjust former next of end
    ListNode<T>* oldNextEnd = kEndIter.GetNode()->m_pkNext;
    if (oldNextEnd != NULL)
        oldNextEnd->m_pkPrevious = kStartIter.GetNode()->m_pkPrevious;
    else
        m_pkLast = kStartIter.GetNode()->m_pkPrevious;
 
    // adjust former previous of iter
    ListNode<T>* oldPrevious = kIter.GetNode()->m_pkPrevious;
    if (oldPrevious != NULL)
        oldPrevious->m_pkNext = kStartIter.GetNode();
    else
        m_pkFront = kStartIter.GetNode();
 
    // new previous
    kStartIter.GetNode()->m_pkPrevious = oldPrevious;
 
    // new next
    kEndIter.GetNode()->m_pkNext = kIter.GetNode();
    kIter.GetNode()->m_pkPrevious = kEndIter.GetNode();
 
    return true;
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::MoveAfter(Iterator &kIter1, Iterator &kIter2)
{
    if (!(kIter1.GetNode() && kIter2.GetNode()))
    {
        return false;
    }
 
    if (kIter1.GetNode()->m_pkPrevious == kIter2.GetNode())
    {
        return false;
    }
 
    // adjust former previous of iter1
    ListNode<T>* oldPrevious1 = kIter1.GetNode()->m_pkPrevious;
    if (oldPrevious1 != NULL)
        oldPrevious1->m_pkNext = kIter1.GetNode()->m_pkNext;
    else
        m_pkFront = kIter1.GetNode()->m_pkNext;
 
    // adjust former next of iter1
    ListNode<T>* oldNext1 = kIter1.GetNode()->m_pkNext;
    if (oldNext1 != NULL)
        oldNext1->m_pkPrevious = kIter1.GetNode()->m_pkPrevious;
    else
        m_pkLast = kIter1.GetNode()->m_pkPrevious;
 
    // adjust former next of iter2
    ListNode<T>* oldNext2 = kIter2.GetNode()->m_pkNext;
    if (oldNext2 != NULL)
        oldNext2->m_pkPrevious = kIter1.GetNode();
    else
        m_pkLast = kIter1.GetNode();
 
    // new previous
    kIter1.GetNode()->m_pkPrevious = kIter2.GetNode();
 
    // new next
    kIter1.GetNode()->m_pkNext = oldNext2;
    kIter2.GetNode()->m_pkNext = kIter1.GetNode();
 
    return true;
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::MoveAfter(Iterator &kStartIter, Iterator &kEndIter, Iterator &kIter)
{
    if (!(kStartIter.GetNode() && kEndIter.GetNode() && kIter.GetNode()))
    {
        return false;
    }
 
    if (kStartIter.GetNode()->m_pkPrevious == kIter.GetNode())
    {
        return false;
    }
 
    // adjust former previous of start
    ListNode<T>* oldPreviousStart = kStartIter.GetNode()->m_pkPrevious;
    if (oldPreviousStart != NULL)
        oldPreviousStart->m_pkNext = kEndIter.GetNode()->m_pkNext;
    else
        m_pkFront = kStartIter.GetNode()->m_pkNext;
 
    // adjust former next of end
    ListNode<T>* oldNextEnd = kEndIter.GetNode()->m_pkNext;
    if (oldNextEnd != NULL)
        oldNextEnd->m_pkPrevious = kStartIter.GetNode()->m_pkPrevious;
    else
        m_pkLast = kEndIter.GetNode()->m_pkPrevious;
 
    // adjust former next of iter
    ListNode<T>* oldNext = kIter.GetNode()->m_pkNext;
    if (oldNext != NULL)
        oldNext->m_pkPrevious = kEndIter.GetNode();
    else
        m_pkLast = kEndIter.GetNode();
 
    // new previous
    kStartIter.GetNode()->m_pkPrevious = kIter.GetNode();
 
    // new next
    kEndIter.GetNode()->m_pkNext = oldNext;
    kIter.GetNode()->m_pkNext = kStartIter.GetNode();
 
    return true;
}
 
//----------------------------------------------------------------------------
template <class T>
eC_Bool eC_TListDoubleLinked<T>::Swap(Iterator &kIter1, Iterator &kIter2)
{
    if (!(kIter1.GetNode() && kIter2.GetNode()))
    {
        return false;
    }
 
    T tTempValue = kIter1.GetNode()->m_tValue;
    kIter1.GetNode()->m_tValue = kIter2.GetNode()->m_tValue;
    kIter2.GetNode()->m_tValue = tTempValue;
 
    return true;
}
 
//----------------------------------------------------------------------------
template <class T>
void eC_TListDoubleLinked<T>::SortArraysUsingQuickSort(Node** ppSortPointers, eC_Int iFirst, eC_Int iLast, compare comp)
{
    //quicksort implementation
    eC_Int iIter1 = iFirst, iIter2 = iLast;
    T tPivo = ppSortPointers[(iFirst + iLast) / 2]->m_tValue;
 
    while (iIter1 <= iIter2)
    {
        if (NULL != comp)
        {
            // m_tValue< tPivo
            while (comp(ppSortPointers[iIter1]->m_tValue, tPivo))
            {
                iIter1++;
            }
 
            while (comp(tPivo, ppSortPointers[iIter2]->m_tValue))
            {
                iIter2--;
            }
        }
        else
        {
            // m_tValue< tPivo
            while (
                !((ppSortPointers[iIter1]->m_tValue) > tPivo) &&
                !((ppSortPointers[iIter1]->m_tValue) == tPivo)
                )
            {
                iIter1++;
            }
 
            while ((ppSortPointers[iIter2]->m_tValue) > tPivo)
            {
                iIter2--;
            }
        }
 
        //swap elements
        if (iIter1 <= iIter2)
        {
            Node * pkTempNode = ppSortPointers[iIter1];
            ppSortPointers[iIter1] = ppSortPointers[iIter2];
            ppSortPointers[iIter2] = pkTempNode;
 
            iIter1++;
            iIter2--;
        }
    }
 
    //more than 1 element in "upper" part of Array
    if (iFirst < iIter2)
    {
        SortArraysUsingQuickSort(ppSortPointers, iFirst, iIter2, comp);
    }
 
    //more than 1 element in "lower" part of Array
    if (iIter1 < iLast)
    {
        SortArraysUsingQuickSort(ppSortPointers, iIter1, iLast, comp);
    }
}
 
//----------------------------------------------------------------------------
 
template <class T>
void eC_TListDoubleLinked<T>::SortArraysUsingMergeSort(Node** ppkMerged, eC_UInt uiQuantity, compare comp)
{
    // If there's only one element, there's nothing to sort
    if (uiQuantity > 1)
    {
        // Mergesort implementation
        eC_UInt uiMiddle = uiQuantity / 2;
        eC_UInt uiRightQuantity = uiQuantity - uiMiddle;
        eC_UInt uiLeftQuantity = uiMiddle;
 
        Node** ppkLeft = new Node*[uiLeftQuantity];
        for (eC_UInt i = 0; i < uiLeftQuantity; ++i)
            ppkLeft[i] = NULL;
 
        Node** ppkRight = new Node*[uiRightQuantity];
        for (eC_UInt i = 0; i < uiRightQuantity; ++i)
            ppkRight[i] = NULL;
 
        eC_UInt uiRight, uiLeft;
        for (uiLeft = 0; uiLeft < uiMiddle; ++uiLeft)
            ppkLeft[uiLeft] = ppkMerged[uiLeft];
 
        uiRight = 0;
        for (eC_UInt ui = uiMiddle; ui < uiQuantity; ++ui)
        {
            ppkRight[uiRight] = ppkMerged[ui];
            uiRight++;
        }
 
        // Recursive call with first half of the list and number of elements of it
        SortArraysUsingMergeSort(ppkLeft, uiLeft, comp);
 
        // Recursive call with second half of the list and number of elements of it
        SortArraysUsingMergeSort(ppkRight, uiRight, comp);
 
        // Merging part
        eC_UInt ui = 0, uj = 0, uk = 0;
        while (ui < uiQuantity)
        {
            if ((uiLeftQuantity != uj) && (uiRightQuantity != uk))
            {
                if (NULL != comp)
                {
                    if (comp(ppkRight[uk]->m_tValue, ppkLeft[uj]->m_tValue))
                    {
                        ppkMerged[ui] = ppkRight[uk];
                        uk++;
                    }
                    else
                    {
                        ppkMerged[ui] = ppkLeft[uj];
                        uj++;
                    }
                }
                else
                {
                    // if right < left (inverted logic is needed since not all operators may be defined)
                    if (
                        !(ppkRight[uk]->m_tValue > ppkLeft[uj]->m_tValue) &&
                        !(ppkRight[uk]->m_tValue == ppkLeft[uj]->m_tValue)
                        )
                    {
                        ppkMerged[ui] = ppkRight[uk];
                        uk++;
                    }
                    else
                    {
                        ppkMerged[ui] = ppkLeft[uj];
                        uj++;
                    }
                }
            }
            else if (uiLeftQuantity != uj)
            {
                ppkMerged[ui] = ppkLeft[uj];
                uj++;
            }
            else if (uiRightQuantity != uk)
            {
                ppkMerged[ui] = ppkRight[uk];
                uk++;
            }
            ui++;
        }
        delete[] ppkLeft;
        delete[] ppkRight;
    }
}
 
//----------------------------------------------------------------------------
 
template <class T>
void eC_TListDoubleLinked<T>::Sort(eC_Bool bIsQuicksort, compare comp)
{
    if (m_uiQuantity > 1)
    {
        eC_UInt ui;
        Node** ppSortPointers;
        ppSortPointers = new Node *[m_uiQuantity];
 
        Iterator pkIter;
        pkIter = GetBegin();
 
        //Get pointers to List Nodes into Array;
        for (ui = 0; ui < m_uiQuantity; ui++)
        {
            ppSortPointers[ui] = pkIter.GetNode();
            if (pkIter.IsValid())
            {
                ++pkIter;
            }
            else
            {
                delete[] ppSortPointers;
                return;
            }
        }
 
        //sort Node pointers in Array
        if (bIsQuicksort)
            SortArraysUsingQuickSort(ppSortPointers, 0, m_uiQuantity - 1, comp);
        else
            SortArraysUsingMergeSort(ppSortPointers, m_uiQuantity, comp);
 
        //set List pointers
 
        //firstElement
        m_pkFront = ppSortPointers[0];
 
        ppSortPointers[0]->m_pkPrevious = NULL;
        ppSortPointers[0]->m_pkNext = ppSortPointers[1];
 
        for (ui = 1; ui < m_uiQuantity - 1; ui++)
        {
            ppSortPointers[ui]->m_pkPrevious = ppSortPointers[ui - 1];
            ppSortPointers[ui]->m_pkNext = ppSortPointers[ui + 1];
        }
 
        //lastElement
        ppSortPointers[m_uiQuantity - 1]->m_pkPrevious = ppSortPointers[m_uiQuantity - 2];
        ppSortPointers[m_uiQuantity - 1]->m_pkNext = NULL;
 
        m_pkLast = ppSortPointers[m_uiQuantity - 1];
 
        delete[] ppSortPointers;
 
        UpdateIterators(pkIter.GetNode(), KILL);
    }
}
 
//----------------------------------------------------------------------------
 
template <class T>
void eC_TListDoubleLinked<T>::UpdateIterators(Node* pkNode, Update_t eUpdate) const
{
    for (eC_UInt i = 0; i < m_uiIterRegisterCnt; i++)
    {
        //Update Safe Iterators, if element is removed or added
        assert(m_ppIterRegister[i] != NULL);
        (m_ppIterRegister[i])->Validate(pkNode, eUpdate);
    }
}
 
//----------------------------------------------------------------------------
template <class T>
void eC_TListDoubleLinked<T>::RegisterIterator(eC_TSafeIterator<T>* pkNewIter)
{
    if (pkNewIter)
    {
        if (m_uiIterRegisterSize == m_uiIterRegisterCnt)
        {
            //resize Array (+5)
            eC_TSafeIterator<T>** ppTempRegister = new eC_TSafeIterator<T>*[m_uiIterRegisterSize + 5];
 
            //Copy elements from old array to new one
            for (eC_UInt i = 0; i < m_uiIterRegisterCnt; i++)
            {
                ppTempRegister[i] = m_ppIterRegister[i];
            }
 
            if (m_uiIterRegisterSize != 0)
            {
                //delete old array
                delete[] m_ppIterRegister;
            }
 
            m_ppIterRegister = ppTempRegister;
            m_uiIterRegisterSize = m_uiIterRegisterSize + 5;
        }
 
        //add new Iterator pointer
        m_ppIterRegister[m_uiIterRegisterCnt] = pkNewIter;
        m_uiIterRegisterCnt++;
        pkNewIter->SetList(this);
    }
}
 
//----------------------------------------------------------------------------
template <class T>
void eC_TListDoubleLinked<T>::UnregisterIterator(eC_TSafeIterator<T>* pkRemoveIter)
{
    if (pkRemoveIter)
    {
        for (eC_UInt i = 0; i < m_uiIterRegisterCnt; i++)
        {
            //delete and shrink
            if (m_ppIterRegister[i] == pkRemoveIter)
            {
                m_ppIterRegister[i] = NULL;
                pkRemoveIter->SetList(NULL);
                for (eC_UInt j = i; j < m_uiIterRegisterCnt - 1; j++)
                {
                    m_ppIterRegister[j] = m_ppIterRegister[j + 1];
                }
 
                m_uiIterRegisterCnt--;
                break;
            }
        }
    }
}
 
//----------------------------------------------------------------------------
 
template<typename T>
bool operator==(const eC_TListDoubleLinked<T>& list1,
    const eC_TListDoubleLinked<T>& list2)
{
    if (list1.GetQuantity() != list2.GetQuantity())
    {
        return false;
    }
 
    typename eC_TListDoubleLinked<T>::Iterator it1, it2;
    it2 = list2.GetBegin();
 
    for (it1 = list1.GetBegin(); it1.IsInsideList(); ++it1, ++it2)
    {
        if (!((*it1) == (*it2)))
        {
            return false;
        }
    }
 
    return true;
}
 
template<typename T>
bool operator!=(const eC_TListDoubleLinked<T>& list1,
    const eC_TListDoubleLinked<T>& list2)
{
    return !(list1 == list2);
}
 
// prevent compiler errors if memory-mapping is active
#include "eC_CustomMemoryMappingUndef.h"
 
#endif