Sorting and non-unique keys

[garyhoran]

Hi Guys,

I have a collection that contains various attributes (stuff like
strings, DateTime and Timespan) . I would like to access the collection
in various orders at different points in the application ie sometimes I
want to cycle through the values in the collection in DateTime order
while at other times in TimeSpan order.

Ideally I would like multiple keys - such as Timespan within DateTime
order but maybe that is asking too much.

Also some of the keys I would like to use are not unique.

So I guess I have three questions

1. Whats the best way of sorting a collection in general
2. Is there anyway to sort with multiple keys
3. Is there any way to do sorts with non-unique keys

Would really appreciate any info you guys could give me.

Regards,

Gary

 

[> Adrian]

Would it be an idea not to have just one data collection,
but to have, in addition, several key collections that you
can sort and that give access to your data collection?

Adrian.

 

[Cor Ligthert [MVP]]

Gary,

You can use a sorted list.

If you have more keys, you can create more in a way that there is one that
holds the data and others which holds the references to that one in the key
value pair.

Cor

 

[garyhoran]

But a sorted list requires a unique key right?

Any options for non unique keys?

Gary

 

[> Adrian]

Read them sequentially, or make chains, i.e.,
have a field that refers key x to the next key x.
Adrian.

 

[> Adrian]

Re non unique keys

Another option might be to write a binary sort routine.
Then go for the key and see if there are any data items
before or after the retrieved data item that have the same
key value, and also extract those data items.

Adrian.

 

[Rick Lones]

Hi Guys,

I have a collection that contains various attributes (stuff like
strings, DateTime and Timespan) . I would like to access the collection
in various orders at different points in the application ie sometimes I
want to cycle through the values in the collection in DateTime order
while at other times in TimeSpan order.

Ideally I would like multiple keys - such as Timespan within DateTime
order but maybe that is asking too much.

Also some of the keys I would like to use are not unique.

So I guess I have three questions

1. Whats the best way of sorting a collection in general

Depends on your constraints and requirements, such as those you indicate below.

2. Is there anyway to sort with multiple keys

Absolutely - but I think you mean compound keys rather than multiple. Here is
one from a real-world application which works by defining a class (or struct) to
contain the data members of the compound key and then implements IComparable to
provide a custom sort:

/// <summary>
/// CategorySetMemberKey: sorts by category id within category set id
/// </summary>
public class CSMKey : IComparable
{
public long CategorySetID;
public long CategoryID;

public CSMKey(long setid, long catid)
{
this.CategorySetID = setid;
this.CategoryID = catid;
}

public int CompareTo(object obj)
{
int highorder = this.CategorySetID.CompareTo(((CSMKey)obj).CategorySetID);
if(highorder != 0)
return highorder;
else
return this.CategoryID.CompareTo(((CSMKey)obj).CategoryID);
}
}

The resulting compound key can be used as the key portion of any IDictionary
(e.g., Hashtable or SortedList) as long as uniqueness of the overall compound
key is maintained.

Notes:
1. The compounding can easily be extended to more than 2 levels.
2. In the above example both members happen to be long ints, but the types of
the members can be mixed in any way as long as each member is a type which is
IComparable. (In particular, they could be strings or DateTime structs or
TimeSpan structs.)

3. Is there any way to do sorts with non-unique keys

One obvious trick would be similar to the above - make a unique compound key by
appending a sequence number in a lower-order member. Depending on your
requirements that may suffice.


HTH,
-rick-

 

[Cor Ligthert [MVP]]

Gary,

Than take the datatable in combination with the defaultview (inbuild
dataview).

You can than sort on every field in every direction and in every
combination.

Cor

 

[Dave Sexton]

Hi Rick,

The resulting compound key can be used as the key portion of any IDictionary
(e.g., Hashtable or SortedList) as long as uniqueness of the overall
compound key is maintained.

Your CSMKey class cannot be used to key a Hashtable or Dictionary unless you
make it a struct. Or you can just override Equals and GetHashCode; although,
if you override Equals then CSMKey should probably be an immutable struct
anyway.

Your current implementation will work with a SortedList because that class
doesn't use the GetHashCode method - it requires its keys to implement
IComparable. Hashtable and the generic Dictionary class (2.0 framework) do
not use IComparable implementations, they use the GetHashCode and Equals
methods.

 

[Rick Lones]

Hi Rick,


Your CSMKey class cannot be used to key a Hashtable or Dictionary unless you
make it a struct. Or you can just override Equals and GetHashCode; although,
if you override Equals then CSMKey should probably be an immutable struct
anyway.

Your current implementation will work with a SortedList because that class
doesn't use the GetHashCode method - it requires its keys to implement
IComparable. Hashtable and the generic Dictionary class (2.0 framework) do
not use IComparable implementations, they use the GetHashCode and Equals
methods.

Hi Dave,

Wow, I had no idea. I just reviewed a module of mine which holds some three
dozen collections - Arraylists, Hashtables and SortedLists - and indeed the
compound key trick was only used with some of the SortedLists. In hindsight it
makes total sense of course that IComparable would not be relevant to Hashtable
keys.

Thanks for pointing this out, you probably saved me some head-scratching time in
the future . . .

Regards,
-rick-

 

[sloan]

See

http://sholliday.spaces.live.com/blog/ 6/19/2006 Advanced
IComparer // Sorting on Multiple Values

 

[sloan]

See:


http://sholliday.spaces.live.com/blog/ 6/19/2006 Advanced
IComparer // Sorting on Multiple Values