cpp-trie/trie_test.cpp

//
//  trie_test.cpp
//  trie
//
//  Created by Sam Jaffe on 6/2/18.
//

#include <gmock/gmock.h>
#include <gtest/gtest.h>

#include "trie.hpp"

class TrieTest : public ::testing::Test {
protected:
  virtual void SetUp() override;
  virtual void TearDown() override;

  trie<int, int> data;
};

void TrieTest::SetUp() {
  data = 1;
  data[0] = 5;
  data[{0, 1}] = 4;
  data[{0, 1, 0}] = 3;
  data[{0, 1, 2}] = 6;
  data[{0, 2, 0}] = 7;
  data[1] = 2;
  data[{1, 1}] = 8;
  data[{1, 1, 0}] = 9;
}

void TrieTest::TearDown() { data.clear(); }

template <typename Iter> std::vector<int> flatten(Iter it) {
  decltype(it) end{};
  std::vector<int> out;
  out.reserve(size_t(std::distance(it, end)));
  std::copy(it, end, std::back_inserter(out));
  return out;
}

TEST_F(TrieTest, DefaultConstructorHasNoElementsExceptRoot) {
  trie<int, int> empty;
  EXPECT_THAT(flatten(empty.cbegin()), std::vector<int>{0});
}

TEST_F(TrieTest, MoveConstructorIsDestructive) {
  trie<int, int> moved = std::move(data);
  EXPECT_THAT(flatten(data.cbegin()), std::vector<int>{0});
}

TEST_F(TrieTest, MoveAssignmentOverwritesAnfRelocates) {
  trie<int, int> value;
  value[2] = 1;
  value = std::move(data);
  EXPECT_THAT(value.find(2), value.end());
  EXPECT_THAT(value, ::testing::Not(data));
}

TEST_F(TrieTest, CopyConstructorIsDeep) {
  trie<int, int> copy = data;
  copy[{0, 1}] += 1;
  EXPECT_THAT(copy, ::testing::Not(::testing::Eq(data)));
}

TEST_F(TrieTest, CopyAssignmentOverwritesData) {
  trie<int, int> value;
  value[2] = 1;
  value = data;
  EXPECT_THAT(value, data);
}

TEST_F(TrieTest, EqualityIsPathSensitive) {
  trie<int, int> t1, t2;
  t1[1] = 1;
  t2[2] = 1;
  EXPECT_THAT(flatten(t1.cbegin()), flatten(t2.cbegin()));
  EXPECT_THAT(t1, ::testing::Not(::testing::Eq(t2)));
}

TEST_F(TrieTest, NormalIterationIsPreOrdered) {
  EXPECT_THAT(flatten(data.cbegin()),
              std::vector<int>({1, 5, 4, 3, 6, 0, 7, 2, 8, 9}));
}

TEST_F(TrieTest, PostIteratorUsesPostOrder) {
  EXPECT_THAT(flatten(trie<int, int>::const_post_iterator(&data)),
              std::vector<int>({1, 2, 8, 9, 5, 0, 7, 4, 6, 3}));
}

TEST_F(TrieTest, ReverseIterationIsBackwardsPreOrdered) {
  EXPECT_THAT(flatten(data.crbegin()),
              std::vector<int>({9, 8, 2, 7, 0, 6, 3, 4, 5, 1}));
}

TEST_F(TrieTest, InsertingNewElementReturnsSuccess) {
  trie<int, int> example;
  std::pair<trie<int, int>::iterator, bool> rval = example.insert(1, 2);
  EXPECT_TRUE(rval.second);
  EXPECT_THAT(*rval.first, 2);
}

TEST_F(TrieTest, EmplacingNewElementReturnsSuccess) {
  trie<int, int> example;
  std::pair<trie<int, int>::iterator, bool> rval = example.emplace(1, 2);
  EXPECT_TRUE(rval.second);
  EXPECT_THAT(*rval.first, 2);
}

TEST_F(TrieTest, InsertingWithPathWillCreateParents) {
  trie<int, int> example;
  std::pair<trie<int, int>::iterator, bool> rval =
      example.emplace({1, 1, 1}, 2);
  EXPECT_TRUE(rval.second);
  EXPECT_THAT(*rval.first, 2);
  EXPECT_THAT(example[1][1][1].value(), 2);
}

TEST_F(TrieTest, InsertingInAlreadyExistantPathNonDestructive) {
  trie<int, int> example;
  example.insert(1, 2);
  std::pair<trie<int, int>::iterator, bool> rval = example.insert(1, 0);
  EXPECT_FALSE(rval.second);
  EXPECT_THAT(*rval.first, ::testing::Not(0));
}

TEST_F(TrieTest, EmplacingInAlreadyExistantPathNonDestructive) {
  trie<int, int> example;
  example.insert(1, 2);
  std::pair<trie<int, int>::iterator, bool> rval = example.emplace(1, 0);
  EXPECT_FALSE(rval.second);
  EXPECT_THAT(*rval.first, ::testing::Not(0));
}

TEST_F(TrieTest, FindWithPathWillReturnIteratorToEntry) {
  EXPECT_THAT(*data.find({0, 1, 2}), 6);
}

TEST_F(TrieTest, FindMissingPathWillReturnEnd) {
  EXPECT_THAT(data.find({0, 3, 2}), data.end());
}

TEST_F(TrieTest, DereferenceWithMissingPathThrows) {
  EXPECT_THROW(*data.find({0, 3, 2}), std::runtime_error);
}

TEST_F(TrieTest, EraseDropsWholeBranch) {
  EXPECT_THAT(data.find({0, 1}), ::testing::Not(data.end()));
  data.erase(0);
  EXPECT_THAT(data.find({0, 1}), data.end());
  EXPECT_THAT(data.find(0), data.end());
}

TEST_F(TrieTest, EraseNonExistentElementIsNoOp) {
  trie<int, int> copy = data;
  copy.erase(-1);
  EXPECT_THAT(copy, data);
}