MetadataCollection.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Net / Net / 3.5.50727.3053 / DEVDIV / depot / DevDiv / releases / Orcas / SP / ndp / fx / src / DataEntity / System / Data / Metadata / Edm / MetadataCollection.cs / 4 / MetadataCollection.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....], [....]
//--------------------------------------------------------------------- 
 
using System;
using System.Collections; 
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Data.Common;
using System.Reflection; 
using System.Text;
using System.Diagnostics; 
using System.Threading; 

namespace System.Data.Metadata.Edm 
{
    /// 
    /// Class representing an actual implementaton of a collection of metadata objects
    ///  
    /// The type of items in this collection
    internal class MetadataCollection : IList where T : MetadataItem 
    { 
        // The way the collection supports both case sensitive and insensitive search is that it maintains two lists: one list
        // for keep tracking of the order (the ordered list) and another list sorted case sensitively (the sorted list) by the 
        // identity of the item.  When a look up on ordinal is requested, the ordered list is used.  When a look up on the name
        // is requested, the sorted list is used.  The two list must be kept in [....] for all update operations.  For case
        // sensitive name lookup, the sorted list is searched.  For case insensitive name lookup, a binary search is used on the
        // sorted list to find the match. 

        // Note: Care must be taken when modifying logic in this class to call virtual methods in this class.  Since virtual methods 
        // can be override by a derived class, the possible results must be thought through.  If needed, add an internal method and 
        // have the public virtual method delegates to it.
 
        #region Constructors
        /// 
        /// Default constructor for constructing an empty collection
        ///  
        internal MetadataCollection()
            : this(null) 
        { 
        }
 
        /// 
        /// The constructor for constructing the collection with the given items
        /// 
        /// The items to populate the collection 
        internal MetadataCollection(IEnumerable items)
        { 
            _collectionData = new CollectionData(); 
            if (items != null)
            { 
                foreach (T item in items)
                {
                    if (item == null)
                    { 
                        throw EntityUtil.CollectionParameterElementIsNull("items");
                    } 
 
                    Debug.Assert(!String.IsNullOrEmpty(item.Identity), "Identity of the item must never be null or empty");
                    AddInternal(item); 
                }
            }

        } 
        #endregion
 
        #region Fields 

        /// structure to contain the indexes of items whose identity match by OrdinalIgnoreCase 
        private struct OrderedIndex {
            /// the index of the item whose identity was used to create the initial dictionary entry
            internal readonly int ExactIndex;
 
            /// the continuation of indexes whose item identities match by OrdinalIgnoreCase
            internal readonly int[] InexactIndexes; 
 
            internal OrderedIndex(int exactIndex, int[] inexactIndexes)
            { 
                ExactIndex = exactIndex;
                InexactIndexes = inexactIndexes;
            }
        } 

        private CollectionData _collectionData; 
        private bool _readOnly; 

#endregion 

        #region Properties
        /// 
        /// Gets whether the collection is a readonly collection 
        /// 
        public bool IsReadOnly 
        { 
            get
            { 
                return _readOnly;
            }
        }
 
        /// 
        /// Returns the collection as a readonly collection 
        ///  
        public virtual System.Collections.ObjectModel.ReadOnlyCollection AsReadOnly
        { 
            get
            {
                return _collectionData.OrderedList.AsReadOnly();
            } 
        }
 
 
        /// 
        /// Returns the collection as a read-only metadata collection. 
        /// 
        public virtual ReadOnlyMetadataCollection AsReadOnlyMetadataCollection()
        {
            return new ReadOnlyMetadataCollection(this); 
        }
 
        ///  
        /// Gets the count on the number of items in the collection
        ///  
        public virtual int Count
        {
            get
            { 
                return _collectionData.OrderedList.Count;
            } 
        } 

        ///  
        /// Gets an item from the collection with the given index
        /// 
        /// The index to search for
        /// An item from the collection 
        /// Thrown if the index is out of the range for the Collection
        /// Always thrown on setter 
        public virtual T this[int index] 
        {
            get 
            {
                return _collectionData.OrderedList[index];
            }
            set 
            {
                throw EntityUtil.OperationOnReadOnlyCollection(); 
            } 
        }
 
        /// 
        /// Gets an item from the collection with the given identity
        /// 
        /// The identity of the item to search for 
        /// An item from the collection
        /// Thrown if identity argument passed in is null 
        /// Thrown if the Collection does not have an item with the given identity 
        /// Always thrown on setter
        public virtual T this[string identity] 
        {
            get
            {
                return GetValue(identity, false); 
            }
            set 
            { 
                throw EntityUtil.OperationOnReadOnlyCollection();
            } 
        }
        #endregion

        #region Methods 
        /// 
        /// Gets an item from the collection with the given identity 
        ///  
        /// The identity of the item to search for
        /// Whether case is ignore in the search 
        /// An item from the collection
        /// Thrown if identity argument passed in is null
        /// Thrown if the Collection does not have an item with the given identity
        public T GetValue(string identity, bool ignoreCase) 
        {
            T item = InternalTryGetValue(identity, ignoreCase); 
            if (null == item) 
            {
                throw EntityUtil.ItemInvalidIdentity(identity, "identity"); 
            }
            return item;
        }
 
        /// 
        /// Adds an item to the collection 
        ///  
        /// The item to add to the list
        /// Thrown if item argument is null 
        /// Thrown if the item passed in or the collection itself instance is in ReadOnly state
        /// Thrown if the MetadataCollection already contains an item with the same identity
        /// Thrown if the item passed into Setter has null or String.Empty identity
        public virtual void Add(T item) 
        {
            AddInternal(item); 
        } 

        /// Adds an item to the identityDictionary 
        /// The collection data to add to
        /// The identity to add
        /// The identity's index in collection
        /// Whether the item should be updated if a matching item is found. 
        /// 
        /// Index of the added entity, possibly different from the index 
        /// parameter if updateIfFound is true. 
        /// 
        private static int AddToDictionary(CollectionData collectionData, string identity, int index, bool updateIfFound) 
        {
            Debug.Assert(collectionData != null && collectionData.IdentityDictionary != null, "the identity dictionary is null");
            Debug.Assert(!String.IsNullOrEmpty(identity), "empty identity");
            int[] inexact = null; 
            OrderedIndex orderIndex;
            int exactIndex = index; 
 
            // find the item(s) by OrdinalIgnoreCase
            if (collectionData.IdentityDictionary.TryGetValue(identity, out orderIndex)) 
            {
                // identity was already tracking an item, verify its not a duplicate by exact name
                if (EqualIdentity(collectionData.OrderedList, orderIndex.ExactIndex, identity))
                { 
                    // If the item is already here and we are updating, there is no more work to be done.
                    if (updateIfFound) 
                    { 
                        return orderIndex.ExactIndex;
                    } 
                    throw EntityUtil.ItemDuplicateIdentity(identity, "item", null);
                }
                else if (null != orderIndex.InexactIndexes)
                { 
                    // search against the ExactIndex and all InexactIndexes
                    // identity was already tracking multiple items, verify its not a duplicate by exact name 
                    for(int i = 0; i < orderIndex.InexactIndexes.Length; ++i) 
                    {
                        if (EqualIdentity(collectionData.OrderedList, orderIndex.InexactIndexes[i], identity)) 
                        {
                            // If the item is already here and we are updating, there is no more work to be done.
                            if (updateIfFound)
                            { 
                                return orderIndex.InexactIndexes[i];
                            } 
                            throw EntityUtil.ItemDuplicateIdentity(identity, "item", null); 
                        }
                    } 
                    // add another item for existing identity that already was tracking multiple items
                    inexact = new int[orderIndex.InexactIndexes.Length + 1];
                    orderIndex.InexactIndexes.CopyTo(inexact, 0);
                    inexact[inexact.Length-1] = index; 
                }
                else 
                { 
                    // turn the previously unique identity by ignore case into a multiple item for identity by ignore case
                    inexact = new int[1] { index }; 
                }
                // the index of the item whose identity was used to create the initial dictionary entry
                exactIndex = orderIndex.ExactIndex;
            } 
            // else this is a new identity
 
            collectionData.IdentityDictionary[identity] = new OrderedIndex(exactIndex, inexact); 
            return index;
        } 

        /// 
        /// Adds an item to the collection
        ///  
        /// This method only exists to allow ctor to avoid virtual method call
        /// The item to add to the list 
        /// Thrown if item argument is null 
        /// Thrown if the item passed in or the collection itself instance is in ReadOnly state
        /// Thrown if the MetadataCollection already contains an item with the same identity 
        /// Thrown if the item passed into Setter has null or String.Empty identity
        private void AddInternal(T item)
        {
            Util.CheckItemHasIdentity(item, "item"); 
            ThrowIfReadOnly();
 
            AddInternalHelper(item, _collectionData, false); 
        }
 

        // This magic number was determined by the performance test cases in SQLBU 489927.
        // It compared Dictionary (hashtable), SortedList (binary search) and linear searching.
        // Its the approximate (x86) point at which doing a OrdinalCaseInsenstive linear search on _orderedItems. 
        // becomes slower than doing a OrdinalCaseInsenstive Dictionary lookup in identityDictionary.
        // On x64, the crossover point is lower - but we desire to keep a smaller overal memory footprint. 
        // We expect the ItemCollections to be large, but individual Member/Facet collections to be small. 
        private const int UseSortedListCrossover = 25;
 
        /// 
        /// Adds an item to the collection represented by a list and a dictionary
        /// 
        /// The item to add to the list 
        /// The collection data where the item will be added
        /// Whether the item should be updated if a matching item is found. 
        /// Thrown if item argument is null 
        /// Thrown if the item passed in or the collection itself instance is in ReadOnly state
        /// Thrown if the MetadataCollection already contains an item with the same identity 
        /// Thrown if the item passed into Setter has null or String.Empty identity
        /// 
        /// If updateIfFound is true, then an update is done in-place instead of
        /// having an exception thrown. The in-place aspect is required to avoid 
        /// disrupting the indices generated for indexed items, and to enable
        /// foreach loops to be able to modify the enumerated facets as if it 
        /// were a property update rather than an instance replacement. 
        /// 
        private static void AddInternalHelper(T item, CollectionData collectionData, bool updateIfFound) 
        {
            Util.CheckItemHasIdentity(item, "item");

            int index; 
            int listCount = collectionData.OrderedList.Count;
            if (null != collectionData.IdentityDictionary) 
            { 
                index = AddToDictionary(collectionData, item.Identity, listCount, updateIfFound);
            } 
            else
            {
                // We only have to take care of the ordered list.
                index = IndexOf(collectionData, item.Identity, false); 
                if (0 <= index)
                { 
                    // The item is found in the linear ordered list. Unless 
                    // we're updating, it's an error.
                    if (!updateIfFound) 
                    {
                        throw EntityUtil.ItemDuplicateIdentity(item.Identity, "item", null);
                    }
                } 
                else
                { 
                    // This is a new item to be inserted. Grow if we must before adding to ordered list. 
                    if (UseSortedListCrossover <= listCount)
                    { 
                        collectionData.IdentityDictionary = new Dictionary(collectionData.OrderedList.Count + 1, StringComparer.OrdinalIgnoreCase);
                        for (int i = 0; i < collectionData.OrderedList.Count; ++i)
                        {
                            AddToDictionary(collectionData, collectionData.OrderedList[i].Identity, i, false); 
                        }
                        AddToDictionary(collectionData, item.Identity, listCount, false); 
                    } 
                }
            } 

            // Index will be listCount when AddToDictionary doesn't find
            // an existing match, and -1 if IndexOf doesn't find in ordered list.
            if (0 <= index && index < listCount) 
            {
                collectionData.OrderedList[index] = item; 
            } 
            else
            { 
                System.Diagnostics.Debug.Assert(index == -1 || index == listCount);
                collectionData.OrderedList.Add(item);
            }
        } 

        ///  
        /// Adds a collection of items to the collection 
        /// 
        /// The items to add to the list 
        /// Thrown if item argument is null
        /// Thrown if the item passed in or the collection itself instance is in ReadOnly state
        /// Thrown if the item that is being added already belongs to another ItemCollection
        /// Thrown if the ItemCollection already contains an item with the same identity 
        /// Whether the add was successful
        internal bool AtomicAddRange(List items) 
        { 
            CollectionData originalData = _collectionData;
            CollectionData newData = new CollectionData(originalData, items.Count); 

            // Add the new items, this will also perform duplication check
            foreach (T item in items)
            { 
                AddInternalHelper(item, newData, false);
            } 
 
            CollectionData swappedOutData = Interlocked.CompareExchange(ref _collectionData, newData, originalData);
 
            // Check if the exchange was done, if not, then someone must have changed the data in the meantime, so
            // return false
            if (swappedOutData != originalData)
            { 
                return false;
            } 
 
            return true;
        } 

        /// Does Item at index have the same identity
        private static bool EqualIdentity(List orderedList, int index, string identity)
        { 
            return ((string)orderedList[index].Identity == (string)identity);
        } 
 
        /// 
        /// Not supported, the collection is treated as read-only. 
        /// 
        /// The index where to insert the given item
        /// The item to be inserted
        /// Thrown if the item passed in or the collection itself instance is in ReadOnly state 
        void IList.Insert(int index, T item)
        { 
            throw EntityUtil.OperationOnReadOnlyCollection(); 
        }
 
        /// 
        /// Not supported, the collection is treated as read-only.
        /// 
        /// The item to be removed 
        /// True if the item is actually removed, false if the item is not in the list
        /// Always thrown 
        bool ICollection.Remove(T item) 
        {
            throw EntityUtil.OperationOnReadOnlyCollection(); 
        }

        /// 
        /// Not supported, the collection is treated as read-only. 
        /// 
        /// The index at which the item is removed 
        /// Always thrown 
        void IList.RemoveAt(int index)
        { 
            throw EntityUtil.OperationOnReadOnlyCollection();
        }

        ///  
        /// Not supported, the collection is treated as read-only.
        ///  
        /// Always thrown 
        void ICollection.Clear()
        { 
            throw EntityUtil.OperationOnReadOnlyCollection();
        }

        ///  
        /// Determines if this collection contains the given item
        ///  
        /// The item to check for 
        /// True if the collection contains the item
        /// Thrown if item argument passed in is null 
        /// Thrown if the item passed in has null or String.Empty identity
        public bool Contains(T item)
        {
            Util.CheckItemHasIdentity(item, "item"); 
            return (-1 != IndexOf(item));
        } 
 
        /// 
        /// Determines if this collection contains an item of the given identity 
        /// 
        /// The identity of the item to check for
        /// True if the collection contains the item with the given identity
        /// Thrown if identity argument passed in is null 
        /// Thrown if identity argument passed in is empty string
        public virtual bool ContainsIdentity(string identity) 
        { 
            EntityUtil.CheckStringArgument(identity, "identity");
            return (0 <= IndexOf(_collectionData, identity, false)); 
        }

        /// Find the index of an item identitified by identity
        /// The collection data to search in 
        /// The identity whose index is to be returned
        /// Should OrdinalIgnoreCase be used? 
        /// The index of the found item, -1 if not found 
        /// Thrown if ignoreCase and an exact match does not exist, but has multiple inexact matches
        private static int IndexOf(CollectionData collectionData, string identity, bool ignoreCase) 
        {
            Debug.Assert(null != identity, "null identity");

            int index = -1; 
            if (null != collectionData.IdentityDictionary)
            {   // OrdinalIgnoreCase dictionary lookup 
                OrderedIndex orderIndex; 
                if (collectionData.IdentityDictionary.TryGetValue(identity, out orderIndex))
                { 
                    if (ignoreCase)
                    {
                        index = orderIndex.ExactIndex;
                    } 
                    //return this, only in case when ignore case is false
                    else if (EqualIdentity(collectionData.OrderedList, orderIndex.ExactIndex, identity)) 
                    {   // fast return if exact match 
                        return orderIndex.ExactIndex;
                    } 

                    // search against the ExactIndex and all InexactIndexes
                    if (null != orderIndex.InexactIndexes)
                    { 
                        if (ignoreCase)
                        {   // the ignoreCase will throw, 
                            throw EntityUtil.MoreThanOneItemMatchesIdentity(identity); 
                        }
                        // search for the exact match or throw if ignoreCase 
                        for (int i = 0; i < orderIndex.InexactIndexes.Length; ++i)
                        {
                            if (EqualIdentity(collectionData.OrderedList, orderIndex.InexactIndexes[i], identity))
                            { 
                                return orderIndex.InexactIndexes[i];
                            } 
                        } 
                    }
                    Debug.Assert(ignoreCase == (0 <= index), "indexof verification"); 
                }
            }
            else if (ignoreCase)
            {   // OrdinalIgnoreCase linear search 
                for(int i = 0; i < collectionData.OrderedList.Count; ++i)
                { 
                    if (String.Equals(collectionData.OrderedList[i].Identity, identity, StringComparison.OrdinalIgnoreCase)) 
                    {
                        if (0 <= index) 
                        {
                            throw EntityUtil.MoreThanOneItemMatchesIdentity(identity);
                        }
                        index = i; 
                    }
                } 
            } 
            else
            {   // Ordinal linear search 
                for (int i = 0; i < collectionData.OrderedList.Count; ++i)
                {
                    if (EqualIdentity(collectionData.OrderedList, i, identity))
                    { 
                        return i;
                    } 
                } 
            }
            return index; 
        }

        /// 
        /// Find the index of an item 
        /// 
        /// The item whose index is to be looked for 
        /// The index of the found item, -1 if not found 
        /// Thrown if item argument passed in is null
        /// Thrown if the item passed in has null or String.Empty identity 
        public virtual int IndexOf(T item)
        {
            Util.CheckItemHasIdentity(item, "item");
            int index = IndexOf(_collectionData, item.Identity, false); 

            if (index != -1 && _collectionData.OrderedList[index] == item) 
            { 
                return index;
            } 

            return -1;
        }
 
        /// 
        /// Copies the items in this collection to an array 
        ///  
        /// The array to copy to
        /// The index in the array at which to start the copy 
        /// Thrown if array argument is null
        /// Thrown if the arrayIndex is less than zero
        /// Thrown if the array argument passed in with respect to the arrayIndex passed in not big enough to hold the MetadataCollection being copied
        public virtual void CopyTo(T[] array, int arrayIndex) 
        {
            EntityUtil.GenericCheckArgumentNull(array, "array"); 
 
            if (arrayIndex < 0)
            { 
                throw EntityUtil.ArgumentOutOfRange("arrayIndex");
            }

            if (_collectionData.OrderedList.Count > array.Length - arrayIndex) 
            {
                throw EntityUtil.ArrayTooSmall("arrayIndex"); 
            } 

            _collectionData.OrderedList.CopyTo(array, arrayIndex); 
        }

        /// 
        /// Gets the enumerator over this collection 
        /// 
        ///  
        public ReadOnlyMetadataCollection.Enumerator GetEnumerator() 
        {
            return new ReadOnlyMetadataCollection.Enumerator(this); 
        }

        /// 
        /// Gets the enumerator over this collection 
        /// 
        ///  
        IEnumerator IEnumerable.GetEnumerator() 
        {
            return this.GetEnumerator(); 
        }

        /// 
        /// Gets the enumerator over this collection 
        /// 
        ///  
        IEnumerator IEnumerable.GetEnumerator() 
        {
            return this.GetEnumerator(); 
        }

        /// 
        /// Set this collection as readonly so no more changes can be made on it 
        /// 
        public MetadataCollection SetReadOnly() 
        { 
            for (int i = 0; i < _collectionData.OrderedList.Count; i++)
            { 
                _collectionData.OrderedList[i].SetReadOnly();
            }
            _collectionData.OrderedList.TrimExcess();
            _readOnly = true; 
            return this;
        } 
 
        /// 
        /// Gets an item from the collection with the given identity 
        /// 
        /// The identity of the item to search for
        /// Whether case is ignore in the search
        /// An item from the collection, null if the item is not found 
        /// True an item is retrieved
        /// Thrown if the identity argument is null  
        public virtual bool TryGetValue(string identity, bool ignoreCase, out T item) 
        {
            item = InternalTryGetValue(identity, ignoreCase); 
            return (null != item);
        }

        ///  
        /// Gets an item from the collection with the given identity
        ///  
        /// The identity of the item to search for 
        /// Whether case is ignore in the search
        /// item else null 
        private T InternalTryGetValue(string identity, bool ignoreCase)
        {
            int index = IndexOf(_collectionData, EntityUtil.GenericCheckArgumentNull(identity, "identity"), ignoreCase);
            Debug.Assert((index < 0) || 
                        (ignoreCase && String.Equals(_collectionData.OrderedList[index].Identity, identity, StringComparison.OrdinalIgnoreCase)) ||
                        EqualIdentity(_collectionData.OrderedList, index, identity), "different exact identity"); 
            return (0 <= index) ? _collectionData.OrderedList[index] : null; 
        }
 
        /// 
        /// Throws an appropriate exception if the given item is a readonly, used when an attempt is made to change
        /// the collection
        ///  
        internal void ThrowIfReadOnly()
        { 
            if (IsReadOnly) 
            {
                throw EntityUtil.OperationOnReadOnlyCollection(); 
            }
        }

        #endregion 

        #region InnerClasses 
 
        /// 
        /// The data structures for this collection, which contains a list and a dictionary 
        /// 
        private class CollectionData
        {
            ///  
            /// The IdentityDictionary is a case-insensitive dictionary
            /// used after a certain # of elements have been added to the OrderedList. 
            /// It aids in fast lookup by T.Identity by mapping a string value to 
            /// an OrderedIndex structure with other case-insensitive matches for the
            /// entry.  See additional comments in AddInternal. 
            /// 
            internal Dictionary IdentityDictionary;
            internal List OrderedList;
 
            internal CollectionData()
            { 
                OrderedList = new List(); 
            }
 
            internal CollectionData(CollectionData original, int additionalCapacity)
            {
                this.OrderedList = new List(original.OrderedList.Count + additionalCapacity);
                foreach (T item in original.OrderedList) 
                {   // using AddRange results in a temporary memory allocation
                    this.OrderedList.Add(item); 
                } 

                if (UseSortedListCrossover <= this.OrderedList.Capacity) 
                {
                    this.IdentityDictionary = new Dictionary(this.OrderedList.Capacity, StringComparer.OrdinalIgnoreCase);

                    if (null != original.IdentityDictionary) 
                    {
                        foreach (KeyValuePair pair in original.IdentityDictionary) 
                        { 
                            this.IdentityDictionary.Add(pair.Key, pair.Value);
                        } 
                    }
                    else
                    {
                        for (int i = 0; i < this.OrderedList.Count; ++i) 
                        {
                            AddToDictionary(this, this.OrderedList[i].Identity, i, false); 
                        } 
                    }
                } 
            }
        }

        #endregion 
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....], [....]
//--------------------------------------------------------------------- 
 
using System;
using System.Collections; 
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Data.Common;
using System.Reflection; 
using System.Text;
using System.Diagnostics; 
using System.Threading; 

namespace System.Data.Metadata.Edm 
{
    /// 
    /// Class representing an actual implementaton of a collection of metadata objects
    ///  
    /// The type of items in this collection
    internal class MetadataCollection : IList where T : MetadataItem 
    { 
        // The way the collection supports both case sensitive and insensitive search is that it maintains two lists: one list
        // for keep tracking of the order (the ordered list) and another list sorted case sensitively (the sorted list) by the 
        // identity of the item.  When a look up on ordinal is requested, the ordered list is used.  When a look up on the name
        // is requested, the sorted list is used.  The two list must be kept in [....] for all update operations.  For case
        // sensitive name lookup, the sorted list is searched.  For case insensitive name lookup, a binary search is used on the
        // sorted list to find the match. 

        // Note: Care must be taken when modifying logic in this class to call virtual methods in this class.  Since virtual methods 
        // can be override by a derived class, the possible results must be thought through.  If needed, add an internal method and 
        // have the public virtual method delegates to it.
 
        #region Constructors
        /// 
        /// Default constructor for constructing an empty collection
        ///  
        internal MetadataCollection()
            : this(null) 
        { 
        }
 
        /// 
        /// The constructor for constructing the collection with the given items
        /// 
        /// The items to populate the collection 
        internal MetadataCollection(IEnumerable items)
        { 
            _collectionData = new CollectionData(); 
            if (items != null)
            { 
                foreach (T item in items)
                {
                    if (item == null)
                    { 
                        throw EntityUtil.CollectionParameterElementIsNull("items");
                    } 
 
                    Debug.Assert(!String.IsNullOrEmpty(item.Identity), "Identity of the item must never be null or empty");
                    AddInternal(item); 
                }
            }

        } 
        #endregion
 
        #region Fields 

        /// structure to contain the indexes of items whose identity match by OrdinalIgnoreCase 
        private struct OrderedIndex {
            /// the index of the item whose identity was used to create the initial dictionary entry
            internal readonly int ExactIndex;
 
            /// the continuation of indexes whose item identities match by OrdinalIgnoreCase
            internal readonly int[] InexactIndexes; 
 
            internal OrderedIndex(int exactIndex, int[] inexactIndexes)
            { 
                ExactIndex = exactIndex;
                InexactIndexes = inexactIndexes;
            }
        } 

        private CollectionData _collectionData; 
        private bool _readOnly; 

#endregion 

        #region Properties
        /// 
        /// Gets whether the collection is a readonly collection 
        /// 
        public bool IsReadOnly 
        { 
            get
            { 
                return _readOnly;
            }
        }
 
        /// 
        /// Returns the collection as a readonly collection 
        ///  
        public virtual System.Collections.ObjectModel.ReadOnlyCollection AsReadOnly
        { 
            get
            {
                return _collectionData.OrderedList.AsReadOnly();
            } 
        }
 
 
        /// 
        /// Returns the collection as a read-only metadata collection. 
        /// 
        public virtual ReadOnlyMetadataCollection AsReadOnlyMetadataCollection()
        {
            return new ReadOnlyMetadataCollection(this); 
        }
 
        ///  
        /// Gets the count on the number of items in the collection
        ///  
        public virtual int Count
        {
            get
            { 
                return _collectionData.OrderedList.Count;
            } 
        } 

        ///  
        /// Gets an item from the collection with the given index
        /// 
        /// The index to search for
        /// An item from the collection 
        /// Thrown if the index is out of the range for the Collection
        /// Always thrown on setter 
        public virtual T this[int index] 
        {
            get 
            {
                return _collectionData.OrderedList[index];
            }
            set 
            {
                throw EntityUtil.OperationOnReadOnlyCollection(); 
            } 
        }
 
        /// 
        /// Gets an item from the collection with the given identity
        /// 
        /// The identity of the item to search for 
        /// An item from the collection
        /// Thrown if identity argument passed in is null 
        /// Thrown if the Collection does not have an item with the given identity 
        /// Always thrown on setter
        public virtual T this[string identity] 
        {
            get
            {
                return GetValue(identity, false); 
            }
            set 
            { 
                throw EntityUtil.OperationOnReadOnlyCollection();
            } 
        }
        #endregion

        #region Methods 
        /// 
        /// Gets an item from the collection with the given identity 
        ///  
        /// The identity of the item to search for
        /// Whether case is ignore in the search 
        /// An item from the collection
        /// Thrown if identity argument passed in is null
        /// Thrown if the Collection does not have an item with the given identity
        public T GetValue(string identity, bool ignoreCase) 
        {
            T item = InternalTryGetValue(identity, ignoreCase); 
            if (null == item) 
            {
                throw EntityUtil.ItemInvalidIdentity(identity, "identity"); 
            }
            return item;
        }
 
        /// 
        /// Adds an item to the collection 
        ///  
        /// The item to add to the list
        /// Thrown if item argument is null 
        /// Thrown if the item passed in or the collection itself instance is in ReadOnly state
        /// Thrown if the MetadataCollection already contains an item with the same identity
        /// Thrown if the item passed into Setter has null or String.Empty identity
        public virtual void Add(T item) 
        {
            AddInternal(item); 
        } 

        /// Adds an item to the identityDictionary 
        /// The collection data to add to
        /// The identity to add
        /// The identity's index in collection
        /// Whether the item should be updated if a matching item is found. 
        /// 
        /// Index of the added entity, possibly different from the index 
        /// parameter if updateIfFound is true. 
        /// 
        private static int AddToDictionary(CollectionData collectionData, string identity, int index, bool updateIfFound) 
        {
            Debug.Assert(collectionData != null && collectionData.IdentityDictionary != null, "the identity dictionary is null");
            Debug.Assert(!String.IsNullOrEmpty(identity), "empty identity");
            int[] inexact = null; 
            OrderedIndex orderIndex;
            int exactIndex = index; 
 
            // find the item(s) by OrdinalIgnoreCase
            if (collectionData.IdentityDictionary.TryGetValue(identity, out orderIndex)) 
            {
                // identity was already tracking an item, verify its not a duplicate by exact name
                if (EqualIdentity(collectionData.OrderedList, orderIndex.ExactIndex, identity))
                { 
                    // If the item is already here and we are updating, there is no more work to be done.
                    if (updateIfFound) 
                    { 
                        return orderIndex.ExactIndex;
                    } 
                    throw EntityUtil.ItemDuplicateIdentity(identity, "item", null);
                }
                else if (null != orderIndex.InexactIndexes)
                { 
                    // search against the ExactIndex and all InexactIndexes
                    // identity was already tracking multiple items, verify its not a duplicate by exact name 
                    for(int i = 0; i < orderIndex.InexactIndexes.Length; ++i) 
                    {
                        if (EqualIdentity(collectionData.OrderedList, orderIndex.InexactIndexes[i], identity)) 
                        {
                            // If the item is already here and we are updating, there is no more work to be done.
                            if (updateIfFound)
                            { 
                                return orderIndex.InexactIndexes[i];
                            } 
                            throw EntityUtil.ItemDuplicateIdentity(identity, "item", null); 
                        }
                    } 
                    // add another item for existing identity that already was tracking multiple items
                    inexact = new int[orderIndex.InexactIndexes.Length + 1];
                    orderIndex.InexactIndexes.CopyTo(inexact, 0);
                    inexact[inexact.Length-1] = index; 
                }
                else 
                { 
                    // turn the previously unique identity by ignore case into a multiple item for identity by ignore case
                    inexact = new int[1] { index }; 
                }
                // the index of the item whose identity was used to create the initial dictionary entry
                exactIndex = orderIndex.ExactIndex;
            } 
            // else this is a new identity
 
            collectionData.IdentityDictionary[identity] = new OrderedIndex(exactIndex, inexact); 
            return index;
        } 

        /// 
        /// Adds an item to the collection
        ///  
        /// This method only exists to allow ctor to avoid virtual method call
        /// The item to add to the list 
        /// Thrown if item argument is null 
        /// Thrown if the item passed in or the collection itself instance is in ReadOnly state
        /// Thrown if the MetadataCollection already contains an item with the same identity 
        /// Thrown if the item passed into Setter has null or String.Empty identity
        private void AddInternal(T item)
        {
            Util.CheckItemHasIdentity(item, "item"); 
            ThrowIfReadOnly();
 
            AddInternalHelper(item, _collectionData, false); 
        }
 

        // This magic number was determined by the performance test cases in SQLBU 489927.
        // It compared Dictionary (hashtable), SortedList (binary search) and linear searching.
        // Its the approximate (x86) point at which doing a OrdinalCaseInsenstive linear search on _orderedItems. 
        // becomes slower than doing a OrdinalCaseInsenstive Dictionary lookup in identityDictionary.
        // On x64, the crossover point is lower - but we desire to keep a smaller overal memory footprint. 
        // We expect the ItemCollections to be large, but individual Member/Facet collections to be small. 
        private const int UseSortedListCrossover = 25;
 
        /// 
        /// Adds an item to the collection represented by a list and a dictionary
        /// 
        /// The item to add to the list 
        /// The collection data where the item will be added
        /// Whether the item should be updated if a matching item is found. 
        /// Thrown if item argument is null 
        /// Thrown if the item passed in or the collection itself instance is in ReadOnly state
        /// Thrown if the MetadataCollection already contains an item with the same identity 
        /// Thrown if the item passed into Setter has null or String.Empty identity
        /// 
        /// If updateIfFound is true, then an update is done in-place instead of
        /// having an exception thrown. The in-place aspect is required to avoid 
        /// disrupting the indices generated for indexed items, and to enable
        /// foreach loops to be able to modify the enumerated facets as if it 
        /// were a property update rather than an instance replacement. 
        /// 
        private static void AddInternalHelper(T item, CollectionData collectionData, bool updateIfFound) 
        {
            Util.CheckItemHasIdentity(item, "item");

            int index; 
            int listCount = collectionData.OrderedList.Count;
            if (null != collectionData.IdentityDictionary) 
            { 
                index = AddToDictionary(collectionData, item.Identity, listCount, updateIfFound);
            } 
            else
            {
                // We only have to take care of the ordered list.
                index = IndexOf(collectionData, item.Identity, false); 
                if (0 <= index)
                { 
                    // The item is found in the linear ordered list. Unless 
                    // we're updating, it's an error.
                    if (!updateIfFound) 
                    {
                        throw EntityUtil.ItemDuplicateIdentity(item.Identity, "item", null);
                    }
                } 
                else
                { 
                    // This is a new item to be inserted. Grow if we must before adding to ordered list. 
                    if (UseSortedListCrossover <= listCount)
                    { 
                        collectionData.IdentityDictionary = new Dictionary(collectionData.OrderedList.Count + 1, StringComparer.OrdinalIgnoreCase);
                        for (int i = 0; i < collectionData.OrderedList.Count; ++i)
                        {
                            AddToDictionary(collectionData, collectionData.OrderedList[i].Identity, i, false); 
                        }
                        AddToDictionary(collectionData, item.Identity, listCount, false); 
                    } 
                }
            } 

            // Index will be listCount when AddToDictionary doesn't find
            // an existing match, and -1 if IndexOf doesn't find in ordered list.
            if (0 <= index && index < listCount) 
            {
                collectionData.OrderedList[index] = item; 
            } 
            else
            { 
                System.Diagnostics.Debug.Assert(index == -1 || index == listCount);
                collectionData.OrderedList.Add(item);
            }
        } 

        ///  
        /// Adds a collection of items to the collection 
        /// 
        /// The items to add to the list 
        /// Thrown if item argument is null
        /// Thrown if the item passed in or the collection itself instance is in ReadOnly state
        /// Thrown if the item that is being added already belongs to another ItemCollection
        /// Thrown if the ItemCollection already contains an item with the same identity 
        /// Whether the add was successful
        internal bool AtomicAddRange(List items) 
        { 
            CollectionData originalData = _collectionData;
            CollectionData newData = new CollectionData(originalData, items.Count); 

            // Add the new items, this will also perform duplication check
            foreach (T item in items)
            { 
                AddInternalHelper(item, newData, false);
            } 
 
            CollectionData swappedOutData = Interlocked.CompareExchange(ref _collectionData, newData, originalData);
 
            // Check if the exchange was done, if not, then someone must have changed the data in the meantime, so
            // return false
            if (swappedOutData != originalData)
            { 
                return false;
            } 
 
            return true;
        } 

        /// Does Item at index have the same identity
        private static bool EqualIdentity(List orderedList, int index, string identity)
        { 
            return ((string)orderedList[index].Identity == (string)identity);
        } 
 
        /// 
        /// Not supported, the collection is treated as read-only. 
        /// 
        /// The index where to insert the given item
        /// The item to be inserted
        /// Thrown if the item passed in or the collection itself instance is in ReadOnly state 
        void IList.Insert(int index, T item)
        { 
            throw EntityUtil.OperationOnReadOnlyCollection(); 
        }
 
        /// 
        /// Not supported, the collection is treated as read-only.
        /// 
        /// The item to be removed 
        /// True if the item is actually removed, false if the item is not in the list
        /// Always thrown 
        bool ICollection.Remove(T item) 
        {
            throw EntityUtil.OperationOnReadOnlyCollection(); 
        }

        /// 
        /// Not supported, the collection is treated as read-only. 
        /// 
        /// The index at which the item is removed 
        /// Always thrown 
        void IList.RemoveAt(int index)
        { 
            throw EntityUtil.OperationOnReadOnlyCollection();
        }

        ///  
        /// Not supported, the collection is treated as read-only.
        ///  
        /// Always thrown 
        void ICollection.Clear()
        { 
            throw EntityUtil.OperationOnReadOnlyCollection();
        }

        ///  
        /// Determines if this collection contains the given item
        ///  
        /// The item to check for 
        /// True if the collection contains the item
        /// Thrown if item argument passed in is null 
        /// Thrown if the item passed in has null or String.Empty identity
        public bool Contains(T item)
        {
            Util.CheckItemHasIdentity(item, "item"); 
            return (-1 != IndexOf(item));
        } 
 
        /// 
        /// Determines if this collection contains an item of the given identity 
        /// 
        /// The identity of the item to check for
        /// True if the collection contains the item with the given identity
        /// Thrown if identity argument passed in is null 
        /// Thrown if identity argument passed in is empty string
        public virtual bool ContainsIdentity(string identity) 
        { 
            EntityUtil.CheckStringArgument(identity, "identity");
            return (0 <= IndexOf(_collectionData, identity, false)); 
        }

        /// Find the index of an item identitified by identity
        /// The collection data to search in 
        /// The identity whose index is to be returned
        /// Should OrdinalIgnoreCase be used? 
        /// The index of the found item, -1 if not found 
        /// Thrown if ignoreCase and an exact match does not exist, but has multiple inexact matches
        private static int IndexOf(CollectionData collectionData, string identity, bool ignoreCase) 
        {
            Debug.Assert(null != identity, "null identity");

            int index = -1; 
            if (null != collectionData.IdentityDictionary)
            {   // OrdinalIgnoreCase dictionary lookup 
                OrderedIndex orderIndex; 
                if (collectionData.IdentityDictionary.TryGetValue(identity, out orderIndex))
                { 
                    if (ignoreCase)
                    {
                        index = orderIndex.ExactIndex;
                    } 
                    //return this, only in case when ignore case is false
                    else if (EqualIdentity(collectionData.OrderedList, orderIndex.ExactIndex, identity)) 
                    {   // fast return if exact match 
                        return orderIndex.ExactIndex;
                    } 

                    // search against the ExactIndex and all InexactIndexes
                    if (null != orderIndex.InexactIndexes)
                    { 
                        if (ignoreCase)
                        {   // the ignoreCase will throw, 
                            throw EntityUtil.MoreThanOneItemMatchesIdentity(identity); 
                        }
                        // search for the exact match or throw if ignoreCase 
                        for (int i = 0; i < orderIndex.InexactIndexes.Length; ++i)
                        {
                            if (EqualIdentity(collectionData.OrderedList, orderIndex.InexactIndexes[i], identity))
                            { 
                                return orderIndex.InexactIndexes[i];
                            } 
                        } 
                    }
                    Debug.Assert(ignoreCase == (0 <= index), "indexof verification"); 
                }
            }
            else if (ignoreCase)
            {   // OrdinalIgnoreCase linear search 
                for(int i = 0; i < collectionData.OrderedList.Count; ++i)
                { 
                    if (String.Equals(collectionData.OrderedList[i].Identity, identity, StringComparison.OrdinalIgnoreCase)) 
                    {
                        if (0 <= index) 
                        {
                            throw EntityUtil.MoreThanOneItemMatchesIdentity(identity);
                        }
                        index = i; 
                    }
                } 
            } 
            else
            {   // Ordinal linear search 
                for (int i = 0; i < collectionData.OrderedList.Count; ++i)
                {
                    if (EqualIdentity(collectionData.OrderedList, i, identity))
                    { 
                        return i;
                    } 
                } 
            }
            return index; 
        }

        /// 
        /// Find the index of an item 
        /// 
        /// The item whose index is to be looked for 
        /// The index of the found item, -1 if not found 
        /// Thrown if item argument passed in is null
        /// Thrown if the item passed in has null or String.Empty identity 
        public virtual int IndexOf(T item)
        {
            Util.CheckItemHasIdentity(item, "item");
            int index = IndexOf(_collectionData, item.Identity, false); 

            if (index != -1 && _collectionData.OrderedList[index] == item) 
            { 
                return index;
            } 

            return -1;
        }
 
        /// 
        /// Copies the items in this collection to an array 
        ///  
        /// The array to copy to
        /// The index in the array at which to start the copy 
        /// Thrown if array argument is null
        /// Thrown if the arrayIndex is less than zero
        /// Thrown if the array argument passed in with respect to the arrayIndex passed in not big enough to hold the MetadataCollection being copied
        public virtual void CopyTo(T[] array, int arrayIndex) 
        {
            EntityUtil.GenericCheckArgumentNull(array, "array"); 
 
            if (arrayIndex < 0)
            { 
                throw EntityUtil.ArgumentOutOfRange("arrayIndex");
            }

            if (_collectionData.OrderedList.Count > array.Length - arrayIndex) 
            {
                throw EntityUtil.ArrayTooSmall("arrayIndex"); 
            } 

            _collectionData.OrderedList.CopyTo(array, arrayIndex); 
        }

        /// 
        /// Gets the enumerator over this collection 
        /// 
        ///  
        public ReadOnlyMetadataCollection.Enumerator GetEnumerator() 
        {
            return new ReadOnlyMetadataCollection.Enumerator(this); 
        }

        /// 
        /// Gets the enumerator over this collection 
        /// 
        ///  
        IEnumerator IEnumerable.GetEnumerator() 
        {
            return this.GetEnumerator(); 
        }

        /// 
        /// Gets the enumerator over this collection 
        /// 
        ///  
        IEnumerator IEnumerable.GetEnumerator() 
        {
            return this.GetEnumerator(); 
        }

        /// 
        /// Set this collection as readonly so no more changes can be made on it 
        /// 
        public MetadataCollection SetReadOnly() 
        { 
            for (int i = 0; i < _collectionData.OrderedList.Count; i++)
            { 
                _collectionData.OrderedList[i].SetReadOnly();
            }
            _collectionData.OrderedList.TrimExcess();
            _readOnly = true; 
            return this;
        } 
 
        /// 
        /// Gets an item from the collection with the given identity 
        /// 
        /// The identity of the item to search for
        /// Whether case is ignore in the search
        /// An item from the collection, null if the item is not found 
        /// True an item is retrieved
        /// Thrown if the identity argument is null  
        public virtual bool TryGetValue(string identity, bool ignoreCase, out T item) 
        {
            item = InternalTryGetValue(identity, ignoreCase); 
            return (null != item);
        }

        ///  
        /// Gets an item from the collection with the given identity
        ///  
        /// The identity of the item to search for 
        /// Whether case is ignore in the search
        /// item else null 
        private T InternalTryGetValue(string identity, bool ignoreCase)
        {
            int index = IndexOf(_collectionData, EntityUtil.GenericCheckArgumentNull(identity, "identity"), ignoreCase);
            Debug.Assert((index < 0) || 
                        (ignoreCase && String.Equals(_collectionData.OrderedList[index].Identity, identity, StringComparison.OrdinalIgnoreCase)) ||
                        EqualIdentity(_collectionData.OrderedList, index, identity), "different exact identity"); 
            return (0 <= index) ? _collectionData.OrderedList[index] : null; 
        }
 
        /// 
        /// Throws an appropriate exception if the given item is a readonly, used when an attempt is made to change
        /// the collection
        ///  
        internal void ThrowIfReadOnly()
        { 
            if (IsReadOnly) 
            {
                throw EntityUtil.OperationOnReadOnlyCollection(); 
            }
        }

        #endregion 

        #region InnerClasses 
 
        /// 
        /// The data structures for this collection, which contains a list and a dictionary 
        /// 
        private class CollectionData
        {
            ///  
            /// The IdentityDictionary is a case-insensitive dictionary
            /// used after a certain # of elements have been added to the OrderedList. 
            /// It aids in fast lookup by T.Identity by mapping a string value to 
            /// an OrderedIndex structure with other case-insensitive matches for the
            /// entry.  See additional comments in AddInternal. 
            /// 
            internal Dictionary IdentityDictionary;
            internal List OrderedList;
 
            internal CollectionData()
            { 
                OrderedList = new List(); 
            }
 
            internal CollectionData(CollectionData original, int additionalCapacity)
            {
                this.OrderedList = new List(original.OrderedList.Count + additionalCapacity);
                foreach (T item in original.OrderedList) 
                {   // using AddRange results in a temporary memory allocation
                    this.OrderedList.Add(item); 
                } 

                if (UseSortedListCrossover <= this.OrderedList.Capacity) 
                {
                    this.IdentityDictionary = new Dictionary(this.OrderedList.Capacity, StringComparer.OrdinalIgnoreCase);

                    if (null != original.IdentityDictionary) 
                    {
                        foreach (KeyValuePair pair in original.IdentityDictionary) 
                        { 
                            this.IdentityDictionary.Add(pair.Key, pair.Value);
                        } 
                    }
                    else
                    {
                        for (int i = 0; i < this.OrderedList.Count; ++i) 
                        {
                            AddToDictionary(this, this.OrderedList[i].Identity, i, false); 
                        } 
                    }
                } 
            }
        }

        #endregion 
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
                        

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