//#####################################################################
// Copyright 2003-2005, Zhaosheng Bao, Geoffrey Irving.
// This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYRIGHT.txt.
//#####################################################################
// Function hash_function
//#####################################################################
//
// fast and random hash.  Requires only 11 cycles for 32 bit int.
//
//#####################################################################
#ifndef __hash_function__
#define __hash_function__

#include "../Data_Structures/PAIR.h"
#include "../Matrices_And_Vectors/VECTOR_2D.h"
#include "../Matrices_And_Vectors/VECTOR_3D.h"
namespace PhysBAM
{

inline unsigned int int_hash (unsigned int key)
{
	key += ~ (key << 15);
	key ^= (key >> 10);
	key += (key << 3);
	key ^= (key >> 6);
	key += ~ (key << 11);
	key ^= (key >> 16);
	return key;
}

inline unsigned int triple_int_hash (unsigned int a, unsigned int b, unsigned int c)
{
	a -= b;
	a -= c;
	a ^= (c >> 13);
	b -= c;
	b -= a;
	b ^= (a << 8);
	c -= a;
	c -= b;
	c ^= (b >> 13);
	a -= b;
	a -= c;
	a ^= (c >> 12);
	b -= c;
	b -= a;
	b ^= (a << 16);
	c -= a;
	c -= b;
	c ^= (b >> 5);
	a -= b;
	a -= c;
	a ^= (c >> 3);
	b -= c;
	b -= a;
	b ^= (a << 10);
	c -= a;
	c -= b;
	c ^= (b >> 15);
	return c;
}

inline int Hash_Reduce (const int key)
{
	return key;
}

inline int Hash_Reduce (const VECTOR_2D<int>& key)
{
	return triple_int_hash (32138912, key.x, key.y);
}

inline int Hash_Reduce (const VECTOR_3D<int>& key)
{
	return triple_int_hash (key.x, key.y, key.z);
}

template<class T, class T2>
inline int Hash_Reduce (const PAIR<T, T2>& pair)
{
	return triple_int_hash (33232132, Hash_Reduce (pair.x), Hash_Reduce (pair.y));
}

template<class T>
inline int Hash (const T& key)
{
	return Hash_Reduce (key);
}

template<>
inline int Hash (const int& key)
{
	return int_hash (key);
}

}
#endif