File: Shared\MS\Utility\FrugalMap.cs
Project: wpf\src\WindowsBase.csproj (WindowsBase)
//---------------------------------------------------------------------------
//
// Copyright (C) Microsoft Corporation.  All rights reserved.
// 
//---------------------------------------------------------------------------
 
using System;
using System.Diagnostics;
using System.Collections;
using System.Windows;
 
#if WINDOWS_BASE
    using MS.Internal.WindowsBase;
#elif PRESENTATION_CORE
    using MS.Internal.PresentationCore;
#elif PRESENTATIONFRAMEWORK
    using MS.Internal.PresentationFramework;
#elif DRT
    using MS.Internal.Drt;
#else
#error Attempt to use FriendAccessAllowedAttribute from an unknown assembly.
using MS.Internal.YourAssemblyName;
#endif
 
namespace MS.Utility
{
    // These classes implement a frugal storage model for key/value pair data
    // structures. The keys are integers, and the values objects.
    // Performance measurements show that Avalon has many maps that contain a
    // single key/value pair. Therefore these classes are structured to prefer
    // a map that contains a single key/value pair and uses a conservative
    // growth strategy to minimize the steady state memory footprint. To enforce
    // the slow growth the map does not allow the user to set the capacity.
    // Also note that the map uses one fewer objects than the BCL HashTable and
    // does no allocations at all until an item is inserted into the map.
    //
    // The code is also structured to perform well from a CPU standpoint. Perf
    // analysis of DependencyObject showed that we used a single entry 63% of 
    // the time and growth tailed off quickly. Average access times are 8 to 16
    // times faster than a BCL Hashtable. 
    //
    // FrugalMap is appropriate for small maps or maps that grow slowly. Its
    // primary focus is for maps that contain fewer than 64 entries and that
    // usually start with no entries, or a single entry. If you know your map
    // will always have a minimum of 64 or more entires FrugalMap *may* not
    // be the best choice. Choose your collections wisely and pay particular
    // attention to the growth patterns and search methods.
 
    // This enum controls the growth to successively more complex storage models
    internal enum FrugalMapStoreState
    {
        Success,
        ThreeObjectMap,
        SixObjectMap,
        Array,
        SortedArray,
        Hashtable
    }
 
    abstract class FrugalMapBase
    {
        public abstract FrugalMapStoreState InsertEntry(int key, Object value);
 
        public abstract void RemoveEntry(int key);
 
        /// <summary>
        /// Looks for an entry that contains the given key, null is returned if the
        /// key is not found.
        /// </summary>
        public abstract Object Search(int key);
 
 
        /// <summary>
        /// A routine used by enumerators that need a sorted map
        /// </summary>
        public abstract void Sort();
 
        /// <summary>
        /// A routine used by enumerators to iterate through the map
        /// </summary>
        public abstract void GetKeyValuePair(int index, out int key, out Object value);
 
        /// <summary>
        /// A routine used to iterate through all the entries in the map
        /// </summary>
        public abstract void Iterate(ArrayList list, FrugalMapIterationCallback callback);
 
        /// <summary>
        /// Promotes the key/value pairs in the current collection to the next larger
        /// and more complex storage model.
        /// </summary>
        public abstract void Promote(FrugalMapBase newMap);
 
        /// <summary>
        /// Size of this data store
        /// </summary>
        public abstract int Count
        {
            get;
        }
 
        protected const int INVALIDKEY = 0x7FFFFFFF;
 
        internal struct Entry
        {
            public int Key;
            public Object Value;
        }
    }
 
    /// <summary>
    /// A simple class to handle a single key/value pair
    /// </summary>
    internal sealed class SingleObjectMap : FrugalMapBase
    {
        public SingleObjectMap()
        {
            _loneEntry.Key = INVALIDKEY;
            _loneEntry.Value = DependencyProperty.UnsetValue;
        }
 
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        {
            // If we don't have any entries or the existing entry is being overwritten,
            // then we can use this map.  Otherwise we have to promote.
            if ((INVALIDKEY == _loneEntry.Key) || (key == _loneEntry.Key))
            {
                Debug.Assert(INVALIDKEY != key);
 
                _loneEntry.Key = key;
                _loneEntry.Value = value;
                return FrugalMapStoreState.Success;
            }
            else
            {
                // Entry already used, move to an ThreeObjectMap
                return FrugalMapStoreState.ThreeObjectMap;
            }
        }
 
        public override void RemoveEntry(int key)
        {
            // Wipe out the info in the only entry if it matches the key.
            if (key == _loneEntry.Key)
            {
                _loneEntry.Key = INVALIDKEY;
                _loneEntry.Value = DependencyProperty.UnsetValue;
            }
        }
 
        public override Object Search(int key)
        {
            if (key == _loneEntry.Key)
            {
                return _loneEntry.Value;
            }
            return DependencyProperty.UnsetValue;
        }
 
        public override void Sort()
        {
            // Single items are already sorted.
        }
 
        public override void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (0 == index)
            {
                value = _loneEntry.Value;
                key = _loneEntry.Key;
            }
            else
            {
                value = DependencyProperty.UnsetValue;
                key = INVALIDKEY;
                throw new ArgumentOutOfRangeException("index");
            }
        }
        
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        {
            if (Count == 1)
            {
                callback(list, _loneEntry.Key, _loneEntry.Value);
            }
        }
 
        public override void Promote(FrugalMapBase newMap)
        {
            if (FrugalMapStoreState.Success == newMap.InsertEntry(_loneEntry.Key, _loneEntry.Value))
            {
            }
            else
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
        }
 
        // Size of this data store
        public override int Count
        {
            get
            {
                if (INVALIDKEY != _loneEntry.Key)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        }
 
        private Entry _loneEntry;
    }
 
 
    /// <summary>
    /// A simple class to handle a single object with 3 key/value pairs.  The pairs are stored unsorted
    /// and uses a linear search.  Perf analysis showed that this yielded better memory locality and
    /// perf than an object and an array.
    /// </summary>
    /// <remarks>
    /// This map inserts at the last position.  Any time we add to the map we set _sorted to false. If you need
    /// to iterate through the map in sorted order you must call Sort before using GetKeyValuePair.
    /// </remarks>
    internal sealed class ThreeObjectMap : FrugalMapBase
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        {
            // Check to see if we are updating an existing entry
            Debug.Assert(INVALIDKEY != key);
 
            // First check if the key matches the key of one of the existing entries.
            // If it does, overwrite the existing value and return success.
            switch (_count)
            {
                case 1:
                    if (_entry0.Key == key)
                    {
                        _entry0.Value = value;
                        return FrugalMapStoreState.Success;
                    }
                    break;
 
                case 2:
                    if (_entry0.Key == key)
                    {
                        _entry0.Value = value;
                        return FrugalMapStoreState.Success;
                    }
                    if (_entry1.Key == key)
                    {
                        _entry1.Value = value;
                        return FrugalMapStoreState.Success;
                    }
                    break;
 
                case 3:
                    if (_entry0.Key == key)
                    {
                        _entry0.Value = value;
                        return FrugalMapStoreState.Success;
                    }
                    if (_entry1.Key == key)
                    {
                        _entry1.Value = value;
                        return FrugalMapStoreState.Success;
                    }
                    if (_entry2.Key == key)
                    {
                        _entry2.Value = value;
                        return FrugalMapStoreState.Success;
                    }
                    break;
 
                default:
                    break;
            }
 
            // If we got past the above switch, that means this key
            // doesn't exist in the map already so we should add it.
            // Only add it if we're not at the size limit; otherwise
            // we have to promote.
            if (SIZE > _count)
            {
                // Space still available to store the value. Insert
                // into the entry at _count (the next available slot).
                switch (_count)
                {
                    case 0:
                        _entry0.Key = key;
                        _entry0.Value = value;
                        _sorted = true;
                        break;
 
                    case 1:
                        _entry1.Key = key;
                        _entry1.Value = value;
                        // We have added an entry to the array, so we may not be sorted any longer
                        _sorted = false;
                        break;
 
                    case 2:
                        _entry2.Key = key;
                        _entry2.Value = value;
                        // We have added an entry to the array, so we may not be sorted any longer
                        _sorted = false;
                        break;
                }
                ++_count;
 
                return FrugalMapStoreState.Success;
            }
            else
            {
                // Array is full, move to a SixObjectMap
                return FrugalMapStoreState.SixObjectMap;
            }
        }
 
        public override void RemoveEntry(int key)
        {
            // If the key matches an existing entry, wipe out the last 
            // entry and move all the other entries up.  Because we only
            // have three entries we can just unravel all the cases.
            switch (_count)
            {
                case 1:
                    if (_entry0.Key == key)
                    {
                        _entry0.Key = INVALIDKEY;
                        _entry0.Value = DependencyProperty.UnsetValue;
                        --_count;
                        return;
                    }
                    break;
 
                case 2:
                    if (_entry0.Key == key)
                    {
                        _entry0 = _entry1;
                        _entry1.Key = INVALIDKEY;
                        _entry1.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry1.Key == key)
                    {
                        _entry1.Key = INVALIDKEY;
                        _entry1.Value = DependencyProperty.UnsetValue;
                        --_count;
                    }
                    break;
 
                case 3:
                    if (_entry0.Key == key)
                    {
                        _entry0 = _entry1;
                        _entry1 = _entry2;
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry1.Key == key)
                    {
                        _entry1 = _entry2;
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry2.Key == key)
                    {
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    break;
 
                default:
                    break;
            }
        }
 
        public override Object Search(int key)
        {
            Debug.Assert(INVALIDKEY != key);
            if (_count > 0)
            {
                if (_entry0.Key == key)
                {
                    return _entry0.Value;
                }
                if (_count > 1)
                {
                    if (_entry1.Key == key)
                    {
                        return _entry1.Value;
                    }
                    if ((_count > 2) && (_entry2.Key == key))
                    {
                        return _entry2.Value;
                    }
                }
            }
            return DependencyProperty.UnsetValue;
        }
 
        public override void Sort()
        {
            // If we're unsorted and we have entries to sort, do a simple
            // sort.  Sort the pairs (0,1), (1,2) and then (0,1) again.  
            if ((false == _sorted) && (_count > 1))
            {
                Entry temp;
                if (_entry0.Key > _entry1.Key)
                {
                    temp = _entry0;
                    _entry0 = _entry1;
                    _entry1 = temp;
                }
                if (_count > 2)
                {
                    if (_entry1.Key > _entry2.Key)
                    {
                        temp = _entry1;
                        _entry1 = _entry2;
                        _entry2 = temp;
 
                        if (_entry0.Key > _entry1.Key)
                        {
                            temp = _entry0;
                            _entry0 = _entry1;
                            _entry1 = temp;
                        }
                    }
                }
                _sorted = true;
            }
        }
 
        public override void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (index < _count)
            {
                switch (index)
                {
                    case 0:
                        key = _entry0.Key;
                        value = _entry0.Value;
                        break;
 
                    case 1:
                        key = _entry1.Key;
                        value = _entry1.Value;
                        break;
 
                    case 2:
                        key = _entry2.Key;
                        value = _entry2.Value;
                        break;
 
                    default:
                        key = INVALIDKEY;
                        value = DependencyProperty.UnsetValue;
                        break;
                }
            }
            else
            {
                key = INVALIDKEY;
                value = DependencyProperty.UnsetValue;
                throw new ArgumentOutOfRangeException("index");
            }
        }
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        {
            if (_count > 0)
            {
                if (_count >= 1)
                {
                    callback(list, _entry0.Key, _entry0.Value);
                }
                if (_count >= 2)
                {
                    callback(list, _entry1.Key, _entry1.Value);
                }
                if (_count == 3)
                {
                    callback(list, _entry2.Key, _entry2.Value);
                }
            }
        }
 
        public override void Promote(FrugalMapBase newMap)
        {
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry0.Key, _entry0.Value))
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry1.Key, _entry1.Value))
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry2.Key, _entry2.Value))
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
        }
 
        // Size of this data store
        public override int Count
        {
            get
            {
                return _count;
            }
        }
 
        private const int SIZE = 3;
 
        // The number of items in the map.
        private UInt16 _count;
 
        private bool _sorted;
        private Entry _entry0;
        private Entry _entry1;
        private Entry _entry2;
    }
 
    /// <summary>
    /// A simple class to handle a single object with 6 key/value pairs.  The pairs are stored unsorted
    /// and uses a linear search.  Perf analysis showed that this yielded better memory locality and
    /// perf than an object and an array.
    /// </summary>
    /// <remarks>
    /// This map inserts at the last position.  Any time we add to the map we set _sorted to false. If you need
    /// to iterate through the map in sorted order you must call Sort before using GetKeyValuePair.
    /// </remarks>
    internal sealed class SixObjectMap : FrugalMapBase
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        {
            // Check to see if we are updating an existing entry
            Debug.Assert(INVALIDKEY != key);
 
            // First check if the key matches the key of one of the existing entries.
            // If it does, overwrite the existing value and return success.
            if (_count > 0)
            {
                if (_entry0.Key == key)
                {
                    _entry0.Value = value;
                    return FrugalMapStoreState.Success;
                }
                if (_count > 1)
                {
                    if (_entry1.Key == key)
                    {
                        _entry1.Value = value;
                        return FrugalMapStoreState.Success;
                    }
                    if (_count > 2)
                    {
                        if (_entry2.Key == key)
                        {
                            _entry2.Value = value;
                            return FrugalMapStoreState.Success;
                        }
                        if (_count > 3)
                        {
                            if (_entry3.Key == key)
                            {
                                _entry3.Value = value;
                                return FrugalMapStoreState.Success;
                            }
                            if (_count > 4)
                            {
                                if (_entry4.Key == key)
                                {
                                    _entry4.Value = value;
                                    return FrugalMapStoreState.Success;
                                }
                                if ((_count > 5) && (_entry5.Key == key))
                                {
                                    _entry5.Value = value;
                                    return FrugalMapStoreState.Success;
                                }
                            }
                        }
                    }
                }
            }
 
            // If we got past the above switch, that means this key
            // doesn't exist in the map already so we should add it.
            // Only add it if we're not at the size limit; otherwise
            // we have to promote.
            if (SIZE > _count)
            {
                // We are adding an entry to the array, so we may not be sorted any longer
                _sorted = false;
                
                // Space still available to store the value. Insert
                // into the entry at _count (the next available slot).
                switch (_count)
                {
                    case 0:
                        _entry0.Key = key;
                        _entry0.Value = value;
 
                        // Single entries are always sorted
                        _sorted = true;
                        break;
 
                    case 1:
                        _entry1.Key = key;
                        _entry1.Value = value;
                        break;
 
                    case 2:
                        _entry2.Key = key;
                        _entry2.Value = value;
                        break;
 
                    case 3:
                        _entry3.Key = key;
                        _entry3.Value = value;
                        break;
 
                    case 4:
                        _entry4.Key = key;
                        _entry4.Value = value;
                        break;
 
                    case 5:
                        _entry5.Key = key;
                        _entry5.Value = value;
                        break;
                }
                ++_count;
 
                return FrugalMapStoreState.Success;
            }
            else
            {
                // Array is full, move to a Array
                return FrugalMapStoreState.Array;
            }
        }
 
        public override void RemoveEntry(int key)
        {
            // If the key matches an existing entry, wipe out the last 
            // entry and move all the other entries up.  Because we only
            // have three entries we can just unravel all the cases.
            switch (_count)
            {
                case 1:
                    if (_entry0.Key == key)
                    {
                        _entry0.Key = INVALIDKEY;
                        _entry0.Value = DependencyProperty.UnsetValue;
                        --_count;
                        return;
                    }
                    break;
 
                case 2:
                    if (_entry0.Key == key)
                    {
                        _entry0 = _entry1;
                        _entry1.Key = INVALIDKEY;
                        _entry1.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry1.Key == key)
                    {
                        _entry1.Key = INVALIDKEY;
                        _entry1.Value = DependencyProperty.UnsetValue;
                        --_count;
                    }
                    break;
 
                case 3:
                    if (_entry0.Key == key)
                    {
                        _entry0 = _entry1;
                        _entry1 = _entry2;
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry1.Key == key)
                    {
                        _entry1 = _entry2;
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry2.Key == key)
                    {
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    break;
 
                case 4:
                    if (_entry0.Key == key)
                    {
                        _entry0 = _entry1;
                        _entry1 = _entry2;
                        _entry2 = _entry3;
                        _entry3.Key = INVALIDKEY;
                        _entry3.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry1.Key == key)
                    {
                        _entry1 = _entry2;
                        _entry2 = _entry3;
                        _entry3.Key = INVALIDKEY;
                        _entry3.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry2.Key == key)
                    {
                        _entry2 = _entry3;
                        _entry3.Key = INVALIDKEY;
                        _entry3.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry3.Key == key)
                    {
                        _entry3.Key = INVALIDKEY;
                        _entry3.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    break;
 
                case 5:
                    if (_entry0.Key == key)
                    {
                        _entry0 = _entry1;
                        _entry1 = _entry2;
                        _entry2 = _entry3;
                        _entry3 = _entry4;
                        _entry4.Key = INVALIDKEY;
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry1.Key == key)
                    {
                        _entry1 = _entry2;
                        _entry2 = _entry3;
                        _entry3 = _entry4;
                        _entry4.Key = INVALIDKEY;
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry2.Key == key)
                    {
                        _entry2 = _entry3;
                        _entry3 = _entry4;
                        _entry4.Key = INVALIDKEY;
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry3.Key == key)
                    {
                        _entry3 = _entry4;
                        _entry4.Key = INVALIDKEY;
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry4.Key == key)
                    {
                        _entry4.Key = INVALIDKEY;
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    break;
 
                case 6:
                    if (_entry0.Key == key)
                    {
                        _entry0 = _entry1;
                        _entry1 = _entry2;
                        _entry2 = _entry3;
                        _entry3 = _entry4;
                        _entry4 = _entry5;
                        _entry5.Key = INVALIDKEY;
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry1.Key == key)
                    {
                        _entry1 = _entry2;
                        _entry2 = _entry3;
                        _entry3 = _entry4;
                        _entry4 = _entry5;
                        _entry5.Key = INVALIDKEY;
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry2.Key == key)
                    {
                        _entry2 = _entry3;
                        _entry3 = _entry4;
                        _entry4 = _entry5;
                        _entry5.Key = INVALIDKEY;
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry3.Key == key)
                    {
                        _entry3 = _entry4;
                        _entry4 = _entry5;
                        _entry5.Key = INVALIDKEY;
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry4.Key == key)
                    {
                        _entry4 = _entry5;
                        _entry5.Key = INVALIDKEY;
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    if (_entry5.Key == key)
                    {
                        _entry5.Key = INVALIDKEY;
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    }
                    break;
 
                default:
                    break;
            }
        }
 
        public override Object Search(int key)
        {
            Debug.Assert(INVALIDKEY != key);
            if (_count > 0)
            {
                if (_entry0.Key == key)
                {
                    return _entry0.Value;
                }
                if (_count > 1)
                {
                    if (_entry1.Key == key)
                    {
                        return _entry1.Value;
                    }
                    if (_count > 2)
                    {
                        if (_entry2.Key == key)
                        {
                            return _entry2.Value;
                        }
                        if (_count > 3)
                        {
                            if (_entry3.Key == key)
                            {
                                return _entry3.Value;
                            }
                            if (_count > 4)
                            {
                                if (_entry4.Key == key)
                                {
                                    return _entry4.Value;
                                }
                                if ((_count > 5) && (_entry5.Key == key))
                                {
                                    return _entry5.Value;
                                }
                            }
                        }
                    }
                }
            }
            return DependencyProperty.UnsetValue;
        }
 
        public override void Sort()
        {
            // If we're unsorted and we have entries to sort, do a simple
            // bubble sort. Sort the pairs, 0..5, and then again until we no
            // longer do any swapping.
            if ((false == _sorted) && (_count > 1))
            {
                bool swapped;
 
                do
                {
                    swapped = false;
 
                    Entry temp;
                    if (_entry0.Key > _entry1.Key)
                    {
                        temp = _entry0;
                        _entry0 = _entry1;
                        _entry1 = temp;
                        swapped = true;
                    }
                    if (_count > 2)
                    {
                        if (_entry1.Key > _entry2.Key)
                        {
                            temp = _entry1;
                            _entry1 = _entry2;
                            _entry2 = temp;
                            swapped = true;
                        }
                        if (_count > 3)
                        {
                            if (_entry2.Key > _entry3.Key)
                            {
                                temp = _entry2;
                                _entry2 = _entry3;
                                _entry3 = temp;
                                swapped = true;
                            }
                            if (_count > 4)
                            {
                                if (_entry3.Key > _entry4.Key)
                                {
                                    temp = _entry3;
                                    _entry3 = _entry4;
                                    _entry4 = temp;
                                    swapped = true;
                                }
                                if (_count > 5)
                                {
                                    if (_entry4.Key > _entry5.Key)
                                    {
                                        temp = _entry4;
                                        _entry4 = _entry5;
                                        _entry5 = temp;
                                        swapped = true;
                                    }
                                }
                            }
                        }
                    }
                }
                while (swapped);
                _sorted = true;
            }
        }
 
        public override void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (index < _count)
            {
                switch (index)
                {
                    case 0:
                        key = _entry0.Key;
                        value = _entry0.Value;
                        break;
 
                    case 1:
                        key = _entry1.Key;
                        value = _entry1.Value;
                        break;
 
                    case 2:
                        key = _entry2.Key;
                        value = _entry2.Value;
                        break;
 
                    case 3:
                        key = _entry3.Key;
                        value = _entry3.Value;
                        break;
 
                    case 4:
                        key = _entry4.Key;
                        value = _entry4.Value;
                        break;
 
                    case 5:
                        key = _entry5.Key;
                        value = _entry5.Value;
                        break;
 
                    default:
                        key = INVALIDKEY;
                        value = DependencyProperty.UnsetValue;
                        break;
                }
            }
            else
            {
                key = INVALIDKEY;
                value = DependencyProperty.UnsetValue;
                throw new ArgumentOutOfRangeException("index");
            }
        }
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        {
            if (_count > 0)
            {
                if (_count >= 1)
                {
                    callback(list, _entry0.Key, _entry0.Value);
                }
                if (_count >= 2)
                {
                    callback(list, _entry1.Key, _entry1.Value);
                }
                if (_count >= 3)
                {
                    callback(list, _entry2.Key, _entry2.Value);
                }
                if (_count >= 4)
                {
                    callback(list, _entry3.Key, _entry3.Value);
                }
                if (_count >= 5)
                {
                    callback(list, _entry4.Key, _entry4.Value);
                }
                if (_count == 6)
                {
                    callback(list, _entry5.Key, _entry5.Value);
                }
            }
        }
        
        public override void Promote(FrugalMapBase newMap)
        {
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry0.Key, _entry0.Value))
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry1.Key, _entry1.Value))
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry2.Key, _entry2.Value))
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry3.Key, _entry3.Value))
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry4.Key, _entry4.Value))
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry5.Key, _entry5.Value))
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
        }
 
        // Size of this data store
        public override int Count
        {
            get
            {
                return _count;
            }
        }
 
        private const int SIZE = 6;
 
        // The number of items in the map.
        private UInt16 _count;
 
        private bool _sorted;
        private Entry _entry0;
        private Entry _entry1;
        private Entry _entry2;
        private Entry _entry3;
        private Entry _entry4;
        private Entry _entry5;
    }
 
    /// <summary>
    /// A simple class to handle an array of between 6 and 12 key/value pairs.  It is unsorted
    /// and uses a linear search.  Perf analysis showed that this was the optimal size for both
    /// memory and perf.  The values may need to be adjusted as the CLR and Avalon evolve.
    /// </summary>
    internal sealed class ArrayObjectMap : FrugalMapBase
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        {
            // Check to see if we are updating an existing entry
            for (int index = 0; index < _count; ++index)
            {
                Debug.Assert(INVALIDKEY != key);
 
                if (_entries[index].Key == key)
                {
                    _entries[index].Value = value;
                    return FrugalMapStoreState.Success;
                }
            }
 
            // New key/value pair
            if (MAXSIZE > _count)
            {
                // Space still available to store the value
                if (null != _entries)
                {
                    // We are adding an entry to the array, so we may not be sorted any longer
                    _sorted = false;
 
                    if (_entries.Length > _count)
                    {
                        // Have empty entries, just set the first available
                    }
                    else
                    {
                        Entry[] destEntries = new Entry[_entries.Length + GROWTH];
 
                        // Copy old array
                        Array.Copy(_entries, 0, destEntries, 0, _entries.Length);
                        _entries = destEntries;
                    }
                }
                else
                {
                    _entries = new Entry[MINSIZE];
 
                    // No entries, must be sorted
                    _sorted = true;
                }
 
                // Stuff in the new key/value pair
                _entries[_count].Key = key;
                _entries[_count].Value = value;
 
                // Bump the count for the entry just added.
                ++_count;
 
                return FrugalMapStoreState.Success;
            }
            else
            {
                // Array is full, move to a SortedArray
                return FrugalMapStoreState.SortedArray;
            }
        }
 
        public override void RemoveEntry(int key)
        {
            for (int index = 0; index < _count; ++index)
            {
                if (_entries[index].Key == key)
                {
                    // Shift entries down
                    int numToCopy = (_count - index) - 1;
                    if (numToCopy > 0)
                    {
                        Array.Copy(_entries, index + 1, _entries, index, numToCopy);
                    }
 
                    // Wipe out the last entry
                    _entries[_count - 1].Key = INVALIDKEY;
                    _entries[_count - 1].Value = DependencyProperty.UnsetValue;
                    --_count;
                    break;
                }
            }
        }
 
        public override Object Search(int key)
        {
            for (int index = 0; index < _count; ++index)
            {
                if (key == _entries[index].Key)
                {
                    return _entries[index].Value;
                }
            }
            return DependencyProperty.UnsetValue;
        }
 
        public override void Sort()
        {
            if ((false == _sorted) && (_count > 1))
            {
                QSort(0, (_count - 1));
                _sorted = true;
            }
        }
 
        public override void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (index < _count)
            {
                value = _entries[index].Value;
                key = _entries[index].Key;
            }
            else
            {
                value = DependencyProperty.UnsetValue;
                key = INVALIDKEY;
                throw new ArgumentOutOfRangeException("index");
            }
        }
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        {
            if (_count > 0)
            {
                for (int i=0; i< _count; i++)
                {
                    callback(list, _entries[i].Key, _entries[i].Value);
                }
            }
        }
 
        public override void Promote(FrugalMapBase newMap)
        {
            for (int index = 0; index < _entries.Length; ++index)
            {
                if (FrugalMapStoreState.Success == newMap.InsertEntry(_entries[index].Key, _entries[index].Value))
                {
                    continue;
                }
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
        }
 
        // Size of this data store
        public override int Count
        {
            get
            {
                return _count;
            }
        }
 
        // Compare two Entry nodes in the _entries array
        private int Compare(int left, int right)
        {
            return (_entries[left].Key - _entries[right].Key);
        }
 
        // Partition the _entries array for QuickSort
        private int Partition(int left, int right)
        {
            int pivot = right;
            int i = left - 1;
            int j = right;
            Entry temp;
 
            for (;;)
            {
                while (Compare(++i, pivot) < 0);
                while (Compare(pivot, --j) < 0)
                {
                    if (j == left)
                    {
                        break;
                    }
                }
                if (i >= j)
                {
                    break;
                }
                temp = _entries[j];
                _entries[j] = _entries[i];
                _entries[i] = temp;
            }
            temp = _entries[right];
            _entries[right] = _entries[i];
            _entries[i] = temp;
            return i;
        }
 
        // Sort the _entries array using an index based QuickSort
        private void QSort(int left, int right)
        {
            if (left < right)
            {
                int pivot = Partition(left, right);
                QSort(left, pivot - 1);
                QSort(pivot + 1, right);
            }
        }
 
        // MINSIZE and GROWTH chosen to minimize memory footprint
        private const int MINSIZE = 9;
        private const int MAXSIZE = 15;
        private const int GROWTH = 3;
 
        // The number of items in the map.
        private UInt16 _count;
 
        private bool _sorted;
        private Entry[] _entries;
    }
 
    // A sorted array of key/value pairs. A binary search is used to minimize the cost of insert/search.
 
    internal sealed class SortedObjectMap : FrugalMapBase
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        {
            bool found;
 
            Debug.Assert(INVALIDKEY != key);
 
            // Check to see if we are updating an existing entry
            int index = FindInsertIndex(key, out found);
            if (found)
            {
                _entries[index].Value = value;
                return FrugalMapStoreState.Success;
            }
            else
            {
                // New key/value pair
                if (MAXSIZE > _count)
                {
                    // Less than the maximum array size
                    if (null != _entries)
                    {
                        if (_entries.Length > _count)
                        {
                            // Have empty entries, just set the first available
                        }
                        else
                        {
                            Entry[] destEntries = new Entry[_entries.Length + GROWTH];
 
                            // Copy old array
                            Array.Copy(_entries, 0, destEntries, 0, _entries.Length);
                            _entries = destEntries;
                        }
                    }
                    else
                    {
                        _entries = new Entry[MINSIZE];
                    }
 
                    // Inserting into the middle of the existing entries?
                    if (index < _count)
                    {
                        // Move higher valued keys to make room for the new key
                        Array.Copy(_entries, index, _entries, index + 1, (_count - index));
                    }
                    else
                    {
                        _lastKey = key;
                    }
 
                    // Stuff in the new key/value pair
                    _entries[index].Key = key;
                    _entries[index].Value = value;
                    ++_count;
                    return FrugalMapStoreState.Success;
                }
                else
                {
                    // SortedArray is full, move to a hashtable
                    return FrugalMapStoreState.Hashtable;
                }
            }
        }
 
        public override void RemoveEntry(int key)
        {
            bool found;
 
            Debug.Assert(INVALIDKEY != key);
 
            int index = FindInsertIndex(key, out found);
 
            if (found)
            {
                // Shift entries down
                int numToCopy = (_count - index) - 1;
                if (numToCopy > 0)
                {
                    Array.Copy(_entries, index + 1, _entries, index, numToCopy);
                }
                else 
                {
                    // If we're not copying anything, then it means we are 
                    //  going to remove the last entry.  Update _lastKey so
                    //  that it reflects the key of the new "last entry"
                    if( _count > 1 )
                    {
                        // Next-to-last entry will be the new last entry
                        _lastKey = _entries[_count - 2].Key;
                    }
                    else
                    {
                        // Unless there isn't a next-to-last entry, in which
                        //  case the key is reset to INVALIDKEY.
                        _lastKey = INVALIDKEY;
                    }
                }
 
                // Wipe out the last entry
                _entries[_count - 1].Key = INVALIDKEY;
                _entries[_count - 1].Value = DependencyProperty.UnsetValue;
 
                --_count;
            }
        }
 
        public override Object Search(int key)
        {
            bool found;
 
            int index = FindInsertIndex(key, out found);
            if (found)
            {
                return _entries[index].Value;
            }
            return DependencyProperty.UnsetValue;
        }
 
        public override void Sort()
        {
            // Always sorted.
        }
 
        public override void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (index < _count)
            {
                value = _entries[index].Value;
                key = _entries[index].Key;
            }
            else
            {
                value = DependencyProperty.UnsetValue;
                key = INVALIDKEY;
                throw new ArgumentOutOfRangeException("index");
            }
        }
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        {
            if (_count > 0)
            {
                for (int i=0; i< _count; i++)
                {
                    callback(list, _entries[i].Key, _entries[i].Value);
                }
            }
        }
 
        public override void Promote(FrugalMapBase newMap)
        {
            for (int index = 0; index < _entries.Length; ++index)
            {
                if (FrugalMapStoreState.Success == newMap.InsertEntry(_entries[index].Key, _entries[index].Value))
                {
                    continue;
                }
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
        }
 
        private int FindInsertIndex(int key, out bool found)
        {
            int iLo = 0;
 
            // Only do the binary search if there is a chance of finding the key
            // This also speeds insertion because we tend to insert at the end.
            if ((_count > 0) && (key <= _lastKey))
            {
                // The array index used for insertion is somewhere between 0 
                //  and _count-1 inclusive
                int iHi = _count-1;
 
                // Do a binary search to find the insertion point
                do
                {
                    int iPv = (iHi + iLo) / 2;
                    if (key <= _entries[iPv].Key)
                    {
                        iHi = iPv;
                    }
                    else
                    {
                        iLo = iPv + 1;
                    }
                }
                while (iLo < iHi);
                found = (key == _entries[iLo].Key);
            }
            else
            {
                // Insert point is at the end
                iLo = _count;
                found = false;
            }
            return iLo;
        }
 
        public override int Count
        {
            get
            {
                return _count;
            }
        }
 
        // MINSIZE chosen to be larger than MAXSIZE of the ArrayObjectMap with some extra space for new values
        // The MAXSIZE and GROWTH are chosen to minimize memory usage as we grow the array
        private const int MINSIZE = 16;
        private const int MAXSIZE = 128;
        private const int GROWTH = 8;
 
        // The number of items in the map.
        internal int _count;
 
        private int _lastKey = INVALIDKEY;
        private Entry[] _entries;
    }
 
    internal sealed class HashObjectMap : FrugalMapBase
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        {
            Debug.Assert(INVALIDKEY != key);
 
            if (null != _entries)
            {
                // This is done because forward branches
                // default prediction is not to be taken
                // making this a CPU win because insert
                // is a common operation.
            }
            else
            {
                _entries = new Hashtable(MINSIZE);
            }
 
            _entries[key] = ((value != NullValue) && (value != null)) ? value : NullValue;
            return FrugalMapStoreState.Success;
        }
 
        public override void RemoveEntry(int key)
        {
            _entries.Remove(key);
        }
 
        public override Object Search(int key)
        {
            object value = _entries[key];
 
            return ((value != NullValue) && (value != null)) ? value : DependencyProperty.UnsetValue;
        }
 
        public override void Sort()
        {
            // Always sorted.
        }
 
        public override void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (index < _entries.Count)
            {
                IDictionaryEnumerator myEnumerator = _entries.GetEnumerator();
 
                // Move to first valid value
                myEnumerator.MoveNext();
 
                for (int i = 0; i < index; ++i)
                {
                    myEnumerator.MoveNext();
                }
                key = (int)myEnumerator.Key;
                if ((myEnumerator.Value != NullValue) && (myEnumerator.Value != null))
                {
                    value = myEnumerator.Value;
                }
                else
                {
                    value = DependencyProperty.UnsetValue;
                }
            }
            else
            {
                value = DependencyProperty.UnsetValue;
                key = INVALIDKEY;
                throw new ArgumentOutOfRangeException("index");
            }
        }
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        {
            IDictionaryEnumerator myEnumerator = _entries.GetEnumerator();
            
            while (myEnumerator.MoveNext())
            {
                int key = (int)myEnumerator.Key;
                object value;
                if ((myEnumerator.Value != NullValue) && (myEnumerator.Value != null))
                {
                    value = myEnumerator.Value;
                }
                else
                {
                    value = DependencyProperty.UnsetValue;
                }
            
                callback(list, key, value);
            }
        }
 
        public override void Promote(FrugalMapBase newMap)
        {
            // Should never get here
            throw new InvalidOperationException(SR.Get(SRID.FrugalMap_CannotPromoteBeyondHashtable));
        }
 
        // Size of this data store
        public override int Count
        {
            get
            {
                return _entries.Count;
            }
        }
 
        // 163 is chosen because it is the first prime larger than 128, the MAXSIZE of SortedObjectMap
        internal const int MINSIZE = 163;
 
        // Hashtable will return null from its indexer if the key is not
        // found OR if the value is null.  To distinguish between these
        // two cases we insert NullValue instead of null.
        private static object NullValue = new object();
 
        internal Hashtable _entries;
    }
 
    [FriendAccessAllowed]
    internal struct FrugalMap
    {
        public object this[int key]
        {
            get
            {
                // If no entry, DependencyProperty.UnsetValue is returned
                if (null != _mapStore)
                {
                    return _mapStore.Search(key);
                }
                return DependencyProperty.UnsetValue;
            }
 
            set
            {
                if (value != DependencyProperty.UnsetValue)
                {
                    // If not unset value, ensure write success
                    if (null != _mapStore)
                    {
                        // This is done because forward branches
                        // default prediction is not to be taken
                        // making this a CPU win because set is
                        // a common operation.
                    }
                    else
                    {
                        _mapStore = new SingleObjectMap();
                    }
 
                    FrugalMapStoreState myState = _mapStore.InsertEntry(key, value);
                    if (FrugalMapStoreState.Success == myState)
                    {
                        return;
                    }
                    else
                    {
                        // Need to move to a more complex storage
                        FrugalMapBase newStore;
 
                        if (FrugalMapStoreState.ThreeObjectMap == myState)
                        {
                            newStore = new ThreeObjectMap();
                        }
                        else if (FrugalMapStoreState.SixObjectMap == myState)
                        {
                            newStore = new SixObjectMap();
                        }
                        else if (FrugalMapStoreState.Array == myState)
                        {
                            newStore = new ArrayObjectMap();
                        }
                        else if (FrugalMapStoreState.SortedArray == myState)
                        {
                            newStore = new SortedObjectMap();
                        }
                        else if (FrugalMapStoreState.Hashtable == myState)
                        {
                            newStore = new HashObjectMap();
                        }
                        else
                        {
                            throw new InvalidOperationException(SR.Get(SRID.FrugalMap_CannotPromoteBeyondHashtable));
                        }
 
                        // Extract the values from the old store and insert them into the new store
                        _mapStore.Promote(newStore);
 
                        // Insert the new value
                        _mapStore = newStore;
                        _mapStore.InsertEntry(key, value);
                    }
                }
                else
                {
                    // DependencyProperty.UnsetValue means remove the value
                    if (null != _mapStore)
                    {
                        _mapStore.RemoveEntry(key);
                        if (_mapStore.Count == 0)
                        {
                            // Map Store is now empty ... throw it away
                            _mapStore = null;
                        }
                    }
                }
            }
        }
 
        public void Sort()
        {
            if (null != _mapStore)
            {
                _mapStore.Sort();
            }
        }
 
        public void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (null != _mapStore)
            {
                _mapStore.GetKeyValuePair(index, out key, out value);
            }
            else
            {
                throw new ArgumentOutOfRangeException("index");
            }
        }
        
        public void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        {
            if (null != callback)
            {
                if (null != list)
                {
                    if (_mapStore != null)
                    {
                        _mapStore.Iterate(list, callback);
                    }
                }
                else
                {
                    throw new ArgumentNullException("list");
                }
            }
            else
            {
                throw new ArgumentNullException("callback");
            }
        }
 
        public int Count
        {
            get
            {
                if (null != _mapStore)
                {
                    return _mapStore.Count;
                }
                return 0;
            }
        }
 
        internal FrugalMapBase _mapStore;
    }
 
    // A sorted array of key/value pairs. A binary search is used to minimize the cost of insert/search.
 
    internal sealed class LargeSortedObjectMap : FrugalMapBase
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        {
            bool found;
 
            Debug.Assert(INVALIDKEY != key);
 
            // Check to see if we are updating an existing entry
            int index = FindInsertIndex(key, out found);
            if (found)
            {
                _entries[index].Value = value;
                return FrugalMapStoreState.Success;
            }
            else
            {
                // New key/value pair
                if (null != _entries)
                {
                    if (_entries.Length > _count)
                    {
                        // Have empty entries, just set the first available
                    }
                    else
                    {
                        int size = _entries.Length;
                        Entry[] destEntries = new Entry[size + (size >> 1)];
 
                        // Copy old array
                        Array.Copy(_entries, 0, destEntries, 0, _entries.Length);
                        _entries = destEntries;
                    }
                }
                else
                {
                    _entries = new Entry[MINSIZE];
                }
 
                // Inserting into the middle of the existing entries?
                if (index < _count)
                {
                    // Move higher valued keys to make room for the new key
                    Array.Copy(_entries, index, _entries, index + 1, (_count - index));
                }
                else
                {
                    _lastKey = key;
                }
 
                // Stuff in the new key/value pair
                _entries[index].Key = key;
                _entries[index].Value = value;
                ++_count;
                return FrugalMapStoreState.Success;
            }
        }
 
        public override void RemoveEntry(int key)
        {
            bool found;
 
            Debug.Assert(INVALIDKEY != key);
 
            int index = FindInsertIndex(key, out found);
 
            if (found)
            {
                // Shift entries down
                int numToCopy = (_count - index) - 1;
                if (numToCopy > 0)
                {
                    Array.Copy(_entries, index + 1, _entries, index, numToCopy);
                }
                else 
                {
                    // If we're not copying anything, then it means we are 
                    //  going to remove the last entry.  Update _lastKey so
                    //  that it reflects the key of the new "last entry"
                    if( _count > 1 )
                    {
                        // Next-to-last entry will be the new last entry
                        _lastKey = _entries[_count - 2].Key;
                    }
                    else
                    {
                        // Unless there isn't a next-to-last entry, in which
                        //  case the key is reset to INVALIDKEY.
                        _lastKey = INVALIDKEY;
                    }
                }
 
                // Wipe out the last entry
                _entries[_count - 1].Key = INVALIDKEY;
                _entries[_count - 1].Value = DependencyProperty.UnsetValue;
 
                --_count;
            }
        }
 
        public override Object Search(int key)
        {
            bool found;
 
            int index = FindInsertIndex(key, out found);
            if (found)
            {
                return _entries[index].Value;
            }
            return DependencyProperty.UnsetValue;
        }
 
        public override void Sort()
        {
            // Always sorted.
        }
 
        public override void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (index < _count)
            {
                value = _entries[index].Value;
                key = _entries[index].Key;
            }
            else
            {
                value = DependencyProperty.UnsetValue;
                key = INVALIDKEY;
                throw new ArgumentOutOfRangeException("index");
            }
        }
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        {
            if (_count > 0)
            {
                for (int i=0; i< _count; i++)
                {
                    callback(list, _entries[i].Key, _entries[i].Value);
                }
            }
        }
 
        public override void Promote(FrugalMapBase newMap)
        {
            for (int index = 0; index < _entries.Length; ++index)
            {
                if (FrugalMapStoreState.Success == newMap.InsertEntry(_entries[index].Key, _entries[index].Value))
                {
                    continue;
                }
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
        }
 
        private int FindInsertIndex(int key, out bool found)
        {
            int iLo = 0;
 
            // Only do the binary search if there is a chance of finding the key
            // This also speeds insertion because we tend to insert at the end.
            if ((_count > 0) && (key <= _lastKey))
            {
                // The array index used for insertion is somewhere between 0 
                //  and _count-1 inclusive
                int iHi = _count-1;
 
                // Do a binary search to find the insertion point
                do
                {
                    int iPv = (iHi + iLo) / 2;
                    if (key <= _entries[iPv].Key)
                    {
                        iHi = iPv;
                    }
                    else
                    {
                        iLo = iPv + 1;
                    }
                }
                while (iLo < iHi);
                found = (key == _entries[iLo].Key);
            }
            else
            {
                // Insert point is at the end
                iLo = _count;
                found = false;
            }
            return iLo;
        }
 
        public override int Count
        {
            get
            {
                return _count;
            }
        }
 
        // MINSIZE chosen to be small, growth rate of 1.5 is slow at small sizes, but increasingly agressive as
        // the array grows
        private const int MINSIZE = 2;
 
        // The number of items in the map.
        internal int _count;
 
        private int _lastKey = INVALIDKEY;
        private Entry[] _entries;
    }
 
    // This is a variant of FrugalMap that always uses an array as the underlying store.
    // This avoids the virtual method calls that are present when the store morphs through
    // the size efficient store classes normally used. It is appropriate only when we know the
    // store will always be populated and individual elements will be accessed in a tight loop.
    internal struct InsertionSortMap
    {
        public object this[int key]
        {
            get
            {
                // If no entry, DependencyProperty.UnsetValue is returned
                if (null != _mapStore)
                {
                    return _mapStore.Search(key);
                }
                return DependencyProperty.UnsetValue;
            }
 
            set
            {
                if (value != DependencyProperty.UnsetValue)
                {
                    // If not unset value, ensure write success
                    if (null != _mapStore)
                    {
                        // This is done because forward branches
                        // default prediction is not to be taken
                        // making this a CPU win because set is
                        // a common operation.
                    }
                    else
                    {
                        _mapStore = new LargeSortedObjectMap();
                    }
 
                    FrugalMapStoreState myState = _mapStore.InsertEntry(key, value);
                    if (FrugalMapStoreState.Success == myState)
                    {
                        return;
                    }
                    else
                    {
                        // Need to move to a more complex storage
                        LargeSortedObjectMap newStore;
 
                        if (FrugalMapStoreState.SortedArray == myState)
                        {
                            newStore = new LargeSortedObjectMap();
                        }
                        else
                        {
                            throw new InvalidOperationException(SR.Get(SRID.FrugalMap_CannotPromoteBeyondHashtable));
                        }
 
                        // Extract the values from the old store and insert them into the new store
                        _mapStore.Promote(newStore);
 
                        // Insert the new value
                        _mapStore = newStore;
                        _mapStore.InsertEntry(key, value);
                    }
                }
                else
                {
                    // DependencyProperty.UnsetValue means remove the value
                    if (null != _mapStore)
                    {
                        _mapStore.RemoveEntry(key);
                        if (_mapStore.Count == 0)
                        {
                            // Map Store is now empty ... throw it away
                            _mapStore = null;
                        }
                    }
                }
            }
        }
 
        public void Sort()
        {
            if (null != _mapStore)
            {
                _mapStore.Sort();
            }
        }
 
        public void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (null != _mapStore)
            {
                _mapStore.GetKeyValuePair(index, out key, out value);
            }
            else
            {
                throw new ArgumentOutOfRangeException("index");
            }
        }
 
        public void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        {
            if (null != callback)
            {
                if (null != list)
                {
                    if (_mapStore != null)
                    {
                        _mapStore.Iterate(list, callback);
                    }
                }
                else
                {
                    throw new ArgumentNullException("list");
                }
            }
            else
            {
                throw new ArgumentNullException("callback");
            }
        }
 
        public int Count
        {
            get
            {
                if (null != _mapStore)
                {
                    return _mapStore.Count;
                }
                return 0;
            }
        }
 
        internal LargeSortedObjectMap _mapStore;
    }
 
    /// <summary>
    ///     FrugalMapIterationCallback
    /// </summary>
    internal delegate void FrugalMapIterationCallback(ArrayList list, int key, object value);
}