Mapping Module Implementation
In mathematics a mapping is generally considered as a relation between two values. We can say, for example, that 5 is related to false and denote it as 5 -> false; we could think of this relation as \is even" for the value 5. Mappings can be represented as key-value pairs, i.e. (5; false). Mappings de ne functions and we often consider sets of mappings. For example, the function is even for integers could be defined
is _even = {: : : ; ( 2; true); ( 1; false); (0; true); (1; false); (2; true); : : :}
Where the domain consists of the set of all integers (Z) and the range is the set {true; false} (B). Note that for a mapping to represent a function it must represent a relation that associates each element in its domain set to a single value in the range set. This can also be referred to as the Cartesian product of sets Z and B, denoted as Z B = f(a; b) j a 2 Z ^ b 2 Bg where every value a is unique.
In Computer Science a mapping with a finite set for the domain is often referred to as a finite mapping (or finite function; note that this definition is different than a finite function in mathematics). Consider, for example, the following finite mapping/function for the first 8 Fibonacci numbers (which are 1,1,2,3,5,8,13,21):
fib = f(1; 1); (2; 1); (3; 2); (4; 3); (5; 5); (6; 8); (7; 13); (8; 21)g
We then say that fib(3) = 2, fib(7) = 13, etc. Note that this function returns no value, and is therefore undefined, for any domain value d such that d 2= f1; 2; : : : ; 7; 8g.
Let’s de ne a function called mappings that maps integers to integers. Given X; Y 2 Z ^ mappings X Y , then
8x 2 Z; 8y 2 Z; 8z 2 Z; ((x; y) 2 mappings ^ (x; z) 2 mappings) =) y = z
The primary objective for this project is to write an abstract data type (ADT) that implements the mappings type defined above. Essentially this will involve you writing code to de ne and maintain a list of pairs of integers where the first item in the pair is unique. To accomplish this you will also need to develop a simple ADT to represent and manipulate integer pairs.
Using intPair ADT to Manipulate Ordered Integer Pairs
The intPair ADT will be used to create and manipulate your ordered integer pairs. And whereas you will need to implement this module, you will not turn it in { I will use my own implementation to test your mappings module. The intPair.h speci cation le listed below is available for download o of the class Canvas pages. You will need to implement this module in le intPair.c . To aid
you in your module development I have provided a Unity test le (intPairUnity.c) downloadable o of the class Canvas pages.
#ifndef INTPAIR_H
#define INTPAIR_H
typedef struct {
int left, right;
} intPair;
void createPair(intPair* p,int l,int r); // returns pair (l,r) in p
int getLeft(intPair); // returns the left value in pair int getRight(intPair); // returns the right value in pair
void setLeft(intPair* p,int); // sets the left value in pair p void setRight(intPair* p,int); // sets the right value in pair p
char *toString(intPair); // returns a string representation of a pair;
// the pair (1,2) would be represented by "(1,2)"
#endif
Mappings Specification
Here is a listing of the specification file mappings.h (also downloadable o of the Canvas class pages).
#include
#include
#ifndef MAPPINGS_H
#define MAPPINGS_H
typedef struct {
intPair *data; // your data array
int arraySize, // the size of the array
listSize, // number of mappings in list
expandSize; // size of each expansion of list as needed
} mappings;
#define NOT_A_VALUE INT_MIN
mappings *createMappings(); // returns a malloc’ed mappings value
void destroyMappings(mappings*); // free’s both the data array & mappings structure
int addMapping(mappings*,intPair p); // adds p to end of list only if left value is unique; // returns index of value added, -1 if nothing is added;
// expands array as needed
int removeMapping(mappings*,int n); // removes mapping where left == n; returns index of item
// removed or -1 if item isn’t found
bool removeAt(mappings*,int i); // removes mapping at location i, returning true if item
// is removed; does nothing and returns false if item // does not exist
int funcCall(mappings* f,int l); // calls function f with l; returns NOT_A_VALUE if l // is not in domain of f
bool inDomain(mappings* f,int l); // returns true if l in domain of f, false otherwise
int size(mappings*); // returns number of pairs in list
bool isEmpty(mappings*); // returns true if mapping is empty, false otherwise
char *mappingsToString(mappings*); // returns a string representation of mapping; an empty
// mapping: "[]"; mapping (1,2),(2,3),(3,4) would be
// represented by s = "[(1,2),(2,3),(3,4)]"; string returned
// should be the exact necessary size to store string, i.e.
// strlen(s) = 19 stored in returned char array with 20 cells
#endif
Example of Driver Program in C
A sample drive program, mappingsDrive.c, is given below. Note the command used on the command line to compile the entire project.
#include
#include
#include "intPair.h"
#include "mappings.h"
int main(void){
mappings *m = createMappings();
for(int i = 1; i <=8; i++) {
intPair *ip = malloc(sizeof(intPair));
createPair(ip,i,i*2);
addMapping(m,*ip);
}
printf("%s\n",mappingsToString(m));
printf("m(%d) = %d\n",3,funcCall(m,3));
return 0;
}
Mapping Driver Code
#include
#include
#include "intPair.h"
#include "mappings.h"
int main(void)
{
char *str;
mappings *m = createMappings();
for (int i = 1; i <= 8; i++)
{
intPair *ip = malloc(sizeof(intPair));
createPair(ip, i, i * 2);
addMapping(m, *ip);
free(ip);
}
str = mappingsToString(m);
printf("%s\n", str);
free(str);
printf("m(%d) = %d\n", 3, funcCall(m, 3));
printf("\n");
printf("remove key 3 = %d\n", removeMapping(m, 3));
str = mappingsToString(m);
printf("%s\n", str);
free(str);
printf("m(%d) = %d\n", 3, funcCall(m, 3));
printf("\n");
printf("remove at 3 = %d\n", removeAt(m, 3));
str = mappingsToString(m);
printf("%s\n", str);
free(str);
printf("\n");
printf("In domain 1 = %d\n", inDomain(m, 1));
printf("In domain 2 = %d\n", inDomain(m, 2));
printf("In domain 3 = %d\n", inDomain(m, 3));
printf("Size = %d\n", size(m));
printf("Is Empty = %d\n", isEmpty(m));
destroyMappings(m);
return 0;
}