Test driven data structure implementation in C++
I decided to explore the GoogleTest test framework for C++ while also brushing up on Templated data structures. I used Clion for this project.
MyDataStructures github repository
First use of GoogleTest
After creating the main project I created a subfolder called “Google_tests” and extracted the repository of GoogleTest in “Google_tests/lib”
I then added a CMakeLists.txt inside the Google_tests folder with the content:
project(Google_tests)
add_subdirectory(lib)
include_directories(${gtest_SOURCE_DIR}/include ${gtest_SOURCE_DIR})
Finally I added to the main project’s CMakeList.txt:
add_subdirectory(Google_tests)
and reloaded the project.
To see if everything works I created a “/Google_tests/tests.cpp” file with contents:
#include "gtest/gtest.h"
TEST(testSuite, testName){
EXPECT_EQ(1,1);
}
I added a new executable and linked it with GoogleTest in the “Google_tests/CMakeLists.txt” :
add_executable(Google_Tests_run tests.cpp)
target_link_libraries(Google_Tests_run gtest gtest_main)
After a quick reload I ran the test and everything worked fine!
MyDataStructures_lib
At first I implemented a linked list “/MyDataStructures_lib/LinkedList.h”, writing tests for it beforehand. The LinkedList class is templated so I used <int> for my tests. The tests are at “/Google_tests/LinkedListTests.cpp”.
Example of test and methods:
Test:
TEST(linkedListSuite, addToListWithIndexAndGetTest){
auto l = std::make_unique<myds::LinkedList<int>>();
l->add(0, 5);
EXPECT_EQ(l->get(0), 5);
}
Methods:
void add(const int idx, const T& data) {
if (idx > size || idx < 0) {
std::cerr << "Index out of bounds." << std::endl;
return;
}
auto newNode = std::make_shared<Node<T>>();
newNode->data = data;
auto currentNode = head;
if (idx == 0) {
newNode->next = head;
head = newNode;
} else {
for (int i=0; i<idx-1; i++) {
currentNode = currentNode->next;
}
newNode->next = currentNode->next;
currentNode->next = newNode;
}
size++;
}
T get(const int idx) const {
if (idx > size || idx < 0) {
std::cerr << "Index out of bounds." << std::endl;
return NULL;
} else {
auto currentNode = head;
for (int i=0; i<idx; i++) {
currentNode = currentNode->next;
}
return currentNode->data;
}
}
Using that linked list implementation we can easily create stacks and queues, so that’s exactly what I did. The Stack class living at “/MyDataStructures_lib/Stack.h” uses a linked list underneath and the tests for it are at “/Google_tests/StackTests.cpp”. Same for the Queue and Deque classes:“/MyDataStructures_lib/Queue.h”, “/Google_tests/QueueTests.cpp” and “/MyDataStructures_lib/Deque.h”, “/Google_tests/DequeTests.cpp”.
Trees
Next I’ll be creating a Binary Search Tree and then inherit from it to create an AVL Tree. I experimented a bit with variadic templates in order to insert multiple data to the binary tree at once:
void insert(const T& data) {
//impl
}
//Variadic overload of insert
template <std::same_as<T> ... Ts>
void insert(const T& data, const Ts& ... ts) {
insert(data);
insert(ts...);
}
std::same_as<T> needs C++20
I’m still new to variadic templates so maybe there’s a better way to do this.
I wanted to avoid using recursion on insertion and deletion so they became a bit complicated, especially the deletion.
Insertion:
void insert(const T& data) {
if (root == nullptr) {
root = std::make_shared<TreeNode<T>>();
root->data = data;
} else {
std::shared_ptr<TreeNode<T>> parentNode = nullptr;
auto currentNode = root;
while (currentNode != nullptr) {
parentNode = currentNode;
if (data < currentNode->data) {
currentNode = currentNode->leftChild;
} else if (data > currentNode->data){
currentNode = currentNode->rightChild;
} else { //duplicate entry
if (!allowDuplicates) return;
currentNode = currentNode->rightChild;
}
}
if (data < parentNode->data) {
parentNode->leftChild = std::make_shared<TreeNode<T>>();
parentNode->leftChild->data = data;
} else {
parentNode->rightChild = std::make_shared<TreeNode<T>>();
parentNode->rightChild->data = data;
}
}
}
Deletion:
void remove(const T& data) {
std::shared_ptr<TreeNode<T>> parentNode = nullptr;
auto currentNode = root;
while (currentNode != nullptr && currentNode->data != data) {
parentNode = currentNode;
if (data < currentNode->data) {
currentNode = currentNode->leftChild;
} else {
currentNode = currentNode->rightChild;
}
}
if (currentNode == nullptr) {
std::cerr << "Data not found." << std::endl;
return;
//if node has 0 to 1 children
} else if ( currentNode->leftChild == nullptr || currentNode->rightChild == nullptr) {
std::shared_ptr<TreeNode<T>> temp;
if (currentNode->leftChild == nullptr) {
temp = currentNode->rightChild;
} else {
temp = currentNode->leftChild;
}
if (parentNode == nullptr) {
//we changed the root
return;
} else if ( currentNode == parentNode->leftChild) {
parentNode->leftChild = temp;
} else {
parentNode->rightChild = temp;
}
//node has 2 children
} else {
parentNode = nullptr;
std::shared_ptr<TreeNode<T>> temp;
temp = currentNode->rightChild;
while (temp->leftChild != nullptr) {
parentNode = temp;
temp = temp->leftChild;
}
if (parentNode != nullptr) {
parentNode->leftChild = temp->rightChild;
} else {
currentNode->rightChild = temp->rightChild;
}
currentNode->data = temp->data;
}
}
As always the Binary Search Tree code lives at “/MyDataStructures_lib/BinarySearchTree.h” and the tests at “/Google_tests/BinarySearchTreeTests.cpp”.
Vasilis Vlasopoulos
dev/sec/sre