using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Ubiq
{
/// <summary>
/// A container of key-value-pairs that is ordered like a list, but also implements
/// the methods of a dictionary for fast look-up by key.
/// </summary>
/// <typeparam name="TKey">The type of the key.</typeparam>
/// <typeparam name="TValue">The type of the value.</typeparam>
public class IndexedList<TKey,TValue> :
IDictionary<TKey, TValue>,
IList<KeyValuePair<TKey, TValue>>
{
List<TKey> keys = new List<TKey>();
List<TValue> values = new List<TValue>();
Dictionary<TKey, int> index = new Dictionary<TKey, int>();
void ReIndex()
{
index.Clear();
for (int i = 0; i < keys.Count; ++i)
{
index[keys[i]] = i;
}
}
/// <summary>
/// Determines the index of a specific item in the <see cref="T:Ubiq.IndexedList`2"/>.
/// </summary>
/// <param name="item">The object to locate in the <see cref="T:Ubiq.IndexedList`2"/>.</param>
/// <returns>
/// The index of <paramref name="item"/> if found in the list; otherwise, -1.
/// </returns>
public int IndexOf(KeyValuePair<TKey, TValue> item)
{
int valueIndex;
if (index.TryGetValue(item.Key, out valueIndex))
{
if (values[valueIndex].Equals(item.Value))
{
return valueIndex;
}
}
return -1;
}
void InsertOnly(int index, KeyValuePair<TKey, TValue> item)
{
int keyIndex;
if (this.index.TryGetValue(item.Key, out keyIndex))
{
keys.RemoveAt(keyIndex);
values.RemoveAt(keyIndex);
if (keyIndex < index)
{
--index;
}
}
keys.Insert(index, item.Key);
values.Insert(index, item.Value);
}
/// <summary>
/// Inserts an item to the <see cref="T:Ubiq.IndexedList`2"/> at the specified index.
/// </summary>
/// <param name="index">The zero-based index at which <paramref name="item"/> should be inserted.</param>
/// <param name="item">The object to insert into the <see cref="T:Ubiq.IndexedList`2"/>.</param>
/// <exception cref="T:System.ArgumentOutOfRangeException">
/// <paramref name="index"/> is not a valid index in the <see cref="T:Ubiq.IndexedList`2"/>.
/// </exception>
/// <exception cref="T:System.NotSupportedException">
/// The <see cref="T:Ubiq.IndexedList`2"/> is read-only.
/// </exception>
public void Insert(int index, KeyValuePair<TKey, TValue> item)
{
InsertOnly(index, item);
ReIndex();
}
void RemoveOnly(int index)
{
keys.RemoveAt(index);
values.RemoveAt(index);
}
/// <summary>
/// Removes the <see cref="T:Ubiq.IndexedList`2"/> item at the specified index.
/// </summary>
/// <param name="index">The zero-based index of the item to remove.</param>
/// <exception cref="T:System.ArgumentOutOfRangeException">
/// <paramref name="index"/> is not a valid index in the <see cref="T:Ubiq.IndexedList`2"/>.
/// </exception>
/// <exception cref="T:System.NotSupportedException">
/// The <see cref="T:Ubiq.IndexedList`2"/> is read-only.
/// </exception>
public void RemoveAt(int index)
{
RemoveOnly(index);
ReIndex();
}
#region IDictionary<TKey,TValue> Members
/// <summary>
/// Adds an element with the provided key and value to the <see cref="T:Ubiq.IndexedList`2"/>.
/// </summary>
/// <param name="key">The object to use as the key of the element to add.</param>
/// <param name="value">The object to use as the value of the element to add.</param>
/// <exception cref="T:System.ArgumentNullException">
/// <paramref name="key"/> is null.
/// </exception>
/// <exception cref="T:System.ArgumentException">
/// An element with the same key already exists in the <see cref="T:Ubiq.IndexedList`2"/>.
/// </exception>
/// <exception cref="T:System.NotSupportedException">
/// The <see cref="T:Ubiq.IndexedList`2"/> is read-only.
/// </exception>
public void Add(TKey key, TValue value)
{
Remove(key);
int i = keys.Count;
keys.Add(key);
values.Add(value);
index.Add(key, i);
}
/// <summary>
/// Determines whether the <see cref="T:Ubiq.IndexedList`2"/> contains an element with the specified key.
/// </summary>
/// <param name="key">The key to locate in the <see cref="T:Ubiq.IndexedList`2"/>.</param>
/// <returns>
/// true if the <see cref="T:Ubiq.IndexedList`2"/> contains an element with the key; otherwise, false.
/// </returns>
/// <exception cref="T:System.ArgumentNullException">
/// <paramref name="key"/> is null.
/// </exception>
public bool ContainsKey(TKey key)
{
return index.ContainsKey(key);
}
/// <summary>
/// Gets an <see cref="T:Ubiq.IndexedList`2"/> containing the keys of the <see cref="T:Ubiq.IndexedList`2"/>.
/// </summary>
/// <value></value>
/// <returns>
/// An <see cref="T:Ubiq.IndexedList`2"/> containing the keys of the object that implements <see cref="T:Ubiq.IndexedList`2"/>.
/// </returns>
public ICollection<TKey> Keys
{
get
{
return keys;
}
}
/// <summary>
/// Removes the element with the specified key from the <see cref="T:Ubiq.IndexedList`2"/>.
/// </summary>
/// <param name="key">The key of the element to remove.</param>
/// <returns>
/// true if the element is successfully removed; otherwise, false. This method also returns false if <paramref name="key"/> was not found in the original <see cref="T:Ubiq.IndexedList`2"/>.
/// </returns>
/// <exception cref="T:System.ArgumentNullException">
/// <paramref name="key"/> is null.
/// </exception>
/// <exception cref="T:System.NotSupportedException">
/// The <see cref="T:Ubiq.IndexedList`2"/> is read-only.
/// </exception>
public bool Remove(TKey key)
{
int keyIndex;
if (index.TryGetValue(key, out keyIndex))
{
keys.RemoveAt(keyIndex);
values.RemoveAt(keyIndex);
ReIndex();
return true;
}
return false;
}
/// <summary>
/// Gets the value associated with the specified key.
/// </summary>
/// <param name="key">The key whose value to get.</param>
/// <param name="value">When this method returns, the value associated with the specified key, if the key is found; otherwise, the default value for the type of the <paramref name="value"/> parameter. This parameter is passed uninitialized.</param>
/// <returns>
/// true if the object that implements <see cref="T:Ubiq.IndexedList`2"/> contains an element with the specified key; otherwise, false.
/// </returns>
/// <exception cref="T:System.ArgumentNullException">
/// <paramref name="key"/> is null.
/// </exception>
public bool TryGetValue(TKey key, out TValue value)
{
int keyIndex;
if (index.TryGetValue(key, out keyIndex))
{
value = values[keyIndex];
return true;
}
value = default(TValue);
return false;
}
/// <summary>
/// Gets an <see cref="T:Ubiq.IndexedList`2"/> containing the values in the <see cref="T:Ubiq.IndexedList`2"/>.
/// </summary>
/// <value></value>
/// <returns>
/// An <see cref="T:Ubiq.IndexedList`2"/> containing the values in the object that implements <see cref="T:Ubiq.IndexedList`2"/>.
/// </returns>
public ICollection<TValue> Values
{
get
{
return values;
}
}
/// <summary>
/// Gets or sets the <see cref="TValue"/> with the specified key.
/// </summary>
/// <value></value>
public TValue this[TKey key]
{
get
{
return values[index[key]];
}
set
{
Add(key, value);
}
}
#endregion
#region ICollection<KeyValuePair<TKey,TValue>> Members
/// <summary>
/// Adds an item to the <see cref="T:Ubiq.IndexedList`2"/>.
/// </summary>
/// <param name="item">The object to add to the <see cref="T:Ubiq.IndexedList`2"/>.</param>
/// <exception cref="T:System.NotSupportedException">
/// The <see cref="T:Ubiq.IndexedList`2"/> is read-only.
/// </exception>
public void Add(KeyValuePair<TKey, TValue> item)
{
Add(item.Key, item.Value);
}
/// <summary>
/// Removes all items from the <see cref="T:Ubiq.IndexedList`2"/>.
/// </summary>
/// <exception cref="T:System.NotSupportedException">
/// The <see cref="T:Ubiq.IndexedList`2"/> is read-only.
/// </exception>
public void Clear()
{
keys.Clear();
values.Clear();
index.Clear();
}
/// <summary>
/// Determines whether the <see cref="T:Ubiq.IndexedList`2"/> contains a specific value.
/// </summary>
/// <param name="item">The object to locate in the <see cref="T:Ubiq.IndexedList`2"/>.</param>
/// <returns>
/// true if <paramref name="item"/> is found in the <see cref="T:Ubiq.IndexedList`2"/>; otherwise, false.
/// </returns>
public bool Contains(KeyValuePair<TKey, TValue> item)
{
int valueIndex;
if (index.TryGetValue(item.Key, out valueIndex))
{
if (values[valueIndex].Equals(item.Value))
{
return true;
}
}
return false;
}
/// <summary>
/// Copies the elements of the <see cref="T:Ubiq.IndexedList`2"/> to an <see cref="T:System.Array"/>, starting at a particular <see cref="T:System.Array"/> index.
/// </summary>
/// <param name="array">The one-dimensional <see cref="T:System.Array"/> that is the destination of the elements copied from <see cref="T:Ubiq.IndexedList`2"/>. The <see cref="T:System.Array"/> must have zero-based indexing.</param>
/// <param name="arrayIndex">The zero-based index in <paramref name="array"/> at which copying begins.</param>
/// <exception cref="T:System.ArgumentNullException">
/// <paramref name="array"/> is null.
/// </exception>
/// <exception cref="T:System.ArgumentOutOfRangeException">
/// <paramref name="arrayIndex"/> is less than 0.
/// </exception>
/// <exception cref="T:System.ArgumentException">
/// <paramref name="array"/> is multidimensional.
/// -or-
/// <paramref name="arrayIndex"/> is equal to or greater than the length of <paramref name="array"/>.
/// -or-
/// The number of elements in the source <see cref="T:Ubiq.IndexedList`2"/> is greater than the available space from <paramref name="arrayIndex"/> to the end of the destination <paramref name="array"/>.
/// -or-
/// Type <paramref name="T"/> cannot be cast automatically to the type of the destination <paramref name="array"/>.
/// </exception>
public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
{
for (int i = 0; i < keys.Count; ++i)
{
array[arrayIndex + i] = new KeyValuePair<TKey,TValue>(keys[i], values[i]);
}
}
/// <summary>
/// Gets the number of elements contained in the <see cref="T:Ubiq.IndexedList`2"/>.
/// </summary>
/// <value></value>
/// <returns>
/// The number of elements contained in the <see cref="T:Ubiq.IndexedList`2"/>.
/// </returns>
public int Count
{
get
{
return keys.Count;
}
}
/// <summary>
/// Gets a value indicating whether the <see cref="T:Ubiq.IndexedList`2"/> is read-only.
/// </summary>
/// <value></value>
/// <returns>true if the <see cref="T:Ubiq.IndexedList`2"/> is read-only; otherwise, false.
/// </returns>
public bool IsReadOnly
{
get
{
return false;
}
}
/// <summary>
/// Removes the first occurrence of a specific object from the <see cref="T:Ubiq.IndexedList`2"/>.
/// </summary>
/// <param name="item">The object to remove from the <see cref="T:Ubiq.IndexedList`2"/>.</param>
/// <returns>
/// true if <paramref name="item"/> was successfully removed from the <see cref="T:Ubiq.IndexedList`2"/>; otherwise, false. This method also returns false if <paramref name="item"/> is not found in the original <see cref="T:Ubiq.IndexedList`2"/>.
/// </returns>
/// <exception cref="T:System.NotSupportedException">
/// The <see cref="T:Ubiq.IndexedList`2"/> is read-only.
/// </exception>
public bool Remove(KeyValuePair<TKey, TValue> item)
{
int valueIndex;
if (index.TryGetValue(item.Key, out valueIndex))
{
if (values[valueIndex].Equals(item.Value))
{
index.Remove(item.Key);
keys.RemoveAt(valueIndex);
values.RemoveAt(valueIndex);
ReIndex();
return true;
}
}
return false;
}
#endregion
#region IEnumerable<KeyValuePair<TKey,TValue>> Members
/// <summary>
/// Returns an enumerator that iterates through the collection.
/// </summary>
/// <returns>
/// A <see cref="T:System.Collections.Generic.IEnumerator`1"/> that can be used to iterate through the collection.
/// </returns>
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
for (int i = 0; i < keys.Count; ++i)
{
yield return new KeyValuePair<TKey, TValue>(keys[i], values[i]);
}
}
#endregion
#region IEnumerable Members
/// <summary>
/// Returns an enumerator that iterates through a collection.
/// </summary>
/// <returns>
/// An <see cref="T:System.Collections.IEnumerator"/> object that can be used to iterate through the collection.
/// </returns>
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return ((IEnumerable<KeyValuePair<TKey, TValue>>)this).GetEnumerator();
}
#endregion
#region IList<KeyValuePair<TKey,TValue>> Members
/// <summary>
/// Gets or sets the <see cref="T:System.Collections.Generic.KeyValuePair`2;"/> at the specified index.
/// </summary>
/// <value></value>
KeyValuePair<TKey, TValue> IList<KeyValuePair<TKey, TValue>>.this[int index]
{
get
{
return new KeyValuePair<TKey, TValue>(keys[index], values[index]);
}
set
{
RemoveOnly(index);
InsertOnly(index, value);
ReIndex();
}
}
#endregion
}
}
Submit an article or tip