using System;
|
|
using System.Collections;
|
|
using System.Collections.Generic;
|
|
|
|
namespace LeTai.TrueShadow
|
|
{
|
|
class IndexedSet<T> : IList<T>
|
|
{
|
|
readonly List<T> list = new List<T>();
|
|
readonly Dictionary<T, int> dict = new Dictionary<T, int>();
|
|
|
|
public void Add(T item)
|
|
{
|
|
dict.Add(item, list.Count);
|
|
list.Add(item);
|
|
}
|
|
|
|
public bool AddUnique(T item)
|
|
{
|
|
if (dict.ContainsKey(item))
|
|
return false;
|
|
|
|
dict.Add(item, list.Count);
|
|
list.Add(item);
|
|
|
|
return true;
|
|
}
|
|
|
|
public bool Remove(T item)
|
|
{
|
|
if (!dict.TryGetValue(item, out var index))
|
|
return false;
|
|
|
|
RemoveAt(index);
|
|
return true;
|
|
}
|
|
|
|
public void Remove(Predicate<T> match)
|
|
{
|
|
int i = 0;
|
|
while (i < list.Count)
|
|
{
|
|
T item = list[i];
|
|
if (match(item))
|
|
Remove(item);
|
|
else
|
|
i++;
|
|
}
|
|
}
|
|
|
|
public void Clear()
|
|
{
|
|
list.Clear();
|
|
dict.Clear();
|
|
}
|
|
|
|
public bool Contains(T item)
|
|
{
|
|
return dict.ContainsKey(item);
|
|
}
|
|
|
|
public void CopyTo(T[] array, int arrayIndex)
|
|
{
|
|
list.CopyTo(array, arrayIndex);
|
|
}
|
|
|
|
public int Count => list.Count;
|
|
|
|
public bool IsReadOnly => false;
|
|
|
|
public int IndexOf(T item)
|
|
{
|
|
if (dict.TryGetValue(item, out var index))
|
|
return index;
|
|
return -1;
|
|
}
|
|
|
|
public void Insert(int index, T item)
|
|
{
|
|
//We could support this, but the semantics would be weird. Order is not guaranteed..
|
|
throw new NotSupportedException(
|
|
"Random Insertion is semantically invalid, since this structure does not guarantee ordering.");
|
|
}
|
|
|
|
public void RemoveAt(int index)
|
|
{
|
|
T item = list[index];
|
|
dict.Remove(item);
|
|
if (index == list.Count - 1)
|
|
list.RemoveAt(index);
|
|
else
|
|
{
|
|
int replaceItemIndex = list.Count - 1;
|
|
T replaceItem = list[replaceItemIndex];
|
|
list[index] = replaceItem;
|
|
dict[replaceItem] = index;
|
|
list.RemoveAt(replaceItemIndex);
|
|
}
|
|
}
|
|
|
|
public T this[int index]
|
|
{
|
|
get => list[index];
|
|
set
|
|
{
|
|
T item = list[index];
|
|
dict.Remove(item);
|
|
list[index] = value;
|
|
dict.Add(item, index);
|
|
}
|
|
}
|
|
|
|
//Sorts the internal list, this makes the exposed index accessor sorted as well.
|
|
//But note that any insertion or deletion, can unorder the collection again.
|
|
public void Sort(Comparison<T> sortLayoutFunction)
|
|
{
|
|
//There might be better ways to sort and keep the dictionary index up to date.
|
|
list.Sort(sortLayoutFunction);
|
|
//Rebuild the dictionary index.
|
|
for (int i = 0; i < list.Count; ++i)
|
|
{
|
|
T item = list[i];
|
|
dict[item] = i;
|
|
}
|
|
}
|
|
|
|
|
|
public IEnumerator<T> GetEnumerator()
|
|
{
|
|
return list.GetEnumerator();
|
|
}
|
|
|
|
IEnumerator IEnumerable.GetEnumerator()
|
|
{
|
|
return GetEnumerator();
|
|
}
|
|
}
|
|
}
|