|
|
Comments and Discussions
|
|
 |
|
Hi,
Just a quick one for and when (if) you do an update, the link to Marc Clifton's article in Background is broken.
Cheers,
|
|
|
|
|
I don't know why but he didn't implement the set part, so I could not update the value of an item.
Here it is and it works fine for my needs. I thought it would be useful. 
IRNBRU
public object this[object key] {
get {
if (key == null){
throw new ArgumentNullException();
}
object result = null;
Lookup findItem = this.GetByKey(key);
if (findItem != null) {
result = findItem.Value;
}
return result;
}
set {
if (key == null){
throw new ArgumentNullException();
}
Lookup findItem = this.GetByKey(key);
if (findItem != null) {
findItem.Value = value;
}
}
}
|
|
|
|
|
|
Altyd lekker om Bloemfonten op CodeProject te sien!;P
|
|
|
|
|
Gooi Mielies 
|
|
|
|
|
It seems to me that one could use Lutz Roeder's .NET Reflector[^] and view the decompiled code for SortedList and make a few changes to sort by value instead. That way you don't have to worry about the performance issues, since, as Jared Utley pointed out, we already know SortedList is quite fast.
But still, a great solution to what's always been a vexing problem. I had been using a combination of Mike McPhail's Hashlist[^] and a ORDER BY clause in order to get my DropDownList options to order correctly.
|
|
|
|
|
howcheng wrote:
one could use Lutz Roeder's .NET Reflector[^] and view the decompiled code for SortedList and make a few changes to sort by value instead
I did this and here is the working code :
namespace Custom.Collections
{
using System;
using System.Reflection;
using System.Collections;
[Serializable]
public class SortedListByValue : IDictionary, ICollection, IEnumerable, ICloneable
{
// Methods
public SortedListByValue()
{
this.keys = new object[0x10];
this.values = new object[0x10];
this.comparer = new SortedByListDefaultComparer();
}
public SortedListByValue(IComparer comparer) : this()
{
if (comparer != null)
{
this.comparer = comparer;
}
}
public SortedListByValue(IDictionary d) : this(d, (IComparer) null)
{
}
public SortedListByValue(int initialCapacity)
{
if (initialCapacity < 0)
{
throw new ArgumentOutOfRangeException("initialCapacity"); //, Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
}
this.keys = new object[initialCapacity];
this.values = new object[initialCapacity];
this.comparer = new SortedByListDefaultComparer();
}
public SortedListByValue(IComparer comparer, int capacity) : this(comparer)
{
this.Capacity = capacity;
}
public SortedListByValue(IDictionary d, IComparer comparer) : this(comparer, (d != null) ? d.Count : 0)
{
if (d == null)
{
throw new ArgumentNullException("d"); //, Environment.GetResourceString("ArgumentNull_Dictionary"));
}
d.Keys.CopyTo(this.keys, 0);
d.Values.CopyTo(this.values, 0);
Array.Sort(this.keys, this.values, comparer);
this._size = d.Count;
}
public virtual void Add(object key, object value)
{
if (key == null)
{
throw new ArgumentNullException("key"); //, Environment.GetResourceString("ArgumentNull_Key"));
}
int num1 = Array.BinarySearch(this.values, 0, this._size, value, this.comparer);
if (num1 >= 0)
{
object[] objArray1 = new object[2] { this.GetKey(num1), key } ;
throw new ArgumentException("Cannot add duplicate key"); //(Environment.GetResourceString("Argument_AddingDuplicate__", objArray1));
}
this.Insert(~num1, key, value);
}
public virtual void Clear()
{
this.version++;
this._size = 0;
this.keys = new object[0x10];
this.values = new object[0x10];
}
public virtual object Clone()
{
SortedListByValue list1 = new SortedListByValue(this._size);
Array.Copy(this.keys, 0, list1.keys, 0, this._size);
Array.Copy(this.values, 0, list1.values, 0, this._size);
list1._size = this._size;
list1.version = this.version;
list1.comparer = this.comparer;
return list1;
}
public virtual bool Contains(object key)
{
return (this.IndexOfKey(key) >= 0);
}
public virtual bool ContainsKey(object key)
{
return (this.IndexOfKey(key) >= 0);
}
public virtual bool ContainsValue(object value)
{
return (this.IndexOfValue(value) >= 0);
}
public virtual void CopyTo(Array array, int arrayIndex)
{
if (array == null)
{
throw new ArgumentNullException("array"); //, Environment.GetResourceString("ArgumentNull_Array"));
}
if (array.Rank != 1)
{
throw new ArgumentException(); //Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
}
if (arrayIndex < 0)
{
throw new ArgumentOutOfRangeException("arrayIndex"); //, Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
}
if ((array.Length - arrayIndex) < this.Count)
{
throw new ArgumentException(); //Environment.GetResourceString("Arg_ArrayPlusOffTooSmall"));
}
for (int num1 = 0; num1 < this.Count; num1++)
{
DictionaryEntry entry1;
entry1 = new DictionaryEntry(this.keys[num1], this.values[num1]);
array.SetValue(entry1, (int) (num1 + arrayIndex));
}
}
private void EnsureCapacity(int min)
{
int num1 = (this.keys.Length == 0) ? 0x10 : (this.keys.Length * 2);
if (num1 < min)
{
num1 = min;
}
this.Capacity = num1;
}
public virtual object GetByIndex(int index)
{
if ((index < 0) || (index >= this._size))
{
throw new ArgumentOutOfRangeException("index"); //, Environment.GetResourceString("ArgumentOutOfRange_Index"));
}
return this.values[index];
}
public virtual IDictionaryEnumerator GetEnumerator()
{
return new SortedListByValue.SortedListEnumerator(this, 0, this._size, 3);
}
public virtual object GetKey(int index)
{
if ((index < 0) || (index >= this._size))
{
throw new ArgumentOutOfRangeException("index"); //, Environment.GetResourceString("ArgumentOutOfRange_Index"));
}
return this.keys[index];
}
public virtual IList GetKeyList()
{
if (this.keyList == null)
{
this.keyList = new KeyList(this);
}
return this.keyList;
}
public virtual IList GetValueList()
{
if (this.valueList == null)
{
this.valueList = new ValueList(this);
}
return this.valueList;
}
public virtual int IndexOfKey(object key)
{
if (key == null)
{
throw new ArgumentNullException("key"); //, Environment.GetResourceString("ArgumentNull_Key"));
}
int num1 = Array.BinarySearch(this.keys, 0, this._size, key, this.comparer);
if (num1 < 0)
{
return -1;
}
return num1;
}
public virtual int IndexOfValue(object value)
{
return Array.IndexOf(this.values, value, 0, this._size);
}
private void Insert(int index, object key, object value)
{
if (this._size == this.keys.Length)
{
this.EnsureCapacity(this._size + 1);
}
if (index < this._size)
{
Array.Copy(this.keys, index, this.keys, (int) (index + 1), (int) (this._size - index));
Array.Copy(this.values, index, this.values, (int) (index + 1), (int) (this._size - index));
}
this.keys[index] = key;
this.values[index] = value;
this._size++;
this.version++;
}
public virtual void Remove(object key)
{
int num1 = this.IndexOfKey(key);
if (num1 >= 0)
{
this.RemoveAt(num1);
}
}
public virtual void RemoveAt(int index)
{
if ((index < 0) || (index >= this._size))
{
throw new ArgumentOutOfRangeException("index"); //, Environment.GetResourceString("ArgumentOutOfRange_Index"));
}
this._size--;
if (index < this._size)
{
Array.Copy(this.keys, (int) (index + 1), this.keys, index, (int) (this._size - index));
Array.Copy(this.values, (int) (index + 1), this.values, index, (int) (this._size - index));
}
this.keys[this._size] = null;
this.values[this._size] = null;
this.version++;
}
public virtual void SetByIndex(int index, object value)
{
if ((index < 0) || (index >= this._size))
{
throw new ArgumentOutOfRangeException("index"); //, Environment.GetResourceString("ArgumentOutOfRange_Index"));
}
this.values[index] = value;
this.version++;
}
public static SortedListByValue Synchronized(SortedListByValue list)
{
if (list == null)
{
throw new ArgumentNullException("list");
}
return new SyncSortedList(list);
}
IEnumerator IEnumerable.GetEnumerator()
{
return new SortedListByValue.SortedListEnumerator(this, 0, this._size, 3);
}
public virtual void TrimToSize()
{
this.Capacity = this._size;
}
// Properties
public virtual int Capacity
{
get
{
return this.keys.Length;
}
set
{
if (value != this.keys.Length)
{
if (value < this._size)
{
throw new ArgumentOutOfRangeException("value"); //, Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity"));
}
if (value > 0)
{
object[] objArray1 = new object[value];
object[] objArray2 = new object[value];
if (this._size > 0)
{
Array.Copy(this.keys, 0, objArray1, 0, this._size);
Array.Copy(this.values, 0, objArray2, 0, this._size);
}
this.keys = objArray1;
this.values = objArray2;
}
else
{
this.keys = new object[0x10];
this.values = new object[0x10];
}
}
}
}
public virtual int Count
{
get
{
return this._size;
}
}
public virtual bool IsFixedSize
{
get
{
return false;
}
}
public virtual bool IsReadOnly
{
get
{
return false;
}
}
public virtual bool IsSynchronized
{
get
{
return false;
}
}
public virtual object this[object key]
{
get
{
int num1 = this.IndexOfKey(key);
if (num1 >= 0)
{
return this.values[num1];
}
return null;
}
set
{
if (key == null)
{
throw new ArgumentNullException("key"); //, Environment.GetResourceString("ArgumentNull_Key"));
}
int num1 = Array.BinarySearch(this.keys, 0, this._size, key, this.comparer);
if (num1 >= 0)
{
this.values[num1] = value;
this.version++;
}
else
{
this.Insert(~num1, key, value);
}
}
}
public virtual ICollection Keys
{
get
{
return this.GetKeyList();
}
}
public virtual object SyncRoot
{
get
{
return this;
}
}
public virtual ICollection Values
{
get
{
return this.GetValueList();
}
}
// Fields
private const int _defaultCapacity = 0x10;
private int _size;
private IComparer comparer;
private KeyList keyList;
private object[] keys;
private ValueList valueList;
private object[] values;
private int version;
// Nested Types
[Serializable]
private class KeyList : IList, ICollection, IEnumerable
{
// Methods
internal KeyList(SortedListByValue sortedList)
{
this.sortedList = sortedList;
}
public virtual int Add(object key)
{
throw new NotSupportedException(); //Environment.GetResourceString("NotSupported_SortedListNestedWrite"));
}
public virtual void Clear()
{
throw new NotSupportedException(); //Environment.GetResourceString("NotSupported_SortedListNestedWrite"));
}
public virtual bool Contains(object key)
{
return this.sortedList.Contains(key);
}
public virtual void CopyTo(Array array, int arrayIndex)
{
if ((array != null) && (array.Rank != 1))
{
throw new ArgumentException(); //Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
}
Array.Copy(this.sortedList.keys, 0, array, arrayIndex, this.sortedList.Count);
}
public virtual IEnumerator GetEnumerator()
{
return new SortedListByValue.SortedListEnumerator(this.sortedList, 0, this.sortedList.Count, 1);
}
public virtual int IndexOf(object key)
{
if (key == null)
{
throw new ArgumentNullException("key"); //, Environment.GetResourceString("ArgumentNull_Key"));
}
int num1 = Array.BinarySearch(this.sortedList.keys, 0, this.sortedList.Count, key, this.sortedList.comparer);
if (num1 >= 0)
{
return num1;
}
return -1;
}
public virtual void Insert(int index, object value)
{
throw new NotSupportedException(); //Environment.GetResourceString("NotSupported_SortedListNestedWrite"));
}
public virtual void Remove(object key)
{
throw new NotSupportedException(); //Environment.GetResourceString("NotSupported_SortedListNestedWrite"));
}
public virtual void RemoveAt(int index)
{
throw new NotSupportedException(); //Environment.GetResourceString("NotSupported_SortedListNestedWrite"));
}
// Properties
public virtual int Count
{
get
{
return this.sortedList._size;
}
}
public virtual bool IsFixedSize
{
get
{
return true;
}
}
public virtual bool IsReadOnly
{
get
{
return true;
}
}
public virtual bool IsSynchronized
{
get
{
return this.sortedList.IsSynchronized;
}
}
public virtual object this[int index]
{
get
{
return this.sortedList.GetKey(index);
}
set
{
throw new NotSupportedException(); //("NotSupported_KeyCollectionSet"));
}
}
public virtual object SyncRoot
{
get
{
return this.sortedList.SyncRoot;
}
}
// Fields
private SortedListByValue sortedList;
}
[Serializable]
private class SortedListEnumerator : IDictionaryEnumerator, IEnumerator, ICloneable
{
// Methods
internal SortedListEnumerator(SortedListByValue sortedList, int index, int count, int getObjRetType)
{
this.sortedList = sortedList;
this.index = index;
this.startIndex = index;
this.endIndex = index + count;
this.version = sortedList.version;
this.getObjectRetType = getObjRetType;
this.current = false;
}
public object Clone()
{
return base.MemberwiseClone();
}
public virtual bool MoveNext()
{
if (this.version != this.sortedList.version)
{
throw new InvalidOperationException(); //Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
}
if (this.index < this.endIndex)
{
this.key = this.sortedList.keys[this.index];
this.value = this.sortedList.values[this.index];
this.index++;
this.current = true;
return true;
}
this.key = null;
this.value = null;
this.current = false;
return false;
}
public virtual void Reset()
{
if (this.version != this.sortedList.version)
{
throw new InvalidOperationException(); //Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
}
this.index = this.startIndex;
this.current = false;
this.key = null;
this.value = null;
}
// Properties
public virtual object Current
{
get
{
if (!this.current)
{
throw new InvalidOperationException(); //Environment.GetResourceString("InvalidOperation_EnumOpCantHappen"));
}
if (this.getObjectRetType == 1)
{
return this.key;
}
if (this.getObjectRetType == 2)
{
return this.value;
}
return new DictionaryEntry(this.key, this.value);
}
}
public virtual DictionaryEntry Entry
{
get
{
if (this.version != this.sortedList.version)
{
throw new InvalidOperationException(); //Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
}
if (!this.current)
{
throw new InvalidOperationException(); //Environment.GetResourceString("InvalidOperation_EnumOpCantHappen"));
}
return new DictionaryEntry(this.key, this.value);
}
}
public virtual object Key
{
get
{
if (this.version != this.sortedList.version)
{
throw new InvalidOperationException(); //Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
}
if (!this.current)
{
throw new InvalidOperationException(); //Environment.GetResourceString("InvalidOperation_EnumOpCantHappen"));
}
return this.key;
}
}
public virtual object Value
{
get
{
if (this.version != this.sortedList.version)
{
throw new InvalidOperationException(); //Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
}
if (!this.current)
{
throw new InvalidOperationException(); //Environment.GetResourceString("InvalidOperation_EnumOpCantHappen"));
}
return this.value;
}
}
// Fields
private bool current;
internal const int DictEntry = 3;
private int endIndex;
private int getObjectRetType;
private int index;
private object key;
internal const int Keys = 1;
private SortedListByValue sortedList;
private int startIndex;
private object value;
internal const int Values = 2;
private int version;
}
[Serializable]
private class SyncSortedList : SortedListByValue
{
// Methods
internal SyncSortedList(SortedListByValue list)
{
this._list = list;
this._root = list.SyncRoot;
}
public override void Add(object key, object value)
{
lock (this._root)
{
this._list.Add(key, value);
}
}
public override void Clear()
{
lock (this._root)
{
this._list.Clear();
}
}
public override object Clone()
{
object obj1;
lock (this._root)
{
obj1 = this._list.Clone();
}
return obj1;
}
public override bool Contains(object key)
{
bool flag1;
lock (this._root)
{
flag1 = this._list.Contains(key);
}
return flag1;
}
public override bool ContainsKey(object key)
{
bool flag1;
lock (this._root)
{
flag1 = this._list.ContainsKey(key);
}
return flag1;
}
public override bool ContainsValue(object key)
{
bool flag1;
lock (this._root)
{
flag1 = this._list.ContainsValue(key);
}
return flag1;
}
public override void CopyTo(Array array, int index)
{
lock (this._root)
{
this._list.CopyTo(array, index);
}
}
public override object GetByIndex(int index)
{
object obj1;
lock (this._root)
{
obj1 = this._list.GetByIndex(index);
}
return obj1;
}
public override IDictionaryEnumerator GetEnumerator()
{
IDictionaryEnumerator enumerator1;
lock (this._root)
{
enumerator1 = this._list.GetEnumerator();
}
return enumerator1;
}
public override object GetKey(int index)
{
object obj1;
lock (this._root)
{
obj1 = this._list.GetKey(index);
}
return obj1;
}
public override IList GetKeyList()
{
IList list1;
lock (this._root)
{
list1 = this._list.GetKeyList();
}
return list1;
}
public override IList GetValueList()
{
IList list1;
lock (this._root)
{
list1 = this._list.GetValueList();
}
return list1;
}
public override int IndexOfKey(object key)
{
int num1;
lock (this._root)
{
num1 = this._list.IndexOfKey(key);
}
return num1;
}
public override int IndexOfValue(object value)
{
int num1;
lock (this._root)
{
num1 = this._list.IndexOfValue(value);
}
return num1;
}
public override void Remove(object key)
{
lock (this._root)
{
this._list.Remove(key);
}
}
public override void RemoveAt(int index)
{
lock (this._root)
{
this._list.RemoveAt(index);
}
}
public override void SetByIndex(int index, object value)
{
lock (this._root)
{
this._list.SetByIndex(index, value);
}
}
public override void TrimToSize()
{
lock (this._root)
{
this._list.TrimToSize();
}
}
// Properties
public override int Capacity
{
get
{
int num1;
lock (this._root)
{
num1 = this._list.Capacity;
}
return num1;
}
}
public override int Count
{
get
{
int num1;
lock (this._root)
{
num1 = this._list.Count;
}
return num1;
}
}
public override bool IsFixedSize
{
get
{
return this._list.IsFixedSize;
}
}
public override bool IsReadOnly
{
get
{
return this._list.IsReadOnly;
}
}
public override bool IsSynchronized
{
get
{
return true;
}
}
public override object this[object key]
{
get
{
object obj1;
lock (this._root)
{
obj1 = this._list[key];
}
return obj1;
}
set
{
lock (this._root)
{
this._list[key] = value;
}
}
}
public override object SyncRoot
{
get
{
return this._root;
}
}
// Fields
private SortedListByValue _list;
private object _root;
}
[Serializable]
private class ValueList : IList, ICollection, IEnumerable
{
// Methods
internal ValueList(SortedListByValue sortedList)
{
this.sortedList = sortedList;
}
public virtual int Add(object key)
{
throw new NotSupportedException(); //Environment.GetResourceString("NotSupported_SortedListNestedWrite"));
}
public virtual void Clear()
{
throw new NotSupportedException(); //Environment.GetResourceString("NotSupported_SortedListNestedWrite"));
}
public virtual bool Contains(object value)
{
return this.sortedList.ContainsValue(value);
}
public virtual void CopyTo(Array array, int arrayIndex)
{
if ((array != null) && (array.Rank != 1))
{
throw new ArgumentException(); //Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
}
Array.Copy(this.sortedList.values, 0, array, arrayIndex, this.sortedList.Count);
}
public virtual IEnumerator GetEnumerator()
{
return new SortedListByValue.SortedListEnumerator(this.sortedList, 0, this.sortedList.Count, 2);
}
public virtual int IndexOf(object value)
{
return Array.IndexOf(this.sortedList.values, value, 0, this.sortedList.Count);
}
public virtual void Insert(int index, object value)
{
throw new NotSupportedException(); //Environment.GetResourceString("NotSupported_SortedListNestedWrite"));
}
public virtual void Remove(object value)
{
throw new NotSupportedException(); //Environment.GetResourceString("NotSupported_SortedListNestedWrite"));
}
public virtual void RemoveAt(int index)
{
throw new NotSupportedException(); //Environment.GetResourceString("NotSupported_SortedListNestedWrite"));
}
// Properties
public virtual int Count
{
get
{
return this.sortedList._size;
}
}
public virtual bool IsFixedSize
{
get
{
return true;
}
}
public virtual bool IsReadOnly
{
get
{
return true;
}
}
public virtual bool IsSynchronized
{
get
{
return this.sortedList.IsSynchronized;
}
}
public virtual object this[int index]
{
get
{
return this.sortedList.GetByIndex(index);
}
set
{
this.sortedList.SetByIndex(index, value);
}
}
public virtual object SyncRoot
{
get
{
return this.sortedList.SyncRoot;
}
}
// Fields
private SortedListByValue sortedList;
}
}
public class SortedByListDefaultComparer : IComparer
{
public int Compare(object x,object y)
{
return 0;
}
}
}
|
|
|
|
|
There is an error in this code. You should have swapped the routines for IndexOfKey and IndexOfValue. The current way will give an error because the IComparer passed in is used for the keys and not the values.
|
|
|
|
|
There's also an error in the indexer for the key, because of the same issue. It should read:
public virtual object this[object key]
{
get
{
int num1 = this.IndexOfKey(key);
if (num1 >= 0)
{
return this.values[num1];
}
return null;
}
set
{
if (key == null)
{
throw new ArgumentNullException("key"); //, Environment.GetResourceString("ArgumentNull_Key"));
}
int num1 = Array.IndexOf(this.keys, value, 0, this._size);
if (num1 >= 0)
{
this.values[num1] = value;
this.version++;
}
else
{
this.Add(key, value);
}
}
}
|
|
|
|
|
Kudos for creating this class, it really works well for small datasets.
However, I bound this class to a ListBox with some 2190 key-value pairs and it crunches away incredibly long (around 20-30 seconds). Using a SortedList or a HashTable returns the results nearly instantaneously.
I can certainly take different approaches to suit my needs, and I know that perfomance was not the main goal of the exercise, but I wonder if there are some efficiency improvements that can be made to make this already good object even better.
:: Jared Utley
|
|
|
|
|
I used the following code on a Windows Form and saw that my class do indeed suffer from performance issues!
this._lookupList.Clear();
for (int i = 0; i < 2000; i++)
{
this._lookupList.Add(i.ToString(), System.Guid.NewGuid().ToString());
}
The main cause of this is the inappropriate placement of the code that sorts the internal array list. I have changed my code and now only sort in the following members in the LookupCollection.cs file:
- GetEnumerator (1)
- GetEnumerator (2)
- Keys
- Values
I think that this will solve some of your issues, I would be cool if you can test this out before I make a change to the article. Mail me for the source if you are uncertain where to make changes.
Thanx for your feedback!
Foulds.NET
|
|
|
|
|
You're right on to what I was thinking. I went a little further, however. I figured this object was all set up for "lazy" sorting. It never needs to be sorted until the user asks for it, right? In fact, I saw no reason why the items need be sorted at all unless the user wants them to be. So, the most straightforward approach I saw was the following in LookupCollection.cs:
1. Remove ALL instances of the Sort() function. (I believe this mainly occurs on this.mItems)
2. Create a separate function as follows:
public void Sort()
{
this.mItems.Sort();
}
Then you simply tell the object to sort itself.
LookupCollection lc = new LookupCollection();
while(datareader.Read())
{
lc.Add(datareader.GetValue(0), datareader.GetValue(1).ToString());
}
lc.Sort();
listbox.DataSource = lc;
listbox.DataValueField = "key";
listbox.DataValueField = "value";
listbox.DataBind();
listbox.Rows = 20;
On a dataset of around 2000+ records, the performance time went from 45 seconds (sorting in each routine) to about 4 seconds (sorting at the end).
:: Jared Utley
|
|
|
|
|
|
I wondered why it was not included in the standard collection class.
A very useful little class that works wonderfully!
|
|
|
|
|
|
|
 General  News  Suggestion  Question  Bug  Answer  Joke  Rant  Admin
|
An article on creating a custom collection like the SortedList that sort entries by value instead of by key.
| Type | Article |
| Licence | |
| First Posted | 6 May 2004 |
| Views | 110,926 |
| Bookmarked | 40 times |
|
|
Submit an article or tip
Post your Blog
