TLDR; replace your List by an IndexableList, code in on github.
We needed to code a List (that cares about the order of its elements) which was also able to retreive an element by its unique ID, very fastly. So we’re sharing this code to you if you need a such enhanced Indexed List, that integrates with Generics and implements IEnumerable.
During the development of Silicon City, performances can be the most critical part of our code, and a good architecture needs to be planned early and in a smart way.
Sadly this is not always the case and some innocent code becomes the beginning of new mechanics.
We are using Lists of waypoints to manage paths for our citizens, navigating in their city. Originally stored in a Generic.List<Waypoint>, the elements would define the path the citizen would take to go from point A to point B. The requirements are the following:
- The List must take care of the order of the elements, to have an index somewhere tracking where we’re currently located in the path
- The List must be able to grow or srink when path needs to be recalculated
- A shortcut can be added in the middle of the run, so that would remove a range of waypoints before inserting a new shorter range
- We should be very fast to know if a given waypoint is within the List
- We should be able to extract a waypoint from the list, by its position or by it’s unique key
- Supports IEnumerable<T> and List<T> methods
Yes, one important point is that our waypoints have unique keys, but one can technically be added twice in the List (in which case the path is most likely simplifiable).
To keep the code clean and optimize the changes, we made a new List-like class that would override all the usual methods of a List<T> to match the existing.
public class IndexableList<TKey, TValue> : IEnumerable<TValue>, IEnumerable
where TKey : IEquatable<TKey>
where TValue : IIndexable<TKey>
{
}The IndexableList depends on two types: TKey for the tye of the elements unique key, and TValue the type of our elements. It also states that TKey must implement the interface IEquatable, which means the function Equals(). This is already the case for String or Guid. As well, the elements of type TValue must implement the interface IIndexable:
/// <summary>
/// The class that depends on this Interface must return a getter (Key) that return a unique key from which an instance of this object will be indexed.
/// </summary>
/// <typeparam name="TKey">Type of the unique key of the object to index</typeparam>
public interface IIndexable<TKey>
where TKey : IEquatable<TKey>
{
/// <summary>
/// How to read the key from this IIndexable item.
/// </summary>
TKey Key { get; }
}An exemple of implementation of this interface could look like:
namespace Polycorne.SiliconCity.Mechanics.Navigation.Waypoints
{
public class Waypoint: IEquatable<Waypoint>, IIndexable<Guid>
{
[DataMember]
public Guid UID { get; private set; }
// Implementation of IIndexable's Key
public Guid Key => this.UID;
}
}Here’s how nos the IndexableList can be used:
public IndexableList<Guid, Waypoint> Path = new IndexableList<Guid, Waypoint>();
Path.Add(origin);
Path.AddRange(nextwaypoints);
Path.Add(destination);
if(Path.Contains(destination))
{
Path.Remove(destination);
}The main idea of this class, is to very quickly run the Contains() operation. this is why the class has both an internal list and a dictionary. It also come with two optional settings, IndexNullValues and AllowNonUniqueKey that can be respectively turned on or off.
/// <summary>
/// The List where elements are added. Classic Generic list.
/// </summary>
private List<TValue> _list;
/// <summary>
/// The Key-indexed dictionary. A replication of <seealso cref="_list"/>, but for indexation.
/// </summary>
private Dictionary<TKey, TValue> _IndexableList;
/// <summary>
/// Set to false, to prevent adding a null value to the list because it would lack the key counter part.
/// Set to True to force it. This may lead into Exceptions, getting a key from a null Object.
/// </summary>
public bool IndexNullValues = false;
/// <summary>
/// Optional to prevent several items to have the same key.
/// Default value: true, this is how a Generic.List would behave.
/// If set to True, this will decrease a bit the performances upon item removal, but might be very helpful to replace a List<T> object.
/// When manipulating extra large amounts of records and not caring about which item to get as long as they identify to their Key.
/// </summary>
public bool AllowNonUniqueKey = true;Here is the full code of the first version of both classes, IndexedList and IIndexable. This article might not be maintained if the code evolves.
You can find the latest version of this code on github here: https://github.com/geck1942/indexablelist. If someone can try a benchmark of the performances I’d be very happy to see it and try to improve the array. There is room for improvements to store duplicates objects in a separate list.
/// <summary>
///
/// IndexableList Extends the Generic.List class and retreive objects faster with a hidden dictionary.
/// Objects stored must implement the IIndexable interface.
/// ----
/// If an item is added to the list but its key has been added already. This happens usually with a standard List.
/// The key dictionary is not updated, but onRemove, it will look for another item with the same key to index at
/// </summary>
/// <typeparam name="TKey">Type of the Key on which items are indexed. Must implement IEquatable</typeparam>
/// <typeparam name="TValue">Items of the List Type</typeparam>
public class IndexableList<TKey, TValue> : IEnumerable<TValue>, IEnumerable
where TKey : IEquatable<TKey>
where TValue : IIndexable<TKey>
{
/// <summary>
/// The List where elements are added. Classic Generic list.
/// </summary>
private List<TValue> _list;
/// <summary>
/// The Key-indexed dictionary. A replication of <seealso cref="_list"/>, but for indexation.
/// </summary>
private Dictionary<TKey, TValue> _IndexableList;
/// <summary>
/// Set to false, to prevent adding a null value to the list because it would lack the key counter part.
/// Set to True to force it. This may lead into Exceptions, getting a key from a null Object.
/// </summary>
public bool IndexNullValues = false;
/// <summary>
/// Optional to prevent several items to have the same key.
/// Default value: true, this is how a Generic.List would behave.
/// If set to True, this will decrease a bit the performances upon item removal, but might be very helpful to replace a List<T> object.
/// When manipulating extra large amounts of records and not caring about which item to get as long as they identify to their Key.
/// </summary>
public bool AllowNonUniqueKey = true;
/// <summary>
/// Main constructor.
/// </summary>
public IndexableList()
{
this._list = new List<TValue>();
this._IndexableList = new Dictionary<TKey, TValue>();
}
/// <summary>
/// Initialize with an Array
/// </summary>
/// <param name="InitialArray"></param>
public IndexableList(List<TValue> InitialArray)
: this()
{
if (InitialArray != null && InitialArray.Any())
this.AddRange(InitialArray);
}
#region IEnumerable & List Methods
/// <summary>
/// Finds quickly if an item that can be found with a unique Key is in the list.
/// The main goal of this class is here, using an indexed dictionary over a simple List.
/// </summary>
/// <param name="ComparableItem">The item to delete, at least the one with that <seealso cref="IIndexable{TKey}.Key">Key</seealso></param>
/// <returns>True if an item with the same key has been found</returns>
public bool Contains(TValue ComparableItem)
{
return this._IndexableList.ContainsKey(ComparableItem.Key);
}
/// <summary>
/// Adds an item to the list. If an item with the same key exists and AllowNonUniqueKey permits it, it will be added anyway.
/// </summary>
/// <param name="newItem">The item to add to the list</seealso></param>
public void Add(TValue newItem)
{
if (IndexNullValues || newItem != null)
{
if (this._IndexableList.ContainsKey(newItem.Key))
{
if(AllowNonUniqueKey)
this._list.Add(newItem);
}
else
{
this._list.Add(newItem);
this._IndexableList.Add(newItem.Key, newItem);
}
}
}
/// <summary>
/// Adds a list of items to the list. If AllowNonUniqueKey permits it and any of these items share the same key as another items, it will be added anyway.
/// </summary>
/// <param name="newItems">The items to add to the list</seealso></param>
public void AddRange(IEnumerable<TValue> newItems)
{
if (newItems != null)
foreach (var newItem in newItems)
this.Add(newItem);
}
/// <summary>
/// Removes the item from the list. It will match the first item with that key.
/// </summary>
/// <param name="oldItem">The Item to remove</param>
public void Remove(TValue oldItem)
{
this._list.Remove(oldItem);
if (IndexNullValues || oldItem != null)
{
// remove from dictionary
this._IndexableList.Remove(oldItem.Key);
// if any item remains, adds back any other item with that key to keep stuff being found;
if(AllowNonUniqueKey)
{
// now find any other item with that key
var anyRemainingItemWithThisKey = this._list.FirstOrDefault(othrItem => othrItem.Key.Equals(oldItem.Key));
// and add it back ad indexed in dictionary
if (anyRemainingItemWithThisKey != null)
this._IndexableList.Add(oldItem.Key, anyRemainingItemWithThisKey);
}
}
}
/// <summary>
/// Remove element at the index of the List
/// </summary>
public void RemoveAt(int index)
{
// remove value by its index
this.Remove(this._list[index]);
}
/// <summary>
/// Remove n elements from a position in the list
/// </summary>
public void RemoveRange(int index, int count)
{
for (int i = 0; i < count && this._list.Count() > index; i++)
this.RemoveAt(index);
}
public int Count()
{
return this._list.Count();
}
public bool Any()
{
return this._list.Count() > 0;
}
public TValue First()
{
if (this._list.Any())
return this._list[0];
else
return default(TValue);
}
public TValue ElementAt(int index)
{
return this._list.ElementAt(index);
}
public List<TValue> ToList()
{
return this._list;
}
public IEnumerator<TValue> GetEnumerator()
{
return _list.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return _list.GetEnumerator();
}
#endregion
}
/// <summary>
/// The class that depends on this Interface must return a getter (Key) that return a unique key from which an instance of this object will be indexed.
/// </summary>
/// <typeparam name="TKey"></typeparam>
public interface IIndexable<TKey>
where TKey : IEquatable<TKey>
{
/// <summary>
/// How to read the key from this IIndexable item.
/// </summary>
TKey Key { get; }
}