lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From nightowl...@apache.org
Subject [10/58] [abbrv] lucenenet git commit: Added TreeSet and TreeDictionary from C5 to the Support namespace
Date Thu, 10 Nov 2016 11:47:24 GMT
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/5f198526/src/Lucene.Net.Core/Support/C5.Support.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Support/C5.Support.cs b/src/Lucene.Net.Core/Support/C5.Support.cs
new file mode 100644
index 0000000..9a9fcf6
--- /dev/null
+++ b/src/Lucene.Net.Core/Support/C5.Support.cs
@@ -0,0 +1,7335 @@
+/*
+ Copyright (c) 2003-2016 Niels Kokholm, Peter Sestoft, and Rasmus Lystrøm
+ 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.
+*/
+
+using System;
+using System.Linq;
+using System.Reflection;
+using SCG = System.Collections.Generic;
+
+namespace Lucene.Net.Support.C5
+{
+    // LUCENENET NOTE: These are support types required by TreeSet{T} and 
+    // TreeDictionary{K, V} (which is similar to TreeMap in Java). These were brought
+    // over from the C5 library. https://github.com/sestoft/C5
+
+    /// <summary>
+    /// Base class for classes implementing ICollectionValue[T]
+    /// </summary>
+    [Serializable]
+    public abstract class CollectionValueBase<T> : EnumerableBase<T>, ICollectionValue<T>, IShowable
+    {
+        #region Event handling
+        EventBlock<T> eventBlock;
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value></value>
+        public virtual EventTypeEnum ListenableEvents { get { return 0; } }
+
+        /// <summary>
+        /// A flag bitmap of the events currently subscribed to by this collection.
+        /// </summary>
+        /// <value></value>
+        public virtual EventTypeEnum ActiveEvents { get { return eventBlock == null ? 0 : eventBlock.events; } }
+
+        private void checkWillListen(EventTypeEnum eventType)
+        {
+            if ((ListenableEvents & eventType) == 0)
+                throw new UnlistenableEventException();
+        }
+
+        /// <summary>
+        /// The change event. Will be raised for every change operation on the collection.
+        /// </summary>
+        public virtual event CollectionChangedHandler<T> CollectionChanged
+        {
+            add { checkWillListen(EventTypeEnum.Changed); (eventBlock ?? (eventBlock = new EventBlock<T>())).CollectionChanged += value; }
+            remove
+            {
+                checkWillListen(EventTypeEnum.Changed);
+                if (eventBlock != null)
+                {
+                    eventBlock.CollectionChanged -= value;
+                    if (eventBlock.events == 0) eventBlock = null;
+                }
+            }
+        }
+        /// <summary>
+        /// Fire the CollectionChanged event
+        /// </summary>
+        protected virtual void raiseCollectionChanged()
+        { if (eventBlock != null) eventBlock.raiseCollectionChanged(this); }
+
+        /// <summary>
+        /// The clear event. Will be raised for every Clear operation on the collection.
+        /// </summary>
+        public virtual event CollectionClearedHandler<T> CollectionCleared
+        {
+            add { checkWillListen(EventTypeEnum.Cleared); (eventBlock ?? (eventBlock = new EventBlock<T>())).CollectionCleared += value; }
+            remove
+            {
+                checkWillListen(EventTypeEnum.Cleared);
+                if (eventBlock != null)
+                {
+                    eventBlock.CollectionCleared -= value;
+                    if (eventBlock.events == 0) eventBlock = null;
+                }
+            }
+        }
+        /// <summary>
+        /// Fire the CollectionCleared event
+        /// </summary>
+        protected virtual void raiseCollectionCleared(bool full, int count)
+        { if (eventBlock != null) eventBlock.raiseCollectionCleared(this, full, count); }
+
+        /// <summary>
+        /// Fire the CollectionCleared event
+        /// </summary>
+        protected virtual void raiseCollectionCleared(bool full, int count, int? offset)
+        { if (eventBlock != null) eventBlock.raiseCollectionCleared(this, full, count, offset); }
+
+        /// <summary>
+        /// The item added  event. Will be raised for every individual addition to the collection.
+        /// </summary>
+        public virtual event ItemsAddedHandler<T> ItemsAdded
+        {
+            add { checkWillListen(EventTypeEnum.Added); (eventBlock ?? (eventBlock = new EventBlock<T>())).ItemsAdded += value; }
+            remove
+            {
+                checkWillListen(EventTypeEnum.Added);
+                if (eventBlock != null)
+                {
+                    eventBlock.ItemsAdded -= value;
+                    if (eventBlock.events == 0) eventBlock = null;
+                }
+            }
+        }
+        /// <summary>
+        /// Fire the ItemsAdded event
+        /// </summary>
+        /// <param name="item">The item that was added</param>
+        /// <param name="count"></param>
+        protected virtual void raiseItemsAdded(T item, int count)
+        { if (eventBlock != null) eventBlock.raiseItemsAdded(this, item, count); }
+
+        /// <summary>
+        /// The item removed event. Will be raised for every individual removal from the collection.
+        /// </summary>
+        public virtual event ItemsRemovedHandler<T> ItemsRemoved
+        {
+            add { checkWillListen(EventTypeEnum.Removed); (eventBlock ?? (eventBlock = new EventBlock<T>())).ItemsRemoved += value; }
+            remove
+            {
+                checkWillListen(EventTypeEnum.Removed);
+                if (eventBlock != null)
+                {
+                    eventBlock.ItemsRemoved -= value;
+                    if (eventBlock.events == 0) eventBlock = null;
+                }
+            }
+        }
+        /// <summary>
+        /// Fire the ItemsRemoved event
+        /// </summary>
+        /// <param name="item">The item that was removed</param>
+        /// <param name="count"></param>
+        protected virtual void raiseItemsRemoved(T item, int count)
+        { if (eventBlock != null) eventBlock.raiseItemsRemoved(this, item, count); }
+
+        /// <summary>
+        /// The item added  event. Will be raised for every individual addition to the collection.
+        /// </summary>
+        public virtual event ItemInsertedHandler<T> ItemInserted
+        {
+            add { checkWillListen(EventTypeEnum.Inserted); (eventBlock ?? (eventBlock = new EventBlock<T>())).ItemInserted += value; }
+            remove
+            {
+                checkWillListen(EventTypeEnum.Inserted);
+                if (eventBlock != null)
+                {
+                    eventBlock.ItemInserted -= value;
+                    if (eventBlock.events == 0) eventBlock = null;
+                }
+            }
+        }
+        /// <summary>
+        /// Fire the ItemInserted event
+        /// </summary>
+        /// <param name="item">The item that was added</param>
+        /// <param name="index"></param>
+        protected virtual void raiseItemInserted(T item, int index)
+        { if (eventBlock != null) eventBlock.raiseItemInserted(this, item, index); }
+
+        /// <summary>
+        /// The item removed event. Will be raised for every individual removal from the collection.
+        /// </summary>
+        public virtual event ItemRemovedAtHandler<T> ItemRemovedAt
+        {
+            add { checkWillListen(EventTypeEnum.RemovedAt); (eventBlock ?? (eventBlock = new EventBlock<T>())).ItemRemovedAt += value; }
+            remove
+            {
+                checkWillListen(EventTypeEnum.RemovedAt);
+                if (eventBlock != null)
+                {
+                    eventBlock.ItemRemovedAt -= value;
+                    if (eventBlock.events == 0) eventBlock = null;
+                }
+            }
+        }
+        /// <summary> 
+        /// Fire the ItemRemovedAt event
+        /// </summary>
+        /// <param name="item">The item that was removed</param>
+        /// <param name="index"></param>
+        protected virtual void raiseItemRemovedAt(T item, int index)
+        { if (eventBlock != null) eventBlock.raiseItemRemovedAt(this, item, index); }
+
+        #region Event support for IList
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="index"></param>
+        /// <param name="value"></param>
+        /// <param name="item"></param>
+        protected virtual void raiseForSetThis(int index, T value, T item)
+        {
+            if (ActiveEvents != 0)
+            {
+                raiseItemsRemoved(item, 1);
+                raiseItemRemovedAt(item, index);
+                raiseItemsAdded(value, 1);
+                raiseItemInserted(value, index);
+                raiseCollectionChanged();
+            }
+        }
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="i"></param>
+        /// <param name="item"></param>
+        protected virtual void raiseForInsert(int i, T item)
+        {
+            if (ActiveEvents != 0)
+            {
+                raiseItemInserted(item, i);
+                raiseItemsAdded(item, 1);
+                raiseCollectionChanged();
+            }
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="item"></param>
+        protected void raiseForRemove(T item)
+        {
+            if (ActiveEvents != 0)
+            {
+                raiseItemsRemoved(item, 1);
+                raiseCollectionChanged();
+            }
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="item"></param>
+        /// <param name="count"></param>
+        protected void raiseForRemove(T item, int count)
+        {
+            if (ActiveEvents != 0)
+            {
+                raiseItemsRemoved(item, count);
+                raiseCollectionChanged();
+            }
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="index"></param>
+        /// <param name="item"></param>
+        protected void raiseForRemoveAt(int index, T item)
+        {
+            if (ActiveEvents != 0)
+            {
+                raiseItemRemovedAt(item, index);
+                raiseItemsRemoved(item, 1);
+                raiseCollectionChanged();
+            }
+        }
+
+        #endregion
+
+        #region Event  Support for ICollection
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="newitem"></param>
+        /// <param name="olditem"></param>
+        protected virtual void raiseForUpdate(T newitem, T olditem)
+        {
+            if (ActiveEvents != 0)
+            {
+                raiseItemsRemoved(olditem, 1);
+                raiseItemsAdded(newitem, 1);
+                raiseCollectionChanged();
+            }
+        }
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="newitem"></param>
+        /// <param name="olditem"></param>
+        /// <param name="count"></param>
+        protected virtual void raiseForUpdate(T newitem, T olditem, int count)
+        {
+            if (ActiveEvents != 0)
+            {
+                raiseItemsRemoved(olditem, count);
+                raiseItemsAdded(newitem, count);
+                raiseCollectionChanged();
+            }
+        }
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="item"></param>
+        protected virtual void raiseForAdd(T item)
+        {
+            if (ActiveEvents != 0)
+            {
+                raiseItemsAdded(item, 1);
+                raiseCollectionChanged();
+            }
+        }
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="wasRemoved"></param>
+        protected virtual void raiseForRemoveAll(ICollectionValue<T> wasRemoved)
+        {
+            if ((ActiveEvents & EventTypeEnum.Removed) != 0)
+                foreach (T item in wasRemoved)
+                    raiseItemsRemoved(item, 1);
+            if (wasRemoved != null && wasRemoved.Count > 0)
+                raiseCollectionChanged();
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        [Serializable]
+        protected class RaiseForRemoveAllHandler
+        {
+            CollectionValueBase<T> collection;
+            CircularQueue<T> wasRemoved;
+            bool wasChanged = false;
+
+            /// <summary>
+            /// 
+            /// </summary>
+            /// <param name="collection"></param>
+            public RaiseForRemoveAllHandler(CollectionValueBase<T> collection)
+            {
+                this.collection = collection;
+                mustFireRemoved = (collection.ActiveEvents & EventTypeEnum.Removed) != 0;
+                MustFire = (collection.ActiveEvents & (EventTypeEnum.Removed | EventTypeEnum.Changed)) != 0;
+            }
+
+            bool mustFireRemoved;
+            /// <summary>
+            /// 
+            /// </summary>
+            public readonly bool MustFire;
+
+            /// <summary>
+            /// 
+            /// </summary>
+            /// <param name="item"></param>
+            public void Remove(T item)
+            {
+                if (mustFireRemoved)
+                {
+                    if (wasRemoved == null)
+                        wasRemoved = new CircularQueue<T>();
+                    wasRemoved.Enqueue(item);
+                }
+                if (!wasChanged)
+                    wasChanged = true;
+            }
+
+            /// <summary>
+            /// 
+            /// </summary>
+            public void Raise()
+            {
+                if (wasRemoved != null)
+                    foreach (T item in wasRemoved)
+                        collection.raiseItemsRemoved(item, 1);
+                if (wasChanged)
+                    collection.raiseCollectionChanged();
+            }
+        }
+        #endregion
+
+        #endregion
+
+        internal MemoryType MemoryType { get; set; }
+
+        /// <summary>
+        /// Check if collection is empty.
+        /// </summary>
+        /// <value>True if empty</value>
+        public abstract bool IsEmpty { get; }
+
+        /// <summary>
+        /// The number of items in this collection.
+        /// </summary>
+        /// <value></value>
+        public abstract int Count { get; }
+
+        /// <summary>
+        /// The value is symbolic indicating the type of asymptotic complexity
+        /// in terms of the size of this collection (worst-case or amortized as
+        /// relevant).
+        /// </summary>
+        /// <value>A characterization of the speed of the 
+        /// <code>Count</code> property in this collection.</value>
+        public abstract Speed CountSpeed { get; }
+
+        /// <summary>
+        /// Copy the items of this collection to part of an array.
+        /// </summary>
+        /// <exception cref="ArgumentOutOfRangeException"> if <code>index</code> 
+        /// is not a valid index
+        /// into the array (i.e. negative or greater than the size of the array)
+        /// or the array does not have room for the items.</exception>
+        /// <param name="array">The array to copy to.</param>
+        /// <param name="index">The starting index.</param>
+        public virtual void CopyTo(T[] array, int index)
+        {
+            if (index < 0 || index + Count > array.Length)
+                throw new ArgumentOutOfRangeException();
+
+            foreach (T item in this) array[index++] = item;
+        }
+
+        /// <summary>
+        /// Create an array with the items of this collection (in the same order as an
+        /// enumerator would output them).
+        /// </summary>
+        /// <returns>The array</returns>
+        public virtual T[] ToArray()
+        {
+            T[] res = new T[Count];
+            int i = 0;
+
+            foreach (T item in this) res[i++] = item;
+
+            return res;
+        }
+
+        /// <summary>
+        /// Apply an single argument action, <see cref="T:Action`1"/> to this enumerable
+        /// </summary>
+        /// <param name="action">The action delegate</param>
+        public virtual void Apply(Action<T> action)
+        {
+            foreach (T item in this)
+                action(item);
+        }
+
+
+        /// <summary>
+        /// Check if there exists an item  that satisfies a
+        /// specific predicate in this collection.
+        /// </summary>
+        /// <param name="predicate">A delegate 
+        /// (<see cref="T:Func`2"/> with <code>R = bool</code>) 
+        /// defining the predicate</param>
+        /// <returns>True if such an item exists</returns>
+        public virtual bool Exists(Func<T, bool> predicate)
+        {
+            foreach (T item in this)
+                if (predicate(item))
+                    return true;
+
+            return false;
+        }
+
+        /// <summary>
+        /// Check if there exists an item  that satisfies a
+        /// specific predicate in this collection and return the first one in enumeration order.
+        /// </summary>
+        /// <param name="predicate">A delegate 
+        /// (<see cref="T:Func`2"/> with <code>R == bool</code>) defining the predicate</param>
+        /// <param name="item"></param>
+        /// <returns>True is such an item exists</returns>
+        public virtual bool Find(Func<T, bool> predicate, out T item)
+        {
+            foreach (T jtem in this)
+                if (predicate(jtem))
+                {
+                    item = jtem;
+                    return true;
+                }
+            item = default(T);
+            return false;
+        }
+
+        /// <summary>
+        /// Check if all items in this collection satisfies a specific predicate.
+        /// </summary>
+        /// <param name="predicate">A delegate 
+        /// (<see cref="T:Func`2"/> with <code>R = bool</code>) 
+        /// defining the predicate</param>
+        /// <returns>True if all items satisfies the predicate</returns>
+        public virtual bool All(Func<T, bool> predicate)
+        {
+            foreach (T item in this)
+                if (!predicate(item))
+                    return false;
+
+            return true;
+        }
+
+        /// <summary>
+        /// Create an enumerable, enumerating the items of this collection that satisfies 
+        /// a certain condition.
+        /// </summary>
+        /// <param name="predicate">A delegate 
+        /// (<see cref="T:Func`2"/> with <code>R = bool</code>) 
+        /// defining the predicate</param>
+        /// <returns>The filtered enumerable</returns>
+        public virtual SCG.IEnumerable<T> Filter(Func<T, bool> predicate)
+        {
+            if (MemoryType == MemoryType.Strict) throw new Exception("This is not a memory safe function and cannot be used in MemoryType.Strict");
+
+            foreach (T item in this)
+                if (predicate(item))
+                    yield return item;
+        }
+
+        /// <summary>
+        /// Choose some item of this collection. 
+        /// </summary>
+        /// <exception cref="NoSuchItemException">if collection is empty.</exception>
+        /// <returns></returns>
+        public abstract T Choose();
+
+
+        #region IShowable Members
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="stringbuilder"></param>
+        /// <param name="rest"></param>
+        /// <param name="formatProvider"></param>
+        /// <returns></returns>
+        public virtual bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
+        {
+            return Showing.ShowCollectionValue<T>(this, stringbuilder, ref rest, formatProvider);
+        }
+        #endregion
+
+        #region IFormattable Members
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="format"></param>
+        /// <param name="formatProvider"></param>
+        /// <returns></returns>
+        public virtual string ToString(string format, IFormatProvider formatProvider)
+        {
+            return Showing.ShowString(this, format, formatProvider);
+        }
+
+        #endregion
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <returns></returns>
+        public override string ToString()
+        {
+            return ToString(null, null);
+        }
+    }
+
+
+    /// <summary>
+    /// A base class for implementing a dictionary based on a set collection implementation.
+    /// <i>See the source code for <see cref="T:C5.HashDictionary`2"/> for an example</i>
+    /// 
+    /// </summary>
+    [Serializable]
+    public abstract class DictionaryBase<K, V> : CollectionValueBase<KeyValuePair<K, V>>, IDictionary<K, V>
+    {
+        /// <summary>
+        /// The set collection of entries underlying this dictionary implementation
+        /// </summary>
+        protected ICollection<KeyValuePair<K, V>> pairs;
+
+        SCG.IEqualityComparer<K> keyequalityComparer;
+
+        private readonly KeysCollection _keyCollection;
+        private readonly ValuesCollection _valueCollection;
+
+        #region Events
+
+        ProxyEventBlock<KeyValuePair<K, V>> eventBlock;
+
+        /// <summary>
+        /// The change event. Will be raised for every change operation on the collection.
+        /// </summary>
+        public override event CollectionChangedHandler<KeyValuePair<K, V>> CollectionChanged
+        {
+            add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionChanged += value; }
+            remove { if (eventBlock != null) eventBlock.CollectionChanged -= value; }
+        }
+
+        /// <summary>
+        /// The change event. Will be raised for every change operation on the collection.
+        /// </summary>
+        public override event CollectionClearedHandler<KeyValuePair<K, V>> CollectionCleared
+        {
+            add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionCleared += value; }
+            remove { if (eventBlock != null) eventBlock.CollectionCleared -= value; }
+        }
+
+        /// <summary>
+        /// The item added  event. Will be raised for every individual addition to the collection.
+        /// </summary>
+        public override event ItemsAddedHandler<KeyValuePair<K, V>> ItemsAdded
+        {
+            add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsAdded += value; }
+            remove { if (eventBlock != null) eventBlock.ItemsAdded -= value; }
+        }
+
+        /// <summary>
+        /// The item added  event. Will be raised for every individual removal from the collection.
+        /// </summary>
+        public override event ItemsRemovedHandler<KeyValuePair<K, V>> ItemsRemoved
+        {
+            add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsRemoved += value; }
+            remove { if (eventBlock != null) eventBlock.ItemsRemoved -= value; }
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        public override EventTypeEnum ListenableEvents
+        {
+            get
+            {
+                return EventTypeEnum.Basic;
+            }
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        public override EventTypeEnum ActiveEvents
+        {
+            get
+            {
+                return pairs.ActiveEvents;
+            }
+        }
+
+        #endregion
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="keyequalityComparer"></param>
+        /// <param name = "memoryType"></param>
+        protected DictionaryBase(SCG.IEqualityComparer<K> keyequalityComparer, MemoryType memoryType)
+        {
+            if (keyequalityComparer == null)
+                throw new NullReferenceException("Key equality comparer cannot be null");
+            this.keyequalityComparer = keyequalityComparer;
+            MemoryType = memoryType;
+
+            _keyCollection = new KeysCollection(pairs, memoryType);
+            _valueCollection = new ValuesCollection(pairs, memoryType);
+        }
+
+        #region IDictionary<K,V> Members
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value></value>
+        public virtual SCG.IEqualityComparer<K> EqualityComparer { get { return keyequalityComparer; } }
+
+
+        /// <summary>
+        /// Add a new (key, value) pair (a mapping) to the dictionary.
+        /// </summary>
+        /// <exception cref="DuplicateNotAllowedException"> if there already is an entry with the same key. </exception>
+        /// <param name="key">Key to add</param>
+        /// <param name="value">Value to add</param>
+        public virtual void Add(K key, V value)
+        {
+            KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
+
+            if (!pairs.Add(p))
+                throw new DuplicateNotAllowedException("Key being added: '" + key + "'");
+        }
+
+        /// <summary>
+        /// Add the entries from a collection of <see cref="T:C5.KeyValuePair`2"/> pairs to this dictionary.
+        /// <para><b>TODO: add restrictions L:K and W:V when the .Net SDK allows it </b></para>
+        /// </summary>
+        /// <exception cref="DuplicateNotAllowedException"> 
+        /// If the input contains duplicate keys or a key already present in this dictionary.</exception>
+        /// <param name="entries"></param>
+        public virtual void AddAll<L, W>(SCG.IEnumerable<KeyValuePair<L, W>> entries)
+            where L : K
+            where W : V
+        {
+            foreach (KeyValuePair<L, W> pair in entries)
+            {
+                KeyValuePair<K, V> p = new KeyValuePair<K, V>(pair.Key, pair.Value);
+                if (!pairs.Add(p))
+                    throw new DuplicateNotAllowedException("Key being added: '" + pair.Key + "'");
+            }
+        }
+
+        /// <summary>
+        /// Remove an entry with a given key from the dictionary
+        /// </summary>
+        /// <param name="key">The key of the entry to remove</param>
+        /// <returns>True if an entry was found (and removed)</returns>
+        public virtual bool Remove(K key)
+        {
+            KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
+
+            return pairs.Remove(p);
+        }
+
+
+        /// <summary>
+        /// Remove an entry with a given key from the dictionary and report its value.
+        /// </summary>
+        /// <param name="key">The key of the entry to remove</param>
+        /// <param name="value">On exit, the value of the removed entry</param>
+        /// <returns>True if an entry was found (and removed)</returns>
+        public virtual bool Remove(K key, out V value)
+        {
+            KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
+
+            if (pairs.Remove(p, out p))
+            {
+                value = p.Value;
+                return true;
+            }
+            else
+            {
+                value = default(V);
+                return false;
+            }
+        }
+
+
+        /// <summary>
+        /// Remove all entries from the dictionary
+        /// </summary>
+        public virtual void Clear() { pairs.Clear(); }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value></value>
+        public virtual Speed ContainsSpeed { get { return pairs.ContainsSpeed; } }
+
+        /// <summary>
+        /// Check if there is an entry with a specified key
+        /// </summary>
+        /// <param name="key">The key to look for</param>
+        /// <returns>True if key was found</returns>
+        public virtual bool Contains(K key)
+        {
+            KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
+
+            return pairs.Contains(p);
+        }
+
+        [Serializable]
+        class LiftedEnumerable<H> : SCG.IEnumerable<KeyValuePair<K, V>> where H : K
+        {
+            SCG.IEnumerable<H> keys;
+            public LiftedEnumerable(SCG.IEnumerable<H> keys) { this.keys = keys; }
+            public SCG.IEnumerator<KeyValuePair<K, V>> GetEnumerator() { foreach (H key in keys) yield return new KeyValuePair<K, V>(key); }
+
+            #region IEnumerable Members
+
+            System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
+            {
+                throw new NotImplementedException();
+            }
+
+            #endregion
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="keys"></param>
+        /// <returns></returns>
+        public virtual bool ContainsAll<H>(SCG.IEnumerable<H> keys) where H : K
+        {
+            if (MemoryType == MemoryType.Strict)
+                throw new Exception("The use of ContainsAll generates garbage as it still uses a non-memory safe enumerator");
+            return pairs.ContainsAll(new LiftedEnumerable<H>(keys));
+        }
+
+        /// <summary>
+        /// Check if there is an entry with a specified key and report the corresponding
+        /// value if found. This can be seen as a safe form of "val = this[key]".
+        /// </summary>
+        /// <param name="key">The key to look for</param>
+        /// <param name="value">On exit, the value of the entry</param>
+        /// <returns>True if key was found</returns>
+        public virtual bool Find(ref K key, out V value)
+        {
+            KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
+
+            if (pairs.Find(ref p))
+            {
+                key = p.Key;
+                value = p.Value;
+                return true;
+            }
+            else
+            {
+                value = default(V);
+                return false;
+            }
+        }
+
+
+        /// <summary>
+        /// Look for a specific key in the dictionary and if found replace the value with a new one.
+        /// This can be seen as a non-adding version of "this[key] = val".
+        /// </summary>
+        /// <param name="key">The key to look for</param>
+        /// <param name="value">The new value</param>
+        /// <returns>True if key was found</returns>
+        public virtual bool Update(K key, V value)
+        {
+            KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
+
+            return pairs.Update(p);
+        }
+
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="key"></param>
+        /// <param name="value"></param>
+        /// <param name="oldvalue"></param>
+        /// <returns></returns>
+        public virtual bool Update(K key, V value, out V oldvalue)
+        {
+            KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
+
+            bool retval = pairs.Update(p, out p);
+            oldvalue = p.Value;
+            return retval;
+        }
+
+
+        /// <summary>
+        /// Look for a specific key in the dictionary. If found, report the corresponding value,
+        /// else add an entry with the key and the supplied value.
+        /// </summary>
+        /// <param name="key">On entry the key to look for</param>
+        /// <param name="value">On entry the value to add if the key is not found.
+        /// On exit the value found if any.</param>
+        /// <returns>True if key was found</returns>
+        public virtual bool FindOrAdd(K key, ref V value)
+        {
+            KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
+
+            if (!pairs.FindOrAdd(ref p))
+                return false;
+            else
+            {
+                value = p.Value;
+                //key = p.key;
+                return true;
+            }
+        }
+
+
+        /// <summary>
+        /// Update value in dictionary corresponding to key if found, else add new entry.
+        /// More general than "this[key] = val;" by reporting if key was found.
+        /// </summary>
+        /// <param name="key">The key to look for</param>
+        /// <param name="value">The value to add or replace with.</param>
+        /// <returns>True if entry was updated.</returns>
+        public virtual bool UpdateOrAdd(K key, V value)
+        {
+            return pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value));
+        }
+
+
+        /// <summary>
+        /// Update value in dictionary corresponding to key if found, else add new entry.
+        /// More general than "this[key] = val;" by reporting if key was found and the old value if any.
+        /// </summary>
+        /// <param name="key"></param>
+        /// <param name="value"></param>
+        /// <param name="oldvalue"></param>
+        /// <returns></returns>
+        public virtual bool UpdateOrAdd(K key, V value, out V oldvalue)
+        {
+            KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
+            bool retval = pairs.UpdateOrAdd(p, out p);
+            oldvalue = p.Value;
+            return retval;
+        }
+
+
+
+        #region Keys,Values support classes
+        [Serializable]
+        internal class ValuesCollection : CollectionValueBase<V>, ICollectionValue<V>
+        {
+            private ICollection<KeyValuePair<K, V>> _pairs;
+            private readonly ValueEnumerator _valueEnumerator;
+
+
+            internal ValuesCollection(ICollection<KeyValuePair<K, V>> keyValuePairs, MemoryType memoryType)
+            {
+                _pairs = keyValuePairs;
+                _valueEnumerator = new ValueEnumerator(keyValuePairs, memoryType);
+            }
+
+
+            #region Private Enumerator
+
+            [Serializable]
+            private class ValueEnumerator : MemorySafeEnumerator<V>
+            {
+                private ICollection<KeyValuePair<K, V>> _keyValuePairs;
+
+                private SCG.IEnumerator<KeyValuePair<K, V>> _keyValuePairEnumerator;
+
+                public ValueEnumerator(ICollection<KeyValuePair<K, V>> keyValuePairs, MemoryType memoryType)
+                    : base(memoryType)
+                {
+                    _keyValuePairs = keyValuePairs;
+                }
+
+                internal void UpdateReference(ICollection<KeyValuePair<K, V>> keyValuePairs)
+                {
+                    _keyValuePairs = keyValuePairs;
+                    Current = default(V);
+                }
+
+                public override bool MoveNext()
+                {
+                    ICollection<KeyValuePair<K, V>> list = _keyValuePairs;
+
+                    if (_keyValuePairEnumerator == null)
+                        _keyValuePairEnumerator = list.GetEnumerator();
+
+                    if (_keyValuePairEnumerator.MoveNext())
+                    {
+                        var curr = _keyValuePairEnumerator.Current;
+                        Current = curr.Value;
+                        return true;
+                    }
+
+                    _keyValuePairEnumerator.Dispose();
+                    Current = default(V);
+                    return false;
+                }
+
+                public override void Reset()
+                {
+                    Current = default(V);
+                }
+                protected override MemorySafeEnumerator<V> Clone()
+                {
+                    var enumerator = new ValueEnumerator(_keyValuePairs, MemoryType)
+                    {
+                        Current = default(V)
+                    };
+                    return enumerator;
+                }
+            }
+
+            #endregion
+
+
+            public override V Choose()
+            {
+                return _pairs.Choose().Value;
+            }
+
+            public override SCG.IEnumerator<V> GetEnumerator()
+            {
+                //Updatecheck is performed by the pairs enumerator
+                var enumerator = (ValueEnumerator)_valueEnumerator.GetEnumerator();
+                enumerator.UpdateReference(_pairs);
+                return enumerator;
+            }
+
+            public override bool IsEmpty { get { return _pairs.IsEmpty; } }
+
+            public override int Count { get { return _pairs.Count; } }
+
+            public override Speed CountSpeed { get { return Speed.Constant; } }
+
+            public void Update(ICollection<KeyValuePair<K, V>> keyValuePairs)
+            {
+                _pairs = keyValuePairs;
+            }
+        }
+
+        [Serializable]
+        internal class KeysCollection : CollectionValueBase<K>, ICollectionValue<K>
+        {
+            ICollection<KeyValuePair<K, V>> _pairs;
+
+            private readonly KeyEnumerator _keyEnumerator;
+
+            #region Private Enumerator
+
+            [Serializable]
+            private class KeyEnumerator : MemorySafeEnumerator<K>
+            {
+                private ICollection<KeyValuePair<K, V>> _internalList;
+
+                private SCG.IEnumerator<KeyValuePair<K, V>> _keyValuePairEnumerator;
+
+                public KeyEnumerator(ICollection<KeyValuePair<K, V>> list, MemoryType memoryType)
+                    : base(memoryType)
+                {
+                    _internalList = list;
+                }
+
+                internal void UpdateReference(ICollection<KeyValuePair<K, V>> list)
+                {
+                    _internalList = list;
+                    Current = default(K);
+                }
+
+
+                public override bool MoveNext()
+                {
+                    ICollection<KeyValuePair<K, V>> list = _internalList;
+
+                    if (_keyValuePairEnumerator == null)
+                        _keyValuePairEnumerator = list.GetEnumerator();
+
+                    if (_keyValuePairEnumerator.MoveNext())
+                    {
+                        Current = _keyValuePairEnumerator.Current.Key;
+                        return true;
+                    }
+
+                    _keyValuePairEnumerator.Dispose();
+
+                    Current = default(K);
+                    return false;
+                }
+
+                public override void Reset()
+                {
+                    Current = default(K);
+                }
+
+                protected override MemorySafeEnumerator<K> Clone()
+                {
+                    var enumerator = new KeyEnumerator(_internalList, MemoryType)
+                    {
+                        Current = default(K)
+                    };
+                    return enumerator;
+                }
+            }
+
+            #endregion
+
+            internal KeysCollection(ICollection<KeyValuePair<K, V>> pairs, MemoryType memoryType)
+            {
+                _pairs = pairs;
+
+                _keyEnumerator = new KeyEnumerator(pairs, memoryType);
+            }
+
+            public void Update(ICollection<KeyValuePair<K, V>> pairs)
+            {
+                _pairs = pairs;
+            }
+
+            public override K Choose()
+            {
+                return _pairs.Choose().Key;
+            }
+
+            public override SCG.IEnumerator<K> GetEnumerator()
+            {
+                var enumerator = (KeyEnumerator)_keyEnumerator.GetEnumerator();
+                enumerator.UpdateReference(_pairs);
+                return enumerator;
+            }
+
+            public override bool IsEmpty { get { return _pairs.IsEmpty; } }
+
+            public override int Count { get { return _pairs.Count; } }
+
+            public override Speed CountSpeed { get { return _pairs.CountSpeed; } }
+        }
+
+        #endregion
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value>A collection containing all the keys of the dictionary</value>
+        public virtual ICollectionValue<K> Keys
+        {
+            get
+            {
+                _keyCollection.Update(pairs);
+                return _keyCollection;
+
+            }
+        }
+
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value>A collection containing all the values of the dictionary</value>
+        public virtual ICollectionValue<V> Values
+        {
+            get
+            {
+                _valueCollection.Update(pairs);
+                return _valueCollection;
+            }
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        public virtual Func<K, V> Func { get { return delegate (K k) { return this[k]; }; } }
+
+        /// <summary>
+        /// Indexer by key for dictionary. 
+        /// <para>The get method will throw an exception if no entry is found. </para>
+        /// <para>The set method behaves like <see cref="M:C5.DictionaryBase`2.UpdateOrAdd(`0,`1)"/>.</para>
+        /// </summary>
+        /// <exception cref="NoSuchItemException"> On get if no entry is found. </exception>
+        /// <value>The value corresponding to the key</value>
+        public virtual V this[K key]
+        {
+            get
+            {
+                KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
+
+                if (pairs.Find(ref p))
+                    return p.Value;
+                else
+                    throw new NoSuchItemException("Key '" + key.ToString() + "' not present in Dictionary");
+            }
+            set
+            { pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value)); }
+        }
+
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value>True if dictionary is read  only</value>
+        public virtual bool IsReadOnly { get { return pairs.IsReadOnly; } }
+
+
+        /// <summary>
+        /// Check the integrity of the internal data structures of this dictionary.
+        /// </summary>
+        /// <returns>True if check does not fail.</returns>
+        public virtual bool Check() { return pairs.Check(); }
+
+        #endregion
+
+        #region ICollectionValue<KeyValuePair<K,V>> Members
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value>True if this collection is empty.</value>
+        public override bool IsEmpty { get { return pairs.IsEmpty; } }
+
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value>The number of entries in the dictionary</value>
+        public override int Count { get { return pairs.Count; } }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value>The number of entries in the dictionary</value>
+        public override Speed CountSpeed { get { return pairs.CountSpeed; } }
+
+        /// <summary>
+        /// Choose some entry in this Dictionary. 
+        /// </summary>
+        /// <exception cref="NoSuchItemException">if collection is empty.</exception>
+        /// <returns></returns>
+        public override KeyValuePair<K, V> Choose() { return pairs.Choose(); }
+
+        /// <summary>
+        /// Create an enumerator for the collection of entries of the dictionary
+        /// </summary>
+        /// <returns>The enumerator</returns>
+        public override SCG.IEnumerator<KeyValuePair<K, V>> GetEnumerator()
+        {
+            return pairs.GetEnumerator();
+        }
+
+        #endregion
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="stringbuilder"></param>
+        /// <param name="rest"></param>
+        /// <param name="formatProvider"></param>
+        /// <returns></returns>
+        public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
+        {
+            return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);
+        }
+    }
+
+
+    /// <summary>
+    /// A base class for implementing a sorted dictionary based on a sorted set collection implementation.
+    /// <i>See the source code for <see cref="T:C5.TreeDictionary`2"/> for an example</i>
+    /// 
+    /// </summary>
+    [Serializable]
+    public abstract class SortedDictionaryBase<K, V> : DictionaryBase<K, V>, ISortedDictionary<K, V>
+    {
+        #region Fields
+
+        /// <summary>
+        /// 
+        /// </summary>
+        protected ISorted<KeyValuePair<K, V>> sortedpairs;
+        SCG.IComparer<K> keycomparer;
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="keycomparer"></param>
+        /// <param name="keyequalityComparer"></param>
+        /// <param name="memoryType">The memory type of the enumerator used to iterate the collection.</param>
+        protected SortedDictionaryBase(SCG.IComparer<K> keycomparer, SCG.IEqualityComparer<K> keyequalityComparer, MemoryType memoryType = MemoryType.Normal)
+            : base(keyequalityComparer, memoryType)
+        {
+            this.keycomparer = keycomparer;
+            MemoryType = memoryType;
+        }
+
+        #endregion
+
+        #region ISortedDictionary<K,V> Members
+
+        /// <summary>
+        /// The key comparer used by this dictionary.
+        /// </summary>
+        /// <value></value>
+        public SCG.IComparer<K> Comparer { get { return keycomparer; } }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value></value>
+        /// I should add something to return the same instance
+        public new ISorted<K> Keys { get { return new SortedKeysCollection(this, sortedpairs, keycomparer, EqualityComparer, MemoryType); } }
+
+        /// <summary>
+        /// Find the entry in the dictionary whose key is the
+        /// predecessor of the specified key.
+        /// </summary>
+        /// <param name="key">The key</param>
+        /// <param name="res">The predecessor, if any</param>
+        /// <returns>True if key has a predecessor</returns>
+        public bool TryPredecessor(K key, out KeyValuePair<K, V> res)
+        {
+            return sortedpairs.TryPredecessor(new KeyValuePair<K, V>(key), out res);
+        }
+
+        /// <summary>
+        /// Find the entry in the dictionary whose key is the
+        /// successor of the specified key.
+        /// </summary>
+        /// <param name="key">The key</param>
+        /// <param name="res">The successor, if any</param>
+        /// <returns>True if the key has a successor</returns>
+        public bool TrySuccessor(K key, out KeyValuePair<K, V> res)
+        {
+            return sortedpairs.TrySuccessor(new KeyValuePair<K, V>(key), out res);
+        }
+
+        /// <summary>
+        /// Find the entry in the dictionary whose key is the
+        /// weak predecessor of the specified key.
+        /// </summary>
+        /// <param name="key">The key</param>
+        /// <param name="res">The predecessor, if any</param>
+        /// <returns>True if key has a weak predecessor</returns>
+        public bool TryWeakPredecessor(K key, out KeyValuePair<K, V> res)
+        {
+            return sortedpairs.TryWeakPredecessor(new KeyValuePair<K, V>(key), out res);
+        }
+
+        /// <summary>
+        /// Find the entry in the dictionary whose key is the
+        /// weak successor of the specified key.
+        /// </summary>
+        /// <param name="key">The key</param>
+        /// <param name="res">The weak successor, if any</param>
+        /// <returns>True if the key has a weak successor</returns>
+        public bool TryWeakSuccessor(K key, out KeyValuePair<K, V> res)
+        {
+            return sortedpairs.TryWeakSuccessor(new KeyValuePair<K, V>(key), out res);
+        }
+
+        /// <summary>
+        /// Get the entry in the dictionary whose key is the
+        /// predecessor of the specified key.
+        /// </summary>
+        /// <exception cref="NoSuchItemException"></exception>
+        /// <param name="key">The key</param>
+        /// <returns>The entry</returns>
+        public KeyValuePair<K, V> Predecessor(K key)
+        {
+            return sortedpairs.Predecessor(new KeyValuePair<K, V>(key));
+        }
+
+        /// <summary>
+        /// Get the entry in the dictionary whose key is the
+        /// successor of the specified key.
+        /// </summary>
+        /// <exception cref="NoSuchItemException"></exception>
+        /// <param name="key">The key</param>
+        /// <returns>The entry</returns>
+        public KeyValuePair<K, V> Successor(K key)
+        {
+            return sortedpairs.Successor(new KeyValuePair<K, V>(key));
+        }
+
+        /// <summary>
+        /// Get the entry in the dictionary whose key is the
+        /// weak predecessor of the specified key.
+        /// </summary>
+        /// <exception cref="NoSuchItemException"></exception>
+        /// <param name="key">The key</param>
+        /// <returns>The entry</returns>
+        public KeyValuePair<K, V> WeakPredecessor(K key)
+        {
+            return sortedpairs.WeakPredecessor(new KeyValuePair<K, V>(key));
+        }
+
+        /// <summary>
+        /// Get the entry in the dictionary whose key is the
+        /// weak successor of the specified key.
+        /// </summary>
+        /// <exception cref="NoSuchItemException"></exception>
+        /// <param name="key">The key</param>
+        /// <returns>The entry</returns>
+        public KeyValuePair<K, V> WeakSuccessor(K key)
+        {
+            return sortedpairs.WeakSuccessor(new KeyValuePair<K, V>(key));
+        }
+
+        #endregion
+
+        #region ISortedDictionary<K,V> Members
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <returns></returns>
+        public KeyValuePair<K, V> FindMin()
+        {
+            return sortedpairs.FindMin();
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <returns></returns>
+        public KeyValuePair<K, V> DeleteMin()
+        {
+            return sortedpairs.DeleteMin();
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <returns></returns>
+        public KeyValuePair<K, V> FindMax()
+        {
+            return sortedpairs.FindMax();
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <returns></returns>
+        public KeyValuePair<K, V> DeleteMax()
+        {
+            return sortedpairs.DeleteMax();
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="cutter"></param>
+        /// <param name="lowEntry"></param>
+        /// <param name="lowIsValid"></param>
+        /// <param name="highEntry"></param>
+        /// <param name="highIsValid"></param>
+        /// <returns></returns>
+        public bool Cut(IComparable<K> cutter, out KeyValuePair<K, V> lowEntry, out bool lowIsValid, out KeyValuePair<K, V> highEntry, out bool highIsValid)
+        {
+            return sortedpairs.Cut(new KeyValuePairComparable(cutter), out lowEntry, out lowIsValid, out highEntry, out highIsValid);
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="bot"></param>
+        /// <returns></returns>
+        public IDirectedEnumerable<KeyValuePair<K, V>> RangeFrom(K bot)
+        {
+            return sortedpairs.RangeFrom(new KeyValuePair<K, V>(bot));
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="bot"></param>
+        /// <param name="top"></param>
+        /// <returns></returns>
+        public IDirectedEnumerable<KeyValuePair<K, V>> RangeFromTo(K bot, K top)
+        {
+            return sortedpairs.RangeFromTo(new KeyValuePair<K, V>(bot), new KeyValuePair<K, V>(top));
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="top"></param>
+        /// <returns></returns>
+        public IDirectedEnumerable<KeyValuePair<K, V>> RangeTo(K top)
+        {
+            return sortedpairs.RangeTo(new KeyValuePair<K, V>(top));
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <returns></returns>
+        public IDirectedCollectionValue<KeyValuePair<K, V>> RangeAll()
+        {
+            return sortedpairs.RangeAll();
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="items"></param>
+        public void AddSorted(SCG.IEnumerable<KeyValuePair<K, V>> items)
+        {
+            sortedpairs.AddSorted(items);
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="lowKey"></param>
+        public void RemoveRangeFrom(K lowKey)
+        {
+            sortedpairs.RemoveRangeFrom(new KeyValuePair<K, V>(lowKey));
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="lowKey"></param>
+        /// <param name="highKey"></param>
+        public void RemoveRangeFromTo(K lowKey, K highKey)
+        {
+            sortedpairs.RemoveRangeFromTo(new KeyValuePair<K, V>(lowKey), new KeyValuePair<K, V>(highKey));
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="highKey"></param>
+        public void RemoveRangeTo(K highKey)
+        {
+            sortedpairs.RemoveRangeTo(new KeyValuePair<K, V>(highKey));
+        }
+
+        #endregion
+        [Serializable]
+        class KeyValuePairComparable : IComparable<KeyValuePair<K, V>>
+        {
+            IComparable<K> cutter;
+
+            internal KeyValuePairComparable(IComparable<K> cutter) { this.cutter = cutter; }
+
+            public int CompareTo(KeyValuePair<K, V> other) { return cutter.CompareTo(other.Key); }
+
+            public bool Equals(KeyValuePair<K, V> other) { return cutter.Equals(other.Key); }
+        }
+
+        [Serializable]
+        class ProjectedDirectedEnumerable : MappedDirectedEnumerable<KeyValuePair<K, V>, K>
+        {
+            public ProjectedDirectedEnumerable(IDirectedEnumerable<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }
+
+            public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }
+
+        }
+
+        [Serializable]
+        class ProjectedDirectedCollectionValue : MappedDirectedCollectionValue<KeyValuePair<K, V>, K>
+        {
+            public ProjectedDirectedCollectionValue(IDirectedCollectionValue<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }
+
+            public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }
+
+        }
+
+        [Serializable]
+        sealed class SortedKeysCollection : SequencedBase<K>, ISorted<K>
+        {
+
+            #region Private Enumerator
+
+            [Serializable]
+            private class KeyEnumerator : MemorySafeEnumerator<K>
+            {
+                private ICollection<KeyValuePair<K, V>> _internalList;
+
+                private SCG.IEnumerator<KeyValuePair<K, V>> _internalEnumerator;
+
+
+
+                public KeyEnumerator(ICollection<KeyValuePair<K, V>> list, MemoryType memoryType)
+                    : base(memoryType)
+                {
+                    _internalList = list;
+                }
+
+                internal void UpdateReference(ICollection<KeyValuePair<K, V>> list)
+                {
+                    _internalList = list;
+                    Current = default(K);
+                }
+
+
+                public override void Dispose()
+                {
+                    _internalEnumerator.Dispose();
+                    _internalEnumerator = null;
+                }
+
+                public override bool MoveNext()
+                {
+                    ICollection<KeyValuePair<K, V>> list = _internalList;
+
+                    if (IteratorState == -1 || IteratorState == 0) // enumerator hasn't initialized yet or it has already run
+                        _internalEnumerator = list.GetEnumerator();
+
+                    IteratorState = 1;
+
+                    if (_internalEnumerator.MoveNext())
+                    {
+                        Current = _internalEnumerator.Current.Key;
+                        return true;
+                    }
+
+                    IteratorState = 0;
+                    return false;
+                }
+                public override void Reset()
+                {
+                    try
+                    {
+                        _internalEnumerator.Reset();
+                    }
+                    catch (Exception)
+                    {
+                        //swallow the exception
+                    }
+                    finally
+                    {
+                        Current = default(K);
+                    }
+                }
+
+
+                protected override MemorySafeEnumerator<K> Clone()
+                {
+                    var enumerator = new KeyEnumerator(_internalList, MemoryType)
+                    {
+                        Current = default(K)
+                    };
+                    return enumerator;
+                }
+            }
+
+            #endregion
+
+            private readonly KeyEnumerator _internalEnumerator;
+
+            ISortedDictionary<K, V> sorteddict;
+            //TODO: eliminate this. Only problem is the Find method because we lack method on dictionary that also
+            //      returns the actual key.
+            ISorted<KeyValuePair<K, V>> sortedpairs;
+            SCG.IComparer<K> comparer;
+
+            internal SortedKeysCollection(ISortedDictionary<K, V> sorteddict, ISorted<KeyValuePair<K, V>> sortedpairs, SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> itemequalityComparer, MemoryType memoryType)
+                : base(itemequalityComparer, memoryType)
+            {
+                this.sorteddict = sorteddict;
+                this.sortedpairs = sortedpairs;
+                this.comparer = comparer;
+
+                _internalEnumerator = new KeyEnumerator(sortedpairs, memoryType);
+            }
+
+            public override K Choose()
+            {
+                return sorteddict.Choose().Key;
+            }
+
+            public override SCG.IEnumerator<K> GetEnumerator()
+            {
+                _internalEnumerator.UpdateReference(sortedpairs);
+                return _internalEnumerator.GetEnumerator();
+                //                foreach (KeyValuePair<K, V> p in sorteddict)
+                //                    yield return p.Key;
+            }
+
+            public override bool IsEmpty { get { return sorteddict.IsEmpty; } }
+
+            public override int Count { get { return sorteddict.Count; } }
+
+            public override Speed CountSpeed { get { return sorteddict.CountSpeed; } }
+
+            #region ISorted<K> Members
+
+            public K FindMin() { return sorteddict.FindMin().Key; }
+
+            public K DeleteMin() { throw new ReadOnlyCollectionException(); }
+
+            public K FindMax() { return sorteddict.FindMax().Key; }
+
+            public K DeleteMax() { throw new ReadOnlyCollectionException(); }
+
+            public SCG.IComparer<K> Comparer { get { return comparer; } }
+
+            public bool TryPredecessor(K item, out K res)
+            {
+                KeyValuePair<K, V> pRes;
+                bool success = sorteddict.TryPredecessor(item, out pRes);
+                res = pRes.Key;
+                return success;
+            }
+
+            public bool TrySuccessor(K item, out K res)
+            {
+                KeyValuePair<K, V> pRes;
+                bool success = sorteddict.TrySuccessor(item, out pRes);
+                res = pRes.Key;
+                return success;
+            }
+
+            public bool TryWeakPredecessor(K item, out K res)
+            {
+                KeyValuePair<K, V> pRes;
+                bool success = sorteddict.TryWeakPredecessor(item, out pRes);
+                res = pRes.Key;
+                return success;
+            }
+
+            public bool TryWeakSuccessor(K item, out K res)
+            {
+                KeyValuePair<K, V> pRes;
+                bool success = sorteddict.TryWeakSuccessor(item, out pRes);
+                res = pRes.Key;
+                return success;
+            }
+
+            public K Predecessor(K item) { return sorteddict.Predecessor(item).Key; }
+
+            public K Successor(K item) { return sorteddict.Successor(item).Key; }
+
+            public K WeakPredecessor(K item) { return sorteddict.WeakPredecessor(item).Key; }
+
+            public K WeakSuccessor(K item) { return sorteddict.WeakSuccessor(item).Key; }
+
+            public bool Cut(IComparable<K> c, out K low, out bool lowIsValid, out K high, out bool highIsValid)
+            {
+                KeyValuePair<K, V> lowpair, highpair;
+                bool retval = sorteddict.Cut(c, out lowpair, out lowIsValid, out highpair, out highIsValid);
+                low = lowpair.Key;
+                high = highpair.Key;
+                return retval;
+            }
+
+            public IDirectedEnumerable<K> RangeFrom(K bot)
+            {
+                return new ProjectedDirectedEnumerable(sorteddict.RangeFrom(bot));
+            }
+
+            public IDirectedEnumerable<K> RangeFromTo(K bot, K top)
+            {
+                return new ProjectedDirectedEnumerable(sorteddict.RangeFromTo(bot, top));
+            }
+
+            public IDirectedEnumerable<K> RangeTo(K top)
+            {
+                return new ProjectedDirectedEnumerable(sorteddict.RangeTo(top));
+            }
+
+            public IDirectedCollectionValue<K> RangeAll()
+            {
+                return new ProjectedDirectedCollectionValue(sorteddict.RangeAll());
+            }
+
+            public void AddSorted(SCG.IEnumerable<K> items) { throw new ReadOnlyCollectionException(); }
+
+            public void RemoveRangeFrom(K low) { throw new ReadOnlyCollectionException(); }
+
+            public void RemoveRangeFromTo(K low, K hi) { throw new ReadOnlyCollectionException(); }
+
+            public void RemoveRangeTo(K hi) { throw new ReadOnlyCollectionException(); }
+            #endregion
+
+            #region ICollection<K> Members
+            public Speed ContainsSpeed { get { return sorteddict.ContainsSpeed; } }
+
+            public bool Contains(K key) { return sorteddict.Contains(key); ; }
+
+            public int ContainsCount(K item) { return sorteddict.Contains(item) ? 1 : 0; }
+
+            /// <summary>
+            /// 
+            /// </summary>
+            /// <returns></returns>
+            public ICollectionValue<K> UniqueItems()
+            {
+                return this;
+            }
+
+            /// <summary>
+            /// 
+            /// </summary>
+            /// <returns></returns>
+            public ICollectionValue<KeyValuePair<K, int>> ItemMultiplicities()
+            {
+                return new MultiplicityOne<K>(this);
+            }
+
+
+            public bool ContainsAll(SCG.IEnumerable<K> items)
+            {
+                //TODO: optimize?
+                foreach (K item in items)
+                    if (!sorteddict.Contains(item))
+                        return false;
+                return true;
+            }
+
+            public bool Find(ref K item)
+            {
+                KeyValuePair<K, V> p = new KeyValuePair<K, V>(item);
+                bool retval = sortedpairs.Find(ref p);
+                item = p.Key;
+                return retval;
+            }
+
+            public bool FindOrAdd(ref K item) { throw new ReadOnlyCollectionException(); }
+
+            public bool Update(K item) { throw new ReadOnlyCollectionException(); }
+
+            public bool Update(K item, out K olditem) { throw new ReadOnlyCollectionException(); }
+
+            public bool UpdateOrAdd(K item) { throw new ReadOnlyCollectionException(); }
+
+            public bool UpdateOrAdd(K item, out K olditem) { throw new ReadOnlyCollectionException(); }
+
+            public bool Remove(K item) { throw new ReadOnlyCollectionException(); }
+
+            public bool Remove(K item, out K removeditem) { throw new ReadOnlyCollectionException(); }
+
+            public void RemoveAllCopies(K item) { throw new ReadOnlyCollectionException(); }
+
+            public void RemoveAll(SCG.IEnumerable<K> items) { throw new ReadOnlyCollectionException(); }
+
+            public void Clear() { throw new ReadOnlyCollectionException(); }
+
+            public void RetainAll(SCG.IEnumerable<K> items) { throw new ReadOnlyCollectionException(); }
+
+            #endregion
+
+            #region IExtensible<K> Members
+            public override bool IsReadOnly { get { return true; } }
+
+            public bool AllowsDuplicates { get { return false; } }
+
+            public bool DuplicatesByCounting { get { return true; } }
+
+            public bool Add(K item) { throw new ReadOnlyCollectionException(); }
+
+            void SCG.ICollection<K>.Add(K item) { throw new ReadOnlyCollectionException(); }
+
+            public void AddAll(System.Collections.Generic.IEnumerable<K> items) { throw new ReadOnlyCollectionException(); }
+
+            public bool Check() { return sorteddict.Check(); }
+
+            #endregion
+
+            #region IDirectedCollectionValue<K> Members
+
+            public override IDirectedCollectionValue<K> Backwards()
+            {
+                return RangeAll().Backwards();
+            }
+
+            #endregion
+
+            #region IDirectedEnumerable<K> Members
+
+            IDirectedEnumerable<K> IDirectedEnumerable<K>.Backwards() { return Backwards(); }
+            #endregion
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="stringbuilder"></param>
+        /// <param name="rest"></param>
+        /// <param name="formatProvider"></param>
+        /// <returns></returns>
+        public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
+        {
+            return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);
+        }
+
+    }
+
+    /// <summary>
+    /// Base class (abstract) for sequenced collection implementations.
+    /// </summary>
+    [Serializable]
+    public abstract class SequencedBase<T> : DirectedCollectionBase<T>, IDirectedCollectionValue<T>
+    {
+        #region Fields
+
+        int iSequencedHashCode, iSequencedHashCodeStamp = -1;
+
+        #endregion
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="itemequalityComparer"></param>
+        /// <param name = "memoryType">The type of memory for the enumerator used to iterate the collection</param>
+        protected SequencedBase(SCG.IEqualityComparer<T> itemequalityComparer, MemoryType memoryType) : base(itemequalityComparer, memoryType) { }
+
+        #region Util
+
+        //TODO: make random for release
+        const int HASHFACTOR = 31;
+
+        /// <summary>
+        /// Compute the unsequenced hash code of a collection
+        /// </summary>
+        /// <param name="items">The collection to compute hash code for</param>
+        /// <param name="itemequalityComparer">The item equalitySCG.Comparer</param>
+        /// <returns>The hash code</returns>
+        public static int ComputeHashCode(ISequenced<T> items, SCG.IEqualityComparer<T> itemequalityComparer)
+        {
+            //NOTE: It must be possible to devise a much stronger combined hashcode, 
+            //but unfortunately, it has to be universal. OR we could use a (strong)
+            //family and initialise its parameter randomly at load time of this class!
+            //(We would not want to have yet a flag to check for invalidation?!)
+            //NBNBNB: the current hashcode has the very bad property that items with hashcode 0
+            // is ignored.
+            int iIndexedHashCode = 0;
+
+            foreach (T item in items)
+                iIndexedHashCode = iIndexedHashCode * HASHFACTOR + itemequalityComparer.GetHashCode(item);
+
+            return iIndexedHashCode;
+        }
+
+
+        /// <summary>
+        /// Examine if tit and tat are equal as sequenced collections
+        /// using the specified item equalityComparer (assumed compatible with the two collections).
+        /// </summary>
+        /// <param name="collection1">The first collection</param>
+        /// <param name="collection2">The second collection</param>
+        /// <param name="itemequalityComparer">The item equalityComparer to use for comparison</param>
+        /// <returns>True if equal</returns>
+        public static bool StaticEquals(ISequenced<T> collection1, ISequenced<T> collection2, SCG.IEqualityComparer<T> itemequalityComparer)
+        {
+            if (ReferenceEquals(collection1, collection2))
+                return true;
+
+            if (collection1.Count != collection2.Count)
+                return false;
+
+            //This way we might run through both enumerations twice, but
+            //probably not (if the hash codes are good)
+            if (collection1.GetSequencedHashCode() != collection2.GetSequencedHashCode())
+                return false;
+
+            using (SCG.IEnumerator<T> dat = collection2.GetEnumerator(), dit = collection1.GetEnumerator())
+            {
+                while (dit.MoveNext())
+                {
+                    dat.MoveNext();
+                    if (!itemequalityComparer.Equals(dit.Current, dat.Current))
+                        return false;
+                }
+            }
+
+            return true;
+        }
+
+
+        /// <summary>
+        /// Get the sequenced collection hash code of this collection: from the cached 
+        /// value if present and up to date, else (re)compute.
+        /// </summary>
+        /// <returns>The hash code</returns>
+        public virtual int GetSequencedHashCode()
+        {
+            if (iSequencedHashCodeStamp == stamp)
+                return iSequencedHashCode;
+
+            iSequencedHashCode = ComputeHashCode((ISequenced<T>)this, itemequalityComparer);
+            iSequencedHashCodeStamp = stamp;
+            return iSequencedHashCode;
+        }
+
+
+        /// <summary>
+        /// Check if the contents of that is equal to the contents of this
+        /// in the sequenced sense. Using the item equalityComparer of this collection.
+        /// </summary>
+        /// <param name="otherCollection">The collection to compare to.</param>
+        /// <returns>True if  equal</returns>
+        public virtual bool SequencedEquals(ISequenced<T> otherCollection)
+        {
+            return StaticEquals((ISequenced<T>)this, otherCollection, itemequalityComparer);
+        }
+
+
+        #endregion
+
+        /// <summary>
+        /// <code>Forwards</code> if same, else <code>Backwards</code>
+        /// </summary>
+        /// <value>The enumeration direction relative to the original collection.</value>
+        public override EnumerationDirection Direction { get { return EnumerationDirection.Forwards; } }
+
+        /// <summary>
+        /// Check if there exists an item  that satisfies a
+        /// specific predicate in this collection and return the index of the first one.
+        /// </summary>
+        /// <param name="predicate">A delegate defining the predicate</param>
+        /// <returns>the index, if found, a negative value else</returns>
+        public int FindIndex(Func<T, bool> predicate)
+        {
+            int index = 0;
+            foreach (T item in this)
+            {
+                if (predicate(item))
+                    return index;
+                index++;
+            }
+            return -1;
+        }
+
+        /// <summary>
+        /// Check if there exists an item  that satisfies a
+        /// specific predicate in this collection and return the index of the last one.
+        /// </summary>
+        /// <param name="predicate">A delegate defining the predicate</param>
+        /// <returns>the index, if found, a negative value else</returns>
+        public int FindLastIndex(Func<T, bool> predicate)
+        {
+            int index = Count - 1;
+            foreach (T item in Backwards())
+            {
+                if (predicate(item))
+                    return index;
+                index--;
+            }
+            return -1;
+        }
+
+    }
+
+    /// <summary>
+    /// Base class (abstract) for ICollection implementations.
+    /// </summary>
+    [Serializable]
+    public abstract class CollectionBase<T> : CollectionValueBase<T>
+    {
+        #region Fields
+
+        /// <summary>
+        /// The underlying field of the ReadOnly property
+        /// </summary>
+        protected bool isReadOnlyBase = false;
+
+        /// <summary>
+        /// The current stamp value
+        /// </summary>
+        protected int stamp { get; set; }
+
+        /// <summary>
+        /// The number of items in the collection
+        /// </summary>
+        protected int size;
+
+        /// <summary>
+        /// The item equalityComparer of the collection
+        /// </summary>
+        protected readonly SCG.IEqualityComparer<T> itemequalityComparer;
+
+        int iUnSequencedHashCode, iUnSequencedHashCodeStamp = -1;
+
+        #endregion
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="itemequalityComparer"></param>
+        /// <param name = "memoryType">The type of memory for the enumerator used to iterate the collection</param>
+        protected CollectionBase(SCG.IEqualityComparer<T> itemequalityComparer, MemoryType memoryType)
+        {
+            if (itemequalityComparer == null)
+                throw new NullReferenceException("Item EqualityComparer cannot be null.");
+            this.itemequalityComparer = itemequalityComparer;
+
+            MemoryType = memoryType;
+        }
+
+        #region Util
+
+        /// <summary>
+        /// Utility method for range checking.
+        /// </summary>
+        /// <exception cref="ArgumentOutOfRangeException"> if the start or count is negative or
+        ///  if the range does not fit within collection size.</exception>
+        /// <param name="start">start of range</param>
+        /// <param name="count">size of range</param>
+        protected void checkRange(int start, int count)
+        {
+            if (start < 0 || count < 0 || start + count > size)
+                throw new ArgumentOutOfRangeException();
+        }
+
+
+        /// <summary>
+        /// Compute the unsequenced hash code of a collection
+        /// </summary>
+        /// <param name="items">The collection to compute hash code for</param>
+        /// <param name="itemequalityComparer">The item equalitySCG.Comparer</param>
+        /// <returns>The hash code</returns>
+        public static int ComputeHashCode(ICollectionValue<T> items, SCG.IEqualityComparer<T> itemequalityComparer)
+        {
+            int h = 0;
+
+            //But still heuristic: 
+            //Note: the three odd factors should really be random, 
+            //but there will be a problem with serialization/deserialization!
+            //Two products is too few
+            foreach (T item in items)
+            {
+                uint h1 = (uint)itemequalityComparer.GetHashCode(item);
+
+                h += (int)((h1 * 1529784657 + 1) ^ (h1 * 2912831877) ^ (h1 * 1118771817 + 2));
+            }
+
+            return h;
+            /*
+                  The pairs (-1657792980, -1570288808) and (1862883298, -272461342) gives the same
+                  unsequenced hashcode with this hashfunction. The pair was found with code like
+
+                  HashDictionary<int, int[]> set = new HashDictionary<int, int[]>();
+                  Random rnd = new C5Random(12345);
+                  while (true)
+                  {
+                      int[] a = new int[2];
+                      a[0] = rnd.Next(); a[1] = rnd.Next();
+                      int h = unsequencedhashcode(a);
+                      int[] b = a;
+                      if (set.FindOrAdd(h, ref b))
+                      {
+                          Logger.Log(string.Format("Code {5}, Pair ({1},{2}) number {0} matched other pair ({3},{4})", set.Count, a[0], a[1], b[0], b[1], h));
+                      }
+                  }
+                  */
+
+        }
+
+        static Type isortedtype = typeof(ISorted<T>);
+
+        /// <summary>
+        /// Examine if collection1 and collection2 are equal as unsequenced collections
+        /// using the specified item equalityComparer (assumed compatible with the two collections).
+        /// </summary>
+        /// <param name="collection1">The first collection</param>
+        /// <param name="collection2">The second collection</param>
+        /// <param name="itemequalityComparer">The item equalityComparer to use for comparison</param>
+        /// <returns>True if equal</returns>
+        public static bool StaticEquals(ICollection<T> collection1, ICollection<T> collection2, SCG.IEqualityComparer<T> itemequalityComparer)
+        {
+            if (ReferenceEquals(collection1, collection2))
+                return true;
+
+            // bug20070227:
+            if (collection1 == null || collection2 == null)
+                return false;
+
+            if (collection1.Count != collection2.Count)
+                return false;
+
+            //This way we might run through both enumerations twice, but
+            //probably not (if the hash codes are good)
+            //TODO: check equal equalityComparers, at least here!
+            if (collection1.GetUnsequencedHashCode() != collection2.GetUnsequencedHashCode())
+                return false;
+
+            //TODO: move this to the sorted implementation classes? 
+            //Really depends on speed of InstanceOfType: we could save a cast
+            {
+                ISorted<T> stit, stat;
+                if ((stit = collection1 as ISorted<T>) != null && (stat = collection2 as ISorted<T>) != null && stit.Comparer == stat.Comparer)
+                {
+                    using (SCG.IEnumerator<T> dat = collection2.GetEnumerator(), dit = collection1.GetEnumerator())
+                    {
+                        while (dit.MoveNext())
+                        {
+                            dat.MoveNext();
+                            if (!itemequalityComparer.Equals(dit.Current, dat.Current))
+                                return false;
+                        }
+                        return true;
+                    }
+                }
+            }
+
+            if (!collection1.AllowsDuplicates && (collection2.AllowsDuplicates || collection2.ContainsSpeed >= collection1.ContainsSpeed))
+            {
+                foreach (T x in collection1) if (!collection2.Contains(x)) return false;
+            }
+            else if (!collection2.AllowsDuplicates)
+            {
+                foreach (T x in collection2) if (!collection1.Contains(x)) return false;
+            }
+            // Now tit.AllowsDuplicates && tat.AllowsDuplicates
+            else if (collection1.DuplicatesByCounting && collection2.DuplicatesByCounting)
+            {
+                foreach (T item in collection2) if (collection1.ContainsCount(item) != collection2.ContainsCount(item)) return false;
+            }
+            else
+            {
+                // To avoid an O(n^2) algorithm, we make an aux hashtable to hold the count of items
+                // bug20101103: HashDictionary<T, int> dict = new HashDictionary<T, int>();
+                HashDictionary<T, int> dict = new HashDictionary<T, int>(itemequalityComparer);
+                foreach (T item in collection2)
+                {
+                    int count = 1;
+                    if (dict.FindOrAdd(item, ref count))
+                        dict[item] = count + 1;
+                }
+                foreach (T item in collection1)
+                {
+                    var i = item;
+                    int count;
+                    if (dict.Find(ref i, out count) && count > 0)
+                        dict[item] = count - 1;
+                    else
+                        return false;
+                }
+                return true;
+            }
+
+            return true;
+        }
+
+
+        /// <summary>
+        /// Get the unsequenced collection hash code of this collection: from the cached 
+        /// value if present and up to date, else (re)compute.
+        /// </summary>
+        /// <returns>The hash code</returns>
+        public virtual int GetUnsequencedHashCode()
+        {
+            if (iUnSequencedHashCodeStamp == stamp)
+                return iUnSequencedHashCode;
+
+            iUnSequencedHashCode = ComputeHashCode(this, itemequalityComparer);
+            iUnSequencedHashCodeStamp = stamp;
+            return iUnSequencedHashCode;
+        }
+
+
+        /// <summary>
+        /// Check if the contents of otherCollection is equal to the contents of this
+        /// in the unsequenced sense.  Uses the item equality comparer of this collection
+        /// </summary>
+        /// <param name="otherCollection">The collection to compare to.</param>
+        /// <returns>True if  equal</returns>
+        public virtual bool UnsequencedEquals(ICollection<T> otherCollection)
+        {
+            return otherCollection != null && StaticEquals((ICollection<T>)this, otherCollection, itemequalityComparer);
+        }
+
+
+        /// <summary>
+        /// Check if the collection has been modified since a specified time, expressed as a stamp value.
+        /// </summary>
+        /// <exception cref="CollectionModifiedException"> if this collection has been updated 
+        /// since a target time</exception>
+        /// <param name="thestamp">The stamp identifying the target time</param>
+        protected virtual void modifycheck(int thestamp)
+        {
+            if (stamp != thestamp)
+                throw new CollectionModifiedException();
+        }
+
+
+        /// <summary>
+        /// Check if it is valid to perform update operations, and if so increment stamp.
+        /// </summary>
+        /// <exception cref="ReadOnlyCollectionException">If collection is read-only</exception>
+        protected virtual void updatecheck()
+        {
+            if (isReadOnlyBase)
+                throw new ReadOnlyCollectionException();
+
+            stamp++;
+        }
+
+        #endregion
+
+        #region ICollection<T> members
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value>True if this collection is read only</value>
+        public virtual bool IsReadOnly { get { return isReadOnlyBase; } }
+
+        #endregion
+
+        #region ICollectionValue<T> members
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value>The size of this collection</value>
+        public override int Count { get { return size; } }
+
+        /// <summary>
+        /// The value is symbolic indicating the type of asymptotic complexity
+        /// in terms of the size of this collection (worst-case or amortized as
+        /// relevant).
+        /// </summary>
+        /// <value>A characterization of the speed of the 
+        /// <code>Count</code> property in this collection.</value>
+        public override Speed CountSpeed { get { return Speed.Constant; } }
+
+
+        #endregion
+
+        #region IExtensible<T> members
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value></value>
+        public virtual SCG.IEqualityComparer<T> EqualityComparer { get { return itemequalityComparer; } }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <value>True if this collection is empty</value>
+        public override bool IsEmpty { get { return size == 0; } }
+
+        #endregion
+
+    }
+
+    /// <summary>
+    /// 
+    /// </summary>
+    /// <typeparam name="T"></typeparam>
+    [Serializable]
+    public abstract class DirectedCollectionBase<T> : CollectionBase<T>, IDirectedCollectionValue<T>
+    {
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="itemequalityComparer"></param>
+        /// <param name = "memoryType">The type of memory for the enumerator used to iterate the collection</param>
+        protected DirectedCollectionBase(SCG.IEqualityComparer<T> itemequalityComparer, MemoryType memoryType) : base(itemequalityComparer, memoryType) { }
+        /// <summary>
+        /// <code>Forwards</code> if same, else <code>Backwards</code>
+        /// </summary>
+        /// <value>The enumeration direction relative to the original collection.</value>
+        public virtual EnumerationDirection Direction { get { return EnumerationDirection.Forwards; } }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <returns></returns>
+        public abstract IDirectedCollectionValue<T> Backwards();
+
+        IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return Backwards(); }
+
+        /// <summary>
+        /// Check if there exists an item  that satisfies a
+        /// specific predicate in this collection and return the first one in enumeration order.
+        /// </summary>
+        /// <param name="predicate">A delegate 
+        /// (<see cref="T:Func`2"/> with <code>R == bool</code>) defining the predicate</param>
+        /// <param name="item"></param>
+        /// <returns>True is such an item exists</returns>
+        public virtual bool FindLast(Func<T, bool> predicate, out T item)
+        {
+            foreach (T jtem in Backwards())
+                if (predicate(jtem))
+                {
+                    item = jtem;
+                    return true;
+                }
+            item = default(T);
+            return false;
+        }
+    }
+
+    /// <summary>
+    /// A generic dictionary class based on a hash set class <see cref="T:C5.HashSet`1"/>. 
+    /// </summary>
+    [Serializable]
+    public class HashDictionary<K, V> : DictionaryBase<K, V>, IDictionary<K, V>
+    {
+        /// <summary>
+        /// Create a hash dictionary using a default equalityComparer for the keys.
+        /// Initial capacity of internal table will be 16 entries and threshold for 
+        /// expansion is 66% fill.
+        /// </summary>
+        public HashDictionary(MemoryType memoryType = MemoryType.Normal) : this(EqualityComparer<K>.Default, memoryType) { }
+
+        /// <summary>
+        /// Create a hash dictionary using a custom equalityComparer for the keys.
+        /// Initial capacity of internal table will be 16 entries and threshold for 
+        /// expansion is 66% fill.
+        /// </summary>
+        /// <param name="keyequalityComparer">The external key equalitySCG.Comparer</param>
+        /// <param name="memoryType">The memory type of the enumerator used to iterate the collection</param>
+        public HashDictionary(SCG.IEqualityComparer<K> keyequalityComparer, MemoryType memoryType = MemoryType.Normal)
+            : base(keyequalityComparer, memoryType)
+        {
+            pairs = new HashSet<KeyValuePair<K, V>>(new KeyValuePairEqualityComparer<K, V>(keyequalityComparer), memoryType);
+        }
+
+        /// <summary>
+        /// Create a hash dictionary using a custom equalityComparer and prescribing the 
+        /// initial size of the dictionary and a non-default threshold for internal table expansion.
+        /// </summary>
+        /// <param name="capacity">The initial capacity. Will be rounded upwards to nearest
+        /// power of 2, at least 16.</param>
+        /// <param name="fill">The expansion threshold. Must be between 10% and 90%.</param>
+        /// <param name="keyequalityComparer">The external key equalitySCG.Comparer</param>
+        /// <param name="memoryType">The memory type of the enumerator used to iterate the collection</param>
+        public HashDictionary(int capacity, double fill, SCG.IEqualityComparer<K> keyequalityComparer, MemoryType memoryType = MemoryType.Normal)
+            : base(keyequalityCompar

<TRUNCATED>

Mime
View raw message