============================================ vis/COMPILE 12:32:04_Thursday_16_May_2002 ============================================ ===== 433-253 Project 2 Testing ===== --- queue.h SUBMITTED --- queue.c SUBMITTED --- pqueue.h SUBMITTED --- pqueue.c SUBMITTED --- comparison.txt SUBMITTED Compiling with gcc -I../data -I. ../data/sim.c queue.c pqueue.c -o sim... Compiling with gcc -I../data -I. ../data/sim2.c queue.c pqueue.c -o sim2... ============================================ vis/RESULT 12:32:04_Thursday_16_May_2002 ============================================ === Testing with sim.c and sim2.c === Testing with sim.c (small memory) ---sim testing : Output is correct. Testing with sim2.c (large memory) ---sim2 testing: Output is correct. ============================================ vis/sim.out 12:32:04_Thursday_16_May_2002 ============================================ 0 manager check: Idle lane 5 customer 0 arrives wanting 10 things 7 customer 1 arrives wanting 15 things 9 customer 2 arrives wanting 20 things 10 manager check: Idle lane 11 customer 3 arrives wanting 25 things 13 customer 4 arrives wanting 30 things 15 customer 5 arrives wanting 4 things 17 customer 6 arrives wanting 9 things 19 customer 7 arrives wanting 14 things 20 manager check: Idle lane 21 customer 8 arrives wanting 19 things 23 customer 9 arrives wanting 24 things 25 customer 10 arrives wanting 29 things 26 customer 5 chooses lane 0 (queue length 1) 26 checkout start for customer 5 27 customer 11 arrives wanting 3 things 28 customer 0 chooses lane 0 (queue length 2) 29 customer 12 arrives wanting 8 things 30 manager check: 30 checkout end for customer 5 30 checkout start for customer 0 31 customer 13 arrives wanting 13 things 33 customer 14 arrives wanting 18 things 35 customer 15 arrives wanting 23 things 36 customer 11 chooses lane 0 (queue length 2) 37 customer 16 arrives wanting 28 things 38 customer 6 chooses lane 0 (queue length 3) 39 customer 17 arrives wanting 2 things 40 customer 1 chooses lane 0 (queue length 4) 40 manager check: 40 checkout end for customer 0 40 checkout start for customer 11 41 customer 18 arrives wanting 7 things 43 customer 19 arrives wanting 12 things 43 checkout end for customer 11 43 checkout start for customer 6 45 customer 20 arrives wanting 17 things 46 customer 17 chooses lane 0 (queue length 3) 47 customer 21 arrives wanting 22 things 48 customer 12 chooses lane 0 (queue length 4) 49 customer 22 arrives wanting 27 things 50 customer 7 chooses lane 0 (queue length 5) 50 manager check: Long queues - better open another lane! 51 customer 23 arrives wanting 1 things 52 customer 2 chooses lane 0 (queue length 6) 52 checkout end for customer 6 52 checkout start for customer 1 53 customer 24 arrives wanting 6 things 55 customer 25 arrives wanting 11 things 55 Lane 1 is now open 56 customer 23 chooses lane 1 (queue length 1) 56 checkout start for customer 23 57 customer 26 arrives wanting 16 things 57 checkout end for customer 23 58 customer 18 chooses lane 1 (queue length 1) 58 checkout start for customer 18 59 customer 27 arrives wanting 21 things 60 customer 13 chooses lane 1 (queue length 2) 60 manager check: 61 customer 28 arrives wanting 26 things 62 customer 8 chooses lane 1 (queue length 3) 63 customer 29 arrives wanting 0 things 64 customer 3 chooses lane 1 (queue length 4) 65 customer 30 arrives wanting 5 things 65 checkout end for customer 18 65 checkout start for customer 13 66 customer 29 chooses lane 1 (queue length 4) 67 customer 31 arrives wanting 10 things 67 checkout end for customer 1 67 checkout start for customer 17 68 customer 24 chooses lane 1 (queue length 5) 69 customer 32 arrives wanting 15 things 69 checkout end for customer 17 69 checkout start for customer 12 70 customer 19 chooses lane 0 (queue length 4) 70 manager check: 71 customer 33 arrives wanting 20 things 72 customer 14 chooses lane 0 (queue length 5) 73 customer 34 arrives wanting 25 things 74 customer 9 chooses lane 1 (queue length 6) 75 customer 35 arrives wanting 30 things 76 customer 4 chooses lane 0 (queue length 6) 77 customer 36 arrives wanting 4 things 77 checkout end for customer 12 77 checkout start for customer 7 78 customer 30 chooses lane 0 (queue length 6) 78 checkout end for customer 13 78 checkout start for customer 8 79 customer 37 arrives wanting 9 things 80 customer 25 chooses lane 1 (queue length 6) 80 manager check: Long queues - better open another lane! 81 customer 38 arrives wanting 14 things 82 customer 20 chooses lane 1 (queue length 7) 83 customer 39 arrives wanting 19 things 84 customer 15 chooses lane 0 (queue length 7) 85 customer 40 arrives wanting 24 things 85 Lane 2 is now open 86 customer 10 chooses lane 2 (queue length 1) 86 checkout start for customer 10 87 customer 41 arrives wanting 29 things 88 customer 36 chooses lane 2 (queue length 2) 89 customer 42 arrives wanting 3 things 90 customer 31 chooses lane 2 (queue length 3) 90 manager check: 91 customer 43 arrives wanting 8 things 91 checkout end for customer 7 91 checkout start for customer 2 92 customer 26 chooses lane 2 (queue length 4) 93 customer 44 arrives wanting 13 things 94 customer 21 chooses lane 2 (queue length 5) 95 customer 45 arrives wanting 18 things 96 customer 16 chooses lane 2 (queue length 6) 97 customer 46 arrives wanting 23 things 97 checkout end for customer 8 97 checkout start for customer 3 98 customer 42 chooses lane 2 (queue length 7) 99 customer 47 arrives wanting 28 things 100 customer 37 chooses lane 1 (queue length 7) 100 manager check: Long queues - better open another lane! 101 customer 48 arrives wanting 2 things 102 customer 32 chooses lane 0 (queue length 7) 103 customer 49 arrives wanting 7 things 104 customer 27 chooses lane 2 (queue length 8) 105 Lane 3 is now open 106 customer 22 chooses lane 3 (queue length 1) 106 checkout start for customer 22 108 customer 48 chooses lane 3 (queue length 2) 110 customer 43 chooses lane 3 (queue length 3) 110 manager check: 111 checkout end for customer 2 111 checkout start for customer 19 112 customer 38 chooses lane 3 (queue length 4) 114 customer 33 chooses lane 3 (queue length 5) 115 checkout end for customer 10 115 checkout start for customer 36 116 customer 28 chooses lane 3 (queue length 6) 119 checkout end for customer 36 119 checkout start for customer 31 120 customer 49 chooses lane 3 (queue length 7) 120 manager check: Long queues - better open another lane! 122 customer 44 chooses lane 2 (queue length 7) 122 checkout end for customer 3 122 checkout start for customer 29 122 checkout end for customer 29 122 checkout start for customer 24 123 checkout end for customer 19 123 checkout start for customer 14 124 customer 39 chooses lane 1 (queue length 6) 125 Lane 4 is now open 126 customer 34 chooses lane 4 (queue length 1) 126 checkout start for customer 34 128 checkout end for customer 24 128 checkout start for customer 9 129 checkout end for customer 31 129 checkout start for customer 26 130 manager check: 133 checkout end for customer 22 133 checkout start for customer 48 134 customer 45 chooses lane 4 (queue length 2) 135 checkout end for customer 48 135 checkout start for customer 43 136 customer 40 chooses lane 4 (queue length 3) 138 customer 35 chooses lane 4 (queue length 4) 140 manager check: 141 checkout end for customer 14 141 checkout start for customer 4 143 checkout end for customer 43 143 checkout start for customer 38 145 checkout end for customer 26 145 checkout start for customer 21 146 customer 46 chooses lane 4 (queue length 5) 148 customer 41 chooses lane 3 (queue length 5) 150 manager check: 151 checkout end for customer 34 151 checkout start for customer 45 152 checkout end for customer 9 152 checkout start for customer 25 157 checkout end for customer 38 157 checkout start for customer 33 158 customer 47 chooses lane 4 (queue length 5) 160 manager check: 163 checkout end for customer 25 163 checkout start for customer 20 167 checkout end for customer 21 167 checkout start for customer 16 169 checkout end for customer 45 169 checkout start for customer 40 170 manager check: 171 checkout end for customer 4 171 checkout start for customer 30 176 checkout end for customer 30 176 checkout start for customer 15 177 checkout end for customer 33 177 checkout start for customer 28 180 checkout end for customer 20 180 manager check: 180 checkout start for customer 37 189 checkout end for customer 37 189 checkout start for customer 39 190 manager check: 193 checkout end for customer 40 193 checkout start for customer 35 195 checkout end for customer 16 195 checkout start for customer 42 198 checkout end for customer 42 198 checkout start for customer 27 199 checkout end for customer 15 199 checkout start for customer 32 200 customer 50 arrives wanting 12 things 200 manager check: 203 checkout end for customer 28 203 checkout start for customer 49 204 customer 51 arrives wanting 17 things 208 customer 52 arrives wanting 22 things 208 checkout end for customer 39 210 manager check: Idle lane: lane 1 closed 210 checkout end for customer 49 210 checkout start for customer 41 212 customer 53 arrives wanting 27 things 214 checkout end for customer 32 216 customer 54 arrives wanting 1 things 219 checkout end for customer 27 219 checkout start for customer 44 220 customer 55 arrives wanting 6 things 220 manager check: Idle lane: lane 0 closed 221 customer 54 chooses lane 3 (queue length 2) 223 checkout end for customer 35 223 checkout start for customer 46 224 customer 56 arrives wanting 11 things 227 customer 50 chooses lane 2 (queue length 2) 228 customer 57 arrives wanting 16 things 230 manager check: 232 customer 58 arrives wanting 21 things 232 checkout end for customer 44 232 checkout start for customer 50 235 customer 55 chooses lane 2 (queue length 2) 236 customer 59 arrives wanting 26 things 239 checkout end for customer 41 239 checkout start for customer 54 240 customer 60 arrives wanting 0 things 240 manager check: 240 checkout end for customer 54 241 customer 51 chooses lane 3 (queue length 1) 241 checkout start for customer 51 243 customer 60 chooses lane 3 (queue length 2) 244 customer 61 arrives wanting 5 things 244 checkout end for customer 50 244 checkout start for customer 55 246 checkout end for customer 46 246 checkout start for customer 47 248 customer 62 arrives wanting 10 things 249 customer 56 chooses lane 4 (queue length 2) 250 manager check: 250 checkout end for customer 55 252 customer 63 arrives wanting 15 things 255 customer 52 chooses lane 2 (queue length 1) 255 checkout start for customer 52 256 customer 64 arrives wanting 20 things 257 customer 61 chooses lane 2 (queue length 2) 258 checkout end for customer 51 258 checkout start for customer 60 258 checkout end for customer 60 260 customer 65 arrives wanting 25 things 260 manager check: Idle lane: lane 3 closed 263 customer 57 chooses lane 4 (queue length 3) 264 customer 66 arrives wanting 30 things 268 customer 67 arrives wanting 4 things 269 customer 53 chooses lane 2 (queue length 3) 270 manager check: 271 customer 62 chooses lane 4 (queue length 4) 272 customer 68 arrives wanting 9 things 274 checkout end for customer 47 274 checkout start for customer 56 276 customer 69 arrives wanting 14 things 277 customer 58 chooses lane 4 (queue length 4) 277 checkout end for customer 52 277 checkout start for customer 61 279 customer 67 chooses lane 2 (queue length 3) 280 customer 70 arrives wanting 19 things 280 manager check: 282 checkout end for customer 61 282 checkout start for customer 53 284 customer 71 arrives wanting 24 things 285 customer 63 chooses lane 2 (queue length 3) 285 checkout end for customer 56 285 checkout start for customer 57 288 customer 72 arrives wanting 29 things 290 manager check: 291 customer 59 chooses lane 4 (queue length 4) 292 customer 73 arrives wanting 3 things 293 customer 68 chooses lane 2 (queue length 4) 296 customer 74 arrives wanting 8 things 299 customer 64 chooses lane 4 (queue length 5) 300 customer 75 arrives wanting 13 things 300 manager check: 301 checkout end for customer 57 301 customer 73 chooses lane 4 (queue length 5) 301 checkout start for customer 62 304 customer 76 arrives wanting 18 things 307 customer 69 chooses lane 2 (queue length 5) 308 customer 77 arrives wanting 23 things 309 checkout end for customer 53 309 checkout start for customer 67 310 manager check: 311 checkout end for customer 62 311 checkout start for customer 58 312 customer 78 arrives wanting 28 things 313 customer 65 chooses lane 4 (queue length 5) 313 checkout end for customer 67 313 checkout start for customer 63 315 customer 74 chooses lane 2 (queue length 4) 316 customer 79 arrives wanting 2 things 320 customer 80 arrives wanting 7 things 320 manager check: 321 customer 70 chooses lane 2 (queue length 5) 323 customer 79 chooses lane 4 (queue length 6) 324 customer 81 arrives wanting 12 things 327 customer 66 chooses lane 2 (queue length 6) 328 customer 82 arrives wanting 17 things 328 checkout end for customer 63 328 checkout start for customer 68 329 customer 75 chooses lane 2 (queue length 6) 330 manager check: Long queues - better open another lane! 332 customer 83 arrives wanting 22 things 332 checkout end for customer 58 332 checkout start for customer 59 335 customer 71 chooses lane 4 (queue length 6) 335 Lane 0 is now open 336 customer 84 arrives wanting 27 things 337 customer 80 chooses lane 0 (queue length 1) 337 checkout end for customer 68 337 checkout start for customer 80 337 checkout start for customer 69 340 customer 85 arrives wanting 1 things 340 manager check: 343 customer 76 chooses lane 0 (queue length 2) 344 customer 86 arrives wanting 6 things 344 checkout end for customer 80 344 checkout start for customer 76 345 customer 85 chooses lane 0 (queue length 2) 348 customer 87 arrives wanting 11 things 349 customer 72 chooses lane 0 (queue length 3) 350 manager check: 351 customer 81 chooses lane 0 (queue length 4) 351 checkout end for customer 69 351 checkout start for customer 74 352 customer 88 arrives wanting 16 things 356 customer 89 arrives wanting 21 things 357 customer 77 chooses lane 2 (queue length 5) 358 checkout end for customer 59 358 checkout start for customer 64 359 customer 86 chooses lane 0 (queue length 5) 359 checkout end for customer 74 359 checkout start for customer 70 360 manager check: 362 checkout end for customer 76 362 checkout start for customer 85 363 checkout end for customer 85 363 checkout start for customer 72 365 customer 82 chooses lane 0 (queue length 4) 370 manager check: 371 customer 78 chooses lane 2 (queue length 5) 373 customer 87 chooses lane 0 (queue length 5) 378 checkout end for customer 64 378 checkout end for customer 70 378 checkout start for customer 73 378 checkout start for customer 66 379 customer 83 chooses lane 4 (queue length 5) 380 manager check: 381 checkout end for customer 73 381 checkout start for customer 65 387 customer 88 chooses lane 4 (queue length 5) 390 manager check: 392 checkout end for customer 72 392 checkout start for customer 81 393 customer 84 chooses lane 2 (queue length 5) 400 manager check: 401 customer 89 chooses lane 0 (queue length 5) 404 checkout end for customer 81 404 checkout start for customer 86 406 checkout end for customer 65 406 checkout start for customer 79 408 checkout end for customer 66 408 checkout end for customer 79 408 checkout start for customer 75 408 checkout start for customer 71 410 manager check: 410 checkout end for customer 86 410 checkout start for customer 82 420 manager check: 421 checkout end for customer 75 421 checkout start for customer 77 427 checkout end for customer 82 427 checkout start for customer 87 430 manager check: 432 checkout end for customer 71 432 checkout start for customer 83 438 checkout end for customer 87 438 checkout start for customer 89 440 manager check: 444 checkout end for customer 77 444 checkout start for customer 78 450 manager check: 454 checkout end for customer 83 454 checkout start for customer 88 459 checkout end for customer 89 460 manager check: Idle lane: lane 0 closed 470 checkout end for customer 88 470 manager check: Idle lane: lane 4 closed 472 checkout end for customer 78 472 checkout start for customer 84 480 manager check: 490 manager check: 499 checkout end for customer 84 500 manager check: Idle lane 510 manager check: Idle lane 520 manager check: Idle lane 530 manager check: Idle lane 540 manager check: Idle lane 550 manager check: Idle lane 560 manager check: Idle lane 570 manager check: Idle lane 580 manager check: Idle lane 590 manager check: Idle lane 600 manager check: Idle lane 610 manager check: Idle lane 620 manager check: Idle lane 630 manager check: Idle lane 640 manager check: Idle lane 650 manager check: Idle lane 660 manager check: Idle lane 670 manager check: Idle lane 680 manager check: Idle lane 690 manager check: Idle lane 700 manager check: Idle lane 710 manager check: Idle lane 720 manager check: Idle lane 730 manager check: Idle lane 740 manager check: Idle lane 750 manager check: Idle lane 760 manager check: Idle lane 770 manager check: Idle lane 780 manager check: Idle lane 790 manager check: Idle lane 800 manager check: Idle lane 810 manager check: Idle lane 820 manager check: Idle lane 830 manager check: Idle lane 840 manager check: Idle lane 850 manager check: Idle lane 860 manager check: Idle lane 870 manager check: Idle lane 880 manager check: Idle lane 890 manager check: Idle lane 900 manager check: Idle lane 910 manager check: Idle lane 920 manager check: Idle lane 930 manager check: Idle lane 940 manager check: Idle lane 950 manager check: Idle lane 960 manager check: Idle lane 970 manager check: Idle lane 980 manager check: Idle lane 990 manager check: Idle lane ============================================ src/comparison.txt 12:32:02_Thursday_16_May_2002 ============================================ ALGORITHMS AND DATA STRUCTURES 433-253 - University of Melbourne PROJECT 2 Colin Cheong - 134835 cheongc@students.cs.mu.oz.au Description: comparison.txt - analysis of project QUEUES------------------------------------------------------------------------- The Queue implementation is based on the Haskell prototype code provided but converted into C code. Basically, the struct definition of queue in queue.h has been transformed to be a struct of 2 queuelists (which are essentially linked lists of type person). The first and second linked lists are used to pop and insert items respectively. If the first list is empty upon pop, it is given the reverse of the second list. The linked lists do not use a tail pointer so it does not conflict with the specification requirement. The prototype version of the queue implementation utilises a fixed size array of persons, in a struct that contains int values of the head and tail of this array. Because of this, when a queuesize of less than 20(QUEUE_LEN_LIMIT) is stored in the prototype, memory is wasted. It is also limited therefore to queuesizes of less than 21 as well. It does not check for queue_add overflow, and if the QUEUE_LEN_LIMIT is increased, this just makes the implementation more inefficient with regards to memory and small queues. The new implementation has improved memory efficiency. Since we are now using linked lists, we create linked lists dynamically - ie. only when new nodes are actually required. Thus we only use as much memory as we need as well as taking care of the overflow issue. The time complexity of queue_add in the new implementation is O(1). The new item(person) is simply added to the front of the second linked list. In the queue_rm function, the best case complexity is O(1) also, if the first list is not empty. But if it is not, there has to be O(N) exchanges depending on the length (N) of the second list. An alternative efficient implementation could be creating a single circular linked list where you can traverse either back or forth. This would include a static pointer to the head, and the tail item pointing back to the head. In order to add an item, it is placed to the head, the previous head linked to the new item next and vice versa, and the tail next relinked to the new head and vice versa. Accessing the tail then from the head would be O(1), as well as adding. However the specification stated that we were unable to use a list based queue implementation utilising a tail pointer. PQUEUES------------------------------------------------------------------------- The prototype pqueue implementation is based on heap sort. Yet again there are several bugs/limitations. In the prototype it states that if two events of the same time are added to the pqueue, then the latter one should be considered to have the greater time. The prototype does not do this. The new implementation takes care of the equal time issue, and this is commented upon within the relevant code of the pqueue_add function. The prototype version of the pqueue implementation also utilises a fixed size array of events. This is limited by PQUEUE_LEN_LIM (100). As with queue, a pqueuesize of less than 100 is wasting memory (as well as risking getting back random junk from an illegal-initialized array reference) and also limited to pqueue size of less than 101. Once again, It does not check for pqueue_add overflow, and if the PQUEUE_LEN_LIM is increased, this just makes the implementation more inefficient with regards to memory and small pqueues. The new implementation is based on BST's (Binary Search Trees). As with queues, the binary search tree is similar to linked lists in regard to memory consumption and efficiency. It creates new nodes dynamically, as it is needed. Hence it can support arbitrarily long priority queues, and does not have the overflow issue. The time complexity of the prototype implementation which is based on heap sort is 2lgN comparisons or O(NlogN) on worst case scenarios for pqueue_add. It is only O(1) to insert the new item into the array, but the time complexity is spent due to having to sort the array again via the upheap function. The same can be said for pqueue_rm, it is O(1), as the maximum item should be at the head of the array, but the time complexity here is spent on the downheap function sort. As a little side note, heapsort also has the property of being in-place. For the new BST based implementation, if all values are in reverse sorted order, a stick in decreasing order will be created (equivalent to a singly linked list). This will create the worst case scenario for pqueue_add and pqueue_rm. In pqueue_add, O(N) comparisons will have to be made, and in pqueue_rm the time complexity would also be linear O(N) to get to the lower left item. However, since the specification states that "An early event can be added to the pqueue after a late event." In other words, events should be random, so the worst case scenarios should not be applicable in reality. On average then, search hits on a truly random BST should yield 2lnN~= 1.39LgN or O(logN) from N keys. We are required to perform our own performance analysis on our BST based pqueue for the simulation. I considered using the (timex sim) command on a CS machine for an empirical analysis, but this was not recommended in the FAQ specification, as doing so would require an alteration to sim.c to make the simulation run for longer. Therefore, I took the step of adding code to the pqueue_rm function that would keep track of the amount of comparisons, the size of the current pqueue and the event->time being returned. The code is commented out on submission. Here is a sample of the output to stdout as a result of the extra code. REMOVE DONE on 0 with 0 comparisons with 92 nodes 0 manager check: Idle lane REMOVE DONE on 5 with 1 comparisons with 92 nodes 5 customer 0 arrives wanting 10 things REMOVE DONE on 7 with 1 comparisons with 92 nodes 7 customer 1 arrives wanting 15 things REMOVE DONE on 9 with 1 comparisons with 92 nodes 9 customer 2 arrives wanting 20 things REMOVE DONE on 10 with 2 comparisons with 92 nodes To compute the time complexity I added the average of all the ratios of the comparisons divided by the size N nodes. This was the method suggested in the FAQ specification. The total for queue_rm was 1005 comparisons and aggregate N size of 19,311. (Might not be totally precise but precision not really required) This is somewhere between O(logN) and O(NlogN). I did the same for pqueue_add, and these are the results I got. 6527 comparisons and aggregate N size of 18,845. Again, this is somewhere between O(logN) and O(NlogN). In both cases, it is closer to being O(logN). This is comparable then to the time complexities encountered with heap sort. However bear in mind BST's have the ability to dynamically allocate memory as opposed to a fixed array size allocation required in heapsort. There are some alternative efficient implementations that might be applicable for pqueue. The first is a BST Splay Insert pqueue_add function. Splaying the BST during insert keeps the tree balanced, therefore the worst case linear time complexities cannot exist. The number of comparisons used when a splay BST is built from N insertions into an initially empty tree is O(NlogN). Another option might be to implement the heap purely in a Binary Tree form, without the use of arrays. This, in theory addresses the issue of being efficient with regard to memory memory, but it is not very practical when trying to implement the actual code. ============================================ src/queue.h 12:32:02_Thursday_16_May_2002 ============================================ /* ALGORITHMS AND DATA STRUCTURES 433-253 - University of Melbourne PROJECT 2 Colin Cheong - 134835 cheongc@students.cs.mu.oz.au Description: Header file for queue.c */ //defines type queuelist (of people - assumes type person already defined). typedef struct queuelist_s* queuelist; struct queuelist_s { person data; queuelist next; }; //defines type queue (2 lists of queuelist; list1 for popping, list2 for inserting) typedef struct queue_s* queue; struct queue_s { queuelist list1; queuelist list2; int size; }; /*INTERFACE DEFINITIONS FOR ABSTRACT DATA TYPES*/ extern queue queue_init(); extern int queue_len(queue); extern void queue_add(queue, person); extern void queue_rm(queue); extern person queue_head(queue); ============================================ src/queue.c 12:32:02_Thursday_16_May_2002 ============================================ /* ALGORITHMS AND DATA STRUCTURES 433-253 - University of Melbourne PROJECT 2 Colin Cheong - 134835 cheongc@students.cs.mu.oz.au Description: Implementation of queue of people using ADT */ #include #include #include "person.h" #include "queue.h" //function prototype definitions static queuelist insert (queuelist, person); static queuelist reverselist (queuelist); static void delete (queuelist); /* static void printlists( queue ); static void printsublist( queuelist ); */ /* initialise a new empty queue*/ /***********************************************************/ queue queue_init() { queue newqueue; newqueue = (queue) malloc((size_t)sizeof(struct queue_s)) ; if (newqueue == NULL) { fprintf(stderr, "Error: Memory allocation error: queue_init\n"); exit (EXIT_FAILURE); } //set queue to be empty (NULL) newqueue->list1=NULL; newqueue->list2=NULL; newqueue->size=0; return newqueue; } /*return length of queue*/ /***********************************************************/ int queue_len(queue q) { return q->size; } /* adds person to end of queue*/ /***********************************************************/ void queue_add(queue q, person p) { queuelist newqueue; newqueue = (queuelist) malloc((size_t)sizeof(struct queuelist_s)) ; if (newqueue == NULL) { fprintf(stderr, "Error: Memory allocation error\n"); exit (EXIT_FAILURE); } newqueue->data = p; newqueue->next = q->list2; q->list2 = newqueue; q->size++; //increment queue length //printlists(q); return; } /* removes (permanent) person from head*/ /***********************************************************/ void queue_rm(queue q) { //printf("REMOVE HEAD PERMANANT"); //printlists(q); if (q->list1 == NULL) { //list1 empty if (q->list2 !=NULL) { //both lists empty! //reverse list2 into list1 q->list1 = reverselist(q->list2); q->list2 = NULL; } else { fprintf(stderr, "Error: Trying to pop empty list\n"); return; } } q->list1 = q->list1->next; //increment pointer to next head q->size--; //decrement queue length // printlists(q); } /*function to reverse a given list*/ /***********************************************************/ static queuelist reverselist (queuelist head) { queuelist reversedlist = NULL; //storage for return while (head !=NULL) { reversedlist = insert (reversedlist, head->data); head = head->next; } delete (head); //free memeory return reversedlist; } /*function to delete node and free up memory*/ /***********************************************************/ static void delete (queuelist doomednode) { queuelist temp; while (doomednode != NULL){ temp = doomednode; doomednode = doomednode->next; free (temp); } return; } /*function insert a value to front of list (LIFO - stack)*/ /***********************************************************/ static queuelist insert (queuelist head, person insertvalue ) { queuelist newn; newn = malloc(sizeof(queuelist)); if (newn!=NULL) { newn->data = insertvalue; newn->next = head; } else { fprintf (stderr, "Error: Memory allocation error\n"); exit(EXIT_FAILURE); } return newn; } /* returns person@head of queue unchanged; return person pointed to by head*/ /***********************************************************/ person queue_head(queue q) { //printf("REMOVE HEAD UNCHANGED"); //printlists(q); if (q->list1 == NULL) { //list1 empty if (q->list2 !=NULL) { //list1 empty but list2 not //reverse list2 into list1 q->list1 = reverselist(q->list2); q->list2 = NULL; } else { //both lists empty! fprintf(stderr, "Error: Trying to pop empty list\n"); return; } } return q->list1->data; //increment pointer to new head } /* static void printlists( queue q ) { printf( "\n** -forward : " ); printsublist( q->list1 ); printf( "\n** -reverse : " ); printsublist( q->list2 ); printf( "\n" ); return; } static void printsublist( queuelist tmp ) { while ( tmp!=NULL ) { printf( "%d -> " , tmp->data->id ); tmp = tmp->next; } printf( "NULL" ); return; } */ ============================================ src/pqueue.c 12:32:02_Thursday_16_May_2002 ============================================ /* ALGORITHMS AND DATA STRUCTURES 433-253 - University of Melbourne PROJECT 2 Colin Cheong - 134835 cheongc@students.cs.mu.oz.au Description: Implentation of priority queue */ #include #include #include "event.h" #include "pqueue.h" static void bstpqueue_add(bstpqueue, event); static bstpqueue create_pqueue(event); /*used for performance analaysis static int nodecount; static int comparisons;*/ /* initialise a new empty pqueue*/ /***********************************************************/ pqueue pqueue_init() { pqueue newpqueue; //printf("INIT PQUEUE\n"); newpqueue = (pqueue) malloc((size_t)sizeof(struct pqueue_s)) ; if (newpqueue == NULL) { fprintf(stderr, "Error: Memory allocation error: pqueue_init\n"); exit (EXIT_FAILURE); } //set pqueue to be empty (NULL), size 0 newpqueue->node=NULL; newpqueue->size=0; return newpqueue; } /* returns length (size) of pqueue*/ /***********************************************************/ int pqueue_len(pqueue pq) { return pq->size; } /* Add event to pqueue*/ /***********************************************************/ void pqueue_add(pqueue pq, event e) { bstpqueue newbstpqueue; if (pq->node == NULL) {//pq initially emptyh pq->node = create_pqueue(e); } else { bstpqueue_add(pq->node, e); } /*performance analysis printf("\nADD DONE on %4d with %d comparisons with %d nodes\n", e->time, comparisons, pq->size); nodecount += pq->size; printf("nodecount %d \n", nodecount ); printf("comparisons %d \n", comparisons ); */ //increment size count pq->size++; } static void bstpqueue_add(bstpqueue curr, event e) { while (TRUE) {//delete for recursive if ( curr->data->time > e->time ) { //comparisons++; //used for performance analysis if ( curr->left == NULL ) { curr->left = create_pqueue(e); break;//delete for recursive } else { curr=curr->left; //go down left //bstpqueue_add( curr->left , e); /(RECURSIVE VERSION) } } /*for all ELSE we mean when curr->data->time <=(less than or equal to) e->time, hence all events with the same time are added to the right node (hence larger than the one already in the queue which was added first). When it comes to removing the min, the pqueue_rm function will find the one added first first, since the latter one will have been added to the right.*/ else { //comparisons++; //used for performance analysis if ( curr->right == NULL ) { curr->right = create_pqueue(e); break;//delete for recursive } else { curr = curr->right; //go down right //bstpqueue_add( curr->right , e); (RECURSIVE VERSION) } } } return; } static bstpqueue create_pqueue( event e ) { bstpqueue newbstpqueue; //create new bstpqueue and assign event to its struct newbstpqueue = malloc( (size_t) sizeof(struct bstpqueue_s) ); if ( newbstpqueue==NULL ) { fprintf(stderr, "Error: Memory allocation error\n"); exit (EXIT_FAILURE); } newbstpqueue->left = NULL; newbstpqueue->right = NULL; newbstpqueue->data = e; return newbstpqueue; } /* removes "minimum" event, returns event*/ /***********************************************************/ event pqueue_rm(pqueue pq) { bstpqueue curr, marker=NULL; event e; // int comparisons=0;//(used for performance analysis) if ( pq->node == NULL ) { fprintf( stderr , "Error : Cannot pop empty queue!\n" ); // exit (EXIT_FAILURE); return; } curr = pq->node; while ( curr->left != NULL ) { marker = curr; //marker node curr = curr->left; //traverse to the min item //comparisons++; //(used for performance analysis) } e = curr->data; //set min item //delete node permanantly from tree if ( marker == NULL ) { //pq->node removed, reassign to right link pq->node = curr->right; } else { //join right side of deleted node marker->left = curr->right; } /* performance analysis printf("\nREMOVE DONE on %4d with %d comparisons with %d nodes", e->time, comparisons, pq->size); nodecount += pq->size; printf("RATIO %d \n", nodecount ); printf("RATIO %d \n", comparisons ); */ //decrement size pq->size--; return e; } ============================================ src/pqueue.h 12:32:02_Thursday_16_May_2002 ============================================ /* ALGORITHMS AND DATA STRUCTURES 433-253 - University of Melbourne PROJECT 2 Colin Cheong - 134835 cheongc@students.cs.mu.oz.au Description: Header file for pqueue.c */ #define TRUE 1 //define TRUE /*type definition for BST based priority queue (assume type event already defined. We use a min heap to represent the priority queue.*/ typedef struct bstpqueue_s *bstpqueue; struct bstpqueue_s { bstpqueue left; event data; bstpqueue right; }; typedef struct pqueue_s *pqueue; struct pqueue_s { int size; bstpqueue node; }; /*INTERFACE DEFINITIONS FOR ABSTRACT DATA TYPES*/ extern pqueue pqueue_init(); extern int pqueue_len(pqueue); extern void pqueue_add(pqueue, event); extern event pqueue_rm(pqueue); /* extern void pqueue_dump(pqueue); */ /* not implemented in prototype */