Squeezing More Performance from SortedList

// TODO See if can implement a IList interface, which would make it more generic.
// restrict split jump by expected number of monotonous input
// calculate this value based on past data
using System.Collections.Generic;
using System.Diagnostics;
using System;


namespace SplitArrayDictionary
{
    
    
    abstract public class SortedCyclicSplitArray<TKey, TValue>
    : CyclicArrayBase<TKey,TValue> , IEnumerable<KeyValuePair<TKey,TValue>>
        where TKey : IComparable<TKey>
{
    abstract public int PrefetchKeyMSB(TKey key);
    abstract public int Compare(TKey left, TKey right);
    abstract public bool LessOrEqual(TKey left, TKey right);
    abstract public bool Less(TKey left, TKey right);
    abstract public bool GreaterOrEqual(TKey left, TKey right);
    abstract public bool Greater(TKey left, TKey right);
    abstract public bool Equal(TKey left, TKey right);

    int MinIndex { get; set; }
    int MaxIndex { get; set; }
    int LocalMaxIndex { get; set; }
    int LocalMinIndex { get; set; }
    int LastShiftInsertIndex;

    
    protected SortedCyclicSplitArray(int minCapacity) 
        : base ((int)(Math.Ceiling(Math.Log(minCapacity,2))))
    {
        Clear();
    }

    protected bool TryCyclicBinarySearch(TKey key, out int index)
    {
        return TryCyclicBinarySearch(key, PrefetchKeyMSB(key), out index);
    }

    protected bool TryCyclicBinarySearch(TKey key, int keyPrefetch, out int index)
    {
        Debug.Assert(DebugSortValidationCheck());
        Debug.Assert(KeyMightBeInArray(key));
              
        //assuming no split in the array
        int searchMinIndex = this.MinIndex;
        int searchMaxIndex = this.MaxIndex;
        Debug.Assert(!this.Empty);

        if (this.Split)
        {
            if (keyPrefetch >= GetSortingPrefetch(this.MinIndex) &&
                keyPrefetch <= GetSortingPrefetch(this.LocalMaxIndex) &&
                GreaterOrEqual(key, this.MinKey) &&
                LessOrEqual(key, GetKey(this.LocalMaxIndex)))
            {
                searchMaxIndex = this.LocalMaxIndex;
            }
            else
            {
                Debug.Assert(LessOrEqual(key, GetKey(this.MaxIndex)) &&
                             GreaterOrEqual(key, GetKey(this.LocalMinIndex)));
                searchMinIndex = this.LocalMinIndex;
            }
        }

        if (searchMaxIndex < searchMinIndex)
        {
            int topPrefetch = GetSortingPrefetch(this.LastIndex);
            int bottomPrefetch = GetSortingPrefetch(0);
            if (keyPrefetch < topPrefetch)
            {
                searchMaxIndex = this.LastIndex;
            }
            else if (keyPrefetch > bottomPrefetch)
            {
                searchMinIndex = 0;
            }
            else if (keyPrefetch < bottomPrefetch && keyPrefetch > topPrefetch)
            {
                index = LastIndex;
                return false;                
            }
            else
            {
                Debug.Assert(keyPrefetch == topPrefetch ||
                             keyPrefetch == bottomPrefetch);
                int compareTop = Compare(key,GetKey(this.LastIndex));
                if (compareTop == 0)
                {
                    index = LastIndex;
                    return true;
                }
                int compareBottom = Compare(key, GetKey(0));
                if (compareBottom == 0)
                {
                    index = 0;
                    return true;
                }

                if (compareTop < 0)
                {
                    searchMaxIndex = this.LastIndex;
                }                
                else if (compareBottom > 0)
                {
                    searchMinIndex = 0;
                }
                else                 
                {
                    Debug.Assert((compareTop > 0) && (compareBottom < 0));
                    index = LastIndex;
                    return false;
                }
            }
        } // (searchMaxIndex < searchMinIndex)
        Debug.Assert(searchMaxIndex >= searchMinIndex);        

        Debug.Assert(LessOrEqual(key, this.GetKey(searchMaxIndex)));
        Debug.Assert(GreaterOrEqual(key, this.GetKey(searchMinIndex)));

        return TryBinarySearchInRange(key, keyPrefetch, out index, searchMinIndex, searchMaxIndex);        
    }

    /* [inline] */
    protected new void Clear() 
    {         
        this.Empty=true;
        this.LastShiftInsertIndex = -1;
        MinIndex=0; 
        MaxIndex=0;
        LocalMaxIndex = 0;
        LocalMinIndex = 0;
        base.Clear();
    }

    public bool Empty 
    { 
        /* [inline] */
        get;
        /* [inline] */
        protected set;
    }

    public bool Split
    {
        get
        {
            if (MinIndex != this.LocalMinIndex)
            {
                Debug.Assert(MaxIndex != this.LocalMaxIndex);
                return true;
            }
            return false;
        }
    }

    protected int Count 
    {
        get
        {
            if (Empty)
            {
                return 0;
            }
            if (Full)
            {
                return LastIndex+1;
            }
            return CyclicInc(CyclicSub(LocalMaxIndex, LocalMinIndex));
        }
    }

    protected bool Full 
    { 
        /* [inline] */
        get 
        {
            return (CyclicInc(LocalMaxIndex) == LocalMinIndex);
        }
    }
    
    protected bool KeyMightBeInArray(TKey key)
    {
        if (Empty) return false;
        
        int prefetch = PrefetchKeyMSB(key);
        if (prefetch > GetSortingPrefetch(this.LocalMinIndex) &&
            prefetch < GetSortingPrefetch(this.LocalMaxIndex))
        {
            return true;
        }        
        bool MaxKeyIsMaxima = (prefetch <= GetSortingPrefetch(this.MaxIndex)) &&
                              LessOrEqual(key, MaxKey);
        if (!MaxKeyIsMaxima) return false;
        bool MinKeyIsMinima = (prefetch >= GetSortingPrefetch(this.MinIndex)) && 
                              GreaterOrEqual(key, MinKey);
        if (!MinKeyIsMinima) return false;
        bool LocalMinKeyIsMinima =(prefetch >= GetSortingPrefetch(this.LocalMinIndex) &&
                                   GreaterOrEqual(key, GetKey(this.LocalMinIndex)));
        Debug.Assert(MaxKeyIsMaxima);
        if (LocalMinKeyIsMinima) return true;
        bool LocalMaxKeyIsMaxima  = prefetch <= GetSortingPrefetch(this.LocalMaxIndex) && 
                                     LessOrEqual(key, GetKey(this.LocalMaxIndex));
        Debug.Assert(MinKeyIsMinima);
        if (LocalMaxKeyIsMaxima) return true;
        return false; //falls in the gap. No keys there.
    }
    
    private bool TryBinarySearchInRange(TKey key,
                                    int keyPrefetch, 
                                    out int index, 
                                    int searchMinIndex, 
                                    int searchMaxIndex)
    {
        if (Equal(key, GetKey(searchMinIndex)))
        {
            index = searchMinIndex;
            return true;
        }

        if (Equal(key, GetKey(searchMaxIndex)))
        {
            index = searchMaxIndex;
            return true;
        }

        int delta = (searchMaxIndex - searchMinIndex) / 2;
        
        for (; delta != 0 ; delta = (searchMaxIndex - searchMinIndex) / 2)
        {
            Debug.Assert(Greater (key,GetKey(searchMinIndex)));
            Debug.Assert(Less    (key,GetKey(searchMaxIndex)));            
        
            int i = searchMinIndex + delta;
            int prefetch = GetSortingPrefetch(i);
            Debug.Assert(i >= 0 && i <= LastIndex);
            if (keyPrefetch < prefetch)
            {
                searchMaxIndex = i;
                continue;
            }

            if (keyPrefetch > prefetch)
            {
                searchMinIndex = i;
                continue;
            }

            Debug.Assert(keyPrefetch == prefetch);
            int compare = Compare(key, GetKey(i));
            if (compare == 0)
            {
                index = i;
                return true;
            }

            if (compare < 0)
            {
                searchMaxIndex = i;
            }
            else
            {
                Debug.Assert(compare > 0);
                searchMinIndex = i;
            }
        }//for
        Debug.Assert(Greater(key, GetKey(searchMinIndex)));
        Debug.Assert(Less(key, GetKey(searchMaxIndex)));
        Debug.Assert(delta == 0);
        index = searchMinIndex;
        return false;
        
   }
    
    
    void InsertShiftLeft(TKey key, int hint, TValue value, int endIndexBeforeShift)
    {
        Debug.Assert(DebugSortValidationCheck());
        Debug.Assert(endIndexBeforeShift != LocalMaxIndex);

        int length = CyclicSub(endIndexBeforeShift + 1, LocalMinIndex);
        if (LastShiftInsertIndex == endIndexBeforeShift) 
        {
            SplitLeft(endIndexBeforeShift);
            Debug.Assert(DebugSortValidationCheck());
            if (Split)  
            {
                InsertNewLocalMaxKey(key, hint, value);
                Debug.Assert(DebugSortValidationCheck());
                return;
            }
            Debug.Assert(!Split);
            if (endIndexBeforeShift != CyclicDec(MinIndex))
            {
                InsertNewMaxKey(key, hint, value);
                return;
            }
            InsertNewMinKey(key, hint, value);            
            return;
        }
        
        if (LastShiftInsertIndex == CyclicInc(endIndexBeforeShift) )
        {
            SplitLeft(endIndexBeforeShift);
            Debug.Assert(DebugSortValidationCheck());
            if (Split)
            {
                InsertNewLocalMinKey(key, hint, value);
                Debug.Assert(DebugSortValidationCheck());
                return;
            }
            InsertNewMinKey(key, hint, value);
            Debug.Assert(DebugSortValidationCheck());
            return;        
        }

        //shift only by one index left
        TKey minKey = MinKey;
        Debug.Assert(CyclicAdd(LocalMinIndex,length-1)==endIndexBeforeShift);    
        ShiftLeft(LocalMinIndex, length);            
        Insert(key, value, hint,endIndexBeforeShift);
        LastShiftInsertIndex = endIndexBeforeShift;    
        if (endIndexBeforeShift == MaxIndex)
        {
            // we have a new minimum or a new maximum
            if (Less(key, minKey))
            {
                // found a new minimum
                MinIndex = MaxIndex;            //MinIndex--
                MaxIndex = CyclicDec(MaxIndex); //MaxIndex--
            }
            else
            {
                // found a new maximum
                // but it's in the same position
                // of the previous maximum
            }
        }
        else if (Split &&
            CyclicSub(MaxIndex+1,LocalMinIndex) <= length)
            //CyclicSub(endIndexBeforeShift+1,LocalMinIndex))
        {
            //MaxIndex and MinIndex moved during shift
            MinIndex = MaxIndex;            //MinIndex--;
            MaxIndex = CyclicDec(MaxIndex); //MaxIndex--;
        }
        else if (!Split)
        {
            //MinIndex moved during shift
            MinIndex = CyclicDec(MinIndex);
        }
        LocalMinIndex = CyclicDec(LocalMinIndex);
    }

    void InsertShiftRight(TKey key, int hint, TValue value, int index)
    {
        Debug.Assert(DebugSortValidationCheck());
        Debug.Assert(index != LocalMinIndex);

        if (LastShiftInsertIndex == index) 
        {
            SplitRight(index);
            Debug.Assert(DebugSortValidationCheck());
            if (Split)  
            {
                InsertNewLocalMinKey(key, hint, value);
                Debug.Assert(DebugSortValidationCheck());
                return;
            }
            InsertNewMinKey(key, hint, value);
            Debug.Assert(DebugSortValidationCheck());
            return;
        }
        
        if (LastShiftInsertIndex == CyclicDec(index) )
        {
            SplitRight(index);
            Debug.Assert(DebugSortValidationCheck());
            if (Split)
            {
                InsertNewLocalMaxKey(key, hint, value);
                Debug.Assert(DebugSortValidationCheck());
                return;
            }
            InsertNewMaxKey(key, hint, value);
            Debug.Assert(DebugSortValidationCheck());
            return;
        }
        
        TKey maxKey = MaxKey;
        int length = CyclicSub(LocalMaxIndex + 1, index);
        ShiftRight(index, length);
        Insert(key, value, hint,index);
        LastShiftInsertIndex = index;
        Debug.Assert(!Full);
        if (index == MinIndex)
        {
            Debug.Assert(!Equals(key, maxKey));
                
            if (GreaterOrEqual(key, maxKey))
            {
                MaxIndex = MinIndex;            //MaxIndex++
                MinIndex = CyclicInc(MinIndex); //MinIndex++
            }
            else
            {
                // we have a new minimum
                // but it's in the same place as the
                // previous minimum.
            }
        }
        else if (Split &&
            CyclicSub(LocalMaxIndex, MaxIndex) <=
            CyclicSub(LocalMaxIndex, index))
        {                                
            MaxIndex = MinIndex;            //MaxIndex++
            MinIndex = CyclicInc(MinIndex); //MinIndex++
        }
        else if (!Split)
        {
            MaxIndex = CyclicInc(MaxIndex); //MaxIndex++
        }
        this.LocalMaxIndex = CyclicInc(this.LocalMaxIndex);
    }

    void SplitLeft(int endIndexBeforeShift)
    {
        int length = CyclicSub(endIndexBeforeShift+1,LocalMinIndex);
        int shift = CyclicSub(LocalMinIndex, LocalMaxIndex + 1);
        ShiftLeft(LocalMinIndex, length, shift);
        // 000abcdef000 --> splitLeft(c) --> 000000defabc
        
        if (MaxIndex == endIndexBeforeShift)
        {
            // 000000defabc --> splitLeft(f) --> def000000abc
            MaxIndex = CyclicSub(MaxIndex, shift);
            LocalMaxIndex = MaxIndex;
            LocalMinIndex = MinIndex;
            Debug.Assert(!Split);
            Debug.Assert(DebugSortValidationCheck());
            return;
        }
        
        if (CyclicSub(MinIndex, LocalMinIndex) <=
            CyclicSub(endIndexBeforeShift, LocalMinIndex))
        {
            // 000000defabc --> SplitLeft(a) --> defa000000bc
            MinIndex = CyclicSub(MinIndex, shift);
            MaxIndex = CyclicDec(MinIndex);            
        }
        else
        {
            // 000000defabc --> SplitLeft(e) --> de0000fabc
        }
        LocalMaxIndex = CyclicAdd(LocalMaxIndex, length);
        LocalMinIndex = CyclicInc(endIndexBeforeShift);
        Debug.Assert(Split);
        Debug.Assert(DebugSortValidationCheck());
    }

    void SplitRight(int index)
    {
        int length = CyclicSub(LocalMaxIndex + 1, index);
        int shift = CyclicSub(LocalMinIndex, LocalMaxIndex+1);
        ShiftRight(index, length, shift);
        if (MinIndex == index)
        {
            // efabc0000d splitright(a) -->  ef0000abcd
            MinIndex = CyclicAdd(MinIndex, shift);
            LocalMinIndex = MinIndex;
            LocalMaxIndex = MaxIndex;
            Debug.Assert(!Split);
            Debug.Assert(DebugSortValidationCheck());
            return;
        }

        if (CyclicSub(LocalMaxIndex, MaxIndex) <=
            CyclicSub(LocalMaxIndex, index))
        {
            // efabc0000d splitright(f) -->  e0000fabcd
            MaxIndex = CyclicAdd(MaxIndex, shift);
            MinIndex = CyclicInc(MaxIndex);
        }
        else
        {
            // 00abcdef00 splitright(d) -->  efabc0000d 
        }
        LocalMinIndex = CyclicSub(LocalMinIndex, length);
        LocalMaxIndex = CyclicDec(index);
        Debug.Assert(Split);
        Debug.Assert(DebugSortValidationCheck());
    }

    void InsertNewLocalMinKey(TKey key, int hint, TValue value)
    {
        Debug.Assert(DebugSortValidationCheck());
        Debug.Assert(Less(key, GetKey(LocalMinIndex)));
        Debug.Assert(Greater(key, GetKey(LocalMaxIndex)));
        Debug.Assert(!Full);
        Debug.Assert(Split);
        
        this.LocalMinIndex = CyclicDec(this.LocalMinIndex);
        Insert(key, value, hint,this.LocalMinIndex);
        LastShiftInsertIndex = this.LocalMinIndex;

        Debug.Assert(DebugSortValidationCheck());
        Debug.Assert(Split);
    }

    void InsertNewLocalMaxKey(TKey key, int hint, TValue value)
    {
        Debug.Assert(DebugSortValidationCheck());
        Debug.Assert(Split);
        Debug.Assert(Less(key, GetKey(LocalMinIndex)));
        Debug.Assert(Greater(key, GetKey(LocalMaxIndex)));
        Debug.Assert(!Full);
        

        this.LocalMaxIndex = CyclicInc(this.LocalMaxIndex);
        Insert(key, value, hint,this.LocalMaxIndex);
        LastShiftInsertIndex = this.LocalMaxIndex;

        Debug.Assert(DebugSortValidationCheck());
        Debug.Assert(Split);
    }

    void InsertNewMinKey(TKey key, int hint, TValue value)
    {
        Debug.Assert(!Full);
        Debug.Assert(!Split);
        Debug.Assert(DebugSortValidationCheck());
        Debug.Assert(Less(key, MinKey));
        this.LocalMinIndex = CyclicDec(this.LocalMinIndex);
        MinIndex = this.LocalMinIndex;
        Insert(key, value, hint,this.LocalMinIndex);
        LastShiftInsertIndex = this.LocalMinIndex;
        
        Debug.Assert(!Split);
        Debug.Assert(DebugSortValidationCheck());
    }

    void InsertNewMaxKey(TKey key, int hint, TValue value)
    {
        Debug.Assert(!Full);
        Debug.Assert(Greater(key, MaxKey));
        Debug.Assert(!Split);
        Debug.Assert(DebugSortValidationCheck());
        
        this.LocalMaxIndex = CyclicInc(this.LocalMaxIndex);
        MaxIndex = this.LocalMaxIndex;
        Insert(key, value, hint,this.LocalMaxIndex);
        LastShiftInsertIndex = this.LocalMaxIndex;
        
        Debug.Assert(!Split);
        Debug.Assert(DebugSortValidationCheck());
    }

    public TKey MinKey
    {
        get
        {
            Debug.Assert(!Empty);
            return this.GetKey(this.MinIndex);
        }
    }

    protected TKey MaxKey
    {
        get
        {
            Debug.Assert(!Empty);
            return GetKey(this.MaxIndex);
        }
    }

    bool DebugSortValidationCheck()
    {
        if (Empty) return true;
        if (!Full)
        {
            DebugDeleteUnused(CyclicInc(this.LocalMaxIndex), CyclicDec(this.LocalMinIndex));
        }
        return  DebugValidationCheck(this.MinIndex, this.LocalMaxIndex) &&
                DebugValidationCheck(this.LocalMinIndex, this.MaxIndex);
    }

    void DebugDeleteUnused(int start , int end)
    {
        if (start != end)
        {
            for (int i = start; i != end; i = CyclicInc(i))
            {
                Insert(default(TKey), default(TValue), 0,i);
            }
        }
        Insert(default(TKey), default(TValue),0, end);
    }

    bool DebugValidationCheck(int minindex, int maxindex)
    {
        for (int i = minindex; i != maxindex; i = CyclicInc(i))
        {
            if (GreaterOrEqual(GetKey(i), GetKey(CyclicInc(i))))
                return false;
            if (GetSortingPrefetch(i) > GetSortingPrefetch(CyclicInc(i)))
                return false;
        }
        return true;
    }
   
    // fails if key already exists AND overwriteValue is false
    // fails if key does not exists AND dictionary is Full.
    protected bool Insert(TKey key, TValue value, bool overwriteValue)
    {
        Debug.Assert(DebugSortValidationCheck());
        Debug.Assert(overwriteValue || !Full);
        int index;
        int hint = PrefetchKeyMSB(key);
        
        if (Empty)
        {            
            Empty = false;
            Insert(key, value, hint,this.LocalMaxIndex);
            return true;
        }

        if (Split &&
            Greater(key, this.GetKey(this.LocalMaxIndex)) &&
            Less(key, this.GetKey(this.LocalMinIndex)))
        {
            if (Full)
            {
                return false;
            }

            if (LastShiftInsertIndex == this.LocalMinIndex)
            {
                InsertNewLocalMinKey(key, hint, value);               
            }
            else
            {
                InsertNewLocalMaxKey(key, hint, value);
            }
            return true;
        }
        
        bool newMaxKey = (hint > this.GetSortingPrefetch(MaxIndex)
                          || Greater(key, MaxKey));
        if (!Split && newMaxKey)
        {
            if (Full)
            {
                return false;
            }
            InsertNewMaxKey(key, hint, value);
            return true;
        }        
        bool newMinKey = (hint < this.GetSortingPrefetch(MinIndex) ||
                          Less(key, MinKey));
        if (!Split && newMinKey)
        {
            if (Full) return false;
            InsertNewMinKey(key, hint, value);
            return true;
        }

        if (newMinKey)
        {        
            Debug.Assert(Split);
            Debug.Assert(CyclicDec(MinIndex) == MaxIndex);
            
            //shift the array to accomodate space for the new node
            if (ShiftRightIsFaster(MaxIndex))
            {
                SplitRight(MinIndex);
            }
            else
            {
                SplitLeft(MaxIndex);
            }
            Debug.Assert(!Split);
            InsertNewMinKey(key, hint, value);
            return true;
        }
        
        if (newMaxKey)
        {
            Debug.Assert(Split);
            Debug.Assert(CyclicDec(MinIndex) == MaxIndex);

            //shift the array to accomodate space for the new node
            if (ShiftRightIsFaster(MaxIndex))
            {
                SplitRight(MinIndex);
            }
            else
            {
                SplitLeft(MaxIndex);
            }
            Debug.Assert(!Split);
            InsertNewMaxKey(key, hint, value);
            return true;
        }

        if (TryCyclicBinarySearch(key, hint, out index))
        {
            if (!overwriteValue)
            {
                // key,value pair already exists
                return false;
            }
            //replace value of existing key
            Insert(key, value, hint,index);
            return true;
        }
    
        
        if (Full)
        {
            return false;
        }

        //shift the array to accomodate space for the new node      
        if (ShiftRightIsFaster(index))
        {
            index = CyclicInc(index);
            InsertShiftRight(key,hint, value, index);
        }
        else
        {
            InsertShiftLeft(key,hint, value,index);            
        }
        return true;
    }

    /// <summary>
    /// Removes a key if it exists and its value is found
    /// </summary>
    /// <param name="key">key to remove</param>
    /// <param name="value">value to remove</param>
    /// <returns>true if key is found and its value equals value.</returns>
    protected bool RemoveByKeyValue(TKey key, TValue value)
    {
        Debug.Assert(DebugSortValidationCheck());
        bool res;
        int index;
        if (KeyMightBeInArray(key) &&
            TryCyclicBinarySearch(key, out index) &&
            GetValue(index).Equals(value))
        {
            RemoveByIndex(index);
            res = true;
        }
        else
        {
            res = false;
        }
        Debug.Assert(DebugSortValidationCheck());
        return res;
    }

    // fails if key does not exist
    protected bool RemoveByKey(TKey key)
    {
        Debug.Assert(DebugSortValidationCheck());
        
        int index;
        if (KeyMightBeInArray(key) && 
            TryCyclicBinarySearch(key, out index))
        {
            RemoveByIndex(index);
            return true;
        }    
        return false;
    }

    private void RemoveByIndex(int index)
    {
        bool split = Split;
        if (Count == 1)
        {
            Debug.Assert(index == MinIndex);
            Clear();
        }

        else if (index == LocalMaxIndex)
        {
            LocalMaxIndex = CyclicDec(LocalMaxIndex);
            if (!split)
            {
                MaxIndex = LocalMaxIndex;
            }
            else if (LocalMaxIndex == MaxIndex)
            {
                // no longer split
                MinIndex = LocalMinIndex;
            }
        }

        else if (index == LocalMinIndex)
        {            
            LocalMinIndex = CyclicInc(LocalMinIndex);
            if (!split)
            {
                MinIndex = LocalMinIndex;
            }
            else if (LocalMinIndex == MinIndex)
            {
                // no longer split
                MaxIndex = LocalMaxIndex;
            }
        }

        else if (!split && CyclicSub(MaxIndex, index) < CyclicSub(index, MinIndex))
        {
            ShiftLeft(CyclicInc(index), CyclicSub(MaxIndex, index));
            MaxIndex = CyclicDec(MaxIndex);
            LocalMaxIndex = MaxIndex;
        }

        else if (!split)
        {
            ShiftRight(MinIndex, CyclicSub(index, MinIndex));
            MinIndex = CyclicInc(MinIndex);
            LocalMinIndex = MinIndex;
        }

        else if (index > LocalMinIndex)
        {
            Debug.Assert(Split);
            ShiftRight(LocalMinIndex, CyclicSub(index, LocalMinIndex));
            if (MinIndex > LocalMinIndex && index >= MinIndex)
            {
                MinIndex = CyclicInc(MinIndex);
                MaxIndex = CyclicInc(MaxIndex);
            }
            LocalMinIndex = CyclicInc(LocalMinIndex);
            Debug.Assert(LocalMinIndex != MinIndex);
        }
        else
        {
            Debug.Assert(Split);
            Debug.Assert(index < LocalMaxIndex);
            ShiftLeft(CyclicInc(index), CyclicSub(LocalMaxIndex, index));
            if (MaxIndex < LocalMaxIndex && index <= MaxIndex)
            {
                MaxIndex = CyclicDec(MaxIndex);
                MinIndex = CyclicDec(MinIndex);
            }
            LocalMaxIndex = CyclicDec(LocalMaxIndex);
            Debug.Assert(LocalMaxIndex != MaxIndex);
        }        
    }


    // returns true if index is closer to the beginning of the cyclic array
    // returns false if index is closer to the end of the array.
    /* [inline] */
    private bool ShiftRightIsFaster(int index)
    {
        Debug.Assert(!Full);

        return (CyclicSub(LocalMaxIndex + 1,index) <
                CyclicSub(index+1,LocalMinIndex));        
    }

    void ShiftRight(int index, int length)
    {
        ShiftRight(index, length, 1);
    }

    void ShiftRight(int index, int length, int shift)
    {
        Debug.Assert(length + shift <= LastIndex+1);
        CyclicArrayCopy(index, CyclicAdd(index, shift), length);
    }

    void ShiftLeft(int index, int length)
    {
        TKey debugKey = GetKey(index);
        ShiftLeft(index, length, 1);
        Debug.Assert(debugKey.Equals(GetKey(CyclicDec(index))));
    }

    void ShiftLeft(int startIndex, int length, int shift)
    {
        Debug.Assert(length + shift <= LastIndex+1);
        CyclicArrayCopy(startIndex,
                        CyclicSub(startIndex, shift),
                        length);
    }



    #region IEnumerable<KeyValuePair<TKey,TValue>> Members

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        if (Empty) 
        {
            yield break;
        }

        for (int index = this.MinIndex; index <= this.MaxIndex; index = CyclicInc(index))
        {
            yield return new KeyValuePair<TKey, TValue>(GetKey(index), GetValue(index));
        }
    }

    #endregion

    #region IEnumerable Members

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

    #endregion
}//class
    
}