?using System;
using System.Collections;
using System.Threading;
using LoggingLib.Impl;

namespace WindowsApplication1
{
    /// <summary>
    /// This class sinulates a real processor in the PSRS algorithm.
    /// </summary>
    public class Processor
    {


        protected Processor(int segNum, int[] originalData)
        {
            this.mySegmentNumber = segNum;
            this.myOriginalData = originalData;
            this.mySamplesReady = new AutoResetEvent(false);
            this.GlobalSortedDataOk = new AutoResetEvent(false);
        }

        /// <summary>
        /// Some varirants are initlized here.
        /// </summary>
        private void initlize()
        {
            myGlobalChange = new Semaphore(0, this.ProcessorNumbers);
        }

        /// <summary>
        /// Creat processors that will sort the original datas.
        /// </summary>
        /// <param name="originalData">Original datas that will be sorted.</param>
        /// <param name="num">The number of processors that we want to create</param>
        public static void CreatProcessors(int[] originalData, int num)
        {

            
            if ((num * num) <= originalData.Length)
            {
                processors = new Processor[num];
                for (int i = 0; i < num; i++)
                {
                    processors[i] = new Processor(i, originalData);
                }
                if ((originalData.Length / num) != 0)
                {
                    Processor.countPerProcessor = originalData.Length / num + 1;
                }
                else
                {
                    Processor.countPerProcessor = originalData.Length / num;
                }
                Processor.mainCell = new int[num - 1];
                Processor.mainCellReady = new Semaphore(0, num);
                Processor.myGlobalSortedData = new MyArrayList<int>(originalData.Length);
                Processor.mySamplesNotHandled = true;
            }
            else
            {
                throw new ArgumentException("Create too many processors!");
            }
        }

        /// <summary>
        /// Start processors that have been create in CreatProcessors function.
        /// </summary>
        public static void StartProcessors()
        {
            if (processors != null)
            {
                for (int i = 0; i < processors.Length; i++)
                {
                    Thread t = new Thread(processors[i].Run);
                    t.Start();
                }
            }
        }

        /// <summary>
        /// Wait for sorted datas. Actually this function just waits for the last processor to send the sorted datas to myGlobalSortedData feilds.
        /// </summary>
        public static void WaitSortCompleted()
        {
            processors[processors.Length - 1].GlobalSortedDataOk.WaitOne();
        }

        /// <summary>
        /// Get the proper partitions that should be merge sorted by this processor first. Then sorted these partition with mergesort algorithm. 
        /// Then send the sorted datas to myGlobalSortedData and indicated next processor can send his datas.
        /// </summary>
        public void GlobalExchangeAndSort()
        {
            int[][] partitions = new int[this.ProcessorNumbers][];
            for (int i = 0; i < partitions.Length; i++)
            {
                Processor p = processors[i];
                partitions[i] = p.GetOnePartition(this.SegmentNumber);
                Logger.getInstance().debug(this.Name + " get one partition form " + p.Name);
            }
            int[] sortedData = this.MergeSort(partitions, 0, partitions.Length);
            if (this.SegmentNumber == 0)
            {
                myGlobalSortedData.AddRange(sortedData);
                Logger.getInstance().debug(this.Name + " has added sorted datas to global!");
                this.GlobalSortedDataOk.Set();
            }
            else
            {
                Processor pre = processors[this.SegmentNumber - 1];
                Logger.getInstance().debug(this.Name + " is waiting for " + pre.Name + " to complete its GlobalExchangeAndSort method!");
                pre.GlobalSortedDataOk.WaitOne();
                myGlobalSortedData.AddRange(sortedData);
                Logger.getInstance().debug(this.Name + " has added sorted datas to global!");
                this.GlobalSortedDataOk.Set();
            }
        }

        /// <summary>
        /// Selecte ProcessorNumbers Samples from the local data.
        /// </summary>
        /// <returns></returns>
        public int[] GetSamples()
        {
            this.mySamplesReady.WaitOne();
            int[] samples = new int[this.ProcessorNumbers];
            int delt = this.localData.Length / this.ProcessorNumbers;
            for (int i = 0; i < samples.Length; i++)
            {
                samples[i] = this.localData[delt * i];
            }
            return samples;
        }

        /// <summary>
        /// Return one partition whose partition index is partitionNumber
        /// </summary>
        /// <param name="partitionNumber">The partition index</param>
        /// <returns>The partition with right index</returns>
        public int[] GetOnePartition(int partitionNumber)
        {
            myGlobalChange.WaitOne();
            int startIndex = this.partitionFlags[partitionNumber];
            if (startIndex < 0 || startIndex >= this.localData.Length)
                return null;
            int length = 0;
            if (partitionNumber == (this.ProcessorNumbers - 1))
            {
                length = this.localData.Length - startIndex;
            }
            else
            {
                length = this.partitionFlags[partitionNumber + 1] - startIndex;
            }
            int[] partition = new int[length];
            for (int i = 0; i < length; i++)
            {
                partition[i] = this.localData[startIndex + i];
            }
            return partition;
        }

        /// <summary>
        /// First sort in the PSRS algorithm.
        /// </summary>
        public void LocalSort()
        {
            this.localData = this.Sort(this.myOriginalData, this.Start, this.Length);
            this.mySamplesReady.Set();
        }

        /// <summary>
        /// This method will merge proper arrays to a single sorted array.
        /// </summary>
        /// <param name="arrays">Arrays to be merged</param>
        /// <param name="start">The start array's index to be merged</param>
        /// <param name="length">The length of arrays to be merged</param>
        /// <returns>This array stores the sorted datas.</returns>
        public int[] MergeSort(int[][] arrays, int start, int length)
        {
            if (length < 0)
            {
                throw new ArgumentOutOfRangeException("Argument \"length\" must be greater than 0!");
            }
            if (start < 0 || start >= arrays.Length)
            {
                throw new ArgumentOutOfRangeException("Argument \"start\" is out of range!");
            }
            if (start + length > arrays.Length)
                length = arrays.Length - start;
            if (length == 1)
                return arrays[start];
            else if (length == 2)
            {
                return MergeSort(arrays[start], arrays[start + 1]);
            }
            else
            {
                int[] array1 = MergeSort(arrays, start, length / 2);
                int[] array2 = MergeSort(arrays, start + length / 2, length - length / 2);
                return MergeSort(array1, array2);
            }
        }

        /// <summary>
        /// Merge array1 and array2 to a sorted array(This method implements the merge sort algorithom)
        /// </summary>
        /// <param name="array1"></param>
        /// <param name="array2"></param>
        /// <returns>A sorted array</returns>
        public int[] MergeSort(int[] array1, int[] array2)
        {
            if (array1 == null)
                return array2;
            if (array2 == null)
                return array1;
            int[] result = new int[array1.Length + array2.Length];
            int i = 0;
            int j = 0;
            int k = 0;
            while (i < array1.Length && j < array2.Length)
            {
                if (array1[i] < array2[j])
                {
                    result[k] = array1[i];
                    i++;
                    k++;
                }
                else
                {
                    result[k] = array2[j];
                    j++;
                    k++;
                }
            }
            if (i < array1.Length)
            {
                Array.Copy(array1, i, result, k, array1.Length - i);
            }
            else