#include "queue.h"
        #include "fatal.h"
        #include <stdlib.h>

        #define MinQueueSize ( 4 )

        struct QueueRecord
        {
            int Capacity;
            int Front;
            int Rear;
            int Size;
            ElementTypeS *Array;
        };

        int
        IsEmpty( Queue Q )
        {
            return Q->Size == 0;
        }

        int
        IsFull( Queue Q )
        {
            return Q->Size == Q->Capacity;
        }

        Queue
        CreateQueue( int MaxElements )
        {
            Queue Q;

/* 1*/      if( MaxElements < MinQueueSize )
/* 2*/          Error( "Queue size is too small" );

/* 3*/      Q = (Queue)malloc( sizeof( struct QueueRecord ) );
/* 4*/      if( Q == NULL )
/* 5*/          FatalError( "Out of space!!!" );

/* 6*/      Q->Array = (ElementTypeS*)malloc( sizeof( ElementTypeS ) * MaxElements );
/* 7*/      if( Q->Array == NULL )
/* 8*/          FatalError( "Out of space!!!" );
/* 9*/      Q->Capacity = MaxElements;
/*10*/      MakeEmptyQ( Q );

/*11*/      return Q;
        }

        void
        MakeEmptyQ( Queue Q )
        {
            Q->Size = 0;
            Q->Front = 1;
            Q->Rear = 0;
        }

        void
        DisposeQueue( Queue Q )
        {
            if( Q != NULL )
            {
                free( Q->Array );
                free( Q );
            }
        }

        static int
        Succ( int Value, Queue Q )
        {
            if( ++Value == Q->Capacity )
                Value = 0;
            return Value;
        }

        void
        Enqueue( ElementTypeS X, Queue Q )
        {
            	int i,found=0;
		ElementTypeS e;
		
		for(i=Q->Front;i<=Q->Rear;i++) {
			e = Q->Array[i];
			if(e.v == X.v && e.u == X.u) {
				found = 1;
				break;
			}
		}
		
            if( IsFull( Q ) )
                Error( "Full queue" );
            else if(found==0)
            {
                Q->Size++;
                Q->Rear = Succ( Q->Rear, Q );
                Q->Array[ Q->Rear ] = X;
            }
        }


        ElementTypeS
        Front( Queue Q )
        {
            if( !IsEmpty( Q ) )
                return Q->Array[ Q->Front ];
            Error( "Empty queue" );
            
            ElementTypeS *empty = new ElementTypeS;
            empty->u = 0;
            empty->v = 0;
            return *empty;
            //return 0;  /* Return value used to avoid warning */
        }

        void
        Dequeue( Queue Q )
        {
            if( IsEmpty( Q ) )
                Error( "Empty queue" );
            else
            {
                Q->Size--;
                Q->Front = Succ( Q->Front, Q );
            }
        }
        
        void
	Remove(Queue S, int v, int u) {
		ElementTypeS e;
		int i,j;
		//printf("finding %d %d...\n",v,u);
		
		for(i=S->Front;i<=S->Rear;i++) {
			e = S->Array[i];
			//printf("found %d %d\n",e.v,e.u);
			if(e.v == v && e.u == u) {
				//printf("find\n");
				
				for(j=i;j<S->Rear;j++) 
					S->Array[j] = S->Array[j+1];
				S->Size--;
				S->Rear--;
				break;
			}
		}
	}
	
	void
	showQueue(Queue S) {
		int i;
		ElementTypeS e;
		for(i=S->Front;i<=S->Rear;i++) {
			e = S->Array[i];
			printf("%d %d\n",e.v,e.u);
		}
	}