// APS105 Lab6 11/05/06
// Geoffrey Lang
// 995155772
// langgeof@ecf.utoronto.ca
#include <iostream>
#include <fstream>
using namespace std;
const int MAX_WORDS = 10000;
const int MAX_WORD_LENGTH = 25;
const int WORD_NOT_FOUND = -1;
bool goodLetter(char a);
void printArray(char words[][MAX_WORD_LENGTH], int n);
void selectionSort(char words[][MAX_WORD_LENGTH], int n);
void deleteDuplicates(char words[][MAX_WORD_LENGTH], int& n);
int binarySearch(char words[][MAX_WORD_LENGTH], int n, char key[]);
int main (int argc, char *argv[])
{
char current, currentkey;
int i = 0, j = 0, k = 0, totalwords = 0, uniquewords = 0, foundloc;
bool twolines = 0, keydone = 0, exit = 0;
char words[MAX_WORDS][MAX_WORD_LENGTH];
char key[MAX_WORD_LENGTH];
ifstream in_stream; // Opens the file written after the
in_stream.open(argv[1]); // name of this program when it is run
while(!in_stream.eof())
{
in_stream.get(current);
current = tolower(current);
if((current == ' ' || current == '\n') && twolines == 1)// Move to next line if there is
{ // a space in the input
while(!goodLetter(words[i][strlen(words[i])-1]))
{
words[i][strlen(words[i])-1] = '\0';
}
i++;
j = 0;
twolines = 0;
}
if(j == 0 && goodLetter(current) || j != 0) // Check that the first letter isn't punctuation
{ // before putting the word into the array and
words[i][j] = current; // if its not the first letter, put it in anyway
j++;
twolines = 1;
}
}
selectionSort(words,i); // Apply selection sort to the array
// and then print it (for testing
totalwords = i; // purposes only)
deleteDuplicates(words,i); // Delete the duplicates in the array
uniquewords = i; // and print it to check that they are
printArray(words,i); // all deleted
cout << "Total words: " << totalwords << ".\n";
cout << "Unique words: " << uniquewords << ".\n";
while(exit == 0) // Continues to ask the user for a
{ // Key to search the words array for.
cout << "\nEnter a word to search for: "; // If the first non-punctuation
// character is a number, the program
while(keydone == 0) // will quit, also deletes punctuation
{ // leading or following the search key
cin.get(currentkey);
currentkey = tolower(currentkey);
if(currentkey == ' ' || currentkey == '\n')
{
while(!goodLetter(key[strlen(key)])-1)
{
key[strlen(key)] = '\0';
}
keydone = 1;
k = 0;
}
if (k == 0 && goodLetter(currentkey) || k != 0)
{
key[k] = currentkey;
k++;
}
}
keydone = 0;
if (key[0] >= '0' && key[0] <= '9')
{
exit = 1;
cout << "... Quitting ...\n";
}
else
{
cout << "... Searching ...\n";
foundloc = binarySearch(words, i, key);
if(foundloc >= 0)
{
cout << "\"" << key << "\" FOUND at location: " << foundloc << ".\n";
}
else
{
cout << "\"" << key << "\" NOT FOUND.\n";
}
}
for (int t = 0; t <= MAX_WORD_LENGTH; t++) // Clears the key array after the
{ // search is complete
key[t] = '\0';
}
}
return 0;
}
bool goodLetter(char a) // Function to check if a character is
{ // a character that can start or end
if((a >= 'a' && a <= 'z') || (a >= '0' && a <= '9')) // a word--must be a letter or a
{ // number. Returns 1 if the character
return 1; // is a letter or number, 0 if not
}
else
{
return 0;
}
}
void printArray(char words[][MAX_WORD_LENGTH], int n) // Function to print an array, one
{ // word per line
for(int x = 0; x < n; x++)
{
for (int y = 0; words[x][y] != '\0'; y++)
{
cout << words[x][y];
}
cout << endl;
}
return;
}
void selectionSort(char words[][MAX_WORD_LENGTH], int n) // Function to sort an array of
{ // c-strings in alphabetical
for(int i = 0; i < n - 1; i++) // order
{
int smallest = i;
for(int j = i + 1; j < n; j++)
{
if(strncmp(words[j],words[smallest],MAX_WORD_LENGTH) < 0)
{
smallest = j;
}
}
char temp[1][MAX_WORD_LENGTH];
strncpy(temp[0],words[i],MAX_WORD_LENGTH);
strncpy(words[i],words[smallest],MAX_WORD_LENGTH);
strncpy(words[smallest],temp[0],MAX_WORD_LENGTH);
}
return;
}
void deleteDuplicates(char words[][MAX_WORD_LENGTH], int& n) // Function to delete all duplicate
{ // enteries in an array of sorted
int i = 0, j = 0, k = 0; // c-strings
while(i < n - 1)
{
while (strncmp(words[i-j],words[i+1],MAX_WORD_LENGTH) == 0)
{
j++;
i++;
}
if (j > 0)
{
strncpy(words[i-j+1],words[i+1],MAX_WORD_LENGTH);
j--;
}
else
{
i++;
}
k++;
}
n = k;
return;
}
int binarySearch(char words[][MAX_WORD_LENGTH], int n, char key[]) // Function to search the words array
// for the key array and return the
{ // index of the words array that the
int left = 0, right = n - 1, middle, result; // that the key is in
while(left < right)
{
middle = (left + right)/2;
if(strncmp(key,words[middle],MAX_WORD_LENGTH) > 0)
{
left = middle + 1;
}
else
{
right = middle;
}
}
if(strncmp(key,words[left],MAX_WORD_LENGTH) == 0)
{
result = left;
}
else
{
result = WORD_NOT_FOUND;
}
return result;
}