Maybe I'm slow, but isn't this the easiest implementation ever?
class SortedList<T> : List<T>
{
public new void Add(T item)
{
Insert(~BinarySearch(item), item);
}
}
http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx
Unfortunately, Add
wasn't overrideable so I had to new
it which isn't so nice when you have List<T> list = new SortedList<T>;
which I actually needed to do.... so I went ahead and rebuilt the whole thing...
class SortedList<T> : IList<T>
{
private List<T> list = new List<T>();
public int IndexOf(T item)
{
var index = list.BinarySearch(item);
return index < 0 ? -1 : index;
}
public void Insert(int index, T item)
{
throw new NotImplementedException("Cannot insert at index; must preserve order.");
}
public void RemoveAt(int index)
{
list.RemoveAt(index);
}
public T this[int index]
{
get
{
return list[index];
}
set
{
list.RemoveAt(index);
this.Add(value);
}
}
public void Add(T item)
{
list.Insert(~list.BinarySearch(item), item);
}
public void Clear()
{
list.Clear();
}
public bool Contains(T item)
{
return list.BinarySearch(item) >= 0;
}
public void CopyTo(T[] array, int arrayIndex)
{
list.CopyTo(array, arrayIndex);
}
public int Count
{
get { return list.Count; }
}
public bool IsReadOnly
{
get { return false; }
}
public bool Remove(T item)
{
var index = list.BinarySearch(item);
if (index < 0) return false;
list.RemoveAt(index);
return true;
}
public IEnumerator<T> GetEnumerator()
{
return list.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return list.GetEnumerator();
}
}
Or perhaps something like this is a more appropriate Remove
function...
public bool Remove(T item)
{
var index = list.BinarySearch(item);
if (index < 0) return false;
while (((IComparable)item).CompareTo((IComparable)list[index]) == 0)
{
if (item == list[index])
{
list.RemoveAt(index);
return true;
}
index++;
}
return false;
}
Assuming items can compare equal but not be equal...
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…