comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: unit-test/utility/tuple-hash.test.cpp

Depends on

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ITP1_1_A

#include "src/utility/tuple-hash.hpp"

#include "src/cpp-template/header/int-alias.hpp"
#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"

#include <algorithm>
#include <cassert>
#include <iostream>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

namespace luz {

  void main_() {
    {
      i64 large_number = 998244353ll * 512;

      std::tuple< i32, char, i64 > a(5, 'b', large_number),
          b(6, 'b', large_number), c(5, 'c', large_number),
          d(5, 'b', large_number + 1);
      std::vector< usize > hs({TupleHash()(a), TupleHash()(b),
                               TupleHash()(c), TupleHash()(d)});
      std::sort(hs.begin(), hs.end());
      hs.erase(std::unique(hs.begin(), hs.end()), hs.end());
      assert(hs.size() == (usize)4);
    }

    {
      using Tuple = std::tuple< i32, i32, i32 >;
      std::vector< Tuple > ts({{1, 2, 3},
                               {1, 3, 2},
                               {2, 1, 3},
                               {2, 3, 1},
                               {3, 1, 2},
                               {3, 2, 1}});
      std::vector< usize > hs(6);
      for (usize i: rep(0, 6)) {
        hs[i] = TupleHash()(ts[i]);
      }
      std::sort(hs.begin(), hs.end());
      hs.erase(std::unique(hs.begin(), hs.end()), hs.end());
      assert(hs.size() == (usize)6);
    }

    using PrimitiveTuple =
        std::tuple< bool, char, short, int, long, long long >;
    std::unordered_map< PrimitiveTuple, usize, TupleHash > ump;
    std::unordered_multimap< PrimitiveTuple, usize, TupleHash > ummp;
    std::unordered_set< PrimitiveTuple, TupleHash > ust;
    std::unordered_multiset< PrimitiveTuple, TupleHash > umst;

    std::cout << "Hello World" << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}
#line 1 "unit-test/utility/tuple-hash.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ITP1_1_A

#line 2 "src/utility/tuple-hash.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/utility/tuple-hash.hpp"

#include <functional>
#include <tuple>
#include <utility>

namespace luz::impl_tuple_hash {

  template < usize Index >
  class ImplTupleHash {
   public:
    template < typename T >
    usize hash_combine(const T &x, usize hr) const {
      usize h = std::hash< T >()(x);
      return hr ^ (h + (hr << 11) + (hr >> 13));
    }

    template < class Tuple >
    usize operator()(const Tuple &t) const noexcept {
      usize hr = ImplTupleHash< Index - 1 >()(t);
      return hash_combine(std::get< Index - 1 >(t), hr);
    }
  };

  template <>
  class ImplTupleHash< 0 > {
   public:
    template < class Tuple >
    usize operator()([[maybe_unused]] const Tuple &_) const noexcept {
      return 0;
    }
  };

} // namespace luz::impl_tuple_hash

namespace luz {

  class TupleHash {
    template < usize Index >
    using ImplTupleHash = impl_tuple_hash::ImplTupleHash< Index >;

   public:
    template < class... Args >
    usize operator()(const std::tuple< Args... > &t) const {
      using Tuple = std::tuple< Args... >;
      return ImplTupleHash< std::tuple_size< Tuple >::value >()(t);
    }
  };

} // namespace luz
#line 4 "unit-test/utility/tuple-hash.test.cpp"

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32  = std::int32_t;
  using i64  = std::int64_t;
  using i128 = __int128_t;

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 2 "src/cpp-template/header/rep.hpp"

#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 8 "unit-test/utility/tuple-hash.test.cpp"

#line 10 "unit-test/utility/tuple-hash.test.cpp"
#include <cassert>
#include <iostream>
#line 13 "unit-test/utility/tuple-hash.test.cpp"
#include <unordered_map>
#include <unordered_set>
#line 16 "unit-test/utility/tuple-hash.test.cpp"
#include <vector>

namespace luz {

  void main_() {
    {
      i64 large_number = 998244353ll * 512;

      std::tuple< i32, char, i64 > a(5, 'b', large_number),
          b(6, 'b', large_number), c(5, 'c', large_number),
          d(5, 'b', large_number + 1);
      std::vector< usize > hs({TupleHash()(a), TupleHash()(b),
                               TupleHash()(c), TupleHash()(d)});
      std::sort(hs.begin(), hs.end());
      hs.erase(std::unique(hs.begin(), hs.end()), hs.end());
      assert(hs.size() == (usize)4);
    }

    {
      using Tuple = std::tuple< i32, i32, i32 >;
      std::vector< Tuple > ts({{1, 2, 3},
                               {1, 3, 2},
                               {2, 1, 3},
                               {2, 3, 1},
                               {3, 1, 2},
                               {3, 2, 1}});
      std::vector< usize > hs(6);
      for (usize i: rep(0, 6)) {
        hs[i] = TupleHash()(ts[i]);
      }
      std::sort(hs.begin(), hs.end());
      hs.erase(std::unique(hs.begin(), hs.end()), hs.end());
      assert(hs.size() == (usize)6);
    }

    using PrimitiveTuple =
        std::tuple< bool, char, short, int, long, long long >;
    std::unordered_map< PrimitiveTuple, usize, TupleHash > ump;
    std::unordered_multimap< PrimitiveTuple, usize, TupleHash > ummp;
    std::unordered_set< PrimitiveTuple, TupleHash > ust;
    std::unordered_multiset< PrimitiveTuple, TupleHash > umst;

    std::cout << "Hello World" << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}
Back to top page