QueueAr.h

// CQueue class interface: array implementation
//
// Etype: must have zero-parameter constructor and operator=
// CONSTRUCTION: with (a) no initializer;
//     copy construction of CQueue objects is DISALLOWED
// Deep copy is supported
//
// ******************PUBLIC OPERATIONS*********************
// void Enqueue( Etype X )--> Insert X
// void Dequeue( )        --> Remove least recently inserted item
// Etype GetFront( )      --> Return least recently inserted item
// int IsEmpty( )         --> Return 1 if empty; else return 0
// int IsFull( )          --> Return 1 if full; else return 0
// void MakeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// Predefined exception is propogated if new fails
// EXCEPTION is called for GetFront or Dequeue on empty queue
 
#ifndef __QUEUEAR_H
#define __QUEUEAR_H
 
#include "AbsQueue.h"
 
BEGIN_MOOTOOLS_NAMESPACE
 
    // Array-based queue
    template <class Etype>
    class CQueue : public AbsQueue<Etype>
    {
      public:
        CQueue( );
        ~CQueue( ) { xDeleteArray(Array, MaxSize); }
 
        const CQueue & operator=( const CQueue & Rhs );
 
        void Enqueue( const Etype & X );
        void Dequeue( );
        const Etype & GetFront( ) const;
        int IsEmpty( ) const   { return CurrentSize == 0; }
        int GetSize( ) const   { return CurrentSize; }
        int IsFull( ) const    { return 0; }
        void MakeEmpty( );
 
      protected:
        // Copy constructor remains disabled by inheritance
        int MaxSize;
        int CurrentSize;
        int Front;
        int Back;
        Etype *Array;
 
        void DoubleQueue( );             // Double array -- complicated
        void Increment( int & X ) const; // Add one with wraparound
    };
 
    #define QUEUE_SIZE 3
 
    // Add one with wraparound
    template <class Etype>
    void
    CQueue<Etype>::Increment( int & X ) const
    {
        if( ++X == MaxSize )
            X = 0;
    }
 
    template <class Etype>
    CQueue<Etype>::CQueue( ) : MaxSize( QUEUE_SIZE ),
                             CurrentSize( 0 ), Front( 0 ), Back( -1 )
    {
        Array = xNewArray(Etype ,  MaxSize);
    }
 
    template <class Etype>
    const CQueue<Etype> &
    CQueue<Etype>::operator=( const CQueue<Etype> & Rhs )
    {
        if( this == &Rhs )
            return Rhs;
 
        xDeleteArray(Array, MaxSize);
        Array = xNewArray(Etype, Rhs.MaxSize);
 
        CurrentSize = Rhs.CurrentSize;
        MaxSize = Rhs.MaxSize;
        Front = 0;
        Back = CurrentSize - 1;
 
        for( int i = 0, j = Rhs.Front; i < CurrentSize; i++, Increment( j ) )
            Array[ i ] = Rhs.Array[ j ];
 
        return *this;
    }
 
    template <class Etype>
    void
    CQueue<Etype>::DoubleQueue( void )
    {
        int OldSize  = MaxSize;
        int NewSize  = MaxSize * 2;
        Etype *Old = Array;
 
        Array = xNewArray(Etype, NewSize);
 
        for( int i = 0, j = Front; i < CurrentSize; i++, Increment( j ) ) 
            Array[ i ] = Old[ j ];
 
        Front = 0;
        Back = CurrentSize - 1;
        MaxSize = NewSize;
 
        xDeleteArray(Old, OldSize);
    }
    
    template <class Etype>
    void
    CQueue<Etype>::Enqueue( const Etype & X )
    {
        if( CurrentSize == MaxSize )
            DoubleQueue( );
 
        Increment( Back );
        Array[ Back ] = X;
        CurrentSize++;
    }
 
    template <class Etype>
    void
    CQueue<Etype>::Dequeue( void )
    {
        CurrentSize--;
        Increment( Front );
    }
 
    template <class Etype>
    const Etype &
    CQueue<Etype>::GetFront( ) const
    {
        return Array[ Front ];
    }
 
    template <class Etype>
    void
    CQueue<Etype>::MakeEmpty( void )
    {
        CurrentSize = 0;
        Front = 0;
        Back = -1;
    }
 
END_MOOTOOLS_NAMESPACE
 
#endif // __QUEUEAR_H