Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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 *);
```
fun.h

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 {
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 {
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 {
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 {
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 }
```
fun.c

2014-06-17 11:58