tests/extend_hash.test.cpp

View this file on GitHub
Last update: 2025-01-25 08:45:50+09:00

Depends on

Code

// competitive-verifier: STANDALONE

#include <algorithm>
#include <functional>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
#include "tools/assert_that.hpp"
#include "tools/extend_hash.hpp"

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

  {
    std::vector<std::size_t> v;
    const std::hash<std::pair<int, int>> hasher;
    for (int i = 0; i < 3000; ++i) {
      for (int j = 0; j < 3000; ++j) {
        const auto pair = std::make_pair(i, j);
        v.push_back(hasher(pair));
        assert_that(hasher(pair) == 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 std::hash<std::tuple<int, int>> hasher;
    for (int i = 0; i < 3000; ++i) {
      for (int 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);
  }

  return 0;
}

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

#include <algorithm>
#include <functional>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
#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/extend_hash.hpp"



// WARNING:
// This file adds partial specializations for classes in std namespace, for convenience.
// Strictly speaking, it is not allowed in C++.
// It makes the program ill-formed to include this file, and may cause undefined behavior.

#include <cstddef>
#line 1 "tools/tuple_hash.hpp"



#line 6 "tools/tuple_hash.hpp"
#include <limits>
#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 14 "tools/extend_hash.hpp"

namespace std {
  template <class T1, class T2>
  struct hash<::std::pair<T1, T2>> {
    ::std::size_t operator()(const ::std::pair<T1, T2>& key) const {
      static const ::tools::tuple_hash<T1, T2> hasher;
      return hasher(::std::make_tuple(key.first, key.second));
    }
  };

  template <class... Args>
  struct hash<::std::tuple<Args...>> {
    ::std::size_t operator()(const ::std::tuple<Args...>& key) const {
      static const ::tools::tuple_hash<Args...> hasher;
      return hasher(key);
    }
  };
}


#line 11 "tests/extend_hash.test.cpp"

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

  {
    std::vector<std::size_t> v;
    const std::hash<std::pair<int, int>> hasher;
    for (int i = 0; i < 3000; ++i) {
      for (int j = 0; j < 3000; ++j) {
        const auto pair = std::make_pair(i, j);
        v.push_back(hasher(pair));
        assert_that(hasher(pair) == 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 std::hash<std::tuple<int, int>> hasher;
    for (int i = 0; i < 3000; ++i) {
      for (int 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);
  }

  return 0;
}