EvanAndC

/*Evan Macintosh Program 3
 This program creates a queue with a dynamic array and contains functions for queue operations, such as
    1) Creating the queue
    2) adding and removing from the queue
    3) testing whether the queue is full, half-full, and empty
    4) growing or shrinking the queue by a factor of 2
*/
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

/*This function creates a new queue
    IN: a size, a pointer of where to put the next element
    OUT: a new queue
*/
float* create_queue(int capacity, int* tail){
    *tail=0;                                    //this variable represents where the next element is to be placed
    return (float*) malloc(sizeof(float) * capacity);
}

/*This function adds a FLOAT to the queue.
    IN: the queue, the tail pointer, the capacity pointer, the new value to add
    OUT: "a queue with the new value added"
*/
void add(float* queue, int* tail, int* capacity, float new_value){
    if(test_full(tail, capacity) == 1){     //if the queue is full
        grow(queue, tail, capacity);            //grow it
    }
    int i = (*tail);
    //*(queue + *(tail))= new_value;            //add the new item
    queue[i]=new_value;
    //((*queue) + *(tail)) = new_value;         //add the new item; THE ORIGINAL WAY
    (*tail)++;                                  //update the tail
}

/*This function does the trivial task of seeing if the queue is full
    IN: the tail pointer, the capacity pointer
    OUT: 1 if full, 0 if not
*/
int test_full(int* tail, int* capacity){
    if (tail == capacity-1){return 1;}  //if the tail is at the end
    return 0;                                   //the queue isnt full
}

/*This function doubles the size of the queue and copies over all the 'old' values
    IN: the queue pointer, the tail pointer, the capacity pointer
    OUT: "a bigger queue"
*/
void grow(float* queue, int* tail, int* capacity){
    float* tmp=(float*)malloc(sizeof(float) * (*capacity) * 2);//temp array
    int i=0;
    for(i; i<(*tail); i++){         //loop across the array
        tmp[i]=queue[i];                //copy the values over to the new array
    }
    (*capacity) *= 2;                   //double the size of the queue
    free(queue);                        //free up the old queue
    queue = tmp;                        //reassign the pointer to the queue
}

/*This function performs the trivial task of determining whether or not the queue is empty
    IN: the tail pointer
    OUT: 0 if empty, >0 if not
*/
int test_empty(int* tail){
    return (*tail);         //returning 0 means it is empty, anything else means it's not
}

/*This function removes the first item in the queue
    IN: the queue pointer, the tail pointer, the capacity pointer
    OUT: the first item in the queue
*/
float deque(float* queue, int* tail, int* capacity){
    float ret_val = 0.0;                            //the return value
    if (test_empty(tail) != 0){         //if the queue isnt empty
        ret_val = queue[0];                         //assign the return value
        int i=0;
        for(i; i<(*tail); i++){                 //shift left loop
            queue[i]=queue[i+1];                    //do the shift
        }
        (*tail)--;                                  //reduce tail
        //>>><<<
        if(test_half_full(tail, capacity) == 1 && test_empty(tail) > 0){//if the queue is half full or less
            shrink(queue, tail, capacity);      //shrink the queue
        }
    }
    return ret_val;
}

/*This function performs the trivial task of determining if the queue is half full
    IN: the tail pointer, the capacity pointer
    OUT: 1 if > half full, 0 if not
*/
int test_half_full(int* tail, int* capacity){
    if((*tail) > (*capacity)/2) return 1;   //if the next spot to fill is greater than half way
    return 0;
}

/*This function shrinks the queue by a factor of 2 (via >>)
    IN: the queue pointer, the tail pointer, the capacity pointer
    OUT: "a shrunk queue"
*/
void shrink(float* queue,int* tail, int* capacity){
    int t_capacity = *capacity;
    float* tmp = (float*)malloc(sizeof(float) * t_capacity / 2);//create a new temporary array
    int i=0;
    for(i; i<(*tail); i++){             //loop for copying elements
        tmp[i]=queue[i];                    //copy things over
    }
    (*capacity) /=2;                        //divide the size by 2
    //(*capacity) >> 1;                     //divide the size by 2
    free (queue);                           //free up the old queue
    queue = tmp;                            //reassign the pointer to the queue
}