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::Ne(data));
}

/**
 * This is important because a trie is implemented as a
 * map<key_type, self_type*>. Therefore, a naive copy-ctor would result in the
 * copy having the same data after the first level (root value and inserts with
 * one key wouldn't backflow, but everything else would).
 */
TEST_F(TrieTest, CopyConstructorIsDeep) {
  trie<int, int> copy = data;
  copy[{0, 1}] += 1;
  EXPECT_THAT(copy, ::testing::Ne(data));
}

/**
 * Ensure that copy-assign doesn't simply add-all.
 */
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::Ne(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>({3, 6, 4, 7, 0, 5, 9, 8, 2, 1}));
}

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.find({1}), testing::Ne(example.end()));
  EXPECT_THAT(example.find({1, 1}), testing::Ne(example.end()));
  EXPECT_THAT(example.find({1, 1, 1}), rval.first);
}

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::Ne(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);
}