SET LIBRARY John T. Rine 01/01/2011 ======Objectives====== My library is available at:\\ http://lab46.corning-cc.edu/~jr018429/setLibrary.zip\\ \\ The objective of this project is to create a set library with which to write programs that can create, test, manipulate and destroy sets. This project is a requirement of the Discrete Structures course.\\ Currently, this library has only two set functions: * set parseSet(char *), * void displaySet(set), however, there are the following supporting functions used in the set functions above: * int cntChars(char *) * int checkSetNotation(char *) * int occurrences(char *, char) * int strEqu(char *, char *) ======Prerequisites====== In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved: * understand and use the C/C++ programming language * understand and use functions * understand and use pointers in general * understand and use malloc() to dynamically allocate memory * understand and use free() to deallocate memory * know how to create and use a static library ======Background====== The set library was developed for the CSCS 2330-Discrete Structures course. One of the areas that discrete structures or discrete mathematics deals with is set theory. The purpose of creating a set library is to practice using set theory in software. A specific application the instructor has in mind is for this library is poker, specifically, Texas hold'em. ======Scope====== As defined by the course instructor, Joe Oppenheim, the scope of this project was to create set related routines which do the following, and to implement them as a static library: * Create a set (convert a string in proper set notation to a set type data structure) * Print a set or list (convert a set type data structure to a string formatted in proper set notation) * Count members of a set * Check membership of an element to a set * Intersection of sets * Union of sets * Add elements to a set * Remove elements from a set * Replace an element in a set ======Attributes====== The course requirement for Data Structures projects are listed at:\\ http://lab46.corning-cc.edu/haas/fall2011/data/projects This project has the following project attributes described on that page: ^Attribute^Qty Needed^Description^ |Pointers|8|Indirection/dereferencing are demonstarted| |malloc/new|4|Utilization of dynamic memory allocation| |Libraries|4|Implementation/utilization of non-core libc library| \\ This project, therefore, is eligible for 16 attributes total, however, only 6 of these are achieveable per project, so project far exceeds the minimum attribut requirements.\\ ======Code====== My library is composed of the following functions:\\ **set.h**\\ set.h is the header file for the set library. It should be included in any .c library files whose function prototypes have been added to it. Also, it must be added to any programs utilizing the library's functions.\\ Example code:\\ //set.h //John T. Rine //October 15, 2011 //November 3, 2011 #ifndef _SET_H #define _SET_H struct Set { char ** setPtr; int numberOfElements; }; typedef struct Set set; set parseSet(char *); int cntChars(char *); int checkSetNotation(char *); int occurrences(char *, char); void displaySet(set); int strEqu(char *, char *); #endif **int strEqu(char *, char*)**\\ strEqu.c contains the function definition for the function that checks two strings for equality. If they are equal, TRUE is returned, otherwise FALSE is returned. This function will be used to test whether set elements are common between sets.\\ Example code:\\ //strEqu.c //John T. Rine //November 3, 2011 #include"set.h" int strEqu(char *str1, char *str2) { int var = 1; //equal int i = 0; while (!(*(str1 + i) == '\0' && *(str2 + i) == '\0')) { if (*(str1 + i) != *(str2 + i)) { var = 0; break; } i++; } return var; } **set parseSet(char *)**\\ parseSet.c contains the function definition for the function that parses an input string and creates, if possible, a set from the result of the parsing. parseSet contains the set library function int checkSetNotation(char *inputString)which checks that the input string is in proper set notation, if it isn't, an error is returned.\\ Example code:\\ //parseSet.c //John T. Rine //October 15, 2011 #include "set.h" #include set parseSet(char *setInput) { int i, count = 0; char **rowPtr = NULL; int stringCharacterPosition = 0; int elementNumber = 0; int elementCount = 0; int elementCharacterCount = 0; int oldElementCharacterCount = 0; int oldStringCharacterPosition = 0; set returnSet; if(checkSetNotation(setInput) == 0) exit(1); elementCount = occurrences(setInput, ',') + 1; rowPtr = malloc(sizeof(char *) * elementCount); while(*(setInput + stringCharacterPosition) != '\0') { if(*(setInput + stringCharacterPosition) == '{') stringCharacterPosition++; oldElementCharacterCount = elementCharacterCount; oldStringCharacterPosition = stringCharacterPosition; while(*(setInput + stringCharacterPosition) != ',' && *(setInput + stringCharacterPosition) != '}') { elementCharacterCount++; stringCharacterPosition++; } *(rowPtr + elementNumber) = malloc(sizeof(char) * (elementCharacterCount + 1)); count = 0; while(*(setInput + oldStringCharacterPosition) != ',' && *(setInput + oldStringCharacterPosition) != '}') { *(*(rowPtr + elementNumber) + count) = *(setInput + oldStringCharacterPosition); oldStringCharacterPosition++; count++; } *(*(rowPtr + elementNumber) + count) = '\0'; elementCharacterCount = 0; elementNumber++; stringCharacterPosition++; } returnSet.setPtr = rowPtr; returnSet.numberOfElements = elementNumber; return returnSet; } **int cntChars(char *)**\\ The function cntChars takes as its parameter a character pointer (the base address of a character array, a string, and returns the number of characters in the string up to the maximum size of an integer).\\ Example code:\\ //cntChars.c //John T. Rine //September 23, 2011 #include"set.h" int cntChars(char *inputString) { int count = 0; while(*(inputString + count) != '\0') ++count; return(count); } **int checkSetNotation(char *)**\\ checkSetNotation.c checks that the input string is in proper set notation, if it isn't, an error is returned.\\ //checkSetNotation.c //John T. Rine //October 15, 2011 #include"set.h" #include int checkSetNotation(char *inputString) { char oldChar = 'C'; int position = 0; int numberOfCharsInSet = 0; numberOfCharsInSet = cntChars(inputString); if(*(inputString + position) != '{') { printf("First character in a set representation must be a '{'\n"); return 0; } else if (*(inputString + numberOfCharsInSet - 1) != '}') { printf("Last character in a set representation must be a '}'\n"); return 0; } else if (*(inputString + numberOfCharsInSet - 2) == ',') { printf("Last two characters in a set representation can't be \",}\"\n"); return 0; } else if (*(inputString + 1) == ',') { printf("First two characters in a set representation can't be \"{,\"\n"); return 0; } while(*(inputString + position) != '\0') { if (*(inputString + position) == ',' && oldChar == ',') { printf("Can't have two adjacent commas in a set representation\n"); return 0; } oldChar = *(inputString + position); position ++; } return 1; } **int occurrences(char *, char)**\\ The function occurrences takes as function parameters a character and a character pointer (the base address of a character array, a string). occurences returns the number of times a particular character occurs in a string up to the maximum size of a integer.\\ Example code:\\ //occurrences.c //John T. Rine //September 23, 2011 #include "set.h" int occurrences(char *inputString, char c) { int i = 0; int r = 0; while (*(inputString + i) != '\0') { if(*(inputString + i) == c) r++; i++; } return r; } **void displaySet(set)**\\ displaySet.c takes the set set datatype which consists of a structure wrapping a pointer to a two dimensional array and an integer to store the number of elements in the set, and formats and prints it in proper set notation.\\ Example code:\\ //displaySet.c //John T. Rine //October 15, 2011 #define DEBUG #include"set.h" #include void displaySet(set inputSet) { int i; printf("{"); for(i = 0; i < inputSet.numberOfElements; i++) { printf("%s", inputSet.setPtr[i]); if(i != inputSet.numberOfElements - 1) printf(","); } printf("}\n"); #ifdef DEBUG if (strEqu(inputSet.setPtr[0], inputSet.setPtr[1])) printf("if DEBUG defined, then inputSet.setPtr[0] == inputSet.setPtr[1]\n"); else printf("if DEBUG defined, inputSet.setPtr[0] != inputSet.setPtr[1]\n"); #endif } **setTest.c**\\ setTest.c is the test file that utilizes the set library functions.\\ Example code:\\ //setTest.c //John T. Rine //October 16, 2011 #include #include #include"set.h" int main(int argc, char **argv) { set setData; int i; if (argc == 1) { printf("Should be at least one command line argument supplied after the file name\n"); exit(1); } else setData = parseSet(*(argv + 1)); displaySet(setData); for (i = 0; i < setData.numberOfElements; i++) free(setData.setPtr[i]); free(setData.setPtr); return 0; } **makeSetTest.bat**\\ The Windows batch file makeSetTest.bat automates, manufacture of all of the .o files, the creation of the static library file, compiling, linking, and execution of setTest, the test file.\\ Example code:\\ REM makeSetTest.bat REM John T. Rine REM October 16, 2011 del *.exe del *.o del *.a gcc -c displaySet.c -o displaySet.o gcc -c cntChars.c -o cntChars.o gcc -c checkSetNotation.c -o checkSetNotation.o gcc -c occurrences.c -o occurrences.o gcc -c parseSet.c -o parseSet.o gcc -c strEqu.c -o strEqu.o ar src libset.a *.o gcc -I. setTest.c -o setTest libset.a SET /P M=What program to run? setTest %M% pause **makeSetTest.sh**\\ The bash shell script file makeSetTest.sh automates the manufacture of all of the .o files, the creation of the static library file, compiling, linking and execution of setTest, the test file.\\ Example code:\\ #!/bin/bash gcc -c checkSetNotation.c -o checkSetNotation.o gcc -c cntChars.c -o cntChars.o gcc -c displaySet.c -o displaySet.o gcc -c occurrences.c -o occurrences.o gcc -c parseSet.c -o parseSet.o gcc -c strEqu.c -o strEqu.o ar scr libset.a *.o gcc -I. setTest.c -o setTest libset.a read input run="./setTest " concat="$run$input" $concat ======Execution====== The following setTest execution illustrates the capabilities of the checkSetNotation function.\\ This function checks for the following conditions: * beginning brace * ending brace * beginning brace and adjacent comma (error) * adjacent comma and ending brace (error) * adjacent commas (error) The function therefore will ignore spaces. It should treat them as though they are part of an element of a set.\\ c:\MinGW\jrprogs\set\setProject>setTest {A,B,C,D,E} {A,B,C,D,E} c:\MinGW\jrprogs\set\setProject>setTest A,B,C,D,E} First character in a set representation must be a '{' c:\MinGW\jrprogs\set\setProject>setTest {,B,C,D,E} First two characters in a set representation can't be "{," c:\MinGW\jrprogs\set\setProject>setTest {A,,C,D,E} Can't have two adjacent commas in a set representation c:\MinGW\jrprogs\set\setProject>setTest {A,B,,D,E} Can't have two adjacent commas in a set representation c:\MinGW\jrprogs\set\setProject>setTest {A,B,C,,E} Can't have two adjacent commas in a set representation c:\MinGW\jrprogs\set\setProject>setTest {A,B,C,D,} Last two characters in a set representation can't be ",}" c:\MinGW\jrprogs\set\setProject>setTest {A,B,C,D,E Last character in a set representation must be a '}' \\ Execution of makeSetTest.bat:\\ C:\Users\John\Desktop\setLibrary\setLibrary>REM makeSetTest.bat C:\Users\John\Desktop\setLibrary\setLibrary>REM John T. Rine C:\Users\John\Desktop\setLibrary\setLibrary>REM October 16, 2011 C:\Users\John\Desktop\setLibrary\setLibrary>del *.exe C:\Users\John\Desktop\setLibrary\setLibrary>del *.o C:\Users\John\Desktop\setLibrary\setLibrary>del *.a C:\Users\John\Desktop\setLibrary\setLibrary>gcc -c displaySet.c -o displaySet.o C:\Users\John\Desktop\setLibrary\setLibrary>gcc -c cntChars.c -o cntChars.o C:\Users\John\Desktop\setLibrary\setLibrary>gcc -c checkSetNotation.c -o checkSe tNotation.o C:\Users\John\Desktop\setLibrary\setLibrary>gcc -c occurrences.c -o occurrences. o C:\Users\John\Desktop\setLibrary\setLibrary>gcc -c parseSet.c -o parseSet.o C:\Users\John\Desktop\setLibrary\setLibrary>gcc -c strEqu.c -o strEqu.o C:\Users\John\Desktop\setLibrary\setLibrary>ar src libset.a *.o C:\Users\John\Desktop\setLibrary\setLibrary>gcc -I. setTest.c -o setTest libset. a C:\Users\John\Desktop\setLibrary\setLibrary>SET /P M=What program to run? What program to run?{dog,dog,cat,bird} C:\Users\John\Desktop\setLibrary\setLibrary>setTest {dog,dog,cat,bird} {dog,dog,cat,bird} if DEBUG defined, then inputSet.setPtr[0] == inputSet.setPtr[1] C:\Users\John\Desktop\setLibrary\setLibrary>pause Press any key to continue . . . \\ Execution of makeSetTest.sh:\\ lab46:~/src/setLibrary$ ./makeSetTest.sh {dog,dog,cat} {dog,dog,cat} if DEBUG defined, then inputSet.setPtr[0] == inputSet.setPtr[1] lab46:~/src/setLibrary$ \\ ======Reflection====== The purpose of the set library is to learn how to create a library composed of functions to create, compare, manipulate, and destroy sets.\\ The plan is to use the set library to create a Texas Hold'em computer game.\\ ======References====== * http://en.wikipedia.org/wiki/Discrete_mathematics * http://en.wikibooks.org/wiki/Discrete_Mathematics/Set_theory * http://en.wikibooks.org/wiki/Discrete_Mathematics/Set_theory/Exercises * http://www.doc.ic.ac.uk/~iccp/papers/discrete94.pdf * http://www.youtube.com/watch?v=9AUCdsmBGmA * http://www.cl.cam.ac.uk/~gw104/DiscMathRevised07.pdf * http://www.cs.odu.edu/~toida/nerzic/content/intro2discrete/intro2discrete.html \\