A3/OutputProcessor.cpp
2024-10-10 21:12:43 -06:00

344 lines
No EOL
12 KiB
C++

/**
* @author Tyler Beckman (tyler_beckman@mines.edu)
* @brief A3 - A program to parse a text input and analyze it for statistics based on
* word and letter frequency, and then output them to a user-specified file. It
* assumes text is only alphabetical + spaces + the punctuation contained within
* main.cpp. In addition, the list of word counts is sorted using a recursive
* MSD radix sort before being outputted into the specified file.
* @version 1
* @date 2024-10-10
*
* Resources used:
* For the general program (not sorting), I utilized all autocomplete and
* cppreference to find the detailed reference of functions I needed to use. For
* implementing radix sort I primarily used
* https://en.wikipedia.org/wiki/Radix_sort#Most_significant_digit,_forward_recursive
* and a lot of trial and error. The sorting part is also VERY commented to make
* sure I knew exactly what I was doing at each point and why I was doing it.
*/
#include "OutputProcessor.h"
#include <fstream>
#include <iomanip>
#include <iostream>
#include <optional>
#include <ostream>
#include <string>
#include <vector>
#include <cstdint>
/**
* @brief Recursively most significant digit radix sorts a vector of indexes,
* based on the alphabetical value of a vector of strings. The returned vector
* is the same index vector but re-arranged to show where the elements in the
* string vector should be placed.
*
* @param INDEXES The vector of indexes to sort
* @param VECTOR_TO_SORT The string vector to base the sort off of. This will
* not be modified, and is only used to decide where an index in the other
* vector gets placed during sort.
* @param DEPTH The current sort depth, should be 0 or not passed if called from
* outside of this function. This controls which character of strings is
* inspected during sort.
*/
void radixSortIndexes(std::vector<size_t> &INDEXES,
const std::vector<std::string> &VECTOR_TO_SORT,
const unsigned int DEPTH = 0) {
// Construct 26 buckets, where 0 = A, 1 = B, 2 = C, ..., 25 = Z
std::vector<std::vector<size_t>> buckets(26);
// Another "bucket" for words that have already been completely sorted, as
// they have no character to check at position `DEPTH`
std::optional<size_t> alreadySorted = std::nullopt;
// Pass over each index, bucketing based on the character corresponding to
// the current depth
for (size_t i = 0; i < INDEXES.size(); i++) {
const size_t INDEX_TO_SORT = INDEXES.at(i);
const std::string &WORD = VECTOR_TO_SORT.at(INDEX_TO_SORT);
// Check if the word has any more characters to bucket. If it doesn't,
// place it in the special `alreadySorted` bucket. If it does, add it to
// the correct bucket for the current depth.
if (WORD.length() == DEPTH) {
alreadySorted = INDEX_TO_SORT;
} else {
buckets.at(WORD.at(DEPTH) - 65).push_back(INDEX_TO_SORT);
}
}
// Recursively apply bucket sort to each bucket unless it is already
// completely sorted (has no elements or only has one). With this we cascade
// the bucketing as far as is necessary, flattening after we have reached a
// depth at which there is no more to bucket (each bucket has 0 or 1
// elements)
for (size_t i = 0; i < buckets.size(); i++) {
std::vector<size_t> &bucket = buckets.at(i);
if (bucket.size() > 1) {
radixSortIndexes(bucket, VECTOR_TO_SORT, DEPTH + 1);
}
}
// Flatten the buckets at the current stage. We first add the
// `alreadySorted` value (less characters should go before more characters),
// and then append each item from each bucket individually.
std::vector<size_t> flattenedBucket;
if (alreadySorted.has_value()) {
flattenedBucket.push_back(alreadySorted.value());
}
for (size_t i = 0; i < buckets.size(); i++) {
flattenedBucket.insert(flattenedBucket.end(), buckets.at(i).begin(),
buckets.at(i).end());
}
// Finally, replace the indexes with the sorted result
INDEXES = flattenedBucket;
}
/**
* @brief Sorts the `words` vector (and `wordCounts` alongside) alphabetically
* using a most significant digit radix sort.
*
* @param words The list of words to sort alphabetically
* @param wordCounts The vector of word counts aligned to the `words` vector,
* which will be be adjusted based on the result of sorting `words`
*/
void radixSort(std::vector<std::string> &words,
std::vector<unsigned int> &wordCounts) {
// Create a vector of indexes the size of the amount of words we have. This
// is the vector that will actually be returned sorted in the end, where
// each element of this vector `i` is set to the index of `words` or
// `wordCounts` that belongs in position `i` when sorted. By doing this, we
// avoid having to try and pass around both the words and their
// corresponding counts throughout the sort, and can just re-assemble the
// vectors at the end.
std::vector<size_t> indexVector(words.size());
for (size_t i = 0; i < words.size(); i++) {
indexVector.push_back(i);
}
// Sort the `indexVector` vector against the `words` vector, starting with
// depth 0 (the left-most character)
radixSortIndexes(indexVector, words);
// Reconstruct the `words` and `wordCounts` vectors from the list of
// indexes, and replace the originals with the new ones
std::vector<std::string> sortedWords;
std::vector<unsigned int> sortedWordCounts;
for (size_t i = 0; i < indexVector.size(); i++) {
sortedWords.push_back(words.at(indexVector.at(i)));
sortedWordCounts.push_back(wordCounts.at(indexVector.at(i)));
}
words = sortedWords;
wordCounts = sortedWordCounts;
}
OutputProcessor::OutputProcessor() {
_fileOut = std::ofstream();
_allWords = std::vector<std::string>();
_uniqueWords = std::vector<std::string>();
_letterCounts = std::vector<unsigned int>(26, 0);
_wordCounts = std::vector<unsigned int>();
_totalLetterCount = 0;
_totalWordCount = 0;
}
void OutputProcessor::analyzeWords(std::vector<std::string> allWords,
const std::string PUNCTUATION) {
// Iterate over all words, processing incrementally
for (size_t wordIdx = 0; wordIdx < allWords.size(); wordIdx++) {
std::string &word = allWords.at(wordIdx);
// Remove punctuation from word
size_t punctuationIdx = 0;
while ((punctuationIdx = word.find_first_of(PUNCTUATION)) !=
std::string::npos) {
word.erase(punctuationIdx, 1);
}
// Save word internally
_allWords.push_back(word);
// Check all unique words for a match, and if so increment the count
bool foundUnique = false;
size_t uniqueWordIdx;
for (uniqueWordIdx = 0; uniqueWordIdx < _uniqueWords.size();
uniqueWordIdx++) {
if (_uniqueWords.at(uniqueWordIdx) == word) {
foundUnique = true;
break;
}
}
// If no unique word exists, add it to both vectors
if (!foundUnique) {
_uniqueWords.push_back(word);
_wordCounts.push_back(1);
} else {
_wordCounts.at(uniqueWordIdx)++;
}
// Add letter count for each letter in the word
for (size_t letterIdx = 0; letterIdx < word.length(); letterIdx++) {
char letter = word.at(letterIdx);
// Normalize to uppercase
if (letter >= 'a' && letter <= 'z') {
letter -= 97;
} else {
if (letter >= 'A' && letter <= 'Z') {
letter -= 65;
} else {
continue;
}
}
// Subtracting an uppercase letter by 65 creates its alphabetical
// index
_letterCounts.at(letter)++;
}
// Sum total letter count
_totalLetterCount += word.length();
// Increment total word count
_totalWordCount++;
}
radixSort(_uniqueWords, _wordCounts);
}
bool OutputProcessor::openStream() {
std::string file;
std::cout << "What is the name of the file you would like to write to? ";
std::cin >> file;
if (std::cin.fail()) {
std::cerr << "Invalid file input" << std::endl;
return false;
}
_fileOut.open(file);
if (_fileOut.fail()) {
std::cerr << "Unable to open file, does it exist?" << std::endl;
return false;
}
return true;
}
void OutputProcessor::closeStream() { _fileOut.close(); }
void OutputProcessor::write() {
// Calculate longest word length, longest number length, most common word,
// and least common word for later use in one pass for efficiency
size_t longestWordLength = 0;
size_t mostCommonWordIdx = 0;
size_t leastCommonWordIdx = 0;
for (size_t uniqueWordIdx = 0; uniqueWordIdx < _uniqueWords.size();
uniqueWordIdx++) {
std::string &uniqueWord = _uniqueWords.at(uniqueWordIdx);
unsigned long wordCount = _wordCounts.at(uniqueWordIdx);
if (uniqueWord.length() > longestWordLength) {
longestWordLength = uniqueWord.length();
}
// Equality can be ignored here because we want the word that was
// encountered first, so any subsequent extremes can be ignored
if (wordCount < _wordCounts.at(leastCommonWordIdx)) {
leastCommonWordIdx = uniqueWordIdx;
} else {
if (wordCount > _wordCounts.at(mostCommonWordIdx)) {
mostCommonWordIdx = uniqueWordIdx;
}
}
}
_fileOut << "Read in " << _totalWordCount << " words" << std::endl;
_fileOut << "Encountered " << _uniqueWords.size() << " unique words"
<< std::endl;
// Print out each unique word and how often it happened
const size_t MOST_COMMON_WORD_COUNT_LENGTH =
std::to_string(_wordCounts.at(mostCommonWordIdx)).length();
for (size_t uniqueWordIdx = 0; uniqueWordIdx < _uniqueWords.size();
uniqueWordIdx++) {
_fileOut << std::setw(longestWordLength) << std::left
<< _uniqueWords.at(uniqueWordIdx) << " : "
<< std::setw(MOST_COMMON_WORD_COUNT_LENGTH) << std::right
<< _wordCounts.at(uniqueWordIdx) << std::endl;
}
// Print the most and least common word
const std::string &MOST_COMMON_WORD = _uniqueWords.at(mostCommonWordIdx);
const std::string &LEAST_COMMON_WORD = _uniqueWords.at(leastCommonWordIdx);
size_t longerFrequentWordLength =
MOST_COMMON_WORD.length() > LEAST_COMMON_WORD.length()
? MOST_COMMON_WORD.length()
: LEAST_COMMON_WORD.length();
size_t mostFrequentWordCountLength =
std::to_string(_wordCounts.at(mostCommonWordIdx)).length();
_fileOut << " Most Frequent Word: " << std::setw(longerFrequentWordLength)
<< std::left << MOST_COMMON_WORD << " " << std::right
<< std::setw(mostFrequentWordCountLength)
<< _wordCounts.at(mostCommonWordIdx) << " (" << std::setw(7)
<< std::fixed << std::setprecision(3) << std::right
<< (float)_wordCounts.at(mostCommonWordIdx) / _totalWordCount * 100
<< "%)" << std::endl;
_fileOut << "Least Frequent Word: " << std::setw(longerFrequentWordLength)
<< std::left << LEAST_COMMON_WORD << " " << std::right
<< std::setw(mostFrequentWordCountLength)
<< _wordCounts.at(leastCommonWordIdx) << " (" << std::setw(7)
<< std::fixed << std::setprecision(3) << std::right
<< (float)_wordCounts.at(leastCommonWordIdx) / _totalWordCount *
100
<< "%)" << std::endl;
// Calculate the most and least common letters to display
uint8_t mostCommonLetterIdx = 0;
uint8_t leastCommonLetterIdx = 0;
for (size_t letterIdx = 0; letterIdx < 26; letterIdx++) {
// Here not using "or equals" means the letters later alphabetically get
// ignored if they occur the same amount
if (_letterCounts.at(letterIdx) <
_letterCounts.at(leastCommonLetterIdx)) {
leastCommonLetterIdx = letterIdx;
} else {
if (_letterCounts.at(letterIdx) >
_letterCounts.at(mostCommonLetterIdx)) {
mostCommonLetterIdx = letterIdx;
}
}
}
// Print out each letter along with the amount of times it occurs
const size_t MOST_COMMON_LETTER_COUNT_LENGTH =
std::to_string(_letterCounts.at(mostCommonLetterIdx)).length();
for (size_t letterIdx = 0; letterIdx < 26; letterIdx++) {
_fileOut << (char)(letterIdx + 65) << ": "
<< std::setw(MOST_COMMON_LETTER_COUNT_LENGTH) << std::right
<< _letterCounts.at(letterIdx) << std::endl;
}
// Print out the most and least common letters in total
_fileOut << " Most Frequent Letter: " << (char)(mostCommonLetterIdx + 65)
<< " " << std::setw(MOST_COMMON_LETTER_COUNT_LENGTH) << std::right
<< _letterCounts.at(mostCommonLetterIdx) << " (" << std::setw(7)
<< std::fixed << std::setprecision(3)
<< ((float)_letterCounts.at(mostCommonLetterIdx) /
_totalLetterCount * 100)
<< "%)" << std::endl;
_fileOut << "Least Frequent Letter: " << (char)(leastCommonLetterIdx + 65)
<< " " << std::setw(MOST_COMMON_LETTER_COUNT_LENGTH) << std::right
<< _letterCounts.at(leastCommonLetterIdx) << " (" << std::setw(7)
<< std::fixed << std::setprecision(3)
<< ((float)_letterCounts.at(leastCommonLetterIdx) /
_totalLetterCount * 100)
<< "%)" << std::endl;
}