using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Runtime.CompilerServices;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading.Tasks;
using System.Threading.Tasks.Dataflow;

namespace Program 
{
    class program
    {
        static void Main(string[] args)
        {
            //reading the 3 road files with 256 values into arrays
            string[] road1_256 = System.IO.File.ReadAllLines("path");
            string[] road2_256 = System.IO.File.ReadAllLines("path");
            string[] road3_256 = System.IO.File.ReadAllLines("path");

            //sorting arrays using quicksort algorithm in ascending order
            quicksort(road1_256, 0, road1_256.Length - 1, true);
            quicksort(road2_256, 0, road2_256.Length - 1, true);
            quicksort(road3_256, 0, road3_256.Length - 1, true);

            //output every 10th value of arrays sorted in ascending order
            Console.WriteLine("every 10th value of arrays in ascending order: ");
            Console.WriteLine("road1_256.txt: ");
            for (int i = 0; i < road1_256.Length; i += 10)
            {
                Console.WriteLine(road1_256[i]);
            }
            Console.WriteLine("road2_256.txt: ");
            for (int i = 0; i < road2_256.Length; i += 10)
            {
                Console.WriteLine(road2_256[i]);
            }
            Console.WriteLine("road3_256.txt: ");
            for (int i = 0; i < road3_256.Length; i += 10)
            {
                Console.WriteLine(road3_256[i]);
            }

            //sorting arrays using quicksort algorithm in descending order
            quicksort(road1_256, 0, road1_256.Length - 1, false);
            quicksort(road2_256, 0, road2_256.Length - 1, false);
            quicksort(road3_256, 0, road3_256.Length - 1, false);

            //output every 10th value of arrays sorted in descending order
            Console.WriteLine("every 10th value of arrays in descending order: ");
            Console.WriteLine("road1_256.txt: ");
            for (int i = 0; i < road1_256.Length; i += 10)
            {
                Console.WriteLine(road1_256[i]);
            }
            Console.WriteLine("road2_256.txt: ");
            for (int i = 0; i < road2_256.Length; i += 10)
            {
                Console.WriteLine(road2_256[i]);
            }
            Console.WriteLine("road3_256.txt: ");
            for (int i = 0; i < road3_256.Length; i += 10)
            {
                Console.WriteLine(road3_256[i]);
            }
            List<int> binarySearch(string[] road, int val, int left, int right)
            {
                List<int> occ = new List<int>();
                int mid = (right + left) / 2;
                if (right < left)
                {
                    return occ;
                }
                if (val > road[mid])
                {
                    return binarySearch(road, val, mid + 1, right);
                }
                else if (val < road[mid])
                {
                    return binarySearch(road, val, left, mid - 1);
                }
                else
                {
                    occ.Add(mid);
                    return mid;
                }


            }
        }

        static void quicksort(string[] road, int start, int stop, bool ascending) //array of numbers, left, right, ascending or descending
        {
            //left most value is the start, right most is the stop value. if start is less that stop, partitions array
            //into 2 halves with elements less than pivot on left, and values larger than pivot on the right.
            if (stop > start)
            {
                int pivot = partition(road, start, stop, ascending);
                quicksort(road, start, pivot - 1, ascending);
                quicksort(road, pivot + 1, stop, ascending);
            }
        }
        static int partition(string[] road, int start, int stop, bool ascending)
        {
            string pivotval = road[stop]; //last element is pivot
            int pivotindex = start;

            for (int i = start; i < stop; i++)
            {
                //If an element is less than or greater than (depending on order)
                //the pivot value, swap with element at pivotindex and increment pivotindex
                if ((ascending && int.Parse(road[i]) < int.Parse(pivotval)) || (!ascending && int.Parse(road[i]) > int.Parse(pivotval)))
                {
                    swap(road, i, pivotindex);
                    pivotindex++;
                }
            }
            swap(road, pivotindex, stop);
            return pivotindex;
        }
        static void swap(string[] road, int i, int j)
        {
            //swapping i and j
            string temp = road[i];
            road[i] = road[j];
            road[j] = temp;
        }
    }
}