proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/multiset.test.cpp

Depends on

Code

// competitive-verifier: STANDALONE

#include <iostream>
#include "tools/assert_that.hpp"
#include "tools/multiset.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  tools::multiset<int, std::greater<int>> bag({3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5});

  assert_that(bag.size() == 11);

  {
    auto it = bag.begin();
    assert_that(*it == 9);
    ++it;
    assert_that(*it == 6);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 4);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 2);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(it == bag.end());
    --it;
    assert_that(*it == 1);
    --it;
    assert_that(*it == 1);
    --it;
    assert_that(*it == 2);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 4);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 6);
    --it;
    assert_that(*it == 9);
  }

  {
    auto it = bag.cbegin();
    assert_that(*it == 9);
    ++it;
    assert_that(*it == 6);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 4);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 2);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(it == bag.cend());
    --it;
    assert_that(*it == 1);
    --it;
    assert_that(*it == 1);
    --it;
    assert_that(*it == 2);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 4);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 6);
    --it;
    assert_that(*it == 9);
  }

  {
    auto it = bag.rbegin();
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 2);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 4);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 6);
    ++it;
    assert_that(*it == 9);
    ++it;
    assert_that(it == bag.rend());
    --it;
    assert_that(*it == 9);
    --it;
    assert_that(*it == 6);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 4);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 2);
    --it;
    assert_that(*it == 1);
    --it;
    assert_that(*it == 1);
  }

  {
    auto it = bag.crbegin();
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 2);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 4);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 6);
    ++it;
    assert_that(*it == 9);
    ++it;
    assert_that(it == bag.crend());
    --it;
    assert_that(*it == 9);
    --it;
    assert_that(*it == 6);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 4);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 2);
    --it;
    assert_that(*it == 1);
    --it;
    assert_that(*it == 1);
  }

  assert_that(bag.count(1) == 2);
  assert_that(bag.count(2) == 1);
  assert_that(bag.count(3) == 2);
  assert_that(bag.count(4) == 1);
  assert_that(bag.count(5) == 3);
  assert_that(bag.count(6) == 1);
  assert_that(bag.count(7) == 0);
  assert_that(bag.count(8) == 0);
  assert_that(bag.count(9) == 1);

  assert_that(std::distance(bag.begin(), bag.lower_bound(1)) == 9);
  assert_that(std::distance(bag.begin(), bag.lower_bound(2)) == 8);
  assert_that(std::distance(bag.begin(), bag.lower_bound(3)) == 6);
  assert_that(std::distance(bag.begin(), bag.lower_bound(4)) == 5);
  assert_that(std::distance(bag.begin(), bag.lower_bound(5)) == 2);
  assert_that(std::distance(bag.begin(), bag.lower_bound(6)) == 1);
  assert_that(std::distance(bag.begin(), bag.lower_bound(7)) == 1);
  assert_that(std::distance(bag.begin(), bag.lower_bound(8)) == 1);
  assert_that(std::distance(bag.begin(), bag.lower_bound(9)) == 0);

  assert_that(std::distance(bag.begin(), bag.upper_bound(1)) == 11);
  assert_that(std::distance(bag.begin(), bag.upper_bound(2)) == 9);
  assert_that(std::distance(bag.begin(), bag.upper_bound(3)) == 8);
  assert_that(std::distance(bag.begin(), bag.upper_bound(4)) == 6);
  assert_that(std::distance(bag.begin(), bag.upper_bound(5)) == 5);
  assert_that(std::distance(bag.begin(), bag.upper_bound(6)) == 2);
  assert_that(std::distance(bag.begin(), bag.upper_bound(7)) == 1);
  assert_that(std::distance(bag.begin(), bag.upper_bound(8)) == 1);
  assert_that(std::distance(bag.begin(), bag.upper_bound(9)) == 1);

  assert_that(bag.key_comp()(2, 1));
  assert_that(!bag.key_comp()(2, 2));
  assert_that(!bag.key_comp()(2, 3));

  assert_that(!bag.empty());

  assert_that(std::distance(bag.begin(), bag.find(1)) == 9);
  assert_that(std::distance(bag.begin(), bag.find(2)) == 8);
  assert_that(std::distance(bag.begin(), bag.find(3)) == 6);
  assert_that(std::distance(bag.begin(), bag.find(4)) == 5);
  assert_that(std::distance(bag.begin(), bag.find(5)) == 2);
  assert_that(std::distance(bag.begin(), bag.find(6)) == 1);
  assert_that(bag.find(7) == bag.end());
  assert_that(bag.find(8) == bag.end());
  assert_that(std::distance(bag.begin(), bag.lower_bound(9)) == 0);

  assert_that(bag.contains(1));
  assert_that(bag.contains(2));
  assert_that(bag.contains(3));
  assert_that(bag.contains(4));
  assert_that(bag.contains(5));
  assert_that(bag.contains(6));
  assert_that(!bag.contains(7));
  assert_that(!bag.contains(8));
  assert_that(bag.contains(9));

  {
    const auto [lb, ub] = bag.equal_range(1);
    assert_that(std::distance(bag.begin(), lb) == 9);
    assert_that(std::distance(bag.begin(), ub) == 11);
  }
  {
    const auto [lb, ub] = bag.equal_range(2);
    assert_that(std::distance(bag.begin(), lb) == 8);
    assert_that(std::distance(bag.begin(), ub) == 9);
  }
  {
    const auto [lb, ub] = bag.equal_range(3);
    assert_that(std::distance(bag.begin(), lb) == 6);
    assert_that(std::distance(bag.begin(), ub) == 8);
  }
  {
    const auto [lb, ub] = bag.equal_range(4);
    assert_that(std::distance(bag.begin(), lb) == 5);
    assert_that(std::distance(bag.begin(), ub) == 6);
  }
  {
    const auto [lb, ub] = bag.equal_range(5);
    assert_that(std::distance(bag.begin(), lb) == 2);
    assert_that(std::distance(bag.begin(), ub) == 5);
  }
  {
    const auto [lb, ub] = bag.equal_range(6);
    assert_that(std::distance(bag.begin(), lb) == 1);
    assert_that(std::distance(bag.begin(), ub) == 2);
  }
  {
    const auto [lb, ub] = bag.equal_range(7);
    assert_that(std::distance(bag.begin(), lb) == 1);
    assert_that(std::distance(bag.begin(), ub) == 1);
  }
  {
    const auto [lb, ub] = bag.equal_range(8);
    assert_that(std::distance(bag.begin(), lb) == 1);
    assert_that(std::distance(bag.begin(), ub) == 1);
  }
  {
    const auto [lb, ub] = bag.equal_range(9);
    assert_that(std::distance(bag.begin(), lb) == 0);
    assert_that(std::distance(bag.begin(), ub) == 1);
  }

  assert_that(bag.value_comp()(2, 1));
  assert_that(!bag.value_comp()(2, 2));
  assert_that(!bag.value_comp()(2, 3));

  assert_that(*bag.find_by_order(0) == 9);
  assert_that(*bag.find_by_order(1) == 6);
  assert_that(*bag.find_by_order(2) == 5);
  assert_that(*bag.find_by_order(3) == 5);
  assert_that(*bag.find_by_order(4) == 5);
  assert_that(*bag.find_by_order(5) == 4);
  assert_that(*bag.find_by_order(6) == 3);
  assert_that(*bag.find_by_order(7) == 3);
  assert_that(*bag.find_by_order(8) == 2);
  assert_that(*bag.find_by_order(9) == 1);
  assert_that(*bag.find_by_order(10) == 1);
  assert_that(bag.find_by_order(11) == bag.end());

  assert_that(bag.order_of_key(1) == 9);
  assert_that(bag.order_of_key(2) == 8);
  assert_that(bag.order_of_key(3) == 6);
  assert_that(bag.order_of_key(4) == 5);
  assert_that(bag.order_of_key(5) == 2);
  assert_that(bag.order_of_key(6) == 1);
  assert_that(bag.order_of_key(7) == 1);
  assert_that(bag.order_of_key(8) == 1);
  assert_that(bag.order_of_key(9) == 0);

  bag.clear();
  assert_that(bag.empty());

  bag.insert({3, 1, 4, 1, 5});
  assert_that(bag.size() == 5);
  {
    auto it = bag.begin();
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 4);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 1);
  }

  bag.emplace(9);
  assert_that(bag.size() == 6);

  bag.erase(std::next(bag.begin()), std::prev(bag.end()));
  assert_that(bag.size() == 2);
  {
    auto it = bag.begin();
    assert_that(*it == 9);
    ++it;
    assert_that(*it == 1);
  }

  bag.insert(1);
  bag.insert(2);
  bag.insert(2);
  assert_that(bag.size() == 5);

  bag.erase(2);
  assert_that(bag.size() == 3);
  {
    auto it = bag.begin();
    assert_that(*it == 9);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 1);
  }

  return 0;
}

#line 1 "tests/multiset.test.cpp"
// competitive-verifier: STANDALONE

#include <iostream>
#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    ::std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    ::std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 1 "tools/multiset.hpp"



#include <functional>
#include <utility>
#include <cstddef>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <iterator>
#include <initializer_list>
#include <limits>
#include <algorithm>

namespace tools {
  template <typename Key, typename Compare = ::std::less<Key>>
  class multiset {
    class PairCompare {
      Compare m_key_comp;

    public:
      PairCompare() = default;
      explicit PairCompare(const Compare& key_comp) : m_key_comp(key_comp) {
      }

      bool operator()(const ::std::pair<Key, ::std::size_t>& lhs, const ::std::pair<Key, ::std::size_t>& rhs) const {
        if (this->m_key_comp(lhs.first, rhs.first)) return true;
        if (this->m_key_comp(rhs.first, lhs.first)) return false;
        return lhs.second < rhs.second;
      }

      Compare key_comp() const {
        return this->m_key_comp;
      }
    };
    using pbds_tree = ::__gnu_pbds::tree<::std::pair<Key, ::std::size_t>, ::__gnu_pbds::null_type, PairCompare, ::__gnu_pbds::rb_tree_tag, ::__gnu_pbds::tree_order_statistics_node_update>;

    ::std::size_t m_next_id;
    pbds_tree m_set;

  public:
    using key_type = Key;
    using value_type = Key;
    using key_compare = Compare;
    using value_compare = Compare;
    using reference = Key&;
    using const_reference = const Key&;
    class iterator {
      typename pbds_tree::iterator m_it;

    public:
      using difference_type = ::std::ptrdiff_t;
      using value_type = Key;
      using reference = const Key&;
      using pointer = const Key*;
      using iterator_category = ::std::bidirectional_iterator_tag;

      iterator() = default;
      iterator(const typename pbds_tree::iterator it) : m_it(it) {
      }

      typename pbds_tree::iterator base() const {
        return this->m_it;
      }

      reference operator*() const {
        return this->m_it->first;
      }
      iterator& operator++() {
        ++this->m_it;
        return *this;
      }
      iterator operator++(int) {
        const auto self = *this;
        ++*this;
        return self;
      }
      iterator& operator--() {
        --this->m_it;
        return *this;
      }
      iterator operator--(int) {
        const auto self = *this;
        --*this;
        return self;
      }

      friend bool operator==(const iterator lhs, const iterator rhs) {
        return lhs.m_it == rhs.m_it;
      }
      friend bool operator!=(const iterator lhs, const iterator rhs) {
        return lhs.m_it != rhs.m_it;
      }
    };
    using const_iterator = iterator;
    using size_type = ::std::size_t;
    using difference_type = ::std::ptrdiff_t;
    using pointer = Key*;
    using const_pointer = const Key*;
    using reverse_iterator = ::std::reverse_iterator<iterator>;
    using const_reverse_iterator = reverse_iterator;

    explicit multiset(const Compare& comp = Compare()) : m_next_id(0), m_set(PairCompare(comp)) {
    }
    template <typename InputIterator>
    multiset(const InputIterator first, const InputIterator last, const Compare& comp = Compare()) : multiset(comp) {
      this->insert(first, last);
    }
    multiset(const ::std::initializer_list<Key> init, const Compare& comp = Compare()) : multiset(comp) {
      this->insert(init);
    }

    iterator begin() const {
      return iterator(this->m_set.begin());
    }
    iterator cbegin() const {
      return this->begin();
    }
    iterator end() const {
      return iterator(this->m_set.end());
    }
    iterator cend() const {
      return this->end();
    }
    reverse_iterator rbegin() const {
      return reverse_iterator(this->end());
    }
    reverse_iterator crbegin() const {
      return this->rbegin();
    }
    reverse_iterator rend() const {
      return reverse_iterator(this->begin());
    }
    reverse_iterator crend() const {
      return this->rend();
    }

    bool empty() const {
      return this->m_set.empty();
    }
    size_type size() const {
      return this->m_set.size();
    }
    size_type max_size() const {
      return this->m_set.max_size();
    }

    void clear() {
      this->m_set.clear();
    }
    iterator insert(const Key& x) {
      return iterator(this->m_set.insert(::std::make_pair(x, this->m_next_id++)).first);
    }
    iterator insert([[maybe_unused]] const iterator position, const Key& x) {
      return this->insert(x);
    }
    template <typename InputIterator>
    void insert(const InputIterator first, const InputIterator last) {
      for (auto it = first; it != last; ++it) {
        this->insert(*it);
      }
    }
    void insert(const ::std::initializer_list<Key> init) {
      for (const auto& x : init) {
        this->insert(x);
      }
    }
    template <class... Args>
    iterator emplace(Args&&... args) {
      return this->insert(Key(::std::forward<Args>(args)...));
    }
    template <class... Args>
    iterator emplace_hint([[maybe_unused]] const iterator hint, Args&&... args) {
      return this->emplace(::std::forward<Args>(args)...);
    }
    iterator erase(const iterator position) {
      return iterator(this->m_set.erase(position.base()));
    }
    size_type erase(const Key& x) {
      size_type n = 0;
      for (auto it = this->lower_bound(x); it != this->end() && !this->key_comp()(x, *it); it = this->erase(it)) {
        ++n;
      }
      return n;
    }
    iterator erase(const iterator first, const iterator last) {
      const size_type n = ::std::distance(first, last);
      auto it = first;
      for (size_type i = 0; i < n; ++i) {
        it = this->erase(it);
      }
      return it;
    }
    void swap(::tools::multiset<Key, Compare>& st) {
      ::std::swap(this->m_next_id, st.m_next_id);
      this->m_set.swap(st.m_set);
    }
    template <typename C2>
    void merge(::tools::multiset<Key, C2>& source) {
      this->insert(source.begin(), source.end());
      source.clear();
    }

    size_type count(const Key& x) const {
      return this->m_set.order_of_key(::std::make_pair(x, ::std::numeric_limits<::std::size_t>::max())) - this->m_set.order_of_key(::std::make_pair(x, 0));
    }
    iterator find(const Key& x) const {
      const auto it = this->lower_bound(x);
      if (it == this->end() || this->key_comp()(x, *it)) return this->end();
      return it;
    }
    bool contains(const Key& x) const {
      return this->find(x) != this->end();
    }
    ::std::pair<iterator, iterator> equal_range(const Key& x) const {
      return ::std::make_pair(this->lower_bound(x), this->upper_bound(x));
    }
    iterator lower_bound(const Key& x) const {
      return iterator(this->m_set.lower_bound(::std::make_pair(x, 0)));
    }
    iterator upper_bound(const Key& x) const {
      return iterator(this->m_set.upper_bound(::std::make_pair(x, ::std::numeric_limits<::std::size_t>::max())));
    }

    Compare key_comp() const {
      return this->m_set.get_cmp_fn().key_comp();
    }
    Compare value_comp() const {
      return this->key_comp();
    }

    friend bool operator==(const ::tools::multiset<Key, Compare>& x, const ::tools::multiset<Key, Compare>& y) {
      return ::std::equal(x.begin(), x.end(), y.begin(), y.end());
    }
    friend bool operator!=(const ::tools::multiset<Key, Compare>& x, const ::tools::multiset<Key, Compare>& y) {
      return !(x == y);
    }
    friend bool operator<(const ::tools::multiset<Key, Compare>& x, const ::tools::multiset<Key, Compare>& y) {
      return ::std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
    }
    friend bool operator<=(const ::tools::multiset<Key, Compare>& x, const ::tools::multiset<Key, Compare>& y) {
      return !(y < x);
    }
    friend bool operator>(const ::tools::multiset<Key, Compare>& x, const ::tools::multiset<Key, Compare>& y) {
      return y < x;
    }
    friend bool operator>=(const ::tools::multiset<Key, Compare>& x, const ::tools::multiset<Key, Compare>& y) {
      return !(x < y);
    }

    iterator find_by_order(const size_type order) const {
      return iterator(this->m_set.find_by_order(order));
    }
    size_type order_of_key(const Key& x) const {
      return this->m_set.order_of_key(::std::make_pair(x, 0));
    }
  };
}


#line 6 "tests/multiset.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  tools::multiset<int, std::greater<int>> bag({3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5});

  assert_that(bag.size() == 11);

  {
    auto it = bag.begin();
    assert_that(*it == 9);
    ++it;
    assert_that(*it == 6);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 4);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 2);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(it == bag.end());
    --it;
    assert_that(*it == 1);
    --it;
    assert_that(*it == 1);
    --it;
    assert_that(*it == 2);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 4);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 6);
    --it;
    assert_that(*it == 9);
  }

  {
    auto it = bag.cbegin();
    assert_that(*it == 9);
    ++it;
    assert_that(*it == 6);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 4);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 2);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(it == bag.cend());
    --it;
    assert_that(*it == 1);
    --it;
    assert_that(*it == 1);
    --it;
    assert_that(*it == 2);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 4);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 6);
    --it;
    assert_that(*it == 9);
  }

  {
    auto it = bag.rbegin();
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 2);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 4);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 6);
    ++it;
    assert_that(*it == 9);
    ++it;
    assert_that(it == bag.rend());
    --it;
    assert_that(*it == 9);
    --it;
    assert_that(*it == 6);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 4);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 2);
    --it;
    assert_that(*it == 1);
    --it;
    assert_that(*it == 1);
  }

  {
    auto it = bag.crbegin();
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 2);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 4);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 6);
    ++it;
    assert_that(*it == 9);
    ++it;
    assert_that(it == bag.crend());
    --it;
    assert_that(*it == 9);
    --it;
    assert_that(*it == 6);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 5);
    --it;
    assert_that(*it == 4);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 3);
    --it;
    assert_that(*it == 2);
    --it;
    assert_that(*it == 1);
    --it;
    assert_that(*it == 1);
  }

  assert_that(bag.count(1) == 2);
  assert_that(bag.count(2) == 1);
  assert_that(bag.count(3) == 2);
  assert_that(bag.count(4) == 1);
  assert_that(bag.count(5) == 3);
  assert_that(bag.count(6) == 1);
  assert_that(bag.count(7) == 0);
  assert_that(bag.count(8) == 0);
  assert_that(bag.count(9) == 1);

  assert_that(std::distance(bag.begin(), bag.lower_bound(1)) == 9);
  assert_that(std::distance(bag.begin(), bag.lower_bound(2)) == 8);
  assert_that(std::distance(bag.begin(), bag.lower_bound(3)) == 6);
  assert_that(std::distance(bag.begin(), bag.lower_bound(4)) == 5);
  assert_that(std::distance(bag.begin(), bag.lower_bound(5)) == 2);
  assert_that(std::distance(bag.begin(), bag.lower_bound(6)) == 1);
  assert_that(std::distance(bag.begin(), bag.lower_bound(7)) == 1);
  assert_that(std::distance(bag.begin(), bag.lower_bound(8)) == 1);
  assert_that(std::distance(bag.begin(), bag.lower_bound(9)) == 0);

  assert_that(std::distance(bag.begin(), bag.upper_bound(1)) == 11);
  assert_that(std::distance(bag.begin(), bag.upper_bound(2)) == 9);
  assert_that(std::distance(bag.begin(), bag.upper_bound(3)) == 8);
  assert_that(std::distance(bag.begin(), bag.upper_bound(4)) == 6);
  assert_that(std::distance(bag.begin(), bag.upper_bound(5)) == 5);
  assert_that(std::distance(bag.begin(), bag.upper_bound(6)) == 2);
  assert_that(std::distance(bag.begin(), bag.upper_bound(7)) == 1);
  assert_that(std::distance(bag.begin(), bag.upper_bound(8)) == 1);
  assert_that(std::distance(bag.begin(), bag.upper_bound(9)) == 1);

  assert_that(bag.key_comp()(2, 1));
  assert_that(!bag.key_comp()(2, 2));
  assert_that(!bag.key_comp()(2, 3));

  assert_that(!bag.empty());

  assert_that(std::distance(bag.begin(), bag.find(1)) == 9);
  assert_that(std::distance(bag.begin(), bag.find(2)) == 8);
  assert_that(std::distance(bag.begin(), bag.find(3)) == 6);
  assert_that(std::distance(bag.begin(), bag.find(4)) == 5);
  assert_that(std::distance(bag.begin(), bag.find(5)) == 2);
  assert_that(std::distance(bag.begin(), bag.find(6)) == 1);
  assert_that(bag.find(7) == bag.end());
  assert_that(bag.find(8) == bag.end());
  assert_that(std::distance(bag.begin(), bag.lower_bound(9)) == 0);

  assert_that(bag.contains(1));
  assert_that(bag.contains(2));
  assert_that(bag.contains(3));
  assert_that(bag.contains(4));
  assert_that(bag.contains(5));
  assert_that(bag.contains(6));
  assert_that(!bag.contains(7));
  assert_that(!bag.contains(8));
  assert_that(bag.contains(9));

  {
    const auto [lb, ub] = bag.equal_range(1);
    assert_that(std::distance(bag.begin(), lb) == 9);
    assert_that(std::distance(bag.begin(), ub) == 11);
  }
  {
    const auto [lb, ub] = bag.equal_range(2);
    assert_that(std::distance(bag.begin(), lb) == 8);
    assert_that(std::distance(bag.begin(), ub) == 9);
  }
  {
    const auto [lb, ub] = bag.equal_range(3);
    assert_that(std::distance(bag.begin(), lb) == 6);
    assert_that(std::distance(bag.begin(), ub) == 8);
  }
  {
    const auto [lb, ub] = bag.equal_range(4);
    assert_that(std::distance(bag.begin(), lb) == 5);
    assert_that(std::distance(bag.begin(), ub) == 6);
  }
  {
    const auto [lb, ub] = bag.equal_range(5);
    assert_that(std::distance(bag.begin(), lb) == 2);
    assert_that(std::distance(bag.begin(), ub) == 5);
  }
  {
    const auto [lb, ub] = bag.equal_range(6);
    assert_that(std::distance(bag.begin(), lb) == 1);
    assert_that(std::distance(bag.begin(), ub) == 2);
  }
  {
    const auto [lb, ub] = bag.equal_range(7);
    assert_that(std::distance(bag.begin(), lb) == 1);
    assert_that(std::distance(bag.begin(), ub) == 1);
  }
  {
    const auto [lb, ub] = bag.equal_range(8);
    assert_that(std::distance(bag.begin(), lb) == 1);
    assert_that(std::distance(bag.begin(), ub) == 1);
  }
  {
    const auto [lb, ub] = bag.equal_range(9);
    assert_that(std::distance(bag.begin(), lb) == 0);
    assert_that(std::distance(bag.begin(), ub) == 1);
  }

  assert_that(bag.value_comp()(2, 1));
  assert_that(!bag.value_comp()(2, 2));
  assert_that(!bag.value_comp()(2, 3));

  assert_that(*bag.find_by_order(0) == 9);
  assert_that(*bag.find_by_order(1) == 6);
  assert_that(*bag.find_by_order(2) == 5);
  assert_that(*bag.find_by_order(3) == 5);
  assert_that(*bag.find_by_order(4) == 5);
  assert_that(*bag.find_by_order(5) == 4);
  assert_that(*bag.find_by_order(6) == 3);
  assert_that(*bag.find_by_order(7) == 3);
  assert_that(*bag.find_by_order(8) == 2);
  assert_that(*bag.find_by_order(9) == 1);
  assert_that(*bag.find_by_order(10) == 1);
  assert_that(bag.find_by_order(11) == bag.end());

  assert_that(bag.order_of_key(1) == 9);
  assert_that(bag.order_of_key(2) == 8);
  assert_that(bag.order_of_key(3) == 6);
  assert_that(bag.order_of_key(4) == 5);
  assert_that(bag.order_of_key(5) == 2);
  assert_that(bag.order_of_key(6) == 1);
  assert_that(bag.order_of_key(7) == 1);
  assert_that(bag.order_of_key(8) == 1);
  assert_that(bag.order_of_key(9) == 0);

  bag.clear();
  assert_that(bag.empty());

  bag.insert({3, 1, 4, 1, 5});
  assert_that(bag.size() == 5);
  {
    auto it = bag.begin();
    assert_that(*it == 5);
    ++it;
    assert_that(*it == 4);
    ++it;
    assert_that(*it == 3);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 1);
  }

  bag.emplace(9);
  assert_that(bag.size() == 6);

  bag.erase(std::next(bag.begin()), std::prev(bag.end()));
  assert_that(bag.size() == 2);
  {
    auto it = bag.begin();
    assert_that(*it == 9);
    ++it;
    assert_that(*it == 1);
  }

  bag.insert(1);
  bag.insert(2);
  bag.insert(2);
  assert_that(bag.size() == 5);

  bag.erase(2);
  assert_that(bag.size() == 3);
  {
    auto it = bag.begin();
    assert_that(*it == 9);
    ++it;
    assert_that(*it == 1);
    ++it;
    assert_that(*it == 1);
  }

  return 0;
}
Back to top page