using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
// From http://www.codeproject.com/KB/recipes/GenericOrderedDictionary.aspx
namespace NW4RTools.Util
{
///
/// Represents a generic collection of key/value pairs that are ordered independently of the key and value.
///
/// The type of the keys in the dictionary
/// The type of the values in the dictionary
public class OrderedDictionary : IOrderedDictionary
{
private const int DefaultInitialCapacity = 0;
private static readonly string _keyTypeName = typeof(TKey).FullName;
private static readonly string _valueTypeName = typeof(TValue).FullName;
private static readonly bool _valueTypeIsReferenceType = !typeof(ValueType).IsAssignableFrom(typeof(TValue));
private Dictionary _dictionary;
private List> _list;
private IEqualityComparer _comparer;
private object _syncRoot;
private int _initialCapacity;
///
/// Initializes a new instance of the OrderedDictionary<TKey,TValue> class.
///
public OrderedDictionary()
: this(DefaultInitialCapacity, null)
{
}
///
/// Initializes a new instance of the OrderedDictionary<TKey,TValue> class using the specified initial capacity.
///
/// The initial number of elements that the OrderedDictionary<TKey,TValue> can contain.
/// is less than 0
public OrderedDictionary(int capacity)
: this(capacity, null)
{
}
///
/// Initializes a new instance of the OrderedDictionary<TKey,TValue> class using the specified comparer.
///
/// The IEqualityComparer<TKey> to use when comparing keys, or to use the default EqualityComparer<TKey> for the type of the key.
public OrderedDictionary(IEqualityComparer comparer)
: this(DefaultInitialCapacity, comparer)
{
}
///
/// Initializes a new instance of the OrderedDictionary<TKey,TValue> class using the specified initial capacity and comparer.
///
/// The initial number of elements that the OrderedDictionary<TKey,TValue> collection can contain.
/// The IEqualityComparer<TKey> to use when comparing keys, or to use the default EqualityComparer<TKey> for the type of the key.
/// is less than 0
public OrderedDictionary(int capacity, IEqualityComparer comparer)
{
if(0 > capacity)
throw new ArgumentOutOfRangeException("capacity", "'capacity' must be non-negative");
_initialCapacity = capacity;
_comparer = comparer;
}
///
/// Converts the object passed as a key to the key type of the dictionary
///
/// The key object to check
/// The key object, cast as the key type of the dictionary
/// is .
/// The key type of the OrderedDictionary<TKey,TValue> is not in the inheritance hierarchy of .
private static TKey ConvertToKeyType(object keyObject)
{
if(null == keyObject)
{
throw new ArgumentNullException("key");
}
else
{
if(keyObject is TKey)
return (TKey)keyObject;
}
throw new ArgumentException("'key' must be of type " + _keyTypeName, "key");
}
///
/// Converts the object passed as a value to the value type of the dictionary
///
/// The object to convert to the value type of the dictionary
/// The value object, converted to the value type of the dictionary
/// is , and the value type of the OrderedDictionary<TKey,TValue> is a value type.
/// The value type of the OrderedDictionary<TKey,TValue> is not in the inheritance hierarchy of .
private static TValue ConvertToValueType(object value)
{
if(null == value)
{
if(_valueTypeIsReferenceType)
return default(TValue);
else
throw new ArgumentNullException("value");
}
else
{
if(value is TValue)
return (TValue)value;
}
throw new ArgumentException("'value' must be of type " + _valueTypeName, "value");
}
///
/// Gets the dictionary object that stores the keys and values
///
/// The dictionary object that stores the keys and values for the OrderedDictionary<TKey,TValue>
/// Accessing this property will create the dictionary object if necessary
private Dictionary Dictionary
{
get
{
if(null == _dictionary)
{
_dictionary = new Dictionary(_initialCapacity, _comparer);
}
return _dictionary;
}
}
///
/// Gets the list object that stores the key/value pairs.
///
/// The list object that stores the key/value pairs for the OrderedDictionary<TKey,TValue>
/// Accessing this property will create the list object if necessary.
private List> List
{
get
{
if(null == _list)
{
_list = new List>(_initialCapacity);
}
return _list;
}
}
IDictionaryEnumerator IOrderedDictionary.GetEnumerator()
{
return Dictionary.GetEnumerator();
}
IDictionaryEnumerator IDictionary.GetEnumerator()
{
return Dictionary.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return List.GetEnumerator();
}
IEnumerator> IEnumerable>.GetEnumerator()
{
return List.GetEnumerator();
}
public TKey GetKeyForIndex(int index) {
return List[index].Key;
}
public TKey GetKeyForValue(TValue value) {
foreach (var kv in List) {
if (kv.Value.Equals(value))
return kv.Key;
}
throw new KeyNotFoundException();
}
public int GetIndexForValue(TValue value) {
int i = 0;
foreach (var kv in List) {
if (kv.Value.Equals(value))
return i;
i += 1;
}
throw new KeyNotFoundException();
}
///
/// Inserts a new entry into the OrderedDictionary<TKey,TValue> collection with the specified key and value at the specified index.
///
/// The zero-based index at which the element should be inserted.
/// The key of the entry to add.
/// The value of the entry to add. The value can be if the type of the values in the dictionary is a reference type.
/// is less than 0.
/// -or-
/// is greater than .
/// is .
/// An element with the same key already exists in the OrderedDictionary<TKey,TValue>.
public void Insert(int index, TKey key, TValue value)
{
if(index > Count || index < 0)
throw new ArgumentOutOfRangeException("index");
Dictionary.Add(key, value);
List.Insert(index, new KeyValuePair(key, value));
}
///
/// Inserts a new entry into the OrderedDictionary<TKey,TValue> collection with the specified key and value at the specified index.
///
/// The zero-based index at which the element should be inserted.
/// The key of the entry to add.
/// The value of the entry to add. The value can be if the type of the values in the dictionary is a reference type.
/// is less than 0.
/// -or-
/// is greater than .
/// is .
/// -or-
/// is , and the value type of the OrderedDictionary<TKey,TValue> is a value type.
/// The key type of the OrderedDictionary<TKey,TValue> is not in the inheritance hierarchy of .
/// -or-
/// The value type of the OrderedDictionary<TKey,TValue> is not in the inheritance hierarchy of .
/// -or-
/// An element with the same key already exists in the OrderedDictionary<TKey,TValue>.
void IOrderedDictionary.Insert(int index, object key, object value)
{
Insert(index, ConvertToKeyType(key), ConvertToValueType(value));
}
///
/// Removes the entry at the specified index from the OrderedDictionary<TKey,TValue> collection.
///
/// The zero-based index of the entry to remove.
/// is less than 0.
/// -or-
/// index is equal to or greater than .
public void RemoveAt(int index)
{
if(index >= Count || index < 0)
throw new ArgumentOutOfRangeException("index", "'index' must be non-negative and less than the size of the collection");
TKey key = List[index].Key;
List.RemoveAt(index);
Dictionary.Remove(key);
}
///
/// Gets or sets the value at the specified index.
///
/// The zero-based index of the value to get or set.
/// The value of the item at the specified index.
/// is less than 0.
/// -or-
/// index is equal to or greater than .
public TValue this[int index]
{
get
{
return List[index].Value;
}
set
{
if(index >= Count || index < 0)
throw new ArgumentOutOfRangeException("index", "'index' must be non-negative and less than the size of the collection");
TKey key = List[index].Key;
List[index] = new KeyValuePair(key, value);
Dictionary[key] = value;
}
}
///
/// Gets or sets the value at the specified index.
///
/// The zero-based index of the value to get or set.
/// The value of the item at the specified index.
/// is less than 0.
/// -or-
/// index is equal to or greater than .
/// is a null reference, and the value type of the OrderedDictionary<TKey,TValue> is a value type.
/// The value type of the OrderedDictionary<TKey,TValue> is not in the inheritance hierarchy of .
object IOrderedDictionary.this[int index]
{
get
{
return this[index];
}
set
{
this[index] = ConvertToValueType(value);
}
}
///
/// Adds an entry with the specified key and value into the OrderedDictionary<TKey,TValue> collection with the lowest available index.
///
/// The key of the entry to add.
/// The value of the entry to add. This value can be .
/// A key cannot be , but a value can be.
/// You can also use the property to add new elements by setting the value of a key that does not exist in the OrderedDictionary<TKey,TValue> collection; however, if the specified key already exists in the OrderedDictionary<TKey,TValue>, setting the property overwrites the old value. In contrast, the method does not modify existing elements.
/// is
/// An element with the same key already exists in the OrderedDictionary<TKey,TValue>
void IDictionary.Add(TKey key, TValue value)
{
Add(key, value);
}
///
/// Adds an entry with the specified key and value into the OrderedDictionary<TKey,TValue> collection with the lowest available index.
///
/// The key of the entry to add.
/// The value of the entry to add. This value can be .
/// The index of the newly added entry
/// A key cannot be , but a value can be.
/// You can also use the property to add new elements by setting the value of a key that does not exist in the OrderedDictionary<TKey,TValue> collection; however, if the specified key already exists in the OrderedDictionary<TKey,TValue>, setting the property overwrites the old value. In contrast, the method does not modify existing elements.
/// is
/// An element with the same key already exists in the OrderedDictionary<TKey,TValue>
public int Add(TKey key, TValue value)
{
Dictionary.Add(key, value);
List.Add(new KeyValuePair(key, value));
return Count - 1;
}
///
/// Adds an entry with the specified key and value into the OrderedDictionary<TKey,TValue> collection with the lowest available index.
///
/// The key of the entry to add.
/// The value of the entry to add. This value can be .
/// is .
/// -or-
/// is , and the value type of the OrderedDictionary<TKey,TValue> is a value type.
/// The key type of the OrderedDictionary<TKey,TValue> is not in the inheritance hierarchy of .
/// -or-
/// The value type of the OrderedDictionary<TKey,TValue> is not in the inheritance hierarchy of .
void IDictionary.Add(object key, object value)
{
Add(ConvertToKeyType(key), ConvertToValueType(value));
}
///
/// Removes all elements from the OrderedDictionary<TKey,TValue> collection.
///
/// The capacity is not changed as a result of calling this method.
public void Clear()
{
Dictionary.Clear();
List.Clear();
}
///
/// Determines whether the OrderedDictionary<TKey,TValue> collection contains a specific key.
///
/// The key to locate in the OrderedDictionary<TKey,TValue> collection.
/// if the OrderedDictionary<TKey,TValue> collection contains an element with the specified key; otherwise, .
/// is
public bool ContainsKey(TKey key)
{
return Dictionary.ContainsKey(key);
}
///
/// Determines whether the OrderedDictionary<TKey,TValue> collection contains a specific key.
///
/// The key to locate in the OrderedDictionary<TKey,TValue> collection.
/// if the OrderedDictionary<TKey,TValue> collection contains an element with the specified key; otherwise, .
/// is
/// The key type of the OrderedDictionary<TKey,TValue> is not in the inheritance hierarchy of .
bool IDictionary.Contains(object key)
{
return ContainsKey(ConvertToKeyType(key));
}
///
/// Gets a value indicating whether the OrderedDictionary<TKey,TValue> has a fixed size.
///
/// if the OrderedDictionary<TKey,TValue> has a fixed size; otherwise, . The default is .
bool IDictionary.IsFixedSize
{
get
{
return false;
}
}
///
/// Gets a value indicating whether the OrderedDictionary<TKey,TValue> collection is read-only.
///
/// if the OrderedDictionary<TKey,TValue> is read-only; otherwise, . The default is .
///
/// A collection that is read-only does not allow the addition, removal, or modification of elements after the collection is created.
/// A collection that is read-only is simply a collection with a wrapper that prevents modification of the collection; therefore, if changes are made to the underlying collection, the read-only collection reflects those changes.
///
public bool IsReadOnly
{
get
{
return false;
}
}
///
/// Gets an object containing the keys in the OrderedDictionary<TKey,TValue>.
///
/// An object containing the keys in the OrderedDictionary<TKey,TValue>.
/// The returned object is not a static copy; instead, the collection refers back to the keys in the original OrderedDictionary<TKey,TValue>. Therefore, changes to the OrderedDictionary<TKey,TValue> continue to be reflected in the key collection.
ICollection IDictionary.Keys
{
get
{
return (ICollection)Keys;
}
}
///
/// Returns the zero-based index of the specified key in the OrderedDictionary<TKey,TValue>
///
/// The key to locate in the OrderedDictionary<TKey,TValue>
/// The zero-based index of , if is found in the OrderedDictionary<TKey,TValue>; otherwise, -1
/// This method performs a linear search; therefore it has a cost of O(n) at worst.
public int IndexOfKey(TKey key)
{
if(null == key)
throw new ArgumentNullException("key");
for(int index = 0; index < List.Count; index++)
{
KeyValuePair entry = List[index];
TKey next = entry.Key;
if(null != _comparer)
{
if(_comparer.Equals(next, key))
{
return index;
}
}
else if(next.Equals(key))
{
return index;
}
}
return -1;
}
///
/// Removes the entry with the specified key from the OrderedDictionary<TKey,TValue> collection.
///
/// The key of the entry to remove
/// if the key was found and the corresponding element was removed; otherwise,
public bool Remove(TKey key)
{
if(null == key)
throw new ArgumentNullException("key");
int index = IndexOfKey(key);
if(index >= 0)
{
if(Dictionary.Remove(key))
{
List.RemoveAt(index);
return true;
}
}
return false;
}
///
/// Removes the entry with the specified key from the OrderedDictionary<TKey,TValue> collection.
///
/// The key of the entry to remove
void IDictionary.Remove(object key)
{
Remove(ConvertToKeyType(key));
}
///
/// Gets an object containing the values in the OrderedDictionary<TKey,TValue> collection.
///
/// An object containing the values in the OrderedDictionary<TKey,TValue> collection.
/// The returned object is not a static copy; instead, the refers back to the values in the original OrderedDictionary<TKey,TValue> collection. Therefore, changes to the OrderedDictionary<TKey,TValue> continue to be reflected in the .
ICollection IDictionary.Values
{
get
{
return (ICollection)Values;
}
}
///
/// Gets or sets the value with the specified key.
///
/// The key of the value to get or set.
/// The value associated with the specified key. If the specified key is not found, attempting to get it returns , and attempting to set it creates a new element using the specified key.
public TValue this[TKey key]
{
get
{
return Dictionary[key];
}
set
{
if(Dictionary.ContainsKey(key))
{
Dictionary[key] = value;
List[IndexOfKey(key)] = new KeyValuePair(key, value);
}
else
{
Add(key, value);
}
}
}
///
/// Gets or sets the value with the specified key.
///
/// The key of the value to get or set.
/// The value associated with the specified key. If the specified key is not found, attempting to get it returns , and attempting to set it creates a new element using the specified key.
object IDictionary.this[object key]
{
get
{
return this[ConvertToKeyType(key)];
}
set
{
this[ConvertToKeyType(key)] = ConvertToValueType(value);
}
}
///
/// Copies the elements of the OrderedDictionary<TKey,TValue> elements to a one-dimensional Array object at the specified index.
///
/// The one-dimensional object that is the destination of the objects copied from the OrderedDictionary<TKey,TValue>. The must have zero-based indexing.
/// The zero-based index in at which copying begins.
/// The method preserves the order of the elements in the OrderedDictionary<TKey,TValue>
void ICollection.CopyTo(Array array, int index)
{
((ICollection)List).CopyTo(array, index);
}
///
/// Gets the number of key/values pairs contained in the OrderedDictionary<TKey,TValue> collection.
///
/// The number of key/value pairs contained in the OrderedDictionary<TKey,TValue> collection.
public int Count
{
get
{
return List.Count;
}
}
///
/// Gets a value indicating whether access to the OrderedDictionary<TKey,TValue> object is synchronized (thread-safe).
///
/// This method always returns false.
bool ICollection.IsSynchronized
{
get
{
return false;
}
}
///
/// Gets an object that can be used to synchronize access to the OrderedDictionary<TKey,TValue> object.
///
/// An object that can be used to synchronize access to the OrderedDictionary<TKey,TValue> object.
object ICollection.SyncRoot
{
get
{
if(this._syncRoot == null)
{
System.Threading.Interlocked.CompareExchange(ref this._syncRoot, new object(), null);
}
return this._syncRoot;
}
}
///
/// Gets an ICollection<TKey> object containing the keys in the OrderedDictionary<TKey,TValue>.
///
/// An ICollection<TKey> object containing the keys in the OrderedDictionary<TKey,TValue>.
/// The returned ICollection<TKey> object is not a static copy; instead, the collection refers back to the keys in the original OrderedDictionary<TKey,TValue>. Therefore, changes to the OrderedDictionary<TKey,TValue> continue to be reflected in the key collection.
public ICollection Keys
{
get
{
return Dictionary.Keys;
}
}
///
/// Gets the value associated with the specified key.
///
/// The key of the value to get.
/// When this method returns, contains the value associated with the specified key, if the key is found; otherwise, the default value for the type of . This parameter can be passed uninitialized.
/// if the OrderedDictionary<TKey,TValue> contains an element with the specified key; otherwise, .
public bool TryGetValue(TKey key, out TValue value)
{
return Dictionary.TryGetValue(key, out value);
}
///
/// Gets an ICollection<TValue> object containing the values in the OrderedDictionary<TKey,TValue>.
///
/// An ICollection<TValue> object containing the values in the OrderedDictionary<TKey,TValue>.
/// The returned ICollection<TKey> object is not a static copy; instead, the collection refers back to the values in the original OrderedDictionary<TKey,TValue>. Therefore, changes to the OrderedDictionary<TKey,TValue> continue to be reflected in the value collection.
public ICollection Values
{
get
{
return Dictionary.Values;
}
}
///
/// Adds the specified value to the OrderedDictionary<TKey,TValue> with the specified key.
///
/// The KeyValuePair<TKey,TValue> structure representing the key and value to add to the OrderedDictionary<TKey,TValue>.
void ICollection>.Add(KeyValuePair item)
{
Add(item.Key, item.Value);
}
///
/// Determines whether the OrderedDictionary<TKey,TValue> contains a specific key and value.
///
/// The KeyValuePair<TKey,TValue> structure to locate in the OrderedDictionary<TKey,TValue>.
/// if is found in the OrderedDictionary<TKey,TValue>; otherwise, .
bool ICollection>.Contains(KeyValuePair item)
{
return ((ICollection>)Dictionary).Contains(item);
}
///
/// Copies the elements of the OrderedDictionary<TKey,TValue> to an array of type , starting at the specified index.
///
/// The one-dimensional array of type KeyValuePair<TKey,TValue> that is the destination of the KeyValuePair<TKey,TValue> elements copied from the OrderedDictionary<TKey,TValue>. The array must have zero-based indexing.
/// The zero-based index in at which copying begins.
void ICollection>.CopyTo(KeyValuePair[] array, int arrayIndex)
{
((ICollection>)Dictionary).CopyTo(array, arrayIndex);
}
///
/// Removes a key and value from the dictionary.
///
/// The KeyValuePair<TKey,TValue> structure representing the key and value to remove from the OrderedDictionary<TKey,TValue>.
/// if the key and value represented by is successfully found and removed; otherwise, . This method returns if is not found in the OrderedDictionary<TKey,TValue>.
bool ICollection>.Remove(KeyValuePair item)
{
return Remove(item.Key);
}
}
}