cpp-trie/trie_test.cpp

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

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

#include "trie.hpp"

using Tree = trie<int, int>;

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

  Tree 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) {
  Tree empty;
  EXPECT_THAT(flatten(empty.cbegin()), std::vector<int>{0});
}

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

TEST_F(TrieTest, MoveAssignmentOverwritesAnfRelocates) {
  Tree 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) {
  Tree copy = data;
  copy[{0, 1}] += 1;
  EXPECT_THAT(copy, ::testing::Not(::testing::Eq(data)));
}

TEST_F(TrieTest, CopyAssignmentOverwritesData) {
  Tree value;
  value[2] = 1;
  value = data;
  EXPECT_THAT(value, data);
}

TEST_F(TrieTest, EqualityIsPathSensitive) {
  Tree 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(Tree::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) {
  Tree example;
  std::pair<Tree::iterator, bool> rval = example.insert(1, 2);
  EXPECT_TRUE(rval.second);
  EXPECT_THAT(*rval.first, 2);
}

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

TEST_F(TrieTest, InsertingWithPathWillCreateParents) {
  Tree example;
  std::pair<Tree::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) {
  Tree example;
  example.insert(1, 2);
  std::pair<Tree::iterator, bool> rval = example.insert(1, 0);
  EXPECT_FALSE(rval.second);
  EXPECT_THAT(*rval.first, ::testing::Not(0));
}

TEST_F(TrieTest, EmplacingInAlreadyExistantPathNonDestructive) {
  Tree example;
  example.insert(1, 2);
  std::pair<Tree::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) {
  Tree copy = data;
  copy.erase(-1);
  EXPECT_THAT(copy, data);
}