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

#if !defined( __DEQUES_H )
#define __DEQUES_H

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

#if !defined( __CHECKS_H )
#include <Checks.h>
#endif  // __CHECKS_H

#if !defined( __SHDDEL_H )
#include <ShdDel.h>
#endif  // __SHDDEL_H

#if !defined( __VECTIMP_H )
#include <VectImp.h>
#endif  // __VECTIMP_H

#if !defined( __DLISTIMP_H )
#include <DListImp.h>
#endif  // __DLISTIMP_H

#if !defined( __CONTAIN_H )
#include <Contain.h>
#endif  // __CONTAIN_H

/*------------------------------------------------------------------------*/
/*                                                                        */
/*  template <class Vect, class T> class BI_DequeAsVectorImp              */
/*                                                                        */
/*  Implements the fundamental dequeue operations, using a vector         */
/*  as the underlying implementation.  The type Vect specifies the        */
/*  form of the vector, either a BI_VectorImp<T0> or a                    */
/*  BI_IVectorImp<T0>.  The type T specifies the type of the              */
/*  objects to be put in the dequeue.  When using BI_VectorImp<T0>,       */
/*  T should be the same as T0. When using BI_IVectorImp<T0>, T           */
/*  should be of type pointer to T0.  See BI_QueueAsVector and            */
/*  BI_IQueueAsVector for examples.                                       */
/*                                                                        */
/*------------------------------------------------------------------------*/

template <class Vect, class T> class _CLASSTYPE BI_DequeAsVectorImp
{

public:

    BI_DequeAsVectorImp( unsigned max = DEFAULT_DEQUE_SIZE ) :
        data(max+1),
        left(0),
        right(0)
        {
        }

    T peekLeft() const
        {
        PRECONDITION( !isEmpty() );
        return data[left];
        }

    T peekRight() const
        {
        PRECONDITION( !isEmpty() );
        return data[prev(right)];
        }

    T getLeft();
    T getRight();

    void putLeft( T );
    void putRight( T );

    void flush( TShouldDelete::DeleteType = TShouldDelete::DefDelete )
        {
        left = right = 0;
        }

    int isFull() const
        {
        return right == prev( left );
        }

    int isEmpty() const
        {
        return right == left;
        }

    int getItemsInContainer() const
        {
        return (right>=left) ? right - left : data.limit()-(left-right);
        }

protected:

    Vect data;
    unsigned left;
    unsigned right;

    unsigned prev( unsigned index ) const
        {
        if( index == 0 )
            index = data.limit();
        return --index;
        }

    unsigned next( unsigned index ) const
        {
        index++;
        if( index == data.limit() )
            index = 0;
        return index;
        }

};

template <class Vect, class T> T BI_DequeAsVectorImp<Vect,T>::getRight()
{
    PRECONDITION( !isEmpty() );
    right = prev(right);
    return data[right];
}

template <class Vect, class T>
void BI_DequeAsVectorImp<Vect,T>::putRight( T t )
{
    PRECONDITION( !isFull() );
    data[right] = t;
    right = next(right);
}

template <class Vect, class T> T BI_DequeAsVectorImp<Vect,T>::getLeft()
{
    PRECONDITION( !isEmpty() );
    T t = data[left];
    left = next(left);
    return t;
}

template <class Vect, class T>
void BI_DequeAsVectorImp<Vect,T>::putLeft( T t )
{
    PRECONDITION( !isFull() );
    left = prev(left);
    data[left] = t;
}

/*------------------------------------------------------------------------*/
/*                                                                        */
/*  template <class T> class BI_DequeAsVectorIteratorImp                  */
/*                                                                        */
/*  Implements an iterator for the family of Deques as Vectors.           */
/*                                                                        */
/*------------------------------------------------------------------------*/

template <class I, class V, class T>
class _CLASSTYPE BI_DequeAsVectorIteratorImp
{

public:

    BI_DequeAsVectorIteratorImp( const V _FAR &, unsigned l, unsigned r );

    operator int();
    T current();
    T operator ++ ( int );
    T operator ++ ();
    void restart();

private:

    unsigned left;
    unsigned right;
    const V _FAR *vect;
    I iter;
    int second;

    void nextBlock();

};

template <class I, class V, class T>
BI_DequeAsVectorIteratorImp<I,V,T>::BI_DequeAsVectorIteratorImp( const V _FAR &v,
                                                               unsigned l,
                                                               unsigned r
                                                             ) :
    iter( v )
{
    vect = &v;
    left = l;
    right = r;
    restart();
}

template <class I, class V, class T>
BI_DequeAsVectorIteratorImp<I,V,T>::operator int()
{
    return int(iter);
}

template <class I, class V, class T>
T BI_DequeAsVectorIteratorImp<I,V,T>::current()
{
    return iter.current();
}

template <class I, class V, class T>
T BI_DequeAsVectorIteratorImp<I,V,T>::operator ++ ( int )
{
    nextBlock();
    return iter++;
}

template <class I, class V, class T>
T BI_DequeAsVectorIteratorImp<I,V,T>::operator ++ ()
{
    T temp = ++iter;
    nextBlock();
    return temp;
}

template <class I, class V, class T>
void BI_DequeAsVectorIteratorImp<I,V,T>::restart()
{
    if( left <= right )
        iter.restart( left, right );
    else
        iter.restart( 0, left );
    second = 0;
}

template <class I, class V, class T>
void BI_DequeAsVectorIteratorImp<I,V,T>::nextBlock()
{
    if( int(iter) == 0 && !second && left > right )
        {
        iter.restart( right, vect->limit() );
        second = 1;
        }
}

/*------------------------------------------------------------------------*/
/*                                                                        */
/*  template <class T> class BI_DequeAsVector                             */
/*                                                                        */
/*  Implements a dequeue of objects of type T, using a vector as          */
/*  the underlying implementation.                                        */
/*                                                                        */
/*------------------------------------------------------------------------*/

template <class T> class _CLASSTYPE BI_DequeAsVector :
    public BI_DequeAsVectorImp<BI_VectorImp<T>,T>
{

public:

    friend class _CLASSTYPE BI_DequeAsVectorIterator<T>;

    BI_DequeAsVector( unsigned max = DEFAULT_DEQUE_SIZE ) :
        BI_DequeAsVectorImp<BI_VectorImp<T>,T>( max )
        {
        }

    void forEach( void (_FAR *f)(T _FAR &, void _FAR *), void _FAR *args )
        {
        data.forEach( f, args, left, right );
        }

    T _FAR *firstThat( int (_FAR *f)(const T _FAR &, void _FAR *),
                       void _FAR *args
                     ) const
        {
        return data.firstThat( f, args, left, right );
        }

    T _FAR *lastThat( int (_FAR *f)(const T _FAR &, void _FAR *),
                      void _FAR *args
                    ) const
        {
        return data.lastThat( f, args, left, right );
        }

};

/*------------------------------------------------------------------------*/
/*                                                                        */
/*  template <class T> class BI_DequeAsVectorIterator                     */
/*                                                                        */
/*  Implements an iterator for a DequeAsVector.                           */
/*                                                                        */
/*------------------------------------------------------------------------*/

template <class T> class _CLASSTYPE BI_DequeAsVectorIterator :
    public BI_DequeAsVectorIteratorImp<BI_VectorIteratorImp<T>,BI_VectorImp<T>,T>
{

public:

    BI_DequeAsVectorIterator( const BI_DequeAsVector<T> _FAR &d ) :
        BI_DequeAsVectorIteratorImp<BI_VectorIteratorImp<T>,BI_VectorImp<T>,T>( d.data,d.left,d.right )
        {
        }

};

/*------------------------------------------------------------------------*/
/*                                                                        */
/*  template <class T> class BI_IDequeAsVector                            */
/*                                                                        */
/*  Implements a dequeue of pointers to objects of type T,                */
/*  using a vector as the underlying implementation.                      */
/*                                                                        */
/*------------------------------------------------------------------------*/

template <class T> class _CLASSTYPE BI_IDequeAsVector :
    public BI_DequeAsVectorImp<BI_IVectorImp<T>,T _FAR *>,
    public virtual TShouldDelete
{

public:

    friend class _CLASSTYPE BI_IDequeAsVectorIterator<T>;

    BI_IDequeAsVector( unsigned sz = DEFAULT_DEQUE_SIZE ) :
        BI_DequeAsVectorImp<BI_IVectorImp<T>,T _FAR *>(sz)
        {
        }

    ~BI_IDequeAsVector()
        {
        flush();
        }

    T _FAR *peekLeft() const
        {
        return (T _FAR *)BI_DequeAsVectorImp<BI_IVectorImp<T>,T _FAR *>::peekLeft();
        }

    T _FAR *peekRight() const
        {
        return (T _FAR *)BI_DequeAsVectorImp<BI_IVectorImp<T>,T _FAR *>::peekRight();
        }

    T _FAR *getLeft()
        {
        return (T _FAR *)BI_DequeAsVectorImp<BI_IVectorImp<T>,T _FAR *>::getLeft();
        }

    T _FAR *getRight()
        {
        return (T _FAR *)BI_DequeAsVectorImp<BI_IVectorImp<T>,T _FAR *>::getRight();
        }

    void putLeft( T _FAR *t )
        {
        BI_DequeAsVectorImp<BI_IVectorImp<T>,T _FAR *>::putLeft( t );
        }

    void putRight( T _FAR *t )
        {
        BI_DequeAsVectorImp<BI_IVectorImp<T>,T _FAR *>::putRight( t );
        }

    void flush( TShouldDelete::DeleteType = TShouldDelete::DefDelete );

    void forEach( void (_FAR *f)(T _FAR &, void _FAR *), void _FAR *args )
        {
        data.forEach( f, args, left, right );
        }

    T _FAR *firstThat( int (_FAR *f)(const T _FAR &, void _FAR *),
                       void _FAR *args
                     ) const
        {
        return data.firstThat( f, args, left, right );
        }

    T _FAR *lastThat( int (_FAR *f)(const T _FAR &, void _FAR *),
                      void _FAR *args
                    ) const
        {
        return data.lastThat( f, args, left, right );
        }

};