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 define functions and we often consider sets of mappings. For example, the function is even for integers could be defined as
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 Z x B = {(a, b) | a E Z ^ b E B} 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 math- ematics). 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 = {(1, 1), (2, 1), (3, 2), (4, 3), (5, 5), (6, 8), (7, 13), (8, 21)}
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 not subset of {1,2,...,7,8}.
Let's define a function called mappings that maps integers to integers. Given X, Y E Z ^ mappings <= X x Y then see image.
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 define 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.
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 specification file listed below is available for download off of the class Canvas pages. You will need to implement this module in file intPair.c . To aid you in your module development I have provided a Unity test file (intPairUnity.c) downloadable off 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
Here is a listing of the specification file mappings.h (also downloadable off of the Canvas class pages).
#include < limits.h >
#include < stdbool.h >
#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
A sample drive program, mappingsDrive.c, is given below. Note the command used on the com- mand line to compile the entire project.
#include < stdio.h >
#include < stdlib.h >
#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;
}