halfordC

EvanAndC

Sep 30th, 2020
1,048
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*Evan Macintosh Program 3
  2.  This program creates a queue with a dynamic array and contains functions for queue operations, such as
  3.     1) Creating the queue
  4.     2) adding and removing from the queue
  5.     3) testing whether the queue is full, half-full, and empty
  6.     4) growing or shrinking the queue by a factor of 2
  7. */
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include "queue.h"
  11.  
  12. /*This function creates a new queue
  13.     IN: a size, a pointer of where to put the next element
  14.     OUT: a new queue
  15. */
  16. float* create_queue(int capacity, int* tail){
  17.     *tail=0;                                    //this variable represents where the next element is to be placed
  18.     return (float*) malloc(sizeof(float) * capacity);
  19. }
  20.  
  21. /*This function adds a FLOAT to the queue.
  22.     IN: the queue, the tail pointer, the capacity pointer, the new value to add
  23.     OUT: "a queue with the new value added"
  24. */
  25. void add(float* queue, int* tail, int* capacity, float new_value){
  26.     if(test_full(tail, capacity) == 1){     //if the queue is full
  27.         grow(queue, tail, capacity);            //grow it
  28.     }
  29.     int i = (*tail);
  30.     //*(queue + *(tail))= new_value;            //add the new item
  31.     queue[i]=new_value;
  32.     //((*queue) + *(tail)) = new_value;         //add the new item; THE ORIGINAL WAY
  33.     (*tail)++;                                  //update the tail
  34. }
  35.  
  36. /*This function does the trivial task of seeing if the queue is full
  37.     IN: the tail pointer, the capacity pointer
  38.     OUT: 1 if full, 0 if not
  39. */
  40. int test_full(int* tail, int* capacity){
  41.     if (tail == capacity-1){return 1;}  //if the tail is at the end
  42.     return 0;                                   //the queue isnt full
  43. }
  44.  
  45. /*This function doubles the size of the queue and copies over all the 'old' values
  46.     IN: the queue pointer, the tail pointer, the capacity pointer
  47.     OUT: "a bigger queue"
  48. */
  49. void grow(float* queue, int* tail, int* capacity){
  50.     float* tmp=(float*)malloc(sizeof(float) * (*capacity) * 2);//temp array
  51.     int i=0;
  52.     for(i; i<(*tail); i++){         //loop across the array
  53.         tmp[i]=queue[i];                //copy the values over to the new array
  54.     }
  55.     (*capacity) *= 2;                   //double the size of the queue
  56.     free(queue);                        //free up the old queue
  57.     queue = tmp;                        //reassign the pointer to the queue
  58. }
  59.  
  60. /*This function performs the trivial task of determining whether or not the queue is empty
  61.     IN: the tail pointer
  62.     OUT: 0 if empty, >0 if not
  63. */
  64. int test_empty(int* tail){
  65.     return (*tail);         //returning 0 means it is empty, anything else means it's not
  66. }
  67.  
  68. /*This function removes the first item in the queue
  69.     IN: the queue pointer, the tail pointer, the capacity pointer
  70.     OUT: the first item in the queue
  71. */
  72. float deque(float* queue, int* tail, int* capacity){
  73.     float ret_val = 0.0;                            //the return value
  74.     if (test_empty(tail) != 0){         //if the queue isnt empty
  75.         ret_val = queue[0];                         //assign the return value
  76.         int i=0;
  77.         for(i; i<(*tail); i++){                 //shift left loop
  78.             queue[i]=queue[i+1];                    //do the shift
  79.         }
  80.         (*tail)--;                                  //reduce tail
  81.         //>>><<<
  82.         if(test_half_full(tail, capacity) == 1 && test_empty(tail) > 0){//if the queue is half full or less
  83.             shrink(queue, tail, capacity);      //shrink the queue
  84.         }
  85.     }
  86.     return ret_val;
  87. }
  88.  
  89. /*This function performs the trivial task of determining if the queue is half full
  90.     IN: the tail pointer, the capacity pointer
  91.     OUT: 1 if > half full, 0 if not
  92. */
  93. int test_half_full(int* tail, int* capacity){
  94.     if((*tail) > (*capacity)/2) return 1;   //if the next spot to fill is greater than half way
  95.     return 0;
  96. }
  97.  
  98. /*This function shrinks the queue by a factor of 2 (via >>)
  99.     IN: the queue pointer, the tail pointer, the capacity pointer
  100.     OUT: "a shrunk queue"
  101. */
  102. void shrink(float* queue,int* tail, int* capacity){
  103.     int t_capacity = *capacity;
  104.     float* tmp = (float*)malloc(sizeof(float) * t_capacity / 2);//create a new temporary array
  105.     int i=0;
  106.     for(i; i<(*tail); i++){             //loop for copying elements
  107.         tmp[i]=queue[i];                    //copy things over
  108.     }
  109.     (*capacity) /=2;                        //divide the size by 2
  110.     //(*capacity) >> 1;                     //divide the size by 2
  111.     free (queue);                           //free up the old queue
  112.     queue = tmp;                            //reassign the pointer to the queue
  113. }
  114.  
RAW Paste Data