using System;
using System.Collections.Generic;

namespace CircualBuffer
{
    class MainClass
    {
        public static void Main (string[] args)
        {
//          var bufferItems = new BufferItem[] {
//              new BufferItem("001", "foo"),
//              new BufferItem("001", "bar"),
//              new BufferItem("001", "baz"),
//              new BufferItem("002", "foo"),
//              new BufferItem("002", "baz"),
//              new BufferItem("003", "foo"),
//              new BufferItem("004", "foo"),
//              new BufferItem("005", "foo"),
//              new BufferItem("006", "foo"),
//              new BufferItem("006", "bar"),
//              new BufferItem("006", "baz"),
//          };

//          var bufferItems = new BufferItem[] {
//              new BufferItem("1", ""),
//              new BufferItem("1", ""),
//              new BufferItem("1", ""),
//              new BufferItem("1", ""),
//              new BufferItem("2", ""),
//              new BufferItem("2", ""),
//              new BufferItem("3", ""),
//              new BufferItem("3", "")
//          };

            var bufferItems = new BufferItem[] {
                new BufferItem("1", ""),
                new BufferItem("1", ""),
                new BufferItem("1", ""),
                new BufferItem("2", ""),
                new BufferItem("2", ""),
                new BufferItem("3", ""),
                new BufferItem("4", ""),
                new BufferItem("5", ""),
                new BufferItem("6", ""),
                new BufferItem("6", ""),
                new BufferItem("6", "")
            };


            var result = BufferItemSorter.Sort (bufferItems);

            for (int i = 0; i < result.Length; i++)
            {
                Console.Write (result [i].Preffix);
                Console.Write (":");
                Console.Write (result [i].Value);

                Console.WriteLine ();
            }

            Console.ReadLine ();
        }
    }

    public static class BufferItemSorter
    {
        public static BufferItem[] Sort(BufferItem[] items)
        {
            var sortedItems = CreateSortedArrayCopy(items, new BufferItemComparer());

            var clusters = CreateClusters(sortedItems);

            if (clusters.Length == 1)
            {
                throw new ArgumentException ("argument sequence contains same preffix");
            }

            if (clusters [0].Length == 1)
            {
                return sortedItems;
            }

            var resultItems = new BufferItem[items.Length];
            var busySlots = new bool[items.Length];

            for (int i = 0; i < clusters[0].Length; i++)
            {
                var itemPosition = i * clusters [0].MinDistance;
                resultItems [itemPosition] = sortedItems [clusters [0].StartIndex + i];
                busySlots[itemPosition] = true;
            }

            for (int i = 1; i < clusters.Length; i++)
            {
                var currentCluster = clusters[i];

                var itemPosition = i;
                for (var j = 0; j < currentCluster.Length; j++)
                {
                    if (j != 0)
                    {
                        itemPosition = itemPosition + currentCluster.MinDistance;
                    }

                    while (busySlots[itemPosition] != false)
                    {
                        itemPosition++;
                    }

                    resultItems [itemPosition] = sortedItems [currentCluster.StartIndex + j];
                    busySlots[itemPosition] = true;
                }
            }

            return resultItems;
        }

        private static T[] CreateSortedArrayCopy<T>(T[] items, IComparer<T> comparer)
        {
            var buffer = new T[items.Length];
            Array.Copy(items, buffer, buffer.Length);
            Array.Sort(buffer, comparer);

            return buffer;
        }

        private static ClusterData[] CreateClusters (BufferItem[] sortedItems)
        {
            var clusterList = new LinkedList<ClusterData> ();

            var index = 1;
            var clusterStartIndex = 0;
            while (index < sortedItems.Length)
            {
                var lastItem = sortedItems.Length - index == 1;
                if (sortedItems[index].Preffix != sortedItems[clusterStartIndex].Preffix || lastItem)
                {
                    var clusterLength = index - clusterStartIndex;
                    if (lastItem)
                    {
                        clusterLength++;
                    }
                    var minDistance = sortedItems.Length / clusterLength;
                    var maxDistance = sortedItems.Length % clusterLength > 0
                            ? minDistance + 1
                            : minDistance;
                    var cluster = new ClusterData(minDistance, maxDistance, clusterStartIndex, clusterLength);
                    clusterList.AddLast (cluster);

                    clusterStartIndex = index;
                }

                index++;
            }

            var resultArray = new ClusterData[clusterList.Count];
            var arrayIndex = 0;
            foreach (var cluster in clusterList)
            {
                resultArray [arrayIndex] = cluster;
                arrayIndex++;
            }
            var sortedArray = CreateSortedArrayCopy (resultArray, new ClusterDataLengthDescComparer ());

            return sortedArray;
        }

        private struct ClusterData
        {
            public readonly int MinDistance;

            public readonly int MaxDistance;

            public readonly int StartIndex;

            public readonly int Length;

            public ClusterData(int minDistance, int maxDistaince, int startIndex, int length)
            {
                MinDistance = minDistance;
                MaxDistance = maxDistaince;
                StartIndex = startIndex;
                Length = length;
            }
        }

        private class ClusterDataLengthDescComparer : IComparer<ClusterData>
        {
            public int Compare(ClusterData val1, ClusterData val2)
            {
                return val1.Length.CompareTo (val2.Length) * -1;
            }
        }
    }

    public struct BufferItem
    {
        public readonly string Preffix;

        public readonly string Value;

        public BufferItem(string preffix, string value)
        {
            Preffix = preffix;
            Value = value;
        }
    }

    public class BufferItemComparer : IComparer<BufferItem>
    {
        public int Compare(BufferItem val1, BufferItem val2)
        {
            var compareResult = val1.Preffix.CompareTo (val2.Preffix);

            if (compareResult != 0)
            {
                return compareResult;
            }

            return val1.Value.CompareTo (val2.Value);
        }
    }
}