Alternative to KeyedByTypeCollection in Mono .Net

I need a factory to create singletons. Usually I would do this with something similar to…

public class Factory<T>
{
    readonly KeyedByTypeCollection<T> singletons = new KeyedByTypeCollection();

    public U GetSingleton<U>() where U : T, new()
    {
        if (!singletons.Contains(typeof(U)))
        {
            singletons.Add(new U());
        }

        return (U)singletons[typeof(U)];
    }
}

This would be the ideal method, as the type of the value is the key. This provides fast search and makes it so only one object of each class type can be in the collection.

However, it doesn’t look like Mono has KeyedByTypeCollection, and I can’t recreate it because it doesn’t have KeyedCollection either.

What is an alternative method in Mono for a factory that creates singletons with unique types?

Also note, I need an alternative that does not rely on reflection. I’m not asking for a ton of code, just a guide in the right direction because I’m not finding much about this on Google.

Thanks @dr3th for pointing me in the right direction. I ended up looking at a lot of .Net source code and learning how some things work under the hood.

Anyway, here is my implementation of a list with unique types. I tried to keep the operation times as constant as possible. By using a dictionary, its operation times are faster than List. Comments in code saying T(n)~=O(1) means that the method time approaches constant, because it uses the dictionary to find the index. This all theoretical though. If anyone has a need for this class, they can test performance.

As a side note, I have found that

Type == Type

and

Type.Equals(Type)

are the same.

Because the default IEqualityComparer for dictionaries uses the most overridden IEqualityComparer.Equals() or Object.Equals(), the dictionary used in my code does comparisons automatically with Type.Equals().

If someone wanted to have equality of types based on derived types, they would need to provide their own IEqualityComparer in the constructor to the dictionary. They would also have to replace all the Type == Type that I use throughout, with Type.IsSubclassOf(Type).

Here is the list class…
using System;
using System.Collections.Generic;

public class UniqueTypeList<T> : IList<T> where T : class
{
	// Stores item types and their index in itemList.
	Dictionary<Type, int> typeDictionary = new Dictionary<Type, int>();

	// The wrapped list.
	List<T> itemList = new List<T>();

	// Used by Enumerator to validate that this UniqueTypeList<T> hasn't changed.
	int version = 0;

	// Gets or sets the item with type.
	public T this[Type type]
	{
		// T(n)~=O(1)
		get
		{
			int index;

			if (!typeDictionary.TryGetValue(type, out index))
			{
				throw new KeyNotFoundException(String.Format("The list doesn't contain an item of type {0}.", type));
			}
			
			return itemList[index];
		}
		
		// T(n)~=O(1)
		set
		{
			int index;

			if (typeDictionary.TryGetValue(type, out index))
			{
				itemList[index] = value;
				version++;
			}
			else
			{
				Add(value);
			}
		}
	}

	// Checks if the list contains an item with type.
	// T(n)~=O(1)
	public bool Contains(Type type)
	{
		return typeDictionary.ContainsKey(type);
	}

	// Removes the item with type.
	// T(n)=O(n)
	public bool Remove(Type type)
	{
		int index;
		
		if (typeDictionary.TryGetValue(type, out index))
		{
			typeDictionary.Remove(type);
			itemList.RemoveAt(index);
			version++;
			return true;
		}
		
		return false;
	}

	// Gets the enumerator.
	public Enumerator GetEnumerator()
	{
		return new Enumerator(this);
	}

	// A custom IEnumerator<T> is used to perform version checking against both wrapped generic collections.
	public class Enumerator : IEnumerator<T>
	{
		UniqueTypeList<T> list;
		int index;
		int version;
		T current;

		// Constructs this enumerator from a UniqueTypeList<T>.
		public Enumerator(UniqueTypeList<T> list)
		{
			this.list = list;
			index = 0;
			version = list.version;
			current = null;
		}

		// Checks if this enumerator has not been modified.
		void ValidateVersion()
		{
			if (list.version != version)
			{
				throw new InvalidOperationException("The Enumerator has been modified, and is no longer valid.");
			}
		}

		#region IEnumerator<T> implementation

		// Gets the current item in this enumerator.
		public T Current
		{
			get
			{
				return current;
			}
		}

		#endregion

		#region IEnumerator implementation

		// Implemented for legacy code.
		Object System.Collections.IEnumerator.Current
		{
			get
			{
				if (index == 0 || index == list.itemList.Count + 1)
				{
					throw new InvalidOperationException("The Enumerator has not been started with MoveNext(), or has reached the end.");
				}
				
				return Current;
			}
		}

		// Moves the current item to the next item in this enumerator.
		public bool MoveNext()
		{
			ValidateVersion();

			if (index < list.itemList.Count)
			{
				current = list.itemList[index++];
				return true;
			}

			current = null;
			index++;
			return false;
		}

		// Reset this enumerator.
		public void Reset()
		{
			ValidateVersion();
			current = null;
			index = 0;
		}

		#endregion
		
		#region IDisposable implementation

		// Does not use unmanaged resources.
		public void Dispose()
		{
		}
		
		#endregion

	}

	#region IList<T> implementation

	// Gets or sets the item with index.
	public T this[int index]
	{
		// T(n)=O(1)
		get
		{
			if (index < 0 || index >= itemList.Count)
			{
				throw new ArgumentOutOfRangeException("index", "The index is outside the range of the list.");
			}

			return itemList[index];
		}

		// T(n)~=O(1)
		set
		{
			if (index < 0 || index >= itemList.Count)
			{
				throw new ArgumentOutOfRangeException("index", "The index is outside the range of the list.");
			}

			Type oldType = itemList[index].GetType();
			Type newType = value.GetType();

			if (oldType != newType)
			{
				if (Contains(newType))
				{
					throw new ArgumentException(String.Format("The list already contains a type of {0}.", newType), "value");
				}

				typeDictionary.Remove(oldType);
				typeDictionary.Add(newType, index);
			}

			itemList[index] = value;
			version++;
		}
	}

	// Gets the index of item in the list.
	// T(n)~=O(1)
	public int IndexOf(T item)
	{
		int index;

		if (typeDictionary.TryGetValue(item.GetType(), out index))
		{
			return index;
		}

		return -1;
	}

	// Inserts item into the list at index.
	// T(n)=O(n)
	public void Insert(int index, T item)
	{
		if (index < 0 || index > itemList.Count)
		{
			throw new ArgumentOutOfRangeException("index", "The index is outside the range of the list.");
		}
		else if (index == itemList.Count)
		{
			Add(item);
		}
		else
		{
			Type type = item.GetType();
			
			if (Contains(type))
			{
				throw new ArgumentException(String.Format("The list already contains a type of {0}.", type), "item");
			}
			
			typeDictionary.Add(type, index);
			itemList.Insert(index, item);
			version++;
		}
	}

	// Removes item from the list at index.
	// T(n)=O(n)
	public void RemoveAt(int index)
	{
		if (index < 0 || index >= itemList.Count)
		{
			throw new ArgumentOutOfRangeException("index", "The index is outside the range of the list.");
		}

		Type type = itemList[index].GetType();
		typeDictionary.Remove(type);
		itemList.RemoveAt(index);
		version++;
	}

	#endregion

	#region ICollection<T> implementation

	// Gets the number of items in the list.
	// T(n)=O(1)
	public int Count
	{
		get
		{
			return itemList.Count;
		}
	}

	// The list is always not read-only.
	// T(n)=O(1)
	public bool IsReadOnly
	{
		get
		{
			return false;
		}
	}

	// Adds item to the end of the list.
	// T(n)~=O(1)
	public void Add(T item)
	{
		Type type = item.GetType();

		if (Contains(type))
		{
			throw new ArgumentException(String.Format("The list already contains a type of {0}.", type), "item");
		}

		typeDictionary.Add(type, itemList.Count);
		itemList.Add(item);
		version++;
	}

	// Clears the list.
	// T(n)=O(1)
	public void Clear()
	{
		typeDictionary = new Dictionary<Type, int>();
		itemList = new List<T>();
		version++;
	}

	// Checks if the list containes item.
	// T(n)=O(n)
	public bool Contains(T item)
	{
		return itemList.Contains(item);
	}

	// Copies the list to array.
	// T(n)=O(n)
	public void CopyTo(T[] array, int arrayIndex)
	{
		itemList.CopyTo(array, arrayIndex);
	}

	// Removes item.
	// T(n)=O(n)
	public bool Remove(T item)
	{
		if (itemList.Remove(item))
		{
			Type type = item.GetType();
			typeDictionary.Remove(type);
			version++;
			return true;
		}

		return false;
	}

	#endregion

	#region IEnumerable<T> implementation

	// Gets the enumerator.
	IEnumerator<T> IEnumerable<T>.GetEnumerator()
	{
		return new Enumerator(this);
	}

	#endregion

	#region IEnumerable implementation

	// Gets the enumerator.
	System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
	{
		return new Enumerator(this);
	}

	#endregion

}

And here is the test class with a few exceptions commented out…

using UnityEngine;
using System.Collections;

public class TestClasses : UnityEngine.MonoBehaviour
{
	void Start()
	{
		UniqueTypeList<TestBase> list = new UniqueTypeList<TestBase>();
		list.Add(new TestA());
		list.Add(new TestA1());
		list.Add(new TestB());
		list.Add(new TestB1());

		foreach (TestBase item in list)
		{
			item.Print();
		}

		// Throws exception
		// list.Add(new TestA1());

		foreach (TestBase item in list)
		{
			// Throws exception
			// Debug.Log(list.Remove(item.GetType()));
		}
	}
}

/*
 * The list of TestBase should be able any combination of child classes, where each child class is not the same.
 * So the following is valid: A, B, A1, B1
 * But this is not: A, A1, A1
 */

public abstract class TestBase
{
	public virtual void Print()
	{
		Debug.Log("TestBase");
	}
}

public class TestA : TestBase
{
	public override void Print()
	{
		Debug.Log("TestA");
	}
}

public class TestB : TestBase
{
	public override void Print()
	{
		Debug.Log("TestB");
	}
}

public class TestA1 : TestA
{
	public override void Print()
	{
		Debug.Log("TestA1");
	}
}

public class TestB1 : TestB
{
	public override void Print()
	{
		Debug.Log("TestB1");
	}
}