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

namespace GFGGame
{
    class SelectionCache<K, T> where K : IComparable<K>
    {
        private List<Selection<K, T>> selections = new List<Selection<K, T>>();

        public int KeyIndex { get; private set; } = -1;

        public T defaultValue;

        public SelectionCache(T defaultValue)
        {
            this.defaultValue = defaultValue;
        }

        public SelectionCache<K, T> AddSelection(Selection<K, T> selection)
        {
            selections.Add(selection);
            selections = selections.OrderBy(x => x.Min).ToList();
            return this;
        }

        public SelectionCache<K, T> AddSelection(List<Selection<K, T>> selectionParams)
        {
            foreach (var selection in selectionParams)
            {
                selections.Add(selection);
            }
            selections = selectionParams.OrderBy(x => x.Min).ToList();
            return this;
        }

        public SelectionCache<K, T> AddSelection(IEnumerable<Selection<K, T>> selection)
        {
            selections.AddRange(selection);
            selections = selections.OrderBy(x => x.Min).ToList();
            return this;
        }

        public T GetValueNoCache(K keyValue)
        {
            int left = 0;
            int right = selections.Count - 1;
            while (left <= right)
            {
                int mid = left + (right - left) / 2;
                if (selections[mid].CheckInclude(keyValue))
                {
                    return selections[mid].Value;
                }

                if (keyValue.CompareTo(selections[mid].Max) > 0)
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }

            return defaultValue;
        }

        public T GetValue(K keyValue)
        {
            var checkIndex = KeyIndex >= 0 ? KeyIndex : 0;
            var nowSelection = selections[checkIndex];
            if (nowSelection.CheckInclude(keyValue))
            {
                KeyIndex = checkIndex;
                return nowSelection.Value;
            }

            if (keyValue.CompareTo(nowSelection.Min) <= 0)
            {
                // binary search to the left
                var left = 0;
                var right = checkIndex;
                while (left <= right)
                {
                    var mid = (left + right) / 2;
                    var midSelection = selections[mid];
                    if (midSelection.CheckInclude(keyValue))
                    {
                        KeyIndex = mid;
                        return midSelection.Value;
                    }

                    if (keyValue.CompareTo(midSelection.Max) > 0)
                    {
                        left = mid + 1;
                    }
                    else
                    {
                        right = mid - 1;
                    }
                }

                KeyIndex = -1;
                return defaultValue;
            }

            if (keyValue.CompareTo(nowSelection.Max) >= 0)
            {
                // binary search to the right
                var left = checkIndex;
                var right = selections.Count - 1;
                while (left <= right)
                {
                    var mid = (left + right) / 2;
                    var midSelection = selections[mid];
                    if (midSelection.CheckInclude(keyValue))
                    {
                        KeyIndex = mid;
                        return midSelection.Value;
                    }

                    if (keyValue.CompareTo(midSelection.Min) < 0)
                    {
                        right = mid - 1;
                    }
                    else
                    {
                        left = mid + 1;
                    }
                }

                KeyIndex = -1;
                return defaultValue;
            }

            return defaultValue;
        }

        public T GetValueByIndex(int index)
        {
            if (index < 0 || index >= selections.Count)
            {
                return defaultValue;
            }

            return selections[index].Value;
        }

        public void Clear()
        {
            KeyIndex = -1;
        }

        public static SelectionCache<K, T> CreateSelectionCache(List<KeyValuePair<K, T>> res, K min, K max,
            T defaultValue, T cacheDefaultValue)
        {
            // 添加首区间
            var firstRes = res.First();
            var selectionCache = new SelectionCache<K, T>(cacheDefaultValue)
                .AddSelection(new Selection<K, T>(min, firstRes.Key, defaultValue,
                    Selection<K, T>.SelectionModel.Left));
            var preRes = firstRes.Value;
            for (var i = 1; i < res.Count; i++)
            {
                var resValue = res[i];
                selectionCache.AddSelection(new Selection<K, T>(res[i - 1].Key, resValue.Key, preRes,
                    Selection<K, T>.SelectionModel.Left));
                preRes = resValue.Value;
            }

            // 添加尾区间
            var lastRes = res.Last();
            selectionCache.AddSelection(new Selection<K, T>(
                lastRes.Key, max, lastRes.Value, Selection<K, T>.SelectionModel.Left));

            return selectionCache;
        }
    }
}