This file contains the definition of the interface for a dynamic array. * You can find descriptions of the dynamic array functions, including their * parameters and their return values, in dynarray.c. * * You should not modify this file. */

#ifndef __DYNARRAY_H #define __DYNARRAY_H

/* * Structure used to represent a dynamic array. */ struct dynarray;

/* * Dynamic array interface function prototypes. Refer to dynarray.c for * documentation about each of these functions. */ struct dynarray* dynarray_create(); void dynarray_free(struct dynarray* da); int dynarray_size(struct dynarray* da); void dynarray_insert(struct dynarray* da, void* val); void dynarray_remove(struct dynarray* da, int idx); void* dynarray_get(struct dynarray* da, int idx); void dynarray_set(struct dynarray* da, int idx, void* val);

#endif

THIS IS THE IMPLEMENTATION FILE FOR DYNARRAY, CAN NOT CHANGE ANYTHING ALREADY IN HERE, MUST USE THESE, BUT CAN

ADD FUNCTIONS TO IT

/* * This file contains a simple implementation of a dynamic array. See the * documentation below for more information on the individual functions in * this implementation. * * You should not modify this file. */

#include #include

#include \"dynarray.h\"

/* * This structure is used to represent a single dynamic array. */ struct dynarray { void** data; int size; int capacity; };

#define DYNARRAY_INIT_CAPACITY 8

/* * This function allocates and initializes a new, empty dynamic array and * returns a pointer to it. */ struct dynarray* dynarray_create() { struct dynarray* da = malloc(sizeof(struct dynarray)); assert(da);

da->data = malloc(DYNARRAY_INIT_CAPACITY * sizeof(void*)); assert(da->data); da->size = 0; da->capacity = DYNARRAY_INIT_CAPACITY;

return yes; }

/* * This function frees the memory associated with a dynamic array. Freeing * any memory associated with values stored in the array is the responsibility * of the caller. * * Params: * da - the dynamic array to be destroyed. May not be NULL. */ void dynarray_free(struct dynarray* da) { assert(da); free(da->data); free(da); }

/* * This function returns the size of a given dynamic array (i.e. the number of * elements stored in it, not the capacity). */ int dynarray_size(struct dynarray* da) { assert(da); return da->size; }

/* * Auxilliary function to perform a resize on a dynamic array's underlying * storage array. */ void _dynarray_resize(struct dynarray* da, int new_capacity) { assert(new_capacity > da->size);

/* * Allocate space for the new array. */ void** new_data = malloc(new_capacity * sizeof(void*)); assert(new_data);

/* * Copy data from the old array to the new one. */ for (int i = 0; i size; i++) { new_data[i] = da->data[i]; }

/* * Put the new array into the dynarray struct. */ free(da->data); da->data = new_data; da->capacity = new_capacity; }

/* * This function inserts a new value to a given dynamic array. The new element * is always inserted at the *end* of the array. * * Params: * da - the dynamic array into which to insert an element. May not be NULL. * val - the value to be inserted. Note that this parameter has type void*, * which means that a pointer of any type can be passed. */ void dynarray_insert(struct dynarray* da, void* val) { assert(da);

/* * Make sure we have enough space for the new element. Resize if needed. */ if (da->size == da->capacity) { _dynarray_resize(da, 2 * da->capacity); }

/* * Put the new element at the end of the array. */ da->data[da->size] = val; da->size++; }

/* * This function removes an element at a specified index from a dynamic array. * All existing elements following the specified index are moved forward to * fill in the gap left by the removed element. * * Params: * da - the dynamic array from which to remove an element. May not be NULL. * idx - the index of the element to be removed. The value of `idx` must be * between 0 (inclusive) and n (exclusive), where n is the number of * elements stored in the array. */ void dynarray_remove(struct dynarray* da, int idx) { assert(da); assert(idx size && idx >= 0);

/* * Move all elements behind the one being removed forward one index, * overwriting the element to be removed in the process. */ for (int i = idx; i size - 1; i++) { da->data[i] = da->data[i+1]; }

da->size--; }

/* * This function returns the value of an existing element in a dynamic array. * * Params: * da - the dynamic array from which to get a value. May not be NULL. * idx - the index of the element whose value should be returned. The value * of `idx` must be between 0 (inclusive) and n (exclusive), where n is the * number of elements stored in the array. */ void* dynarray_get(struct dynarray* da, int idx) { assert(da); assert(idx size && idx >= 0);

return da->data[idx]; }

/* * This function updates (i.e. overwrites) the value of an existing element in * a dynamic array. * * Params: * da - the dynamic array in which to set a value. May not be NULL. * idx - the index of the element whose value should be updated. The value * of `idx` must be between 0 (inclusive) and n (exclusive), where n is the * number of elements stored in the array. * val - the new value to be set. Note that this parameter has type void*, * which means that a pointer of any type can be passed. */ void dynarray_set(struct dynarray* da, int idx, void* val) { assert(da); assert(idx size && idx >= 0);

da->data[idx] = val; }

THIS IS PQ.H , PLEASE DONT CHANGE ANYTHING ALREADY IN HERE, BUT FEEL FREE TO ADD NEW FUNCTIONS TO IT

#ifndef __PQ_H #define __PQ_H

/* * Structure used to represent a priority queue. */ struct pq;

/* * Priority queue interface function prototypes. Refer to pq.c for * documentation about each of these functions. */ struct pq* pq_create(); void pq_free(struct pq* pq); int pq_isempty(struct pq* pq); void pq_insert(struct pq* pq, void* value, int priority); void* pq_first(struct pq* pq); int pq_first_priority(struct pq* pq); void* pq_remove_first(struct pq* pq);

#endif THIS IS THE IMPLEMENTATION FILE FOR PQ.C, DO NOT MODIFY THE PARAMETERS OR NAMES OF FUNCTIONS ALREADY IN HERE, FEEL FREE TO ADD AND USE NEW FUNCTIONS THOUGH, MUST USE ALL FUNCTIONS IN HERE THOUGH.

PQ.C

#include

#include \"pq.h\" #include \"dynarray.h\"

/* * This is the structure that represents a priority queue. You must define * this struct to contain the data needed to implement a priority queue. */ struct pq;

/* * This function should allocate and initialize an empty priority queue and * return a pointer to it. */ struct pq* pq_create() { /* * FIXME: */ return NULL; }

/* * This function should free the memory allocated to a given priority queue. * Note that this function SHOULD NOT free the individual elements stored in * the priority queue. That is the responsibility of the caller. * * Params: * pq - the priority queue to be destroyed. May not be NULL. */ void pq_free(struct pq* pq) { /* * FIXME: */ return; }

/* * This function should return 1 if the specified priority queue is empty and * 0 otherwise. * * Params: * pq - the priority queue whose emptiness is to be checked. May not be * NULL. * * Return: * Should return 1 if pq is empty and 0 otherwise. */ int pq_isempty(struct pq* pq) { /* * FIXME: */ return 1; }

/* * This function should insert a given element into a priority queue with a * specified priority value. Note that in this implementation, LOWER priority * values are assigned to elements with HIGHER priority. In other words, the * element in the priority queue with the LOWEST priority value should be the * FIRST one returned. * * Params: * pq - the priority queue into which to insert an element. May not be * NULL. * value - the value to be inserted into pq. * priority - the priority value to be assigned to the newly-inserted * element. Note that in this implementation, LOWER priority values * should correspond to elements with HIGHER priority. In other words, * the element in the priority queue with the LOWEST priority value should * be the FIRST one returned. */ void pq_insert(struct pq* pq, void* value, int priority) { /* * FIXME: */ return; }

/* * This function should return the value of the first item in a priority * queue, i.e. the item with LOWEST priority value. * * Params: * pq - the priority queue from which to fetch a value. May not be NULL or * empty. * * Return: * Should return the value of the first item in pq, i.e. the item with * LOWEST priority value. */ void* pq_first(struct pq* pq) { /* * FIXME: */ return NULL; }

/* * This function should return the priority value of the first item in a * priority queue, i.e. the item with LOWEST priority value. * * Params: * pq - the priority queue from which to fetch a priority value. May not be * NULL or empty. * * Return: * Should return the priority value of the first item in pq, i.e. the item * with LOWEST priority value. */ int pq_first_priority(struct pq* pq) { /* * FIXME: */ return 0; }

/* * This function should return the value of the first item in a priority * queue, i.e. the item with LOWEST priority value, and then remove that item * from the queue. * * Params: * pq - the priority queue from which to remove a value. May not be NULL or * empty. * * Return: * Should return the value of the first item in pq, i.e. the item with * LOWEST priority value. */ void* pq_remove_first(struct pq* pq) { /* * FIXME: */ return NULL; }