C++
f.a.qx8t
lab03.ziplab03/build.bat
@echo off cls set DRIVE_LETTER=%1: set PATH=%DRIVE_LETTER%\MinGW\bin;%DRIVE_LETTER%\MinGW\msys\1.0\bin;c:\Windows;c:\Windows\system32 g++ -c String.cpp g++ -c Tokens.cpp g++ -c ReadFile.cpp g++ -c WriteFile.cpp g++ -c Keyboard.cpp g++ -c Random.cpp g++ -c Matrix.cpp g++ -c Poly.cpp g++ -c CD.cpp g++ -c Song.cpp g++ -c Integer.cpp g++ -c Double.cpp g++ -c HighPerformanceCounter.cpp g++ -c Permutation.cpp ar -r libCSC2110.a *.o
lab03/fallout.txt
20 observation worshipping description nondescript eliminating survivalist destructive infestation surrounding persecution interesting explanation recognition programming personality hospitality distinguish devastation nightvision engineering
lab03/Lab03Files.zip
CD.cpp
#include "CD.h" #include "ListArrayIterator.h" #include "ReadFile.h" #include "Tokens.h" using namespace CSC2110; #include <iostream> using namespace std; char CD::getRadixChar(CD* cd, int index) //1-based { String* title = cd->getKey(); int title_len = title->length(); if (index <= title_len) { return title->charAt(index - 1); } else { return 32; //ascii for a space } } int CD::compare_items(CD* one, CD* two) { String* title_1 = one->getKey(); String* title_2 = two->getKey(); int title_compare = title_1->compare(title_2); //asc return title_compare; } int CD::compare_keys(String* sk, CD* cd) { String* title_1 = sk; String* title_2 = cd->getKey(); int title_compare = title_1->compare(title_2); //asc return title_compare; } CD::CD(String* artist, String* title, int year, int rating, int num_tracks) { this->artist = artist; this->title = title; this->year = year; this->rating = rating; this->num_tracks = num_tracks; songs = new ListArray<Song>(); } CD::~CD() { ListArrayIterator<Song>* iter = songs->iterator(); while(iter->hasNext()) { Song* song = iter->next(); delete song; } delete iter; delete songs; songs = NULL; delete artist; delete title; } String* CD::getKey() { return title; } void CD::addSong(String* title, String* length) { int track_count = songs->size(); if (track_count < num_tracks) { Song* song = new Song(title, length); songs->add(song); } } void CD::displayCD() { cout << "Artist: "; artist->displayString(); cout << endl; cout << "Title: "; title->displayString(); cout << endl; cout << "Year: " << year << endl; cout << "Rating: " << rating << endl; ListArrayIterator<Song>* iter = songs->iterator(); int count = 1; while(iter->hasNext()) { Song* song = iter->next(); cout << count << " "; song->displaySong(); count++; } delete iter; cout << endl; } ListArray<CD>* CD::readCDs(const char* file_name) { ReadFile* rf = new ReadFile(file_name); ListArray<CD>* cds = new ListArray<CD>(); String* artist = rf->readLine(); while(!rf->eof()) { String* title = rf->readLine(); String* year_str = rf->readLine(); int year = year_str->a_to_i(); delete year_str; String* rating_str = rf->readLine(); int rating = rating_str->a_to_i(); delete rating_str; String* tracks_str = rf->readLine(); int num_tracks = tracks_str->a_to_i(); delete tracks_str; CD* cd = new CD(artist, title, year, rating, num_tracks); cds->add(cd); int track_count = 0; while(track_count < num_tracks) { String* tok = rf->readLine(); Tokens* tokens = new Tokens(tok, ','); delete tok; String* song_length = tokens->getToken(0); String* song_title = tokens->getToken(1); cd->addSong(song_title, song_length); track_count++; delete tokens; } artist = rf->readLine(); } rf->close(); delete rf; return cds; }
CD.h
#if !defined CD_H #define CD_H #include "Song.h" #include "Text.h" using CSC2110::String; #include "ListArray.h" using CSC2110::ListArray; namespace CSC2110 { class CD { private: String* artist; String* title; int year; int rating; int num_tracks; ListArray<Song>* songs; public: CD(String* artist, String* title, int year, int rating, int num_tracks); virtual ~CD(); String* getKey(); void addSong(String* title, String* length); void displayCD(); static ListArray<CD>* readCDs(const char* file_name); static int compare_items(CD* one, CD* two); static int compare_keys(String* sk, CD* cd); static char getRadixChar(CD* cd, int index); //1-based }; } #endif
Double.cpp
#include "Double.h" using CSC2110::Double; Double::Double(double val) { value = val; } Double::~Double() { } double Double::getValue() { return value; }
Double.h
#if !defined (DOUBLE_H) #define DOUBLE_H namespace CSC2110 { class Double { private: double value; public: Double(double val); ~Double(); double getValue(); }; } #endif
HighPerformanceCounter.cpp
#include "HighPerformanceCounter.h" using CSC2110::HighPerformanceCounter; #include <cstdlib> #include <windows.h> HighPerformanceCounter* HighPerformanceCounter::hpc = new HighPerformanceCounter(); HighPerformanceCounter::HighPerformanceCounter() { LARGE_INTEGER ticksPerSecond; QueryPerformanceFrequency(&ticksPerSecond); int tps = ticksPerSecond.QuadPart; double spt = 1.0/tps; //seconds per tick micro_spt = spt/1.0E-6; //microseconds per tick } HighPerformanceCounter::~HighPerformanceCounter() {} HighPerformanceCounter* HighPerformanceCounter::getHighPerformanceCounter() { return hpc; } int HighPerformanceCounter::getCurrentTimeInTicks() { LARGE_INTEGER tick; LARGE_INTEGER ticksPerSecond; QueryPerformanceCounter(&tick); return tick.QuadPart; } double HighPerformanceCounter::getTimeDifferenceInMicroSeconds(int start_time, int end_time) { int diff = end_time - start_time; //total number of ticks double micro = diff * micro_spt; //corresponding time in microseconds return micro; }
HighPerformanceCounter.h
#if !defined (HIGHPERFORMANCECOUNTER_H) #define HIGHPERFORMANCECOUNTER_H namespace CSC2110 { class HighPerformanceCounter { private: double micro_spt; //micro_seconds per tick HighPerformanceCounter(); static HighPerformanceCounter* hpc; static int getTicksPerSecond(); public: virtual ~HighPerformanceCounter(); static HighPerformanceCounter* getHighPerformanceCounter(); int getCurrentTimeInTicks(); double getTimeDifferenceInMicroSeconds(int start_time, int end_time); }; } #endif
Integer.cpp
#include "Integer.h" using CSC2110::Integer; Integer::Integer(int val) { value = val; } Integer::~Integer() { } int Integer::getValue() { return value; }
Integer.h
#if !defined (INTEGER_H) #define INTEGER_H namespace CSC2110 { class Integer { private: int value; public: Integer(int val); virtual ~Integer(); int getValue(); }; } #endif
Keyboard.cpp
#include "Keyboard.h" using CSC2110::Keyboard; #include <iostream> Keyboard::Keyboard() { } Keyboard::~Keyboard() { } Keyboard* Keyboard::getKeyboard() { static Keyboard keyboard; //initialized when method is called the first time return &keyboard; //won't go out of scope as keyboard is static } int Keyboard::readInt(string prompt) { cout << prompt; int val = 0; cin >> val; return val; } int Keyboard::getValidatedInt(string prompt, int min, int max) { int validated = readInt(prompt); cout << validated << endl; while(validated < min || validated > max) { validated = readInt(prompt); cout << validated << endl; } return validated; } double Keyboard::readDouble(string prompt) { cout << prompt; double val = 0; cin >> val; return val; } double Keyboard::getValidatedDouble(string prompt, double min, double max) { double validated = readDouble(prompt); cout << validated << endl; while(validated < min || validated > max) { validated = readDouble(prompt); cout << validated << endl; } return validated; } String* Keyboard::readString(string prompt) { cout << prompt; string text; getline(cin, text); String* str = new String(text.c_str()); return str; }
Keyboard.h
#if !defined KEYBOARD_H #define KEYBOARD_H #include "Text.h" using CSC2110::String; #include <string> using namespace std; namespace CSC2110 { class Keyboard { private: Keyboard(); public: virtual ~Keyboard(); static Keyboard* getKeyboard(); //pre: the string (character literal) that will prompt the user for input //post: the input read from the keyboard interpreted as an int is returned int readInt(string prompt); int getValidatedInt(string prompt, int min, int max); //pre: the string that will prompt the user for input //post: the input read from the keyboard interpreted as a double is returned double readDouble(string prompt); double getValidatedDouble(string prompt, double min, double max); //pre: the string that will prompt the user for input // the string to store the user input and the length of the input storage string //post: the text read from the keyboard is copied into the storage string String* readString(string prompt); }; } #endif
ListArray.h
#if !defined (LISTARRAY_H) #define LISTARRAY_H #include "ListArrayIterator.h" namespace CSC2110 { template < class T > class ListArray { private: int max_size; T** items; int sz; void arrayResize(int new_max_size); public: ListArray(); ~ListArray(); bool isEmpty(); int size(); void removeAll(); T* get(int index); void add(int index, T* item); void add(T* item); void remove(int index); void set(int index, T* item); ListArrayIterator<T>* iterator(); T** toArray(); }; template < class T > ListArray<T>::ListArray() { max_size = 10; items = new T*[max_size]; sz = 0; } template < class T > ListArray<T>::~ListArray() { delete[] items; //the items themselves are not deleted } template < class T > bool ListArray<T>::isEmpty() { return (sz == 0); } template < class T > int ListArray<T>::size() { return sz; } template < class T > //1-based T* ListArray<T>::get(int index) { T* item = NULL; if (index >= 1 && index <= sz) { item = items[index - 1]; } return item; } template < class T > void ListArray<T>::add(T* item) { add(sz + 1, item); //add the item to the end of the array list } template < class T > void ListArray<T>::add(int index, T* item) { if (index < 1 || index > sz + 1) { return; } //need more room in the array list if (sz == max_size) { arrayResize(2*max_size); } for (int i = sz; i >= index; i--) { items[i] = items[i - 1]; } items[index - 1] = item; sz++; } template < class T > void ListArray<T>::remove(int index) { if (index < 1 || index > sz) { return; } for (int i = index; i < sz; i++) { items[i - 1] = items[i]; } items[sz - 1] = NULL; sz--; /* if (sz < max_size/2 - 1) //halve the size of the array, smallest size of max_size should be 2 { arrayResize(max_size/2); } */ } template < class T > ListArrayIterator<T>* ListArray<T>::iterator() { ListArrayIterator<T>* iter = new ListArrayIterator<T>(items, sz); return iter; } template < class T > void ListArray<T>::set(int index, T* item) { //could use other methods already written, but this is more efficient if (index >= 1 && index <= sz) { items[index - 1] = item; //overwrite contents at that location } } template < class T > void ListArray<T>::arrayResize(int new_max_size) { max_size = new_max_size; T** temp = new T*[max_size]; for (int i = 0; i < sz; i++) { temp[i] = items[i]; } delete[] items; items = temp; } template < class T > void ListArray<T>::removeAll() { delete[] items; max_size = 10; items = new T*[max_size]; sz = 0; } template < class T > T** ListArray<T>::toArray() { int num_items = size(); T** to_array = new T*[num_items]; for (int i = 0; i < num_items; i++) { to_array[i] = items[i]; } return to_array; } } #endif
ListArrayIterator.h
#if !defined (NULL) #define NULL 0 #endif #if !defined (LISTARRAYITERATOR_H) #define LISTARRAYITERATOR_H namespace CSC2110 { template < class T > class ListArrayIterator { private: int index; int sz; T** items; public: ListArrayIterator(T** items, int size); ~ListArrayIterator(); bool hasNext(); T* next(); }; template < class T > ListArrayIterator<T>::ListArrayIterator(T** itms, int size) { items = new T*[size]; for (int i = 0; i < size; i++) { items[i] = itms[i]; //snapshot of the data } index = 1; sz = size; } template < class T > ListArrayIterator<T>::~ListArrayIterator() { delete[] items; } template < class T > bool ListArrayIterator<T>::hasNext() { return (index <= sz); } template < class T > T* ListArrayIterator<T>::next() { T* item = NULL; if (hasNext()) { item = items[index - 1]; index++; } return item; } } #endif
Matrix.cpp
#include "Matrix.h" using CSC2110::Matrix; #include <fstream> #include <iostream> using namespace std; int Matrix::getNumRows() { return rows; } int Matrix::getNumCols() { return cols; } //the indices are 1-based!! Matrix::Matrix(int r, int c) { rows = r; cols = c; if (r < 1) { rows = 1; } if (c < 1) { cols = 1; } int num_elements = rows*cols; mat = new double[rows*cols]; //initialize the matrix to contain all zeroes (might not be square in general) int count = 0; for (int i = 1; i <= rows; i++) { for (int j = 1; j <= cols; j++) { mat[count] = 0.0; count++; } } } Matrix::~Matrix() { delete[] mat; } void Matrix::setElement(int row, int col, double val) { int index = (row - 1) * cols + col - 1; mat[index] = val; } double Matrix::getElement(int row, int col) { int index = (row - 1) * cols + col - 1; return mat[index]; } void Matrix::displayMatrix() { for (int i = 1; i <= rows; i++) { for (int j = 1; j <= cols; j++) { cout << this->getElement(i, j) << " "; } cout << endl; } cout << endl; } Matrix* Matrix::add(Matrix* other) { int rows1 = rows; int cols1 = cols; int rows2 = other->rows; //getNumRows() int cols2 = other->cols; //getNumCols() if (cols1 != rows1 || cols2 != rows2) { cout << "Cannot add matrices." << endl; return NULL; } Matrix* result = new Matrix(rows1, cols1); int rows = rows1; int cols = cols1; //loop over all elements of resulting matrix for (int i = 1; i <= rows; i++) { for (int j = 1; j <= cols; j++) { double x = this->getElement(i, j) + other->getElement(i, j); result->setElement(i, j, x); } } return result; } Matrix* Matrix::multiply(Matrix* other) { int rows1 = rows; int cols1 = cols; int rows2 = other->rows; int cols2 = other->cols; if (cols1 != rows2) { cout << "Cannot multiply matrices." << endl; return NULL; } Matrix* result = new Matrix(rows1, cols2); int rows = rows1; int cols = cols2; double x; //loop over all elements of resulting matrix for (int i = 1; i <= rows; i++) { for (int j = 1; j <= cols; j++) { x = 0; //sum up multiplying matrices to obtain value placed in new matrix for (int k = 1; k <= cols1; k++) { x = x + this->getElement(i, k) * other->getElement(k, j); } result->setElement(i, j, x); } } return result; } //assumes a specific format for the file Matrix* Matrix::readMatrix(const char* file_name) { ifstream matrix_file; matrix_file.open(file_name); int rows = 1; int cols = 1; matrix_file >> rows >> cols; if (rows < 1) { rows = 1; } if (cols < 1) { cols = 1; } Matrix* matrix = new Matrix(rows, cols); for (int i = 1; i <= rows; i++) { for (int j = 1; j <= cols; j++) { double val = 0.0; matrix_file >> val; matrix->setElement(i, j, val); } } matrix_file.close(); return matrix; } //assumes a specific format for the file void Matrix::writeMatrix(const char* file_name) { ofstream matrix_file; matrix_file.open(file_name); matrix_file << rows << " " << cols << endl; for (int i = 1; i <= rows; i++) { for (int j = 1; j <= cols; j++) { matrix_file << this->getElement(i, j) << " "; } matrix_file << endl; } matrix_file.close(); }
Matrix.h
#if !defined MATRIX_H #define MATRIX_H //the indices are 1-based!! namespace CSC2110 { class Matrix { private: int rows; int cols; double* mat; public: Matrix(int rows, int cols); //constructor ~Matrix(); //destructor void displayMatrix(); int getNumRows(); int getNumCols(); double getElement(int row, int col); void setElement(int row, int col, double val); Matrix* add(Matrix* other); Matrix* multiply(Matrix* other); static Matrix* readMatrix(const char* file_name); //discuss static void writeMatrix(const char* file_name); }; } #endif
Permutation.cpp
#include "Permutation.h" using CSC2110::Permutation; #include "ListArrayIterator.h" using CSC2110::ListArrayIterator; Permutation::Permutation(int q, int n) { random = Random::getRandom(); r = q; numbers = new ListArray<Integer>(); for (int i = 1; i <= n; i++) { Integer* num = new Integer(i); numbers->add(num); } } Permutation::~Permutation() { ListArrayIterator<Integer>* iter = numbers->iterator(); while(iter->hasNext()) { Integer* i = iter->next(); delete i; } delete iter; delete numbers; } int Permutation::next() { if (r == 0) return -1; int rand = random->getRandomInt(1, numbers->size()); Integer* num = numbers->get(rand); int value = num->getValue(); numbers->remove(rand); delete num; r--; return value; }
Permutation.h
#if !defined (PERMUTATION_H) #define PERMUTATION_H #include "ListArray.h" using CSC2110::ListArray; #include "Integer.h" using CSC2110::Integer; #include "Random.h" using CSC2110::Random; namespace CSC2110 { class Permutation { private: int r; ListArray<Integer>* numbers; Random* random; public: Permutation(int r, int n); virtual ~Permutation(); int next(); }; } #endif
Poly.cpp
#include "Poly.h" #include "ReadFile.h" #include "WriteFile.h" #include "ListArray.h" #include <math.h> #include <stdlib.h> #include <iostream> using namespace std; using namespace CSC2110; Poly::Poly(int m_p) { max_power = 3; if (m_p >= 0) { max_power = m_p; } coeffs = new double[max_power + 1]; //array of doubles for (int i = 0; i <= max_power; i++) { coeffs[i] = 0.0; } degree = 0; max_power = max_power; } Poly::~Poly() { delete[] coeffs; } int Poly::getDegree() { return degree; } double Poly::getCoeff(int power) { if (power > max_power || power < 0) return 0; return coeffs[power]; } void Poly::setCoeff(int power, double cf) { if (power > max_power || power < 0) return; coeffs[power] = cf; if (power >= degree) { degree = power; } } double Poly::evaluate(double x) { double result = getCoeff(degree); for (int i = degree - 1; i >= 0; i--) { result = result * x; result = result + getCoeff(i); } return result; } Poly* Poly::multiply(Poly* other) { double TOL = .00001; int n = getDegree(); int m = other->getDegree(); Poly* temp = new Poly(n + m); for (int i = 0; i <= n; i++) //loop over coeffs { for (int j = 0; j <= m; j++) //loop over second coeffs { double coeff_i = getCoeff(i); double coeff_j = other->getCoeff(j); if (fabs(coeff_i) > TOL && fabs(coeff_j) > TOL) { int power = i + j; double coeff = temp->getCoeff(power); temp->setCoeff(power, coeff + (coeff_i * coeff_j)); } } } return temp; } void Poly::displayPoly() { double TOL = .00001; int degree = getDegree(); cout << getCoeff(degree) << "x^" << degree; for (int i = degree - 1; i >= 0; i--) { double coeff = getCoeff(i); if (fabs(coeff) > TOL) { cout << " + " << coeff << "x^" << i << " "; } } cout << endl; } //assumes a specific format for the file //why is this method static in the header file? Poly* Poly::readPoly(const char* file_name) { ReadFile* rf = new ReadFile(file_name); //for reading String* degree_str = rf->readLine(); int degree = degree_str->a_to_i(); delete degree_str; Poly* poly = new Poly(degree); for (int i = 0; i <= degree; i++) { String* coeff_str = rf->readLine(); float coeff = coeff_str->a_to_f(); delete coeff_str; poly->setCoeff(i, (double) coeff); } delete rf; return poly; } //assumes a specific format for the file void Poly::writePoly(const char* file_name) { WriteFile wf(file_name); //for writing String* degree_str = String::f_to_a(degree); wf.writeLine(degree_str); delete degree_str; for (int i = 0; i <= degree; i++) { float coeff = (float) getCoeff(i); String* coeff_str = String::f_to_a(coeff); wf.writeLine(coeff_str); delete coeff_str; } }
Poly.h
#if !defined (POLY) #define POLY namespace CSC2110 { class Poly { private: int max_power; int degree; double* coeffs; public: Poly(int max_power); ~Poly(); int getDegree(); double getCoeff(int power); void setCoeff(int power, double coeff); double evaluate(double x); Poly* multiply(Poly* other); static Poly* multiply(Poly* one, Poly* two); void displayPoly(); static Poly* readPoly(const char* file_name); void writePoly(const char* file_name); }; } #endif
Random.cpp
#include "Random.h" using CSC2110::Random; #include <time.h> #include <stdlib.h> Random::Random() { randomInit(); } Random::~Random() { } Random* Random::getRandom() { static Random random; //initialized when method is called the first time return &random; } void Random::randomInit() { srand (time(NULL)); //try to get a more random starting number rand(); rand(); rand(); rand(); } int Random::getRandomInt(int lower, int upper) { int diff = upper - lower + 1; int random_num = rand()%diff; random_num = random_num + lower; //gives a number between lower and upper, inclusive return random_num; } float Random::getRandomFloat(float lower, float upper) { float r_float_1 = (float) rand(); float r_float_2 = (float) RAND_MAX; float random_normalized = r_float_1/r_float_2; //between 0.0 and 1.0 float random_float = lower + random_normalized*(upper - lower); return random_float; }
Random.h
#if !defined RANDOM_H #define RANDOM_H namespace CSC2110 { class Random { private: Random(); void randomInit(); public: virtual ~Random(); static Random* getRandom(); int getRandomInt(int lower, int upper); float getRandomFloat(float lower, float upper); }; } #endif
ReadFile.cpp
#include "ReadFile.h" #include <iostream> #include <string> ReadFile::ReadFile(const char* file_name) { input_file = new std::ifstream(); input_file->open(file_name); closed = false; _eof = false; } ReadFile::~ReadFile() { close(); delete input_file; } bool ReadFile::eof() { return _eof; } void ReadFile::close() { if (!closed) { input_file->close(); closed = true; } } String* ReadFile::readLine() { if (closed) return NULL; if (_eof) return NULL; std::string text; _eof = !(getline(*input_file, text)); String* str = new String((const char*) text.c_str()); return str; }
ReadFile.h
#if !defined READ_FILE_H #define READ_FILE_H #include "Text.h" using CSC2110::String; #include <fstream> class ReadFile { private: std::ifstream* input_file; bool _eof; bool closed; public: ReadFile(const char* file_name); ~ReadFile(); String* readLine(); bool eof(); void close(); }; #endif
Song.cpp
#include "Song.h" using CSC2110::Song; #include <iostream> using namespace std; Song::Song(String* title, String* length) { this->title = title; this->length = length; } Song::~Song() { delete title; delete length; } void Song::displaySong() { title->displayString(); cout << " "; length->displayString(); cout << endl; }
Song.h
#if !defined SONG_H #define SONG_H #include "Text.h" using CSC2110::String; namespace CSC2110 { class Song { private: String* title; String* length; public: Song(String* title, String* length); virtual ~Song(); void displaySong(); }; } #endif
String.cpp
#include "Text.h" using CSC2110::String; #include <stdlib.h> //needed for atoi and atof #include <cstring> //needed for strlen and strcmp #include <sstream> #include <iostream> using namespace std; String::String(const char* char_array) { sz = strlen(char_array); char* text = new char[sz+1]; for (int i = 0; i < sz; i++) { text[i] = char_array[i]; } text[sz] = 0; //null terminator this->text = text; } String::~String() { delete[] text; } //zero-based char String::charAt(int index) { if (index < 0 || index >= sz) return -1; return text[index]; } const char* String::getText() { return text; } int String::length() { return sz; } int String::compare(String* other) { return strcmp(text, other->text); } void String::displayString() { cout << text; } int String::find(char delimiter, int start) { if (start >= sz || start < 0) return -1; int loc = sz; for (int i = start; i < sz; i++) { if (text[i] == delimiter) { loc = i; break; } } return loc; //delimiter not found } //the substring will use the characters from start to end inclusive String* String::substr(int start, int end) { if (start > end || start < 0) return NULL; if (start > sz || end > sz) return NULL; int sub_len = end - start + 1; char* sub_text = new char[sub_len + 1]; int count = 0; for (int i = start; i <= end; i++) { sub_text[count] = text[i]; count++; } sub_text[count] = 0; String* sub = new String((const char*) sub_text); return sub; } int String::a_to_i() { return atoi(text); } float String::a_to_f() { return atof(text); } String* String::i_to_a(int number) { stringstream out; out << number; const char* text = out.str().c_str(); return new String(text); } String* String::f_to_a(float number) { stringstream out; out << number; const char* text = out.str().c_str(); return new String(text); }
Text.h
#if !defined STRING_H #define STRING_H namespace CSC2110 { class String { private: const char* text; int sz; //length of string not including null terminator public: String(const char* char_array); virtual ~String(); void displayString(); int length(); const char* getText(); //add this member function char charAt(int index); int a_to_i(); float a_to_f(); static String* i_to_a(int number); static String* f_to_a(float number); //find the location of a particular character in a String and return the index if found //preconditions: // str is the String being examined for the character delimiter (str must point to a valid String) // delimiter is the character being searched for // start is the index to start the search at (the first index of the String is 0, start cannot exceed the length of the String) //postconditions: // if the preconditions are met, the index of the first delimiter encountered at or after the start index is returned // if the delimiter is not present in the String at index start or later, -1 is returned // if the preconditions are not met, no guarantees on output are made int find(char delimiter, int start); //creates a new String that is extracted from an existing String with characters specified by the start and end indices //preconditions: // str is the String from which the substring will be extracted (str must point to a valid String) // start and end are the indices used to create the substring // start must be less than or equal to end, start must be >= 0, end must be >= 0, end < the length of the String //postconditions: // if the preconditions are met, the String extracted from the parameter String // that starts at index start and ends at index end is created and returned // the original string is unaffected String* substr(int start, int end); //need to document that this compare only has three possible return values (-1, 0, 1) int compare(String* other); }; } #endif
Tokens.cpp
#include "Tokens.h" #if !defined NULL #define NULL 0 #endif #include <iostream> using namespace std; using namespace CSC2110; Tokens::Tokens(String* str, char delimiter) { max_tokens = 1; sz = 0; tokens = new String*[max_tokens]; for (int i = 0; i < max_tokens; i++) { tokens[i] = NULL; } int str_len = str->length(); int current_loc = 0; int count = 0; while(current_loc < str_len) { int next_loc = str->find(delimiter, current_loc); if (next_loc > 0) //a delimiter as the first character is a problem { String* token = str->substr(current_loc, next_loc - 1); addToken(token); count++; } current_loc = next_loc + 1; } } Tokens::~Tokens() { delete[] tokens; } int Tokens::getNumTokens() { return sz; } void Tokens::displayTokens() { int num_tokens = sz; String** strings = tokens; for (int i = 0; i < num_tokens; i++) { String* str = strings[i]; str->displayString(); cout << endl; } } void Tokens::resize() { String** resize_strings = new String*[2*max_tokens]; for (int i = 0; i < sz; i++) { resize_strings[i] = tokens[i]; } for (int i = sz; i < 2*sz; i++) { resize_strings[i] = NULL; } delete[] tokens; tokens = resize_strings; max_tokens = 2*max_tokens; } void Tokens::addToken(String* str) { if (sz == max_tokens) { resize(); } tokens[sz] = str; sz++; } String* Tokens::getToken(int index) { if (index < 0 && index >= sz) return NULL; return tokens[index]; }
Tokens.h
#if !defined TOKENS_H #define TOKENS_H #include "Text.h" using CSC2110::String; namespace CSC2110 { class Tokens { private: String** tokens; int max_tokens; int sz; void addToken(String* str); //requires a resizing check void resize(); public: Tokens(String* str, char delimiter); ~Tokens(); //Tokens is not responsible for deleting each token void displayTokens(); String* getToken(int index); //returns a specifically requested token int getNumTokens(); }; } #endif
WriteFile.cpp
#include "WriteFile.h" #include <sstream> WriteFile::WriteFile(const char* file_name) { output_file = new ofstream(); output_file->open(file_name); closed = false; } WriteFile::~WriteFile() { close(); delete output_file; } void WriteFile::close() { if (!closed) { output_file->close(); closed = true; } } void WriteFile::writeLine(String* line) { if (!closed && line->length() > 0) { *output_file << line->getText() << endl; } }
WriteFile.h
#if !defined WRITE_FILE #define WRITE_FILE #include "Text.h" using CSC2110::String; #include <fstream> using namespace std; class WriteFile { private: ofstream* output_file; bool closed; public: WriteFile(const char* file_name); ~WriteFile(); void writeLine(CSC2110::String* line); void close(); }; #endif
lab03/Password.cpp
#include "Password.h" using CSC2110::ListArrayIterator; #include <iostream> using namespace std; int Password::bestGuess() { int best_guess_index = -1; int best_num_eliminated = -1; int num_viable_passwords = getNumberOfPasswordsLeft(); //loop over ALL words, even if they have been eliminated as the password int count = 1; ListArrayIterator<String>* all_iter = all_words->iterator(); while(all_iter->hasNext()) { String* original_word = all_iter->next(); //loop over only those words that could still be the password //count up the number of matches between a possible password and a word in the original list int* count_num_matches = new int[len + 1]; for (int i = 0; i < len; i++) { count_num_matches[i] = 0; } ListArrayIterator<String>* viable_iter = viable_words->iterator(); while(viable_iter->hasNext()) { String* viable_word = viable_iter->next(); int num_matches = getNumMatches(viable_word, original_word); count_num_matches[num_matches]++; } delete viable_iter; //find the largest number in the count_num_matches array //the largest number indicates the guess that will generate the most eliminations int most_num_matches = 0; for (int j = 0; j < len; j++) { int curr_num_matches = count_num_matches[j]; if (curr_num_matches > most_num_matches) { most_num_matches = curr_num_matches; } } //compute the fewest that can possibly be eliminated by guessing the current word (original list) int num_eliminated = num_viable_passwords - most_num_matches; //select the word to guess that maximizes the minimum number of eliminations (minimax) if (num_eliminated > best_num_eliminated) { best_num_eliminated = num_eliminated; best_guess_index = count; } count++; delete[] count_num_matches; } delete all_iter; return best_guess_index; //return a 1-based index into the all_words list of words (careful) }
lab03/Password.h
#if !defined PASSWORD_H #define PASSWORD_H //complete the includes class Password { private: ListArray<String>* viable_words; //the list of words that can still be the password ListArray<String>* all_words; //the original list of words int len; //the length of the first word entered is stored to check that all subsequent words have the same length //a private helper method to report the number of character matches between two Strings int getNumMatches(String* curr_word, String* word_guess); public: }; #endif
lab03/PasswordDriver.cpp
#include "Password.h" //fill in includes, don't forget namespaces #include <iostream> using namespace std; void addWords(Password* fh) { Keyboard* kb = Keyboard::getKeyboard(); String* file_str = kb->readString("Enter the file name containing the possible passwords: "); ReadFile* rf = new ReadFile(file_str->getText()); delete file_str; String* num_words_str = rf->readLine(); int num_words = num_words_str->a_to_i(); delete num_words_str; for (int i = 0; i < num_words; i++) { String* word = rf->readLine(); fh->addWord(word); } delete rf; fh->displayViableWords(); } void guessWords(Password* fh) { Keyboard* kb = Keyboard::getKeyboard(); int numLeft = fh->getNumberOfPasswordsLeft(); while (numLeft > 1) //terminate if the password has been identified, or there is no valid password (user entry error) { int best_guess_index = fh->bestGuess(); String* best_guess_word = fh->getOriginalWord(best_guess_index); cout << "You should guess \""; best_guess_word->displayString(); cout << "\" at index " << best_guess_index; cout << endl << endl; String* guess_str = kb->readString("Index of word in the original word list to guess (1-based): "); int guess = guess_str->a_to_i(); delete guess_str; String* match_str = kb->readString("Number of character matches: "); int match = match_str->a_to_i(); delete match_str; cout << endl; fh->guess(guess, match); //1-based index of the guessed word and the number of character matches fh->displayViableWords(); numLeft = fh->getNumberOfPasswordsLeft(); } } int main() { Password* fallout = new Password(); addWords(fallout); guessWords(fallout); delete fallout; }
