FrugalList.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / Orcas / NetFXw7 / wpf / src / Shared / MS / Utility / FrugalList.cs / 1 / FrugalList.cs

                            //---------------------------------------------------------------------------- 
//
// Copyright (C) Microsoft Corporation.  All rights reserved.
//
//--------------------------------------------------------------------------- 

using System; 
using System.Diagnostics; 
using System.Collections;
using System.Collections.Generic; 
using System.Windows;
using System.Diagnostics.CodeAnalysis;
using MS.Internal.WindowsBase;
 
//using MS.Internal.PresentationCore;
//using SR=MS.Internal.WindowsBase.SR; 
//using SRID=MS.Internal.WindowsBase.SRID; 

    // These classes implement a frugal storage model for lists of type . 
    // Performance measurements show that Avalon has many lists that contain
    // a limited number of entries, and frequently zero or a single entry.
    // Therefore these classes are structured to prefer a storage model that
    // starts at zero, and employs a conservative growth strategy to minimize 
    // the steady state memory footprint. Also note that the list uses one
    // fewer objects than ArrayList and List and does no allocations at all 
    // until an item is inserted into the list. 
    //
    // The code is also structured to perform well from a CPU standpoint. Perf 
    // analysis shows that the reduced number of processor cache misses makes
    // FrugalList faster than ArrayList or List, especially for lists of 6
    // or fewer items. Timing differ with the size of .
    // 
    // FrugalList is appropriate for small lists or lists that grow slowly.
    // Due to the slow growth, if you use it for a list with more than 6 initial 
    // entires is best to set the capacity of the list at construction time or 
    // soon after. If you must grow the list by a large amount, set the capacity
    // or use Insert() method to force list growth to the final size. Choose 
    // your collections wisely and pay particular attention to the growth
    // patterns and search methods.

    // FrugalList has all of the methods of the Ilist interface, but implements 
    // them as virtual methods of the class and not as Interface methods. This
    // is to avoid the virtual stub dispatch CPU costs associated with Interfaces. 
 
    // We suppress two FxCop warnings in this module because not all usages
    // of FrugalList will instantiate all the storage classes and not all class instances 
    // will use every method.
    // CA1811:AvoidUncalledPrivateCode
    // CA1812:AvoidUninstantiatedInternalClasses
    // 

namespace MS.Utility 
{ 
    // These classes implement a frugal storage model for lists of .
    // Performance measurements show that many lists contain a single item. 
    // Therefore this list is structured to prefer a list that contains a single
    // item, and does conservative growth to minimize the memory footprint.

    // This enum controls the growth to successively more complex storage models 
    internal enum FrugalListStoreState
    { 
        Success, 
        SingleItemList,
        ThreeItemList, 
        SixItemList,
        Array
    }
 
    abstract class FrugalListBase
    { 
        ///  
        /// Number of entries in this store
        ///  
        // Number of entries in this store
        public int Count
        {
            get 
            {
                return _count; 
            } 
        }
 
        /// 
        /// Capacity of this store
        /// 
        public abstract int Capacity 
        {
            get; 
        } 

        // Increase size if needed, insert item into the store 
        public abstract FrugalListStoreState Add(T value);

        /// 
        /// Removes all values from the store 
        /// 
        public abstract void Clear(); 
 
        /// 
        /// Returns true if the store contains the entry. 
        /// 
        public abstract bool Contains(T value);

        ///  
        /// Returns the index into the store that contains the item.
        /// -1 is returned if the item is not in the store. 
        ///  
        public abstract int IndexOf(T value);
 
        /// 
        /// Insert item into the store at index, grows if needed
        /// 
        public abstract void Insert(int index, T value); 

        // Place item into the store at index 
        public abstract void SetAt(int index, T value); 

        ///  
        /// Removes the item from the store. If the item was not
        /// in the store false is returned.
        /// 
        public abstract bool Remove(T value); 

        ///  
        /// Removes the item from the store 
        /// 
        public abstract void RemoveAt(int index); 

        /// 
        /// Return the item at index in the store
        ///  
        public abstract T EntryAt(int index);
 
        ///  
        /// Promotes the values in the current store to the next larger
        /// and more complex storage model. 
        /// 
        public abstract void Promote(FrugalListBase newList);

        ///  
        /// Returns the entries as an array
        ///  
        public abstract T[] ToArray(); 

        ///  
        /// Copies the entries to the given array starting at the
        /// specified index
        /// 
        public abstract void CopyTo(T[] array, int index); 

        ///  
        /// Creates a shallow copy of the  list 
        /// 
        public abstract object Clone(); 

        // The number of items in the list.
        protected int _count;
    } 

    ///  
    /// A simple class to handle a single item 
    /// 
    internal sealed class SingleItemList : FrugalListBase 
    {
        // Capacity of this store
        public override int Capacity
        { 
            get
            { 
                return SIZE; 
            }
        } 

        public override FrugalListStoreState Add(T value)
        {
            // If we don't have any entries or the existing entry is being overwritten, 
            // then we can use this store. Otherwise we have to promote.
            if (0 == _count) 
            { 
                _loneEntry = value;
                ++_count; 
                return FrugalListStoreState.Success;
            }
            else
            { 
                // Entry already used, move to an ThreeItemList
                return FrugalListStoreState.ThreeItemList; 
            } 
        }
 
        public override void Clear()
        {
            // Wipe out the info
            _loneEntry = default(T); 
            _count = 0;
        } 
 
        public override bool Contains(T value)
        { 
            return _loneEntry.Equals(value);
        }

        public override int IndexOf(T value) 
        {
            if (_loneEntry.Equals(value)) 
            { 
                return 0;
            } 
            return -1;
        }

        public override void Insert(int index, T value) 
        {
            // Should only get here if count and index are 0 
            if ((_count < SIZE) && (index < SIZE)) 
            {
                _loneEntry = value; 
                ++_count;
                return;
            }
            throw new ArgumentOutOfRangeException("index"); 
        }
 
        public override void SetAt(int index, T value) 
        {
            // Overwrite item at index 
            _loneEntry = value;
        }

        public override bool Remove(T value) 
        {
            // Wipe out the info in the only entry if it matches the item. 
            if (_loneEntry.Equals(value)) 
            {
                _loneEntry = default(T); 
                --_count;
                return true;
            }
 
            return false;
        } 
 
        public override void RemoveAt(int index)
        { 
            // Wipe out the info at index
            if (0 == index)
            {
                _loneEntry = default(T); 
                --_count;
            } 
            else 
            {
                throw new ArgumentOutOfRangeException("index"); 
            }
        }

        public override T EntryAt(int index) 
        {
            return _loneEntry; 
        } 

        public override void Promote(FrugalListBase oldList) 
        {
            if (SIZE == oldList.Count)
            {
                SetCount(SIZE); 
                SetAt(0, oldList.EntryAt(0));
            } 
            else 
            {
                // this list is smaller than oldList 
                throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList");
            }
        }
 
        // Class specific implementation to avoid virtual method calls and additional logic
        public void Promote(SingleItemList oldList) 
        { 
            SetCount(oldList.Count);
            SetAt(0, oldList.EntryAt(0)); 
        }

        public override T[] ToArray()
        { 
            T[] array = new T[1];
            array[0] = _loneEntry; 
            return array; 
        }
 
        public override void CopyTo(T[] array, int index)
        {
            array[index] = _loneEntry;
        } 

        public override object Clone() 
        { 
            SingleItemList newList = new SingleItemList();
            newList.Promote(this); 
            return newList;
        }

        private void SetCount(int value) 
        {
            if ((value >= 0) && (value <= SIZE)) 
            { 
                _count = value;
            } 
            else
            {
                throw new ArgumentOutOfRangeException("Count");
            } 
        }
 
        private const int SIZE = 1; 

        private T _loneEntry; 
    }


    ///  
    /// A simple class to handle a list with 3 items.  Perf analysis showed
    /// that this yielded better memory locality and perf than an object and an array. 
    ///  
    internal sealed class ThreeItemList : FrugalListBase
    { 
        // Capacity of this store
        public override int Capacity
        {
            get 
            {
                return SIZE; 
            } 
        }
 
        public override FrugalListStoreState Add(T value)
        {
            switch (_count)
            { 
                case 0:
                    _entry0 = value; 
                    break; 

                case 1: 
                    _entry1 = value;
                    break;

                case 2: 
                    _entry2 = value;
                    break; 
 
                default:
                    // We have to promote 
                    return FrugalListStoreState.SixItemList;
            }
            ++_count;
            return FrugalListStoreState.Success; 
        }
 
        public override void Clear() 
        {
            // Wipe out the info. 
            _entry0 = default(T);
            _entry1 = default(T);
            _entry2 = default(T);
            _count = 0; 
        }
 
        public override bool Contains(T value) 
        {
            return (-1 != IndexOf(value)); 
        }

        public override int IndexOf(T value)
        { 
            if (_entry0.Equals(value))
            { 
                return 0; 
            }
            if (_count > 1) 
            {
                if (_entry1.Equals(value))
                {
                    return 1; 
                }
                if ((3 == _count) && (_entry2.Equals(value))) 
                { 
                    return 2;
                } 
            }
            return -1;
        }
 
        public override void Insert(int index, T value)
        { 
            // Should only get here if count < SIZE 
            if (_count < SIZE)
            { 
                switch (index)
                {
                    case 0:
                        _entry2 = _entry1; 
                        _entry1 = _entry0;
                        _entry0 = value; 
                        break; 

                    case 1: 
                        _entry2 = _entry1;
                        _entry1 = value;
                        break;
 
                    case 2:
                        _entry2 = value; 
                        break; 

                    default: 
                        throw new ArgumentOutOfRangeException("index");
                }
                ++_count;
                return; 
            }
            throw new ArgumentOutOfRangeException("index"); 
        } 

        public override void SetAt(int index, T value) 
        {
            // Overwrite item at index
            switch (index)
            { 
                case 0:
                    _entry0 = value; 
                    break; 

                case 1: 
                    _entry1 = value;
                    break;

                case 2: 
                    _entry2 = value;
                    break; 
 
                default:
                    throw new ArgumentOutOfRangeException("index"); 
            }
        }

        public override bool Remove(T value) 
        {
            // If the item 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.
            if (_entry0.Equals(value)) 
            {
                RemoveAt(0);
                return true;
            } 
            else if ( _count > 1)
            { 
                if (_entry1.Equals(value)) 
                {
                    RemoveAt(1); 
                    return true;
                }
                else if ((3 == _count) && (_entry2.Equals(value)))
                { 
                    RemoveAt(2);
                    return true; 
                } 
            }
            return false; 
        }

        public override void RemoveAt(int index)
        { 
            // Remove entry at index, 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 (index)
            { 
                case 0:
                    _entry0 = _entry1;
                    _entry1 = _entry2;
                    break; 

                case 1: 
                    _entry1 = _entry2; 
                    break;
 
                case 2:
                    break;

                default: 
                    throw new ArgumentOutOfRangeException("index");
            } 
            _entry2 = default(T); 
            --_count;
        } 

        public override T EntryAt(int index)
        {
            switch (index) 
            {
                case 0: 
                    return _entry0; 

                case 1: 
                    return _entry1;

                case 2:
                    return _entry2; 

                default: 
                    throw new ArgumentOutOfRangeException("index"); 
            }
        } 

        public override void Promote(FrugalListBase oldList)
        {
            int oldCount = oldList.Count; 
            if (SIZE >= oldCount)
            { 
                SetCount(oldList.Count); 

                switch (oldCount) 
                {
                    case 3:
                        SetAt(0, oldList.EntryAt(0));
                        SetAt(1, oldList.EntryAt(1)); 
                        SetAt(2, oldList.EntryAt(2));
                        break; 
 
                    case 2:
                        SetAt(0, oldList.EntryAt(0)); 
                        SetAt(1, oldList.EntryAt(1));
                        break;

                    case 1: 
                        SetAt(0, oldList.EntryAt(0));
                        break; 
 
                    case 0:
                        break; 

                    default:
                        throw new ArgumentOutOfRangeException("index");
                } 
            }
            else 
            { 
                // this list is smaller than oldList
                throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); 
            }
        }

        // Class specific implementation to avoid virtual method calls and additional logic 
        public void Promote(SingleItemList oldList)
        { 
            SetCount(oldList.Count); 
            SetAt(0, oldList.EntryAt(0));
        } 

        // Class specific implementation to avoid virtual method calls and additional logic
        public void Promote(ThreeItemList oldList)
        { 
            int oldCount = oldList.Count;
            SetCount(oldList.Count); 
 
            switch (oldCount)
            { 
                case 3:
                    SetAt(0, oldList.EntryAt(0));
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    break;
 
                case 2: 
                    SetAt(0, oldList.EntryAt(0));
                    SetAt(1, oldList.EntryAt(1)); 
                    break;

                case 1:
                    SetAt(0, oldList.EntryAt(0)); 
                    break;
 
                case 0: 
                    break;
 
                default:
                    throw new ArgumentOutOfRangeException("index");
            }
        } 

        public override T[] ToArray() 
        { 
            T[] array = new T[_count];
 
            array[0] = _entry0;
            if (_count >= 2)
            {
                array[1] = _entry1; 
                if (_count == 3)
                { 
                    array[2] = _entry2; 
                }
            } 
            return array;
        }

        public override void CopyTo(T[] array, int index) 
        {
            array[index] = _entry0; 
            if (_count >= 2) 
            {
                array[index+1] = _entry1; 
                if (_count == 3)
                {
                    array[index+2] = _entry2;
                } 
            }
        } 
 
        public override object Clone()
        { 
            ThreeItemList newList = new ThreeItemList();
            newList.Promote(this);
            return newList;
        } 

        private void SetCount(int value) 
        { 
            if ((value >= 0) && (value <= SIZE))
            { 
                _count = value;
            }
            else
            { 
                throw new ArgumentOutOfRangeException("Count");
            } 
        } 

        private const int SIZE = 3; 

        private T _entry0;
        private T _entry1;
        private T _entry2; 
    }
 
    ///  
    /// A simple class to handle a list with 6 items.
    ///  
    internal sealed class SixItemList : FrugalListBase
    {
        // Capacity of this store
        public override int Capacity 
        {
            get 
            { 
                return SIZE;
            } 
        }

        public override FrugalListStoreState Add(T value)
        { 
            switch (_count)
            { 
                case 0: 
                    _entry0 = value;
                    break; 

                case 1:
                    _entry1 = value;
                    break; 

                case 2: 
                    _entry2 = value; 
                    break;
 
                case 3:
                    _entry3 = value;
                    break;
 
                case 4:
                    _entry4 = value; 
                    break; 

                case 5: 
                    _entry5 = value;
                    break;

                default: 
                    // We have to promote
                    return FrugalListStoreState.Array; 
            } 
            ++_count;
            return FrugalListStoreState.Success; 
        }

        public override void Clear()
        { 
            // Wipe out the info.
            _entry0 = default(T); 
            _entry1 = default(T); 
            _entry2 = default(T);
            _entry3 = default(T); 
            _entry4 = default(T);
            _entry5 = default(T);
            _count = 0;
        } 

        public override bool Contains(T value) 
        { 
            return (-1 != IndexOf(value));
        } 

        public override int IndexOf(T value)
        {
            if (_entry0.Equals(value)) 
            {
                return 0; 
            } 
            if (_count > 1)
            { 
                if (_entry1.Equals(value))
                {
                    return 1;
                } 
                if (_count > 2)
                { 
                    if (_entry2.Equals(value)) 
                    {
                        return 2; 
                    }
                    if (_count > 3)
                    {
                        if (_entry3.Equals(value)) 
                        {
                            return 3; 
                        } 
                        if (_count > 4)
                        { 
                            if (_entry4.Equals(value))
                            {
                                return 4;
                            } 
                            if ((6 == _count) && (_entry5.Equals(value)))
                            { 
                                return 5; 
                            }
                        } 
                    }
                }
            }
            return -1; 
        }
 
        public override void Insert(int index, T value) 
        {
            // Should only get here if count is less than SIZE 
            if (_count < SIZE)
            {
                switch (index)
                { 
                    case 0:
                        _entry5 = _entry4; 
                        _entry4 = _entry3; 
                        _entry3 = _entry2;
                        _entry2 = _entry1; 
                        _entry1 = _entry0;
                        _entry0 = value;
                        break;
 
                    case 1:
                        _entry5 = _entry4; 
                        _entry4 = _entry3; 
                        _entry3 = _entry2;
                        _entry2 = _entry1; 
                        _entry1 = value;
                        break;

                    case 2: 
                        _entry5 = _entry4;
                        _entry4 = _entry3; 
                        _entry3 = _entry2; 
                        _entry2 = value;
                        break; 

                    case 3:
                        _entry5 = _entry4;
                        _entry4 = _entry3; 
                        _entry3 = value;
                        break; 
 
                    case 4:
                        _entry5 = _entry4; 
                        _entry4 = value;
                        break;

                    case 5: 
                        _entry5 = value;
                        break; 
 
                    default:
                        throw new ArgumentOutOfRangeException("index"); 
                }
                ++_count;
                return;
            } 
            throw new ArgumentOutOfRangeException("index");
        } 
 
        public override void SetAt(int index, T value)
        { 
            // Overwrite item at index
            switch (index)
            {
                case 0: 
                    _entry0 = value;
                    break; 
 
                case 1:
                    _entry1 = value; 
                    break;

                case 2:
                    _entry2 = value; 
                    break;
 
                case 3: 
                    _entry3 = value;
                    break; 

                case 4:
                    _entry4 = value;
                    break; 

                case 5: 
                    _entry5 = value; 
                    break;
 
                default:
                    throw new ArgumentOutOfRangeException("index");
            }
        } 

        public override bool Remove(T value) 
        { 
            // If the item matches an existing entry, wipe out the last
            // entry and move all the other entries up.  Because we only 
            // have six entries we can just unravel all the cases.
            if (_entry0.Equals(value))
            {
                RemoveAt(0); 
                return true;
            } 
            else if (_count > 1) 
            {
                if (_entry1.Equals(value)) 
                {
                    RemoveAt(1);
                    return true;
                } 
                else if (_count > 2)
                { 
                    if (_entry2.Equals(value)) 
                    {
                        RemoveAt(2); 
                        return true;
                    }
                    else if (_count > 3)
                    { 
                        if (_entry3.Equals(value))
                        { 
                            RemoveAt(3); 
                            return true;
                        } 
                        else if (_count > 4)
                        {
                            if (_entry4.Equals(value))
                            { 
                                RemoveAt(4);
                                return true; 
                            } 
                            else if ((6 == _count) && (_entry5.Equals(value)))
                            { 
                                RemoveAt(5);
                                return true;
                            }
                        } 
                    }
                } 
            } 

            return false; 
        }

        public override void RemoveAt(int index)
        { 
            // Remove entry at index, wipe out the last entry and move
            // all the other entries up. Because we only have six 
            // entries we can just unravel all the cases. 
            switch (index)
            { 
                case 0:
                    _entry0 = _entry1;
                    _entry1 = _entry2;
                    _entry2 = _entry3; 
                    _entry3 = _entry4;
                    _entry4 = _entry5; 
                    break; 

                case 1: 
                    _entry1 = _entry2;
                    _entry2 = _entry3;
                    _entry3 = _entry4;
                    _entry4 = _entry5; 
                    break;
 
                case 2: 
                    _entry2 = _entry3;
                    _entry3 = _entry4; 
                    _entry4 = _entry5;
                    break;

                case 3: 
                    _entry3 = _entry4;
                    _entry4 = _entry5; 
                    break; 

                case 4: 
                    _entry4 = _entry5;
                    break;

                case 5: 
                    break;
 
                default: 
                    throw new ArgumentOutOfRangeException("index");
            } 
            _entry5 = default(T);
            --_count;
        }
 
        public override T EntryAt(int index)
        { 
            switch (index) 
            {
                case 0: 
                    return _entry0;

                case 1:
                    return _entry1; 

                case 2: 
                    return _entry2; 

                case 3: 
                    return _entry3;

                case 4:
                    return _entry4; 

                case 5: 
                    return _entry5; 

                default: 
                    throw new ArgumentOutOfRangeException("index");
            }
        }
 
        public override void Promote(FrugalListBase oldList)
        { 
            int oldCount = oldList.Count; 
            if (SIZE >= oldCount)
            { 
                SetCount(oldList.Count);

                switch (oldCount)
                { 
                    case 6:
                        SetAt(0, oldList.EntryAt(0)); 
                        SetAt(1, oldList.EntryAt(1)); 
                        SetAt(2, oldList.EntryAt(2));
                        SetAt(3, oldList.EntryAt(3)); 
                        SetAt(4, oldList.EntryAt(4));
                        SetAt(5, oldList.EntryAt(5));
                        break;
 
                    case 5:
                        SetAt(0, oldList.EntryAt(0)); 
                        SetAt(1, oldList.EntryAt(1)); 
                        SetAt(2, oldList.EntryAt(2));
                        SetAt(3, oldList.EntryAt(3)); 
                        SetAt(4, oldList.EntryAt(4));
                        break;

                    case 4: 
                        SetAt(0, oldList.EntryAt(0));
                        SetAt(1, oldList.EntryAt(1)); 
                        SetAt(2, oldList.EntryAt(2)); 
                        SetAt(3, oldList.EntryAt(3));
                        break; 

                    case 3:
                        SetAt(0, oldList.EntryAt(0));
                        SetAt(1, oldList.EntryAt(1)); 
                        SetAt(2, oldList.EntryAt(2));
                        break; 
 
                    case 2:
                        SetAt(0, oldList.EntryAt(0)); 
                        SetAt(1, oldList.EntryAt(1));
                        break;

                    case 1: 
                        SetAt(0, oldList.EntryAt(0));
                        break; 
 
                    case 0:
                        break; 

                    default:
                        throw new ArgumentOutOfRangeException("index");
                } 
            }
            else 
            { 
                // this list is smaller than oldList
                throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); 
            }
        }

        // Class specific implementation to avoid virtual method calls and additional logic 
        public void Promote(ThreeItemList oldList)
        { 
            int oldCount = oldList.Count; 
            if (SIZE <= oldCount)
            { 
                SetCount(oldList.Count);

                switch (oldCount)
                { 
                    case 3:
                        SetAt(0, oldList.EntryAt(0)); 
                        SetAt(1, oldList.EntryAt(1)); 
                        SetAt(2, oldList.EntryAt(2));
                        break; 

                    case 2:
                        SetAt(0, oldList.EntryAt(0));
                        SetAt(1, oldList.EntryAt(1)); 
                        break;
 
                    case 1: 
                        SetAt(0, oldList.EntryAt(0));
                        break; 

                    case 0:
                        break;
 
                    default:
                        throw new ArgumentOutOfRangeException("index"); 
                } 
            }
            else 
            {
                // this list is smaller than oldList
                throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList");
            } 
        }
 
        // Class specific implementation to avoid virtual method calls and additional logic 
        public void Promote(SixItemList oldList)
        { 
            int oldCount = oldList.Count;
            SetCount(oldList.Count);

            switch (oldCount) 
            {
                case 6: 
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    SetAt(3, oldList.EntryAt(3));
                    SetAt(4, oldList.EntryAt(4));
                    SetAt(5, oldList.EntryAt(5));
                    break; 

                case 5: 
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    SetAt(3, oldList.EntryAt(3));
                    SetAt(4, oldList.EntryAt(4));
                    break;
 
                case 4:
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1)); 
                    SetAt(2, oldList.EntryAt(2));
                    SetAt(3, oldList.EntryAt(3)); 
                    break;

                case 3:
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    break; 

                case 2: 
                    SetAt(0, oldList.EntryAt(0));
                    SetAt(1, oldList.EntryAt(1));
                    break;
 
                case 1:
                    SetAt(0, oldList.EntryAt(0)); 
                    break; 

                case 0: 
                    break;

                default:
                    throw new ArgumentOutOfRangeException("index"); 
            }
        } 
 
        public override T[] ToArray()
        { 
            T[] array = new T[_count];

            if (_count >= 1)
            { 
                array[0] = _entry0;
                if (_count >= 2) 
                { 
                    array[1] = _entry1;
                    if (_count >= 3) 
                    {
                        array[2] = _entry2;
                        if (_count >= 4)
                        { 
                            array[3] = _entry3;
                            if (_count >= 5) 
                            { 
                                array[4] = _entry4;
                                if (_count == 6) 
                                {
                                    array[5] = _entry5;
                                }
                            } 
                        }
                    } 
                } 
            }
            return array; 
        }

        public override void CopyTo(T[] array, int index)
        { 
            if (_count >= 1)
            { 
                array[index] = _entry0; 
                if (_count >= 2)
                { 
                    array[index+1] = _entry1;
                    if (_count >= 3)
                    {
                        array[index+2] = _entry2; 
                        if (_count >= 4)
                        { 
                            array[index+3] = _entry3; 
                            if (_count >= 5)
                            { 
                                array[index+4] = _entry4;
                                if (_count == 6)
                                {
                                    array[index+5] = _entry5; 
                                }
                            } 
                        } 
                    }
                } 
            }
        }

        public override object Clone() 
        {
            SixItemList newList = new SixItemList(); 
            newList.Promote(this); 
            return newList;
        } 

        private void SetCount(int value)
        {
            if ((value >= 0) && (value <= SIZE)) 
            {
                _count = value; 
            } 
            else
            { 
                throw new ArgumentOutOfRangeException("Count");
            }
        }
 
        private const int SIZE = 6;
 
        private T _entry0; 
        private T _entry1;
        private T _entry2; 
        private T _entry3;
        private T _entry4;
        private T _entry5;
    } 

    ///  
    /// A simple class to handle an array of 7 or more items.  It is unsorted and uses 
    /// a linear search.
    ///  
    internal sealed class ArrayItemList : FrugalListBase
    {
        public ArrayItemList()
        { 
        }
 
        public ArrayItemList(int size) 
        {
            // Make size a multiple of GROWTH 
            size += (GROWTH - 1);
            size -= (size % GROWTH);
            _entries = new T[size];
        } 

        public ArrayItemList(ICollection collection) 
        { 
            if (collection != null)
            { 
                _count = collection.Count;
                _entries = new T[_count];
                collection.CopyTo(_entries, 0);
            } 
        }
 
        public ArrayItemList(ICollection collection) 
        {
            if (collection != null) 
            {
                _count = collection.Count;
                _entries = new T[_count];
                collection.CopyTo(_entries, 0); 
            }
        } 
 
        // Capacity of this store
        public override int Capacity 
        {
            get
            {
                if (_entries != null) 
                {
                    return _entries.Length; 
                } 
                return 0;
            } 
        }

        public override FrugalListStoreState Add(T value)
        { 
            // If we don't have any entries or the existing entry is being overwritten,
            // then we can use this store. Otherwise we have to promote. 
            if ((null != _entries) && (_count < _entries.Length)) 
            {
                _entries[_count] = value; 
                ++_count;
            }
            else
            { 
                if (null != _entries)
                { 
                    int size = _entries.Length; 

                    // Grow the list slowly while it is small but 
                    // faster once it reaches the LARGEGROWTH size
                    if (size < LARGEGROWTH)
                    {
                        size += GROWTH; 
                    }
                    else 
                    { 
                        size += size >> 2;
                    } 

                    T[] destEntries = new T[size];

                    // Copy old array 
                    Array.Copy(_entries, 0, destEntries, 0, _entries.Length);
                    _entries = destEntries; 
                } 
                else
                { 
                    _entries = new T[MINSIZE];
                }

                // Insert into new array 
                _entries[_count] = value;
                ++_count; 
            } 
            return FrugalListStoreState.Success;
        } 

        public override void Clear()
        {
            // Wipe out the info. 
            for (int i = 0; i < _count; ++i)
            { 
                _entries[i] = default(T); 
            }
            _count = 0; 
        }

        public override bool Contains(T value)
        { 
            return (-1 != IndexOf(value));
        } 
 
        public override int IndexOf(T value)
        { 
            for (int index = 0; index < _count; ++index)
            {
                if (_entries[index].Equals(value))
                { 
                    return index;
                } 
            } 
            return -1;
        } 

        public override void Insert(int index, T value)
        {
            if ((null != _entries) && (_count < _entries.Length)) 
            {
                // Move down the required number of items 
                Array.Copy(_entries, index, _entries, index + 1, _count - index); 

                // Put in the new item at the specified index 
                _entries[index] = value;
                ++_count;
                return;
            } 
            throw new ArgumentOutOfRangeException("index");
        } 
 
        public override void SetAt(int index, T value)
        { 
            // Overwrite item at index
            _entries[index] = value;
        }
 
        public override bool Remove(T value)
        { 
            for (int index = 0; index < _count; ++index) 
            {
                if (_entries[index].Equals(value)) 
                {
                    RemoveAt(index);
                    return true;
                } 
            }
 
            return false; 
        }
 
        public override void RemoveAt(int index)
        {
            // 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] = default(T);
            --_count;
            return; 
        }
 
        public override T EntryAt(int index) 
        {
            return _entries[index]; 
        }

        public override void Promote(FrugalListBase oldList)
        { 
            for (int index = 0; index < oldList.Count; ++index)
            { 
                if (FrugalListStoreState.Success == Add(oldList.EntryAt(index))) 
                {
                    continue; 
                }
                // this list is smaller than oldList
                throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList");
            } 
        }
 
        // Class specific implementation to avoid virtual method calls and additional logic 
        public void Promote(SixItemList oldList)
        { 
            int oldCount = oldList.Count;
            SetCount(oldList.Count);

            switch (oldCount) 
            {
                case 6: 
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    SetAt(3, oldList.EntryAt(3));
                    SetAt(4, oldList.EntryAt(4));
                    SetAt(5, oldList.EntryAt(5));
                    break; 

                case 5: 
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    SetAt(3, oldList.EntryAt(3));
                    SetAt(4, oldList.EntryAt(4));
                    break;
 
                case 4:
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1)); 
                    SetAt(2, oldList.EntryAt(2));
                    SetAt(3, oldList.EntryAt(3)); 
                    break;

                case 3:
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    break; 

                case 2: 
                    SetAt(0, oldList.EntryAt(0));
                    SetAt(1, oldList.EntryAt(1));
                    break;
 
                case 1:
                    SetAt(0, oldList.EntryAt(0)); 
                    break; 

                case 0: 
                    break;

                default:
                    throw new ArgumentOutOfRangeException("index"); 
            }
        } 
 
        // Class specific implementation to avoid virtual method calls and additional logic
        public void Promote(ArrayItemList oldList) 
        {
            int oldCount = oldList.Count;
            if (_entries.Length >= oldCount)
            { 
                SetCount(oldList.Count);
 
                for (int index = 0; index < oldCount; ++index) 
                {
                    SetAt(index, oldList.EntryAt(index)); 
                }
            }
            else
            { 
                // this list is smaller than oldList
                throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); 
            } 
        }
 
        public override T[] ToArray()
        {
            T[] array = new T[_count];
 
            for (int i = 0; i < _count; ++i)
            { 
                array[i] = _entries[i]; 
            }
            return array; 
        }

        public override void CopyTo(T[] array, int index)
        { 
            for (int i = 0; i < _count; ++i)
            { 
                array[index+i] = _entries[i]; 
            }
        } 

        public override object Clone()
        {
            ArrayItemList newList = new ArrayItemList(this.Capacity); 
            newList.Promote(this);
            return newList; 
        } 

        private void SetCount(int value) 
        {
            if ((value >= 0) && (value <= _entries.Length))
            {
                _count = value; 
            }
            else 
            { 
                throw new ArgumentOutOfRangeException("Count");
            } 
        }

        // MINSIZE and GROWTH chosen to minimize memory footprint
        private const int MINSIZE = 9; 
        private const int GROWTH = 3;
        private const int LARGEGROWTH = 18; 
 
        private T[] _entries;
    } 

    // Use FrugalObjectList when more than one reference to the list is needed.
    // The "object" in FrugalObjectLIst refers to the list itself, not what the list contains.
 
    [FriendAccessAllowed] // Built into Core, also used by Framework.
    internal class FrugalObjectList 
    { 
        public FrugalObjectList()
        { 
        }

        public FrugalObjectList(int size)
        { 
            Capacity = size;
        } 
 
        public int Capacity
        { 
            get
            {
                if (null != _listStore)
                { 
                    return _listStore.Capacity;
                } 
                return 0; 
            }
            set 
            {
                int capacity = 0;
                if (null != _listStore)
                { 
                    capacity = _listStore.Capacity;
                } 
                if (capacity < value) 
                {
                    // Need to move to a more complex storage 
                    FrugalListBase newStore;

                    if (value == 1)
                    { 
                        newStore = new SingleItemList();
                    } 
                    else if (value <= 3) 
                    {
                        newStore = new ThreeItemList(); 
                    }
                    else if (value <= 6)
                    {
                        newStore = new SixItemList(); 
                    }
                    else 
                    { 
                        newStore = new ArrayItemList(value);
                    } 

                    if (null != _listStore)
                    {
                        // Move entries in the old store to the new one 
                        newStore.Promote(_listStore);
                    } 
 
                    _listStore = newStore;
                } 
            }
        }

        public int Count 
        {
            get 
            { 
                if (null != _listStore)
                { 
                    return _listStore.Count;
                }
                return 0;
            } 
        }
 
 
        public T this[int index]
        { 
            get
            {
                // If no entry, default(T) is returned
                if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) 
                {
                    return _listStore.EntryAt(index); 
                } 
                throw new ArgumentOutOfRangeException("index");
            } 

            set
            {
                // Ensure write success 
                if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0)))
                { 
                    _listStore.SetAt(index, value); 
                    return;
                } 
                throw new ArgumentOutOfRangeException("index");
            }
        }
 
        public int Add(T value)
        { 
            if (null != _listStore) 
            {
                // This is done because forward branches 
                // default prediction is not to be taken
                // making this a CPU win because Add is
                // a common operation.
            } 
            else
            { 
                _listStore = new SingleItemList(); 
            }
 
            FrugalListStoreState myState = _listStore.Add(value);
            if (FrugalListStoreState.Success == myState)
            {
            } 
            else
            { 
                // Need to move to a more complex storage 
                // Allocate the store, promote, and add using the derived classes
                // to avoid virtual method calls 

                if (FrugalListStoreState.ThreeItemList == myState)
                {
                    ThreeItemList newStore = new ThreeItemList(); 

                    // Extract the values from the old store and insert them into the new store 
                    newStore.Promote(_listStore); 

                    // Insert the new item 
                    newStore.Add(value);
                    _listStore = newStore;
                }
                else if (FrugalListStoreState.SixItemList == myState) 
                {
                    SixItemList newStore = new SixItemList(); 
 
                    // Extract the values from the old store and insert them into the new store
                    newStore.Promote(_listStore); 
                    _listStore = newStore;

                    // Insert the new item
                    newStore.Add(value); 
                    _listStore = newStore;
                } 
                else if (FrugalListStoreState.Array == myState) 
                {
                    ArrayItemList newStore = new ArrayItemList(_listStore.Count + 1); 

                    // Extract the values from the old store and insert them into the new store
                    newStore.Promote(_listStore);
                    _listStore = newStore; 

                    // Insert the new item 
                    newStore.Add(value); 
                    _listStore = newStore;
                } 
                else
                {
                    throw new InvalidOperationException(SR.Get(SRID.FrugalList_CannotPromoteBeyondArray));
                } 
            }
            return _listStore.Count - 1; 
        } 

        public void Clear() 
        {
            if (null != _listStore)
            {
                _listStore.Clear(); 
            }
        } 
 
        public bool Contains(T value)
        { 
            if ((null != _listStore) && (_listStore.Count > 0))
            {
                return _listStore.Contains(value);
            } 
            return false;
        } 
 
        public int IndexOf(T value)
        { 
            if ((null != _listStore) && (_listStore.Count > 0))
            {
                return _listStore.IndexOf(value);
            } 
            return -1;
        } 
 
        public void Insert(int index, T value)
        { 
            if ((index == 0) || ((null != _listStore) && ((index <= _listStore.Count) && (index >= 0))))
            {
                // Make sure we have a place to put the item
                int minCapacity = 1; 

                if ((null != _listStore) && (_listStore.Count == _listStore.Capacity)) 
                { 
                    // Store is full
                    minCapacity = Capacity + 1; 
                }

                // Make the Capacity at *least* this big
                Capacity = minCapacity; 

                _listStore.Insert(index, value); 
                return; 
            }
            throw new ArgumentOutOfRangeException("index"); 
        }

        public bool Remove(T value)
        { 
            if ((null != _listStore) && (_listStore.Count > 0))
            { 
                return _listStore.Remove(value); 
            }
            return false; 
        }

        public void RemoveAt(int index)
        { 
            if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0)))
            { 
                _listStore.RemoveAt(index); 
                return;
            } 
            throw new ArgumentOutOfRangeException("index");
        }

        public void EnsureIndex(int index) 
        {
            if (index >= 0) 
            { 
                int delta = (index + 1) - Count;
                if (delta > 0) 
                {
                    // Grow the store
                    Capacity = index + 1;
 
                    T filler = default(T);
 
                    // Insert filler structs or objects 
                    for (int i = 0; i < delta; ++i)
                    { 
                        _listStore.Add(filler);
                    }
                }
                return; 
            }
            throw new ArgumentOutOfRangeException("index"); 
        } 

        public T[] ToArray() 
        {
            if ((null != _listStore) && (_listStore.Count > 0))
            {
                return _listStore.ToArray(); 
            }
            return null; 
        } 

        public void CopyTo(T[] array, int index) 
        {
            if ((null != _listStore) && (_listStore.Count > 0))
            {
                _listStore.CopyTo(array, index); 
            }
        } 
 
        public FrugalObjectList Clone()
        { 
            FrugalObjectList myClone = new FrugalObjectList();

            if (null != _listStore)
            { 
                myClone._listStore = (FrugalListBase)_listStore.Clone();
            } 
 
            return myClone;
        } 

        internal FrugalListBase _listStore;
    }
 
    // Use FrugalStructList when only one reference to the list is needed.
    // The "struct" in FrugalStructList refers to the list itself, not what the list contains. 
    [FriendAccessAllowed] // Built into Core, also used by Framework. 
    internal struct FrugalStructList
    { 
        public FrugalStructList(int size)
        {
            _listStore = null;
            Capacity = size; 
        }
 
        public FrugalStructList(ICollection collection) 
        {
            if (collection.Count > 6) 
            {
                _listStore = new ArrayItemList(collection);
            }
            else 
            {
                _listStore = null; 
                Capacity = collection.Count; 
                foreach (T item in collection)
                { 
                    Add(item);
                }
            }
        } 

        public FrugalStructList(ICollection collection) 
        { 
            if (collection.Count > 6)
            { 
                _listStore = new ArrayItemList(collection);
            }
            else
            { 
                _listStore = null;
                Capacity = collection.Count; 
                foreach (T item in collection) 
                {
                    Add(item); 
                }
            }
        }
 
        public int Capacity
        { 
            get 
            {
                if (null != _listStore) 
                {
                    return _listStore.Capacity;
                }
                return 0; 
            }
            set 
            { 
                int capacity = 0;
                if (null != _listStore) 
                {
                    capacity = _listStore.Capacity;
                }
                if (capacity < value) 
                {
                    // Need to move to a more complex storage 
                    FrugalListBase newStore; 

                    if (value == 1) 
                    {
                        newStore = new SingleItemList();
                    }
                    else if (value <= 3) 
                    {
                        newStore = new ThreeItemList(); 
                    } 
                    else if (value <= 6)
                    { 
                        newStore = new SixItemList();
                    }
                    else
                    { 
                        newStore = new ArrayItemList(value);
                    } 
 
                    if (null != _listStore)
                    { 
                        // Move entries in the old store to the new one
                        newStore.Promote(_listStore);
                    }
 
                    _listStore = newStore;
                } 
            } 
        }
 
        public int Count
        {
            get
            { 
                if (null != _listStore)
                { 
                    return _listStore.Count; 
                }
                return 0; 
            }
        }

 
        public T this[int index]
        { 
            get 
            {
                // If no entry, default(T) is returned 
                if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0)))
                {
                    return _listStore.EntryAt(index);
                } 
                throw new ArgumentOutOfRangeException("index");
            } 
 
            set
            { 
                // Ensure write success
                if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0)))
                {
                    _listStore.SetAt(index, value); 
                    return;
                } 
                throw new ArgumentOutOfRangeException("index"); 
            }
        } 

        public int Add(T value)
        {
            if (null != _listStore) 
            {
                // This is done because forward branches 
                // default prediction is not to be taken 
                // making this a CPU win because Add is
                // a common operation. 
            }
            else
            {
                _listStore = new SingleItemList(); 
            }
 
            FrugalListStoreState myState = _listStore.Add(value); 
            if (FrugalListStoreState.Success == myState)
            { 
            }
            else
            {
                // Need to move to a more complex storage 
                // Allocate the store, promote, and add using the derived classes
                // to avoid virtual method calls 
 
                if (FrugalListStoreState.ThreeItemList == myState)
                { 
                    ThreeItemList newStore = new ThreeItemList();

                    // Extract the values from the old store and insert them into the new store
                    newStore.Promote(_listStore); 

                    // Insert the new item 
                    newStore.Add(value); 
                    _listStore = newStore;
                } 
                else if (FrugalListStoreState.SixItemList == myState)
                {
                    SixItemList newStore = new SixItemList();
 
                    // Extract the values from the old store and insert them into the new store
                    newStore.Promote(_listStore); 
                    _listStore = newStore; 

                    // Insert the new item 
                    newStore.Add(value);
                    _listStore = newStore;
                }
                else if (FrugalListStoreState.Array == myState) 
                {
                    ArrayItemList newStore = new ArrayItemList(_listStore.Count + 1); 
 
                    // Extract the values from the old store and insert them into the new store
                    newStore.Promote(_listStore); 
                    _listStore = newStore;

                    // Insert the new item
                    newStore.Add(value); 
                    _listStore = newStore;
                } 
                else 
                {
                    throw new InvalidOperationException(SR.Get(SRID.FrugalList_CannotPromoteBeyondArray)); 
                }
            }
            return _listStore.Count - 1;
        } 

        public void Clear() 
        { 
            if (null != _listStore)
            { 
                _listStore.Clear();
            }
        }
 
        public bool Contains(T value)
        { 
            if ((null != _listStore) && (_listStore.Count > 0)) 
            {
                return _listStore.Contains(value); 
            }
            return false;
        }
 
        public int IndexOf(T value)
        { 
            if ((null != _listStore) && (_listStore.Count > 0)) 
            {
                return _listStore.IndexOf(value); 
            }
            return -1;
        }
 
        public void Insert(int index, T value)
        { 
            if ((index == 0) || ((null != _listStore) && ((index <= _listStore.Count) && (index >= 0)))) 
            {
                // Make sure we have a place to put the item 
                int minCapacity = 1;

                if ((null != _listStore) && (_listStore.Count == _listStore.Capacity))
                { 
                    // Store is full
                    minCapacity = Capacity + 1; 
                } 

                // Make the Capacity at *least* this big 
                Capacity = minCapacity;

                _listStore.Insert(index, value);
                return; 
            }
            throw new ArgumentOutOfRangeException("index"); 
        } 

        public bool Remove(T value) 
        {
            if ((null != _listStore) && (_listStore.Count > 0))
            {
                return _listStore.Remove(value); 
            }
            return false; 
        } 

        public void RemoveAt(int index) 
        {
            if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0)))
            {
                _listStore.RemoveAt(index); 
                return;
            } 
            throw new ArgumentOutOfRangeException("index"); 
        }
 
        public void EnsureIndex(int index)
        {
            if (index >= 0)
            { 
                int delta = (index + 1) - Count;
                if (delta > 0) 
                { 
                    // Grow the store
                    Capacity = index + 1; 

                    T filler = default(T);

                    // Insert filler structs or objects 
                    for (int i = 0; i < delta; ++i)
                    { 
                        _listStore.Add(filler); 
                    }
                } 
                return;
            }
            throw new ArgumentOutOfRangeException("index");
        } 

        public T[] ToArray() 
        { 
            if ((null != _listStore) && (_listStore.Count > 0))
            { 
                return _listStore.ToArray();
            }
            return null;
        } 

        public void CopyTo(T[] array, int index) 
        { 
            if ((null != _listStore) && (_listStore.Count > 0))
            { 
                _listStore.CopyTo(array, index);
            }
        }
 
        public FrugalStructList Clone()
        { 
            FrugalStructList myClone = new FrugalStructList(); 

            if (null != _listStore) 
            {
                myClone._listStore = (FrugalListBase)_listStore.Clone();
            }
 
            return myClone;
        } 
 
        internal FrugalListBase _listStore;
    } 
}


// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.
//---------------------------------------------------------------------------- 
//
// Copyright (C) Microsoft Corporation.  All rights reserved.
//
//--------------------------------------------------------------------------- 

using System; 
using System.Diagnostics; 
using System.Collections;
using System.Collections.Generic; 
using System.Windows;
using System.Diagnostics.CodeAnalysis;
using MS.Internal.WindowsBase;
 
//using MS.Internal.PresentationCore;
//using SR=MS.Internal.WindowsBase.SR; 
//using SRID=MS.Internal.WindowsBase.SRID; 

    // These classes implement a frugal storage model for lists of type . 
    // Performance measurements show that Avalon has many lists that contain
    // a limited number of entries, and frequently zero or a single entry.
    // Therefore these classes are structured to prefer a storage model that
    // starts at zero, and employs a conservative growth strategy to minimize 
    // the steady state memory footprint. Also note that the list uses one
    // fewer objects than ArrayList and List and does no allocations at all 
    // until an item is inserted into the list. 
    //
    // The code is also structured to perform well from a CPU standpoint. Perf 
    // analysis shows that the reduced number of processor cache misses makes
    // FrugalList faster than ArrayList or List, especially for lists of 6
    // or fewer items. Timing differ with the size of .
    // 
    // FrugalList is appropriate for small lists or lists that grow slowly.
    // Due to the slow growth, if you use it for a list with more than 6 initial 
    // entires is best to set the capacity of the list at construction time or 
    // soon after. If you must grow the list by a large amount, set the capacity
    // or use Insert() method to force list growth to the final size. Choose 
    // your collections wisely and pay particular attention to the growth
    // patterns and search methods.

    // FrugalList has all of the methods of the Ilist interface, but implements 
    // them as virtual methods of the class and not as Interface methods. This
    // is to avoid the virtual stub dispatch CPU costs associated with Interfaces. 
 
    // We suppress two FxCop warnings in this module because not all usages
    // of FrugalList will instantiate all the storage classes and not all class instances 
    // will use every method.
    // CA1811:AvoidUncalledPrivateCode
    // CA1812:AvoidUninstantiatedInternalClasses
    // 

namespace MS.Utility 
{ 
    // These classes implement a frugal storage model for lists of .
    // Performance measurements show that many lists contain a single item. 
    // Therefore this list is structured to prefer a list that contains a single
    // item, and does conservative growth to minimize the memory footprint.

    // This enum controls the growth to successively more complex storage models 
    internal enum FrugalListStoreState
    { 
        Success, 
        SingleItemList,
        ThreeItemList, 
        SixItemList,
        Array
    }
 
    abstract class FrugalListBase
    { 
        ///  
        /// Number of entries in this store
        ///  
        // Number of entries in this store
        public int Count
        {
            get 
            {
                return _count; 
            } 
        }
 
        /// 
        /// Capacity of this store
        /// 
        public abstract int Capacity 
        {
            get; 
        } 

        // Increase size if needed, insert item into the store 
        public abstract FrugalListStoreState Add(T value);

        /// 
        /// Removes all values from the store 
        /// 
        public abstract void Clear(); 
 
        /// 
        /// Returns true if the store contains the entry. 
        /// 
        public abstract bool Contains(T value);

        ///  
        /// Returns the index into the store that contains the item.
        /// -1 is returned if the item is not in the store. 
        ///  
        public abstract int IndexOf(T value);
 
        /// 
        /// Insert item into the store at index, grows if needed
        /// 
        public abstract void Insert(int index, T value); 

        // Place item into the store at index 
        public abstract void SetAt(int index, T value); 

        ///  
        /// Removes the item from the store. If the item was not
        /// in the store false is returned.
        /// 
        public abstract bool Remove(T value); 

        ///  
        /// Removes the item from the store 
        /// 
        public abstract void RemoveAt(int index); 

        /// 
        /// Return the item at index in the store
        ///  
        public abstract T EntryAt(int index);
 
        ///  
        /// Promotes the values in the current store to the next larger
        /// and more complex storage model. 
        /// 
        public abstract void Promote(FrugalListBase newList);

        ///  
        /// Returns the entries as an array
        ///  
        public abstract T[] ToArray(); 

        ///  
        /// Copies the entries to the given array starting at the
        /// specified index
        /// 
        public abstract void CopyTo(T[] array, int index); 

        ///  
        /// Creates a shallow copy of the  list 
        /// 
        public abstract object Clone(); 

        // The number of items in the list.
        protected int _count;
    } 

    ///  
    /// A simple class to handle a single item 
    /// 
    internal sealed class SingleItemList : FrugalListBase 
    {
        // Capacity of this store
        public override int Capacity
        { 
            get
            { 
                return SIZE; 
            }
        } 

        public override FrugalListStoreState Add(T value)
        {
            // If we don't have any entries or the existing entry is being overwritten, 
            // then we can use this store. Otherwise we have to promote.
            if (0 == _count) 
            { 
                _loneEntry = value;
                ++_count; 
                return FrugalListStoreState.Success;
            }
            else
            { 
                // Entry already used, move to an ThreeItemList
                return FrugalListStoreState.ThreeItemList; 
            } 
        }
 
        public override void Clear()
        {
            // Wipe out the info
            _loneEntry = default(T); 
            _count = 0;
        } 
 
        public override bool Contains(T value)
        { 
            return _loneEntry.Equals(value);
        }

        public override int IndexOf(T value) 
        {
            if (_loneEntry.Equals(value)) 
            { 
                return 0;
            } 
            return -1;
        }

        public override void Insert(int index, T value) 
        {
            // Should only get here if count and index are 0 
            if ((_count < SIZE) && (index < SIZE)) 
            {
                _loneEntry = value; 
                ++_count;
                return;
            }
            throw new ArgumentOutOfRangeException("index"); 
        }
 
        public override void SetAt(int index, T value) 
        {
            // Overwrite item at index 
            _loneEntry = value;
        }

        public override bool Remove(T value) 
        {
            // Wipe out the info in the only entry if it matches the item. 
            if (_loneEntry.Equals(value)) 
            {
                _loneEntry = default(T); 
                --_count;
                return true;
            }
 
            return false;
        } 
 
        public override void RemoveAt(int index)
        { 
            // Wipe out the info at index
            if (0 == index)
            {
                _loneEntry = default(T); 
                --_count;
            } 
            else 
            {
                throw new ArgumentOutOfRangeException("index"); 
            }
        }

        public override T EntryAt(int index) 
        {
            return _loneEntry; 
        } 

        public override void Promote(FrugalListBase oldList) 
        {
            if (SIZE == oldList.Count)
            {
                SetCount(SIZE); 
                SetAt(0, oldList.EntryAt(0));
            } 
            else 
            {
                // this list is smaller than oldList 
                throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList");
            }
        }
 
        // Class specific implementation to avoid virtual method calls and additional logic
        public void Promote(SingleItemList oldList) 
        { 
            SetCount(oldList.Count);
            SetAt(0, oldList.EntryAt(0)); 
        }

        public override T[] ToArray()
        { 
            T[] array = new T[1];
            array[0] = _loneEntry; 
            return array; 
        }
 
        public override void CopyTo(T[] array, int index)
        {
            array[index] = _loneEntry;
        } 

        public override object Clone() 
        { 
            SingleItemList newList = new SingleItemList();
            newList.Promote(this); 
            return newList;
        }

        private void SetCount(int value) 
        {
            if ((value >= 0) && (value <= SIZE)) 
            { 
                _count = value;
            } 
            else
            {
                throw new ArgumentOutOfRangeException("Count");
            } 
        }
 
        private const int SIZE = 1; 

        private T _loneEntry; 
    }


    ///  
    /// A simple class to handle a list with 3 items.  Perf analysis showed
    /// that this yielded better memory locality and perf than an object and an array. 
    ///  
    internal sealed class ThreeItemList : FrugalListBase
    { 
        // Capacity of this store
        public override int Capacity
        {
            get 
            {
                return SIZE; 
            } 
        }
 
        public override FrugalListStoreState Add(T value)
        {
            switch (_count)
            { 
                case 0:
                    _entry0 = value; 
                    break; 

                case 1: 
                    _entry1 = value;
                    break;

                case 2: 
                    _entry2 = value;
                    break; 
 
                default:
                    // We have to promote 
                    return FrugalListStoreState.SixItemList;
            }
            ++_count;
            return FrugalListStoreState.Success; 
        }
 
        public override void Clear() 
        {
            // Wipe out the info. 
            _entry0 = default(T);
            _entry1 = default(T);
            _entry2 = default(T);
            _count = 0; 
        }
 
        public override bool Contains(T value) 
        {
            return (-1 != IndexOf(value)); 
        }

        public override int IndexOf(T value)
        { 
            if (_entry0.Equals(value))
            { 
                return 0; 
            }
            if (_count > 1) 
            {
                if (_entry1.Equals(value))
                {
                    return 1; 
                }
                if ((3 == _count) && (_entry2.Equals(value))) 
                { 
                    return 2;
                } 
            }
            return -1;
        }
 
        public override void Insert(int index, T value)
        { 
            // Should only get here if count < SIZE 
            if (_count < SIZE)
            { 
                switch (index)
                {
                    case 0:
                        _entry2 = _entry1; 
                        _entry1 = _entry0;
                        _entry0 = value; 
                        break; 

                    case 1: 
                        _entry2 = _entry1;
                        _entry1 = value;
                        break;
 
                    case 2:
                        _entry2 = value; 
                        break; 

                    default: 
                        throw new ArgumentOutOfRangeException("index");
                }
                ++_count;
                return; 
            }
            throw new ArgumentOutOfRangeException("index"); 
        } 

        public override void SetAt(int index, T value) 
        {
            // Overwrite item at index
            switch (index)
            { 
                case 0:
                    _entry0 = value; 
                    break; 

                case 1: 
                    _entry1 = value;
                    break;

                case 2: 
                    _entry2 = value;
                    break; 
 
                default:
                    throw new ArgumentOutOfRangeException("index"); 
            }
        }

        public override bool Remove(T value) 
        {
            // If the item 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.
            if (_entry0.Equals(value)) 
            {
                RemoveAt(0);
                return true;
            } 
            else if ( _count > 1)
            { 
                if (_entry1.Equals(value)) 
                {
                    RemoveAt(1); 
                    return true;
                }
                else if ((3 == _count) && (_entry2.Equals(value)))
                { 
                    RemoveAt(2);
                    return true; 
                } 
            }
            return false; 
        }

        public override void RemoveAt(int index)
        { 
            // Remove entry at index, 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 (index)
            { 
                case 0:
                    _entry0 = _entry1;
                    _entry1 = _entry2;
                    break; 

                case 1: 
                    _entry1 = _entry2; 
                    break;
 
                case 2:
                    break;

                default: 
                    throw new ArgumentOutOfRangeException("index");
            } 
            _entry2 = default(T); 
            --_count;
        } 

        public override T EntryAt(int index)
        {
            switch (index) 
            {
                case 0: 
                    return _entry0; 

                case 1: 
                    return _entry1;

                case 2:
                    return _entry2; 

                default: 
                    throw new ArgumentOutOfRangeException("index"); 
            }
        } 

        public override void Promote(FrugalListBase oldList)
        {
            int oldCount = oldList.Count; 
            if (SIZE >= oldCount)
            { 
                SetCount(oldList.Count); 

                switch (oldCount) 
                {
                    case 3:
                        SetAt(0, oldList.EntryAt(0));
                        SetAt(1, oldList.EntryAt(1)); 
                        SetAt(2, oldList.EntryAt(2));
                        break; 
 
                    case 2:
                        SetAt(0, oldList.EntryAt(0)); 
                        SetAt(1, oldList.EntryAt(1));
                        break;

                    case 1: 
                        SetAt(0, oldList.EntryAt(0));
                        break; 
 
                    case 0:
                        break; 

                    default:
                        throw new ArgumentOutOfRangeException("index");
                } 
            }
            else 
            { 
                // this list is smaller than oldList
                throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); 
            }
        }

        // Class specific implementation to avoid virtual method calls and additional logic 
        public void Promote(SingleItemList oldList)
        { 
            SetCount(oldList.Count); 
            SetAt(0, oldList.EntryAt(0));
        } 

        // Class specific implementation to avoid virtual method calls and additional logic
        public void Promote(ThreeItemList oldList)
        { 
            int oldCount = oldList.Count;
            SetCount(oldList.Count); 
 
            switch (oldCount)
            { 
                case 3:
                    SetAt(0, oldList.EntryAt(0));
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    break;
 
                case 2: 
                    SetAt(0, oldList.EntryAt(0));
                    SetAt(1, oldList.EntryAt(1)); 
                    break;

                case 1:
                    SetAt(0, oldList.EntryAt(0)); 
                    break;
 
                case 0: 
                    break;
 
                default:
                    throw new ArgumentOutOfRangeException("index");
            }
        } 

        public override T[] ToArray() 
        { 
            T[] array = new T[_count];
 
            array[0] = _entry0;
            if (_count >= 2)
            {
                array[1] = _entry1; 
                if (_count == 3)
                { 
                    array[2] = _entry2; 
                }
            } 
            return array;
        }

        public override void CopyTo(T[] array, int index) 
        {
            array[index] = _entry0; 
            if (_count >= 2) 
            {
                array[index+1] = _entry1; 
                if (_count == 3)
                {
                    array[index+2] = _entry2;
                } 
            }
        } 
 
        public override object Clone()
        { 
            ThreeItemList newList = new ThreeItemList();
            newList.Promote(this);
            return newList;
        } 

        private void SetCount(int value) 
        { 
            if ((value >= 0) && (value <= SIZE))
            { 
                _count = value;
            }
            else
            { 
                throw new ArgumentOutOfRangeException("Count");
            } 
        } 

        private const int SIZE = 3; 

        private T _entry0;
        private T _entry1;
        private T _entry2; 
    }
 
    ///  
    /// A simple class to handle a list with 6 items.
    ///  
    internal sealed class SixItemList : FrugalListBase
    {
        // Capacity of this store
        public override int Capacity 
        {
            get 
            { 
                return SIZE;
            } 
        }

        public override FrugalListStoreState Add(T value)
        { 
            switch (_count)
            { 
                case 0: 
                    _entry0 = value;
                    break; 

                case 1:
                    _entry1 = value;
                    break; 

                case 2: 
                    _entry2 = value; 
                    break;
 
                case 3:
                    _entry3 = value;
                    break;
 
                case 4:
                    _entry4 = value; 
                    break; 

                case 5: 
                    _entry5 = value;
                    break;

                default: 
                    // We have to promote
                    return FrugalListStoreState.Array; 
            } 
            ++_count;
            return FrugalListStoreState.Success; 
        }

        public override void Clear()
        { 
            // Wipe out the info.
            _entry0 = default(T); 
            _entry1 = default(T); 
            _entry2 = default(T);
            _entry3 = default(T); 
            _entry4 = default(T);
            _entry5 = default(T);
            _count = 0;
        } 

        public override bool Contains(T value) 
        { 
            return (-1 != IndexOf(value));
        } 

        public override int IndexOf(T value)
        {
            if (_entry0.Equals(value)) 
            {
                return 0; 
            } 
            if (_count > 1)
            { 
                if (_entry1.Equals(value))
                {
                    return 1;
                } 
                if (_count > 2)
                { 
                    if (_entry2.Equals(value)) 
                    {
                        return 2; 
                    }
                    if (_count > 3)
                    {
                        if (_entry3.Equals(value)) 
                        {
                            return 3; 
                        } 
                        if (_count > 4)
                        { 
                            if (_entry4.Equals(value))
                            {
                                return 4;
                            } 
                            if ((6 == _count) && (_entry5.Equals(value)))
                            { 
                                return 5; 
                            }
                        } 
                    }
                }
            }
            return -1; 
        }
 
        public override void Insert(int index, T value) 
        {
            // Should only get here if count is less than SIZE 
            if (_count < SIZE)
            {
                switch (index)
                { 
                    case 0:
                        _entry5 = _entry4; 
                        _entry4 = _entry3; 
                        _entry3 = _entry2;
                        _entry2 = _entry1; 
                        _entry1 = _entry0;
                        _entry0 = value;
                        break;
 
                    case 1:
                        _entry5 = _entry4; 
                        _entry4 = _entry3; 
                        _entry3 = _entry2;
                        _entry2 = _entry1; 
                        _entry1 = value;
                        break;

                    case 2: 
                        _entry5 = _entry4;
                        _entry4 = _entry3; 
                        _entry3 = _entry2; 
                        _entry2 = value;
                        break; 

                    case 3:
                        _entry5 = _entry4;
                        _entry4 = _entry3; 
                        _entry3 = value;
                        break; 
 
                    case 4:
                        _entry5 = _entry4; 
                        _entry4 = value;
                        break;

                    case 5: 
                        _entry5 = value;
                        break; 
 
                    default:
                        throw new ArgumentOutOfRangeException("index"); 
                }
                ++_count;
                return;
            } 
            throw new ArgumentOutOfRangeException("index");
        } 
 
        public override void SetAt(int index, T value)
        { 
            // Overwrite item at index
            switch (index)
            {
                case 0: 
                    _entry0 = value;
                    break; 
 
                case 1:
                    _entry1 = value; 
                    break;

                case 2:
                    _entry2 = value; 
                    break;
 
                case 3: 
                    _entry3 = value;
                    break; 

                case 4:
                    _entry4 = value;
                    break; 

                case 5: 
                    _entry5 = value; 
                    break;
 
                default:
                    throw new ArgumentOutOfRangeException("index");
            }
        } 

        public override bool Remove(T value) 
        { 
            // If the item matches an existing entry, wipe out the last
            // entry and move all the other entries up.  Because we only 
            // have six entries we can just unravel all the cases.
            if (_entry0.Equals(value))
            {
                RemoveAt(0); 
                return true;
            } 
            else if (_count > 1) 
            {
                if (_entry1.Equals(value)) 
                {
                    RemoveAt(1);
                    return true;
                } 
                else if (_count > 2)
                { 
                    if (_entry2.Equals(value)) 
                    {
                        RemoveAt(2); 
                        return true;
                    }
                    else if (_count > 3)
                    { 
                        if (_entry3.Equals(value))
                        { 
                            RemoveAt(3); 
                            return true;
                        } 
                        else if (_count > 4)
                        {
                            if (_entry4.Equals(value))
                            { 
                                RemoveAt(4);
                                return true; 
                            } 
                            else if ((6 == _count) && (_entry5.Equals(value)))
                            { 
                                RemoveAt(5);
                                return true;
                            }
                        } 
                    }
                } 
            } 

            return false; 
        }

        public override void RemoveAt(int index)
        { 
            // Remove entry at index, wipe out the last entry and move
            // all the other entries up. Because we only have six 
            // entries we can just unravel all the cases. 
            switch (index)
            { 
                case 0:
                    _entry0 = _entry1;
                    _entry1 = _entry2;
                    _entry2 = _entry3; 
                    _entry3 = _entry4;
                    _entry4 = _entry5; 
                    break; 

                case 1: 
                    _entry1 = _entry2;
                    _entry2 = _entry3;
                    _entry3 = _entry4;
                    _entry4 = _entry5; 
                    break;
 
                case 2: 
                    _entry2 = _entry3;
                    _entry3 = _entry4; 
                    _entry4 = _entry5;
                    break;

                case 3: 
                    _entry3 = _entry4;
                    _entry4 = _entry5; 
                    break; 

                case 4: 
                    _entry4 = _entry5;
                    break;

                case 5: 
                    break;
 
                default: 
                    throw new ArgumentOutOfRangeException("index");
            } 
            _entry5 = default(T);
            --_count;
        }
 
        public override T EntryAt(int index)
        { 
            switch (index) 
            {
                case 0: 
                    return _entry0;

                case 1:
                    return _entry1; 

                case 2: 
                    return _entry2; 

                case 3: 
                    return _entry3;

                case 4:
                    return _entry4; 

                case 5: 
                    return _entry5; 

                default: 
                    throw new ArgumentOutOfRangeException("index");
            }
        }
 
        public override void Promote(FrugalListBase oldList)
        { 
            int oldCount = oldList.Count; 
            if (SIZE >= oldCount)
            { 
                SetCount(oldList.Count);

                switch (oldCount)
                { 
                    case 6:
                        SetAt(0, oldList.EntryAt(0)); 
                        SetAt(1, oldList.EntryAt(1)); 
                        SetAt(2, oldList.EntryAt(2));
                        SetAt(3, oldList.EntryAt(3)); 
                        SetAt(4, oldList.EntryAt(4));
                        SetAt(5, oldList.EntryAt(5));
                        break;
 
                    case 5:
                        SetAt(0, oldList.EntryAt(0)); 
                        SetAt(1, oldList.EntryAt(1)); 
                        SetAt(2, oldList.EntryAt(2));
                        SetAt(3, oldList.EntryAt(3)); 
                        SetAt(4, oldList.EntryAt(4));
                        break;

                    case 4: 
                        SetAt(0, oldList.EntryAt(0));
                        SetAt(1, oldList.EntryAt(1)); 
                        SetAt(2, oldList.EntryAt(2)); 
                        SetAt(3, oldList.EntryAt(3));
                        break; 

                    case 3:
                        SetAt(0, oldList.EntryAt(0));
                        SetAt(1, oldList.EntryAt(1)); 
                        SetAt(2, oldList.EntryAt(2));
                        break; 
 
                    case 2:
                        SetAt(0, oldList.EntryAt(0)); 
                        SetAt(1, oldList.EntryAt(1));
                        break;

                    case 1: 
                        SetAt(0, oldList.EntryAt(0));
                        break; 
 
                    case 0:
                        break; 

                    default:
                        throw new ArgumentOutOfRangeException("index");
                } 
            }
            else 
            { 
                // this list is smaller than oldList
                throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); 
            }
        }

        // Class specific implementation to avoid virtual method calls and additional logic 
        public void Promote(ThreeItemList oldList)
        { 
            int oldCount = oldList.Count; 
            if (SIZE <= oldCount)
            { 
                SetCount(oldList.Count);

                switch (oldCount)
                { 
                    case 3:
                        SetAt(0, oldList.EntryAt(0)); 
                        SetAt(1, oldList.EntryAt(1)); 
                        SetAt(2, oldList.EntryAt(2));
                        break; 

                    case 2:
                        SetAt(0, oldList.EntryAt(0));
                        SetAt(1, oldList.EntryAt(1)); 
                        break;
 
                    case 1: 
                        SetAt(0, oldList.EntryAt(0));
                        break; 

                    case 0:
                        break;
 
                    default:
                        throw new ArgumentOutOfRangeException("index"); 
                } 
            }
            else 
            {
                // this list is smaller than oldList
                throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList");
            } 
        }
 
        // Class specific implementation to avoid virtual method calls and additional logic 
        public void Promote(SixItemList oldList)
        { 
            int oldCount = oldList.Count;
            SetCount(oldList.Count);

            switch (oldCount) 
            {
                case 6: 
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    SetAt(3, oldList.EntryAt(3));
                    SetAt(4, oldList.EntryAt(4));
                    SetAt(5, oldList.EntryAt(5));
                    break; 

                case 5: 
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    SetAt(3, oldList.EntryAt(3));
                    SetAt(4, oldList.EntryAt(4));
                    break;
 
                case 4:
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1)); 
                    SetAt(2, oldList.EntryAt(2));
                    SetAt(3, oldList.EntryAt(3)); 
                    break;

                case 3:
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    break; 

                case 2: 
                    SetAt(0, oldList.EntryAt(0));
                    SetAt(1, oldList.EntryAt(1));
                    break;
 
                case 1:
                    SetAt(0, oldList.EntryAt(0)); 
                    break; 

                case 0: 
                    break;

                default:
                    throw new ArgumentOutOfRangeException("index"); 
            }
        } 
 
        public override T[] ToArray()
        { 
            T[] array = new T[_count];

            if (_count >= 1)
            { 
                array[0] = _entry0;
                if (_count >= 2) 
                { 
                    array[1] = _entry1;
                    if (_count >= 3) 
                    {
                        array[2] = _entry2;
                        if (_count >= 4)
                        { 
                            array[3] = _entry3;
                            if (_count >= 5) 
                            { 
                                array[4] = _entry4;
                                if (_count == 6) 
                                {
                                    array[5] = _entry5;
                                }
                            } 
                        }
                    } 
                } 
            }
            return array; 
        }

        public override void CopyTo(T[] array, int index)
        { 
            if (_count >= 1)
            { 
                array[index] = _entry0; 
                if (_count >= 2)
                { 
                    array[index+1] = _entry1;
                    if (_count >= 3)
                    {
                        array[index+2] = _entry2; 
                        if (_count >= 4)
                        { 
                            array[index+3] = _entry3; 
                            if (_count >= 5)
                            { 
                                array[index+4] = _entry4;
                                if (_count == 6)
                                {
                                    array[index+5] = _entry5; 
                                }
                            } 
                        } 
                    }
                } 
            }
        }

        public override object Clone() 
        {
            SixItemList newList = new SixItemList(); 
            newList.Promote(this); 
            return newList;
        } 

        private void SetCount(int value)
        {
            if ((value >= 0) && (value <= SIZE)) 
            {
                _count = value; 
            } 
            else
            { 
                throw new ArgumentOutOfRangeException("Count");
            }
        }
 
        private const int SIZE = 6;
 
        private T _entry0; 
        private T _entry1;
        private T _entry2; 
        private T _entry3;
        private T _entry4;
        private T _entry5;
    } 

    ///  
    /// A simple class to handle an array of 7 or more items.  It is unsorted and uses 
    /// a linear search.
    ///  
    internal sealed class ArrayItemList : FrugalListBase
    {
        public ArrayItemList()
        { 
        }
 
        public ArrayItemList(int size) 
        {
            // Make size a multiple of GROWTH 
            size += (GROWTH - 1);
            size -= (size % GROWTH);
            _entries = new T[size];
        } 

        public ArrayItemList(ICollection collection) 
        { 
            if (collection != null)
            { 
                _count = collection.Count;
                _entries = new T[_count];
                collection.CopyTo(_entries, 0);
            } 
        }
 
        public ArrayItemList(ICollection collection) 
        {
            if (collection != null) 
            {
                _count = collection.Count;
                _entries = new T[_count];
                collection.CopyTo(_entries, 0); 
            }
        } 
 
        // Capacity of this store
        public override int Capacity 
        {
            get
            {
                if (_entries != null) 
                {
                    return _entries.Length; 
                } 
                return 0;
            } 
        }

        public override FrugalListStoreState Add(T value)
        { 
            // If we don't have any entries or the existing entry is being overwritten,
            // then we can use this store. Otherwise we have to promote. 
            if ((null != _entries) && (_count < _entries.Length)) 
            {
                _entries[_count] = value; 
                ++_count;
            }
            else
            { 
                if (null != _entries)
                { 
                    int size = _entries.Length; 

                    // Grow the list slowly while it is small but 
                    // faster once it reaches the LARGEGROWTH size
                    if (size < LARGEGROWTH)
                    {
                        size += GROWTH; 
                    }
                    else 
                    { 
                        size += size >> 2;
                    } 

                    T[] destEntries = new T[size];

                    // Copy old array 
                    Array.Copy(_entries, 0, destEntries, 0, _entries.Length);
                    _entries = destEntries; 
                } 
                else
                { 
                    _entries = new T[MINSIZE];
                }

                // Insert into new array 
                _entries[_count] = value;
                ++_count; 
            } 
            return FrugalListStoreState.Success;
        } 

        public override void Clear()
        {
            // Wipe out the info. 
            for (int i = 0; i < _count; ++i)
            { 
                _entries[i] = default(T); 
            }
            _count = 0; 
        }

        public override bool Contains(T value)
        { 
            return (-1 != IndexOf(value));
        } 
 
        public override int IndexOf(T value)
        { 
            for (int index = 0; index < _count; ++index)
            {
                if (_entries[index].Equals(value))
                { 
                    return index;
                } 
            } 
            return -1;
        } 

        public override void Insert(int index, T value)
        {
            if ((null != _entries) && (_count < _entries.Length)) 
            {
                // Move down the required number of items 
                Array.Copy(_entries, index, _entries, index + 1, _count - index); 

                // Put in the new item at the specified index 
                _entries[index] = value;
                ++_count;
                return;
            } 
            throw new ArgumentOutOfRangeException("index");
        } 
 
        public override void SetAt(int index, T value)
        { 
            // Overwrite item at index
            _entries[index] = value;
        }
 
        public override bool Remove(T value)
        { 
            for (int index = 0; index < _count; ++index) 
            {
                if (_entries[index].Equals(value)) 
                {
                    RemoveAt(index);
                    return true;
                } 
            }
 
            return false; 
        }
 
        public override void RemoveAt(int index)
        {
            // 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] = default(T);
            --_count;
            return; 
        }
 
        public override T EntryAt(int index) 
        {
            return _entries[index]; 
        }

        public override void Promote(FrugalListBase oldList)
        { 
            for (int index = 0; index < oldList.Count; ++index)
            { 
                if (FrugalListStoreState.Success == Add(oldList.EntryAt(index))) 
                {
                    continue; 
                }
                // this list is smaller than oldList
                throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList");
            } 
        }
 
        // Class specific implementation to avoid virtual method calls and additional logic 
        public void Promote(SixItemList oldList)
        { 
            int oldCount = oldList.Count;
            SetCount(oldList.Count);

            switch (oldCount) 
            {
                case 6: 
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    SetAt(3, oldList.EntryAt(3));
                    SetAt(4, oldList.EntryAt(4));
                    SetAt(5, oldList.EntryAt(5));
                    break; 

                case 5: 
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    SetAt(3, oldList.EntryAt(3));
                    SetAt(4, oldList.EntryAt(4));
                    break;
 
                case 4:
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1)); 
                    SetAt(2, oldList.EntryAt(2));
                    SetAt(3, oldList.EntryAt(3)); 
                    break;

                case 3:
                    SetAt(0, oldList.EntryAt(0)); 
                    SetAt(1, oldList.EntryAt(1));
                    SetAt(2, oldList.EntryAt(2)); 
                    break; 

                case 2: 
                    SetAt(0, oldList.EntryAt(0));
                    SetAt(1, oldList.EntryAt(1));
                    break;
 
                case 1:
                    SetAt(0, oldList.EntryAt(0)); 
                    break; 

                case 0: 
                    break;

                default:
                    throw new ArgumentOutOfRangeException("index"); 
            }
        } 
 
        // Class specific implementation to avoid virtual method calls and additional logic
        public void Promote(ArrayItemList oldList) 
        {
            int oldCount = oldList.Count;
            if (_entries.Length >= oldCount)
            { 
                SetCount(oldList.Count);
 
                for (int index = 0; index < oldCount; ++index) 
                {
                    SetAt(index, oldList.EntryAt(index)); 
                }
            }
            else
            { 
                // this list is smaller than oldList
                throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); 
            } 
        }
 
        public override T[] ToArray()
        {
            T[] array = new T[_count];
 
            for (int i = 0; i < _count; ++i)
            { 
                array[i] = _entries[i]; 
            }
            return array; 
        }

        public override void CopyTo(T[] array, int index)
        { 
            for (int i = 0; i < _count; ++i)
            { 
                array[index+i] = _entries[i]; 
            }
        } 

        public override object Clone()
        {
            ArrayItemList newList = new ArrayItemList(this.Capacity); 
            newList.Promote(this);
            return newList; 
        } 

        private void SetCount(int value) 
        {
            if ((value >= 0) && (value <= _entries.Length))
            {
                _count = value; 
            }
            else 
            { 
                throw new ArgumentOutOfRangeException("Count");
            } 
        }

        // MINSIZE and GROWTH chosen to minimize memory footprint
        private const int MINSIZE = 9; 
        private const int GROWTH = 3;
        private const int LARGEGROWTH = 18; 
 
        private T[] _entries;
    } 

    // Use FrugalObjectList when more than one reference to the list is needed.
    // The "object" in FrugalObjectLIst refers to the list itself, not what the list contains.
 
    [FriendAccessAllowed] // Built into Core, also used by Framework.
    internal class FrugalObjectList 
    { 
        public FrugalObjectList()
        { 
        }

        public FrugalObjectList(int size)
        { 
            Capacity = size;
        } 
 
        public int Capacity
        { 
            get
            {
                if (null != _listStore)
                { 
                    return _listStore.Capacity;
                } 
                return 0; 
            }
            set 
            {
                int capacity = 0;
                if (null != _listStore)
                { 
                    capacity = _listStore.Capacity;
                } 
                if (capacity < value) 
                {
                    // Need to move to a more complex storage 
                    FrugalListBase newStore;

                    if (value == 1)
                    { 
                        newStore = new SingleItemList();
                    } 
                    else if (value <= 3) 
                    {
                        newStore = new ThreeItemList(); 
                    }
                    else if (value <= 6)
                    {
                        newStore = new SixItemList(); 
                    }
                    else 
                    { 
                        newStore = new ArrayItemList(value);
                    } 

                    if (null != _listStore)
                    {
                        // Move entries in the old store to the new one 
                        newStore.Promote(_listStore);
                    } 
 
                    _listStore = newStore;
                } 
            }
        }

        public int Count 
        {
            get 
            { 
                if (null != _listStore)
                { 
                    return _listStore.Count;
                }
                return 0;
            } 
        }
 
 
        public T this[int index]
        { 
            get
            {
                // If no entry, default(T) is returned
                if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) 
                {
                    return _listStore.EntryAt(index); 
                } 
                throw new ArgumentOutOfRangeException("index");
            } 

            set
            {
                // Ensure write success 
                if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0)))
                { 
                    _listStore.SetAt(index, value); 
                    return;
                } 
                throw new ArgumentOutOfRangeException("index");
            }
        }
 
        public int Add(T value)
        { 
            if (null != _listStore) 
            {
                // This is done because forward branches 
                // default prediction is not to be taken
                // making this a CPU win because Add is
                // a common operation.
            } 
            else
            { 
                _listStore = new SingleItemList(); 
            }
 
            FrugalListStoreState myState = _listStore.Add(value);
            if (FrugalListStoreState.Success == myState)
            {
            } 
            else
            { 
                // Need to move to a more complex storage 
                // Allocate the store, promote, and add using the derived classes
                // to avoid virtual method calls 

                if (FrugalListStoreState.ThreeItemList == myState)
                {
                    ThreeItemList newStore = new ThreeItemList(); 

                    // Extract the values from the old store and insert them into the new store 
                    newStore.Promote(_listStore); 

                    // Insert the new item 
                    newStore.Add(value);
                    _listStore = newStore;
                }
                else if (FrugalListStoreState.SixItemList == myState) 
                {
                    SixItemList newStore = new SixItemList(); 
 
                    // Extract the values from the old store and insert them into the new store
                    newStore.Promote(_listStore); 
                    _listStore = newStore;

                    // Insert the new item
                    newStore.Add(value); 
                    _listStore = newStore;
                } 
                else if (FrugalListStoreState.Array == myState) 
                {
                    ArrayItemList newStore = new ArrayItemList(_listStore.Count + 1); 

                    // Extract the values from the old store and insert them into the new store
                    newStore.Promote(_listStore);
                    _listStore = newStore; 

                    // Insert the new item 
                    newStore.Add(value); 
                    _listStore = newStore;
                } 
                else
                {
                    throw new InvalidOperationException(SR.Get(SRID.FrugalList_CannotPromoteBeyondArray));
                } 
            }
            return _listStore.Count - 1; 
        } 

        public void Clear() 
        {
            if (null != _listStore)
            {
                _listStore.Clear(); 
            }
        } 
 
        public bool Contains(T value)
        { 
            if ((null != _listStore) && (_listStore.Count > 0))
            {
                return _listStore.Contains(value);
            } 
            return false;
        } 
 
        public int IndexOf(T value)
        { 
            if ((null != _listStore) && (_listStore.Count > 0))
            {
                return _listStore.IndexOf(value);
            } 
            return -1;
        } 
 
        public void Insert(int index, T value)
        { 
            if ((index == 0) || ((null != _listStore) && ((index <= _listStore.Count) && (index >= 0))))
            {
                // Make sure we have a place to put the item
                int minCapacity = 1; 

                if ((null != _listStore) && (_listStore.Count == _listStore.Capacity)) 
                { 
                    // Store is full
                    minCapacity = Capacity + 1; 
                }

                // Make the Capacity at *least* this big
                Capacity = minCapacity; 

                _listStore.Insert(index, value); 
                return; 
            }
            throw new ArgumentOutOfRangeException("index"); 
        }

        public bool Remove(T value)
        { 
            if ((null != _listStore) && (_listStore.Count > 0))
            { 
                return _listStore.Remove(value); 
            }
            return false; 
        }

        public void RemoveAt(int index)
        { 
            if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0)))
            { 
                _listStore.RemoveAt(index); 
                return;
            } 
            throw new ArgumentOutOfRangeException("index");
        }

        public void EnsureIndex(int index) 
        {
            if (index >= 0) 
            { 
                int delta = (index + 1) - Count;
                if (delta > 0) 
                {
                    // Grow the store
                    Capacity = index + 1;
 
                    T filler = default(T);
 
                    // Insert filler structs or objects 
                    for (int i = 0; i < delta; ++i)
                    { 
                        _listStore.Add(filler);
                    }
                }
                return; 
            }
            throw new ArgumentOutOfRangeException("index"); 
        } 

        public T[] ToArray() 
        {
            if ((null != _listStore) && (_listStore.Count > 0))
            {
                return _listStore.ToArray(); 
            }
            return null; 
        } 

        public void CopyTo(T[] array, int index) 
        {
            if ((null != _listStore) && (_listStore.Count > 0))
            {
                _listStore.CopyTo(array, index); 
            }
        } 
 
        public FrugalObjectList Clone()
        { 
            FrugalObjectList myClone = new FrugalObjectList();

            if (null != _listStore)
            { 
                myClone._listStore = (FrugalListBase)_listStore.Clone();
            } 
 
            return myClone;
        } 

        internal FrugalListBase _listStore;
    }
 
    // Use FrugalStructList when only one reference to the list is needed.
    // The "struct" in FrugalStructList refers to the list itself, not what the list contains. 
    [FriendAccessAllowed] // Built into Core, also used by Framework. 
    internal struct FrugalStructList
    { 
        public FrugalStructList(int size)
        {
            _listStore = null;
            Capacity = size; 
        }
 
        public FrugalStructList(ICollection collection) 
        {
            if (collection.Count > 6) 
            {
                _listStore = new ArrayItemList(collection);
            }
            else 
            {
                _listStore = null; 
                Capacity = collection.Count; 
                foreach (T item in collection)
                { 
                    Add(item);
                }
            }
        } 

        public FrugalStructList(ICollection collection) 
        { 
            if (collection.Count > 6)
            { 
                _listStore = new ArrayItemList(collection);
            }
            else
            { 
                _listStore = null;
                Capacity = collection.Count; 
                foreach (T item in collection) 
                {
                    Add(item); 
                }
            }
        }
 
        public int Capacity
        { 
            get 
            {
                if (null != _listStore) 
                {
                    return _listStore.Capacity;
                }
                return 0; 
            }
            set 
            { 
                int capacity = 0;
                if (null != _listStore) 
                {
                    capacity = _listStore.Capacity;
                }
                if (capacity < value) 
                {
                    // Need to move to a more complex storage 
                    FrugalListBase newStore; 

                    if (value == 1) 
                    {
                        newStore = new SingleItemList();
                    }
                    else if (value <= 3) 
                    {
                        newStore = new ThreeItemList(); 
                    } 
                    else if (value <= 6)
                    { 
                        newStore = new SixItemList();
                    }
                    else
                    { 
                        newStore = new ArrayItemList(value);
                    } 
 
                    if (null != _listStore)
                    { 
                        // Move entries in the old store to the new one
                        newStore.Promote(_listStore);
                    }
 
                    _listStore = newStore;
                } 
            } 
        }
 
        public int Count
        {
            get
            { 
                if (null != _listStore)
                { 
                    return _listStore.Count; 
                }
                return 0; 
            }
        }

 
        public T this[int index]
        { 
            get 
            {
                // If no entry, default(T) is returned 
                if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0)))
                {
                    return _listStore.EntryAt(index);
                } 
                throw new ArgumentOutOfRangeException("index");
            } 
 
            set
            { 
                // Ensure write success
                if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0)))
                {
                    _listStore.SetAt(index, value); 
                    return;
                } 
                throw new ArgumentOutOfRangeException("index"); 
            }
        } 

        public int Add(T value)
        {
            if (null != _listStore) 
            {
                // This is done because forward branches 
                // default prediction is not to be taken 
                // making this a CPU win because Add is
                // a common operation. 
            }
            else
            {
                _listStore = new SingleItemList(); 
            }
 
            FrugalListStoreState myState = _listStore.Add(value); 
            if (FrugalListStoreState.Success == myState)
            { 
            }
            else
            {
                // Need to move to a more complex storage 
                // Allocate the store, promote, and add using the derived classes
                // to avoid virtual method calls 
 
                if (FrugalListStoreState.ThreeItemList == myState)
                { 
                    ThreeItemList newStore = new ThreeItemList();

                    // Extract the values from the old store and insert them into the new store
                    newStore.Promote(_listStore); 

                    // Insert the new item 
                    newStore.Add(value); 
                    _listStore = newStore;
                } 
                else if (FrugalListStoreState.SixItemList == myState)
                {
                    SixItemList newStore = new SixItemList();
 
                    // Extract the values from the old store and insert them into the new store
                    newStore.Promote(_listStore); 
                    _listStore = newStore; 

                    // Insert the new item 
                    newStore.Add(value);
                    _listStore = newStore;
                }
                else if (FrugalListStoreState.Array == myState) 
                {
                    ArrayItemList newStore = new ArrayItemList(_listStore.Count + 1); 
 
                    // Extract the values from the old store and insert them into the new store
                    newStore.Promote(_listStore); 
                    _listStore = newStore;

                    // Insert the new item
                    newStore.Add(value); 
                    _listStore = newStore;
                } 
                else 
                {
                    throw new InvalidOperationException(SR.Get(SRID.FrugalList_CannotPromoteBeyondArray)); 
                }
            }
            return _listStore.Count - 1;
        } 

        public void Clear() 
        { 
            if (null != _listStore)
            { 
                _listStore.Clear();
            }
        }
 
        public bool Contains(T value)
        { 
            if ((null != _listStore) && (_listStore.Count > 0)) 
            {
                return _listStore.Contains(value); 
            }
            return false;
        }
 
        public int IndexOf(T value)
        { 
            if ((null != _listStore) && (_listStore.Count > 0)) 
            {
                return _listStore.IndexOf(value); 
            }
            return -1;
        }
 
        public void Insert(int index, T value)
        { 
            if ((index == 0) || ((null != _listStore) && ((index <= _listStore.Count) && (index >= 0)))) 
            {
                // Make sure we have a place to put the item 
                int minCapacity = 1;

                if ((null != _listStore) && (_listStore.Count == _listStore.Capacity))
                { 
                    // Store is full
                    minCapacity = Capacity + 1; 
                } 

                // Make the Capacity at *least* this big 
                Capacity = minCapacity;

                _listStore.Insert(index, value);
                return; 
            }
            throw new ArgumentOutOfRangeException("index"); 
        } 

        public bool Remove(T value) 
        {
            if ((null != _listStore) && (_listStore.Count > 0))
            {
                return _listStore.Remove(value); 
            }
            return false; 
        } 

        public void RemoveAt(int index) 
        {
            if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0)))
            {
                _listStore.RemoveAt(index); 
                return;
            } 
            throw new ArgumentOutOfRangeException("index"); 
        }
 
        public void EnsureIndex(int index)
        {
            if (index >= 0)
            { 
                int delta = (index + 1) - Count;
                if (delta > 0) 
                { 
                    // Grow the store
                    Capacity = index + 1; 

                    T filler = default(T);

                    // Insert filler structs or objects 
                    for (int i = 0; i < delta; ++i)
                    { 
                        _listStore.Add(filler); 
                    }
                } 
                return;
            }
            throw new ArgumentOutOfRangeException("index");
        } 

        public T[] ToArray() 
        { 
            if ((null != _listStore) && (_listStore.Count > 0))
            { 
                return _listStore.ToArray();
            }
            return null;
        } 

        public void CopyTo(T[] array, int index) 
        { 
            if ((null != _listStore) && (_listStore.Count > 0))
            { 
                _listStore.CopyTo(array, index);
            }
        }
 
        public FrugalStructList Clone()
        { 
            FrugalStructList myClone = new FrugalStructList(); 

            if (null != _listStore) 
            {
                myClone._listStore = (FrugalListBase)_listStore.Clone();
            }
 
            return myClone;
        } 
 
        internal FrugalListBase _listStore;
    } 
}


// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.

                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK