+2008-04-29 Juraj Skripsky <js@hotfeet.ch>
+
+ * Dictionary.cs (Clear, Remove): Clear empty slots in keySlots
+ and valueSlots. Otherwise the garbage collector cannot reclaim
+ the referenced key/value. Fixes bug #384723.
+
+2008-04-02 Andreas Nahr <ClassDevelopment@A-SoftTech.com>
+
+ * KeyNotFoundException.cs
+ * KeyValuePair.cs: Fix parameter names
+
+2008-03-21 Sebastien Pouliot <sebastien@ximian.com>
+
+ * EqualityComparer.cs: Add null checks in GetHashCode. Fix bug
+ #372892
+
+2007-11-05 Sebastien Pouliot <sebastien@ximian.com>
+
+ * Dictionary.cs: Ensure that the non-generic CopyTo works on Array.
+ Fix #322783
+
+2007-10-31 Miguel de Icaza <miguel@novell.com>
+
+ * Dictionary.cs: Do not increment curTableItem when we return
+ false. Was not necessary, just a defensive move.
+
+2007-10-10 Juraj Skripsky <js@hotfeet.ch>
+
+ * Dictionary.cs (Enumerator.MoveNext): Handle the case where we
+ had already reached the end. Fixes bug #332534.
+
+2007-08-20 Jb Evain <jbevain@novell.com>
+
+ * List.cs (AddCollection): return early if the collection
+ to be added is empty.
+
+2007-08-08 Atsushi Enomoto <atsushi@ximian.com>
+
+ * Dictionary.cs : [Comvisible(true)]->[ComVisible(false)].
+
+2007-06-23 Marek Safar <marek.safar@gmail.com>
+
+ * List.cs: Make CheckMatch static.
+
+2007-06-20 Juraj Skripsky <js@hotfeet.ch>
+
+ * Dictionary.cs: Optimize and add implementation notes. Use a "mini-heap"
+ to store the linked lists instead of the regular heap. Split arrays of
+ structs into separate arrays to make the GC's life simpler (see bug 81879
+ for details). Make class serialization compatible with MS.NET.
+
+ * EqualityComparer.cs: Rename IEquatableOfTEqualityComparer<T> to
+ GenericEqualityComparer<T> to fix binary serialization compatibility
+ with MS.
+
+2006-04-16 Jonathan Chambers <joncham@gmail.com>
+
+ * List.cs: Clear entry in RemoveAt after removing item.
+ Fixes bug #81387.
+
+2007-03-27 Alan McGovern <alan.mcgovern@gmail.com>
+
+ * List.cs: Optimized several methods to increase performance
+
+2007-03-21 Juraj Skripsky <js@hotfeet.ch>
+
+ * List.cs (FindAllStackBits): Small optimization to the new code.
+ Built resulting List<T> directly as an array, wrap it in a List<T>
+ afterwards. Stop the filling of the result array as soon as all
+ matching items have been processed.
+
+2007-03-20 Juan Cristóbal Olivares <juancri@gmail.com>
+
+ * List.cs (FindAll): Optimize FindAll using a bitmask to determine
+ the number of positive matches, this increases the performance in
+ all cases below 10,000,000 elements extensively:
+
+ 100 elements:
+ old method: 00:00:00.0126610 (26x)
+ stackalloc bit method: 00:00:00.0004750 (1x)
+ array bit method: 00:00:00.0010700 (2x)
+ heap bit method: 00:00:00.0038830 (8x)
+
+ 1,000 elements:
+ old method: 00:00:00.0139250 (24x)
+ stackalloc bit method: 00:00:00.0005670 (1x)
+ array bit method: 00:00:00.0010890 (2x)
+ heap bit method: 00:00:00.0034920 (6x)
+
+ 10,000 elements:
+ old method: 00:00:00.0136110 (12x)
+ stackalloc bit method: 00:00:00.0011240 (1x)
+ array bit method: 00:00:00.0016450 (1.4x)
+ heap bit method: 00:00:00.0043110 (3x)
+
+ 50,000 elements:
+ old method: 00:00:00.0175970 (3x)
+ stackalloc bit method: 00:00:00.0085630 (1.5x)
+ array bit method: 00:00:00.0055010 (1x)
+ heap bit method: 00:00:00.0099590 (1.8x)
+
+ 100,000 elements:
+ old method: 00:00:00.0210330 (2x)
+ array bit method: 00:00:00.0100430 (1x)
+ heap bit method: 00:00:00.0154150 (1.5x)
+
+ 1,000,000 elements:
+ old method: 00:00:00.1243730 (1.2x)
+ array bit method: 00:00:00.0973110 (1x)
+ heap bit method: 00:00:00.1285650 (1.3x)
+
+ 10,000,000 elements:
+ old method: 00:00:00.9252570 (1x)
+ array bit method: 00:00:00.9632300 ( 1.05x)
+ heap bit method: 00:00:01.1098490 (1.20x)
+
+2007-03-08 David Mitchell <dmitchell@logos.com>
+
+ * List.cs: Fix the case where List.set_Item(int index) throws
+ inappropriate exception when index is equal to List.Count
+
+ List.IndexOf(object item) and IList.Contains(object item) throw
+ exceptions when given invalid types.
+
+ IList.Add(object item) throws InvalidCastException when item is
+ not of the correct type.
+
+2007-03-08 Gert Driesen <drieseng@users.sourceforge.net>
+
+ * Comparer.cs: Renamed IComparableOfTComparer<T> to GenericComparer<T>
+ to fix binary serialization compatibility with MS.
+
+2007-03-05 David Mitchell <dmitchell@logos.com>
+
+ * Dictionary.cs: An instance of Dictionary<TKey,TValue> is
+ supposed to throw a KeyNotFoundException when
+ the user attempts to retrieve the value associated with a key that
+ is not in the dictionary.
+
+ On the other hand, an instance of IDictionary is supposed to
+ return null in similar circumstances.
+
+2007-03-05 David Mitchell <dmitchell@logos.com>
+
+ * List.cs: Fix InsertRange bug (80930).
+
+2006-09-15 Gert Driesen <drieseng@users.sourceforge.net>
+
+ * List.cs: Fixed binary serialization compatibility with MS.NET.
+ Increment version whenever _items is modified; this fixes version
+ checks in Enumerator.
+
+2006-09-06 Zoltan Varga <vargaz@gmail.com>
+
+ * Dictionary.cs: Speed up get_Item/set_Item/GetPrev () a bit. Increase capacity
+ specified by the user so 'capacity' elements can really be added without resizing.
+
+2006-07-12 Zoltan Varga <vargaz@gmail.com>
+
+ * Dictionary.cs: Swap order of parameters to cmp.Equals () to improve
+ compatibility with MS.NET and strange Equals () implementations.
+
+2006-05-17 Kazuki Oikawa <kazuki@panicode.com>
+
+ * List.cs : implemented Sort(Comparison <T>).
+
+2006-05-08 Atsushi Enomoto <atsushi@ximian.com>
+
+ * List.cs : use proper comparer in Contains(), IndexOf() and
+ LastIndexOf(). Patch by Kazuki Oikawa. Fixed bug #77277.
+
+2006-03-16 Ankit Jain <jankit@novell.com>
+
+ * List.cs (CheckIndex): Check for -ve indices and allow index == size.
+ (Insert): Use CheckIndex.
+
+2006-03-12 Zoltan Varga <vargaz@gmail.com>
+
+ * List.cs: Applied patch from <kazuki@panicode.com>. Fixes #77504.
+
+2006-02-10 Martin Baulig <martin@ximian.com>
+
+ * Comparer.cs
+ (IComparableOfTComparer): `T' must implement `IComparable<T>' and
+ not `IComparable'.
+
+Tue Jan 24 18:22:54 CET 2006 Paolo Molaro <lupus@ximian.com>
+
+ * Dictionary.cs: avoid long reminder operations.
+
+2006-01-23 Raja R Harinath <rharinath@novell.com>
+
+ Speed up remove. Use 'dict[k]=v' as a self-tuning hint.
+ * Dictionary.cs (GetSlot): Move data-structure traversal to ...
+ (GetPrev): ... this. Returns the slot prior to the place we're
+ looking for, or null if that place is the head of the chain.
+ (Remove): Use it.
+ (this.set): Use it. Implement move-to-front on set.
+
+ * Dictionary.cs (ToTKey, ToTValue): New helpers to convert from
+ type 'object'.
+ (IDictionary.this, IDictionary.Add): Use them.
+ (IDictionary.Contains, IDictionary.Remove): If the types don't
+ match, do nothing.
+
+2006-01-19 Raja R Harinath <rharinath@novell.com>
+
+ Fix to pass new nunit tests.
+ * Dictionary.cs (ShimEnumerator): New class. Implement the
+ requirement that ((IDictionary) foo).GetEnumerator ().Current has
+ type DictionaryEntry.
+ (IDictionary.GetEnumerator): Use ShimEnumerator.
+ (Enumerator.Current): Now has type KeyValuePair<TKey, TValue>.
+ (Enumerator.MoveNext): Use VerifyState.
+ (Enumerator.VerifyState): Move validation of 'current' field to ...
+ (Enumerator.CurrentSlot): ... this.
+ (Enumerator.Current, Enumerator.IDictionaryEnumerator.Entry):
+ Use CurrentSlot.
+ (CopyTo, ICollection.CopyTo): Use subtle reasoning to replace a
+ '>=' with a '>'. Don't throw an ArgumentException when
+ index==array.Length && Count==0.
+ (KeyCollection.CopyTo, ValueCollection.CopyTo): Likewise, and thus
+ obviate the need to check (dictionary.Count == 0).
+
+2005-12-20 Sebastien Pouliot <sebastien@ximian.com>
+
+ * List.cs: Applied Atsushi's patch for Sort (bug 76361) now that the
+ generic versions of Array.Sort are implemented.
+
+2005-12-19 Sebastien Pouliot <sebastien@ximian.com>
+
+ * Dictionary.cs: Added [Serializable] attribute to both inner
+ Enumerator struct in Key and Value inner collection classes.
+ * EqualityComparer.cs: Added missing IEqualityComparer interface.
+ * List.cs: Added [Serializable] attribute to both inner Enumerator
+ struct.
+
+2005-12-19 Sebastien Pouliot <sebastien@ximian.com>
+
+ * Dictionary.cs: Fixed ICollection.CopyTo to use DictionaryEntry. Fixed
+ Key and Value CopyTo not to throw exception if the dictionary is empty
+ (fix bug #77019).
+ * List.cs: Fix exception reporting to match MS behaviour (2.0 final).
+
+2005-11-19 Zoltan Varga <vargaz@gmail.com>
+
+ * KeyNotFoundException.cs: Add default message.
+
+2005-09-18 Miguel de Icaza <miguel@novell.com>
+
+ * Dictionary.cs: Change style for internal fields.
+
+ If the capacity is zero, set the capacity to our default size as 0
+ is an allowed parameter in .NET
+
+2005-08-10 Kamil Skalski <nazgul@nemerle.org>
+
+ * KeyValuePair.cs, Dictionary.cs: Change Key and Value to properties to match
+ .NET 2.0 July CTP. Update its use in Dictionary, since now we
+ cannot write to them.
+
+2005-07-10 Kamil Skalski <nazgul@nemerle.org>
+
+ * Comparer.cs, EqualityComparer.cs: Use MakeGenericType instead of BindGenericParameters.
+
+
+2005-06-27 Raja R Harinath <rharinath@novell.com>
+
+ Introduce some thread-safety by removing the modify-on-read
+ move-to-front heuristic.
+ * Dictionary.cs (_enumeratorGeneration, _enumerators): Remove.
+ (Count): Add internal property set. Invalidate enumerators when
+ Count is changed. Change all references of _usedSlots to Count.
+ (this): Invalidate enumerators when the value of some slot is
+ changed, even if the layout of the data-structure isn't modified.
+ (DoHash): Remove null-key check. All codepaths leading to this
+ function already have the check.
+ (GetSlot): Remove move-to-front heuristic.
+ (Remove): Update.
+
+2005-06-24 Martin Baulig <martin@ximian.com>
+
+ * IDictionary.cs: Use the same type parameter names than on MS.
+
+ * IDictionary.cs, Dictionary.cs: We don't need the `CLSCompliant'
+ attribute here.
+
+2005-06-23 Martin Baulig <martin@ximian.com>
+
+ * *.cs: Removed the `[ComVisible(false)]' attributes everywhere.
+
+2005-06-22 Raja R Harinath <rharinath@novell.com>
+
+ * Dictionary.cs (_generation, _enumeratorGeneration, _enumerators):
+ New fields to implement fail-fast semantics. All code that
+ modifies the table increment _generation.
+ (GetSlot): Use _hcp to compare keys. Return the slot containing
+ the key, rather than the index. Avoid move-to-front heuristic
+ when there's an enumerator coursing through the table.
+ (this, Add, TryGetValue, ContainsKey, Remove): Update to change.
+ (Enumerator.Enumerator): Save the generation of the dictionary.
+ (Enumerator.Dispose): Inform dictionary that the enumerator is no more.
+ (Enumerator.MoveNext, Enumerator.VerifyState): Fail if the
+ dictionary has been modified.
+
+2005-06-20 David waite <mass@akuma.org>
+
+ * List.cs : substantial changes and optimizations
+ (AddCollection, AddEnumerable): new internal specializations of AddRange
+ (AsReadOnly): returns specific IList<T> to match ms.net 2.0b2 api.
+ (Clear): reset size to zero on clear
+ (ConvertAll): catch null converter, use Add to prevent OutOfBounds
+ exception
+ (FindAll, FindIndex, FindLast, FindLastIndex, RemoveAll, TrueForAll):
+ check for null match
+ (FindLastIndex): correct index parameters based on ms.net 2005b2 behavior
+ (ForEach): catch null action
+ (CheckIndex): new internal function similar to CheckRange for functions
+ which only provide a starting index
+ (InsertCollection, InsertEnumerable): new internal specializations of
+ InsertRange
+ (ReadOnlyList): removed, ReadOnlyCollection in
+ System.Collections.ObjectModel is used instead now
+
+2005-06-16 David Waite <mass@akuma.org>
+
+ * Dictionary.cs (EnumerationMode): Remove.
+ (Enumerator): Remove return type flag - legacy return is expected to
+ always return a DictionaryEntry
+ (Enumerator): Make constructor internal, it is not public on ms.net
+ beta 2
+ (VerifyState): Added method to check state preconditions and throw
+ appropriate exceptions.
+ (KeyCollection,ValueCollection): Mark sealed to match ms.net beta 2
+ (KeyCollection.Enumerator._hostEnumerator): make exact struct type,
+ rather than boxing and using by interface
+ (KeyCollection.Enumerator.Dispose): Call _hostEnumerator.Dispose.
+ (ValueCollection.Enumerator._hostEnumerator): make exact struct type,
+ rather than boxing and using by interface
+ (ValueCollection.Enumerator.Dispose): Call _hostEnumerator.Dispose.
+ * EqualityComparer.cs (DefaultComparer, IEquatableOfTEqualityComparer):
+ Mark as serializable.
+
+2005-06-16 Raja R Harinath <rharinath@novell.com>
+
+ * Dictionary.cs (GetKeys, GetValues): Remove.
+ (SetThreshold): New function to calculate the resize threshold.
+ (CopyTo): Don't use foreach syntax.
+ (ContainsValue): Likewise. Use default equality comparer of the
+ value type.
+ (GetObjectData): Use CopyTo to copy into temporary array. Don't
+ save redundant _usedSlots and _threshold.
+ (OnDeserialization): Rewrite.
+ (ICollection<>.CopyTo): Forward to CopyTo.
+ (Enumerator._nextIndex): Rename to from _index.
+ (Enumerator._next, Enumerator.FixNext): Remove.
+ (Enumerator.Current): Rewrite to avoid need for _next.
+ (Enumerator.IEnumerator.Reset): Update.
+ (KeyCollection): Is also IEnumerable<TKey> and IEnumerable.
+ Update methods to conform to standard.
+ (KeyCollection.GetEnumerator): Restore. Return the correct type.
+ (KeyCollection.Enumerator): Rename from KeyEnumerator. Simple
+ wrapper that forwards to Dictionary<,>.Enumerator.
+ (ValueCollection): Likewise.
+
+2005-06-12 David Waite <dwaite@gmail.com>
+
+ * IKeyComparer.cs: removed
+ * KeyValuePair.cs: add same-style ToString as ms.net Beta2 impl,
+ make Serializable, use correct field names.
+ * Dictionary.cs: Miscelaneus clean-ups, added serialization
+ support, use Hashtable prime functions
+
+2005-06-12 Ben Maurer <bmaurer@ximian.com>
+
+ * Comparer.cs, EqualityComparer.cs: Important performance hack:
+ make sure that we don't box stuff and do reflection on every
+ comparison. We use reflection at cctor time rather than on every
+ request.
+
+2005-06-09 Raja R Harinath <rharinath@novell.com>
+
+ Simplify Enumerator.MoveNext to make it "obviously correct", rather
+ than require subtle reasoning about the state of various variables.
+ * Dictionary.cs (Enumerator._isValid): Remove. Replace all uses
+ with "_current == null".
+ (Enumerator._validNodeVisited): Remove.
+ (Enumerator._next): New. Holds the the next position.
+ (Enumerator.FixNest): New helper function that ensures that _next
+ has the right value.
+ (Enumerator.MoveNext): Simplify. Now, copies _next to _current
+ and advances _next if possible.
+
+2005-06-08 Martin Baulig <martin@ximian.com>
+
+ * Dictionary.cs (Dictionary.KeyEnumerator): Removed the public
+ GetEnumerator() function since it's returning the wrong type.
+ (Dictionary.ValueEnumerator): Likewise. Fix #75073.
+
+2005-06-08 Ankit Jain <ankit@corewars.org>
+
+ * Dictionary.cs (Dictionary<TKey, TValue>.MoveNext): Allow traversal of chain in last slot
+ of the table. Fixes #75168.
+
+2005-06-04 Ben Maurer <bmaurer@ximian.com>
+
+ * *.cs: 2.0 api fixups
+
+2005-05-26 Miguel de Icaza <miguel@novell.com>
+
+ * Dictionary.cs: Remove the `Hash' name from the Dictionary
+ internal classes, make them public.
+
+2005-05-26 Zoltan Varga <vargaz@freemail.hu>
+
+ * Dictionary.cs: Fix a warning.
+
+ * IDictionary.cs: Add missing TryGetValue method.
+
+2005-05-19 Geoff Norton <gnorton@customerdna.com>
+
+ * List.cs (Insert): Resize the array before the shift if needed
+
+2005-05-18 Miguel de Icaza <miguel@novell.com>
+
+ * List.cs (GetRange): Implement.
+
+ Do not do lazy loading of data. Not worth adding an
+ extra check, and not worth the bugs.
+
+ This decision wont be discussed until: a) a full List regression
+ test suite exists and b) performance benchmarks are created. (b)
+ depends on (a) or the argument wont even be heard.
+
+2005-05-13 Atsushi Enomoto <atsushi@ximian.com>
+
+ * Queue.cs, Stack.cs: moved to System.dll
+
+2005-05-06 Martin Baulig <martin@ximian.com>
+
+ * *.cs: Add CLSCompliant(true) where missing.
+
+2005-05-06 Zoltan Varga <vargaz@freemail.hu>
+
+ * *.cs: Remove CLSCompliant(false) attributes.
+
+2005-05-05 Zoltan Varga <vargaz@freemail.hu>
+
+ * List.cs: Applied patch from Mart Roosmaa (roosmaa@gmail.com).
+ Fix Insert method. Fixes #74824.
+
+2005-04-29 Martin Baulig <martin@ximian.com>
+
+ Reflect latest spec changes.
+
+ * IEnumerable.cs (IEnumerable<T>): Implement IEnumerable.
+ * IEnumerator.cs (IEnumerator<T>): Implement IEnumerator.
+
+2005-04-29 Raja R Harinath <rharinath@novell.com>
+
+ Remove FIXME.
+ * Dictionary.cs (Slot<K,V>): Move to ...
+ (Dictionary<K,V>.Slot): ... here.
+
+2005-04-28 Martin Baulig <martin@ximian.com>
+
+ * Dictionary.cs, Queue.cs, Stack.cs, List.cs, Comparer.cs: Don't
+ duplicate type parameters in the nested classes.
+
2005-04-20 Zoltan Varga <vargaz@freemail.hu>
* List.cs: Fix ToArray () method. Fixes #74675.