SortedDictionary.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / CompMod / System / Collections / Generic / SortedDictionary.cs / 1305376 / SortedDictionary.cs

                            namespace System.Collections.Generic { 
    using System;
    using System.Diagnostics;
    using System.Diagnostics.CodeAnalysis;
    using System.Runtime.Serialization; 

    [Serializable] 
    [DebuggerTypeProxy(typeof(System_DictionaryDebugView<,>))] 
    [DebuggerDisplay("Count = {Count}")]
    public class SortedDictionary : IDictionary, IDictionary { 
        [NonSerialized]
        private KeyCollection keys;

        [NonSerialized] 
        private ValueCollection values;
 
        private TreeSet> _set; 

        public SortedDictionary() : this((IComparer)null) { 
        }

        public SortedDictionary(IDictionary dictionary) : this( dictionary, null) {
        } 

        public SortedDictionary(IDictionary dictionary, IComparer comparer) { 
            if( dictionary == null) { 
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
            } 

            _set = new TreeSet>(new KeyValuePairComparer(comparer));

            foreach(KeyValuePair pair in dictionary) { 
                _set.Add(pair);
            } 
        } 

        public SortedDictionary(IComparer comparer) { 
            _set = new TreeSet>(new KeyValuePairComparer(comparer));
        }

        void ICollection>.Add(KeyValuePair keyValuePair) { 
            _set.Add(keyValuePair);
        } 
 
        bool ICollection>.Contains(KeyValuePair keyValuePair) {
            TreeSet>.Node node = _set.FindNode(keyValuePair); 
            if ( node == null) {
                return false;
            }
 
            if( keyValuePair.Value == null) {
                return node.Item.Value == null; 
            } 
            else {
                return EqualityComparer.Default.Equals(node.Item.Value, keyValuePair.Value); 
            }
        }

        bool ICollection>.Remove(KeyValuePair keyValuePair) { 
            TreeSet>.Node node = _set.FindNode(keyValuePair);
            if ( node == null) { 
                return false; 
            }
 
            if( EqualityComparer.Default.Equals(node.Item.Value, keyValuePair.Value)) {
                _set.Remove(keyValuePair);
                return true;
            } 
            return false;
        } 
 
        bool ICollection>.IsReadOnly {
            get { 
                return false;
            }
        }
 
        public TValue this[TKey key] {
            get { 
                if ( key == null) { 
                    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
                } 

                TreeSet>.Node node = _set.FindNode(new KeyValuePair(key, default(TValue)));
                if ( node == null) {
                    ThrowHelper.ThrowKeyNotFoundException(); 
                }
 
                return node.Item.Value; 
            }
            set { 
                if( key == null) {
                    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
                }
 
                TreeSet>.Node node = _set.FindNode(new KeyValuePair(key, default(TValue)));
                if ( node == null) { 
                    _set.Add(new KeyValuePair(key, value)); 
                } else {
                    node.Item = new KeyValuePair( node.Item.Key, value); 
                    _set.UpdateVersion();
                }
            }
        } 

        public int Count { 
            get { 
                return _set.Count;
            } 
        }

        public IComparer Comparer {
            get { 
                return ((KeyValuePairComparer)_set.Comparer).keyComparer;
            } 
        } 

        public KeyCollection Keys { 
            get {
                if (keys == null) keys = new KeyCollection(this);
                return keys;
            } 
        }
 
        ICollection IDictionary.Keys { 
            get {
                return Keys; 
            }
        }

        public ValueCollection Values { 
            get {
                if (values == null) values = new ValueCollection(this); 
                return values; 
            }
        } 

        ICollection IDictionary.Values {
            get {
                return Values; 
            }
        } 
 
        public void Add(TKey key, TValue value) {
            if( key == null) { 
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
            _set.Add(new KeyValuePair(key, value));
        } 

        public void Clear() { 
            _set.Clear(); 
        }
 
        public bool ContainsKey(TKey key) {
            if( key == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            } 

            return _set.Contains(new KeyValuePair(key, default(TValue))); 
        } 

        public bool ContainsValue(TValue value) { 
            bool found = false;
            if( value == null) {
                _set.InOrderTreeWalk( delegate(TreeSet>.Node node) {
                                     if(node.Item.Value == null) { 
                                        found = true;
                                        return false;  // stop the walk 
                                     } 
                                     return true;
                                }); 

            }
            else {
                EqualityComparer valueComparer = EqualityComparer.Default; 
                _set.InOrderTreeWalk( delegate(TreeSet>.Node node) {
                                     if(valueComparer.Equals(node.Item.Value, value)) { 
                                        found = true; 
                                        return false;  // stop the walk
                                     } 
                                     return true;
                                });
            }
            return found; 
        }
 
        public void CopyTo(KeyValuePair[] array, int index) { 
            _set.CopyTo(array, index);
        } 

        public Enumerator GetEnumerator() {
            return new Enumerator(this, Enumerator.KeyValuePair);
        } 

        IEnumerator> IEnumerable>.GetEnumerator() { 
            return new Enumerator(this, Enumerator.KeyValuePair); 
        }
 
        public bool Remove(TKey key) {
            if( key == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            } 

            return _set.Remove(new KeyValuePair(key, default(TValue))); 
        } 

        public bool TryGetValue( TKey key, out TValue value) { 
            if( key == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
 
            TreeSet>.Node node = _set.FindNode(new KeyValuePair(key, default(TValue)));
            if ( node == null) { 
                value = default(TValue); 
                return false;
            } 
            value = node.Item.Value;
            return true;
        }
 
        void ICollection.CopyTo(Array array, int index) {
            ((ICollection)_set).CopyTo(array, index); 
        } 

        bool IDictionary.IsFixedSize { 
            get { return false; }
        }

        bool IDictionary.IsReadOnly { 
            get { return false; }
        } 
 
        ICollection IDictionary.Keys {
            get { return (ICollection)Keys; } 
        }

        ICollection IDictionary.Values {
            get { return (ICollection)Values; } 
        }
 
        object IDictionary.this[object key] { 
            get {
                if( IsCompatibleKey(key)) { 
                    TValue value;
                    if( TryGetValue((TKey)key, out value)) {
                        return value;
                    } 
                }
 
                return null; 
            }
            set { 
                if (key == null)
                {
                    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
                } 

                ThrowHelper.IfNullAndNullsAreIllegalThenThrow(value, ExceptionArgument.value); 
 
                try {
                    TKey tempKey = (TKey)key; 
                    try {
                        this[tempKey] = (TValue)value;
                    }
                    catch (InvalidCastException) { 
                        ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue));
                    } 
                } 
                catch (InvalidCastException) {
                    ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey)); 
                }
            }
        }
 
        void IDictionary.Add(object key, object value) {
            if (key == null) 
            { 
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            } 

            ThrowHelper.IfNullAndNullsAreIllegalThenThrow(value, ExceptionArgument.value);

            try { 
                TKey tempKey = (TKey)key;
 
                try { 
                    Add(tempKey, (TValue)value);
                } 
                catch (InvalidCastException) {
                    ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue));
                }
            } 
            catch (InvalidCastException) {
                ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey)); 
            } 
        }
 
        bool IDictionary.Contains(object key) {
            if(IsCompatibleKey(key)) {
                return ContainsKey((TKey)key);
            } 
            return false;
        } 
 
        private static bool IsCompatibleKey(object key) {
            if( key == null) { 
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }

            return (key is TKey); 
        }
 
        IDictionaryEnumerator IDictionary.GetEnumerator() { 
            return new Enumerator(this, Enumerator.DictEntry);
        } 

        void IDictionary.Remove(object key) {
            if(IsCompatibleKey(key))
            { 
                Remove((TKey)key);
            } 
        } 

        bool ICollection.IsSynchronized { 
            get { return false; }
        }

        object ICollection.SyncRoot { 
            get { return ((ICollection)_set).SyncRoot; }
        } 
 
        IEnumerator IEnumerable.GetEnumerator() {
            return new Enumerator(this, Enumerator.KeyValuePair); 
        }

        [SuppressMessage("Microsoft.Performance", "CA1815:OverrideEqualsAndOperatorEqualsOnValueTypes", Justification = "not an expected scenario")]
        public struct Enumerator : IEnumerator>, IDictionaryEnumerator { 
            private TreeSet>.Enumerator treeEnum;
            private int getEnumeratorRetType;  // What should Enumerator.Current return? 
 
            internal const int KeyValuePair = 1;
            internal const int DictEntry = 2; 

            internal Enumerator(SortedDictionary dictionary, int getEnumeratorRetType) {
                treeEnum = dictionary._set.GetEnumerator();
                this.getEnumeratorRetType = getEnumeratorRetType; 
            }
 
            public bool MoveNext() { 
                return treeEnum.MoveNext();
            } 

            public void Dispose() {
                treeEnum.Dispose();
            } 

            public KeyValuePair Current { 
                get { 
                    return treeEnum.Current;
                } 
            }

            internal bool NotStartedOrEnded {
                get { 
                    return treeEnum.NotStartedOrEnded;
                } 
            } 

            internal void Reset() { 
                treeEnum.Reset();
            }

 
            void IEnumerator.Reset() {
                treeEnum.Reset(); 
            } 

            object IEnumerator.Current { 
                get {
                    if( NotStartedOrEnded) {
                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
                    } 

                    if (getEnumeratorRetType == DictEntry) { 
                        return new DictionaryEntry(Current.Key, Current.Value); 
                    } else {
                        return new KeyValuePair(Current.Key, Current.Value);			 
                    }		

                }
            } 

            object IDictionaryEnumerator.Key { 
                get { 
                    if(NotStartedOrEnded) {
                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); 
                    }

                    return Current.Key;
                } 
            }
 
            object IDictionaryEnumerator.Value { 
                get {
                    if(NotStartedOrEnded) { 
                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
                    }

                    return Current.Value; 
                }
            } 
 
            DictionaryEntry IDictionaryEnumerator.Entry {
                get { 
                    if(NotStartedOrEnded) {
                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
                    }
 
                    return new DictionaryEntry(Current.Key, Current.Value);
                } 
            } 
        }
 
        [DebuggerTypeProxy(typeof(System_DictionaryKeyCollectionDebugView<,>))]
        [DebuggerDisplay("Count = {Count}")]
        [Serializable]
        public sealed class KeyCollection: ICollection, ICollection { 
            private SortedDictionary dictionary;
 
            public KeyCollection(SortedDictionary dictionary) { 
                if (dictionary == null) {
                    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); 
                }
                this.dictionary = dictionary;
            }
 
            public Enumerator GetEnumerator() {
                return new Enumerator(dictionary); 
            } 

            IEnumerator IEnumerable.GetEnumerator() { 
                return new Enumerator(dictionary);
            }

            IEnumerator IEnumerable.GetEnumerator() { 
                return new Enumerator(dictionary);
            } 
 
            public void CopyTo(TKey[] array, int index) {
                if (array == null) { 
                    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
                }

                if (index < 0) { 
                    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index);
                } 
 
                if (array.Length - index < Count) {
                    ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); 
                }

                dictionary._set.InOrderTreeWalk( delegate(TreeSet>.Node node){ array[index++] = node.Item.Key; return true;});
            } 

            void ICollection.CopyTo(Array array, int index) { 
                if (array==null) { 
                    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
                } 

                if (array.Rank != 1) {
                    ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
                } 

                if( array.GetLowerBound(0) != 0 ) { 
                    ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); 
                }
 
                if (index < 0 ) {
                    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
                }
 
                if (array.Length - index < dictionary.Count) {
                    ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); 
                } 

                TKey[] keys = array as TKey[]; 
                if (keys != null) {
                    CopyTo(keys, index);
                }
                else { 
                    object[] objects = (object[])array;
                    if (objects == null) { 
                        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); 
                    }
 
                    try {
                        dictionary._set.InOrderTreeWalk( delegate(TreeSet>.Node node){ objects[index++] = node.Item.Key; return true;});
                    }
                    catch(ArrayTypeMismatchException) { 
                        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
                    } 
                } 
            }
 
            public int Count {
                get { return dictionary.Count;}
            }
 
            bool ICollection.IsReadOnly {
                get { return true;} 
            } 

            void ICollection.Add(TKey item){ 
                ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
            }

            void ICollection.Clear(){ 
                ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
            } 
 
            bool ICollection.Contains(TKey item){
                return dictionary.ContainsKey(item); 
            }

            bool ICollection.Remove(TKey item){
                ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet); 
                return false;
            } 
 
            bool ICollection.IsSynchronized {
                get { return false; } 
            }

            Object ICollection.SyncRoot {
                get { return ((ICollection)dictionary).SyncRoot; } 
            }
 
            [SuppressMessage("Microsoft.Performance", "CA1815:OverrideEqualsAndOperatorEqualsOnValueTypes", Justification = "not an expected scenario")] 
            public struct Enumerator : IEnumerator, IEnumerator {
                private SortedDictionary.Enumerator dictEnum; 

                internal Enumerator(SortedDictionary dictionary) {
                    dictEnum = dictionary.GetEnumerator();
                } 

                public void Dispose() { 
                    dictEnum.Dispose(); 
                }
 
                public bool MoveNext() {
                    return dictEnum.MoveNext();
                }
 
                public TKey Current {
                    get { 
                        return dictEnum.Current.Key; 
                    }
                } 

                object IEnumerator.Current {
                    get {
                        if( dictEnum.NotStartedOrEnded) { 
                             ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
                        } 
 
                        return Current;
                    } 
                }

                void IEnumerator.Reset() {
                    dictEnum.Reset(); 
                }
 
            } 
        }
 
        [DebuggerTypeProxy(typeof(System_DictionaryValueCollectionDebugView<,>))]
        [DebuggerDisplay("Count = {Count}")]
        [Serializable]
        public sealed class ValueCollection: ICollection, ICollection { 
            private SortedDictionary dictionary;
 
            public ValueCollection(SortedDictionary dictionary) { 
                if (dictionary == null) {
                    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); 
                }
                this.dictionary = dictionary;
            }
 
            public Enumerator GetEnumerator() {
                return new Enumerator(dictionary); 
            } 

            IEnumerator IEnumerable.GetEnumerator() { 
                return new Enumerator(dictionary);
            }

            IEnumerator IEnumerable.GetEnumerator() { 
                return new Enumerator(dictionary);
            } 
 
            public void CopyTo(TValue[] array, int index) {
                if (array == null) { 
                    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
                }

                if (index < 0 ) { 
                    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index);
                } 
 
                if (array.Length - index < Count) {
                    ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); 
                }

                dictionary._set.InOrderTreeWalk( delegate(TreeSet>.Node node){ array[index++] = node.Item.Value; return true;});
            } 

            void ICollection.CopyTo(Array array, int index) { 
                if (array==null) { 
                    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
                } 

                if (array.Rank != 1) {
                    ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
                } 

                if( array.GetLowerBound(0) != 0 ) { 
                    ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); 
                }
 
                if (index < 0) {
                    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
                }
 
                if (array.Length - index < dictionary.Count) {
                    ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); 
                } 

                TValue[] values = array as TValue[]; 
                if (values != null) {
                    CopyTo(values, index);
                }
                else { 
                    object[] objects = (object[])array;
                    if (objects == null) { 
                        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); 
                    }
 
                    try {
                        dictionary._set.InOrderTreeWalk( delegate(TreeSet>.Node node){ objects[index++] = node.Item.Value; return true;});
                    }
                    catch(ArrayTypeMismatchException) { 
                        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
                    } 
                } 
            }
 
            public int Count {
                get { return dictionary.Count;}
            }
 
            bool ICollection.IsReadOnly {
                get { return true;} 
            } 

            void ICollection.Add(TValue item){ 
                ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet);
            }

            void ICollection.Clear(){ 
                ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet);
            } 
 
            bool ICollection.Contains(TValue item){
                return dictionary.ContainsValue(item); 
            }

            bool ICollection.Remove(TValue item){
                ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet); 
                return false;
            } 
 
            bool ICollection.IsSynchronized {
                get { return false; } 
            }

            Object ICollection.SyncRoot {
                get { return ((ICollection)dictionary).SyncRoot; } 
            }
 
            [SuppressMessage("Microsoft.Performance", "CA1815:OverrideEqualsAndOperatorEqualsOnValueTypes", Justification = "not an expected scenario")] 
            public struct Enumerator : IEnumerator, IEnumerator {
                private SortedDictionary.Enumerator dictEnum; 

                internal Enumerator(SortedDictionary dictionary) {
                    dictEnum = dictionary.GetEnumerator();
                } 

                public void Dispose() { 
                    dictEnum.Dispose(); 
                }
 
                public bool MoveNext() {
                    return dictEnum.MoveNext();
                }
 
                public TValue Current {
                    get { 
                        return dictEnum.Current.Value; 
                    }
                } 

                object IEnumerator.Current {
                    get {
                        if( dictEnum.NotStartedOrEnded) { 
                             ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
                        } 
 
                        return Current;
                    } 
                }

                void IEnumerator.Reset() {
                    dictEnum.Reset(); 
                }
            } 
        } 

        [Serializable] 
        internal class KeyValuePairComparer : Comparer> {
            internal IComparer keyComparer;

            public KeyValuePairComparer(IComparer keyComparer) { 
                if ( keyComparer == null) {
                    this.keyComparer = Comparer.Default; 
                } else { 
                    this.keyComparer = keyComparer;
                } 
            }

            public  override int Compare( KeyValuePair x, KeyValuePair y) {
                return keyComparer.Compare(x.Key, y.Key); 
            }
        } 
    } 

 

    /// 
    /// This class is intended as a helper for backwards compatibility with existing SortedDictionaries.
    /// TreeSet has been converted into SortedSet, which will be exposed publicly. SortedDictionaries 
    /// have the problem where they have already been serialized to disk as having a backing class named
    /// TreeSet. To ensure that we can read back anything that has already been written to disk, we need to 
    /// make sure that we have a class named TreeSet that does everything the way it used to. 
    ///
    /// The only thing that makes it different from SortedSet is that it throws on duplicates 
    /// 
    /// 
    [Serializable]
    internal class TreeSet : SortedSet { 

        public TreeSet() 
            : base() { } 

        public TreeSet(IComparer comparer) : base(comparer) { } 

        public TreeSet(ICollection collection) : base(collection) { }

        public TreeSet(ICollection collection, IComparer comparer) : base(collection, comparer) { } 

        public TreeSet(SerializationInfo siInfo, StreamingContext context) : base(siInfo, context) { } 
 
        internal override bool AddIfNotPresent(T item) {
            bool ret = base.AddIfNotPresent(item); 
            if (!ret) {
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
            }
            return ret; 
        }
 
    } 

} 

// 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