/*------------------------------------------------------------------------*/
/*                                                                        */
/*  LISTIMP.H                                                             */
/*                                                                        */
/*  Copyright Borland International 1991                                  */
/*  All Rights Reserved                                                   */
/*                                                                        */
/*------------------------------------------------------------------------*/

#if !defined( __LISTIMP_H )
#define __LISTIMP_H

#if !defined( ___DEFS_H )
#include <_defs.h>
#endif  // ___DEFS_H

#if !defined( __MEMMGR_H )
#include <MemMgr.h>
#endif  // __MEMMGR_H

/*------------------------------------------------------------------------*/
/*                                                                        */
/*  template <class T> class BI_ListElement                               */
/*                                                                        */
/*  Node for templates BI_ListImp<T> and BI_IListImp<T>                   */
/*                                                                        */
/*------------------------------------------------------------------------*/

template <class T> class _CLASSTYPE BI_ListImp;

template <class T> class _CLASSTYPE BI_ListBlockInitializer
{

protected:

    BI_ListBlockInitializer()
        {
        PRECONDITION( count != UINT_MAX );
        if( count++ == 0 )
            BI_ListElement<T>::mgr = 
                new MemBlocks( sizeof(BI_ListElement<T>), 20 );
        }

    ~BI_ListBlockInitializer()
        {
        PRECONDITION( count != 0 );
        if( --count == 0 )
            {
            delete BI_ListElement<T>::mgr;
            BI_ListElement<T>::mgr = 0;
            }
        }

    static unsigned count;

};

template <class T> unsigned BI_ListBlockInitializer<T>::count = 0;

template <class T> class _CLASSTYPE BI_ListElement
{

public:

    BI_ListElement( T t, BI_ListElement<T> _FAR *p ) :
        data(t)
        {
        next = p->next;
        p->next = this;
        }

    BI_ListElement();

    BI_ListElement<T> _FAR *next;
    T data;

    void _FAR *operator new( size_t sz );
    void operator delete( void _FAR * );

private:

    friend class BI_ListBlockInitializer<T>;

    static MemBlocks *mgr;

};

template <class T> MemBlocks *BI_ListElement<T>::mgr = 0;

template <class T> inline BI_ListElement<T>::BI_ListElement()
{
    next = 0;
}

template <class T> void _FAR *BI_ListElement<T>::operator new( size_t sz )
{
    PRECONDITION( mgr != 0 );
    return mgr->allocate( sz );
}

template <class T> void BI_ListElement<T>::operator delete( void _FAR *b )
{
    PRECONDITION( mgr != 0 );
    mgr->free( b );
}

inline BI_ListElement<void _FAR *>::BI_ListElement()
{
    next = 0;
    data = 0;
}

/*------------------------------------------------------------------------*/
/*                                                                        */
/*  template <class T> class BI_ListImp                                   */
/*                                                                        */
/*  Implements a list of objects of type T.  Assumes that                 */
/*  T has meaningful copy semantics and a default constructor.            */
/*                                                                        */
/*------------------------------------------------------------------------*/

template <class T> class _CLASSTYPE BI_ListIteratorImp;

template <class T> class _CLASSTYPE BI_ListImp : 
    private BI_ListBlockInitializer<T>
{

public:

    friend class BI_ListIteratorImp<T>;

    BI_ListImp()
        {
        initList();
        }

    ~BI_ListImp()
        {
        flush();
        }

    T peekHead() const
        {
        return head.next->data;
        }

    void add( T );
    void detach( T, int = 0 );
    void flush( int del = 0 );

    int isEmpty() const
        {
        return head.next == &tail;
        }

    void forEach( void (_FAR *)(T _FAR &, void _FAR *), void _FAR * );
    T _FAR *firstThat( int (_FAR *)(const T _FAR &, void _FAR *),
                       void _FAR *
                     ) const;
    T _FAR *lastThat( int (_FAR *)(const T _FAR &, void _FAR *),
                      void _FAR *
                    ) const;

protected:

    BI_ListElement<T> head, tail;

    virtual BI_ListElement<T> _FAR *findDetach( T t )
        {
        return findPred(t);
        }

    virtual BI_ListElement<T> _FAR *findPred( T );

private:

    virtual void removeData( BI_ListElement<T> _FAR * )
        {
        }

    void initList();

};

template <class T> void BI_ListImp<T>::initList()
{
    head.next = &tail;
    tail.next = &tail;
}

template <class T> void BI_ListImp<T>::add( T toAdd )
{
    new BI_ListElement<T>( toAdd, &head );
}

template <class T> BI_ListElement<T> _FAR *BI_ListImp<T>::findPred( T t )
{
    tail.data = t;
    BI_ListElement<T> _FAR *cursor = &head;
    while( !(t == cursor->next->data) )
        cursor = cursor->next;
    return cursor;
}

template <class T> void BI_ListImp<T>::detach( T toDetach, int del )
{
    BI_ListElement<T> _FAR *pred = findDetach( toDetach );
    BI_ListElement<T> _FAR *item = pred->next;
    if( item != &tail )
        {
        pred->next = pred->next->next;
        if( del != 0 )
            removeData( item );
        delete item;
        }
}

template <class T> void BI_ListImp<T>::flush( int del )
{
    BI_ListElement<T> _FAR *current = head.next;
    while( current != &tail )
        {
        BI_ListElement<T> _FAR *temp = current;
        current = current->next;
        if( del != 0 )
            removeData( temp );
        delete temp;
        }
    initList();
}

template <class T>
void BI_ListImp<T>::forEach( void (_FAR *f)(T _FAR &, void _FAR *),
                             void _FAR *args
                           )
{
    BI_ListElement<T> _FAR *cur = head.next;
    while( cur->next != cur )
        {
        f( cur->data, args );
        cur = cur->next;
        }
}

template <class T>
T _FAR *BI_ListImp<T>::firstThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
                                  void _FAR *args
                                ) const
{
    BI_ListElement<T> _FAR *cur = head.next;
    while( cur->next != cur )
        if( cond( cur->data, args ) != 0 )
            return &(cur->data);
        else
            cur = cur->next;
    return 0;
}

template <class T>
T _FAR *BI_ListImp<T>::lastThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
                                 void _FAR *args
                               ) const
{
    T _FAR *res = 0;
    BI_ListElement<T> _FAR *cur = head.next;
    while( cur->next != cur )
        {
        if( cond( cur->data, args ) != 0 )
            res = &(cur->data);
        cur = cur->next;
        }
    return res;
}

/*------------------------------------------------------------------------*/
/*                                                                        */
/*  template <class T> class BI_SListImp                                  */
/*                                                                        */
/*  Implements a sorted list of objects of type T.  Assumes that          */
/*  T has meaningful copy semantics, a meaningful < operator, and a       */
/*  default constructor.                                                  */
/*                                                                        */
/*------------------------------------------------------------------------*/

template <class T> class _CLASSTYPE BI_SListImp : public BI_ListImp<T>
{

public:

    void add( T );