using System.Collections;
using System.Collections.Generic;

namespace DataStructures
{
    /// <summary>
    ///     Implementation of SortedList using binary search.
    /// </summary>
    /// <typeparam name="T">Generic Type.</typeparam>
    public class SortedList<T> : IEnumerable<T>
    {
        private readonly IComparer<T> comparer;
        private readonly List<T> memory;

        /// <summary>
        ///     Initializes a new instance of the <see cref="SortedList{T}" /> class. Uses a Comparer.Default for type T.
        /// </summary>
        public SortedList()
            : this(Comparer<T>.Default)
        {
        }

        /// <summary>
        ///     Gets the number of elements containing in <see cref="SortedList{T}" />.
        /// </summary>
        public int Count => memory.Count;

        /// <summary>
        ///     Initializes a new instance of the <see cref="SortedList{T}" /> class.
        /// </summary>
        /// <param name="comparer">Comparer user for binary search.</param>
        public SortedList(IComparer<T> comparer)
        {
            memory = new List<T>();
            this.comparer = comparer;
        }

        /// <summary>
        ///     Adds new item to <see cref="SortedList{T}" /> instance, maintaining the order.
        /// </summary>
        /// <param name="item">An element to insert.</param>
        public void Add(T item)
        {
            var index = IndexFor(item, out _);
            memory.Insert(index, item);
        }

        /// <summary>
        ///     Gets an element of <see cref="SortedList{T}" /> at specified index.
        /// </summary>
        /// <param name="i">Index.</param>
        public T this[int i] => memory[i];

        /// <summary>
        /// Removes all elements from <see cref="SortedList{T}" />.
        /// </summary>
        public void Clear()
            => memory.Clear();

        /// <summary>
        /// Indicates whether a <see cref="SortedList{T}" /> contains a certain element.
        /// </summary>
        /// <param name="item">An element to search.</param>
        /// <returns>true - <see cref="SortedList{T}" /> contains an element, otherwise - false.</returns>
        public bool Contains(T item)
        {
            _ = IndexFor(item, out var found);
            return found;
        }

        /// <summary>
        /// Removes a certain element from <see cref="SortedList{T}" />.
        /// </summary>
        /// <param name="item">An element to remove.</param>
        /// <returns>true - element is found and removed, otherwise false.</returns>
        public bool TryRemove(T item)
        {
            var index = IndexFor(item, out var found);

            if (found)
            {
                memory.RemoveAt(index);
            }

            return found;
        }

        /// <summary>
        /// Returns an enumerator that iterates through the <see cref="SortedList{T}" />.
        /// </summary>
        /// <returns>A Enumerator for the <see cref="SortedList{T}" />.</returns>
        public IEnumerator<T> GetEnumerator()
            => memory.GetEnumerator();

        /// <inheritdoc cref="IEnumerable.GetEnumerator"/>
        IEnumerator IEnumerable.GetEnumerator()
            => GetEnumerator();

        /// <summary>
        /// Binary search algorithm for finding element index in <see cref="SortedList{T}" />.
        /// </summary>
        /// <param name="item">Element.</param>
        /// <param name="found">Indicates whether the equal value was found in <see cref="SortedList{T}" />.</param>
        /// <returns>Index for the Element.</returns>
        private int IndexFor(T item, out bool found)
        {
            var left = 0;
            var right = memory.Count;

            while (right - left > 0)
            {
                var mid = (left + right) / 2;

                switch (comparer.Compare(item, memory[mid]))
                {
                    case > 0:
                        left = mid + 1;
                        break;
                    case < 0:
                        right = mid;
                        break;
                    default:
                        found = true;
                        return mid;
                }
            }

            found = false;
            return left;
        }
    }
}