gzTemplates.h

Go to the documentation of this file.

//*****************************************************************************
// File         : gzTemplates.h
// Module       : gzBase
// Description  : Class definition of iterator utilities
// Author       : Anders Modén      
// Product      : GizmoBase 2.1.1
//      
// Copyright © 2003- Saab Training Systems AB, Sweden    
//          
// NOTE:    GizmoBase is a platform abstraction utility layer for C++. It contains 
//          design patterns and C++ solutions for the advanced programmer.
//
//
// Revision History...                          
//                                  
// Who  Date    Description                     
//                                  
// AMO  980915  Created file    
//
//******************************************************************************

#ifndef __GZ_TEMPLATES_H__
#define __GZ_TEMPLATES_H__


#include "gzBasicTypes.h"
#include "gzMemory.h"
#include "gzAssembler.h"

#include <float.h>

// Forward prototyp
GZ_BASE_EXPORT gzVoid throwFatalTemplateError(char *string);


template <class T> class gzListIterator;
template <class T> class gzListConstIterator;
template <class T> class gzRefList;

//******************************************************************************
// Template : gzList
//                                  
// Purpose  : Linked list with index insort and reference management
//                                  
// Notes    : -
//                                  
// Revision History...                          
//                                  
// Who  Date    Description                     
//                                  
// AMO  980601  Created 
//                                  
//******************************************************************************
template <class T> class gzList 
{
    friend class gzListIterator<T>; 
    friend class gzListConstIterator<T>; 
    friend class gzRefList<T>;

    public:

        gzList(gzBool reuseLinks=FALSE);


        gzList(const gzList<T> &copy)  ;

        virtual ~gzList()  ;

        gzVoid insert(T *item)  ;                   // Adds at end of list

        gzVoid insertAt(gzULong index,T *item)  ;   // Adds at index

        gzVoid pre_insert(T *item) ;                    // Adds at beginning of list


        T   *insert(T *item, gzDouble sortval)  ;


        gzBool post_insert(T *item, gzDouble sortval)  ;


        gzBool pre_insert(T *item, gzDouble sortval)  ;

        T   *operator[](gzULong i)  ;

        gzList &operator=(const gzList &copy )  ;

        gzList &operator+=(const gzList &copy )  ;

        virtual gzVoid clear()  ;

        virtual gzVoid clearAndDestroy()  ;

        gzULong entries() const  ;

        gzBool contains(const T *item) const  ;

        T   *findSortItem(gzDouble sortval,const T *prevItem=NULL);

        T   *removeFirst()  ;
        
        T   *removeLast()  ;

        T   *remove( T * item )  ;
        
        T   *removeAt( gzULong index )  ;

        T   *last() const;

        T   *first() const;

        virtual gzVoid onInsert(T *item ) const {};

        virtual gzVoid onRemove(T *item ) const {};


        virtual T* cloneEntry(T *item ) const ;

        gzVoid  cleanLinks()  ;

        gzVoid reuseLinks(gzBool on=FALSE) ;

        gzBool operator==(const gzList &right) const;

    protected:

        struct LinkItem
        {
            gzDouble        sortval;
            T               *item;
            LinkItem        *next;
        };

        gzVoid          disposeLink(LinkItem *link) ;
        LinkItem *      allocLink() ;


        LinkItem    *m_link;

        LinkItem    *m_last;

        LinkItem    *m_recycle;

        gzULong     m_entries;

        gzBool      m_reuseLinks;

};


//***********************************************************************

template <class T> inline gzBool gzList<T>::operator==(const gzList &right) const
{
    if(m_entries!=right.m_entries)
        return FALSE;

    LinkItem *a=m_link;

    LinkItem *b=right.m_link;

    while(a)
    {
        if(a->item!=b->item)
            return FALSE;

        a=a->next;
        b=b->next;
    }
    
    return TRUE;
}

template <class T> inline gzVoid gzList<T>::reuseLinks(gzBool on) 
{
    m_reuseLinks=on;
}

template <class T> inline typename gzList<T>::LinkItem * gzList<T>::allocLink() 
{
    if(m_reuseLinks && m_recycle)
    {
        LinkItem *link=m_recycle;

        m_recycle=m_recycle->next;

        return link;
    }
    return new LinkItem;
}

template <class T> inline gzVoid gzList<T>::disposeLink(LinkItem *link) 
{ 
    if(m_reuseLinks)
    {
        link->next=m_recycle;
        m_recycle=link;
    }
    else
        delete link;
}

template <class T> inline gzVoid gzList<T>::cleanLinks() 
{
    if(m_recycle)
    {
        LinkItem *nextlink;

        while(m_recycle)
        {
            nextlink=m_recycle->next;
            delete m_recycle;
            m_recycle=nextlink;
        }
    }
}

//***********************************************************************

template <class T> inline T* gzList<T>::cloneEntry(T *item) const
{
    return item;
}

//***********************************************************************

template <class T> inline gzULong gzList<T>::entries()  const 
{
    return m_entries;
}

//***********************************************************************

template <class T> inline T *gzList<T>::remove( T *item ) 
{
    LinkItem *link=m_link;
    LinkItem *prevlink=0;

    T *retitem;

    while(link)
    {
        if(item==link->item)
        {
            if(!prevlink)
            {
                m_link=link->next;
                if(!m_link)
                    m_last=0;
            }
            else
            {
                prevlink->next=link->next;
                if(!prevlink->next)
                    m_last=prevlink;
            }
            retitem=link->item;
            disposeLink(link);
            m_entries--;
            onRemove(retitem);
            return retitem;
        }
        prevlink=link;
        link=link->next;
    }
    return 0;
}

//***********************************************************************

template <class T> inline T *gzList<T>::removeFirst() 
{
    if(!m_link)
        return 0;

    LinkItem *link=m_link;

    T *item=link->item;
    m_link=m_link->next;
    if(!m_link)
        m_last=0;

    disposeLink(link);

    m_entries--;

    onRemove(item);
    return item;
}

//***********************************************************************

template <class T> inline T *gzList<T>::removeLast() 
{
    if(!m_link)
        return 0;

    LinkItem *link=m_link;

    T *item=m_last->item;

    if(m_link==m_last)
    {
        disposeLink(m_link);
        m_link=0;
        m_last=0;
    }
    else
    {
        while(link->next!=m_last)
            link=link->next;
        disposeLink(m_last);

        m_last=link;
        m_last->next=0;
    }

    m_entries--;

    onRemove(item);
    return item;
}

//***********************************************************************

template <class T> inline T *gzList<T>::last() const
{
    if(!m_last)
        return 0;
    return m_last->item;
}

//***********************************************************************

template <class T> inline T *gzList<T>::first() const
{
    if(!m_link)
        return 0;
    return m_link->item;
}

//***********************************************************************

template <class T> inline T *gzList<T>::operator[](gzULong i) 
{
    if(i>=m_entries)
        return NULL;

    LinkItem *link=m_link;

    gzULong j;

    for(j=0;j<i;++j)
        link=link->next;

    return link->item;
}

//***********************************************************************

template <class T> inline gzList<T>::gzList(gzBool reuseLinks)  : m_link(0),m_last(0),m_recycle(0),m_entries(0),m_reuseLinks(reuseLinks)
{
}

//***********************************************************************

template <class T> inline gzList<T>::~gzList() 
{
    clear();
    cleanLinks();
}

//***********************************************************************

template <class T> inline gzVoid gzList<T>::insertAt(gzULong index,T *item) 
{
    if(index>=m_entries)
    {
        insert(item);
        return;
    }

    LinkItem *newlink=allocLink();
    newlink->sortval=0;
    newlink->item=item;

    LinkItem *pre_link=NULL;
    LinkItem *post_link=m_link;

    gzULong i;

    for(i=0;i<index;++i)
    {
        if(post_link)
        {
            pre_link=post_link;
            post_link=post_link->next;
        }
        else
            break;
    }

    if(pre_link)    // Not first item
    {
        newlink->next=pre_link->next;
        pre_link->next=newlink;

        if(!post_link)  // last
            m_last=newlink;
    }
    else            // First item
    {
        if(m_link)  // Not last
        {
            newlink->next=m_link;
            m_link=newlink;
        }
        else        // last
        {
            newlink->next=NULL;
            m_last=m_link=newlink;
        }
    }
    ++m_entries;
    onInsert(item);
}

//***********************************************************************

template <class T> inline T * gzList<T>::removeAt(gzULong index) 
{
    if(index>=m_entries-1)
    {
        if(index==m_entries-1)
            return removeLast();
        return NULL;
    }

    LinkItem *pre_link=NULL;
    LinkItem *post_link=m_link;

    gzULong i;

    for(i=0;i<index;++i)
    {
        if(post_link)
        {
            pre_link=post_link;
            post_link=post_link->next;
        }
        else
            break;
    }

    if(post_link)   // item to remove
    {
        if(pre_link)    // have previous item
        {
            if(!(pre_link->next=post_link->next))   // last item
                m_last=pre_link;

        }
        else    // remove first item
        {
            m_link=post_link->next;
            if(!(m_link=post_link->next))   // was last item
                m_last=NULL;
        }
        m_entries--;

        T *item=post_link->item;

        disposeLink(post_link);

        onRemove(item);
        return item;
    }
    else
        return NULL;
}

//***********************************************************************

template <class T> inline gzVoid gzList<T>::insert( T *item) 
{
    LinkItem *newlink=allocLink();

    newlink->next=0;

    newlink->sortval=0;

    if(m_last)
        m_last->next=newlink;
    else
        m_link=newlink;

    newlink->item=item;
    m_last=newlink;

    ++m_entries;
    onInsert(item);
}

//***********************************************************************

template <class T> inline gzVoid gzList<T>::pre_insert( T *item) 
{
    LinkItem *newlink=allocLink();

    newlink->next=m_link;
    newlink->sortval=0;

    m_link=newlink;

    if(!m_last)
        m_last=newlink;

    newlink->item=item;

    ++m_entries;
    onInsert(item);
}

//***********************************************************************
template <class T> inline T * gzList<T>::findSortItem(gzDouble sortval,const T *prevItem)
{
    const typename gzList<T>::LinkItem* link = m_link;
    
    if(prevItem)
    {
        while (link)
        {
            if (link->item == prevItem)
            {
                link = link->next;
                break;
            }

            link = link->next;
        }
    }
    
    while (link)
    {
        if (link->sortval == sortval)
        {
            return link->item;
        }

        link = link->next;
    }

    return NULL;
}

template <class T> inline T* gzList<T>::insert( T *item , gzDouble sortval) 
{
    LinkItem *newlink=allocLink();


    newlink->item=item;
    newlink->sortval=sortval;

    onInsert(item);

    if(m_last)
    {
        if(m_last->sortval<sortval)
        {

            m_last->next=newlink;
            newlink->next=NULL;
            m_last=newlink;
            ++m_entries;

            return NULL;
        }
    }

    T *deleteitem=0;

    LinkItem *sortitem=m_link;
    LinkItem *previtem=0;

    while(sortitem)
    {
        if(sortitem->sortval<sortval)
        {
            if(!previtem)
                previtem=sortitem;
            else
                previtem=previtem->next;
            sortitem=sortitem->next;
        }
        else if(sortitem->sortval==sortval)
        {
            deleteitem=sortitem->item;
            sortitem->item=item;
            disposeLink(newlink);
            onRemove(deleteitem);
            return deleteitem;
        }
        else
            break;
    }
    newlink->next=sortitem;
    if(!previtem)
        m_link=newlink;
    else
        previtem->next=newlink;

    if(!sortitem)
        m_last=newlink;

    ++m_entries;

    return deleteitem;
}

//***********************************************************************

template <class T> inline gzBool gzList<T>::post_insert( T *item , gzDouble sortval) 
{
    LinkItem *newlink=allocLink();

    newlink->item=item;
    newlink->sortval=sortval;

    onInsert(item);

    if(m_last)
    {
        if(m_last->sortval<=sortval)
        {
            gzBool insert=(m_last->sortval==sortval);

            m_last->next=newlink;
            newlink->next=NULL;
            m_last=newlink;
            ++m_entries;

            return insert;
        }
    }

    LinkItem *sortitem=m_link;
    LinkItem *previtem=0;


    while(sortitem)
    {
        if(sortitem->sortval<=sortval)
        {
            if(!previtem)
                previtem=sortitem;
            else
                previtem=previtem->next;
            sortitem=sortitem->next;
        }
        else
            break;
    }

    newlink->next=sortitem;
    if(!previtem)
        m_link=newlink;
    else
        previtem->next=newlink;

    ++m_entries;

    if(!sortitem)
        m_last=newlink;

    if(previtem)
    {
        if(previtem->sortval==sortval)
            return TRUE;
        else
            return FALSE;
    }

    return FALSE;

}

//***********************************************************************

template <class T> inline gzBool gzList<T>::pre_insert( T *item , gzDouble sortval) 
{
    LinkItem *newlink=allocLink();

    newlink->item=item;
    newlink->sortval=sortval;


    onInsert(item);

    if(m_last)
    {
        if(m_last->sortval<sortval)
        {

            m_last->next=newlink;
            newlink->next=NULL;
            m_last=newlink;
            ++m_entries;

            return FALSE;
        }
    }

    LinkItem *sortitem=m_link;
    LinkItem *previtem=0;

    while(sortitem)
    {
        if(sortitem->sortval<sortval)
        {
            if(!previtem)
                previtem=sortitem;
            else
                previtem=previtem->next;
            sortitem=sortitem->next;
        }
        else
            break;
    }

    newlink->next=sortitem;
    if(!previtem)
        m_link=newlink;
    else
        previtem->next=newlink;

    ++m_entries;

    if(!sortitem)
        m_last=newlink;
    else
    {
        if(sortitem->sortval==sortval)
            return TRUE;
        else
            return FALSE;
    }

    return FALSE;
}

//***********************************************************************

template <class T> inline gzList<T> & gzList<T>::operator=(const gzList &copy ) 
{
    if(&copy==this)
        return *this;

    clear();        // rensa gammal data

    m_reuseLinks=copy.m_reuseLinks;

    LinkItem *link=copy.m_link;

    m_link=0;
    m_last=0;

    while(link)
    {
        LinkItem *newlink=allocLink();

        newlink->item=cloneEntry(link->item); // default to copy of instance

        onInsert(newlink->item);
        newlink->sortval=link->sortval;
        newlink->next=0;

        if(m_last)
            m_last->next=newlink;
        else
            m_link=newlink;

        m_last=newlink;

        link=link->next;
    }
    m_entries=copy.m_entries;

    return *this;
}

template <class T> inline gzList<T> & gzList<T>::operator+=(const gzList &copy ) 
{
    if(&copy==this)
        return *this;

    LinkItem *link=copy.m_link;

    while(link)
    {
        LinkItem *newlink=allocLink();

        newlink->item=cloneEntry(link->item); // default to copy of instance

        onInsert(newlink->item);
        newlink->sortval=link->sortval;
        newlink->next=0;

        if(m_last)
            m_last->next=newlink;
        else
            m_link=newlink;

        m_last=newlink;

        link=link->next;
    }
    m_entries+=copy.m_entries;

    return *this;
}

//***********************************************************************

template <class T> inline gzList<T>::gzList(const gzList<T> &copy) 
{
    LinkItem *link=copy.m_link;

    m_link=0;
    m_last=0;
    m_recycle=0;
    m_reuseLinks=FALSE;

    while(link)
    {
        LinkItem *newlink=allocLink();

        newlink->item=cloneEntry(link->item); // default to copy of instance

        onInsert(newlink->item);
        newlink->sortval=link->sortval;
        newlink->next=0;

        if(m_last)
            m_last->next=newlink;
        else
            m_link=newlink;

        m_last=newlink;

        link=link->next;
    }
    m_entries=copy.m_entries;
}

//***********************************************************************

template <class T> inline gzVoid gzList<T>::clearAndDestroy() 
{
    if(m_link)
    {
        LinkItem *nextlink;

        while(m_link)
        {
            nextlink=m_link->next;
            onRemove(m_link->item);
            delete m_link->item;
            disposeLink(m_link);

            m_link=nextlink;
        }
        m_entries=0;
        m_last=0;
    }
}

//***********************************************************************

template <class T> inline gzVoid gzList<T>::clear() 
{
    if(m_link)
    {
        LinkItem *nextlink;

        while(m_link)
        {
            nextlink=m_link->next;
            onRemove(m_link->item);
            disposeLink(m_link);

            m_link=nextlink;
        }
        m_entries=0;
        m_last=0;
    }
}


//******************************************************************************
// Template : gzListIterator
//
// Purpose  : Iterator for gzList
//
// Notes    : -
//
// Revision History...
//
// Who  Date    Description
//
// AMO  980601  Created
//
//******************************************************************************

template <class T> class gzListIterator 
{
    public:

        gzListIterator(gzList<T> &owner);

        gzListIterator(gzList<T> *owner);

        virtual ~gzListIterator(){};


        T *operator()();

        T *operator++(int); // postfix operator


        T *circulate();


        T *key() const;

        T *next() const;


        T *remove();

        gzVoid reset();

        gzVoid setList(gzList<T> &owner);

        gzDouble sortval() const;

        gzVoid post_insert(T *item);

        gzVoid pre_insert(T *item);


    private:
    
        typename gzList<T>::LinkItem *m_link;

        typename gzList<T>::LinkItem *m_prevlink;

        gzList<T> * m_owner;

        gzBool      m_circulating;

};

//***********************************************************************

template <class T> inline gzListIterator<T>::gzListIterator(gzList<T> &owner)
{
    m_link=0;
    m_prevlink=0;
    m_circulating=FALSE;
    m_owner=&owner;
}

template <class T> inline gzListIterator<T>::gzListIterator(gzList<T> *owner)
{
    m_link=0;
    m_prevlink=0;
    m_circulating=FALSE;
    m_owner=owner;
}

//***********************************************************************

template <class T> inline gzVoid gzListIterator<T>::setList(gzList<T> &owner)
{
    m_link=0;
    m_prevlink=0;
    m_owner=&owner;
}

//***********************************************************************

template <class T> inline gzDouble gzListIterator<T>::sortval() const
{
    if(m_link)
        return m_link->sortval;
    else
        return 0;
}

//***********************************************************************

template <class T> inline gzVoid gzListIterator<T>::post_insert(T *item)
{
    if(m_link)
    {
        typename gzList<T>::LinkItem *link=m_owner->allocLink();

        link->next=m_link->next;

        link->sortval=0;

        link->item=item;

        m_link->next=link;

        if(m_owner->m_last==m_link)
            m_owner->m_last=link;


        m_owner->onInsert(item);

        ++m_owner->m_entries;
    }
}

//***********************************************************************

template <class T> inline gzVoid gzListIterator<T>::pre_insert(T *item)
{
    if(m_link)
    {
        typename gzList<T>::LinkItem *link=m_owner->allocLink();

        link->next=m_link;

        link->sortval=0;

        link->item=item;

        if(m_prevlink)
            m_prevlink->next=link;
        else
            m_owner->m_link=link;

        m_prevlink=link;

        m_owner->onInsert(item);

        ++m_owner->m_entries;
    }
}

//***********************************************************************

template <class T> inline T * gzListIterator<T>::remove()
{
    if(!m_link)
        return NULL;

    T *item=m_link->item;

    typename gzList<T>::LinkItem *link;

    if(!m_link->next)
        m_owner->m_last=m_prevlink;

    link=m_link->next;

    if(m_prevlink)
        m_prevlink->next=link;
    else
        m_owner->m_link=link;

    m_owner->onRemove(m_link->item);
    m_owner->disposeLink(m_link);
    m_owner->m_entries--;

    m_link=m_prevlink;

    return item;
}

//***********************************************************************

template <class T> inline gzVoid gzListIterator<T>::reset()
{
    m_link=0;
    m_prevlink=0;
    m_circulating=FALSE;
}

//***********************************************************************

template <class T> inline T *gzListIterator<T>::operator()()
{
    if(m_prevlink=m_link)
        m_link=m_link->next;
    else
        m_link=m_owner->m_link;

    if(m_link)
        return m_link->item;
    else
        return NULL;
}

//***********************************************************************

template <class T> inline T *gzListIterator<T>::operator++(int)
{
    return operator()();
}

//***********************************************************************

template <class T> inline T *gzListIterator<T>::circulate()
{
    m_circulating=TRUE;

    m_prevlink=m_link;

    if(m_link)
        m_link=m_link->next;

    if(!m_link)
    {
        m_link=m_owner->m_link;
        m_prevlink=0;
    }

    if(m_link)
        return m_link->item;
    else
        return NULL;
}

//***********************************************************************

template <class T> inline T *gzListIterator<T>::key() const
{
    if(m_link)
        return m_link->item;
    else
        return NULL;
}

//***********************************************************************

template <class T> inline T *gzListIterator<T>::next() const
{
    if(m_link)
    {
        if(m_link->next)
            return m_link->next->item;
        else if(m_circulating)
            return m_owner->m_link->item;
    }
    return NULL;
}

//******************************************************************************
// Template : gzListConstIterator
//                                  
// Purpose  : Constant Iterator for gzList
//                                  
// Notes    : -
//                                  
// Revision History...                          
//                                  
// Who  Date    Description                     
//                                  
// AMO  040301  Created 
//                                  
//******************************************************************************

template <class T> class gzListConstIterator 
{
    public:

        gzListConstIterator(const gzList<T> &owner);

        virtual ~gzListConstIterator(){};


        T *operator()();

        T *operator++(int); // postfix operator


        T *circulate();


        T *key() const;

        T *next() const;

        gzVoid reset();

        gzDouble sortval() const;


    private:
    
        typename gzList<T>::LinkItem *m_link;

        typename gzList<T>::LinkItem *m_prevlink;

        const gzList<T> *   m_owner;

        gzBool      m_circulating;

};

//***********************************************************************

template <class T> inline gzBool gzList<T>::contains(const T *item) const 
{
    const typename gzList<T>::LinkItem* link = m_link;
        
    while (link)
    {
        if (link->item == item)
        {
            return TRUE;
        }

        link = link->next;
    }
    
    return FALSE;
}

//***********************************************************************

template <class T> inline gzListConstIterator<T>::gzListConstIterator(const gzList<T> &owner)
{
    m_link=0;
    m_prevlink=0;
    m_circulating=FALSE;
    m_owner=&owner;
}

//***********************************************************************

template <class T> inline gzDouble gzListConstIterator<T>::sortval() const
{
    if(m_link)
        return m_link->sortval;
    else
        return 0;
}

//***********************************************************************

template <class T> inline gzVoid gzListConstIterator<T>::reset()
{
    m_link=0;
    m_prevlink=0;
    m_circulating=