Data Structures

This project covers the organization of data and the algorithms!

Software Used

Languages Used

Visual Studio

C++

Feel Free to Download the Source Code.

Project Topics

Explanations
‍Dynamic Array
Vector
List
Dynamic List
Unordered Map
Dictionary
Binary Search Tree
Huffman Compression
Code
Dynamic Array
Vector
List
Dynamic List
Unordered Map
Dictionary
Binary Search Tree
Huffman Compression

Objectives

This project covers the organization of data and the algorithms that are used for sorting, searching, and problem solving. Students will learn how fundamental data structures and algorithms function and are implemented. Topics addressed in this course include managing complexity, linked structures, abstraction, analysis, vectors, lists, stacks, queues, trees, heaps, and graphs.

Programming Code

template<typename Type>
class DynArray { friend class TestSuite; // Giving access to test code Type* mArray;
unsigned int mSize;
unsigned int mCapacity;public: // Default constructor
// Creates a new object
// In: _startingCap An initial size to start the array at (optional)
DynArray(unsigned int _startingCap = 0) {
//mArray = new Type[_startingCap];
//mSize = 0;
if (_startingCap == 0)
{
mArray = nullptr;
}
else
{
mArray = new Type[_startingCap];
}
mCapacity = _startingCap;
} // Destructor
// Cleans up all dynamically allocated memory
~DynArray() {
Clear();
} // Copy constructor
// Used to initialize one object to another
// In: _da The object to copy from
DynArray(const DynArray& _da) {
*this = _da;
} // Assignment operator
// Used to assign one object to another
// In: _da The object to assign from
//
// Return: The invoking object (by reference)
// This allows us to daisy-chain
DynArray& operator=(const DynArray& _da) { if (this != &_da)
{
delete[]mArray;
mCapacity = _da.mCapacity;
mSize = _da.mSize;
mArray = new Type[mCapacity];
for (size_t i = 0; i < mSize; i++)
{
mArray[i] = _da.mArray[i];
}
}
return *this;
} // Overloaded [] operator
// Used to access an element in the internal array (read-only)
// In: _index The index to access at
//
// Return: The item at the specified index (by reference)
const Type& operator[](int _index) const {

return mArray[_index];

} // Overloaded [] operator
// Used to access an element in the internal array (writeable)
// In: _index The index to access at
//
// Return: The item at the specified index (by reference)
Type& operator[](int _index) {
return mArray[_index];
} // Get the current number of elements actively being used
//
// Return: The current number of elements used
int Size() const {
return mSize;
} // Get the current capacity of the internal array
//
// Return: The capacity of the array
int Capacity() const {

return mCapacity;
} // Clear the class for re-use
// Should clean up all dynamic memory and leave the object the same as if the default constructor had been called
void Clear() {
delete[]mArray;
mCapacity = 0;
mSize = 0;
mArray = nullptr;
} // Add an item to the end of the array
// Should resize the array if needed
// In: _data The item to be added
void Append(const Type& _data) {
//mSize = _data;
mArray[mSize] = _data;
if (mSize >= mCapacity)
{
/* mCapacity *= 2;
if (mCapacity == 0)
{
mCapacity = 1;
}*/
Reserve();
//mArray[mSize] = _data;
}
//mArray[mCapacity] = _data;
//mArray = new Type[_data];
//mArray[mSize] = _data;
mSize++;
} // Resizes the internal array, and copies all data over
// In: _newCapacity The new capacity of the array
// NOTE: If 0 is passed, the array should double in size
// If _newCapacity < mCapacity, do nothing
//
// SPECIAL CASE: If mCapacity is 0, then it should be set to 1
void Reserve(unsigned int _newCapacity = 0) {

Type* temp;
if (_newCapacity == 0)
{
mCapacity *= 2;
if (mCapacity==0)
{
mCapacity = 1;
}
_newCapacity = mCapacity;
}
if (_newCapacity >= mCapacity)
{
/*mCapacity = _newCapacity;*/
temp = new Type[mCapacity];
for (size_t i = 0; i < mSize; i++)
{
temp[i] = mArray[i];
}
mCapacity = _newCapacity;
/*for (size_t i = 0; i < mCapacity; i++)
{
delete[] mArray[i];
}*/
delete[]mArray;
mArray = temp;
/*for (size_t i = 0; i < mSize; i++)
{
mArray[i] = temp[i];
}*/
//delete temp;
}

//delete[]temp;
}};

inline bool IsPalindromeNumber(unsigned int _num) {

int rev = 0;
bool check = false;
for (int i = _num; i > 0; i /= 10)
{
rev = rev * 10 + i % 10;
}
if (_num == rev)
{
check = true;
}

return check;
}
class DSA_Lab2
{
friend class TestSuite; // Giving access to test code
private: vector<unsigned int> mValues; // contains all of the values
vector<unsigned int> mPalindromes; // contains just the numbers that are palindromespublic: // Fill out the vector with the contents of the binary file
// First four bytes of the file are the number of ints in the file
//
// In: _input Name of the file to open
//
// Note: Make sure the vector is empty and shrunk to 0 capacity before adding values
void Fill(const char* _input) {
Clear();
ifstream ifl;
int ffbytes;
int ffbytes1;
ifl.open(_input, ios_base::binary);
ifl.read((char*)&ffbytes, sizeof(int));
for (size_t i = 0; i < ffbytes; i++)
{
ifl.read((char*)&ffbytes1, sizeof(int));
mValues.push_back(ffbytes1);
}
mValues.shrink_to_fit();
ifl.close();
} // Fill out the vector with the contents of an array
//
// In: _arr The array of values
// _size The number of elements in the array
//
// Note: Make sure the vector is empty and shrunk to 0 capacity before adding values
void Fill(const unsigned int* _arr, int _size) {
Clear();
for (size_t i = 0; i < _size; i++)
{
mValues.push_back(_arr[i]);
}
} // Remove all elements from vector and decrease capacity to 0
void Clear() {
//vector<unsigned int> erasemValues;
//delete mValues[];
mValues.clear();
//mValues.empty();
mValues.shrink_to_fit();
//erasemValues = mValues.erase(erasemValues);
//mValues[] = { 0 };
//mValues.reserve(0);
mPalindromes.clear();
mPalindromes.shrink_to_fit(); } // Sort the vector
//
// In: _ascending To sort in ascending order or not
void Sort(bool _ascending) {
if (_ascending==true)
{
sort(mValues.begin(), mValues.end());
}
else
{
sort(mValues.begin(), mValues.end(), greater<>());
}
} // Get an individual element from the mValues vector
int operator[](int _index) {
return mValues[_index];
} // Determine if a value is present in the vector
//
// In: _val The value to check for
//
// Return: True, if the value is present
bool Contains(unsigned int _val) const {

bool check = false;
for (size_t i = 0; i < mValues.size(); i++)
{
if (mValues[i] == _val)
{
check = true;
}
}
return check;
} // Move all palindrome numbers from mValues vector to mPalindromes vector
//
// Pseudocode:
// iterate through the main values vector
// if the value is a palindrome
// add it to the palindrome vector
// remove it from the values vector
void MovePalindromes() {
//vector<unsigned int> erasemValues= mValues.begin();
bool check; vector<unsigned int>::iterator iter = mValues.begin(); while (iter != mValues.end())
{
check = IsPalindromeNumber(*iter);
if (check == true)
{
mPalindromes.push_back(*iter);
iter=mValues.erase(iter);
}
++iter;
}
}
};

class DSA_Lab4 { friend class TestSuite; // Giving access to test code // Data members
list<float> mList;public: // Add all of the values from the array into the list using queue ordering
//
// In: _arr The array of values
// _size The number of elements in the array
//
// Note: Make sure the list is empty and shrunk to 0 capacity before adding values
void QueueOrderingAdd(const float* _arr, int _size) {
mList.clear();
for (size_t i = 0; i < _size; i++)
{
mList.push_back(_arr[i]);
}

} // Add all of the values from the array into the list using queue ordering
//
// In: _arr The array of values
// _size The number of elements in the array
//
// Note: Make sure the list is empty and shrunk to 0 capacity before adding values
void StackOrderingAdd(const float* _arr, int _size) {
mList.clear();
for (size_t i = 0; i < _size; i++)
{
mList.push_front(_arr[i]);
} } // Remove a single value from the list using queue ordering
//
// Return: The value that was removed
float QueueOrderingRemove() {
mList.pop_back();
return mList.front();
} // Remove a single value from the list using stack ordering
//
// Return: The value that was removed
float StackOrderingRemove() {
mList.pop_back();
return mList.front();
} // Insert a value _index nodes away from the head node
// If _index is 0 - insert in front of the head/front node
// If _index is 5 - insert in front of the 5th node in the list
//
// Example:
// 0<-[5]<->[1]<->[6]<->[4]<->[2]->0
//
// Inserting a 7 at index 2
//
// 0<-[5]<->[1]<->[7]<->[6]<->[4]<->[2]->0
//
//
// In: _val The value to insert
// _index The "index" to add at
void Insert(float _val, int _index) {
float temp=0;
for (list<float>:: iterator i = mList.begin(); i != mList.end(); ++i)
{
//mList.insert(i, _val);
if (temp == _index)
{
mList.insert(i, _val);
}
/*else if (_index == 5)
{
mList.push_front(temp);
}*/
temp++;
}
} // Insert a value at the spot specified by the iterator passed in
//
// In: _val The value to insert
// _iter The iterator at the place to insert
void Insert(float _val, list<float>::iterator _iter) {
mList.insert(_iter, _val);
/*for (list<float>::iterator i = mList.begin(); i != mList.end(); ++i)
{
mList.insert(_iter, _val);
}*/
} // Remove all values from mList that have a decimal place value larger than _decimal
// Example:
// _decimal: 0.45
//
// mList: 498.28 // not removed, because .28 is not greater than .45
// 39812.181 // not removed, because .181 is not greater than .45
// 983.498 // removed, because .498 is greater than .45
// 3981.89 // removed, because .89 is greater than .45
// 487.2 // not removed, because .2 is not greater than .45
//
// With these values, the function would return 2
//
// In: _decimal The decimal value to check against (always less than 1.0)
//
// Return: The total number of values removed
int RemoveDecimalGreater(float _decimal) {
float dValues=0;
float total=0;
int tnvr=0;
for (list<float>::iterator i = mList.begin(); i != mList.end(); ++i)
{
dValues = (int)*i;
total = *i - dValues;

if (total > _decimal)
{
i = mList.erase(i);
//mList.remove(dValues);
tnvr++;
}

/*i++;*/
}
return tnvr;
}
};

template<typename Type>
class DList { friend class TestSuite; // Giving access to test code // Node structor a doubly linked list
struct Node { // Data members
Type data; // The value being stored
Node* next, * prev; // Pointers to the next and previous nodes // Constructor
//
// In: _data The value to store
// _next Pointer to the next node in the list
// _prev Pointer to the previous node in the list
Node(const Type& _data, Node* _next = nullptr, Node* _prev = nullptr) {
//Node* n = new Node(?);
/*Node* n = new Node;
n->data=_data;
n->next = _next;
n->prev = _prev;*/
data = _data;
next = _next;
prev = _prev;

}
};public: // An iterator class to made traversal more efficient
class Iterator {
public: // Data members
Node* mCurr; // Pre-fix increment operator
//
// Example:
// I - Iterator's curr
// R - Return
/*
Before 0<-[4]<->[5]<->[6]->0
I After 0<-[4]<->[5]<->[6]->0
I
R
*/
// Return: The Iterator (the invoking object)
Iterator& operator++() {
mCurr = mCurr->next;
return *this;

/*int temp = val;
val += 1;
return temp;*/
} // Post-fix increment operator
//
// Example:
// I - Iterator's curr
// R - Return
/*
Before 0<-[4]<->[5]<->[6]->0
I After 0<-[4]<->[5]<->[6]->0
R I */
// Return: The Iterator (before increment)
// NOTE: Will need a temporary pointer
Iterator operator++(int) {
Iterator temp=*this;
++(*this);
return temp;
} // Pre-fix decrement operator
//
// Example:
// I - Iterator's curr
// R - Return
/*
Before 0<-[4]<->[5]<->[6]->0
I After 0<-[4]<->[5]<->[6]->0
I
R
*/
// Return: The Iterator (the invoking object)
Iterator& operator--() {
mCurr = mCurr->prev;
return *this; } // Post-fix decrement operator
//
// Example:
// I - Iterator's curr
// R - Return
/*
Before 0<-[4]<->[5]<->[6]->0
I After 0<-[4]<->[5]<->[6]->0
I R */
// Return: The Iterator (before decrement)
// NOTE: Will need a temporary pointer
Iterator operator--(int) {
Iterator temp1 = *this;
--(*this);
return temp1;
} // Gets the value the iterator is currently pointing to
//
// Return: The data of the current iterator
Type& operator*() {
Iterator temp2 = *this;
return temp2;
}
}; // Data members
Node* mHead; // The head (first node) of the list
Node* mTail; // The tail (last node) of the list
unsigned int mSize; // Current number of nodes being storedpublic: // Default constructor
// Creates a new empty linked list
DList() {
mHead = nullptr;
mTail = nullptr;
mSize=0;
} // Destructor
// Cleans up all dynamically allocated memory
~DList() {

Clear();
} // Copy constructor
// Used to initialize one object to another
//
// In: _copy The object to copy from
DList(const DList& _copy) {
*this = _copy;
} // Assignment operator
// Used to assign one object to another
//
// In: _assign The object to assign from
//
// Return: The invoking object (by reference)
// This allows us to daisy-chain
DList& operator=(const DList& _assign) { if (this != &_assign)
{
Clear();
delete mHead;
delete mTail;
mSize = _assign.mSize; Node* assingIter = _assign.mHead;
while (assingIter != nullptr)
{
Node* n = new Node(assingIter->data, nullptr, nullptr);
n->next = nullptr;
n->data = assingIter->data;
if (mTail !=nullptr)
{
mTail->next = n;
n->prev = mTail;
mTail = n;
}
else
{
n->prev = nullptr;
mHead=n;
mTail=n; }
assingIter = assingIter->next;
}
/*
for (size_t i = 0; i < mSize; i++)
{
mHead[i] = _assign.mHead[i];
mTail[i] = _assign.mmTailt[i];
}*/
}
return *this;
}private: // Optional recursive helper method for use with Rule of 3
//
// In: _curr The current Node to copy
void Copy(const Node* _curr) { }public:
// Add a piece of data to the front of the list
//
// In: _data The object to add to the list
void AddHead(const Type& _data) {

Node* n = new Node(_data);
if (mHead == nullptr) {
mHead = n;
mTail = n;
}
else
{

mHead->prev = n;
n->next = mHead;
mHead = n;
}
mSize++;
} // Add a piece of data to the end of the list
//
// In: _data The object to add to the list
void AddTail(const Type& _data) {

Node* n = new Node(_data);
if (mHead == nullptr) {
mTail = n;
mHead = n;
}
else
{ mTail->next = n;
n->prev = mTail;
mTail = n;
}
mSize++;
} // Clear the list of all dynamic memory
// Resets the list to its default state
void Clear() {
if (mHead != nullptr) {

Node* tempH = mHead;
for (size_t i = 0; i < mSize; i++)
{
Node* tempHN = tempH->next;
delete tempH;
tempH = tempHN;
}
mSize = 0;
mHead = nullptr;
mTail = nullptr;
}
}private: // Optional recursive helper method for use with Clear
//
// In: _curr The current Node to clear
void Clear(const Node* _curr) {
if (mHead != nullptr) {
_curr = mHead;
mHead = mHead->next;
delete _curr;
}
}public: // Insert a piece of data *before* the passed-in iterator
//
// In: _iter The iterator
// _data The value to add
//
// Example:
/*
Before 0<-[4]<->[5]<->[6]->0
I After 0<-[4]<->[9]<->[5]<->[6]->0
I
*/
// Return: The iterator
// SPECIAL CASE: Inserting at head or empty list
// NOTE: The iterator should now be pointing to the new node created
Iterator Insert(Iterator& _iter, const Type& _data) {
Node* n = new Node(_data); if (_iter.mCurr == nullptr || _iter.mCurr == mHead )
{
AddHead(_data);
_iter.mCurr = mHead; }
else
{
n->prev = _iter.mCurr->prev;
n->next = _iter.mCurr; _iter.mCurr->prev->next = n;
_iter.mCurr->prev = n;
_iter.mCurr = n;
}
//mSize++;
return _iter;
} // Erase a Node from the list
//
// In: _iter The iterator
//
// Example
/* Before 0<-[4]<->[5]<->[6]->0
I After 0<-[4]<->[6]->0
I
*/
// Return: The iterator
// SPECIAL CASE: Erasing head or tail
// NOTE: The iterator should now be pointing at the node after the one erased
Iterator Erase(Iterator& _iter) {
Node* tempH;
if (_iter.mCurr == nullptr)
{

/*for (size_t i = 0; i < mSize; i++)
{
_iter = tempH->next;
delete tempH;
tempH = _iter;
}*/
}
else if(_iter.mCurr==mHead)
{
tempH = _iter.mCurr->next;
delete mHead;
mHead = tempH;
_iter.mCurr = mHead;
_iter.mCurr->prev = nullptr;
}
else if (_iter.mCurr == mTail)
{
tempH = _iter.mCurr->prev;
delete mTail;
mTail = tempH;
mTail->next = nullptr;
_iter.mCurr = mTail->next;

}
else
{
tempH = _iter.mCurr;
_iter.mCurr->prev->next = _iter.mCurr->next;
_iter.mCurr->next->prev = _iter.mCurr->prev; Node* tempH1 = _iter.mCurr->next;
delete tempH;

_iter.mCurr = tempH1;

/*for (size_t i = 0; i < mSize; i++)
{
_iter = tempH->prev;
delete tempH;
tempH = _iter;
}*/
}
mSize--;
return _iter;
} // Set an Iterator at the front of the list
//
// Return: An iterator that is pointing to the list's head
Iterator Begin() {
Iterator n;
n.mCurr = mHead;
return n;
} // Set an Iterator pointing to the end of the list
//
// Return: An iterator that is pointing to a null pointer
Iterator End() {
Iterator n;
n.mCurr = mTail;
return n;
}
};

class DSA_Lab6 { friend class TestSuite; // Giving access to test code // Data members
int mLetterValues[26];
unordered_map<string, int> mScrabbleMap;public: // In Scrabble, each letter has a value associated with it.
// This method will populate the array of letter values.
//
// In: _letterValues The array of 26 values
void PopulateLetterValues(const int* _letterValues) {

for (size_t i = 0; i < 26; i++)
{
mLetterValues[i] = _letterValues[i];
}
} // Retrieve the value of a particular letter
//
// In: _letter The letter to get the score for
//
// Return: The score value for the letter passed in
// NOTE: The letter passed in will always be upper-case
int GetLetterValue(char _letter) {

/*char letter = ' ';
for (size_t i = 0; i < 26; i++)
{
letter = mLetterValues[i];
_letter = letter;
}*/
return mLetterValues[_letter - 65];
}

// Get the value of a word
// This is done by adding up the values of each letter in the word
//
// In: _word The word to get the value of
//
// Return: The total value of the word
int GetWordValue(string _word) {

int value = 0;
for (size_t i = 0; i < _word.size(); i++)
{
value += GetLetterValue(_word[i]);
}
return value;
//return mLetterValues[_letter - 65];
} // Create a pair to add into the scrabbleMap
// This will have a "first" of the word, and a "second" of the total score
//
// In: _word The word for the pair
//
// Return: A pair that contains the word and the total score
pair<string, int> CreatePair(string _word) {
pair <string, int> vpair;
vpair.first = _word;
vpair.second = GetWordValue(_word);
return vpair;
} // Load a file containing all of the possible scrabble words, along with their values
// This file will contain one word per line
// In: _filename The name of the file to load
//
// Note: You may want to use one or more existing methods to help.
void LoadWords(const char* _filename) {
ifstream file(_filename);
string doc;
if (file.is_open())
{
while (getline(file,doc))
{
mScrabbleMap.insert(CreatePair(doc));
}
file.close();
}
//mScrabbleMap = unordered_map<string, int>;
}

/**********************************/
/* ONLY FOR USE IN FindValueInMap */
/**********************************/
int values[26] = { 1, 3, 3, 2, 1, 4, 2, 4, 1, 8, 5, 1, 3, 1, 1, 3, 10, 1, 1, 1, 1, 4, 4, 8, 4, 10 }; // Searches for a word in the map, and retrieves the score for that word
// This will make use of some of your previous methods
// Use above "values" array to populate your letter scores
// Use "words.txt" for loading words
//
// In: _word The word to search for
//
// Return: The word score for _word (or -1 if not found)
int FindValueInMap(string _word) {
PopulateLetterValues(values);
LoadWords("words.txt");
if (mScrabbleMap.find(_word) != mScrabbleMap.end())
{
return mScrabbleMap[_word];
}
else
{
return -1;
}
}
};

template<typename Key, typename Value>
class Dictionary { friend class TestSuite; // Giving access to test code // The objects stored in the hash-table
struct Pair {
Key key; // The key for insertion/lookup
Value value; // The data // Constructor
// In: _key
// _value
Pair(const Key& _key, const Value& _value) {
key = _key;
value = _value;
} // For testing
bool operator==(const Pair& _comp) {
return (_comp.key == key &&
_comp.value == value);
}
}; list<Pair>* mTable; // A dynamic array of lists (these are the buckets)
unsigned int mNumBuckets; // Number of elements in mTable
unsigned int(*mHashFunc)(const Key&); // Pointer to the hash functionpublic: // Constructor
// In: _numBuckets The number of elements to allocate
// _hashFunc The hashing function to be used
Dictionary(unsigned int _numBuckets, unsigned int (*_hashFunc)(const Key&)) {
mNumBuckets = _numBuckets;
mHashFunc= _hashFunc;
mTable = new list<Pair>[mNumBuckets];
} // Destructor
// Cleans up any dynamically allocated memory
~Dictionary() {
Clear();
delete[] mTable;
} // Copy constructor
// Used to initialize one object to another
// In: _dict The object to copy from
Dictionary(const Dictionary& _dict) {
*this = _dict;
//this->copyDic(_dict);
} // Assignment operator
// Used to assign one object to another
// In: _dict The object to assign from
//
// Return: The invoking object (by reference)
// This allows us to daisy-chain
Dictionary& operator=(const Dictionary& _dict) {

if (this != &_dict)
{
Clear();
delete[] mTable;
mNumBuckets = _dict.mNumBuckets;
mHashFunc = _dict.mHashFunc;
mTable = new list<Pair>[mNumBuckets];
for (size_t i = 0; i < mNumBuckets; i++)
{
mTable[i] = _dict.mTable[i];
}
}
return *this;
}

// Clear
// Clears all internal data being stored
// NOTE: Does not delete table or reset hash function
void Clear() {

if (mTable != nullptr) {
for (size_t i = 0; i < mNumBuckets; i++)
{
mTable[i].clear();
} }
} // Insert an item into the table
// In: _key The key to add at
// _value The value at the key
//
// NOTE: If there is already an item at the provided key, overwrite it.
void Insert(const Key& _key, const Value& _value) {

int hashValue = mHashFunc(_key);
//mTable[hashValue];
bool check = false; for (typename list<Pair>::iterator i = mTable[hashValue].begin(); i != mTable[hashValue].end(); i++)
{

if (i->key == _key)
{
check = true;
i->value = _value;
}
}
if (!check)
{
Pair mtableValue = Pair(_key, _value);
mTable[hashValue].push_back(mtableValue);
}

} // Find a value at a specified key
// In: _key The key to search for
//
// Return: A const pointer to the value at the searched key
// NOTE: Return a null pointer if key is not present
const Value* Find(const Key& _key) {

//const Value value;
int hashValue = mHashFunc(_key); for (typename list<Pair>::iterator i = mTable[hashValue].begin(); i != mTable[hashValue].end(); i++)
{ //if (i->key != _key)
{
if (i->key == _key)
{
/*value = i->value;*/
return &i->value;

}
}

}
return nullptr;
} // Remove a value at a specified key
// In: _key The key to remove
//
// Return: True, if an item was removed
bool Remove(const Key& _key) {
bool check = false;
int hashValue = mHashFunc(_key);

//list<Pair>::iterator i;
for (typename list<Pair>::iterator i= mTable[hashValue].begin(); i != mTable[hashValue].end(); i++)
{ if (i->key == _key)
{
mTable[hashValue].erase(i);
check = true;
return true;
} else
{
check = false;
}

} return false;
}
};

template<typename Type>
class BST { friend class TestSuite; // Giving access to test code struct Node {
Type data;
Node* left, * right; // Constructor
// Creates a leaf node
//
// In: _data The value to store in this node
Node(const Type& _data) {
this->data = _data;
this->left = nullptr;
this->right = nullptr;
}
}; // Data members
Node* mRoot;public: // Default constructor
// Creates an empty tree
BST()
{ mRoot = nullptr;
/*mRoot->left = nullptr;
mRoot->right = nullptr;*/

//data->left = nullptr;
/*left=nullptr;
right=nullptr;*/
/*this->left = nullptr;
this->right = nullptr;*/
//this->mRoot = NULL;
} // Destructor
// Clear all dynamic memory
~BST() {
Clear();
} // Copy constructor
// Used to initialize one object to another
//
// In: _copy The object to copy from
BST(const BST<Type>& _copy) {
*this = _copy;
}
// Assignment operator
// Used to assign one object to another
//
// In: _assign The object to assign from
//
// Return: The invoking object (by reference)
// This allows us to daisy-chain
BST<Type>& operator=(const BST<Type>& _assign) { Clear();
Copy(_assign.mRoot);
return *this;
}private: // Optional recursive helper method for use with Rule of 3
//
// In: _curr The current Node to copy
//
// NOTE: Use pre-order traversal
void Copy(const Node* _curr) {
if (_curr==nullptr)
{
return;
}
Push(_curr->data);
Copy(_curr->left);
Copy(_curr->right);
}public: // Clears out the tree and readies it for re-use
void Clear() {

Clear(mRoot);
/*delete mRoot->left;
delete mRoot->right;*/
mRoot= nullptr;
}private: // Optional recursive helper method for use with Clear
//
// In: _curr The current Node to clear
//
// NOTE: Use post-order traversal
void Clear(Node* _curr) {

if (_curr == nullptr)
{
return;
}
Clear(_curr->left);
Clear(_curr->right);
delete _curr;
/*delete left;
delete right;*/ }public: // Add a value into the tree
//
// In: _val The value to add
void Push(const Type& _val) {

//Node* nPush = new Node(_val);
//if (mRoot == nullptr)
//{
//
// //nPush->data = _val;
// mRoot = nPush;
//} //else
//{
// Push(_val, mRoot);
//} //
//Node* temp = nPush;
//delete nPush;
Push(_val, mRoot);
}private: // Optional recursive helper method for use with Push
//
// In: _val The value to add
// _curr The current Node being looked at
void Push(const Type& _val, Node* _curr) {
if (mRoot == nullptr)
{
mRoot= new Node(_val);
}
else if (_curr->data > _val)
{
if (_curr->left != nullptr)
{
Push(_val, _curr->left);
}
else
{
//Node* nPushL = new Node(_val);
_curr->left = new Node(_val);
}
}
else
{
if (_curr->right != nullptr)
{
Push(_val, _curr->right);
}
else
{
//Node* nPushR = new Node(_val);
_curr->right = new Node(_val);
}
}
}public: // Checks to see if a value is in the tree
//
// In: _val The value to search for
//
// Return: True, if found
bool Contains(const Type& _val) { if (mRoot == nullptr)
{
return false;
}
else if (mRoot->data < _val)
{
return true;
}
else if (mRoot->data == _val)
{
return true;
}
else
{
if (_val < mRoot->data)
{
return false;
}
}
return false;
}
//// while (mRoot != nullptr)
//// {
//// if (mRoot->data > _val)
//// {
//// //return mRoot->left.Contains(_val);
//// mRoot = mRoot->left;
//// //if (mRoot->data == _val)
//// //{
//// // return true;
//// // //break;
//// //}
//// }
//// else if (mRoot->data < _val)
//// {
//// //return mRoot->right.Contains(_val);
//// mRoot = mRoot->right;
//// //if (mRoot->data == _val)
//// //{
//// // return true;
//// // //break;
//// //}
//// }
//// else if (mRoot->data == _val)
//// {
//// return true;
//// break;
//// }
//// }
//// if (mRoot == nullptr)
//// {
//// return false;
//// }
////}
//
// //return true;
//// if (mRoot->data < _val)
//// {
//// return true;
//// //this.data = data;
//// if (mRoot->left == nullptr)
//// {
//// return false;
//// }
//// else
//// {
//// return mRoot->left.Contains(_val);
//// }
//// }
//// else
//// {
//// return false;
//// //this.data = data;
//// if (mRoot->right == nullptr)
//// {
//// return false;
//// }
//// else
//// {
//// return mRoot->right.Contains(_val);
//// }
//// }
////} // Removes a value from tree (first instance only)
//
// In: _val The value to search for
//
// Return: True, if a Node was removed
// NOTE: Keep in mind the three cases
// A) 2 children ("fix" tree)
// B) 0 children
// C) 1 child
bool Remove(const Type& _val) {
Node* child = mRoot;
Node* parent = nullptr; while (child !=nullptr)
{
if (child->data > _val)
{
parent = child;
child = child->left;
}
else if (child->data < _val)
{
parent = child;
child = child->right;
}
else if (child->data == _val)
{
/*return true;*/
break;
}
} if (child == nullptr)
{
return false;
}
else
{
//case 02
if (child->left != nullptr && child->right != nullptr)
{
Node* endtree = child->right;
while (endtree->left != nullptr)
{
parent = endtree;
endtree = endtree->left;
}
child->data = endtree->data;
child = endtree;
} //case 00
if (child->left == nullptr && child->right == nullptr)
{
if (child==mRoot)
{
mRoot = nullptr;
}
else if (parent->left == child)
{
parent->left = nullptr;
}
else if (parent->right == child)
{
parent->right = nullptr;
}
delete child;
} //case 01
else if (child->left != nullptr || child->right != nullptr)
{
if (child == mRoot)
{
if (child->left !=nullptr)
{
mRoot = child->left;
}
else if (child->right != nullptr)
{
mRoot = child->right;
}
}
else if (parent->left == child)
{
if (child->right == nullptr)
{
parent->left = child->left;
}
else
{
parent->left = child->right;
}
}
else if (parent->right == child)
{
if (child->right == nullptr)
{
parent->right = child->left;
}
else
{
parent->right = child->right;
}
}
delete child;
}

}

return true;
} // Returns a space-delimited string of the tree in order
/*
Example:
24
/ \
10 48
\ \
12 50 Should return: "10 12 24 48 50"
*/
// NOTE: Use to_string to convert an int to its string equivelent string InOrder() {
string sD;
InOrder(mRoot, sD);
sD.pop_back();
return sD;
}private: // Optional recursive helper method to help with InOrder
//
// In: _curr The current Node being looked at
// _str The string to add to
//
// NOTE: Use in-order traversal
void InOrder(Node* _curr, string& _str) {

if (_curr == nullptr)
{
return;
}

if (_curr->left != nullptr)
{
InOrder(_curr->left, _str);
}
if (_curr->right != nullptr) // if left is not empty InOrder right
{
_str.append(to_string(_curr->data) + " ");
InOrder(_curr->right, _str);
}
if (_curr->right == nullptr) // if right is null add data to _str
{
_str.append(to_string(_curr->data) + " ");
}
}};

class Huffman { friend class TestSuite; // Giving access to test code // A node for a a Huffman tree
struct HuffNode {
short value; // The value to store (-1 if not a leaf node, 0-255 for the ascii value)
unsigned int freq; // The frequency of the node
HuffNode* left; // Left child
HuffNode* right; // Right child
HuffNode* parent; // Parent node // Constructor
//
// In: _value The value of the node
// _freq The frequency of the node
// _left The node's left child (OPTIONAL)
// _right The node's right child (OPTIONAL)
// _parent The parent node (OPTIONAL)
HuffNode(short _value, unsigned int _freq, HuffNode* _left = nullptr, HuffNode* _right = nullptr, HuffNode* _parent = nullptr)
: value(_value), freq(_freq), left(_left), right(_right), parent(_parent) {
/*value = _value;
freq = _freq;
left = _left;
right = _right;
parent = _parent;*/
} // Copy constructor
//
// In: _hnode The node to copy from
HuffNode(const HuffNode& _hnode)
: value(_hnode.value), freq(_hnode.freq), left(_hnode.left), right(_hnode.right), parent(_hnode.parent) {
/**this = _hnode;*/
}
}; // A binary predicate used to compare HuffNodes
// This is used in the GenerateTree method
struct HuffCompare {
// Compare the frequency of two nodes
//
// In: _a The first node
// _b The second node
//
// Return: True, if _a's freq is greater than _b's freq
bool operator() (const HuffNode* _a, const HuffNode* _b) {
return(_a->freq > _b->freq);
}
};
// Data members
string mFileName; // The name of the file to open for read/write
unsigned int mFrequencyTable[257]; // The frequency of each character in the file (the index in the array is the char's ASCII value)
// [256] of the array is the total count of characters in the file
vector<HuffNode*> mLeafList; // Contains all of the dynamically allocated leaf nodes
HuffNode* mRoot; // The root of the huffman tree (set in GenerateTree)
vector<bool> mEncodingTable[256]; // Contains all of the bit-codes used to compress/decompress a file // Default constructor
//
// In: _fileName The name of the file to open
// _access The way to open the file
Huffman(string _fileName) {
// 1. Assign the data members the values from the parameters
mFileName = _fileName;
// 2. Zero out the frequency table
for (size_t i = 0; i < 257; i++)
{
mFrequencyTable[i] = 0;
}
}
// Generate the frequency table for the Huffman algorithm (WRITING ONLY)
//
// NOTE: mFrequencyTable is an array of 257 unsigned ints representing the
// count of each character in the file (the index in the array is the char's ASCII value)
// Example: 'A' is ASCII 65, so if A is the character being checked, [65] of your array would get incremented
// [256] of your array is the total count of characters in the file
void GenerateFrequencyTable() {
// 1. Open the file in binary mode
ifstream bFile(mFileName, ios::out | ios::binary); // 2. Get the total count of the file (This can also be done in the next step instead)
size_t totalCount; bFile.seekg(0, bFile.end);
totalCount = bFile.tellg();
bFile.seekg(0, bFile.beg);
// 3. Read the file one byte at a time, and increment the corresponding index
char* fByte = new char[totalCount];
bFile.read(fByte, totalCount); for (size_t i = 0; i < totalCount; i++)
{
mFrequencyTable[fByte[i]]++;
mFrequencyTable[256]++;
//mFrequencyTable[(unsigned char)bFile.get()++];
} // 4. Close the file when complete
bFile.close();
delete[] fByte;
} // Generate the leaf list for the Huffman algorithm (used in READ AND WRITE)
//
// Note: Will cause leaks until ClearTree is implemented
void GenerateLeafList() {
// 1. Iterate through the frequency table (for all ASCII values) and dynamically create a leaf node for each non-0
// frequency. Add it to the mLeafList vector.
for (short i = 0; i < 256; i++)
{
if (mFrequencyTable[i] != 0)
{
struct HuffNode* leafList = new struct HuffNode(i, mFrequencyTable[i]);
mLeafList.push_back(leafList);
}
}
} // Generate a Huffman tree
void GenerateTree() {
// 1. Create the priority queue
// This will be storing HuffNode*'s
// in a vector, and will be using the HuffCompare for comparison
priority_queue<HuffNode*, vector<HuffNode*>, HuffCompare> pq;
// 2. Add in all values from your leaf list
for (size_t i = 0; i < mLeafList.size(); i++)
{
pq.push(mLeafList[i]);
}
// 3. Enter the tree generation algorithm
// While the queue has more than 1 node
// Store the top two nodes into some temporary pointers and pop them
// Create a new parent node /w 1st node as left, and 2nd as right
// Set the parent value to -1, and frequency to the sum of its children
// Set the 1st and 2nd node's parent to the new node you created
// Insert new node into queue while (pq.size() > 1)
{
//Store the top two nodes into some temporary pointers and pop them
HuffNode* tempTopNode1 = pq.top();
pq.pop();
HuffNode* tempTopNode2 = pq.top();
pq.pop(); //Create a new parent node /w 1st node as left, and 2nd as right
HuffNode* parentNode=nullptr;
//Set the parent value to -1, and frequency to the sum of its children
/*parentNode->value = -1;
parentNode->freq = tempTopNode1->freq + tempTopNode2->freq;*/
parentNode = new HuffNode(-1, tempTopNode1->freq + tempTopNode2->freq, tempTopNode1, tempTopNode2); //Set the 1st and 2nd node's parent to the new node you created
tempTopNode1->parent = parentNode;
tempTopNode2->parent = parentNode; //Insert new node into queue
pq.push(parentNode); } // 4. Set the root of the tree (this will be the only node in the queue)
mRoot = pq.top();
pq.pop();
} // Generating the encoding table for the Huffman algorithm
//
// Each vector will contain the bit-code corresponding to that index in the frequency table
void GenerateEncodingTable() {
// 1. Go through all of the leaf nodes and generate the bit codes
// You will do this by traversing up the tree from the leaf node
// As you move up, push a 0 to the vector if you passed through a left child connection
// and a 1 if you passed through a right
// Once you hit the root node, reverse the values in the vector

HuffNode* bitCodes=nullptr; for (size_t i = 0; i < mLeafList.size(); i++)
{
bitCodes = mLeafList[i];
while (bitCodes->parent !=nullptr)
{
//As you move up, push a 0 to the vector if you passed through a left child connection
if (bitCodes->parent->left == bitCodes)
{
mEncodingTable[mLeafList[i]->value].push_back(0);
} //and a 1 if you passed through a right
if (bitCodes->parent->right == bitCodes)
{
mEncodingTable[mLeafList[i]->value].push_back(1);
} bitCodes = bitCodes->parent;
}

//Once you hit the root node, reverse the values in the vector
reverse(mEncodingTable[mLeafList[i]->value].begin(), mEncodingTable[mLeafList[i]->value].end());
}

} // Clear the tree of all dynamic memory (by using the helper function)
void ClearTree() {
// 1. Call the helper function with the root and then set it back to null
ClearTree(mRoot);
mRoot = nullptr;
} // Clear the tree of all dynamic memory (recursive helper function)
//
// In: _curr The current node to clean up
//
// Note: This will be a recursive function that does a post-order deletion
void ClearTree(HuffNode* _curr) {
if (_curr == nullptr)
{
return;
}
ClearTree(_curr->left);
ClearTree(_curr->right);
//free(_curr);
delete _curr;
} // Write a Huffman compressed file to disk
//
// In: _outputFile Where to write the compressed data to
//
// Note: You will use most of your other functionality to complete this function
void Compress(const char* _outputFile) {
// 1. Create the frequency table, leaf list, tree, and encoding table
GenerateFrequencyTable();
GenerateLeafList();
GenerateTree();
GenerateEncodingTable(); // 2. Create a BitOStream and supply it the huffman header
BitOStream bStremFile(_outputFile, (char*)mFrequencyTable, sizeof(int) * 257);
// 3. Open the input file in binary mode with a standard ifstream
ifstream bFile(mFileName, ios::out | ios::binary);
/*int totalCount;
bFile.seekg(0, bFile.end);
totalCount = bFile.tellg();
bFile.seekg(0, bFile.beg);
char* fByte = new char[totalCount]; bFile.read(fByte, totalCount);
char* fHead = new char[257*4];*/ // 4. Start the compression process. (You can read the whole file into a buffer first if you want)
// For each character in the original file, write out the bit-code from the encoding table
/*for (size_t i = 0; i < 257 * 4; i+=4)
{
memccpy((char*)&fHead[i], (char*)&mFrequencyTable[i / 4], 4);
}*/

for (size_t i = 0; i < mFrequencyTable[256]; i ++)
{
bStremFile << mEncodingTable[(char)bFile.get()];
} // 5. Close the file streams when done
bFile.close();
bStremFile.Close();
// 6. Clear the tree (and optional buffer)
ClearTree();
} // Decompress a huffman-compressed file
//
// In: _outputFile Where to write the uncompressed data to
//
// Note: The mFileName will be the compressed file
void Decompress(const char* _outputFile) {
// 1. Create a BitIStream and read the frequency table
BitIStream bStreamFile(mFileName.c_str(), (char*)mFrequencyTable, sizeof(int) * 257);
// 2. Create the leaf list and tree
GenerateLeafList();
GenerateTree(); // 3. Create the stream for output (binary mode)
ofstream oStreamFile(_outputFile, ios_base::binary);
// 4. Create a bool to use for traversing down the list, and a char to store the character for writing
bool check;
char store;
// 5. Create a node pointer for use in traversing the list (start it at the top)
HuffNode* nodetrav = mRoot;
// 6. Go through the compressed file one bit at a time, traversing through the tree
// When you get to a leaf node, write out the value, and go back to the root
// Note: Remember, there may be trailing 0's at the end of the file, so only loop the appropriate number of times
for (size_t i = 0; i < mFrequencyTable[256]; i++)
{
//while (!bStreamFile.eof())
while (nodetrav->right != nullptr && nodetrav->left != nullptr)
{
bStreamFile >> check;
/*if (nodetrav != nullptr && nodetrav->left != nullptr)*/

if (check == true)
{
nodetrav = nodetrav->right;
}
else
{
nodetrav = nodetrav->left;
}
}
store=(char)nodetrav->value;
oStreamFile << store;
nodetrav = mRoot;
}
// 7. Close the streams
bStreamFile.Close();
oStreamFile.close();
// 8. Clean up the dynamic memory by clearing the tree
ClearTree();
}
};

Guidance

Set Up the basic structure of each data type!

Programming Explanation

What is a Dynamic Array?

A dynamic array is quite similar to a regular array, but its size is modifiable during program runtime. DynamArray elements occupy a contiguous block of memory.

Once an array has been created, its size cannot be changed. However, a dynamic array is different. A dynamic array can expand its size even after it has been filled.

During the creation of an array, it is allocated a predetermined amount of memory. This is not the case with a dynamic array as it grows its memory size by a certain factor when there is a need.

‍

Vector

Vectors are same as dynamic arrays with the ability to resize itself automatically when an element is inserted or deleted, with their storage being handled automatically by the container. Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators. In vectors, data is inserted at the end. Inserting at the end takes differential time, as sometimes there may be a need of extending the array. Removing the last element takes only constant time because no resizing happens. Inserting and erasing at the beginning or in the middle is linear in time.

List

Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.

List containers are implemented as doubly-linked lists; Doubly linked lists can store each of the elements they contain in different and unrelated storage locations. The ordering is kept internally by the association to each element of a link to the element preceding it and a link to the element following it.

‍

Dynamic List

Linked lists are inherently dynamic data structures; they rely on new anddelete (or malloc and free) for their operation. Normally, dynamic memory management is provided by the C/C++ standard library, with help fromthe operating system. However, nothing stops us from writing our own allocator,providing the same services as malloc and free.

Unordered Map

The unordered_map in C++ is like a data structure of dictionary type that store element. It has a sequence of (key, value) pair, which allows fast retrieval of an individual element based on their unique key.

‍

Dictionary

A dictionary is defined as a general-purpose data structure for storing a group of objects. A dictionary is associated with a set of keys and each key has a single associated value. Whenpresented with a key, the dictionary will simply return the associated value.

‍

Binary Search Tree

A Binary Search Tree or BST as it is popularly called is a binary tree that fulfills the following conditions:

The nodes that are lesser than the root node which is placed as left children of the BST.
The nodes that are greater than the root node that is placed as the right children of the BST.
The left and right subtrees are in turn the binary search trees.

This arrangement of ordering the keys in a particular sequence facilitates the programmer to carry out operations like searching, inserting, deleting, etc. more efficiently. If the nodes are not ordered, then we might have to compare each and every node before we can get the operation result.

‍

Huffman Compression

Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters. The most frequent character gets the smallest code and the least frequent character gets the largest code.