Sorting a Dictionary by Property

[henry.lee.jr]

Looking for a best approach to the following situation:

I want to create an array of objects that have an ID property and a
Priority property. The trick is that I want to leverage the power of a
Dictionary type object so that I can reference the items by their ID,
like so:

string n = MyObject("2468").Name
int p = MyObject("2468").Priority

At the same time, I also need to loop through these items in an order
that is by Priority.

I would love to simply use a foreach loop, but I believe in the past
when I have done this with a Dictionary object, the order of the
foreach loop is determined by the compiler, and not the order items
were added using .Add()

This is probably a fairly simple question, so thanks in advance!

 

[Scott Seligman]

Looking for a best approach to the following situation:

I want to create an array of objects that have an ID property and a
Priority property. The trick is that I want to leverage the power of a
Dictionary type object so that I can reference the items by their ID,
like so:

Use a SortedDictionary and implement IComparable<> on your object.

 

[henry.lee.jr]

Use a SortedDictionary and implement IComparable<> on your object.

Thanks for the start in the right direction. I am seeing a lot of
examples out there of IComparable ... but a lot of these examples are
using the key as how they want to sort, so I am still not entirely
sure of how to create a SortedDictionary using a non-key property of
my class objects as the sort (if that is even possible). Can someone
cite an example or whip up a few lines of example?

Let's assume I have class with a property ID (string in this case),
and another property called Priority, and I want this dictionary
sorted by Priority, but callable by ID.

Thanks!

 

[henry.lee.jr]

Thanks for the start in the right direction. I am seeing a lot of
examples out there of IComparable ... but a lot of these examples are
using the key as how they want to sort, so I am still not entirely
sure of how to create a SortedDictionary using a non-key property of
my class objects as the sort (if that is even possible). Can someone
cite an example or whip up a few lines of example?

Let's assume I have class with a property ID (string in this case),
and another property called Priority, and I want this dictionary
sorted by Priority, but callable by ID.

Thanks!

FYI, as of now, my best approach would be to create an array that
stores the sort order of the IDs (sorted by Priority), then loop
through that array referencing each dictionary object by key/value one
at a time. It seems cumbersome, however, to maintain an array and a
dictionary just to access them two different ways.

 

[Peter Duniho]

FYI, as of now, my best approach would be to create an array that
stores the sort order of the IDs (sorted by Priority), then loop
through that array referencing each dictionary object by key/value one
at a time. It seems cumbersome, however, to maintain an array and a
dictionary just to access them two different ways.

That's not literally the only way to solve the problem (e.g. see my other
reply). But yes, at some point you _will_ have to maintain a data
structure for each ordering of your collection you want. It's not clear
to me why you would think that a built-in .NET collection would support
more than one comparison function; internally, the collection would still
have to maintain multiple data structures on your behalf, and it would
significantly complicate the API for the collection.

If you have a static collection -- i.e. once it's created, it doesn't
change -- then simply filling an array and sorting it should be fine. If
you expect to have to modify the collection while keeping it in sorted
order, then one of the sorted collections I mentioned would be more
appropriate.

Pete

 

[Gregory A. Beamer]

Looking for a best approach to the following situation:

I want to create an array of objects that have an ID property and a
Priority property. The trick is that I want to leverage the power of a
Dictionary type object so that I can reference the items by their ID,
like so:

string n = MyObject("2468").Name
int p = MyObject("2468").Priority

At the same time, I also need to loop through these items in an order
that is by Priority.

I would love to simply use a foreach loop, but I believe in the past
when I have done this with a Dictionary object, the order of the
foreach loop is determined by the compiler, and not the order items
were added using .Add()

This is probably a fairly simple question, so thanks in advance!

I have looked through the thread, and wanted to add my two cents.

the SortedDictionary, as Peter has stated, will do the dirty work for
you. You will have to key on the property you want it sorted by, but it
will sort, even if you add new objects to the list. One potential caveat
is the sorts in these types of objects are generally, if not always,
exclusive, so you can't key on a field that has 2 objects with 2468. I
do not know if this is true to all of the sorted classes, but it is
something to consider.

Peace and Grace,


--
Gregory A. Beamer
MVP; MCP: +I, SE, SD, DBA

Twitter: @gbworld
Blog: http://gregorybeamer.spaces.live.com

*******************************************
| Think outside the box! |
*******************************************

 

[henry.lee.jr]

That's not literally the only way to solve the problem (e.g. see my other 
reply).  But yes, at some point you _will_ have to maintain a data  
structure for each ordering of your collection you want.  It's not clear  
to me why you would think that a built-in .NET collection would support  
more than one comparison function; internally, the collection would still 
have to maintain multiple data structures on your behalf, and it would  
significantly complicate the API for the collection.

If you have a static collection -- i.e. once it's created, it doesn't  
change -- then simply filling an array and sorting it should be fine.  If  
you expect to have to modify the collection while keeping it in sorted  
order, then one of the sorted collections I mentioned would be more  
appropriate.

Pete

Pete, thanks for the great feedback.

I guess I had been thinking that the idea of a Dictionary was to be
able to look it up via key/value pair, and that the idea of a
SortableDictionary was to extend that further by allowing you to sort
the sequence of the items in whatever way you saw fit (i.e. based on
any property within your object).

In my scenario, I need to do the following:

Loop through each object in an order based on priority. Within each
iteration, I need to quickly look up properties of other items that I
will only know the key/value of.

In my case it is processes that determine whether they are ready to
run dependent upon any number of other processes current status.

So I need to loop through each process object, from higher to lower
priority, and checking at that time whether or not process 47, 1995,
and 14 have a certain status. Each process has differing dependencies.

I've already coded a solution using a Dictionary that handles all of
this, it just does not loop through the objects based on priority,
which is why I was asking the original Q.

Thx!

 

[Jeff Johnson]

Let's assume I have class with a property ID (string in this case),
and another property called Priority, and I want this dictionary
sorted by Priority, but callable by ID.

Not going to happen. SortedDictionaries are both sorted AND indexed by their
key; and you're trying to split the two.

But something about your problem feels weird. You want to loop through the
items in Priority order, right? In my experience, "priority" is usually a
generic thing, which may range, say, from 1 to 5. Multiple things can share
a given priority. But in order to use it as the key to a SortedDictionary,
each Priority value will have to be unique. In that case it sounds like
you're really dealing with an "Order" property, because to me "order" is a
number from 1 to whatever (or 0 if you're a real programming geek!) and
definitely IS unique for each ordered item. So maybe we're just in a
conflict over naming....

If you do have an order like I described above, you could create a second
dictionary to map an ID value to the Priority value on the same object. Then
you could make a simple function like this:

Public MyClass GetItemById(int id)
{
return _mainDictionary[_idToPriority[id]];
}

 

[Jeff Johnson]

If you do have an order like I described above, you could create a second
dictionary to map an ID value to the Priority value on the same object.
Then you could make a simple function like this:

Public MyClass GetItemById(int id)
{
return _mainDictionary[_idToPriority[id]];
}

Argh. This "simple function" was supposed to go in the "wrapper class" which
I started writing about and then deleted from my reply. So, to be a little
more clear, I recommend you create a class which will hold (or be) the main,
sorted dictionary and the mapping dictionary and create methods to access
your data. This class could derive from SortedDictionary or it could
implement the many interfaces that SortedDictionary does manually.

 

[Jeff Johnson]

One potential caveat
is the sorts in these types of objects are generally, if not always,
exclusive, so you can't key on a field that has 2 objects with 2468. I
do not know if this is true to all of the sorted classes, but it is
something to consider.

It's definitely true of SortedDictionary and SortedList, the only two sorted
generics I'm familiar with in .NET 2.0. (Did 3.x add some?)

 

[Peter Duniho]

[...]
In my case it is processes that determine whether they are ready to
run dependent upon any number of other processes current status.

So I need to loop through each process object, from higher to lower
priority, and checking at that time whether or not process 47, 1995,
and 14 have a certain status. Each process has differing dependencies.

I've already coded a solution using a Dictionary that handles all of
this, it just does not loop through the objects based on priority,
which is why I was asking the original Q.

The problem description is fairly vague, but it may be that you'd benefit
from looking at existing task scheduling algorithms. For example,
assuming you have a relatively small number of possible priority values
(e.g. a few dozen at most), it might make more sense to keep an array of
linked lists, with each list representing a priority. In each list would
only be those processes that are in the "runnable" state.

In that way, you don't need any sorting (the array of linked lists is
inherently ordered by priority value), and you'll always know exactly
which processes are runnable and which aren't (those that aren't won't be
in one of these linked lists at all).

As far as maintaining the correlation between a given process's runnable
state and its dependency on some other process, it would be more efficient
to maintain for any given dependency a list of processes that depend on
that dependency. Then if and when a process changes the state of that
dependency, it's trivial to find any and all processes that depend on that
dependency and update their state appropriately (e.g. for a dependency
that can be owned by only one process at a time, when one process releases
it, simply assign it to the next process in the dependency list that is
otherwise runnable).

After all, at some point you wind up having to do a lot of this same kind
of work no matter how you store your collections of processes, so you
might as well store them in a way that is more naturally related to how
you're going to use them.

Pete

 

[Peter Duniho]

It's definitely true of SortedDictionary and SortedList, the only two
sorted
generics I'm familiar with in .NET 2.0. (Did 3.x add some?)

There aren't any new sorted collections. And yes, depending on what the
OP means by "priority", if these values are not unique they can't be used
as the sole key for a sorted collection. He can provide an IComparer<T>
implementation that uses something else as a tie-breaker (e.g. item ID),
but based on his more recent reply, in which he describes more fully the
scenrio, it seems likely that a completely different approach, more akin
to what normal task management algorithms use, would be appropriate (e.g.
round-robin for tie-breaking between items with the same priority).

Pete

 

[Gregory A. Beamer]

Let's assume I have class with a property ID (string in this case),
and another property called Priority, and I want this dictionary
sorted by Priority, but callable by ID.

Sounds like you are heading for a recordset type of object.You can do
something similar with a DataSet using DataView(s) for example, but realize
all of the jumbling around has a perf hit over the simpler Sorted{X}
objects.

And, underneath the hood, you still end up looping.

You could do a custom collection with two dictionaries with the same object
(one for sort, one to pull id, or similar), but then you are duplicating
everything, which is a mess.

Peace and Grace,


--
Gregory A. Beamer
MVP; MCP: +I, SE, SD, DBA

Twitter: @gbworld
Blog: http://gregorybeamer.spaces.live.com

*******************************************
| Think outside the box! |
*******************************************

 

[henry.lee.jr]

There aren't any new sorted collections.  And yes, depending on what the  
OP means by "priority", if these values are not unique they can't be used 
as the sole key for a sorted collection.  He can provide an IComparer<T>  
implementation that uses something else as a tie-breaker (e.g. item ID),  
but based on his more recent reply, in which he describes more fully the  
scenrio, it seems likely that a completely different approach, more akin  
to what normal task management algorithms use, would be appropriate (e.g. 
round-robin for tie-breaking between items with the same priority).

Pete

Thanks again to all who have helped.

To clarify, Priority is something like Low, Medium, High (there could
be a dozen priorities, but the point is the same that many items will
have the same priority). To be clear, I did not want Priority to be
any kind of a key. The ID was the key, as well as what I will need in
order to look up items in the dictionary object. The problem I faced
was that I needed to iterate through the collection based on high to
low priority, not based on ID.

My solution was to create an ArrayList object to store the keys to my
dictionary. As I added an item to the dictionary, I also added the key
value to the array list. Since my data is derived from a SQL query
which sorts the items by priority, and the ArrayList maintains the
order in which I insert them, I was able to iterate using the
ArrayList, using the value in it as the key to the dictionary object.
This gives me the best of both worlds, with the only drawback being I
am maintaining two objects, one a dictionary for lookup by ID, and
another an ArrayList that preserves the proper sort order.

Thanks.

 

[kndg]

Looking for a best approach to the following situation:

I want to create an array of objects that have an ID property and a
Priority property. The trick is that I want to leverage the power of a
Dictionary type object so that I can reference the items by their ID,
like so:

string n = MyObject("2468").Name
int p = MyObject("2468").Priority

At the same time, I also need to loop through these items in an order
that is by Priority.

I would love to simply use a foreach loop, but I believe in the past
when I have done this with a Dictionary object, the order of the
foreach loop is determined by the compiler, and not the order items
were added using .Add()

This is probably a fairly simple question, so thanks in advance!

Hi Henry,

I'm not sure if this is what you means, but give you can do it using Linq,

public class MyObject
{
public string ID { get; set; }
public string Name { get; set; }
public Priority Priority { get; set; }
}

public enum Priority
{
Realtime,
High,
AboveNormal,
Normal,
BelowNormal,
Low,
}

public class MyClass
{
public static void Main(string[] args)
{
Dictionary<string, MyObject> list = new Dictionary<string, MyObject>();

list.Add("1", new MyObject { ID = "1", Name = "Test1", Priority =
Priority.Normal });
list.Add("2", new MyObject { ID = "2", Name = "Test2", Priority =
Priority.Low });
list.Add("3", new MyObject { ID = "3", Name = "Test3", Priority =
Priority.Normal });
list.Add("4", new MyObject { ID = "4", Name = "Test4", Priority =
Priority.High });
list.Add("5", new MyObject { ID = "5", Name = "Test5", Priority =
Priority.BelowNormal });

var sortByPriority = from n in list orderby n.Value.Priority select n;
foreach(var n in sortByPriority)
Console.WriteLine("ID: {0} Name: {1} Priority: {2}", n.Value.ID,
n.Value.Name, n.Value.Priority);
}
}

will output:

ID: 4 Name: Test4 Priority: High
ID: 1 Name: Test1 Priority: Normal
ID: 3 Name: Test3 Priority: Normal
ID: 5 Name: Test5 Priority: BelowNormal
ID: 2 Name: Test2 Priority: Low

Regards.

 

[Raja R Harinath]

Hi,

Looking for a best approach to the following situation:

I want to create an array of objects that have an ID property and a
Priority property. The trick is that I want to leverage the power of a
Dictionary type object so that I can reference the items by their ID,
like so:

string n = MyObject("2468").Name
int p = MyObject("2468").Priority

At the same time, I also need to loop through these items in an order
that is by Priority.

I would love to simply use a foreach loop, but I believe in the past
when I have done this with a Dictionary object, the order of the
foreach loop is determined by the compiler, and not the order items
were added using .Add()

This is probably a fairly simple question, so thanks in advance!

Unfortunately it's not so simple

There's no data structure in the System.Collections[.Generic] that
handle your required semantics. You can maintain two parallel data
structures -- one, a normal dictionary keyed by ID, the other a
SortedDictionary keyed by Priority. The second can be mildly tricky if
multiple objects can share a priority.

In general, classic data structures are oriented towards searching and
iterating on a single key. However, there is a beast known as a
"priority search queue" [1] that combines a finite map on one attribute
and a priority queue on a second attribute.

- Hari

[1] You can start your literature survey with
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.1988

 

[kndg]

Or, if you want to implement your own Dictionary class (but it require
more work):

public class CustomDictionary<TKey, TValue> :
IEnumerable<KeyValuePair<TKey, TValue>>
{
private readonly Dictionary<TKey, TValue> entries;

public TValue this[TKey key]
{
get { return entries[key]; }
}

public CustomDictionary()
{
entries = new Dictionary<TKey, TValue>();
}

public void Add(TKey key, TValue value)
{
entries.Add(key, value);
}

// you have to manually expose Dictionary<TKey, TValue> members
// like Clear, ContainsKey, ContainsValue...etc

public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
var query = from n in entries orderby n.Value select n;

return query.GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}

public class MyObject : IComparable<MyObject>
{
public string ID { get; set; }
public string Name { get; set; }
public Priority Priority { get; set; }

public int CompareTo(MyObject other)
{
return Priority.CompareTo(other.Priority);
}
}

public class MyClass
{
public static void Main(string[] args)
{
CustomDictionary<string, MyObject> list = new
CustomDictionary<string, MyObject>();

list.Add("1", new MyObject { ID = "1", Name = "Test1", Priority =
Priority.Normal });
list.Add("2", new MyObject { ID = "2", Name = "Test2", Priority =
Priority.Low });
list.Add("3", new MyObject { ID = "3", Name = "Test3", Priority =
Priority.Normal });
list.Add("4", new MyObject { ID = "4", Name = "Test4", Priority =
Priority.High });
list.Add("5", new MyObject { ID = "5", Name = "Test5", Priority =
Priority.BelowNormal });

foreach(var n in list)
Console.WriteLine("ID: {0} Name: {1} Priority: {2}", n.Value.ID,
n.Value.Name, n.Value.Priority);
}
}

will produce the same output.

 

[henry.lee.jr]

Or, if you want to implement your own Dictionary class (but it require
more work):

public class CustomDictionary<TKey, TValue> :
IEnumerable<KeyValuePair<TKey, TValue>>
{
   private readonly Dictionary<TKey, TValue> entries;

   public TValue this[TKey key]
   {
     get { return entries[key]; }
   }

   public CustomDictionary()
   {
     entries = new Dictionary<TKey, TValue>();
   }

   public void Add(TKey key, TValue value)
   {
     entries.Add(key, value);
   }

   // you have to manually expose Dictionary<TKey, TValue> members
   // like Clear, ContainsKey, ContainsValue...etc

   public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
   {
     var query = from n in entries orderby n.Value select n;

     return query.GetEnumerator();
   }

   IEnumerator IEnumerable.GetEnumerator()
   {
     return GetEnumerator();
   }

}

public class MyObject : IComparable<MyObject>
{
   public string ID { get; set; }
   public string Name { get; set; }
   public Priority Priority { get; set; }

   public int CompareTo(MyObject other)
   {
     return Priority.CompareTo(other.Priority);
   }

}

public class MyClass
{
   public static void Main(string[] args)
   {
     CustomDictionary<string, MyObject> list = new
CustomDictionary<string, MyObject>();

     list.Add("1", new MyObject { ID = "1", Name = "Test1", Priority =
Priority.Normal });
     list.Add("2", new MyObject { ID = "2", Name = "Test2", Priority =
Priority.Low });
     list.Add("3", new MyObject { ID = "3", Name = "Test3", Priority =
Priority.Normal });
     list.Add("4", new MyObject { ID = "4", Name = "Test4", Priority =
Priority.High });
     list.Add("5", new MyObject { ID = "5", Name = "Test5", Priority =
Priority.BelowNormal });

     foreach(var n in list)
       Console.WriteLine("ID: {0} Name: {1} Priority: {2}", n.Value.ID,
n.Value.Name, n.Value.Priority);
   }

}

will produce the same output.

kndg, Just wanted to send out an extra thanks to you for the
comprehensive replies. I would probably pass on the linq solution for
now, merely because I haven't learned anything about it yet, although
at some point I would like to