proconlib

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

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/tuple_hash.test.cpp

Depends on

Code

// competitive-verifier: STANDALONE

#include <iostream>
#include <vector>
#include <algorithm>
#include "tools/assert_that.hpp"
#include "tools/tuple_hash.hpp"

using ll = long long;

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

  {
    std::vector<std::size_t> v;
    const tools::tuple_hash<ll> hasher;
    for (ll i = 0; i < 10000000; ++i) {
      const auto tuple = std::make_tuple(i);
      v.push_back(hasher(tuple));
      assert_that(hasher(tuple) == v.back());
    }

    const auto old_size = v.size();
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    assert_that(v.size() == old_size);
  }

  {
    std::vector<std::size_t> v;
    const tools::tuple_hash<ll, ll> hasher;
    for (ll i = 0; i < 3000; ++i) {
      for (ll j = 0; j < 3000; ++j) {
        const auto tuple = std::make_tuple(i, j);
        v.push_back(hasher(tuple));
        assert_that(hasher(tuple) == v.back());
      }
    }

    const auto old_size = v.size();
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    assert_that(v.size() == old_size);
  }

  {
    std::vector<std::size_t> v;
    const tools::tuple_hash<ll, ll, ll> hasher;
    for (ll i = 0; i < 200; ++i) {
      for (ll j = 0; j < 200; ++j) {
        for (ll k = 0; k < 200; ++k) {
          const auto tuple = std::make_tuple(i, j, k);
          v.push_back(hasher(tuple));
          assert_that(hasher(tuple) == v.back());
        }
      }
    }

    const auto old_size = v.size();
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    assert_that(v.size() == old_size);
  }

  {
    std::vector<std::size_t> v;
    const tools::tuple_hash<ll, ll, ll, ll> hasher;
    for (ll i = 0; i < 60; ++i) {
      for (ll j = 0; j < 60; ++j) {
        for (ll k = 0; k < 60; ++k) {
          for (ll l = 0; l < 60; ++l) {
            const auto tuple = std::make_tuple(i, j, k, l);
            v.push_back(hasher(tuple));
            assert_that(hasher(tuple) == v.back());
          }
        }
      }
    }

    const auto old_size = v.size();
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    assert_that(v.size() == old_size);
  }

  return 0;
}

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

#include <iostream>
#include <vector>
#include <algorithm>
#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/tuple_hash.hpp"



#include <cstddef>
#include <tuple>
#include <limits>
#include <functional>
#line 1 "tools/now.hpp"



#include <chrono>

namespace tools {
  inline long long now() {
    return ::std::chrono::duration_cast<::std::chrono::nanoseconds>(::std::chrono::high_resolution_clock::now().time_since_epoch()).count();
  }
}


#line 1 "tools/hash_combine.hpp"



#line 6 "tools/hash_combine.hpp"

// Source: https://github.com/google/cityhash/blob/f5dc54147fcce12cefd16548c8e760d68ac04226/src/city.h
// License: MIT
// Author: Google Inc.

// Copyright (c) 2011 Google, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

namespace tools {
  template <typename T>
  void hash_combine(::std::size_t& seed, const T& v) {
    static const ::std::hash<T> hasher;
    static constexpr ::std::size_t k_mul = 0x9ddfea08eb382d69ULL;
    ::std::size_t a = (hasher(v) ^ seed) * k_mul;
    a ^= (a >> 47);
    ::std::size_t b = (seed ^ a) * k_mul;
    b ^= (b >> 47);
    seed = b * k_mul;
  }
}


#line 11 "tools/tuple_hash.hpp"

namespace tools {
  template <typename... Ts>
  struct tuple_hash {
    template <::std::size_t I = sizeof...(Ts) - 1>
    ::std::size_t operator()(const ::std::tuple<Ts...>& key) const {
      if constexpr (I == ::std::numeric_limits<::std::size_t>::max()) {
        static const ::std::size_t seed = ::tools::now();
        return seed;
      } else {
        ::std::size_t seed = this->operator()<I - 1>(key);
        ::tools::hash_combine(seed, ::std::get<I>(key));
        return seed;
      }
    }
  };
}


#line 8 "tests/tuple_hash.test.cpp"

using ll = long long;

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

  {
    std::vector<std::size_t> v;
    const tools::tuple_hash<ll> hasher;
    for (ll i = 0; i < 10000000; ++i) {
      const auto tuple = std::make_tuple(i);
      v.push_back(hasher(tuple));
      assert_that(hasher(tuple) == v.back());
    }

    const auto old_size = v.size();
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    assert_that(v.size() == old_size);
  }

  {
    std::vector<std::size_t> v;
    const tools::tuple_hash<ll, ll> hasher;
    for (ll i = 0; i < 3000; ++i) {
      for (ll j = 0; j < 3000; ++j) {
        const auto tuple = std::make_tuple(i, j);
        v.push_back(hasher(tuple));
        assert_that(hasher(tuple) == v.back());
      }
    }

    const auto old_size = v.size();
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    assert_that(v.size() == old_size);
  }

  {
    std::vector<std::size_t> v;
    const tools::tuple_hash<ll, ll, ll> hasher;
    for (ll i = 0; i < 200; ++i) {
      for (ll j = 0; j < 200; ++j) {
        for (ll k = 0; k < 200; ++k) {
          const auto tuple = std::make_tuple(i, j, k);
          v.push_back(hasher(tuple));
          assert_that(hasher(tuple) == v.back());
        }
      }
    }

    const auto old_size = v.size();
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    assert_that(v.size() == old_size);
  }

  {
    std::vector<std::size_t> v;
    const tools::tuple_hash<ll, ll, ll, ll> hasher;
    for (ll i = 0; i < 60; ++i) {
      for (ll j = 0; j < 60; ++j) {
        for (ll k = 0; k < 60; ++k) {
          for (ll l = 0; l < 60; ++l) {
            const auto tuple = std::make_tuple(i, j, k, l);
            v.push_back(hasher(tuple));
            assert_that(hasher(tuple) == v.back());
          }
        }
      }
    }

    const auto old_size = v.size();
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    assert_that(v.size() == old_size);
  }

  return 0;
}
Back to top page