cpp-trie/trie.t.h

//
//  trie.t.h
//  trie
//
//  Created by Sam Jaffe on 6/16/17.
//

#pragma once

#include <cxxtest/TestSuite.h>

#include "trie.hpp"

class trie_TestSuite : public CxxTest::TestSuite {
private:
  trie<int, int> data;
  
  void setUp() override {
    data.clear();
    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;
  }
  
  template <typename Iter, typename R>
  static void container_equals(Iter l_it, R const & rhs) {
    decltype(l_it) l_end{};
    auto r_it = std::begin(rhs), r_end = std::end(rhs);
    auto l_size = std::distance(l_it, l_end), r_size = std::distance(r_it, r_end);
    TS_ASSERT_EQUALS(l_size, r_size);
    for ( ; l_it != l_end && r_it != r_end; ++l_it, ++r_it ) {
      TS_ASSERT_EQUALS(*l_it, *r_it);
    }
  }
public:
  // Parent, Left -> Right
  void testIterationIsPreOrder() {
    int const expected[] = { 1, 5, 4, 3, 6, 0, 7, 2, 8, 9 };
    container_equals(data.begin(), expected);
  }
  
  // Parent, Right -> Left
  void testPostIterationIsPostOrder() {
    int const expected[] = { 1, 2, 8, 9, 5, 0, 7, 4, 6, 3 };
    auto it = trie<int, int>::const_post_iterator{&data};
    container_equals(it, expected);
  }

  // Right -> Left, Parent
  void testReverseIterationIsInvDepthFirst() {
    int const expected[] = { 9, 8, 2, 7, 0, 6, 3, 4, 5, 1 };
    container_equals(data.crbegin(), expected);
  }

  void testCopyCtorIsDeepCopy() {
    trie<int, int> copy{data};
    TS_ASSERT_EQUALS(data, copy);
    copy[{0, 1}] = -1;
    TS_ASSERT_DIFFERS(data, copy);
  }
  
  void testEqualsConsidersPaths() {
    trie<int, int> t1, t2;
    t1[1] = 1;
    t2[2] = 1;
    TS_ASSERT_DIFFERS(t1, t2);
  }
  
  void testInsertNewElementOutputsTrue() {
    trie<int, int> test;
    auto pair = test.insert(1, 2);
    TS_ASSERT_EQUALS(*pair.first, 2);
    TS_ASSERT(pair.second);
  }

  void testEmplaceNewElementOutputsTrue() {
    trie<int, int> test;
    auto pair = test.emplace(1, 2);
    TS_ASSERT_EQUALS(*pair.first, 2);
    TS_ASSERT(pair.second);
  }

  void testInsertArrayOfElementCreatesAllEntries() {
    trie<int, int> test;
    auto pair = test.insert({1, 1, 1}, 2);
    TS_ASSERT_EQUALS(*pair.first, 2);
    TS_ASSERT(pair.second);
    TS_ASSERT_EQUALS(test[1][1][1].value(), 2);
  }

  void testInsertNotDestructive() {
    trie<int, int> test;
    auto pair = test.insert(1, 2);
    pair = test.insert(1, 0);
    TS_ASSERT_EQUALS(*pair.first, 2);
    TS_ASSERT(!pair.second);
  }
  
  void testCanLocateElement() {
    TS_ASSERT_EQUALS(*data.find({0, 1, 2}), 6);
  }

  void testFindAbsentElementReturnsEnd() {
    TS_ASSERT_EQUALS(data.find({0, 3, 2}), data.end());
  }
  
  void testEraseDropsEntireBranch() {
    data.erase(0);
    TS_ASSERT_EQUALS(data.find(0), data.end());
  }
};