// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

using System;
using System.Collections;
using System.Diagnostics;

namespace MS.Utility
{
    //
    // ItemStructMap<T>
    //

    // Disable warnings about fields never being assigned to
    // This struct is designed to function with its fields starting at
    // their default values and without the need of surfacing a constructor
    // other than the deafult
    #pragma warning disable 649

    internal struct ItemStructMap<T>
    {
        public int EnsureEntry(int key)
        {
            int index = Search(key);
            if (index < 0)
            {
                // Not found, add Entry

                // Create initial capacity, if necessary
                if (Entries == null)
                {
                    Entries = new Entry[SearchTypeThreshold];
                }

                // Convert not-found index to insertion point
                index = ~index;

                Entry[] destEntries = Entries;

                // Increase capacity, if necessary
                if ((Count + 1) > Entries.Length)
                {
                    destEntries = new Entry[Entries.Length * 2];

                    // Initialize start of new array
                    Array.Copy(Entries, 0, destEntries, 0, index);
                }

                // Shift entries to make room for new key at provided insertion point
                Array.Copy(Entries, index, destEntries, index + 1, Count - index);

                // Ensure Source and Destination arrays are the same
                Entries = destEntries;

                // Clear new entry
                Entries[index] = EmptyEntry;

                // Set
                Entries[index].Key = key;

                Count++;
            }

            return index;
        }

        public int Search(int key)
        {
            int keyPv = Int32.MaxValue;
            int iPv = 0;

            // Use fastest search based on size
            if (Count > SearchTypeThreshold)
            {
                // Binary Search
                int iLo = 0;
                int iHi = Count - 1;

                while (iLo <= iHi)
                {
                    iPv = (iHi + iLo) / 2;
                    keyPv = Entries[iPv].Key;

                    if (key == keyPv)
                    {
                        return iPv;
                    }

                    if (key < keyPv)
                    {
                        iHi = iPv - 1;
                    }
                    else
                    {
                        iLo = iPv + 1;
                    }
                }
            }
            else
            {
                // Linear search

                for (int i = 0; i < Count; i++)
                {
                    iPv = i;
                    keyPv = Entries[iPv].Key;

                    if (key == keyPv)
                    {
                        return iPv;
                    }

                    if (key < keyPv)
                    {
                        break;
                    }
                }
            }

            // iPv and keyPv will match and have the last pivot check

            // Return a negative value whose bitwise compliment
            // is this index of the first Entry that is greater
            // than the key passed in (sorted insertion point)

            if (key > keyPv)
            {
                iPv++;
            }


            return ~iPv;
        }

        private const int SearchTypeThreshold = 4;

        public Entry[] Entries;
        public int Count;

        public struct Entry
        {
            public int Key;
            public T Value;
        }

        private static Entry EmptyEntry;
    }

    #pragma warning restore 649
}


