text: #include "set.h"
  
  #include <library/cpp/testing/unittest/registar.h>
  
  #include <utility>
  
  #include <algorithm>
  
  Y_UNIT_TEST_SUITE(YSetTest) {
      Y_UNIT_TEST(TestSet1) {
          TSet<int, TLess<int>> s;
          UNIT_ASSERT(!s);
          UNIT_ASSERT(s.count(42) == 0);
          s.insert(42);
          UNIT_ASSERT(s);
          UNIT_ASSERT(s.count(42) == 1);
          s.insert(42);
          UNIT_ASSERT(s.count(42) == 1);
          size_t count = s.erase(42);
          UNIT_ASSERT(count == 1);
      }
  
      Y_UNIT_TEST(TestSet2) {
          using int_set = TSet<int, TLess<int>>;
          int_set s;
          std::pair<int_set::iterator, bool> p = s.insert(42);
          UNIT_ASSERT(p.second == true);
          p = s.insert(42);
          UNIT_ASSERT(p.second == false);
  
          int array1[] = {1, 3, 6, 7};
          s.insert(array1, array1 + 4);
          UNIT_ASSERT(distance(s.begin(), s.end()) == 5);
  
          int_set s2;
          s2.swap(s);
          UNIT_ASSERT(distance(s2.begin(), s2.end()) == 5);
          UNIT_ASSERT(distance(s.begin(), s.end()) == 0);
  
          int_set s3;
          s3.swap(s);
          s3.swap(s2);
          UNIT_ASSERT(distance(s.begin(), s.end()) == 0);
          UNIT_ASSERT(distance(s2.begin(), s2.end()) == 0);
          UNIT_ASSERT(distance(s3.begin(), s3.end()) == 5);
      }
  
      Y_UNIT_TEST(TestErase) {
          TSet<int, TLess<int>> s;
          s.insert(1);
          s.erase(s.begin());
          UNIT_ASSERT(s.empty());
  
          size_t nb = s.erase(1);
          UNIT_ASSERT(nb == 0);
      }
  
      Y_UNIT_TEST(TestInsert) {
          TSet<int> s;
          TSet<int>::iterator i = s.insert(s.end(), 0);
          UNIT_ASSERT(*i == 0);
      }
  
      Y_UNIT_TEST(TestFind) {
          TSet<int> s;
  
          UNIT_ASSERT(s.find(0) == s.end());
  
          TSet<int> const& crs = s;
  
          UNIT_ASSERT(crs.find(0) == crs.end());
      }
  
      Y_UNIT_TEST(TestHas) {
          TSet<int> s;
          UNIT_ASSERT(!s.contains(0));
  
          TSet<int> const& crs = s;
          UNIT_ASSERT(!crs.contains(0));
  
          s.insert(1);
          s.insert(42);
          s.insert(100);
          s.insert(2);
  
          UNIT_ASSERT(s.contains(1));
          UNIT_ASSERT(s.contains(2));
          UNIT_ASSERT(s.contains(42));
          UNIT_ASSERT(s.contains(100));
      }
  
      Y_UNIT_TEST(TestBounds) {
          int array1[] = {1, 3, 6, 7};
          TSet<int> s(array1, array1 + sizeof(array1) / sizeof(array1[0]));
          TSet<int> const& crs = s;
  
          TSet<int>::iterator sit;
          TSet<int>::const_iterator scit;
          std::pair<TSet<int>::iterator, TSet<int>::iterator> pit;
          std::pair<TSet<int>::const_iterator, TSet<int>::const_iterator> pcit;
  
          //Check iterator on mutable set
          sit = s.lower_bound(2);
          UNIT_ASSERT(sit != s.end());
          UNIT_ASSERT(*sit == 3);
  
          sit = s.upper_bound(5);
          UNIT_ASSERT(sit != s.end());
          UNIT_ASSERT(*sit == 6);
  
          pit = s.equal_range(6);
          UNIT_ASSERT(pit.first != pit.second);
          UNIT_ASSERT(pit.first != s.end());
          UNIT_ASSERT(*pit.first == 6);
          UNIT_ASSERT(pit.second != s.end());
          UNIT_ASSERT(*pit.second == 7);
  
          pit = s.equal_range(4);
          UNIT_ASSERT(pit.first == pit.second);
          UNIT_ASSERT(pit.first != s.end());
          UNIT_ASSERT(*pit.first == 6);
          UNIT_ASSERT(pit.second != s.end());
          UNIT_ASSERT(*pit.second == 6);
  
          //Check const_iterator on mutable set
          scit = s.lower_bound(2);
          UNIT_ASSERT(scit != s.end());
          UNIT_ASSERT(*scit == 3);
  
          scit = s.upper_bound(5);
          UNIT_ASSERT(scit != s.end());
          UNIT_ASSERT(*scit == 6);
  
          pcit = s.equal_range(6);
          UNIT_ASSERT(pcit.first != pcit.second);
          UNIT_ASSERT(pcit.first != s.end());
          UNIT_ASSERT(*pcit.first == 6);
          UNIT_ASSERT(pcit.second != s.end());
          UNIT_ASSERT(*pcit.second == 7);
  
          //Check const_iterator on const set
          scit = crs.lower_bound(2);
          UNIT_ASSERT(scit != crs.end());
          UNIT_ASSERT(*scit == 3);
  
          scit = crs.upper_bound(5);
          UNIT_ASSERT(scit != crs.end());
          UNIT_ASSERT(*scit == 6);
  
          pcit = crs.equal_range(6);
          UNIT_ASSERT(pcit.first != pcit.second);
          UNIT_ASSERT(pcit.first != crs.end());
          UNIT_ASSERT(*pcit.first == 6);
          UNIT_ASSERT(pcit.second != crs.end());
          UNIT_ASSERT(*pcit.second == 7);
      }
  
      Y_UNIT_TEST(TestImplementationCheck) {
          TSet<int> tree;
          tree.insert(1);
          TSet<int>::iterator it = tree.begin();
          int const& int_ref = *it++;
          UNIT_ASSERT(int_ref == 1);
  
          UNIT_ASSERT(it == tree.end());
          UNIT_ASSERT(it != tree.begin());
  
          TSet<int>::const_iterator cit = tree.begin();
          int const& int_cref = *cit++;
          UNIT_ASSERT(int_cref == 1);
      }
  
      Y_UNIT_TEST(TestReverseIteratorTest) {
          TSet<int> tree;
          tree.insert(1);
          tree.insert(2);
  
          {
              TSet<int>::reverse_iterator rit(tree.rbegin());
              UNIT_ASSERT(*(rit++) == 2);
              UNIT_ASSERT(*(rit++) == 1);
              UNIT_ASSERT(rit == tree.rend());
          }
  
          {
              TSet<int> const& ctree = tree;
              TSet<int>::const_reverse_iterator rit(ctree.rbegin());
              UNIT_ASSERT(*(rit++) == 2);
              UNIT_ASSERT(*(rit++) == 1);
              UNIT_ASSERT(rit == ctree.rend());
          }
      }
  
      Y_UNIT_TEST(TestConstructorsAndAssignments) {
          {
              using container = TSet<int>;
  
              container c1;
              c1.insert(100);
              c1.insert(200);
  
              container c2(c1);
  
              UNIT_ASSERT_VALUES_EQUAL(2, c1.size());
              UNIT_ASSERT_VALUES_EQUAL(2, c2.size());
              UNIT_ASSERT(c1.contains(100));
              UNIT_ASSERT(c2.contains(200));
  
              container c3(std::move(c1));
  
              UNIT_ASSERT_VALUES_EQUAL(0, c1.size());
              UNIT_ASSERT_VALUES_EQUAL(2, c3.size());
              UNIT_ASSERT(c3.contains(100));
  
              c2.insert(300);
              c3 = c2;
  
              UNIT_ASSERT_VALUES_EQUAL(3, c2.size());
              UNIT_ASSERT_VALUES_EQUAL(3, c3.size());
              UNIT_ASSERT(c3.contains(300));
  
              c2.insert(400);
              c3 = std::move(c2);
  
              UNIT_ASSERT_VALUES_EQUAL(0, c2.size());
              UNIT_ASSERT_VALUES_EQUAL(4, c3.size());
              UNIT_ASSERT(c3.contains(400));
          }
  
          {
              using container = TMultiSet<int>;
  
              container c1;
              c1.insert(100);
              c1.insert(200);
  
              container c2(c1);
  
              UNIT_ASSERT_VALUES_EQUAL(2, c1.size());
              UNIT_ASSERT_VALUES_EQUAL(2, c2.size());
              UNIT_ASSERT(c1.find(100) != c1.end());
              UNIT_ASSERT(c2.find(200) != c2.end());
  
              container c3(std::move(c1));
  
              UNIT_ASSERT_VALUES_EQUAL(0, c1.size());
              UNIT_ASSERT_VALUES_EQUAL(2, c3.size());
              UNIT_ASSERT(c3.find(100) != c3.end());
  
              c2.insert(300);
              c3 = c2;
  
              UNIT_ASSERT_VALUES_EQUAL(3, c2.size());
              UNIT_ASSERT_VALUES_EQUAL(3, c3.size());
              UNIT_ASSERT(c3.find(300) != c3.end());
  
              c2.insert(400);
              c3 = std::move(c2);
  
              UNIT_ASSERT_VALUES_EQUAL(0, c2.size());
              UNIT_ASSERT_VALUES_EQUAL(4, c3.size());
              UNIT_ASSERT(c3.find(400) != c3.end());
          }
      }
  
      struct TKey {
          TKey()
              : m_data(0)
          {
          }
  
          explicit TKey(int data)
              : m_data(data)
          {
          }
  
          int m_data;
      };
  
      struct TKeyCmp {
          bool operator()(TKey lhs, TKey rhs) const {
              return lhs.m_data < rhs.m_data;
          }
  
          bool operator()(TKey lhs, int rhs) const {
              return lhs.m_data < rhs;
          }
  
          bool operator()(int lhs, TKey rhs) const {
              return lhs < rhs.m_data;
          }
  
          using is_transparent = void;
      };
  
      struct TKeyCmpPtr {
          bool operator()(TKey const volatile* lhs, TKey const volatile* rhs) const {
              return (*lhs).m_data < (*rhs).m_data;
          }
  
          bool operator()(TKey const volatile* lhs, int rhs) const {
              return (*lhs).m_data < rhs;
          }
  
          bool operator()(int lhs, TKey const volatile* rhs) const {
              return lhs < (*rhs).m_data;
          }
  
          using is_transparent = void;
      };
  
      Y_UNIT_TEST(TestTemplateMethods) {
          {
              using KeySet = TSet<TKey, TKeyCmp>;
              KeySet keySet;
              keySet.insert(TKey(1));
              keySet.insert(TKey(2));
              keySet.insert(TKey(3));
              keySet.insert(TKey(4));
  
              UNIT_ASSERT(keySet.count(TKey(1)) == 1);
              UNIT_ASSERT(keySet.count(1) == 1);
              UNIT_ASSERT(keySet.count(5) == 0);
  
              UNIT_ASSERT(keySet.find(2) != keySet.end());
              UNIT_ASSERT(keySet.lower_bound(2) != keySet.end());
              UNIT_ASSERT(keySet.upper_bound(2) != keySet.end());
              UNIT_ASSERT(keySet.equal_range(2) != std::make_pair(keySet.begin(), keySet.end()));
  
              KeySet const& ckeySet = keySet;
              UNIT_ASSERT(ckeySet.find(2) != ckeySet.end());
              UNIT_ASSERT(ckeySet.lower_bound(2) != ckeySet.end());
              UNIT_ASSERT(ckeySet.upper_bound(2) != ckeySet.end());
              UNIT_ASSERT(ckeySet.equal_range(2) != std::make_pair(ckeySet.begin(), ckeySet.end()));
          }
  
          {
              using KeySet = TSet<TKey*, TKeyCmpPtr>;
              KeySet keySet;
              TKey key1(1), key2(2), key3(3), key4(4);
              keySet.insert(&key1);
              keySet.insert(&key2);
              keySet.insert(&key3);
              keySet.insert(&key4);
  
              UNIT_ASSERT(keySet.count(1) == 1);
              UNIT_ASSERT(keySet.count(5) == 0);
  
              UNIT_ASSERT(keySet.find(2) != keySet.end());
              UNIT_ASSERT(keySet.lower_bound(2) != keySet.end());
              UNIT_ASSERT(keySet.upper_bound(2) != keySet.end());
              UNIT_ASSERT(keySet.equal_range(2) != std::make_pair(keySet.begin(), keySet.end()));
  
              KeySet const& ckeySet = keySet;
              UNIT_ASSERT(ckeySet.find(2) != ckeySet.end());
              UNIT_ASSERT(ckeySet.lower_bound(2) != ckeySet.end());
              UNIT_ASSERT(ckeySet.upper_bound(2) != ckeySet.end());
              UNIT_ASSERT(ckeySet.equal_range(2) != std::make_pair(ckeySet.begin(), ckeySet.end()));
          }
          {
              using KeySet = TMultiSet<TKey, TKeyCmp>;
              KeySet keySet;
              keySet.insert(TKey(1));
              keySet.insert(TKey(2));
              keySet.insert(TKey(3));
              keySet.insert(TKey(4));
  
              UNIT_ASSERT(keySet.count(TKey(1)) == 1);
              UNIT_ASSERT(keySet.count(1) == 1);
              UNIT_ASSERT(keySet.count(5) == 0);
  
              UNIT_ASSERT(keySet.find(2) != keySet.end());
              UNIT_ASSERT(keySet.lower_bound(2) != keySet.end());
              UNIT_ASSERT(keySet.upper_bound(2) != keySet.end());
              UNIT_ASSERT(keySet.equal_range(2) != std::make_pair(keySet.begin(), keySet.end()));
  
              KeySet const& ckeySet = keySet;
              UNIT_ASSERT(ckeySet.find(2) != ckeySet.end());
              UNIT_ASSERT(ckeySet.lower_bound(2) != ckeySet.end());
              UNIT_ASSERT(ckeySet.upper_bound(2) != ckeySet.end());
              UNIT_ASSERT(ckeySet.equal_range(2) != std::make_pair(ckeySet.begin(), ckeySet.end()));
          }
  
          {
              using KeySet = TMultiSet<TKey const volatile*, TKeyCmpPtr>;
              KeySet keySet;
              TKey key1(1), key2(2), key3(3), key4(4);
              keySet.insert(&key1);
              keySet.insert(&key2);
              keySet.insert(&key3);
              keySet.insert(&key4);
  
              UNIT_ASSERT(keySet.count(1) == 1);
              UNIT_ASSERT(keySet.count(5) == 0);
  
              UNIT_ASSERT(keySet.find(2) != keySet.end());
              UNIT_ASSERT(keySet.lower_bound(2) != keySet.end());
              UNIT_ASSERT(keySet.upper_bound(2) != keySet.end());
              UNIT_ASSERT(keySet.equal_range(2) != std::make_pair(keySet.begin(), keySet.end()));
  
              KeySet const& ckeySet = keySet;
              UNIT_ASSERT(ckeySet.find(2) != ckeySet.end());
              UNIT_ASSERT(ckeySet.lower_bound(2) != ckeySet.end());
              UNIT_ASSERT(ckeySet.upper_bound(2) != ckeySet.end());
              UNIT_ASSERT(ckeySet.equal_range(2) != std::make_pair(ckeySet.begin(), ckeySet.end()));
          }
      }
  }
  