Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version
Go to top

Squeezing more performance from SortedList

, 10 Oct 2008
A SortedList implementations using a cyclic algorithm and C# IDictionary tweaks.
SplitArrayDictionary_demo.zip
SplitArrayDictionary_bin
Debug
SplitArrayDictionary.exe
SplitArrayDictionary.vshost.exe
SplitArrayDictionary.vshost.exe.manifest
Release
SplitArrayDictionary.exe
SplitArrayDictionary_src.zip
SplitArrayDictionary_src
Properties
src
// 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
    
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

itaifrenkel
Software Developer
Israel Israel
No Biography provided

| Advertise | Privacy | Mobile
Web01 | 2.8.140916.1 | Last Updated 10 Oct 2008
Article Copyright 2007 by itaifrenkel
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid