Main.c file #include "queue.h" #include #include #include

char testNewQueue(); char testEnqueue(); char testFront(); char testIsEmpty(); char testDequeue(); char testRandom(); char checkTail(struct Queue *Q, int target); void testJosephus();

int main(int argv, char **argc) { srand(time(0)); printf("Select Option from list. "); printf("0.) Run All Tests "); printf("1.) Test New Queue "); printf("2.) Test Enqueue "); printf("3.) Test Front "); printf("4.) Test isEmpty "); printf("5.) Test Dequeue "); printf("6.) Run Randomized Tests "); printf("7.) Josephus Puzzle "); printf("Enter Number of test to run: "); int testToRun = -1; int result = scanf("%d", &testToRun); if (result != 1 || testToRun < 0 || testToRun > 7) { printf("Invalid Menu Selection. "); return 1; } switch (testToRun) { case 7: testJosephus(); break; case 0: printf("Running ALL Tests "); case 1: if (!testNewQueue()) { return 1; } if (testToRun != 0) { break; }; case 2: if (!testEnqueue()) { return 1; } if (testToRun != 0) { break; }; case 3: if (!testFront()) { return 1; } if (testToRun != 0) { break; }; case 4: if (!testIsEmpty()) { return 1; } if (testToRun != 0) { break; }; case 5: if (!testDequeue()) { return 1; } if (testToRun != 0) { break; }; case 6: if (!testRandom()) { return 1; } if (testToRun != 0) { break; }; } return 0; }

char testNewQueue() { struct Queue *Q = newQueue(); if (Q == NULL) { printf("newQueue: FAILED "); printf("Calling newQueue returned NULL. "); return 0; } if (Q->head != NULL) { printf("newQueue: FAILED "); printf("Calling newQueue return object that did not have NULL head. "); return 0; } if (Q->tail != NULL) { printf("newQueue: FAILED "); printf("Calling newQueue return object that did not have NULL tail. "); return 0; } printf("newQueue: PASSED "); return 1; }

char testEnqueue() { struct Queue *Q = newQueue(); int tests = 10; // Check that elements are added in for (int i = 0; i < tests; i++) { enqueue(i, Q); // Sanity Check if (Q->head == NULL) { printf("enqueue: FAILED "); printf("Head Null After Enqueue Call! "); return 0; } if (Q->tail == NULL) { printf("enqueue: FAILED "); printf("Tail Null After Enqueue Call! "); return 0; } // Check for Value if (!checkTail(Q, i)) { printf("enqueue: FAILED "); printf("enqueue(%d,Q) did not add %d to tail of queue. ", i, i); printf("Tail Pointer must point to number. "); printQueue(Q); return 0; } } struct Node *ptr = Q->head; int count = 0; while (ptr != NULL) { if (ptr->value != count) { printf("Inserted Numbers from 0 to %d into Q. ", tests); printf("Did not find %d in correct location. ", count); printQueue(Q); return 0; } count++; ptr = ptr->next; } printf("enqueue: PASSED "); return 1; }

char testFront() { struct Queue *Q = newQueue(); if (front(Q) != -1) { printf("Front must return -1 on empty queue. "); printQueue(Q); printf("front: FAILED "); return 0; } enqueue(9, Q); if (front(Q) != 9) { printf("Called enqueue(9,Q) and 9 was not front afterwards. "); printQueue(Q); printf("front: FAILED "); return 0; } enqueue(7, Q); if (front(Q) != 9) { printf("Called enqueue(7,Q) after enqueue(9,Q) and 9 was not front " "afterwards. "); printQueue(Q); printf("front: FAILED "); return 0; } printf("front: PASSED "); return 1; }

char testIsEmpty() { struct Queue *Q = newQueue(); if (!isEmpty(Q)) { printf("Called isEmpty on a new Queue. "); printf("Function did not return true. "); printQueue(Q); printf("isEmpty: FAILED "); return 0; } enqueue(8, Q); if (isEmpty(Q)) { printf("Called isEmpty on Queue Containing 8. "); printf("Function did not return false. "); printQueue(Q); printf("isEmpty: FAILED "); return 0; } printf("isEmpty: PASSED "); return 1; }

char testDequeue() { struct Queue *Q = newQueue(); for (int i = 1; i < 6; i++) { enqueue(i, Q); } int expected = 1; while (!isEmpty(Q)) { if (front(Q) != expected) { printf("Expected %d at front of Queue but saw %d. ", expected, front(Q)); printf("Possible error in dequeue. "); printQueue(Q); printf("dequeue: FAILED "); return 0; } dequeue(Q); expected++; } if (expected != 6) { printf("Dequeue should have removed %d things but only removed %d. ", 6, expected); printf("Possible error in dequeue. "); printQueue(Q); printf("dequeue: FAILED "); return 0; }

printf("dequeue: PASSED "); return 1; }

char testRandom() { struct Queue *Q = newQueue(); for (int i = 0; i < 3; i++) { int size = rand() % 10 + 1; int *T = malloc(size * sizeof(int)); for (int k = 0; k < size; k++) { T[k] = rand() % 100 + 1; } for (int k = 0; k < size; k++) { enqueue(T[k], Q); } for (int k = 0; k < size; k++) { if (front(Q) != T[k]) { printf("Attempted to enqueue and dequeue repeatedly from Queue. "); printf("Failed on Repetition %d on Queue. ", i); printf("Tried to enqueue and dequeue: ["); for (int a = 0; a < size; a++) { printf("%d", T[a]); if (a + 1 != size) { printf(", "); } } printf("] "); printQueue(Q); printf("Random Values: FAILED "); return 0; } dequeue(Q); } } printf("Random Values: PASSED "); return 1; }

char checkTail(struct Queue *Q, int target) { struct Node *ptr = Q->tail; return ptr->value == target; }

void testJosephus() { int n; int m; printf("Enter Number of People (N): "); scanf("%d", &n); printf("Enter Person to Eliminate (M): "); scanf("%d", &m); int *R = josephus(n, m); printf("Order Eliminated: "); for (int i = 0; i < n; i++) { printf("%d", R[i]); if (i + 1 < n) { printf(" "); } } printf(" "); free(R); return; } queue.h

#ifndef _QUEUE_H_ #define _QUEUE_H_

struct Node{ int value; /**< The value stored at this node. */ struct Node* next; /**< A pointer to the next node in the list. */ }; typedef struct Node Node;

struct Queue{ Node* head; Node* tail; }; typedef struct Queue Queue;

Queue* newQueue(); char isEmpty(Queue* Q);

void enqueue(int v, Queue* Q);

int front(Queue* Q);

void dequeue(Queue* Q);

void printQueue(Queue* Q); int* josephus(int n, int m);

#endif Following needs to be completed: Part 1

The goal of this assignment is to implement and use a queue. You will implement the queue using the framework provided. This is a specialized version of a linked list.

You are provided with two files. You will create the third file.

main.c - A collection of tests for your queue. DO NOT CHANGE THIS FILE

queue.h - Prototypes and Data Structures needed for the assignment. DO NOT CHANGE THIS FILE

queue.c - CREATE this file. Then implement all the functions described in queue.h.

Note You can just have josephus return NULL to implement and test this part. The implementation is described in the next section.

You can test the queue you are implementing using main.c. Once it is completely implemented, you should pass all the tests in main.c. See code for more details. We advise you look through main.c to see what the tests do.

The following are the expected tests and outputs of the code.

Test 01

 % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 1 newQueue: PASSED 

Test 02

 % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 2 enqueue: PASSED 

Test 03

 % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 3 front: PASSED 

Test 04

 % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 4 isEmpty: PASSED 

Test 05

 % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 5 dequeue: PASSED 

Test 06

 % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 6 Random Values: PASSED 

Test 00

 % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 0 Running ALL Tests newQueue: PASSED enqueue: PASSED front: PASSED isEmpty: PASSED dequeue: PASSED Random Values: PASSED