cpp-trie/test/trie_test.cxx

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

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

#include "trie/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,
      {{0,
        {5,
         {{1, {4, {{0, {3, {}}}, {2, {6, {}}}}}}, {2, {0, {{0, {7, {}}}}}}}}},
       {1, {2, {{1, {8, {{0, {9, {}}}}}}}}}}};
}

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

template <typename Iter> std::vector<int> flatten(Iter it, Iter const & 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(), empty.cend()), std::vector<int>{0});
}

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

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.insert({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, EmplacingWithPathWillCreateParents) {
  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, CanInsertWithAnyIterablePath) {
  trie<int, int> example;
  std::pair<trie<int, int>::iterator, bool> rval =
      example.insert(std::vector<int>{1, 1, 1}, 2);
  EXPECT_TRUE(rval.second);
  EXPECT_THAT(*rval.first, 2);
  EXPECT_THAT(example.find({1, 1, 1}), rval.first);
}

TEST_F(TrieTest, CanEmplaceWithAnyIterablePath) {
  trie<int, int> example;
  std::pair<trie<int, int>::iterator, bool> rval =
      example.emplace(std::vector<int>{1, 1, 1}, 2);
  EXPECT_TRUE(rval.second);
  EXPECT_THAT(*rval.first, 2);
  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);
  trie<int, int> const & cref = data;
  EXPECT_THAT(*cref.find({0, 1, 2}), 6);
}

TEST_F(TrieTest, FindMissingPathWillReturnEnd) {
  EXPECT_THAT(data.find({0, 3, 2}), data.end());
  trie<int, int> const & cref = data;
  EXPECT_THAT(cref.find({0, 3, 2}), cref.end());
}

TEST_F(TrieTest, SingleElementPathFindsSameAsKeyFind) {
  EXPECT_THAT(data.find({0}), data.find(0));
  EXPECT_THAT(data.find(std::vector<int>{0}), data.find(0));
  trie<int, int> const & cref = data;
  EXPECT_THAT(cref.find({0}), cref.find(0));
  EXPECT_THAT(cref.find(std::vector<int>{0}), cref.find(0));
}

TEST_F(TrieTest, MoveAssignmentOverwritesAndRelocates) {
  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.begin(), t1.end()), flatten(t2.begin(), t2.end()));
  EXPECT_THAT(t1, ::testing::Ne(t2));
}

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

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, CanEraseAtPath) {
  EXPECT_THAT(data.find({0, 1}), ::testing::Ne(data.end()));
  data.erase({0, 1});
  EXPECT_THAT(data.find({0, 1}), data.end());
  EXPECT_THAT(data.find(0), ::testing::Ne(data.end()));
}

TEST_F(TrieTest, CanEraseAtAnyIterablePath) {
  EXPECT_THAT(data.find({0, 1}), ::testing::Ne(data.end()));
  data.erase(std::vector<int>{0, 1});
  EXPECT_THAT(data.find({0, 1}), data.end());
  EXPECT_THAT(data.find(0), ::testing::Ne(data.end()));
}

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