Source: classlib/include/classlib/deques.h

/***************************************************************************
    deques.h  -  doppie code
                             -------------------
    begin                : ven dic  7 17:40:01 CET 2001
    copyright            : (C) 2001 by Nicola De Nisco
    email                : nicola@winada.it
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   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.                                   *
 *                                                                         *
 ***************************************************************************/

#if !defined( __CLASSLIB_DEQUES_H )
#define __CLASSLIB_DEQUES_H

#if !defined( __CHECKS_H )
#include 
#endif  // __CHECKS_H

#if !defined( __CLASSLIB_DEFS_H )
#include "classlib/defs.h"
#endif  // __CLASSLIB_DEFS_H

#if !defined( __CLASSLIB_SHDDEL_H )
#include "classlib/shddel.h"
#endif  // __CLASSLIB_SHDDEL_H

#if !defined( __CLASSLIB_VECTIMP_H )
#include "classlib/vectimp.h"
#endif  // __CLASSLIB_VECTIMP_H

#if !defined( __CLASSLIB_DLISTIMP_H )
#include "classlib/dlistimp.h"
#endif  // __CLASSLIB_DLISTIMP_H

/**
  [INTERNAL USE ONLY]

  template  class TDequeAsVectorImp

  Implements the fundamental dequeue operations, using a vector
  as the underlying implementation.  The type Vect specifies the
  form of the vector, either a TVectorImp or a
  TIVectorImp.  The type T specifies the type of the
  objects to be put in the dequeue.  When using TVectorImp,
  T should be the same as T0. When using TIVectorImp, T
  should be of type pointer to T0.  See TQueueAsVector and
  TIQueueAsVector for examples.

*/

template  class TDequeAsVectorImp
{

public:

    TDequeAsVectorImp( unsigned max = DEFAULT_DEQUE_SIZE ) :
        Data(max+1),
        Left(0),
        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 TMDequeAsVectorIterator;

/**

  template  class TMDequeAsVector

  Implements a managed dequeue of objects of type T, using a vector as
  the underlying implementation.

*/

template  class TMDequeAsVector :
    public TDequeAsVectorImp,T>
{

    typedef TDequeAsVectorImp,T> Parent;

public:

    friend class TMDequeAsVectorIterator;

    typedef void (*IterFunc)(T&, void *);
    typedef int  (*CondFunc)(const T&, void *);

    TMDequeAsVector( unsigned max = DEFAULT_DEQUE_SIZE ) :
        TDequeAsVectorImp,T>( max )
        {
        }

    const T& PeekLeft() const
        {
        PRECONDITION( !IsEmpty() );
        return Data[Left];
        }

    const T& PeekRight() const
        {
        PRECONDITION( !IsEmpty() );
        return Data[Prev(Right)];
        }

    T GetLeft();
    T GetRight();

    void PutLeft( const T& );
    void PutRight( const T& );

	/** auto iterator: use an iterator function calling it for every element of the array;
		the function must have a prototype like this: void iterFunc(T&, void* args); */
    void ForEach( IterFunc iter, void *args );

	/** auto iterator: use a test function calling it for every element of the array;
	    the function must have a prototype like this: int testFunc(const T&, void* args);
		the function must return 0 if the test fail, != 0 if test is ok; the first element
		tested successful will be returned or NULL if no elements is ok */
    T *FirstThat( CondFunc cond, void *args ) const;

	/** auto iterator: use a test function calling it for every element of the array;
	    the function must have a prototype like this: int testFunc(const T&, void* args);
		the function must return 0 if the test fail, != 0 if test is ok; the last element
		tested successful will be returned or NULL if no elements is ok */
    T *LastThat( CondFunc cond, void *args ) const;

	/** Discarge every element in the queue
	*/
    void Flush()
        {
        Left = Right = 0;
        }
};

template 
T TMDequeAsVector::GetRight()
{
    PRECONDITION( !IsEmpty() );
    Right = Prev(Right);
    T t = Data[Right];
    Data[Right] = T();
    return t;
}

template 
void TMDequeAsVector::PutRight( const T& t )
{
    PRECONDITION( !IsFull() );
    Data[Right] = t;
    Right = Next(Right);
}

template 
T TMDequeAsVector::GetLeft()
{
    PRECONDITION( !IsEmpty() );
    T t = Data[Left];
    Data[Left] = T();
    Left = Next(Left);
    return t;
}

template 
void TMDequeAsVector::PutLeft( const T& t )
{
    PRECONDITION( !IsFull() );
    Left = Prev(Left);
    Data[Left] = t;
}

template 
void TMDequeAsVector::ForEach( IterFunc iter, void *args )
{
    for( unsigned index = Left; index != Right; index=Next(index) )
        iter( Data[index], args );
}

template 
T *TMDequeAsVector::FirstThat( CondFunc cond, void *args ) const
{
    for( unsigned index = Left; index != Right; index=Next(index) )
        if( cond( Data[index], args ) )
            return &Data[index];
    return 0;
}

template 
T *TMDequeAsVector::LastThat( CondFunc cond, void *args ) const
{
    T *res = 0;
    for( unsigned index = Left; index != Right; index=Next(index) )
        if( cond( Data[index], args ) )
            res = &Data[index];
    return res;
}

/**

  template  class TMDequeAsVectorIterator

  Implements an iterator for the family of Deques as Vectors.

*/

template  class TMDequeAsVectorIterator
{

public:

    TMDequeAsVectorIterator( const TMDequeAsVector& );

    operator int();
    const T& Current();
    const T& operator ++ ( int );
    const T& operator ++ ();
    void Restart();

private:

    unsigned Left;
    unsigned Right;
    const TMVectorImp *Vect;
    TMVectorIteratorImp Iter;
    int Second;

    void NextBlock();

};

template 
TMDequeAsVectorIterator::TMDequeAsVectorIterator( const TMDequeAsVector& v ) :
    Iter( v.Data )
{
    Vect = &v.Data;
    Left = v.Left;
    Right = v.Right;
    Restart();
}

template 
TMDequeAsVectorIterator::operator int()
{
    return int(Iter);
}

template 
const T& TMDequeAsVectorIterator::Current()
{
    return Iter.Current();
}

template 
const T& TMDequeAsVectorIterator::operator ++ ( int )
{
    const T& temp = Iter++;
    NextBlock();
    return temp;
}

template 
const T& TMDequeAsVectorIterator::operator ++ ()
{
    Iter++;
    NextBlock();
    return Current();
}

template 
void TMDequeAsVectorIterator::Restart()
{
    if( Left <= Right )
        Iter.Restart( Left, Right );
    else
        Iter.Restart( Left, Vect->Limit() );
    Second = 0;
}

template 
void TMDequeAsVectorIterator::NextBlock()
{
    if( int(Iter) == 0 && !Second && Left > Right )
        {
        Iter.Restart( 0, Right );
        Second = 1;
        }
}

/**

  template  class TDequeAsVector
  template  class TDequeAsVectorIterator

  Implements a dequeue of objects of type T, using a vector as the
  underlying implementation.

*/

template  class TDequeAsVector :
    public TMDequeAsVector
{

public:

    TDequeAsVector( unsigned max = DEFAULT_DEQUE_SIZE ) :
        TMDequeAsVector( max )
        {
        }

};

/**

  template  class TDequeAsVector
  template  class TDequeAsVectorIterator

  Implements a dequeue of objects of type T, using a vector as the
  underlying implementation.

*/

template  class TDequeAsVectorIterator :
    public TMDequeAsVectorIterator
{

public:

    TDequeAsVectorIterator( const TDequeAsVector& d ) :
        TMDequeAsVectorIterator( d )
        {
        }

};

template  class TMIDequeAsVectorIterator;

/**

  template  class TMIDequeAsVector

  Implements a managed dequeue of pointers to objects of type T,
  using a vector as the underlying implementation.

*/

template  class TMIDequeAsVector :
    public TDequeAsVectorImp,T *>,
    public TShouldDelete
{

    typedef TDequeAsVectorImp,T *> Parent;

public:

    friend class TMIDequeAsVectorIterator;

    typedef void (*IterFunc)(T&, void *);
    typedef int  (*CondFunc)(const T &, void *);

    TMIDequeAsVector( unsigned sz = DEFAULT_DEQUE_SIZE ) :
        TDequeAsVectorImp,T *>(sz)
        {
        }

    ~TMIDequeAsVector()
        {
        Flush();
        }

    T *PeekLeft() const
        {
        PRECONDITION( !IsEmpty() );
        return Data[Left];
        }

    T *PeekRight() const
        {
        PRECONDITION( !IsEmpty() );
        return Data[Prev(Right)];
        }

    T *GetLeft();
    T *GetRight();
    void PutLeft( T *t );
    void PutRight( T *t );

	/** empty the queue; if the ownership is on also the elements in the queue will be destroyed
	*/
    void Flush( TShouldDelete::DeleteType = TShouldDelete::DefDelete );

	/** auto iterator: use an iterator function calling it for every element of the array;
		the function must have a prototype like this: void iterFunc(T&, void* args); */
    void ForEach( IterFunc iter, void *args );

	/** auto iterator: use a test function calling it for every element of the array;
	    the function must have a prototype like this: int testFunc(const T&, void* args);
		the function must return 0 if the test fail, != 0 if test is ok; the first element
		that testing successful will be returned or NULL if no elements is ok */
    T *FirstThat( CondFunc cond, void *args ) const;

	/** auto iterator: use a test function calling it for every element of the array;
	    the function must have a prototype like this: int testFunc(const T&, void* args);
		the function must return 0 if the test fail, != 0 if test is ok; the last element
		that testing successful will be returned or NULL if no elements is ok */
    T *LastThat( CondFunc cond, void *args ) const;
};

template 
T *TMIDequeAsVector::GetRight()
{
    PRECONDITION( !IsEmpty() );
    Right = Prev(Right);
    T *t = Data[Right];
    Data[Right] = 0;
    return t;
}

template 
void TMIDequeAsVector::PutRight( T *t )
{
    PRECONDITION( !IsFull() );
    Data[Right] = t;
    Right = Next(Right);
}

template 
T *TMIDequeAsVector::GetLeft()
{
    PRECONDITION( !IsEmpty() );
    T *t = Data[Left];
    Data[Left] = 0;
    Left = Next(Left);
    return t;
}

template 
void TMIDequeAsVector::PutLeft( T *t )
{
    PRECONDITION( !IsFull() );
    Left = Prev(Left);
    Data[Left] = t;
}

template 
void TMIDequeAsVector::Flush( TShouldDelete::DeleteType dt )
{
    if( DelObj(dt) != 0 )
        {
        if( Left <= Right )
            Data.Flush( 1, Right, Left );
        else
            {
            Data.Flush( 1, Data.Limit(), Left );
            Data.Flush( 1, Right, 0 );
            }
        }
    Left = Right = 0;
}

template 
void TMIDequeAsVector::ForEach( IterFunc iter, void *args )
{
    for( unsigned index = Left; index != Right; index=Next(index) )
        iter( *(Data[index]), args );
}

template 
T *TMIDequeAsVector::FirstThat( CondFunc cond, void *args ) const
{
    for( unsigned index = Left; index != Right; index=Next(index) )
        if( cond( *(Data[index]), args ) )
            return Data[index];
    return 0;
}

template 
T *TMIDequeAsVector::LastThat( CondFunc cond, void *args ) const
{
    T *res = 0;
    for( unsigned index = Left; index != Right; index=Next(index) )
        if( cond( *(Data[index]), args ) )
            res = Data[index];
    return res;
}

/**

  template  class TMIDequeAsVectorIterator

  Implements an iterator for the family of indirect Deques as Vectors.

*/

template  class TMIDequeAsVectorIterator
{

public:

    TMIDequeAsVectorIterator( const TMIDequeAsVector& );

    operator int();
    T *Current();
    T *operator ++ ( int );
    T *operator ++ ();
    void Restart();

private:

    unsigned Left;
    unsigned Right;
    const TMIVectorImp *Vect;
    TMIVectorIteratorImp Iter;
    int Second;

    void NextBlock();

};

template 
TMIDequeAsVectorIterator::TMIDequeAsVectorIterator( const TMIDequeAsVector& v ) :
    Iter( v.Data )
{
    Vect = &v.Data;
    Left = v.Left;
    Right = v.Right;
    Restart();
}

template 
TMIDequeAsVectorIterator::operator int()
{
    return int(Iter);
}

template 
T *TMIDequeAsVectorIterator::Current()
{
    return Iter.Current();
}

template 
T *TMIDequeAsVectorIterator::operator ++ ( int )
{
    T *temp = Iter++;
    NextBlock();
    return temp;
}

template 
T *TMIDequeAsVectorIterator::operator ++ ()
{
    Iter++;
    NextBlock();
    return Iter.Current();
}

template 
void TMIDequeAsVectorIterator::Restart()
{
    if( Left <= Right )
        Iter.Restart( Left, Right );
    else
        Iter.Restart( Left, Vect->Limit() );
    Second = 0;
}

template 
void TMIDequeAsVectorIterator::NextBlock()
{
    if( int(Iter) == 0 && !Second && Left > Right )
        {
        Iter.Restart( 0, Right );
        Second = 1;
        }
}

/**

  template  class TIDequeAsVector
  template  class TIDequeAsVectorIterator

  Implements a dequeue of pointers to objects of type T, using a vector
  as the underlying implementation.

*/

template  class TIDequeAsVector :
    public TMIDequeAsVector
{

public:

    TIDequeAsVector( unsigned sz = DEFAULT_DEQUE_SIZE ) :
        TMIDequeAsVector(sz)
        {
        }

};

/**

  template  class TIDequeAsVector
  template  class TIDequeAsVectorIterator

  Implements a dequeue of pointers to objects of type T, using a vector
  as the underlying implementation.

*/

template  class TIDequeAsVectorIterator :
    public TMIDequeAsVectorIterator
{

public:

    TIDequeAsVectorIterator( const TIDequeAsVector& d ) :
        TMIDequeAsVectorIterator(d)
        {
        }

};

/**
  [INTERNAL USE ONLY]

  template  class TDequeAsDoubleListImp

  Implements the fundamental dequeue operations, using a list
  as the underlying implementation.  The type Lst specifies the
  form of the list, either a TDoubleListImp or a
  TIDoubleListImp.  The type T specifies the type of the
  objects to be put in the deque.  When using TDoubleListImp,
  T should be the same as T0. When using TIDoubleListImp, T
  should be of type pointer to T0.  See TDequeAsDoubleList and
  TIDequeAsDoubleList for examples.

*/

template  class TDequeAsDoubleListImp
{

public:

    TDequeAsDoubleListImp()
        {
        }

    int IsFull() const
        {
        return 0;
        }

    int IsEmpty() const
        {
        return GetItemsInContainer() == 0;
        }

    int GetItemsInContainer() const
        {
        return Data.GetItemsInContainer();
        }

protected:

    Lst Data;

};

template  class TMDequeAsDoubleListIterator;

/**

  template  class TMDequeAsDoubleList
  template  class TMDequeAsDoubleListIterator

  Implements a managed dequeue of objects of type T, using a
  double-linked list as the underlying implementation.

*/

template  class TMDequeAsDoubleList :
    public TDequeAsDoubleListImp,T>
{

    typedef TDequeAsDoubleListImp,T> Parent;

public:

    friend class TMDequeAsDoubleListIterator;

    typedef void (*IterFunc)(T &, void *);
    typedef int  (*CondFunc)(const T&, void *);

    T GetLeft();
    T GetRight();

    void PutLeft( const T& t )
        {
        Data.Add( t );
        }

    void PutRight( const T& t )
        {
        Data.AddAtTail( t );
        }

    const T& PeekLeft() const
        {
        PRECONDITION( !IsEmpty() );
        return Data.PeekHead();
        }

    const T& PeekRight() const
        {
        PRECONDITION( !IsEmpty() );
        return Data.PeekTail();
        }

	/** auto iterator: use an iterator function calling it for every element of the array;
		the function must have a prototype like this: void iterFunc(T&, void* args); */
    void ForEach( IterFunc iter, void *args )
        {
        Data.ForEach( iter, args );
        }

	/** auto iterator: use a test function calling it for every element of the array;
	    the function must have a prototype like this: int testFunc(const T&, void* args);
		the function must return 0 if the test fail, != 0 if test is ok; the first element
		that testing successful will be returned or NULL if no elements is ok */
    T *FirstThat( CondFunc cond, void *args ) const
        {
        return Data.FirstThat( cond, args );
        }

	/** auto iterator: use a test function calling it for every element of the array;
	    the function must have a prototype like this: int testFunc(const T&, void* args);
		the function must return 0 if the test fail, != 0 if test is ok; the last element
		that testing successful will be returned or NULL if no elements is ok */
    T *LastThat( CondFunc cond, void *args ) const
        {
        return Data.LastThat( cond, args );
        }

	/** Discarge every element in the queue
	*/
    void Flush()
        {
        Data.Flush();
        }

    int Detach( const T& t )
        {
        return Data.Detach(t);
        }

};

template 
T TMDequeAsDoubleList::GetLeft()
{
    PRECONDITION( !IsEmpty() );
    T t = Data.PeekHead();
    Data.Detach( t );
    return t;
}

template 
T TMDequeAsDoubleList::GetRight()
{
    PRECONDITION( !IsEmpty() );
    T t = Data.PeekTail();
    Data.Detach( t );
    return t;
}

/**

  template  class TMDequeAsDoubleList
  template  class TMDequeAsDoubleListIterator

  Implements a managed dequeue of objects of type T, using a
  double-linked list as the underlying implementation.

*/

template  class TMDequeAsDoubleListIterator :
    public TMDoubleListIteratorImp
{

public:

    TMDequeAsDoubleListIterator( const TMDequeAsDoubleList& s ) :
        TMDoubleListIteratorImp(s.Data)
        {
        }

};

/**

  template  class TDequeAsDoubleList
  template  class TDequeAsDoubleListIterator

  Implements a dequeue of objects of type T, using a double-linked list
  as the underlying implementation.

*/

template  class TDequeAsDoubleList :
    public TMDequeAsDoubleList
{
};

template  class TDequeAsDoubleListIterator :
    public TMDequeAsDoubleListIterator
{

public:

    TDequeAsDoubleListIterator( const TDequeAsDoubleList& s ) :
        TMDequeAsDoubleListIterator(s) {}

};

template  class TMIDequeAsDoubleListIterator;

/**

  template  class TMIDequeAsDoubleList
  template  class TMIDequeAsDoubleListIterator

  Implements a managed dequeue of pointers to objects of type T,
  using a double-linked list as the underlying implementation.

*/

template  class TMIDequeAsDoubleList :
    public TDequeAsDoubleListImp,T *>,
    public TShouldDelete
{

    typedef TDequeAsDoubleListImp,T *> Parent;

public:


    friend class TMIDequeAsDoubleListIterator;

    typedef void (*IterFunc)(T&, void *);
    typedef int  (*CondFunc)(const T&, void *);

    T *GetLeft();
    T *GetRight();

    void PutLeft( T *t )
        {
        Data.Add( t );
        }

    void PutRight( T *t )
        {
        Data.AddAtTail( t );
        }

    T *PeekLeft() const
        {
        PRECONDITION( !IsEmpty() );
        return STATIC_CAST(T *,Data.PeekHead());
        }

    T *PeekRight() const
        {
        PRECONDITION( !IsEmpty() );
        return STATIC_CAST(T *,Data.PeekTail());
        }

	/** empty the array; if the ownership is on also the elements in the array will be destroyed
	*/
    void Flush( TShouldDelete::DeleteType dt = TShouldDelete::DefDelete )
        {
        Data.Flush( DelObj(dt) );
        }

	/** auto iterator: use an iterator function calling it for every element of the array;
		the function must have a prototype like this: void iterFunc(T&, void* args); */
    void ForEach( IterFunc iter, void *args )
        {
        Data.ForEach( iter, args );
        }

	/** auto iterator: use a test function calling it for every element of the array;
	    the function must have a prototype like this: int testFunc(const T&, void* args);
		the function must return 0 if the test fail, != 0 if test is ok; the first element
		that testing successful will be returned or NULL if no elements is ok */
    T *FirstThat( CondFunc cond, void *args ) const
        {
        return Data.FirstThat( cond, args );
        }

	/** auto iterator: use a test function calling it for every element of the array;
	    the function must have a prototype like this: int testFunc(const T&, void* args);
		the function must return 0 if the test fail, != 0 if test is ok; the last element
		that testing successful will be returned or NULL if no elements is ok */
    T *LastThat( CondFunc cond, void *args ) const
        {
        return Data.LastThat( cond, args );
        }

	/** remove an element from queue without destroing it if need
	*/
    int Detach( T *t,
                TShouldDelete::DeleteType dt = TShouldDelete::NoDelete )
        {
        return Data.Detach(t,DelObj(dt));
        }
};

template 
T *TMIDequeAsDoubleList::GetLeft()
{
    PRECONDITION( !IsEmpty() );
    T *t = Data.PeekHead();
    Data.Detach( t, 0 );
    return t;
}

template 
T *TMIDequeAsDoubleList::GetRight()
{
    PRECONDITION( !IsEmpty() );
    T *t = Data.PeekTail();
    Data.Detach( t, 0 );
    return t;
}

/**

  template  class TMIDequeAsDoubleList
  template  class TMIDequeAsDoubleListIterator

  Implements a managed dequeue of pointers to objects of type T,
  using a double-linked list as the underlying implementation.

*/

template  class TMIDequeAsDoubleListIterator :
    public TMIDoubleListIteratorImp
{

public:

    TMIDequeAsDoubleListIterator( const TMIDequeAsDoubleList& s ) :
        TMIDoubleListIteratorImp(s.Data)
        {
        }

};

/**

  template  class TIDequeAsDoubleList
  template  class TIDequeAsDoubleListIterator

  Implements a dequeue of pointers to objects of type T, using a
  double-linked list as the underlying implementation.

*/

template  class TIDequeAsDoubleList :
    public TMIDequeAsDoubleList
{
};

/**

  template  class TIDequeAsDoubleList
  template  class TIDequeAsDoubleListIterator

  Implements a dequeue of pointers to objects of type T, using a
  double-linked list as the underlying implementation.

*/

template  class TIDequeAsDoubleListIterator :
    public TMIDequeAsDoubleListIterator
{

public:

    TIDequeAsDoubleListIterator( const TIDequeAsDoubleList& s ) :
        TMIDequeAsDoubleListIterator(s) {}

};

/**

  template  class TDeque
  template  class TDequeIterator

  Easy names for TDequeAsVector and TDequeAsVectorIterator.

*/

template  class TDeque : public TDequeAsVector
{

public:

    TDeque( unsigned max = DEFAULT_QUEUE_SIZE ) :
        TDequeAsVector( max )
        {
        }

};

/**

  template  class TDeque
  template  class TDequeIterator

  Easy names for TDequeAsVector and TDequeAsVectorIterator.

*/

template  class TDequeIterator : public TDequeAsVectorIterator
{

public:


    TDequeIterator( const TDeque& a ) :
        TDequeAsVectorIterator(a)
        {
        }

};

/**

  template  class TIDeque
  template  class TIDequeIterator

  Easy names for TIDequeAsVector and TIDequeAsVectorIterator.

*/

template  class TIDeque : public TIDequeAsVector
{

public:

    TIDeque( unsigned max = DEFAULT_QUEUE_SIZE ) :
        TIDequeAsVector( max )
        {
        }

};

/**

  template  class TIDeque
  template  class TIDequeIterator

  Easy names for TIDequeAsVector and TIDequeAsVectorIterator.

*/

template  class TIDequeIterator : public TIDequeAsVectorIterator
{

public:


    TIDequeIterator( const TIDeque& a ) :
        TIDequeAsVectorIterator(a)
        {
        }

};

#endif  // __CLASSLIB_DEQUES_H