For this assignment, you are to implement a class of objects called Funs that represent functions that take an int as an argument and return an int. Some of these Funs will be wrappers for actual C functions. Others will be constant functions that always return the same value, or step functions based on looking up the input in a table supplied when the Fun is created, or compositions of two previously-constructed Funs. In each case, the interface used to call the Fun is the same: executing funCall(f, x) should return the value of f at x.
1. Header file
The interface for Funs is described in the following header file:
1 /* a Fun represents a function from ints to ints */
2 typedef struct fun Fun;
3
4 /* this routine calls a Fun and returns its value */
5 int funCall(const Fun *, int);
6
7 /* build a Fun whose value is constant */
8 Fun *funConstant(int);
9
10 /* build a Fun based on an actual function */
11 Fun *funFromFunction(int (*)(int));
12
13 /* build a Fun f from a table */
14 /* arguments are length of arrays n */
15 /* increasing array of input values */
16 /* array of corresponding output values */
17 /* value of funCall(f, x) is:
18 *
19 * output[0] when x < input[0]
20 * output[i] when input[i] <= x < input[i+1]
21 * output[n-1] when x >= input[n-1]
22 *
23 */
24 /* funFromTable should copy input and output, so
25 * that it continues to work even if they later change */
26 Fun *funFromTable(int n, const int *input, const int *output);
27
28 /* build a Fun by composing two Funs */
29 /* value at x is f(g(x)) */
30 /* does NOT copy f or g */
31 Fun *funCompose(const Fun *f, const Fun *g);
32
33 /* destroy a Fun, freeing any blocks allocated when it is created */
34 void funDestroy(Fun *);
This header defines four constructors (funConstant, funFromFunction, funFromTable, and funCompose), an accessor (funCall), and a destructor (funDestroy). Fun objects built using funConstant always return the same value. Fun objects built using funFromFunction return whatever the function they contain returns. Fun objects built from funFromTable return the output corresponding to the largest input in the table less than or equal to the input provided to funCall, or the output corresponding to the smallest input in the table if the input to funCall is even smaller. Finally, funCall(h, x) when h is a Fun object built using funCompose(f, g) should act like funCall(f, funCall(g, x)).
We have also provided a Makefile and basic test code illustrating use of Funs:
These files can be downloaded directly from this page, or can be found in /c/cs223/Hwk7/template. Your job is to provide the missing fun.c file that implements Funs.
2. Implementation issues
The four constructors generate Fun objects with very different behaviors when called using funCall. You should think carefully about how you intended to support these behaviors before jumping in and writing the code.
The funFromTable function should not rely on its input and output arrays staying the same (or even surviving) after it is called: whatever data is in these arrays should be stored as an independent copy inside the Fun object is some form. You should also make sure that when funCall is applied to a Fun built from a table, that it uses an efficient algorithm to find the appropriate table entry. The fact that the inputs are required to be sorted may be helpful here.
3. Submitting your assignment
Submit your fun.c file using /c/cs223/bin/submit 7 fun.c as usual. You can run /c/cs223/bin/testit 7 public to check your submitted file using the public test script in /c/cs223/Hwk7/test.public, which may or may not resemble the final test script.
4. Sample solution
1 #include <stdlib.h>
2 #include <assert.h>
3 #include <string.h>
4
5 #include "fun.h"
6
7 /* we do the cheap object-oriented trick */
8
9 /* Note missing semicolon at end.
10 * This lets us put it in later */
11 #define FUN_HEADER \
12 /* how to call me */ \
13 int (*call)(const struct fun *self, int x); \
14 /* how to free me */ \
15 void (*destroy)(struct fun *self)
16
17 /* parent type */
18 struct fun {
19 FUN_HEADER;
20 };
21
22 int
23 funCall(const Fun *f, int x)
24 {
25 return f->call(f, x);
26 }
27
28 void
29 funDestroy(Fun *f)
30 {
31 f->destroy(f);
32 }
33
34 struct funFunction {
35 FUN_HEADER;
36 int (*f)(int); /* function to call */
37 };
38
39 static int
40 funCallFromFunction(const Fun *f, int x)
41 {
42 return ((struct funFunction *) f)->f(x);
43 }
44
45 Fun *
46 funFromFunction(int (*f)(int))
47 {
48 struct funFunction *ff;
49
50 ff = malloc(sizeof(*ff));
51 assert(ff);
52
53 ff->call = funCallFromFunction;
54 ff->destroy = (void (*)(Fun *)) free;
55 ff->f = f;
56
57 return (Fun *) ff;
58 }
59
60 struct funCompose {
61 FUN_HEADER;
62 const Fun *f;
63 const Fun *g;
64 };
65
66 static int
67 funCallCompose(const Fun *f, int x)
68 {
69 struct funCompose *ff;
70
71 ff = (struct funCompose *) f;
72
73 return funCall(ff->f, funCall(ff->g, x));
74 }
75
76 Fun *
77 funCompose(const Fun *f, const Fun *g)
78 {
79 struct funCompose *ff;
80
81 ff = malloc(sizeof(*ff));
82 assert(ff);
83
84 ff->call = funCallCompose;
85 ff->destroy = (void (*)(Fun *)) free;
86 ff->f = f;
87 ff->g = g;
88
89 return (Fun *) ff;
90 }
91
92 /* build a Fun whose value is constant */
93 Fun *
94 funConstant(int x)
95 {
96 int zero = 0;
97
98 return funFromTable(1, &zero, &x);
99 }
100
101 struct funTable {
102 FUN_HEADER;
103 int n;
104 int *input;
105 int *output;
106 };
107
108 static int
109 funCallTable(const Fun *f, int x)
110 {
111 struct funTable *ff;
112 int lo;
113 int hi;
114 int mid;
115
116 ff = (struct funTable *) f;
117
118 if(x <= ff->input[0]) {
119 return ff->output[0];
120 } else if(x >= ff->input[ff->n - 1]) {
121 return ff->output[ff->n - 1];
122 } else {
123 /* use binary search */
124 /* invariant is that input[lo] < x < input[hi] */
125 lo = 0;
126 hi = ff->n - 1;
127
128 while(hi > lo + 1) {
129 mid = (lo + hi) / 2;
130 if(x == ff->input[mid]) {
131 return ff->output[mid];
132 } else if(x < ff->input[mid]) {
133 hi = mid;
134 } else {
135 /* x > ff->input[mid] */
136 lo = mid;
137 }
138 }
139
140 return ff->output[lo];
141 }
142 }
143
144 static void
145 funDestroyTable(Fun *f)
146 {
147 struct funTable *ff;
148
149 ff = (struct funTable *) f;
150
151 free(ff->input);
152 free(ff->output);
153 free(ff);
154 }
155
156 Fun *
157 funFromTable(int n, const int *input, const int *output)
158 {
159 struct funTable *ff;
160
161 assert(n > 0);
162
163 ff = malloc(sizeof(*ff));
164 assert(ff);
165
166 ff->call = funCallTable;
167 ff->destroy = funDestroyTable;
168
169 ff->n = n;
170
171 ff->input = malloc(sizeof(int) * n);
172 memcpy(ff->input, input, sizeof(int) * n);
173
174 ff->output = malloc(sizeof(int) * n);
175 memcpy(ff->output, output, sizeof(int) * n);
176
177 return (Fun *) ff;
178 }