Tests for Shortest Non-Shared Substring task

5_non_shared_substring_test.cpp

#include "catch.hpp"

#include <memory>
#include <random>
#include <unordered_set>

#include "non-shared-substring.h"

using std::string;
using std::unordered_set;

namespace {
class RandomStrGen {
 public:
  RandomStrGen() : gen_(new std::mt19937(std::random_device{}())) {}

  string Generate(const string &alphabet, size_t len) {
    string res;
    res.reserve(len);

    std::uniform_int_distribution<int> dis(
        0, static_cast<int>(alphabet.size() - 1));

    for (size_t i = 0; i < len; ++i) {
      res += alphabet[dis(*gen_)];
    }

    return res;
  }

 private:
  std::unique_ptr<std::mt19937> gen_;
};
}  // anonymous namespace

static void FillWithSubstrings(const string &str,
                               unordered_set<string> *const set) {
  for (size_t i = 0, len = str.size(); i < len; ++i) {
    for (size_t sub_len = 1; sub_len <= len - i; ++sub_len) {
      set->insert(str.substr(i, sub_len));
    }
  }
}

static string ChooseMinNonShared(const unordered_set<string> &set1,
                                 const unordered_set<string> &set2) {
  string res;
  for (const string &substr : set1) {
    const bool is_shared = set2.count(substr) != 0;
    if (!is_shared && (res.empty() || substr.size() < res.size())) {
      res = substr;
    }
  }

  return res;
}

static void TestGetMinNonSharedSubstring(const string &str1,
                                         const string &str2) {
  const auto received = GetMinNonSharedSubstring(str1, str2);

  unordered_set<string> set1, set2;
  FillWithSubstrings(str1, &set1);
  FillWithSubstrings(str2, &set2);

  const string expected = ChooseMinNonShared(set1, set2);

  const bool is_correct = received.size() == expected.size() &&
                          set1.count(received) != 0 &&
                          set2.count(received) == 0;
  CAPTURE(str1);
  CAPTURE(str2);
  CAPTURE(received);
  CAPTURE(expected);
  REQUIRE(is_correct);
}

static void TestGetMinNonSharedSubstringAgainstRandom(size_t str_size,
                                                      size_t iterations_num) {
  static const string ALPHABET = "ATGC";

  RandomStrGen str_gen;
  size_t i = 0;
  while (i < iterations_num) {
    const auto str1 = str_gen.Generate(ALPHABET, str_size);
    const auto str2 = str_gen.Generate(ALPHABET, str_size);
    if (str1 != str2) {
      ++i;
      TestGetMinNonSharedSubstring(str1, str2);
    }
  }
}

TEST_CASE("non_shared_substring") {
  SECTION("1") { TestGetMinNonSharedSubstring("A", "T"); }
  SECTION("2") {
    TestGetMinNonSharedSubstring("AAAAAAAAAAAAAAAAAAAA",
                                 "TTTTTTTTTTTTTTTTTTTT");
  }
  SECTION("3") {
    TestGetMinNonSharedSubstring("CCAAGCTGCTAGAGG", "CATGCTGGGCTGGCT");
  }
  SECTION("4") {
    TestGetMinNonSharedSubstring("ATGCGATGACCTGACTGA", "CTCAACGTATTGGCCAGA");
  }
  SECTION("Random(5,500)") {
    TestGetMinNonSharedSubstringAgainstRandom(5, 500);
  }
  SECTION("Random(10,200)") {
    TestGetMinNonSharedSubstringAgainstRandom(10, 200);
  }
  SECTION("Random(20,100)") {
    TestGetMinNonSharedSubstringAgainstRandom(20, 100);
  }
  SECTION("Random(30,100)") {
    TestGetMinNonSharedSubstringAgainstRandom(30, 100);
  }
}