#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>


int counter = 0;
struct info_node
{
    int  weight ;

struct info_node* next ;

} ;

struct lstack
{
    struct info_node* top ;
} ;

struct lqueue
{
    struct info_node* front ;
    struct info_node*  rear ;
} ;

struct prq_que
{
    struct info_node* top ;
} ;


#define TRUE 1
#define FALSE 0

void  create_stack( struct lstack *  ) ;
int   empty_stack( struct lstack*  ) ;
void  push( struct lstack * , struct info_node * ) ;
struct info_node*  pop( struct lstack * ) ;

void  create_queue( struct lqueue*  ) ;
int   empty_queue( struct lqueue*  ) ;
void  queue_insert( struct lqueue * , struct info_node * ) ;
struct info_node*  queue_remove( struct lqueue * ) ;


void  create_prq( struct prq_que*  ) ;
int   empty_prq( struct prq_que*  ) ;
void  prq_insert( struct prq_que* , struct info_node * ) ;
struct info_node*  prq_remove( struct prq_que * ) ;



int main()
{
    FILE* infile ;

    infile = fopen( "heap_data.txt", "r" ) ;

    struct lstack main_stack ;
    struct lqueue main_queue ;
    struct prq_que pmain_queue ;

    struct info_node * new_node  = NULL ;
    int rweight = 0 ;
    struct info_node* rnode = NULL ;


          create_stack( & main_stack ) ;
          create_queue( & main_queue ) ;
          create_prq( & pmain_queue ) ;

// begin commentation
    //    while (!feof (infile) )
    //    //for( int a = 0 ; a < 20 ; a++ )
    //    {

    //

    //        new_node =  (struct info_node* ) malloc( sizeof( struct info_node ) ) ;
    //        fscanf(infile, "%d", &new_node->weight ) ;

    //        push( &main_stack , new_node ) ;

    //
    //    }  // end of for ( a < 30 )


    //for( int a = 0 ; a < 20 ; a++ )
    //    {
 //
    //        // printf("%d ", pop(&main_stack )->weight ) ;
    //         rnode = pop( &main_stack ) ;

    //     if( rnode != NULL )
    //     {
    //         rweight = rnode->weight ;
    //         printf("%d ", rweight ) ;
    //     }

    //
    //    }  // end of for ( a < 30 )

    //  printf("\n\n") ;

        // end commentation

//  test code for queue
 // begin commentation!
          //while (!feof (infile) )
          // reads in actual order
    counter = 120;
        //?

          for( int a = 0 ; a <counter; a++ )
          {



              new_node =  (struct info_node* ) malloc( sizeof( struct info_node ) ) ;
              fscanf(infile, "%d", &new_node->weight ) ;

              queue_insert( &main_queue , new_node ) ;

              printf("[A]");
              //counter++;
              // MAKE THE a queue of 20 numbers!
          }  // end of for ( a < 30 )

          printf("\n\n");

          // sorts

           for( int a = 0 ; a < counter ; a++ ) // a will end when counter from last is equal
     {

              // printf("%d ", pop(&main_stack->weight) ) ; // should not pop?
               rnode = queue_remove( &main_queue ) ; // remove from queue

           if( rnode != NULL )
           {
               rweight = rnode->weight ;
               printf("%d ", rweight ) ;// write value removed??
           }

              printf("[b]"); // printf debug
     }  // end of for ( a < 30 )

        printf("\n\n");

// end commentation


 for( int a = 0 ; a < counter ; a++ ) // all code same now!
          {



              new_node =  (struct info_node* ) malloc( sizeof( struct info_node ) ) ;
              fscanf(infile, "%d", &new_node->weight ) ;

              prq_insert( &pmain_queue , new_node ) ;

              printf("[C]");
              // this one is read in in the correct order! via a pqueue???
          }  // end of for ( a < 30 )




          for( int a = 0 ; a < counter ; a++ )
          {

             //printf("%d ", pop(&main_stack )->weight ) ; // was commented out
               rnode = prq_remove( &pmain_queue ) ; // why remove first?

           if( rnode != NULL )
           {
               rweight = rnode->weight ;
               printf("%d ", rweight ) ;
           }
           // printed the priority queue?
              printf("[D]");
          }  // end of for ( a < 30 )

        printf("\n\n") ;





        fclose( infile ) ;
        system("PAUSE");
    return( 0 ) ;


}  // end of function main()

void  create_stack( struct lstack * nstack )
{
    nstack->top = NULL ;
    return ;

}  // end of function create_stack()

int   empty_stack( struct lstack* nstack )
{
    if( nstack->top == NULL )
        return( TRUE ) ;
    else
        return( FALSE ) ;

}  // end of function empty_stack()

void  push( struct lstack * nstack , struct info_node * new_node )
{
    new_node->next = nstack->top ;
    nstack->top = new_node ;
    return ;
}  // end of function push()


struct info_node*  pop( struct lstack * nstack )
{
    struct info_node* preturn = NULL ;

    if( empty_stack( nstack ) )
    {
        printf("ERROR: Stack is Empty \n\n" ) ;
        return( preturn ) ;
    }
    else
    {
        preturn = nstack->top ;
        nstack->top = nstack->top->next ;
        return( preturn ) ;
    }

} // end of function pop()




void  create_queue( struct lqueue * nqueue)
{
    nqueue->front = NULL ;
    nqueue->rear  = NULL ;
    return ;

}  // end of function create_queue()

int   empty_queue( struct lqueue* nqueue )
{
    if ( ( nqueue->front == NULL ) && ( nqueue->rear  == NULL ) )
        return( TRUE ) ;
    else
        return( FALSE ) ;

}  // end of function empty_queue()

void  queue_insert( struct lqueue * nqueue , struct info_node * new_node )
{

    if( empty_queue( nqueue ) )
    {
        new_node->next = NULL ;
        nqueue->front = new_node ;
        nqueue->rear  = new_node ;
    }
    else
    {
        nqueue->rear->next = new_node ;
        new_node->next = NULL ;
        nqueue->rear = new_node ;
    }

    return ;
}  // end of function queue_insert ()


struct info_node*  queue_remove( struct lqueue * nqueue )
{
    struct info_node* preturn = NULL ;

    if( empty_queue( nqueue ) )
    {
        printf("ERROR:  Queue is Empty \n\n" ) ;
        return( preturn ) ;
    }
    else if ( nqueue->front == nqueue->rear )
    {
        preturn = nqueue->front  ;
        nqueue->front = NULL  ;
        nqueue->rear  = NULL  ;
        return( preturn ) ;
    }
    else
    {
        preturn = nqueue->front  ;
        nqueue->front = nqueue->front->next  ;
        return( preturn ) ;
    }

} // end of function pop()

void  create_prq( struct prq_que*  ppque )
{
    ppque->top = NULL ;
    return ;

}   // end of function create_prq()


int   empty_prq( struct prq_que* ppque )
{
    if( ppque->top == NULL )
        return(TRUE ) ;
    else
        return(FALSE ) ;

}  // end of function empty_prq()


void  prq_insert( struct prq_que* ppque , struct info_node * nnode)
{

    struct info_node* move_pntr ;
    struct info_node* pre_pntr ;



    if( empty_prq( ppque ) )
    {
        ppque->top = nnode ;
        nnode->next = NULL ;
    }
    else
    {
        move_pntr = ppque->top ;
        pre_pntr = move_pntr ;

        while( ( move_pntr != NULL )&& ( nnode->weight > move_pntr->weight ) )
        {
            pre_pntr = move_pntr ;
            move_pntr = move_pntr->next ;
        }

        if( move_pntr == NULL )
        {
            pre_pntr->next = nnode ;
            nnode->next = NULL ;
        }
        else if( move_pntr == pre_pntr )
        {
            nnode->next = ppque->top ;
            ppque->top = nnode ;
        }
        else
        {
            nnode->next = move_pntr ;
            pre_pntr->next = nnode ;
        }


    }  // end of else ( not empty priority queue )


    return ;

} // end of function prq_insert()



struct info_node*  prq_remove( struct prq_que * ppque )
{

    struct info_node *  rnode = NULL ;

    if( empty_prq( ppque ) )
        printf("ERROR: Priority Queue is Empty \n") ;
    else
    {
        rnode = ppque->top ;
        ppque->top = ppque->top->next ;
    }
    return( rnode ) ;

}  // end of function prq_remove()