void iterate_permutations(std::string pre, std::string word, void (*func)(std::string) )
{
	using namespace std;

	if (word.size() == 1)
		func(pre+word);
	else
	{
		for(unsigned int i=0; i<word.size(); ++i)
		{
			char c = word;
			string n_word = word;
			n_word.erase( n_word.begin() + i );
			iterate_permutations(pre + c, n_word, func);
		}
	}
}

void iterate_permutations_random(std::string pre, std::string word, void (*func)(std::string) )
{
	using namespace std;

	if (word.size() == 1)
		func(pre+word);
	else
	{
		//generate random order to traverse in
		int *order = new int[word.size()];
		for(int i=0; i<(int)word.size(); ++i)
			order = i;
		for(int i=0; i<(int)word.size(); ++i)
		{
			int j = randu(1, i);
			int order_i = order;
			order = order[j];
			order[j] = order_i;
		}

		for(unsigned int j=0; j<word.size(); ++j)
		{
			int i = order[j];

			char c = word;
			string n_word = word;
			n_word.erase( n_word.begin() + i );
			iterate_permutations_random(pre + c, n_word, func);
		}

		delete order;
	}
}

size_t factorial(size_t num){	if (num==1) return 1;	size_t next = factorial(num-1)*num;	if (next < num ) return std::numeric_limits<int>::max();	return next;}

size_t num_permutations(std::string str){	using namespace std;	sort(str.begin(), str.end() );	str.erase( unique(str.begin(), str.end() ), str.end() );	return factorial(str.size());}

std::string random_permutation(std::string word){	std::string pre;	while( word.size() > 0 )	{		size_t j = rand() % word.size();		pre += word[j];		word.erase( word.begin()+j );	}	return pre;}

size_t nump = num_permutations(word);	HashTable<std::string, bool> used_key;	for(size_t i=0; i<nump; ++i){		std::string permutation = random_permutation(word);		bool val;		while( used_key.find(permutation, val) )			permutation = random_permutation(word);		used_key.insert( permutation, true );		cout << i << ": "<< permutation << endl;	}

#pragma once

#include <vector>
#include <string>
#include <cstring>
#include "CoreMath.h"

typedef unsigned int UINT;

template<typename T>
struct is_equal
{
	bool operator()(const T &a, const T &b) const
	{
		return (a == b);
	}
};

template<typename T>
struct hash
{
	// Fallback generic, uses a random number generator with int cast as seed
	UINT operator()(const T &key) const
	{	
		long seed = static_cast<T>(key);
		return static_cast<UINT>( rand(seed)*10000.0f );
	}
};

//specialize hash func for string
template<>
UINT hash<std::string>::operator()(const std::string &str) const
{
	//djb2 hash
	UINT hash = 5381;

	const char *c = str.c_str();
	for(UINT i=0; i<str.size(); ++i)
		hash = ((hash << 5) + hash) + *c++;

	return hash;
}


template<typename Key = std::string, typename Val = UINT, UINT Alloc = 300, typename HashFcn = hash<Key>, typename EqualKey = is_equal<Key> >
class HashTable
{
	struct HashEntry
	{
		Key myKey;
		Val myVal;
		HashEntry *next;
		EqualKey myEqual;

		HashEntry(const Key &_myKey, const Val &_myVal)
			:next(NULL), myKey(_myKey), myVal(_myVal){}

		//inserts HashEntry into this node's chain
		void insert(const Key &_key, const Val &_val)
		{
			if ( myEqual(myKey, _key) )
				myVal = _val;
			else {
				if (next == NULL) next = new HashEntry(_key, _val);
				else next->insert(_key, _val);
			}
		}

		void remove(const Key &_key)
		{
			if (next == NULL) return;
			else next->remove(_key);
		}

		//finds '_val', starts looking at itself then checks chain
		bool find(const Key &_key, Val &_val) const
		{
			if ( myEqual(myKey, _key) ){ 
				_val = myVal;
				return true;
			} else {
				if (next == NULL) return false;
				else return next->find(_key, _val);
			}
		}

		//deletes all nodes in the chain (does not delete self)
		void deleteChain()
		{
			if (next != NULL){
				next->deleteChain();
				delete next;
			}
		}
	};

	HashEntry *data[Alloc];
	HashFcn myHash;
	EqualKey myEqual;

public:
	HashTable()
	{ 
		memset(data, NULL, Alloc*sizeof(HashEntry*) ); 
	}

	~HashTable()
	{
		for(UINT i=0; i<Alloc; ++i)
		{
			if (data != NULL)
			{
				data->deleteChain();
				delete data;
			}
		}
	}

	void insert(const Key &_key, const Val &_val)
	{
		UINT code = myHash(_key) % Alloc;
		HashEntry *&entry = data;
		
		if (entry == NULL) entry = new HashEntry(_key, _val);
		else entry->insert(_key, _val);
	}

	void remove(const Key &_key)
	{
		UINT code = myHash(_key) % Alloc;
		HashEntry *&entry = data;

		if (entry == NULL) return;
		else if ( myEqual(entry->myKey, _key) ) {
			entry->deleteChain();
			delete entry;
			entry = NULL;
		} else entry->remove(_key);
	}

	bool find(const Key &_key, Val &_val) const
	{
		UINT code = myHash(_key) % Alloc;
		HashEntry *entry = data;

		if (entry == NULL) return false;
		else return entry->find(_key, _val);
	}

	//ITERATOR INTERFACE

	//returned by iterator
	struct Pair
	{
		Key key;
		Val val;
	};

	class iterator : public std::iterator<std::forward_iterator_tag, Val >
	{
		UINT i;
		HashEntry *const (*data);
		HashEntry *entry;
		EqualKey myEqual;
		Pair myPair;

		void advance()
		{
			//end iterator cant advance
			if (i < 0 || i >= Alloc) return;

			//try to advance normally
			if (entry != NULL) entry = entry->next;

			//if that failed, advance to first non-null bucket
			if (entry == NULL)
			{
				//if still null, look at next buckets..
				while(entry == NULL && ++i < Alloc)		
					entry = data;
			}
		}
		
	public:
		iterator(HashEntry *const _data[Alloc], UINT _i) : i(_i), data(_data), entry(NULL)
		{
			entry = data[0];
			advance();
		}

		iterator& operator=(const iterator& other) {
			i = other.i;
			data = other.data;
			entry = other.entry;
			return(*this);
		}

		bool operator==(const iterator& other) const{
			return (i == other.i && data == other.data && entry == other.entry);
		}

		bool operator!=(const iterator& other) const{
			return !(operator==(other));
		}

		iterator& operator++() { //prefix
			if (entry != NULL) 
				advance();
			return (*this);
		}

		Pair *operator*()
		{
			if (entry != NULL){
				myPair.key = entry->myKey;
				myPair.val = entry->myVal;
				return &myPair;
			} else return NULL;
		}
	};

	//get iterators
	iterator begin() const
	{
		return iterator(data, 0);			
	}

	iterator end() const
	{
		return iterator(data, Alloc);
	}
};