using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SkipList
{
    [DebuggerTypeProxy(typeof(SkipListProxy<,>))]
    [DebuggerDisplay("Count = {Count}")]
    public class SkipList<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
    {
        private readonly Random _rnd = new Random();
        private const double Probability = 0.5;
        private const int MaxLevel = 30;

        private IComparer<TKey> _comparer;
        private Node[] _heads;
        private int _count;
        private int _currentLevel;
        private int _version;

        public int Count { get { return _count; } }
        public IComparer<TKey> Comparer { get { return _comparer; } }

        public SkipList() : this(null) { }

        public SkipList(IComparer<TKey> comparer)
        {
            _heads = new Node[MaxLevel+1];
            for (int i = 0; i < _heads.Length; i++)
                _heads[i] = new Node();

            _count = 0;
            _currentLevel = 0;
            _version = 0;
            _comparer =comparer ?? Comparer<TKey>.Default;
        }

        public void Add(TKey key, TValue value)
        {
            _version++;
            var pathArray = new Node[_currentLevel + 1];
            var level = GetRandomLevel();
            var node = _heads[_currentLevel];
            if (_count == 0)
            {
                node.Next = new Node(key, value);
                for (int i = 0; i < level; i++)
                {
                    var newHead = new Node();
                    newHead.Next = new Node(key, value) { Down = _heads[_currentLevel].Next };
                    newHead.Down = _heads[_currentLevel];
                    _heads[_currentLevel+1] = newHead;
                    _currentLevel++;
                }
                _count++;
                return;
            }

            Node nextNode;
            Node previous;
            for (int i = _currentLevel; i > level; i--)//Без добавления
            {
                nextNode = node.Next;
                if (nextNode != null && _comparer.Compare(key, nextNode.Key) > 0)
                {
                    do
                    {
                        previous = nextNode;
                        nextNode = nextNode.Next;
                    } while (nextNode != null && _comparer.Compare(key, nextNode.Key) > 0);
                    node = previous.Down;
                    continue;
                }
                node = node.Down;
            }

            var temp = Math.Min(level, _currentLevel);
            nextNode = node.Next;
            if (nextNode != null && _comparer.Compare(key, nextNode.Key) > 0)
            {
                do
                {
                    previous = nextNode;
                    nextNode = nextNode.Next;
                } while (nextNode != null && _comparer.Compare(key, nextNode.Key) > 0);
                previous.Next = new Node(key, value) { Next = previous.Next };
                pathArray[temp] = previous.Next;
                node = previous.Down;
            }
            else
            {
                node.Next = new Node(key, value) { Next = node.Next };
                pathArray[temp] = node.Next;
                node = node.Down;
            }

            for (int i = temp - 1; i >= 0; i--)
            {
                nextNode = node.Next;
                if (nextNode != null && _comparer.Compare(key, nextNode.Key) > 0)
                {
                    do
                    {
                        previous = nextNode;
                        nextNode = nextNode.Next;
                    } while (nextNode != null && _comparer.Compare(key, nextNode.Key) > 0);
                    previous.Next = new Node(key, value) { Next = previous.Next };
                    pathArray[i] = previous.Next;
                    pathArray[i + 1].Down = previous.Next;
                    node = previous.Down;
                    continue;
                }
                node.Next = new Node(key, value) { Next = node.Next };
                pathArray[i] = node.Next;
                pathArray[i + 1].Down = node.Next;
                node = node.Down;
            }
            _count++;
            if (pathArray[0].Next != null && _comparer.Compare(key, pathArray[0].Next.Key) == 0)
                throw new ArgumentException("Элемент с таким ключем уже существует.", nameof(key));

            if (_currentLevel < level)
            {
                Node newHead;
                newHead = new Node() { Down = _heads[_currentLevel] };
                newHead.Next = new Node(key, value) { Down = pathArray[pathArray.Length - 1] };
                _heads[_currentLevel+1] = newHead;
                for (int i = _currentLevel + 1; i < level; i++)
                {
                    newHead = new Node() { Down = _heads[i] };
                    newHead.Next = new Node(key, value) { Down = _heads[i].Next };
                    _heads[i+1] = newHead;
                }
                _currentLevel = level;
            }
        }

        public bool Remove(TKey key)
        {
            _version++;
            var node = _heads[_currentLevel];
            Node nextNode = null;
            Node previous = null;
            bool isDeleted = false;
            while (node != null)
            {
                previous = node;
                nextNode = node.Next;
                while (nextNode != null && _comparer.Compare(key, nextNode.Key) > 0)
                {
                    previous = nextNode;
                    nextNode = nextNode.Next;
                }
                if (previous.Next != null && _comparer.Compare(key, previous.Next.Key) == 0)
                {
                    isDeleted = true;
                    previous.Next = previous.Next.Next;
                }

                node = previous.Down;
            }

            if (isDeleted)
            {
                for (int i = _currentLevel; i > 0; i--)
                {
                    if (_heads[_currentLevel].Next == null) _currentLevel--;
                    else break;
                }
                _count--;
            }

            return isDeleted;
        }

        public bool Containts(TKey key)
        {
            return FindNode(key) != null;
        }

        public TValue this[TKey ind]
        {
            get
            {
                var node = FindNode(ind);
                if (node == null) throw new ArgumentOutOfRangeException(nameof(ind));
                return node.Value;
            }
            set
            {
                var node = FindNode(ind);
                if (node == null) throw new ArgumentOutOfRangeException(nameof(ind));
                while (node != null)
                {
                    node.Value = value;
                    node = node.Down;
                }
            }

        }


#if DEBUG
        public TKey GetFirstKey()
        {
            return _heads[_currentLevel].Next.Key;
        }
#endif

        public TKey[] GetRange()
        {
            if (_count == 0) return new TKey[0];
            var keys = GetRangeAtLevel(0);
            return keys;
        }

        public Dictionary<int, TKey[]> GetAllLevels()
        {
            var dict = new Dictionary<int, TKey[]>();
            for (int level = _currentLevel; level >= 0; level--)
            {
                dict[level] = GetRangeAtLevel(level);
            }
            return dict;
        }
        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        private class Node
        {
            public TKey Key;
            public TValue Value;
            public Node Next;
            public Node Down;

            public Node() { }
            public Node(TKey key, TValue value)
            {
                Key = key;
                Value = value;
            }
        }

        private struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
        {
            private SkipList<TKey, TValue> list;
            private Node current;
            private int version;
            public KeyValuePair<TKey, TValue> Current { get { return new KeyValuePair<TKey, TValue>(current.Key, current.Value); } }

            public Enumerator(SkipList<TKey, TValue> list)
            {
                this.list = list;
                current = list._heads[0];
                version = list._version;
            }
            public void Dispose() { }

            public bool MoveNext()
            {
                if (version != list._version) throw new InvalidOperationException(nameof(list));
                current = current.Next;
                return current != null;
            }

            public void Reset()
            {
                current = list._heads[0];
                version = list._version;
            }

            object IEnumerator.Current
            {
                get { return Current; }
            }
        }

        #region Методы для внутреннего использования

        private Node FindNode(TKey key)
        {
            var node = _heads[_currentLevel];
            Node nextNode = null;
            Node previous = null;
            while (node != null)
            {
                previous = node;
                nextNode = node.Next;
                while (nextNode != null && _comparer.Compare(key, nextNode.Key) > 0)
                {
                    previous = nextNode;
                    nextNode = nextNode.Next;
                }
                if (previous.Next != null && _comparer.Compare(key, previous.Next.Key) == 0)
                {
                    return previous.Next;
                }
                node = previous.Down;
            }
            return null;
        }

        private TKey[] GetRangeAtLevel(int level)
        {
            if (level < 0 || level > _currentLevel) return new TKey[0];
            var node = _heads[level];
            var list = new List<TKey>();
            node = node.Next;
            while (node != null)
            {
                list.Add(node.Key);
                node = node.Next;
            }
            return list.ToArray();
        }

        private int GetRandomLevel()
        {
            var level = 0;
            for (int i = 0; i < MaxLevel; i++)
            {
                var temp = _rnd.NextDouble();
                if (temp <= Probability) level++;
                else break;
            }
            return level;
        }

        #endregion
    }

    internal class SkipListProxy<K,V>
    {
        private SkipList<K, V> _skipList;

        public SkipListProxy(SkipList<K, V> skipList)
        {
            _skipList = skipList;
        }

        [DebuggerBrowsable(DebuggerBrowsableState.Collapsed)]
        public KeyValuePair<K,V>[] Items
        {
            get { return _skipList.ToArray(); }
        }
    }
}