dsa-practice/tests/test.cpp

#include <CppUTest/CommandLineTestRunner.h>
#include <CppUTest/TestHarness.h>

#include <chapter1/chapter1.hpp>
#include <chapter2/chapter2.hpp>
#include <chapter12/chapter12.hpp>
#include <dope/linkedlist.hpp>
#include <dope/stacks.hpp>
#include <dope/bintree.hpp>
#include <string.h>

// Chapter 1: Arrays _________________________________________________

TEST_GROUP(ChapterOne){};

TEST(ChapterOne, IsUnique){
  auto const t1 = IsUnique("aabbcc", 6);
  auto const t2 = IsUnique("abcdef", 6);
  CHECK_FALSE(t1);
  CHECK(t2);
}

TEST(ChapterOne, CheckPermutations){
  const auto s1 = "Hello";
  const auto s2 = "olleH";
  const auto s3 = "Holaa";

  auto const t1 = CheckPermutation(s1, s2, strlen(s1), strlen(s2));
  auto const t2 = CheckPermutation(s1, s3, strlen(s1), strlen(s3));
  CHECK(t1);
  CHECK_FALSE(t2);

}

TEST(ChapterOne, SubArraySum){
  // Not actually in CTCI but is related to arrays

  // Prompt: Given an array, find the sum of all subarrays of length K
  // (fixed sliding window)
  int a1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  CHECK_EQUAL(27, sliding_window_max_sum(a1, 11, 3));

  // Prompt: Find the shortest subarray with a sum greater than or
  // equal to X (dynamic sliding window)
  int a2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
  CHECK_EQUAL(1, sliding_window_shortest_subarray(a2, 9, 7));
}

// Chapter 2: Linked Lists ___________________________________________

TEST_GROUP(ChapterTwo){};
TEST(ChapterTwo, RemoveDups){
  auto dll = new DopeLinkedList();
  dll->AppendData(1);
  dll->AppendData(2);
  dll->AppendData(2);
  dll->AppendData(3);

  remove_dups(dll);
  auto node = dll->GetHead();

  CHECK_EQUAL(1, node->GetData());
  node = node->GetNext();
  CHECK_EQUAL(2, node->GetData());
  node = node->GetNext();
  CHECK_EQUAL(3, node->GetData());
  delete dll;
}

TEST(ChapterTwo, Reverse){
  auto dll = new DopeLinkedList();
  dll->AppendData(1);
  dll->AppendData(2);
  dll->AppendData(3);
  dll->AppendData(100);

  auto node = dll->GetHead();
  CHECK_EQUAL(1, node->GetData());
  reverse_linkedlist(dll);
  node = dll->GetHead();
  CHECK_EQUAL(100, node->GetData());
  node = node->GetNext();
  CHECK_EQUAL(3, node->GetData());
  node = node->GetNext();
  CHECK_EQUAL(2, node->GetData());
  node = node->GetNext();
  CHECK_EQUAL(1, node->GetData());
  CHECK_EQUAL(nullptr, node->GetNext());

  delete dll;
}

// Chapter 3: Stacks and Queues ______________________________________

TEST_GROUP(ChapterThree){};
TEST(ChapterThree, StackMin){
  auto stack = new DopeStack<int, 20>();
  stack->push(10);
  stack->push(25);
  stack->push(42);
  stack->push(100);
  stack->push(2);

  CHECK_EQUAL(2, stack->peek());
  CHECK_EQUAL(2, stack->pop());
  CHECK_EQUAL(100, stack->pop());
  CHECK_FALSE(stack->isEmpty());
  (void)stack->pop();
  (void)stack->pop();
  (void)stack->pop();
  CHECK_TRUE(stack->isEmpty());
  delete stack;
}

// Chapter 4: Trees __________________________________________________
TEST_GROUP(ChapterFour){};
TEST(ChapterFour, BinaryTrees){
  auto btree = DopeBinTree<int>();
  btree.insert(1);
  btree.insert(2);
  btree.insert(3);
  btree.insert(4);
  btree.insert(5);
  btree.insert(6);
  btree.insert(7);
  btree.insert(8);


  auto root = btree.getRoot();
  CHECK_EQUAL(1, root->GetData());
  CHECK_EQUAL(2, root->GetLeft()->GetData());
  CHECK_EQUAL(3, root->GetRight()->GetData());
  CHECK_EQUAL(4, root->GetLeft()->GetLeft()->GetData());
  CHECK_EQUAL(5, root->GetLeft()->GetRight()->GetData());
  CHECK_EQUAL(6, root->GetRight()->GetLeft()->GetData());
  CHECK_EQUAL(7, root->GetRight()->GetRight()->GetData());
  CHECK_EQUAL(8, root->GetLeft()->GetLeft()->GetLeft()->GetData());

}

TEST(ChapterFour, TreeTraversal){
  auto btree = DopeBinTree<int>();
  btree.insert(1); // Root
  btree.insert(2);
  btree.insert(3);
  btree.insert(4);
  btree.insert(5);
  btree.insert(6);
  btree.insert(7);

  int array[10] = {};

  btree.PreOrderTraversal2Array(array, AlgoVariant::Recursive);
  CHECK_EQUAL(1, array[0]);
  CHECK_EQUAL(2, array[1]);
  CHECK_EQUAL(4, array[2]);
  CHECK_EQUAL(5, array[3]);
  CHECK_EQUAL(3, array[4]);
  CHECK_EQUAL(6, array[5]);
  CHECK_EQUAL(7, array[6]);

  std::fill(array, array+10, 0);

  btree.InOrderTraversal2Array(array, AlgoVariant::Recursive);
  CHECK_EQUAL(4, array[0]);
  CHECK_EQUAL(2, array[1]);
  CHECK_EQUAL(5, array[2]);
  CHECK_EQUAL(1, array[3]);
  CHECK_EQUAL(6, array[4]);
  CHECK_EQUAL(3, array[5]);
  CHECK_EQUAL(7, array[6]);

  std::fill(array, array+10, 0);

  btree.PostOrderTraversal2Array(array, AlgoVariant::Recursive);
  CHECK_EQUAL(4, array[0]);
  CHECK_EQUAL(5, array[1]);
  CHECK_EQUAL(2, array[2]);
  CHECK_EQUAL(6, array[3]);
  CHECK_EQUAL(7, array[4]);
  CHECK_EQUAL(3, array[5]);
  CHECK_EQUAL(1, array[6]);

  std::fill(array, array+10, 0);

  btree.PreOrderTraversal2Array(array, AlgoVariant::Iter);
  CHECK_EQUAL(1, array[0]);
  CHECK_EQUAL(2, array[1]);
  CHECK_EQUAL(4, array[2]);
  CHECK_EQUAL(5, array[3]);
  CHECK_EQUAL(3, array[4]);
  CHECK_EQUAL(6, array[5]);
  CHECK_EQUAL(7, array[6]);

  std::fill(array, array+10, 0);

  btree.InOrderTraversal2Array(array, AlgoVariant::Iter);
  CHECK_EQUAL(4, array[0]);
  CHECK_EQUAL(2, array[1]);
  CHECK_EQUAL(5, array[2]);
  CHECK_EQUAL(1, array[3]);
  CHECK_EQUAL(6, array[4]);
  CHECK_EQUAL(3, array[5]);
  CHECK_EQUAL(7, array[6]);

  std::fill(array, array+10, 0);

  btree.PostOrderTraversal2Array(array, AlgoVariant::Iter);
  CHECK_EQUAL(4, array[0]);
  CHECK_EQUAL(5, array[1]);
  CHECK_EQUAL(2, array[2]);
  CHECK_EQUAL(6, array[3]);
  CHECK_EQUAL(7, array[4]);
  CHECK_EQUAL(3, array[5]);
  CHECK_EQUAL(1, array[6]);

}

TEST(ChapterFour, MinHeap){
  auto btree = DopeBinTree<int>();


}

// Chapter 12: C/C++ _________________________________________________

TEST_GROUP(ChapterTwelve){};
TEST(ChapterTwelve, ReverseString){
  char s1[] = "Hello";
  reverse_str(s1);
  STRCMP_EQUAL("olleH", s1);
}

int main (int ac, char** av){
  return CommandLineTestRunner::RunAllTests(ac, av);
}