src/base/features/hash.hpp

#pragma once

#include"base/dependencies/index.hpp"

#include"integers.hpp"
#include"random.hpp"
#include"shortcuts.hpp"

// Merge two hash values.
size_t hash_merge(size_t const l,size_t const r){
    constexpr u64 k=0x9ddfea08eb382d69;
    u64 h=r;
    h=(h^l)*k,h^=(h>>47);
    h=(h^l)*k,h^=(h>>47);
    return static_cast<size_t>(h*k);
}

// Pair hash specialization.
template<class Fst,class Snd>struct hash<pair<Fst,Snd>>{
    // Calculate the hash of the given pair.
    size_t operator()(pair<Fst,Snd>const&p)const{
        size_t h=2;
        h=hash_merge(h,hash<Fst>{}(p.first));
        h=hash_merge(h,hash<Snd>{}(p.second));
        return h;
    }
};

// Tuple hash specialization.
template<class...Types>struct hash<tuple<Types...>>{
    // Calculate the hash of the given tuple.
    size_t operator()(tuple<Types...>const&t)const{
        return apply([](Types const&...args){
            size_t h=sizeof...(Types);
            ((h=hash_merge(h,hash<Types>{}(args))),...);
            return h;
        },t);
    }
};

// Array hash specialization.
template<class Type,size_t Size>struct hash<array<Type,Size>>{
    // Calculate the hash of the given array.
    size_t operator()(array<Type,Size>const&a)const{
        hash<Type>const hasher;
        size_t h=Size;
        FORE(e,a){h=hash_merge(h,hasher(e));}
        return h;
    }
};

// Valarray hash specialization.
template<class Type>struct hash<valarray<Type>>{
    // Calculate the hash of the given valarray.
    size_t operator()(valarray<Type>const&va)const{
        hash<Type>const hasher;
        size_t h=SIZE(va);
        FORE(e,va){h=hash_merge(h,hasher(e));}
        return h;
    }
};

// Hash randomizer functor.
template<class Type>struct rhash{
    // Calculate the randomized hash of the given object.
    size_t operator()(Type const&x)const{
        static u64 const noise=random_seed();
        return static_cast<size_t>(splitmix64(hash<Type>{}(x)+noise));
    }
private:
    // Unsigned 64-bit mixer.
    static u64 splitmix64(u64 n){
        n+=0x9e3779b97f4a7c15;
        n=(n^(n>>30))*0xbf58476d1ce4e5b9;
        n=(n^(n>>27))*0x94d049bb133111eb;
        return n^(n>>31);
    }
};