446 lines
13 KiB
C++
446 lines
13 KiB
C++
#include "sort_controller.hpp"
|
|
#include "basic_sorts.hpp"
|
|
#include "trees.hpp"
|
|
#include <algorithm>
|
|
#include <chrono>
|
|
#include <fstream>
|
|
#include <iostream>
|
|
#include <string>
|
|
#include <vector>
|
|
|
|
// Initialization function for SortController class
|
|
SortController::SortController()
|
|
{
|
|
lineCount = 0;
|
|
currentType = INSERTION;
|
|
filename = "test/PERM/perm15K.txt";
|
|
allLists = 0;
|
|
sortGiven = 0;
|
|
return;
|
|
}
|
|
|
|
// Checks for command line arguments
|
|
void SortController::CheckArguments(int argc, char* arguments[])
|
|
{
|
|
std::string tempStr;
|
|
for (int i = 0; i < argc; i++)
|
|
{
|
|
tempStr = arguments[i];
|
|
if ((tempStr == "-a") || (tempStr == "--all"))
|
|
{
|
|
allLists = 1;
|
|
}
|
|
if ((tempStr == "-f") || (tempStr == "--filename"))
|
|
{
|
|
filename = arguments[i + 1];
|
|
}
|
|
if ((tempStr == "-l") || (tempStr == "--locate"))
|
|
{
|
|
wordToLocate = arguments[i + 1];
|
|
std::transform(wordToLocate.begin(), wordToLocate.end(), wordToLocate.begin(), ::toupper);
|
|
locate = 1;
|
|
}
|
|
if ((tempStr == "-d") || (tempStr == "--default"))
|
|
{
|
|
filename = "test/PERM/perm15K.txt";
|
|
}
|
|
if ((tempStr == "-s") || (tempStr == "--sort-type"))
|
|
{
|
|
sortGiven = 1;
|
|
tempStr = arguments[i + 1];
|
|
if (tempStr == "bst")
|
|
currentType = BST;
|
|
if (tempStr == "rbt")
|
|
currentType = RBT;
|
|
if (tempStr == "insertion")
|
|
currentType = INSERTION;
|
|
if (tempStr == "merge")
|
|
currentType = MERGE;
|
|
if (tempStr == "heap")
|
|
currentType = HEAP;
|
|
if (tempStr == "all")
|
|
sortGiven = 0;
|
|
}
|
|
}
|
|
return;
|
|
}
|
|
|
|
// Sets word list found in file into vector
|
|
void SortController::ReadWordFile(void)
|
|
{
|
|
std::string bufferStr;
|
|
std::ifstream file(this->filename);
|
|
if (!file.is_open())
|
|
{
|
|
std::cout << "Failed opening file: " << this->filename << '\n';
|
|
exit(1);
|
|
}
|
|
while (getline(file, bufferStr))
|
|
{
|
|
originalWordList.push_back(bufferStr);
|
|
lineCount++;
|
|
}
|
|
return;
|
|
}
|
|
|
|
// Main function for calling all sort categories
|
|
void SortController::RunBenchmarks(void)
|
|
{
|
|
if (allLists)
|
|
{
|
|
BenchmarkingAll();
|
|
return;
|
|
}
|
|
ReadWordFile();
|
|
Benchmarking();
|
|
return;
|
|
}
|
|
|
|
|
|
void SortController::SetFilename(std::string name)
|
|
{
|
|
filename = name;
|
|
return;
|
|
}
|
|
|
|
std::string SortController::GetFilename(void)
|
|
{
|
|
return filename;
|
|
}
|
|
|
|
void SortController::SetOutput(std::string filename)
|
|
{
|
|
outputFile.open(filename);
|
|
return;
|
|
}
|
|
|
|
bool SortController::IsOutputSpecified(void)
|
|
{
|
|
return outputFile.is_open();
|
|
}
|
|
|
|
|
|
void SortController::TestInsertion(void)
|
|
{
|
|
newWordList = originalWordList;
|
|
auto start = std::chrono::system_clock::now();
|
|
basic_sorts::InsertionSort(&newWordList);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
OutputResult();
|
|
}
|
|
|
|
void SortController::TestMerge(void)
|
|
{
|
|
newWordList = originalWordList;
|
|
auto start = std::chrono::system_clock::now();
|
|
basic_sorts::MergeSort(&newWordList);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
OutputResult();
|
|
}
|
|
|
|
void SortController::TestHeap(void)
|
|
{
|
|
newWordList = originalWordList;
|
|
auto start = std::chrono::system_clock::now();
|
|
basic_sorts::HeapSort(&newWordList);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
OutputResult();
|
|
}
|
|
|
|
void SortController::ConstructBST(void)
|
|
{
|
|
newWordList = originalWordList;
|
|
auto start = std::chrono::system_clock::now();
|
|
binarySearchTree.InsertWordList(&newWordList);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "BST construction took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::ConstructRBT(void)
|
|
{
|
|
newWordList = originalWordList;
|
|
tree_implementation::RedBlackTree newTree;
|
|
auto start = std::chrono::system_clock::now();
|
|
newTree.InsertWordList(&newWordList);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "RBT construction took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::BSTInsert(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
binarySearchTree.Insert(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::BSTSearch(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
binarySearchTree.Search(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::BSTInOrderTreeTraversal(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
if (IsOutputSpecified())
|
|
binarySearchTree.InOrderTreeTraversal(binarySearchTree.GetNodeWithWord(key), &outputFile);
|
|
else
|
|
binarySearchTree.InOrderTreeTraversal(binarySearchTree.GetNodeWithWord(key));
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::BSTPrintParentKey(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
binarySearchTree.PrintParentKey(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::BSTPrintLeftChild(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
binarySearchTree.PrintLeftChild(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::BSTPrintRightChild(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
binarySearchTree.PrintRightChild(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::BSTPrintPathToRoot(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
binarySearchTree.PrintPathToRoot(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::RBTInsert(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
redBlackTree.Insert(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::RBTSearch(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
redBlackTree.Search(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::RBTInOrderTreeTraversal(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
if (IsOutputSpecified())
|
|
redBlackTree.InOrderTreeTraversal(redBlackTree.GetNodeWithWord(key), &outputFile);
|
|
else
|
|
redBlackTree.InOrderTreeTraversal(redBlackTree.GetNodeWithWord(key));
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::RBTPrintParentKey(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
redBlackTree.PrintParentKey(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::RBTPrintLeftChild(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
redBlackTree.PrintLeftChild(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::RBTPrintRightChild(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
redBlackTree.PrintRightChild(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::RBTPrintPathToRoot(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
redBlackTree.PrintPathToRoot(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::RBTPrintColor(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
redBlackTree.PrintColor(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::RBTPrintParentColor(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
redBlackTree.PrintParentColor(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
void SortController::RBTPrintUncleColor(std::string key)
|
|
{
|
|
auto start = std::chrono::system_clock::now();
|
|
redBlackTree.PrintUncleColor(key);
|
|
auto end = std::chrono::system_clock::now();
|
|
sortTime = end - start;
|
|
std::cout << "Operation took " << sortTime.count() << 's' << std::endl;
|
|
}
|
|
|
|
|
|
// TODO: Depreciated; Clean up
|
|
// Function for starting sort functions
|
|
void SortController::Benchmarking(void)
|
|
{
|
|
// if (!sortGiven)
|
|
// currentType = INSERTION;
|
|
// if (currentType == INSERTION)
|
|
// {
|
|
|
|
// }
|
|
// if (!sortGiven)
|
|
// currentType = MERGE;
|
|
// if (currentType == MERGE)
|
|
// {
|
|
|
|
// }
|
|
// if (!sortGiven)
|
|
// currentType = HEAP;
|
|
// if (currentType == HEAP)
|
|
// {
|
|
|
|
// }
|
|
// if (currentType == BST)
|
|
// {
|
|
|
|
// }
|
|
// if (currentType == RBT)
|
|
// {
|
|
|
|
// start = std::chrono::system_clock::now();
|
|
// newTree.Search(wordToLocate);
|
|
// end = std::chrono::system_clock::now();
|
|
// sortTime = end - start;
|
|
// EchoSortTime("RBT");
|
|
// newTree.PrintPathToRoot(wordToLocate);
|
|
// }
|
|
}
|
|
|
|
// Sorts all default files if allLists is set
|
|
void SortController::BenchmarkingAll(void)
|
|
{
|
|
int fileCount = 10;
|
|
std::string newFilename;
|
|
for (int i = 1; i <= fileCount; i++)
|
|
{
|
|
lineCount = 0;
|
|
newFilename = "test/PERM/perm";
|
|
newFilename += std::to_string(15*i);
|
|
newFilename += "K.txt";
|
|
filename = newFilename;
|
|
ReadWordFile();
|
|
Benchmarking();
|
|
originalWordList.clear();
|
|
}
|
|
}
|
|
|
|
|
|
// Main function for printing results
|
|
void SortController::OutputResult(void)
|
|
{
|
|
switch(currentType)
|
|
{
|
|
case INSERTION:
|
|
EchoSortTime("IS");
|
|
WriteOutputToFile("IS");
|
|
break;
|
|
case MERGE:
|
|
EchoSortTime("MS");
|
|
WriteOutputToFile("MS");
|
|
break;
|
|
case HEAP:
|
|
EchoSortTime("HS");
|
|
WriteOutputToFile("HS");
|
|
break;
|
|
case BST:
|
|
EchoSortTime("BST");
|
|
WriteOutputToFile("BST");
|
|
break;
|
|
case RBT:
|
|
EchoSortTime("RBT");
|
|
WriteOutputToFile("RBT");
|
|
break;
|
|
default:
|
|
break;
|
|
}
|
|
}
|
|
|
|
// Prints sort time to the screen
|
|
void SortController::EchoSortTime(std::string outputFilename)
|
|
{
|
|
std::string sortSizeString = std::to_string(lineCount / 1000);
|
|
std::cout << outputFilename << sortSizeString;
|
|
std::cout << " took " << sortTime.count() << " s" << std::endl;
|
|
return;
|
|
}
|
|
|
|
// Prints result of sort operation to file
|
|
void SortController::WriteOutputToFile(std::string outputFilename)
|
|
{
|
|
std::string sortSizeString = std::to_string(lineCount / 1000);
|
|
std::string outputPath = "test/OUTPUT/";
|
|
outputPath += outputFilename + sortSizeString + "K.txt";
|
|
std::ofstream file(outputPath);
|
|
if (!file.is_open())
|
|
{
|
|
std::cout << "Failed opening file\n";
|
|
exit(1);
|
|
}
|
|
for (unsigned int i = 0; i < lineCount; i++)
|
|
file << newWordList[i] << '\n';
|
|
file.close();
|
|
}
|