using System;
using System.Collections.Generic;

namespace PortsManager
{
    class PortsManager
    {
        int count = 0;

        readonly (int minPort, int maxPort) range;

        LinkedList<(int minPort, int maxPort)> ranges = new LinkedList<(int, int)>();

        internal PortsManager(int minPort, int maxPort)
        {
            count = maxPort - minPort + 1;
            range = (minPort, maxPort);
            ranges.AddLast(range);
        }

        internal int Count { get => count; }

        internal bool IsPortAvailable(int port)
        {
            if (port < range.minPort || port > range.maxPort)
            {
                return false;
            }

            for (var node = ranges.First; node != null; node = node.Next)
            {
                var range = node.Value;
                if (port >= range.minPort && port <= range.maxPort)
                {
                    return true;
                }
            }
            return false;
        }

        internal int? GetPort()
        {
            if (ranges.Count > 0)
            {
                var range = ranges.First.Value;
                int port = range.minPort++;
                ranges.RemoveFirst();
                if (range.minPort <= range.maxPort)
                {
                    ranges.AddFirst(range);
                }
                --count;
                return port;
            }
            return null;
        }

        internal void ReturnPort(int port)
        {
            if (port < range.minPort || port > range.maxPort)
            {
                return;
            }

            ++count;
            for (var node = ranges.First; node != null; node = node.Next)
            {
                var range = node.Value;
                if (port < range.minPort)
                {
                    if (port == range.minPort - 1)
                    {
                        if (node.Previous != null && port == node.Previous.Value.maxPort + 1)
                        {
                            // the port bridges the gap between two adjacent ranges, merge them
                            range.minPort = node.Previous.Value.minPort;
                            ranges.Remove(node.Previous);
                        }
                        else
                        {
                            // just merge the port into the current range
                            --range.minPort;
                        }
                        var next = node.Next;
                        ranges.Remove(node);
                        node = next != null ? ranges.AddBefore(next, range) : ranges.AddLast(range);
                        return;
                    }
                    if (node.Previous != null)
                    {
                        if (port == node.Previous.Value.maxPort + 1)
                        {
                            // merge with the previous node, and done
                            range.minPort = node.Previous.Value.minPort;
                            range.maxPort = node.Previous.Value.maxPort + 1;
                            ranges.Remove(node.Previous);
                            ranges.AddBefore(node, range);
                            return;
                        }
                    }
                    // add a new range
                    ranges.AddBefore(node, (port, port));
                    return;
                }
                else if (port <= range.maxPort)
                {
                    --count; // NB: this is the only scenario where 'count' shouldn't be incremented
                    return;
                }
                else if (node.Next == null)
                {
                    if (port == range.maxPort + 1)
                    {
                        ++range.maxPort;
                        ranges.RemoveLast();
                        ranges.AddLast(range);
                        return;
                    }
                }
            }

            // if control comes here, the port forms the last range
            ranges.AddLast((port, port));
        }

        internal void VerifyIntegrity()
        {
            int count = 0;
            for (var node = ranges.First; node != null; node = node.Next)
            {
                var range = node.Value;
                System.Diagnostics.Debug.Assert(range.minPort <= range.maxPort);
                count += range.maxPort - range.minPort + 1;

                if (node.Previous != null)
                {
                    System.Diagnostics.Debug.Assert(node.Previous.Value.maxPort < range.minPort - 1);
                }
            }
            System.Diagnostics.Debug.Assert(count == this.count);
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            PortsManager pm = new PortsManager(1, 100);

            Random rnd = new Random();
            for (var c = 0; c < 100; ++c)
            {
                for (var i = 0; i < 50; ++i)
                {
                    var port = pm.GetPort();
                    Console.WriteLine($"GetPort: {port}");
                }
                pm.VerifyIntegrity();
                Console.WriteLine($"Count: {pm.Count}");
                for (var i = 0; i < 100; ++i)
                {
                    var port = rnd.Next(1, 100);
                    Console.WriteLine($"ReturnPort: {port}");
                    pm.ReturnPort(port);
                }
                pm.VerifyIntegrity();
                Console.WriteLine($"Count: {pm.Count}");
            }
        }
    }
}