* corlib.dll.sources: IEqualityComparer, etc

[mono.git] / mcs / class / corlib / System.Collections.Generic / Dictionary.cs

//
// System.Collections.Generic.Dictionary
//
// Authors:
//      Sureshkumar T (tsureshkumar@novell.com)
//      Marek Safar (marek.safar@seznam.cz) (stubs)
//      Ankit Jain (radical@corewars.org)
//
//
//
// Copyright (C) 2004 Novell, Inc (http://www.novell.com)
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
// 
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//

#if NET_2_0

using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.Serialization;


namespace System.Collections.Generic {

        [Serializable]
        public class Dictionary<TKey, TValue> : IDictionary<TKey, TValue>,
                IDictionary,
                ICollection,
                IEnumerable,
                ISerializable,
                IDeserializationCallback
        {
                const int INITIAL_SIZE = 10;
                const float DEFAULT_LOAD_FACTOR = (90f / 100);

                [Serializable]
                internal class Slot {
                        public TKey Key;
                        public TValue Value;
                        public Slot next;
                        public Slot (TKey Key, TValue Value, Slot next)
                        {
                                this.Key = Key;
                                this.Value = Value;
                                this.next = next;
                        }
                }
        
                Slot [] _table;
        
                int _usedSlots;
                float _loadFactor = DEFAULT_LOAD_FACTOR;
        
                IEqualityComparer<TKey> _hcp;
        
                uint _threshold;
        
                public int Count {
                        get { return _usedSlots; }
                }

                public TValue this [TKey key] {
                        get {
                                int index = GetSlot (key);
                                if (index < 0)
                                        throw new KeyNotFoundException ();
                                return _table [index].Value;
                        }
                        
                        set {
                                int index = GetSlot (key);
                                if (index < 0)
                                        DoAdd (index, key, value);
                                else
                                        _table [index].Value = value;
                        }
                }
        
                public Dictionary ()
                {
                        Init ();
                }
        
                public Dictionary (IEqualityComparer<TKey> comparer)
                {
                        Init (INITIAL_SIZE, comparer, DEFAULT_LOAD_FACTOR);
                }
        
                public Dictionary (IDictionary<TKey, TValue> dictionary)
                        : this (dictionary, null)
                {
                }
        
                public Dictionary (int capacity)
                {
                        Init (capacity);
                }
        
                public Dictionary (float loadFactor)
                {
                        Init (loadFactor);
                }
        
                public Dictionary (IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer)
                {
                        if (dictionary == null)
                                throw new ArgumentNullException ("dictionary");
                        int capacity = dictionary.Count;
                        Init (capacity, comparer, DEFAULT_LOAD_FACTOR);
                        foreach (KeyValuePair<TKey, TValue> entry in dictionary) {
                                this.Add (entry.Key, entry.Value);
                        }
                }
        
                public Dictionary (int capacity, IEqualityComparer<TKey> comparer)
                {
                        Init (capacity, comparer, DEFAULT_LOAD_FACTOR);
                }
        
                protected Dictionary (SerializationInfo info, StreamingContext context)
                {
                        Init ();
                }
        
                void Init ()
                {
                        Init (INITIAL_SIZE, null, DEFAULT_LOAD_FACTOR);
                }
        
                void Init (int capacity)
                {
                        Init (capacity, null, DEFAULT_LOAD_FACTOR);
                }
        
                void Init (float loadFactor)
                {
                        Init (INITIAL_SIZE, null, loadFactor);
                }
                
                protected void Init (int capacity, IEqualityComparer<TKey> hcp, float loadFactor)
                {
                        if (capacity < 0)
                                throw new ArgumentOutOfRangeException ("capacity");
                        this._hcp = hcp;
                        _table = new Slot [capacity];
                        _loadFactor = loadFactor;
                        _threshold = (uint) (capacity * _loadFactor);
                        if (_threshold == 0 && capacity > 0)
                                _threshold = 1;
                }
        
                ICollection<TValue> GetValues ()
                {
                        return ((IDictionary<TKey, TValue>) this).Values;
                }
        
                ICollection<TKey> GetKeys ()
                {
                        return ((IDictionary<TKey, TValue>) this).Keys;
                }
        
        
                void CopyTo (KeyValuePair<TKey, TValue> [] array, int index)
                {
                        if (array == null)
                                throw new ArgumentNullException ("array");
                        if (index < 0)
                                throw new ArgumentOutOfRangeException ("index");
                        if (index >= array.Length)
                                throw new ArgumentException ("index larger than largest valid index of array");
                        if (array.Length - index < _usedSlots)
                                throw new ArgumentException ("Destination array cannot hold the requested elements!");
                        
                        foreach (KeyValuePair<TKey, TValue> kv in this)
                                array [index++] = kv;
                }
        
                protected void Resize ()
                {
                        // From the SDK docs:
                        //       Hashtable is automatically increased
                        //       to the smallest prime number that is larger
                        //       than twice the current number of Hashtable buckets
                        uint newSize = (uint) ToPrime ((_table.Length << 1) | 1);

                        _threshold = (uint) (newSize * _loadFactor);
                        if (_threshold == 0 && newSize > 0)
                                _threshold = 1;
                
                        Slot nextslot = null;
                        Slot [] oldTable = _table;
                        
                        _table = new Slot [newSize];

                        int index;
                        for (int i = 0; i < oldTable.Length; i++) {
                                for (Slot slot = oldTable [i]; slot != null; slot = nextslot) {
                                        nextslot = slot.next;

                                        index = DoHash (slot.Key);
                                        slot.next = _table [index];
                                        _table [index] = slot;
                                }
                        }
                }

                protected virtual int GetHash (TKey key)
                {
                        //IEqualityComparer<K> hcp = this._hcp;
                        
                        return key.GetHashCode ();
                        /*
                        return (hcp != null)
                        ? hcp.GetHashCode (key)
                        : key.GetHashCode ();
                        */
                }
        
                public void Add (TKey key, TValue value)
                {
                        int index = GetSlot (key);
                        if (index >= 0)
                                throw new ArgumentException ("An element with the same key already exists in the dictionary.");

                        DoAdd (index, key, value);
                }

                void DoAdd (int negated_index, TKey key, TValue value)
                {
                        int index = -negated_index - 1;

                        if (_usedSlots >= _threshold) {
                                Resize ();
                                index = DoHash (key);
                        }

                        _table [index] = new Slot (key, value, _table [index]);
                        ++_usedSlots;
                }
        
                protected int DoHash (TKey key)
                {
                        if (key == null)
                                throw new ArgumentNullException ("key", "null key");
        
                        int size = this._table.Length;
                        int h = this.GetHash (key) & Int32.MaxValue;
                        //Console.WriteLine ("Hashvalue for key {0} is {1}", key.ToString (), h);
                        int spot = (int) ((uint) h % size);
                        return spot;
                }

                public IEqualityComparer<TKey> Comparer {
                        get {
                                return _hcp;
                        }
                }
                
                public void Clear ()
                {
                        for (int i = 0; i < _table.Length; i++)
                                _table [i] = null;
                        _usedSlots = 0;
                }
        
                public bool ContainsKey (TKey key)
                {
                        return GetSlot (key) >= 0;
                }
        
                public bool ContainsValue (TValue value)
                {
                        foreach (TValue v in ((IDictionary) this).Values) {
                                if (v.Equals (value))
                                        return true;
                        }
                        return false;
                }
        
                public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
                {
                        throw new NotImplementedException ();
                }
        
                public virtual void OnDeserialization (object sender)
                {
                        throw new NotImplementedException ();
                }
        
                public bool Remove (TKey key)
                {
                        int index = GetSlot (key);

                        if (index < 0)
                                return false;

                        // If GetSlot returns a valid index, the given key is at the head of the chain.
                        _table [index] = _table [index].next;
                        --_usedSlots;
                        return true;
                }

                //
                // Returns the index of the chain containing key.  Also ensures that the found key is the first element of the chain.
                // If the key is not found, returns -h-1, where 'h' is the index of the chain that would've contained the key.
                // 
                internal int GetSlot (TKey key)
                {
                        if (key == null)
                                throw new ArgumentNullException ("key");
                        int index = DoHash (key);
                        Slot slot = _table [index];
                        Slot prev = null;

                        while (slot != null && !slot.Key.Equals (key)) {
                                prev = slot;
                                slot = slot.next;
                        }
        
                        if (slot == null)
                                return - index - 1;
        
                        if (prev != null) {
                                // Move to the head of the list
                                prev.next = slot.next;
                                slot.next = _table [index];
                                _table [index] = slot;
                        }

                        return index;
                }
        
                public bool TryGetValue (TKey key, out TValue value)
                {
                        int index = GetSlot (key);
                        bool found = index >= 0;
                        value = found ? _table [index].Value : default (TValue);
                        return found;
                }
        
                ICollection<TKey> IDictionary<TKey, TValue>.Keys {
                        get {
                                return Keys;
                        }
                }
        
                ICollection<TValue> IDictionary<TKey, TValue>.Values {
                        get {
                                return Values;
                        }
                }

                public KeyCollection Keys {
                        get {
                                return new KeyCollection (this);
                        }
                }

                public ValueCollection Values {
                        get {
                                return new ValueCollection (this);
                        }
                }
                
                bool IDictionary.IsFixedSize {
                        get { return false; }
                }
                
                bool IDictionary.IsReadOnly {
                        get { return false; }
                }
                
                object IDictionary.this [object key] {
                        get {
                                if (!(key is TKey))
                                        throw new ArgumentException ("key is of not '" + typeof (TKey).ToString () + "'!");
                                return this [(TKey) key];
                        }
                        set { this [(TKey) key] = (TValue) value; }
                }
                ICollection IDictionary.Keys
                {
                        get { return ((IDictionary<TKey, TValue>) this).Keys as ICollection; }
                }
                ICollection IDictionary.Values
                {
                        get { return ((IDictionary<TKey, TValue>) this).Values as ICollection; }
                }
        
                void IDictionary.Add (object key, object value)
                {
                        if (!(key is TKey))
                                throw new ArgumentException ("key is of not '" + typeof (TKey).ToString () + "'!");
                        if (!(value is TValue))
                                throw new ArgumentException ("value is of not '" + typeof (TValue).ToString () + "'!");
                        this.Add ((TKey) key, (TValue) value);
                }
        
                bool IDictionary.Contains (object key)
                {
                        return ContainsKey ((TKey) key);
                }
        
                void IDictionary.Remove (object key)
                {
                        Remove ((TKey) key);
                }
        
                bool ICollection.IsSynchronized {
                        get { return false; }
                }
                object ICollection.SyncRoot {
                        get { return this; }
                }
        
                bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
                        get { return false; }
                }
        
                void ICollection<KeyValuePair<TKey, TValue>>.Add (KeyValuePair<TKey, TValue> keyValuePair)
                {
                        Add (keyValuePair.Key, keyValuePair.Value);
                }
        
                bool ICollection<KeyValuePair<TKey, TValue>>.Contains (KeyValuePair<TKey, TValue> keyValuePair)
                {
                        return this.ContainsKey (keyValuePair.Key);
                }
        
                void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue> [] array, int index)
                {
                        CopyTo (array, index);
                }
        
                bool ICollection<KeyValuePair<TKey, TValue>>.Remove (KeyValuePair<TKey, TValue> keyValuePair)
                {
                        return Remove (keyValuePair.Key);
                }
        
        
                void ICollection.CopyTo (Array array, int index)
                {
                        CopyTo ((KeyValuePair<TKey, TValue> []) array, index);
                }
        
                IEnumerator IEnumerable.GetEnumerator ()
                {
                        return new Enumerator (this, EnumerationMode.DictionaryEntry);
                }
        
                IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator ()
                {
                        return new Enumerator (this);
                }
        
                /**
                 * This is to make the gmcs compiler errror silent
                 */
        //                         IEnumerator<TKey> IEnumerable<K>.GetEnumerator ()
        //                         {
        //                                         throw new NotImplementedException ();
        //                         }
        
        
                IDictionaryEnumerator IDictionary.GetEnumerator ()
                {
                        return new Enumerator (this, EnumerationMode.DictionaryEntry);
                }
        
                public Enumerator GetEnumerator ()
                {
                        return new Enumerator (this, EnumerationMode.KeyValuePair);
                }
        
                public enum EnumerationMode { Key, Value, DictionaryEntry, KeyValuePair };
        
                [Serializable]
                public struct Enumerator : IEnumerator<KeyValuePair<TKey,TValue>>,
                        IDisposable, IDictionaryEnumerator, IEnumerator
                {
                        Dictionary<TKey, TValue> _dictionary;
                        Slot _current;
                        int _index;
                        int _validNodeVisited;
                        bool _isValid;
                        EnumerationMode _navigationMode;
        
        
        
                        public Enumerator (Dictionary<TKey, TValue> dictionary) : this (dictionary, EnumerationMode.KeyValuePair)
                        {
                        }
        
                        public Enumerator (Dictionary<TKey, TValue> dictionary, EnumerationMode mode)
                        {
                                _index = 0;
                                _current = null;
                                _validNodeVisited = 0;
                                _dictionary = dictionary;
                                _isValid = false;
                                _navigationMode = mode;
                        }
        
                        public bool MoveNext ()
                        {
                                if (_validNodeVisited == _dictionary.Count)
                                        return (_isValid = false);
        
                                while (_index < _dictionary._table.Length) {
                                        if (_current == null)
                                                _current = _dictionary._table [_index++];
                                        else
                                                _current = _current.next;
        
                                        if (_current != null) {
                                                ++_validNodeVisited;
                                                return (_isValid = true);
                                        }
                                }
        
                                return (_isValid = false);
                        }
        
                        public KeyValuePair<TKey, TValue> Current {
                                get {
                                        if (!_isValid) throw new InvalidOperationException ();
                                        KeyValuePair<TKey, TValue> kv = new KeyValuePair<TKey, TValue> (_current.Key, _current.Value);
                                        return kv;
                                }
                        }
        
                        object IEnumerator.Current {
                                get {
                                        if (!_isValid) throw new InvalidOperationException ();
                                        switch (_navigationMode) {
                                        case EnumerationMode.Key:
                                                return _current.Key as object;
                                        case EnumerationMode.Value:
                                                return _current.Value as object;
                                        case EnumerationMode.DictionaryEntry:
                                                DictionaryEntry de = new DictionaryEntry (_current.Key, _current.Value);
                                                return de as object;
                                        case EnumerationMode.KeyValuePair:
                                        default:
                                                KeyValuePair<TKey, TValue> kv = new KeyValuePair<TKey, TValue> (_current.Key, _current.Value);
                                                return kv as object;
                                        }
                                }
                        }
        
                        DictionaryEntry IDictionaryEnumerator.Entry
                        {
                                get
                                {
                                        if (!_isValid) throw new InvalidOperationException ();
                                        DictionaryEntry entry = new DictionaryEntry (_current.Key, _current.Value);
                                        return entry;
                                }
                        }
        
                        void IEnumerator.Reset ()
                        {
                                _index = 0;
                                _current = null;
                                _isValid = false;
                                _validNodeVisited = 0;
                        }
        
                        object IDictionaryEnumerator.Key
                        {
                                get
                                {
                                        if (!_isValid) throw new InvalidOperationException ();
                                        return _current.Key;
                                }
                        }
                        object IDictionaryEnumerator.Value
                        {
                                get
                                {
                                        if (!_isValid) throw new InvalidOperationException ();
                                        return _current.Value;
                                }
                        }
        
                        public void Dispose ()
                        {
        
                        }
                }
        
                // This collection is a read only collection
                public class KeyCollection : ICollection<TKey>, ICollection {
                        Dictionary<TKey, TValue> _dictionary;
        
                        public KeyCollection (Dictionary<TKey, TValue> dictionary)
                        {
                                _dictionary = dictionary;
                        }
        
                        void ICollection<TKey>.Add (TKey item)
                        {
                                throw new InvalidOperationException ();
                        }
        
                        void ICollection<TKey>.Clear ()
                        {
                                throw new InvalidOperationException ();
                        }
        
                        bool ICollection<TKey>.Contains (TKey item)
                        {
                                return _dictionary.ContainsKey (item);
                        }
        
                        bool ICollection<TKey>.Remove (TKey item)
                        {
                                throw new InvalidOperationException ();
                        }
        
                        void ICollection.CopyTo (Array array, int index)
                        {
                                CopyTo ((TKey []) array, index);
                        }
        
                        public void CopyTo (TKey [] array, int index)
                        {
                                if (array == null)
                                        throw new ArgumentNullException ("array");
                                if (index < 0)
                                        throw new ArgumentOutOfRangeException ("index");
                                if (index >= array.Length)
                                        throw new ArgumentException ("index larger than largest valid index of array");
                                if (array.Length - index < _dictionary._usedSlots)
                                        throw new ArgumentException ("Destination array cannot hold the requested elements!");

                                IEnumerable<TKey> enumerateThis = (IEnumerable<TKey>) this;
                                foreach (TKey k in enumerateThis) {
                                        array [index++] = k;
                                }
                        }
        
                        public Enumerator GetEnumerator ()
                        {
                                return new Enumerator (_dictionary);
                        }
        
                        IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator ()
                        {
                                return new KeyEnumerator (_dictionary);
                        }
        
                        IEnumerator IEnumerable.GetEnumerator ()
                        {
                                return new Enumerator (_dictionary, EnumerationMode.Key);
                        }
        
        
                        bool ICollection<TKey>.IsReadOnly { get { return ((IDictionary) _dictionary).IsReadOnly; } }
                        public int Count { get { return _dictionary.Count; } }
                        bool ICollection.IsSynchronized { get { return ((IDictionary) _dictionary).IsSynchronized; } }
                        object ICollection.SyncRoot { get { return ((IDictionary) _dictionary).SyncRoot; } }
        
                        public struct KeyEnumerator : IEnumerator<TKey>, IDisposable, IEnumerator {
                                IEnumerator _hostEnumerator;
                                internal KeyEnumerator (Dictionary<TKey, TValue> dictionary)
                                {
                                        _hostEnumerator = new Enumerator (dictionary, EnumerationMode.Key);
                                }
                                
                                public void Dispose ()
                                {
                                }
                                
                                public bool MoveNext ()
                                {
                                        return _hostEnumerator.MoveNext ();
                                }
                                
                                public TKey Current {
                                        get {
                                                return (TKey) _hostEnumerator.Current;
                                        }
                                }
                                
                                object IEnumerator.Current {
                                        get {
                                                return _hostEnumerator.Current;
                                        }
                                }
                                
                                void IEnumerator.Reset ()
                                {
                                        _hostEnumerator.Reset ();
                                }
                        }
                }
        
                // This collection is a read only collection
                public class ValueCollection : ICollection<TValue>, ICollection {
                        Dictionary<TKey, TValue> _dictionary;
        
                        public ValueCollection (Dictionary<TKey, TValue> dictionary)
                        {
                                _dictionary = dictionary;
                        }
        
                        void ICollection<TValue>.Add (TValue item)
                        {
                                throw new InvalidOperationException ();
                        }
        
                        void ICollection<TValue>.Clear ()
                        {
                                throw new InvalidOperationException ();
                        }
        
                        bool ICollection<TValue>.Contains (TValue item)
                        {
                                return _dictionary.ContainsValue (item);
                        }
        
                        bool ICollection<TValue>.Remove (TValue item)
                        {
                                throw new InvalidOperationException ();
                        }
        
                        void ICollection.CopyTo (Array array, int index)
                        {
                                CopyTo ((TValue []) array, index);
                        }
        
                        public void CopyTo (TValue [] array, int index)
                        {
                                if (array == null)
                                        throw new ArgumentNullException ("array");
                                if (index < 0)
                                        throw new ArgumentOutOfRangeException ("index");
                                if (index >= array.Length)
                                        throw new ArgumentException ("index larger than largest valid index of array");
                                if (array.Length - index < _dictionary._usedSlots)
                                        throw new ArgumentException ("Destination array cannot hold the requested elements!");

                                IEnumerable<TValue> enumerateThis = (IEnumerable<TValue>) this;
                                foreach (TValue v in enumerateThis) {
                                        array [index++] = v;
                                }
                        }
        
                        public Enumerator GetEnumerator ()
                        {
                                return new Enumerator (_dictionary);
                        }
        
                        IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator ()
                        {
                                return new ValueEnumerator (_dictionary);
                        }
        
                        IEnumerator IEnumerable.GetEnumerator ()
                        {
                                return new Enumerator (_dictionary, EnumerationMode.Value);
                        }
        
        
                        bool ICollection<TValue>.IsReadOnly { get { return ((IDictionary) _dictionary).IsReadOnly; } }
                        public int Count { get { return _dictionary.Count; } }
                        bool ICollection.IsSynchronized { get { return ((IDictionary) _dictionary).IsSynchronized; } }
                        object ICollection.SyncRoot { get { return ((IDictionary) _dictionary).SyncRoot; } }
        
                        public struct ValueEnumerator : IEnumerator<TValue>
                        {
                                IEnumerator _hostEnumerator;
                                internal ValueEnumerator (Dictionary<TKey, TValue> dictionary)
                                {
                                        _hostEnumerator = new Enumerator (dictionary, EnumerationMode.Value);
                                }
                                
                                public void Dispose ()
                                {
                                }
                                
                                public bool MoveNext ()
                                {
                                        return _hostEnumerator.MoveNext ();
                                }
                                
                                public TValue Current {
                                        get {
                                                return (TValue) _hostEnumerator.Current;
                                        }
                                }
                                
                                object IEnumerator.Current {
                                        get {
                                                return _hostEnumerator.Current;
                                        }
                                }
                                
                                void IEnumerator.Reset ()
                                {
                                        _hostEnumerator.Reset ();
                                }
        
                        }
                }
        
                static bool TestPrime (int x)
                {
                        if ((x & 1) != 0) {
                                for (int n = 3; n < (int) Math.Sqrt (x); n += 2) {
                                        if ((x % n) == 0)
                                                return false;
                                }
                                return true;
                        }
                        // There is only one even prime - 2.
                        return (x == 2);
                }
        
                static int CalcPrime (int x)
                {
                        for (int i = (x & (~1)) - 1; i < Int32.MaxValue; i += 2) {
                                if (TestPrime (i)) return i;
                        }
                        return x;
                }
        
                static int ToPrime (int x)
                {
                        for (int i = 0; i < primeTbl.Length; i++) {
                                if (x <= primeTbl [i])
                                        return primeTbl [i];
                        }
                        return CalcPrime (x);
                }
        
                static readonly int [] primeTbl = {
                        11,
                        19,
                        37,
                        73,
                        109,
                        163,
                        251,
                        367,
                        557,
                        823,
                        1237,
                        1861,
                        2777,
                        4177,
                        6247,
                        9371,
                        14057,
                        21089,
                        31627,
                        47431,
                        71143,
                        106721,
                        160073,
                        240101,
                        360163,
                        540217,
                        810343,
                        1215497,
                        1823231,
                        2734867,
                        4102283,
                        6153409,
                        9230113,
                        13845163
                };
        }
}
#endif