// Copyright 2017 by Mikron
// This piece of code distributed under terms of BSD License and without any warranty.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

namespace MergeSort
{
    class Program
    {

        const int MAX_TEMP_FILES = 14;                  // Prefered size must be 2^n - 2, n > 1
        const int MAX_HEAP_SIZE = (1 << 16) - 1;        // Adjust accordingly to available memmory 

        static readonly Comparison<string> StringComparison = string.CompareOrdinal;
        static readonly Comparison<IEnumerator<string>> StringEnumeratorComparison = (x, y) => string.CompareOrdinal(x.Current, y.Current);

        static void Main(string[] args)
        {
            if (args.Length < 2)
            {
                Console.WriteLine("Usage: {0} <source:_file> <target_file>");
                return;
            }
            var target = new Lazy<FileStream>[MAX_TEMP_FILES / 2];
            var source = new Lazy<FileStream>[MAX_TEMP_FILES - target.Length];
            try
            {
                Func<FileStream> createTempFile = () => new FileStream(Path.GetTempFileName(), FileMode.Create, FileAccess.ReadWrite, FileShare.Read);
                for (var i = 0; i < target.Length; i += 1)
                {
                    target[i] = new Lazy<FileStream>(createTempFile);
                }
                for (var i = 0; i < source.Length; i += 1)
                {
                    source[i] = new Lazy<FileStream>(createTempFile);
                }
                int splitter;
                var timer = new Stopwatch();
                timer.Start();
                using (var sourceFile = new FileStream(args[0], FileMode.Open, FileAccess.Read, FileShare.Read))
                {
                    splitter = Split(MAX_HEAP_SIZE, ReadLines(sourceFile), source);
                }
                int runNo = 0;
                while (splitter > 1)
                {
                    var sourceReq = from s in source select ReadLines(s.Value);
                    splitter = Split(MAX_HEAP_SIZE, Merge(sourceReq.ToArray()), target);
                    var swapTmp = source;
                    source = target;
                    target = swapTmp;
                    foreach (var f in target)
                    {
                        if (f.IsValueCreated)
                        {
                            f.Value.Seek(0, SeekOrigin.Begin);
                            f.Value.SetLength(0);
                        }
                    }
                    runNo += 1;
                }
                timer.Stop();
                Console.WriteLine("Total number of Split/Merge runs: {0,8} in {1} ", runNo, timer.Elapsed);

                source[0].Value.Close();
                File.Move(source[0].Value.Name, args[1]);
                source[0].Value.Dispose();
                source[0] = null;
            }
            finally
            {
                Action<Lazy<FileStream>> cleanUp = (f) =>
                {
                    if (f != null && f.IsValueCreated)
                    {
                        f.Value.Close();
                        File.Delete(f.Value.Name);
                        f.Value.Dispose();
                    }
                };
                foreach (var f in source)
                    cleanUp(f);
                foreach (var f in target)
                    cleanUp(f);
            }
        }

        static IEnumerable<string> ReadLines(FileStream fileStream)
        {
            fileStream.Seek(0, SeekOrigin.Begin);
            using (var reader = new StreamReader(fileStream, Encoding.Default, true, 4096, true))
            {
                string line;
                while ((line = reader.ReadLine()) != null)
                    yield return line;
            }
        }

        static int Split(int heapCapacity, IEnumerable<string> source, Lazy<FileStream>[] destination)
        {
            var heap = new string[heapCapacity];
            var writers = new StreamWriter[destination.Length];
            int targets = 0;
            var ii = source.GetEnumerator();
            try
            {
                int writerIndex = 0;
                long numberOfReadLines = 0L;
                long numberOfSwitches = 0L;
                long longestStrip = 0L;
                long shortestStrip = long.MaxValue;
                int heapSize = 0;
                while (true)
                {
                    // Fill heap
                    while (heapSize < heapCapacity && ii.MoveNext())
                    {
                        heap[heapSize] = ii.Current;
                        BubbleUp(heap, heapSize, StringComparison);
                        heapSize += 1;
                    }
                    if (heapSize == 0)
                        break;
                    // Prepare for wrining next strip
                    long stripLength = 0L;
                    var writer = writers[writerIndex];
                    if (writer == null)
                    {
                        targets += 1;
                        var stream = destination[writerIndex].Value;
                        stream.Seek(0, SeekOrigin.Begin);
                        stream.SetLength(0);
                        writer = writers[writerIndex] = new StreamWriter(stream, Encoding.Default, 4096, true);
                    }
                    writerIndex = (writerIndex + 1) % writers.Length;

                    // Process lines
                    string priorLine = null;
                    while (true)
                    {
                        var line = heap[0];
                        var gapPos = RemoveHead(heap, heapSize, StringComparison);
                        if (priorLine != null && StringComparison(priorLine, line) > 0)
                        {
                            // Here I can be sure, all other elements in heap are above of priorLine
                            // So just flush them out and put line again in heap for begining of the next strip
                            heap[gapPos] = heap[--heapSize];
                            BubbleUp(heap, gapPos, StringComparison);
                            priorLine = line;       
                            break;
                        }
                        writer.WriteLine(line);
                        stripLength += 1L;
                        priorLine = line;
                        if (!ii.MoveNext())
                        {
                            heap[gapPos] = heap[--heapSize];
                            BubbleUp(heap, gapPos, StringComparison);
                            priorLine = null;       // Don't put prior line into heap again
                            break;
                        }
                        heap[gapPos] = ii.Current;
                        BubbleUp(heap, gapPos, StringComparison);
                    }

                    // Empty heap
                    if (heapSize > 0)
                    {
                        stripLength += heapSize;
                        while (true)
                        {
                            writer.WriteLine(heap[0]);
                            var gapPos = RemoveHead(heap, heapSize, StringComparison);
                            if (--heapSize <= 0)
                                break;
                            heap[gapPos] = heap[heapSize];
                            BubbleUp(heap, gapPos, StringComparison);
                        }
                    }
                    longestStrip = Math.Max(longestStrip, stripLength);
                    shortestStrip = Math.Min(shortestStrip, stripLength);
                    numberOfReadLines += stripLength;
                    numberOfSwitches += 1;
                    if (priorLine != null)
                    {
                        heap[heapSize] = priorLine;
                        BubbleUp(heap, heapSize, StringComparison);
                        heapSize += 1;
                    }
                }
                Console.WriteLine("Lines {0,8} Switches {1,8} Strip Min {2,8} Max {3,8} Avg {4,9:F5}", numberOfReadLines, numberOfSwitches,
                    shortestStrip, longestStrip, numberOfReadLines / (double) numberOfSwitches);
            }
            finally
            {
                ii.Dispose();
                foreach(var w in writers)
                {
                    if (w != null)
                        w.Dispose();
                }
            }
            return targets;
        }

        static int Split(IEnumerable<string> source, Lazy<FileStream>[] destination)
        {
            var writers = new StreamWriter[destination.Length];
            int targets = 0;
            try
            {
                int writerIndex = 0;
                StreamWriter writer = null;
                long numberOfReadLines = 0L;
                long numberOfSwitches = 0L;
                long longestStrip = 0L;
                long shortestStrip = long.MaxValue;
                long stripLength = 0L;
                string priorLine = null;
                foreach (var line in source)
                {
                    numberOfReadLines += 1;
                    if (writer == null || string.CompareOrdinal(priorLine, line) > 0)
                    {
                        if (stripLength > 0)
                        {
                            longestStrip = Math.Max(longestStrip, stripLength);
                            shortestStrip = Math.Min(shortestStrip, stripLength);
                        }
                        stripLength = 0L;
                        numberOfSwitches += 1;
                        writer = writers[writerIndex];
                        if (writer == null)
                        {
                            targets += 1;
                            var stream = destination[writerIndex].Value;
                            stream.Seek(0, SeekOrigin.Begin);
                            stream.SetLength(0);
                            writer = writers[writerIndex] = new StreamWriter(stream, Encoding.Default, 4096, true);
                        }
                        writerIndex = (writerIndex + 1) % writers.Length;
                    }
                    priorLine = line;
                    writer.WriteLine(line);
                    stripLength += 1L;
                }
                longestStrip = Math.Max(longestStrip, stripLength);
                shortestStrip = Math.Min(shortestStrip, stripLength);
                Console.WriteLine("Lines {0,8} Switches {1,8} Strip Min {2,8} Max {3,8} Avg {4,9:F5}", numberOfReadLines, numberOfSwitches,
                    shortestStrip, longestStrip, numberOfReadLines / (double)numberOfSwitches);
            }
            finally
            {
                foreach (var w in writers)
                {
                    if (w != null)
                        w.Dispose();
                }
            }
            return targets;
        }

        static IEnumerable<string> Merge(params IEnumerable<string>[] sources)
        {
            if (sources == null || sources.Length == 0)
                yield break;
            // Init heap
            var heap = new IEnumerator<string>[sources.Length];
            var length = 0;
            for (int i = 0; i < sources.Length; i += 1)
            {
                var s = sources[i].GetEnumerator();
                if (!s.MoveNext())
                {
                    s.Dispose();
                }
                else
                {
                    heap[length] = s;
                    BubbleUp(heap, length, StringEnumeratorComparison);
                    length += 1;
                }
            }
            // Enumerate
            while(true)
            {
                var s = heap[0];
                yield return s.Current;
                var gapPos = RemoveHead(heap, length, StringEnumeratorComparison);
                if (!s.MoveNext())
                {
                    s.Dispose();
                    if (--length <= 0)
                        break;
                    s = heap[length];
                }
                heap[gapPos] = s;
                BubbleUp(heap, gapPos, StringEnumeratorComparison);
            }
        }


        static int RemoveHead<T>(T[] heap, int length, Comparison<T> comparer)
        {
            int gap = 0;
            while (true)
            {
                var child = 1 + (gap << 1);
                if (child >= length)
                    break;
                if (child + 1 < length && comparer(heap[child], heap[child + 1]) >= 0)
                {
                    child += 1;
                }
                heap[gap] = heap[child];
                gap = child;
            }
            return gap;
        }

        static int BubbleUp<T>(T[] heap, int i, Comparison<T> comparer)
        {
            var s = heap[i];
            while (i > 0)
            {
                int parent = (i - 1) >> 1;
                if (comparer(heap[parent], s) < 0)
                    break;
                heap[i] = heap[parent];
                heap[parent] = s;
                i = parent;
            }
            return i;
        }

    }
}

        static IEnumerable<string> Merge(params IEnumerable<string>[] sources)
        {
            if (sources == null || sources.Length == 0)
                yield break;
            // Init heap
            var heap = new IEnumerator<string>[sources.Length];
            var size = 0;
            for (int i = 0; i < sources.Length; i += 1)
            {
                var s = sources[i].GetEnumerator();
                if (!s.MoveNext())
                {
                    s.Dispose();
                }
                else
                {
                    heap[size] = s;
                    BubbleUp(heap, size, StringEnumeratorComparison);
                    size += 1;
                }
            }
            // Enumerate
            var nextHeap = new IEnumerator<string>[size];
            while (true)
            {
                var nextSize = 0;
                while (true)
                {
                    var h = heap[0];
                    var s = h.Current;
                    yield return s;
                    var gapPos = RemoveHead(heap, size, StringEnumeratorComparison);
                    if (!h.MoveNext())
                    {
                        h.Dispose();
                        if (--size <= 0)
                            break;
                        h = heap[size];
                    }
                    else if (StringComparison(h.Current, s) < 0)
                    {
                        nextHeap[nextSize] = h;
                        BubbleUp(nextHeap, nextSize, StringEnumeratorComparison);
                        nextSize += 1;
                        if (--size <= 0)
                            break;
                        h = heap[size];
                    }
                    heap[gapPos] = h;
                    BubbleUp(heap, gapPos, StringEnumeratorComparison);
                }
                if (nextSize == 0)
                    break;
                size = nextSize;
                var tmp = heap;
                heap = nextHeap;
                nextHeap = tmp;
            }
        }