Assignment 1

Code only ExpandableArray.cpp and BearHelper.cpp

In this assignment you will make an improved AlphaBear helper as follows:

• Instead of reading the dictionary into an array of strings, you will read the entire file into a single string. Note that the words will be separated by newline characters. You will replace the newline characters with null characters. This will make it easier to use c-string functions like strlen, strcpy..etc. All you would need to do is pass a pointer to the first character in a word and the function will treat it like a string terminated by the null character.
• Instead of deleting the words that will not work, we will create an ExpandableArray that will store pointers to the words that work. This way, I can preserve the dictionary for further queries (without having to re-read the dictionary for each query) and the array of pointers can be easily sorted in any way we like.

Code Format:

• main.cpp - main function to run your program.
• ExpandableArray.h This is a class similar to Java's ArrayList to store the pointers to the words in the result.
• ExpandableArray.cpp This file implements all the methods of ExpandableArray.h. You will need to implement those methods.
• BearHelper.h - Header file with function prototypes.
• BearHelper.cpp - Your code goes in this file. Follow the instructions in the file.

The Program:

The program (main) creates a BearHelper object using the dictionary file and then repeatedly asks user for required and available letters and then prints the answers in order of length (longest word first).

Classes and methods to Implement:

The following classes functions should be implemented by the student.

• Class ExpandableArray: This class is an array that changes size like ArrayList in Java. Every time the array fills up, it doubles in size. The array will store pointers to char* (strings). The following methods need to be implemented
  • Default constructor: Default size can be 16.
  • Constructor that takes an initial size
  • Destructor: Destroy the array allocated
  • Append: Add the element to the end of the array.
  • Sort: Sort the pointers in the array by string length from longest to shortest.
  • Length: Returns the length of the array right now (this is not the maximum size but rather the number of elements in the array at the moment).
  • get: Returns the char* at index i
  • ExpandArray: doubles the size of the array.
• Class BearHelper: This is a modified class as follows:
  • Constructor: In the constructor you will read the entire file into a single string and then replace the newline characters with null characters.
  • Destructor: Destroy the string that stores the dictionary.

  • GetAllWords: prints all words that work for the required and available sets in order of length (longest to shortest). detailed instructions are in the BearHelper.cpp file.

Starter Code:

ExpandableArray.h:

class ExpandableArray

{

public:

//Constructs theArray with an initial size of 16.

ExpandableArray();

//Constructs the array with the specified initial size

ExpandableArray(int initialSize);

// Free the memory allocated for theArray

~ExpandableArray();

//Append an element to the end of theArray as follows:

//a) If there is space in the array, add in location of next free element and return.

//b) If not, then expand the array.

//c) Add the element at the end

void Append(char* element);

//Sort the pointers to words in order of length from longest to shortest. Hint: You can determine the words length using strlen

void Sort();

//Returns the number of elements in the array right now.

int length();

//Return the element at index i in the array

char* get(int i);

private:

//This array contains pointers to c-strings.

//Note that this an array of pointers to characters such that each pointer points to the first character of a word. The words will be stored in a single string in BearHelper.

char** theArray;

//This is the size of the expandableArray. When the currentIndex reaches the maxSize then the array needs to expand

int maxSize;

//The currentIndex is an index to the next open spot in the array. Therefore currentIndex tells you the number of elements in the array

int currentIndex;

//A private method that expands the array. The array doubles in size when it fills up. Expand as follows:

//a) make new array that is twice the size of the old one.

//b) Copy the old array into the new array.

//c) Destroy the old

void ExpandArray();

};

BearHelper.cpp

#include

#include

#include

#include

#include

#include

#include

#include "BearHelper.h"

#include "ExpandableArray.h"

//This method constructs BearHelper object by reading the file f into the dictionary string

BearHelper::BearHelper(const char *f)

{

//Open the file for reading

//Determine the number of characters in file. Hint: you can use fseek and ftell.

//Allocate a string large enough for the entire dictionary.

//Read the entire file into the string allocated

//Replace every character with a null character.

}

//Destructor for the BearHelper to free the memory used by dictionary

BearHelper::~BearHelper()

{

//Destroy any memory allocated on heap and set pointer to null

}

/*

* Returns true if all letters in "letters" are in group of letters "group" (duplicates should be accounted for)

* therefore the letters: "ee" are in group "tree" but not in group "tea"

*

* parameter: letters - list of letters, group - a collection of letter

* return: true of all letters are in set

*/

bool BearHelper::AllLettersInSet(const char *letters, const char *set)

{

int l[26];

int s[26];

for (int x = 0; x < 26; x++)

l[x] = s[x] = 0;

for (const char *t = letters; *t; t++)

{

l[tolower(*t)-97]++;

}

for (const char *t = set; *t; t++)

{

s[tolower(*t)-97]++;

}

for (int x = 0; x < 26; x++)

if (l[x] > s[x])

return false;

return true;

}

//Print all words that satisfy the condition: All characters in required must be in word and all letters in word must be in available

//The words are printed in order of length from longest to shortest.

void BearHelper::GetAllWords(const char* required, const char* available)

{

//Go in order through the dictionary.

//Check if each word matches.

//If it does, add it to the expandable set.

//Sort the expandable set.

//Print the expandable set.

}

Main

#include

#include

#include

#include

#include

#include

#include

#include "BearHelper.h"

int main(int argc, char **argv)

{

std::string required, available;

const char *file = "Dictionary.txt";

BearHelper bh(file);

while (true)

{

std::cout << "Enter required letters: ";

std::cin >> required;

std::cout << "Enter available letters: ";

std::cin >> available;

bh.GetAllWords(required.c_str(), available.c_str());

}

return 0;

}