using System.Diagnostics;
using System;
using System.Collections.Generic;
using System.Security.Cryptography;

namespace projekt
{
    internal class Program
    {
        static private ulong numberOfOperations = 0;
        static int[] GenerateVector(int vectorLength)
        {
            int[] vector = new int[vectorLength];
            for (int i = 0; i < vectorLength; i++)
            {
                vector[i] = i;
            }

            return vector;
        }

        static bool IsPresentBinary(int[] vector, int number)
        {
            int left = 0, right = vector.Length - 1, middle;
            while (left <= right)
            {
                middle = (left + right) / 2;
                if (vector[middle] == number) return true;
                else if (vector[middle] > number) right = middle - 1;
                else left = middle + 1;
            }

            return false;
        }

        static bool IsPresentBinaryInstr(int[] vector, int number)
        {
            numberOfOperations = 0;

            int left = 0, right = vector.Length - 1, middle;

            while (left <= right)
            {
                numberOfOperations++;
                middle = (left + right) / 2;
                if (vector[middle] == number)
                {
                    return true;
                }

                numberOfOperations++;
                if (vector[middle] > number)
                {
                    right = middle - 1;
                }
                else left = middle + 1;
            }

            return false;
        }

        static bool IsPresentLinear(int[] vector, int number)
        {
            for (int i = 0; i < vector.Length; i++)
            {
                if (vector[i] == number) return true;
            }

            return false;
        }

        static bool IsPresentLinearInstr(int[] vector, int number)
        {
            numberOfOperations = 0;
            for (int i = 0; i < vector.Length; i++)
            {
                numberOfOperations++;
                if (vector[i] == number) return true;
            }

            return false;
        }

        static void BinaryMaxInstr(int[] testVector)
        {
            IsPresentBinaryInstr(testVector, testVector.Length + 1);
            Console.Write(numberOfOperations + "\t");
        }

        static void LinearMaxInstr(int[] testVector)
        {
            IsPresentLinearInstr(testVector, testVector.Length + 1);
            Console.Write(numberOfOperations + "\t");
        }

        static void BinaryMaxTime(int[] testVector)
        {
            int nIter = 10;
            double elapsedSeconds;
            long elapsedTime = 0, minTime = long.MaxValue, maxTime = long.MinValue, iterationElapsedTime;
            for (int n = 0; n < nIter + 2; ++n)
            {
                long startingTime = Stopwatch.GetTimestamp();
                IsPresentBinary(testVector, testVector.Length + 1);
                long endingTime = Stopwatch.GetTimestamp();
                iterationElapsedTime = endingTime - startingTime;

                elapsedTime += iterationElapsedTime;
                if (iterationElapsedTime < minTime) minTime = iterationElapsedTime;
                if (iterationElapsedTime > maxTime) maxTime = iterationElapsedTime;
            }

            elapsedTime -= (minTime + maxTime);
            elapsedSeconds = elapsedTime * (1.0 / (nIter * Stopwatch.Frequency));
            Console.Write("\t\t" + elapsedSeconds.ToString("F4"));
        }

        static void LinearMaxTime(int[] testVector)
        {
            int nIter = 10;
            double elapsedSeconds;
            long elapsedTime = 0, minTime = long.MaxValue, maxTime = long.MinValue, iterationElapsedTime;
            for (int n = 0; n < nIter + 2; ++n)
            {
                long startingTime = Stopwatch.GetTimestamp();
                IsPresentLinear(testVector, testVector.Length + 1);
                long endingTime = Stopwatch.GetTimestamp();
                iterationElapsedTime = endingTime - startingTime;

                elapsedTime += iterationElapsedTime;
                if (iterationElapsedTime < minTime) minTime = iterationElapsedTime;
                if (iterationElapsedTime > maxTime) maxTime = iterationElapsedTime;
            }

            elapsedTime -= (minTime + maxTime);
            elapsedSeconds = elapsedTime * (1.0 / (nIter * Stopwatch.Frequency));
            Console.Write("\t" + elapsedSeconds.ToString("F4"));
        }

        static void LinearMeanInstr(int[] testVector)
        {
            int sampleSize = 100, sample = testVector.Length / sampleSize;
            ulong operations = 0;

            for (int i = 0; i <= testVector.Length; i += sample)
            {
                IsPresentLinearInstr(testVector, i);
                operations += numberOfOperations;
            }
            Console.Write(operations/(ulong)sampleSize + "\t");

        }

        static void LinearMeanTime(int[] testVector)
        {
            int sampleSize = 100, sample = testVector.Length / sampleSize;
            double sumTime = 0;

            for (int i = 0; i <= testVector.Length; i += sample)
            {
                int nIter = 5;
                double elapsedSeconds;
                long elapsedTime = 0, minTime = long.MaxValue, maxTime = long.MinValue, iterationElapsedTime;
                for (int n = 0; n < nIter + 2; ++n)
                {
                    long startingTime = Stopwatch.GetTimestamp();
                    IsPresentLinear(testVector, i);
                    long endingTime = Stopwatch.GetTimestamp();
                    iterationElapsedTime = endingTime - startingTime;

                    elapsedTime += iterationElapsedTime;
                    if (iterationElapsedTime < minTime) minTime = iterationElapsedTime;
                    if (iterationElapsedTime > maxTime) maxTime = iterationElapsedTime;
                }

                elapsedTime -= (minTime + maxTime);
                elapsedSeconds = elapsedTime * (1.0 / (nIter * Stopwatch.Frequency));
                sumTime += elapsedSeconds;
            }
            Console.Write( (sumTime/sampleSize).ToString("F4") + "\t");
        }

        static int[] GenerateIndexes(int[] vector)
        {
            List<int[]> listOfIndexes = new List<int[]>();

            int max = vector.Length - 1, index, elementsLeft= vector.Length, elementsOnLevel=1;
            index = max/2;

            while (index > 0)
            {
                if (elementsLeft - elementsOnLevel < 0)
                {
                    elementsOnLevel = elementsLeft;
                }
                int[] temp = new int[2];

                temp[0] = index;
                temp[1] = elementsOnLevel;
                listOfIndexes.Add(temp);

                elementsLeft -= elementsOnLevel;
                index = index / 2;
                elementsOnLevel *= 2;

            }

            foreach (var arr in listOfIndexes)
            {
                foreach (var VARIABLE in arr)
                {
                    Console.Write(VARIABLE+",");
                }
                Console.Write(" ");
            }

            return null;

        }

        static bool IsPresentBinaryMockup(int[] vector, int number)
        {
            int left = 0, right = vector.Length - 1, middle;
            Console.Write("IsPresentBinaryMockup:  ");

            while (left <= right)
            {
                middle = (left + right) / 2;
                Console.Write(middle+";");
                if (vector[middle] == number) return true;
                else if (vector[middle] > number) right = middle - 1;
                else left = middle + 1;
            }

            return false;
        }


        static void BinaryMeanInstr(int[] testVector)
        {
            Console.WriteLine();
        }

        public static void Main(string[] args)
        {
//            Console.WriteLine("vLength\t\tLinMaxInstr\tBinMaxInstr\tLinMaxTime\tBinMaxTime");
//                for (int vectorLength = 10737418; vectorLength <= 268435450 ; vectorLength += 10737418)
//                {
//                    Console.Write(vectorLength + "\t");
//                    int[] testVector = generateVector(vectorLength);
//                    LinearMaxInstr(testVector);
//                    BinaryMaxInstr(testVector);
//                    LinearMaxTime(testVector);
//                    BinaryMaxTime(testVector);
//                    Console.WriteLine();
//                }



            IsPresentBinaryMockup(GenerateVector(7),-1);
            Console.WriteLine();
            GenerateIndexes(GenerateVector(7));


            Console.WriteLine("vLength\t\tLinMeanIns\tLinMeanTime");
            for (int vectorLength = 10737418; vectorLength <= 268435450 ; vectorLength += 10737418)
                {
                    Console.Write(vectorLength + "\t");
                    int[] testVector = GenerateVector(vectorLength);
//                    LinearMeanInstr(testVector);
//                    LinearMeanTime(testVector);
                    Console.WriteLine();
                }

        }
    }
}