1. A secret society scheduler
The Ancient and Honored Society of Accepted and Received C Programmers accepts new members according to a rigidly enforced traditional procedure. Each candidate for membership, who is known to the Society only by an int ID number, is given a score (also an int, and guaranteed to be non-negative) and a number of endorsements, initially 1. The candidates are ordered by their scores divided by the number of endorsements, rounding down as is traditional in C. Whoever has the lowest score is inducted into the Society, and gives an endorsement to a candidate of their choosing, increasing the recipient's number of endorsements by 1. If the recipient does not exist or has already been accepted into the Society, this endorsement is wasted. If there is a tie for the smallest value in the score/endorsements rankings, the candidate with the smaller ID wins.
After a candidate is accepted, the next best candidate is accepted, and so on until no candidates remain. Because a candidates' positions may change over time as they accumulate more endorsements, it is not enough simply to sort the candidates by score; instead, at each iteration the remaining candidates must be examined anew to see who is worthiest for admission to the Society.
2. Your task
The Society has asked you to write a program that simulates their admissions process.
The input to your program is provided on stdin, as dictated by the Elevated Masters. The first line of the input is the number of candidates n in decimal notation as yielded by the mystical %d directive of printf. Each following line contains two ints encoded as if with "%d %d"; the first is the score of the candidate, and the second is the ID of the candidate to which this candidate will give his or her endorsement when accepted. The ID of the candidate is not represented; instead, the first candidate has ID 0, then next ID 1, and so on up to n-1 for the last candidate. These lines are terminated by end-of-file.
The output of your program should be a list of the accepted candidates in order of acceptance. For each candidate, you should print the ID number and the number of endorsements obtained by the candidate at the time of acceptance, in the format governed by the sign of "%d %d\n" in the sacred language of the printf. In the unlikely event that some candidates endorse themselves, their counts should not include the extra self-endorsements.
For example, suppose the input consists of the lines
17 2 25 0 28 6
Then the first candidate to be admitted is 0, who provides an endorsement to 2. Since 2 now has two endorsements, its effective score is 28/2 = 14 and it is admitted before 1. The endorsement of 6 by 2 vanishes, since there is no candidate 6. It follows that 1 is finally admitted with one endorsement. The output of the program would be
0 1 2 2 1 1
More test inputs and their corresponding outputs can be found in /c/cs223/Hwk8 on the Zoo.
3. Submitting your assignment
Using the ancient and venerable /c/cs223/bin/submit 8 command, submit either a single file scheduler.c, or multiple files together with a Makefile that creates a program scheduler when called with make scheduler.
4. Sample solution
This is the main scheduler program:
1 /* new design: pq holds (id, score) pairs */
2 /* when a score drops, we just insert a new (id, score) pair and ignore the other one when it pops out */
3
4 #include <stdio.h>
5 #include <stdlib.h>
6 #include <assert.h>
7
8 #include "pq.h"
9
10 struct pq_entry {
11 int key;
12 int score;
13 };
14
15 struct candidate {
16 int admitted; /* true if already a member */
17 int endorsements;
18 int score;
19 int endorses; /* who this candidate endorses */
20 };
21
22 static int
23 compare_pq_entries(const void *a, const void *b)
24 {
25 const struct pq_entry *aa;
26 const struct pq_entry *bb;
27
28 aa = a;
29 bb = b;
30
31 if(aa->score == bb->score) {
32 return aa->key - bb->key;
33 } else {
34 return aa->score - bb->score;
35 }
36 }
37
38 static void
39 insert_candidate(PQ pq, struct candidate *candidates, int i)
40 {
41 struct pq_entry pqe;
42
43 pqe.key = i;
44 pqe.score = candidates[i].score / candidates[i].endorsements;
45
46 pq_insert(pq, &pqe);
47 }
48
49 int
50 main(int argc, char **argv)
51 {
52 int count; /* return value of scanf */
53 int i;
54 int n;
55 struct candidate *candidates;
56 PQ pq;
57 struct pq_entry pqe;
58 int endorsed;
59
60 pq = pq_create(sizeof(struct pq_entry), compare_pq_entries);
61
62 count = scanf("%d", &n);
63 assert(count == 1);
64
65 candidates = malloc(sizeof(*candidates) * n);
66 assert(candidates);
67
68 /* load 'em up */
69 for(i = 0; i < n; i++) {
70 candidates[i].admitted = 0;
71 candidates[i].endorsements = 1;
72 count = scanf("%d %d", &candidates[i].score, &candidates[i].endorses);
73 assert(count == 2);
74 assert(candidates[i].score >= 0);
75
76 insert_candidate(pq, candidates, i);
77 }
78
79 /* move 'em out */
80 while(!pq_is_empty(pq)) {
81 pq_delete_min(pq, &pqe);
82
83 if(!candidates[pqe.key].admitted) {
84 /* new winner */
85 candidates[pqe.key].admitted = 1;
86 printf("%d %d\n", pqe.key, candidates[pqe.key].endorsements);
87
88 /* apply endorsement */
89 endorsed = candidates[pqe.key].endorses;
90
91 if(endorsed >= 0 && endorsed < n && !candidates[endorsed].admitted) {
92 candidates[endorsed].endorsements++;
93
94 /* put in another copy with lower score */
95 insert_candidate(pq, candidates, endorsed);
96 }
97 }
98 }
99
100 pq_destroy(pq);
101 free(candidates);
102
103 return 0;
104 }
105
106
107
108
109
110
111
112
113
114
115
116
117
And this is the priority queue module it uses:
1 /* generic priority queue */
2
3 typedef struct pq *PQ;
4
5 /* create a new empty priority queue */
6 /* element_length is the size of an element in bytes */
7 /* compare is a comparision function that returns
8 * <0 if its first argument is less than its second
9 * 0 if they are equal
10 * >0 if the first argument is greater than the second. */
11 PQ pq_create(int element_length, int (*compare)(const void *, const void *));
12
13 /* free a priority queue */
14 void pq_destroy(PQ);
15
16 /* add an element to the priority queue */
17 /* the contents of the element are COPIED from elt */
18 void pq_insert(PQ, const void *elt);
19
20 /* returns nonzero if PQ is empty */
21 int pq_is_empty(PQ);
22
23 /* delete the minimum element of the priority queue */
24 /* and COPY its contents to retval */
25 /* it is an error to call this on an empty queue */
26 void pq_delete_min(PQ, void *retval);
27
28 /* utility function: blows up if heap invariant is violated */
29 void pq_sanity_check(PQ);
1 #include <stdlib.h>
2 #include <string.h>
3 #include <assert.h>
4
5 #include "pq.h"
6
7 struct pq {
8 int element_length;
9 int (*compare)(const void *, const void *);
10 int n; /* number of elements */
11 int size; /* number of slots in data */
12 void *swap_space; /* element_length bytes used for swapping */
13 void *data;
14 };
15
16 #define PQ_INITIAL_SIZE (128)
17
18 PQ
19 pq_create(int element_length, int (*compare)(const void *, const void *))
20 {
21 PQ pq;
22
23 pq = malloc(sizeof(*pq));
24 assert(pq);
25
26 pq->element_length = element_length;
27 pq->compare = compare;
28 pq->n = 0;
29 pq->size = PQ_INITIAL_SIZE;
30
31 pq->swap_space = malloc(pq->element_length);
32 assert(pq->swap_space);
33
34 pq->data = malloc(pq->element_length * pq->size);
35 assert(pq->data);
36
37 return pq;
38 }
39
40 void
41 pq_destroy(PQ pq)
42 {
43 free(pq->data);
44 free(pq->swap_space);
45 free(pq);
46 }
47
48 int
49 pq_is_empty(PQ pq)
50 {
51 return pq->n == 0;
52 }
53
54 /* Child(i, 0) and Child(i, 1) are children of i */
55 /* Parent(i) is parent of i */
56 #define Child(i, x) (2*(i)+1+(x))
57 #define Parent(i) (((i)-1)/2)
58
59 #define NUM_CHILDREN (2)
60
61 /* compute the address of position i in the data field */
62 #define REF(pq, i) ((void *) (((char *) (pq)->data) + (pq)->element_length * i))
63
64 /* swap elements at indexes i1 and i2 */
65 static void
66 pq_swap(PQ pq, int i1, int i2)
67 {
68 memcpy(pq->swap_space, REF(pq, i1), pq->element_length);
69 memcpy(REF(pq, i1), REF(pq, i2), pq->element_length);
70 memcpy(REF(pq, i2), pq->swap_space, pq->element_length);
71 }
72
73 void
74 pq_insert(PQ pq, const void *elt)
75 {
76 int floater; /* new element */
77
78 while(pq->n + 1 > pq->size) {
79 pq->size *= 2;
80 pq->data = realloc(pq->data, pq->element_length * pq->size);
81 assert(pq->data);
82 }
83
84 /* copy the new element in */
85 floater = pq->n++;
86 memcpy(REF(pq, floater), elt, pq->element_length);
87
88 /* float it up until it is at the top */
89 /* or it is no smaller than its parent */
90 while(floater > 0 && pq->compare(REF(pq, floater), REF(pq, Parent(floater))) <= 0) {
91 /* it's smaller than its parent */
92 pq_swap(pq, floater, Parent(floater));
93 floater = Parent(floater);
94 }
95 }
96
97 void
98 pq_delete_min(PQ pq, void *retval)
99 {
100 int floater; /* previous loser floating down */
101 int small_child; /* smaller child of floater */
102
103 assert(!pq_is_empty(pq));
104
105 /* first copy out the winner */
106 memcpy(retval, REF(pq, 0), pq->element_length);
107
108 --(pq->n);
109
110 if(pq_is_empty(pq)) {
111 /* pq empty, nothing to do */
112 return;
113 }
114
115 /* else */
116 memcpy(REF(pq, 0), REF(pq, pq->n), pq->element_length);
117
118 floater = 0;
119
120 for(;;) {
121 /* find smaller child of floater */
122 if(Child(floater, 0) >= pq->n) {
123 return; /* no children, bail out */
124 } else if(Child(floater, 1) >= pq->n) {
125 small_child = Child(floater, 0);
126 } else if(pq->compare(REF(pq, Child(floater, 0)), REF(pq, Child(floater, 1))) < 0) {
127 small_child = Child(floater, 0);
128 } else {
129 small_child = Child(floater, 1);
130 }
131
132 /* is floater <= small_child? */
133 if(pq->compare(REF(pq, floater), REF(pq, small_child)) <= 0) {
134 /* yes, we are done */
135 return;
136 } else {
137 /* no, swap and continue floating down */
138 pq_swap(pq, floater, small_child);
139 floater = small_child;
140 }
141 }
142 }
143
144 void
145 pq_sanity_check(PQ pq)
146 {
147 int i;
148 int j;
149
150 assert(pq->n >= 0);
151 assert(pq->n <= pq->size);
152
153 for(i = 0; i < pq->n; i++) {
154 for(j = 0; j < NUM_CHILDREN; j++) {
155 if(Child(i, j) < pq->n) {
156 assert(pq->compare(REF(pq, i), REF(pq, Child(i, j))) <= 0);
157 }
158 }
159 }
160 }