using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
namespace ConsoleApp1
{

    class Program
    {

        static void Main(string[] args)
        {
            int hashFunctions =2;
          //  int[] array = { 47, 50,55,1,2,3,4,5,6,7,8,8,9,10,11,12,13,14,200,300,43254,654,6757,4324,4324324,343,5646,57,6,87,9,890,80,5544,6546,65867,8 ,435,65,7,87,8,789,80,90,345,5,435,435};
            int[] array = { 50, 47, 100, 60 };
            CuckooHash hash = new CuckooHash(array.Length,hashFunctions);
            int size = array.Length;
            hash.HashArray(array,size);
            while (hash.requiresRehashes)
            {
                size = size*2;
                hash = new CuckooHash(size, hashFunctions);
               // hash.Rehash();
                hash.HashArray(array,size);
            }

            hash.ShowResult();
            Console.ReadKey();
        }
    }


    class CuckooHash
    {
        int max;
        int hashFunctionCount;
        int[,] hashtable;
        int[] tempValues;
        public bool requiresRehashes;


        ReaderWriterLockSlim locker = new ReaderWriterLockSlim();
        UniversalHashingFamily hash;
        public CuckooHash(int max, int hashfunctionCount)
        {
            this.max = max;
            this.hashFunctionCount = hashfunctionCount;
            tempValues = new int[hashfunctionCount];
            hash = new UniversalHashingFamily(hashfunctionCount);
            requiresRehashes = false;
        }
        private void InitHashTable()
        {

            hashtable = new int[hashFunctionCount, max];


            Parallel.For(0, max, i =>
            {
                Parallel.For(0, hashFunctionCount, j =>
                {
                    hashtable[j, i] = 0;
                });
            });
            //for (int i = 0; i < max; i++)
            //{
            //    for (int j = 0; j < hashFunctionCount; j++)
            //    {
            //        hashtable[j, i] = 0;
            //    }
            //}

        }

        public void Rehash()
        {
         hash.GenerateNewFunctions();
        }
        public void HashArray(int[] array,int size)
        {
            requiresRehashes = false;
            InitHashTable();
            int cnt = 0;

            Parallel.For(0, array.Length, i =>
            {
                cnt = 0;
                PlaceToHash(array[i], 0, cnt, size);
            });

            //for (int i = 0; i < array.Length; i++)
            //{
            //    cnt = 0;
            //    PlaceToHash(array[i], 0, cnt, size);
            //}
        }

        void PlaceToHash(int value,int tableId,int timesBeenCalled,int cycleCount)
        {
            locker.EnterReadLock();
            if(timesBeenCalled == cycleCount)
            {
                Console.WriteLine("Unpositioned:"+value);
                requiresRehashes = true;
                locker.ExitReadLock();
                return;
            }
            for (int i = 0; i < hashFunctionCount; i++)
            {
                tempValues[i] = HashLocal(i, value);
                if (hashtable[i,tempValues[i]] == value)
                {
                    locker.ExitReadLock();
                    return;
                }
            }

            if(hashtable[tableId,tempValues[tableId]] != 0)
            {
                int swapedValue = hashtable[tableId, tempValues[tableId]];
                hashtable[tableId, tempValues[tableId]] = value;
                locker.ExitReadLock();
                PlaceToHash(swapedValue, (tableId + 1) % hashFunctionCount, timesBeenCalled + 1, cycleCount);

            }
            else
            {
                hashtable[tableId, tempValues[tableId]] = value;
             locker.ExitReadLock();
            }
        }


        public void ShowResult()
        {
            for (int i = 0; i < hashFunctionCount; i++)
            {
                Console.WriteLine("Table " + (i + 1).ToString());
                for (int j = 0; j < max; j++)
                {
                    Console.Write(" "+hashtable[i, j]+" ");
                }
                Console.WriteLine();
            }
        }


        public int HashLocal(int id, int key)
        {
            switch (id)
            {
                case 0:
                    return key % max;
                case 1:
                    return (key / max) % max;
                case 2:
                    return (key * max)%max;
                default:
                    return 0;
            }

        }
    }

    /// <summary>
    /// Provides a list of the first 10,000 primes.
    /// This class is a singleton, and read the primes from the file @"Data\PrimesList_10K.csv".
    /// </summary>
    public sealed class PrimesList
    {
        //
        // Singleton implementation with an attempted thread-safety using double-check locking
        // internal datastorage singleton container
        private static PrimesList _instance;

        // lock for thread-safety laziness
        private static readonly object Mutex = new object();

        //
        // INSTANCE VARIABLES
        private static string _primesDocPath = string.Empty;
        private readonly static List<int> _primes = new List<int>();

        // Picked the HashPrime to be (101) because it is prime, and if the ‘hashSize - 1’ is not a multiple of this HashPrime, which is
        // enforced in _getUpperBoundPrime, then expand function has the potential of being every value from 1 to hashSize - 1.
        // The choice is largely arbitrary.
        public const int HASH_PRIME = 101;


        /// <summary>
        /// Empty private constructor.
        /// </summary>
        private PrimesList() { }

        /// <summary>
        /// Returns the singleton instance of this class.
        /// </summary>
        public static PrimesList Instance
        {
            get
            {
                if (_instance == null)
                {
                    lock (Mutex)
                    {
                        if (_instance == null)
                        {
                            _instance = new PrimesList();
                            _initializeData();
                        }
                    }
                }

                return _instance;
            }
        }

        /// <summary>
        /// Initializes the primes document path and list.
        /// </summary>
        private static void _initializeData()
        {
            _primesDocPath = Path.Combine(Path.GetDirectoryName(Assembly.GetExecutingAssembly().Location), @"Data/PrimesDocument_10K.csv");
            string[] lines = File.ReadAllLines(_primesDocPath);

            foreach (var line in lines)
            {
                // Split the line by commas and convert the collection to a list.
                var numbersAsStrings = line.Split(',').ToList<string>();

                // defensive check against empty strings.
                numbersAsStrings.RemoveAll(item => string.IsNullOrEmpty(item) == true);

                if (numbersAsStrings.Count > 0)
                {
                    // cast them into integers and add them to the primes list
                    var numbers = numbersAsStrings.Select(item => Convert.ToInt32(item)).ToList<int>();
                    _primes.AddRange(numbers);
                }
            }
        }

        /// <summary>
        /// Return count of primes.
        /// </summary>
        public int Count
        {
            get { return _primes.Count; }
        }

        /// <summary>
        /// Returns prime number at the specified index.
        /// </summary>
        public int this[int index]
        {
            get
            {
                if (index < 0 || index >= _primes.Count)
                    throw new ArgumentOutOfRangeException();

                return _primes[index];
            }
        }

        /// <summary>
        /// Checks if a number is a Prime Number.
        /// </summary>
        public bool IsPrime(int candidate)
        {
            if ((candidate & 1) != 0)
            {
                int limit = (int)Math.Sqrt(candidate);

                for (int divisor = 3; divisor <= limit; divisor += 2)
                {
                    if ((candidate % divisor) == 0)
                        return false;
                }

                return true;
            }

            return (candidate == 2);
        }

        /// <summary>
        /// Returns the next biggest prime number.
        /// </summary>
        /// <param name="number"></param>
        /// <returns></returns>
        public int GetNextPrime(int number)
        {
            if (number < 0)
                throw new ArgumentException("Number should be greater than or equal to 0.");

            for (int i = 0; i < _primes.Count; i++)
            {
                if (_primes[i] >= number)
                    return _primes[i];
            }

            // Outside of our predefined table. Compute the prime the hard way.
            for (int i = (number | 1); i < Int32.MaxValue; i += 2)
            {
                if (IsPrime(i) && ((i - 1) % HASH_PRIME != 0))
                    return i;
            }

            return number;
        }

        /// <summary>
        /// Returns the next minimum prime number.
        /// </summary>
        public int GetPreviousPrime(int number)
        {
            if (number < 0)
                throw new ArgumentException("Number should be greater than or equal to 0.");

            for (int i = 0; i < _primes.Count; i++)
            {
                if (_primes[i] >= number)
                    return _primes[i];
            }

            // Outside of our predefined table. Compute the prime the hard way.
            for (int i = (number | 1); i < Int32.MaxValue; i += 2)
            {
                if (IsPrime(i) && ((i - 1) % HASH_PRIME != 0))
                    return i;
            }

            return number;
        }

        /// <summary>
        /// Returns the list of primes
        /// </summary>
        public List<int> GetAll
        {
            get { return _primes; }
        }

        /// <summary>
        /// Copy the primes list to an array, starting from a specified index.
        /// </summary>
        public void CopyTo(int[] array, int index = 0)
        {
            if (array == null)
                array = new int[_primes.Count];

            if (array.Length <= index)
                throw new ArgumentOutOfRangeException();

            int count = array.Length - index;
            int arrayIndex = index;

            if (count - _primes.Count > 0)
                count = _primes.Count;

            for (int i = 0; i < count; i++)
            {
                array[arrayIndex] = _primes[i];
                arrayIndex++;
            }
        }

    }

    /// <summary>
    /// Implements a family of Universal Hash Functions
    /// </summary>
    public class UniversalHashingFamily
        {
            // A large prime, arbitrarily chosen
            // In decimal = 2,146,435,069;
            private const int BIG_PRIME = 0x7FEFFFFD;

            private Random _randomizer { get; set; }
            private int _numberOfHashFunctions { get; set; }
            private int[] _firstMultipliersVector { get; set; }
            private int[] _secondMultipliersVector { get; set; }
            private static readonly PrimesList _primes = PrimesList.Instance;

            /// <summary>
            /// Initializes the family with a specified number of hash functions.
            /// </summary>
            public UniversalHashingFamily(int numberOfHashFunctions)
            {
                if (numberOfHashFunctions <= 0)
                    throw new ArgumentOutOfRangeException("Number of hash functions should be greater than zero.");

                _randomizer = new Random();
                _numberOfHashFunctions = numberOfHashFunctions;
                _firstMultipliersVector = new int[_numberOfHashFunctions];
                _secondMultipliersVector = new int[_numberOfHashFunctions];

                GenerateNewFunctions();
            }

            /// <summary>
            /// Returns number of member hash functions.
            /// </summary>
            public int NumberOfFunctions
            {
                get { return _numberOfHashFunctions; }
            }

            /// <summary>
            /// Generates new hash functions with new randomized multipliers.
            /// </summary>
            public void GenerateNewFunctions()
            {
                // Clear the multipliers vectors
                Array.Clear(_firstMultipliersVector, 0, _firstMultipliersVector.Length);
                Array.Clear(_secondMultipliersVector, 0, _secondMultipliersVector.Length);

                int randomMin = 0;
                int randomMax = _primes.Count - 1;

                for (int i = 0; i < _numberOfHashFunctions; i++)
                {
                    // Get only the primes that are smaller than the biggest-chosen prime.
                    int randomIndex = _randomizer.Next(randomMin, randomMax);

                    while (_primes[randomIndex] >= BIG_PRIME)
                        randomIndex = _randomizer.Next(randomMin, randomMax);

                _firstMultipliersVector[i] = _primes[randomIndex];

                    // make sure the next prime we choose is different than the first one and less than the biggest-prime.
                    randomIndex = _randomizer.Next(randomMin, randomMax);

                    while (_primes[randomIndex] >= BIG_PRIME || _primes[randomIndex] == _firstMultipliersVector[i])
                        randomIndex = _randomizer.Next(randomMin, randomMax);

                    _secondMultipliersVector[i] = _primes[randomIndex];
                }
            }

            /// <summary>
            /// Returns hash value of a string, given the specified number of the hash function to use.
            /// </summary>
            /// <param name="preHashedKey">Int pre-hash code of an object.</param>
            /// <param name="whichHashFunction">Non-zero, non-negative integer that specified the number of the hash function to use.</param>
            /// <returns></returns>
            public int UniversalHash(int preHashedKey, int whichHashFunction)
            {
                if (whichHashFunction <= 0 || whichHashFunction > _numberOfHashFunctions)
                    throw new ArgumentOutOfRangeException("WhichHashFunction parameter should be greater than zero or equal to the number of Hash Functions.");
          //  preHashedKey = 0;
                int a = _firstMultipliersVector[whichHashFunction - 1];
                int b = _secondMultipliersVector[whichHashFunction - 1];

            return ((a * preHashedKey) + b); //% BIG_PRIME;
            }

            /// <summary>
            /// Returns hash value of a string, given the specified number of the hash function to use.
            /// </summary>
            /// <param name="key">string key.</param>
            /// <param name="whichHashFunction">Non-zero, non-negative integer that specified the number of the hash function to use.</param>
            public int UniversalHash(string key, int whichHashFunction)
            {
                if (string.IsNullOrEmpty(key))
                    throw new ArgumentException("Key is either an empty string or null.");

                int prehash = 0;
                var characters = key.ToCharArray();
                int n = characters.Length;

                for (int i = 0; i < n; ++i)
                {
                    prehash = prehash + (characters[i] ^ (n - 1));
                }

                return UniversalHash(prehash, whichHashFunction);
            }
        }

}