test for task domens

#include "test_runner.h"
#include "profile.h"

#include <algorithm>
#include <iostream>
#include <optional>
#include <string>
#include <string_view>
#include <vector>

using namespace std;

template <typename It>
class Range {
public:
  Range(It begin, It end) : begin_(begin), end_(end) {}
  It begin() const { return begin_; }
  It end() const { return end_; }

private:
  It begin_;
  It end_;
};

pair<string_view, optional<string_view>> SplitTwoStrict(string_view s, string_view delimiter = " ") {
  const size_t pos = s.find(delimiter);
  if (pos == s.npos) {
    return {s, nullopt};
  } else {
    return {s.substr(0, pos), s.substr(pos + delimiter.length())};
  }
}

vector<string_view> Split(string_view s, string_view delimiter = " ") {
  vector<string_view> parts;
  if (s.empty()) {
    return parts;
  }
  while (true) {
    const auto [lhs, rhs_opt] = SplitTwoStrict(s, delimiter);
    parts.push_back(lhs);
    if (!rhs_opt) {
      break;
    }
    s = *rhs_opt;
  }
  return parts;
}


class Domain {
public:
  explicit Domain(string_view text) {
    vector<string_view> parts = Split(text, ".");
    parts_reversed_.assign(rbegin(parts), rend(parts));
  }

  size_t GetPartCount() const {
    return parts_reversed_.size();
  }

  auto GetParts() const {
    return Range(rbegin(parts_reversed_), rend(parts_reversed_));
  }
  auto GetReversedParts() const {
    return Range(begin(parts_reversed_), end(parts_reversed_));
  }

  bool operator==(const Domain& other) const {
    return parts_reversed_ == other.parts_reversed_;
  }

private:
  vector<string> parts_reversed_;
};

ostream& operator<<(ostream& stream, const Domain& domain) {
  bool first = true;
  for (const string_view part : domain.GetParts()) {
    if (!first) {
      stream << '.';
    } else {
      first = false;
    }
    stream << part;
  }
  return stream;
}

// domain is subdomain of itself
bool IsSubdomain(const Domain& subdomain, const Domain& domain) {
  const auto subdomain_reversed_parts = subdomain.GetReversedParts();
  const auto domain_reversed_parts = domain.GetReversedParts();
  return
      subdomain.GetPartCount() >= domain.GetPartCount()
      && equal(begin(domain_reversed_parts), end(domain_reversed_parts),
               begin(subdomain_reversed_parts));
}

bool IsSubOrSuperDomain(const Domain& lhs, const Domain& rhs) {
  return lhs.GetPartCount() >= rhs.GetPartCount()
         ? IsSubdomain(lhs, rhs)
         : IsSubdomain(rhs, lhs);
}


class DomainChecker {
public:
  template <typename InputIt>
  DomainChecker(InputIt domains_begin, InputIt domains_end) {
    sorted_domains_.reserve(distance(domains_begin, domains_end));
    for (const Domain& domain : Range(domains_begin, domains_end)) {
      sorted_domains_.push_back(&domain);
    }
    sort(begin(sorted_domains_), end(sorted_domains_), IsDomainLess);
    sorted_domains_ = AbsorbSubdomains(move(sorted_domains_));
  }

  // Check if candidate is subdomain of some domain
  bool IsSubdomain(const Domain& candidate) const {
    const auto it = upper_bound(
        begin(sorted_domains_), end(sorted_domains_),
        &candidate, IsDomainLess);
    if (it == begin(sorted_domains_)) {
      return false;
    }
    return ::IsSubdomain(candidate, **prev(it));
  }

private:
  vector<const Domain*> sorted_domains_;

  static bool IsDomainLess(const Domain* lhs, const Domain* rhs) {
    const auto lhs_reversed_parts = lhs->GetReversedParts();
    const auto rhs_reversed_parts = rhs->GetReversedParts();
    return lexicographical_compare(
      begin(lhs_reversed_parts), end(lhs_reversed_parts),
      begin(rhs_reversed_parts), end(rhs_reversed_parts)
    );
  }

  static vector<const Domain*> AbsorbSubdomains(vector<const Domain*> domains) {
    domains.erase(
        unique(begin(domains), end(domains),
               [](const Domain* lhs, const Domain* rhs) {
                 return IsSubOrSuperDomain(*lhs, *rhs);
               }),
        end(domains)
    );
    return domains;
  }
};


vector<Domain> ReadDomains(istream& in_stream = cin) {
  vector<Domain> domains;

  size_t count;
  in_stream >> count;
  domains.reserve(count);

  for (size_t i = 0; i < count; ++i) {
    string domain_text;
    in_stream >> domain_text;
    domains.emplace_back(domain_text);
  }
  return domains;
}

vector<bool> CheckDomains(const vector<Domain>& banned_domains, const vector<Domain>& domains_to_check) {
  const DomainChecker checker(begin(banned_domains), end(banned_domains));

  vector<bool> check_results;
  check_results.reserve(domains_to_check.size());
  for (const Domain& domain_to_check : domains_to_check) {
    check_results.push_back(!checker.IsSubdomain(domain_to_check));
  }

  return check_results;
}

void PrintCheckResults(const vector<bool>& check_results, ostream& out_stream = cout) {
  for (const bool check_result : check_results) {
    out_stream << (check_result ? "Good" : "Bad") << "\n";
  }
}

void Test1_parts() {
    Domain d0("ru");
    ASSERT_EQUAL(d0.GetPartCount(), 1)
    vector<string_view> v0{ d0.GetParts().begin(), d0.GetParts().end() };
    ASSERT_EQUAL(v0.size(), 1)
    ASSERT_EQUAL(string(v0[0]), "ru")

    Domain d1("az.bz.cz");
    ASSERT_EQUAL(d1.GetPartCount(), 3)
    vector<string_view> v1{ d1.GetParts().begin(), d1.GetParts().end() };
    ASSERT_EQUAL(v1.size(), 3)
    ASSERT_EQUAL(string(v1[0]), "az")
    ASSERT_EQUAL(string(v1[1]), "bz")
    ASSERT_EQUAL(string(v1[2]), "cz")
}

void Test2_reversed_parts() {
    Domain d0("ru");
    vector<string_view> v0{ d0.GetReversedParts().begin(), d0.GetReversedParts().end() };
    ASSERT_EQUAL(v0.size(), 1)
    ASSERT_EQUAL(string(v0[0]), "ru")

    Domain d1("az.bz.cz");
    vector<string_view> v1{ d1.GetReversedParts().begin(), d1.GetReversedParts().end() };
    ASSERT_EQUAL(string(v1[0]), "cz")
    ASSERT_EQUAL(string(v1[1]), "bz")
    ASSERT_EQUAL(string(v1[2]), "az")
}

void Test3_subdomain_of_itself() {
    Domain d1("com");
    Domain d2("a.b.ru");
    Domain d3("mail.com");
    Domain d4("com.com.com");

    ASSERT(IsSubdomain(d1, d1))
    ASSERT(IsSubdomain(d2, d2))
    ASSERT(IsSubdomain(d3, d3))
    ASSERT(IsSubdomain(d4, d4))
}

void Test4_subdomain_swapped() {
    Domain d1("com");
    Domain d2("mail.com");
    Domain d3("mailcom");
    Domain d4("com.com.com");
    Domain d5("com.mail");

    ASSERT(IsSubdomain(d1, d1))
    ASSERT(IsSubdomain(d2, d1))
    ASSERT(IsSubdomain(d4, d1))
    ASSERT(!IsSubdomain(d1, d2))
    ASSERT(!IsSubdomain(d1, d3))
    ASSERT(!IsSubdomain(d1, d4))
    ASSERT(!IsSubdomain(d2, d3))
    ASSERT(!IsSubdomain(d3, d2))
    ASSERT(!IsSubdomain(d5, d2))
    ASSERT(!IsSubdomain(d2, d5))
}

void Test4b_IsSubOrSuperDomain() {
    Domain d1("ru");
    Domain d2("com");
    Domain d3("mail.com");
    Domain d4("mailcom");

    ASSERT(IsSubOrSuperDomain(d2, d2))
    ASSERT(!IsSubOrSuperDomain(d1, d2))
    ASSERT(!IsSubOrSuperDomain(d2, d1))
    ASSERT(IsSubOrSuperDomain(d3, d2))
    ASSERT(IsSubOrSuperDomain(d2, d3))
    ASSERT(!IsSubOrSuperDomain(d4, d3))
    ASSERT(!IsSubOrSuperDomain(d3, d4))
}

void Test5_DomainChecker_IsSubdomain() {
    vector<Domain> test_banned_domains{ Domain("ru"), Domain("mail.cc") };
    DomainChecker checker(begin(test_banned_domains), end(test_banned_domains));
    ASSERT(checker.IsSubdomain(Domain("mail.ya.ru")))
    ASSERT(!checker.IsSubdomain(Domain("mail.yaru")))
    ASSERT(checker.IsSubdomain(Domain("mail.cc")))
    ASSERT(checker.IsSubdomain(Domain("ys.mail.cc")))
    ASSERT(!checker.IsSubdomain(Domain("ysmail.cc")))
    ASSERT(!checker.IsSubdomain(Domain("ma.il.cc")))
    ASSERT(!checker.IsSubdomain(Domain("mailcc")))
    ASSERT(!checker.IsSubdomain(Domain("ru.cc")))
    ASSERT(!checker.IsSubdomain(Domain("cc.mail")))
    ASSERT(!checker.IsSubdomain(Domain("cc.liam")))
    ASSERT(!checker.IsSubdomain(Domain("ru.mail")))
    ASSERT(!checker.IsSubdomain(Domain("ru.cc")))
}

void Test6_check_domains() {
    vector<bool> results1 = CheckDomains(
        {Domain("ru"), Domain("ya.ru"), Domain("com"), Domain("mail.cc"), Domain("ru.su")},
        { Domain("me"), Domain("mail.yaru"), Domain("com"), Domain("mailyaru"), Domain("com.com") });
    vector<bool> expected1{ true, true, false, true, false };
    ASSERT_EQUAL(results1, expected1)


    vector<bool> results2 = CheckDomains(
        { Domain("ya.ya"), Domain("ya.ru"), Domain("ya.com") },
        { Domain("haya.ya"), Domain("teya.ru"), Domain("suya.com"), Domain("ha.ya.ya"), Domain("te.ya.ru"), Domain("su.ya.com") });
    vector<bool> expected2{ true, true, true, false, false, false };
    ASSERT_EQUAL(results2, expected2)


    vector<bool> results3 = CheckDomains(
        { Domain("ya.ru"), Domain("maps.me"), Domain("m.ya.ru"), Domain("com")},
        { Domain("ya.ru"), Domain("ya.com"), Domain("m.maps.me"), Domain("moscow.m.ya.ru"), Domain("maps.com"), Domain("maps.ru"), Domain("ya.ya") });
    vector<bool> expected3{ false, false, false, false, false, true, true };
    ASSERT_EQUAL(results3, expected3)


    vector<bool> results4 = CheckDomains(
        {},
        { Domain("ya.ru"), Domain("ya.com"), Domain("m.maps.me"), Domain("moscow.m.ya.ru"), Domain("maps.com"), Domain("maps.ru"), Domain("ya.ya") });
    vector<bool> expected4{ true, true, true, true, true, true, true };
    ASSERT_EQUAL(results4, expected4)
}

void Test7_print_check_results() {
    stringstream ss;
    PrintCheckResults({ true, false }, ss);
    string s1, s2;
    ss >> s1 >> s2;
    ASSERT_EQUAL(s1, "Good");
    ASSERT_EQUAL(s2, "Bad");
}

void Test8_read_domains() {
    stringstream ss;
    ss << "7\n" << "am\n" << "bm.am\n" << "cm.bm.am\n" << "dm.cm.bm.am\n" << "em.dm.cm.bm.am\n" << "am.am\n" << "am.am.am\n";
    vector<Domain> domains = ReadDomains(ss);
    ASSERT_EQUAL(domains.size(), 7);
    ASSERT_EQUAL(domains[0], Domain("am"));
    ASSERT_EQUAL(domains[1], Domain("bm.am"));
    ASSERT_EQUAL(domains[2], Domain("cm.bm.am"));
    ASSERT_EQUAL(domains[3], Domain("dm.cm.bm.am"));
    ASSERT_EQUAL(domains[4], Domain("em.dm.cm.bm.am"));
    ASSERT_EQUAL(domains[5], Domain("am.am"));
    ASSERT_EQUAL(domains[6], Domain("am.am.am"));

    ss.clear();
    ss << "0\n";
    domains = ReadDomains(ss);
    ASSERT_EQUAL(domains.size(), 0);

    ss.clear();
    ss << "1\n" << "am.am.am\n";
    domains = ReadDomains(ss);
    ASSERT_EQUAL(domains.size(), 1);
    ASSERT_EQUAL(domains[0], Domain("am.am.am"));
}

void Test9_full() {
    stringstream ss_in, ss_out;

    ss_in << "4\n";
    ss_in << "ya.ru\n" << "maps.me\n" << "m.ya.ru\n" << "com\n";
    ss_in << "7\n";
    ss_in << "ya.ru\n" << "ya.com\n" << "m.maps.me\n" << "moscow.m.ya.ru\n" << "maps.com\n" << "maps.ru\n" << "ya.ya\n";

    const vector<Domain> banned_domains = ReadDomains(ss_in);
    const vector<Domain> domains_to_check = ReadDomains(ss_in);
    PrintCheckResults(CheckDomains(banned_domains, domains_to_check), ss_out);
    ASSERT_EQUAL(ss_out.str(), "Bad\nBad\nBad\nBad\nBad\nGood\nGood\n");


    stringstream ss_in2, ss_out2;

    ss_in2 << "3\n";
    ss_in2 << "ya.ya\n" << "ya.ru\n" << "ya.com\n";
    ss_in2 << "7\n";
    ss_in2 << "ha.ya.ya\n" << "te.ya.ru\n" << "su.ya.com\n" << "haya.ya\n" << "teya.ru\n" << "suya.com\n" << "ya.ya.net\n";

    const vector<Domain> banned_domains2 = ReadDomains(ss_in2);
    const vector<Domain> domains_to_check2 = ReadDomains(ss_in2);
    PrintCheckResults(CheckDomains(banned_domains2, domains_to_check2), ss_out2);
    ASSERT_EQUAL(ss_out2.str(), "Bad\nBad\nBad\nGood\nGood\nGood\nGood\n");
}

void TestSimple() {
    // Your tests here
    Test1_parts();
    Test2_reversed_parts();
    Test3_subdomain_of_itself();
    Test4_subdomain_swapped();
    Test4b_IsSubOrSuperDomain();
    Test5_DomainChecker_IsSubdomain();
    Test6_check_domains();
    Test7_print_check_results();
    Test8_read_domains();
    Test9_full();
 }

int main() {
    TestRunner tr;
    RUN_TEST(tr, TestSimple);

    const vector<Domain> banned_domains = ReadDomains();
    const vector<Domain> domains_to_check = ReadDomains();
    PrintCheckResults(CheckDomains(banned_domains, domains_to_check));
    return 0;
}