For this assignment, you are to implement a program ibid that converts a sequence of citations into a sequence of citations with back-references using the standard ibid. and op. cit. abbreviations.
1. Input
Your input, on stdin, consists of a sequence of lines, each of which contains a name or names followed by a comma, then some additional text. Some of these lines may be repeated. For example:
Moriarty, "On the Dynamics of an Asteroid," Journal of Selenological Metaphysics, 1904. Stargardt and Chudzinski, "Destructive Testing of C Programs," Fifth International Symposium on Cyberentomology, 2003. Stargardt and Chudzinski, "Destructive Testing of C Programs," Fifth International Symposium on Cyberentomology, 2003. Moriarty, "On the Dynamics of an Asteroid," Journal of Selenological Metaphysics, 1904. Moriarty, "Practical Applications of Solvents," Criminology Review Letters, 1906. Russano, "History of the Comma," Punctuality, 1997. Moriarty, "Practical Applications of Solvents," Criminology Review Letters, 1906. Stargardt and Chudzinski, "Destructive Testing of C Programs," Fifth International Symposium on Cyberentomology, 2003. Moriarty, "On the Dynamics of an Asteroid," Journal of Selenological Metaphysics, 1904.
If a line does not contain a comma, treat the entire line as the author list.
You may assume that the input is otherwise well-behaved: in particular, you may assume that every line ends with a newline, and that no line contains a null character.
2. Output
The output of your program, on stdout, should obey the following rules:
If a line is identical to the previous line, replace it with the string "ibid.".
If a line is identical to the most recent line with the same author(s) (everything up to the comma, or to end-of-line if there is no comma), replace it with "op. cit. " followed by the author(s).
- In all other cases, output the original line.
Here is the output corresponding to the sample input above:
Moriarty, "On the Dynamics of an Asteroid," Journal of Selenological Metaphysics, 1904. Stargardt and Chudzinski, "Destructive Testing of C Programs," Fifth International Symposium on Cyberentomology, 2003. ibid. op. cit. Moriarty Moriarty, "Practical Applications of Solvents," Criminology Review Letters, 1906. Russano, "History of the Comma," Punctuality, 1997. op. cit. Moriarty op. cit. Stargardt and Chudzinski Moriarty, "On the Dynamics of an Asteroid," Journal of Selenological Metaphysics, 1904.
Note that only the first repetition of On the Dynamics of an Asteroid gets an op. cit.. The last repetition can't be cited this way without referring to the more recent Practical Applications of Solvents by the same author.
3. Submitting your assignment
Submit any .c and .h files you need to build ibid, together with a Makefile that builds ibid when make is called with no arguments. Use /c/cs223/bin/submit 6 as usual.
A public test script is available in /c/cs223/Hwk6/test.public. You may run this script directly (it will work on files in the current directory), or may run it on your submitted files using /c/cs223/bin/testit 6 public.
4. Late policy
Starting with this assignment, the lateness penalty has been revised as follows:
- Late assignments will immediately lose 10% of the points earned.
- There is a 24-hour grace period during which no further points will be deducted.
- Following the grace period, points will decay linearly at the rate of 3%/hour until none remain.
The time of your assignment is measured by the last time that any file is submitted using /c/cs223/bin/submit.
5. Sample solution
1 /* Program for doing MLA-style bibliographic backreferences.
2 *
3 * Input is a sequence of bibliographic references, one per line,
4 * with the author list ending with a comma, e.g.
5 *
6 * Smith, "Destructive Testing of Programs," Journal of Explosive Research, 20(3):17--18
7 *
8 * Output:
9 *
10 * If a line is equal to its predecessor, print "ibid."
11 *
12 * If a line is equal to the last line with the same author, print "op. cit. " + name of author
13 *
14 * Otherwise print the line.
15 */
16
17 #include <stdio.h>
18 #include <stdlib.h>
19 #include <string.h>
20 #include <assert.h>
21
22 #define INITIAL_HASH_SIZE (512)
23
24 /* marker for end of key */
25 #define SEPARATOR (',')
26
27 /* prime for multiplication method */
28 #define PRIME (97)
29
30 struct hash {
31 size_t size; /* size of array */
32 size_t elts; /* number of nonempty positions */
33 char **table; /* contents */
34 };
35
36 /* hash function that ignores everything after first comma */
37 size_t
38 hash(const char *s)
39 {
40 size_t h = 0;
41
42 while(*s && *s != SEPARATOR) {
43 h = h * PRIME + *s;
44 s++;
45 }
46
47 return h;
48 }
49
50 /* equality tester that ignores everything after first comma in s1 */
51 int
52 keysEqual(const char *s1, const char *s2)
53 {
54 /* skip initial equal segment */
55 while(*s1 != '\0' && *s1 != SEPARATOR && *s2 != '\0' && *s2 != SEPARATOR) {
56 if(*s1 != *s2) {
57 return 0;
58 }
59 s1++;
60 s2++;
61 }
62
63 /* now see what happened */
64 return (*s1 == '\0' || *s1 == SEPARATOR) && (*s2 == '\0' || *s2 == SEPARATOR);
65 }
66
67 /* build an empty hash table of given initial size */
68 struct hash *
69 hashCreate(size_t size)
70 {
71 struct hash *h;
72
73 h = malloc(sizeof(struct hash));
74 assert(h);
75
76 h->size = size;
77 h->elts = 0;
78
79 h->table = calloc(h->size, sizeof(char *));
80 assert(h->table);
81
82 return h;
83 }
84
85 #define MAX_LOAD_FACTOR (0.5)
86
87 /* store a line in hash table, returning 1 if already present */
88 /* if another line with same key was present, it is freed and replaced */
89 int
90 hashStore(struct hash *h, char *line)
91 {
92 size_t pos;
93 struct hash *h2; /* for increasing size */
94 int found; /* did we find the exact line? */
95
96 /* check if hash table is getting too full */
97 while(h->elts + 1 > h->size * MAX_LOAD_FACTOR) {
98 /* make a new hash table that is bigger */
99 h2 = hashCreate(h->size * 2);
100
101 for(pos = 0; pos < h->size; pos++) {
102 if(h->table[pos]) {
103 hashStore(h2, h->table[pos]);
104 }
105 }
106
107 /* clone h2 into h */
108 free(h->table);
109 *h = *h2;
110 free(h2);
111 }
112
113 /* hash table OK, do the insertion */
114 for(pos = hash(line) % h->size;; pos = (pos + 1) % h->size) {
115 if(h->table[pos] == 0) {
116 /* nothing that matches is present */
117 h->table[pos] = line;
118 h->elts++;
119 return 0;
120 } else if(keysEqual(h->table[pos], line)) {
121 /* keys match, does line match? */
122 if(!strcmp(h->table[pos], line)) {
123 /* yes, got it */
124 found = 1;
125 } else {
126 /* no, replace old line */
127 found = 0;
128 }
129 /* old line gets freed and replaced either way */
130 free(h->table[pos]);
131 h->table[pos] = line;
132
133 return found;
134 }
135 }
136 }
137
138 void
139 hashDestroy(struct hash *h)
140 {
141 size_t pos;
142
143 for(pos = 0; pos < h->size; pos++) {
144 /* free is no-op on NULL */
145 free(h->table[pos]);
146 }
147
148 free(h->table);
149 free(h);
150 }
151
152 #define INITIAL_BUFSIZE (512)
153
154 /* read a line of input from f */
155 /* return 0 on EOF before getting any characters */
156 /* caller is responsible for freeing return value */
157 char *
158 getline(FILE *f)
159 {
160 char *buffer;
161 int size = INITIAL_BUFSIZE;
162 int top = 0;
163 int c;
164
165 buffer = malloc(size);
166 assert(buffer);
167
168 while((c = getchar()) != '\n') {
169 if(c == EOF) {
170 if(top == 0) {
171 /* got nothing */
172 free(buffer);
173 return 0;
174 } else {
175 /* pretend it's a newline */
176 break;
177 }
178 } else {
179 /* maybe resize */
180 /* -1 is to leave room for null */
181 while(top >= size-1) {
182 size *= 2;
183 buffer = realloc(buffer, size);
184 assert(buffer);
185 }
186 buffer[top++] = c;
187 }
188 }
189
190 buffer[top++] = '\0';
191
192 return realloc(buffer, top);
193 }
194
195 /* print line up to SEPARATOR to file */
196 void
197 putKey(const char *line, FILE *f)
198 {
199 while(*line && *line != SEPARATOR) {
200 fputc(*line++, f);
201 }
202 }
203
204 int
205 main(int argc, char **argv)
206 {
207 struct hash *h;
208 char *line;
209 char *prev_line;
210
211 if(argc != 1) {
212 fprintf(stderr, "Usage: %s\n", argv[0]);
213 return 1;
214 }
215
216 h = hashCreate(INITIAL_HASH_SIZE);
217
218 prev_line = 0;
219
220 while((line = getline(stdin)) != 0) {
221 if(prev_line && !strcmp(line, prev_line)) {
222 puts("ibid.");
223 /* keep old version in table */
224 free(line);
225 } else {
226 /* replace prev_line */
227 /* new line goes in table */
228 prev_line = line;
229 if(hashStore(h, line)) {
230 printf("op. cit. ");
231 putKey(line, stdout);
232 putchar('\n');
233 } else {
234 puts(line);
235 }
236 }
237 }
238
239 hashDestroy(h);
240
241 return 0;
242 }