SortedDictionary with IComparer bug?

R

Ralph Wiggum

I'm trying to use a comparer to sort keys according to a specific priority. After adding the keys,
there is a KeyNotFoundException when I try to read values back from the dictionary. Even if the key is
in the SortedDictionary.Keys collection. Please help!


using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

private void butSort_Click(object sender, EventArgs e)
{
DokumentSort ds = new DokumentSort();
SortedDictionary<string, string> dict = new SortedDictionary<string, string>(ds);

//only "pri1" is valid and should be placed first in dict
string[] sData = new string[] { "noPri0", "noPri1", "noPri2", "pri1" };

for (int i = 0; i < sData.Length; i++) {
if(dict.ContainsKey(sData+"")) continue;
dict.Add(sData+"", "anything"+i);
Debug.WriteLine("Added "+sData + " anything" + i);
}

foreach (string skey in dict.Keys){
//will fail here
Debug.WriteLine(skey + " " + dict[skey+""]);
}
}


public class DokumentSort : IComparer<string>{
Dictionary<string, int> dictPriority = new Dictionary<string, int>();

public DokumentSort(){
//Setup key priority. If unknown key, it should be placed last
string[] sOrder = new string[] { "pri0", "pri1", "pri2" };
for (int i = 0; i < sOrder.Length; i++) {
dictPriority.Add(sOrder+"", i);
}
}

public int Compare(string sX, string sY){
//Debug.WriteLine("Comparing "+sX + " " + sY);
if (sX == sY) return 0;
if(!dictPriority.ContainsKey(sX+"")) return 1;
if(!dictPriority.ContainsKey(sY+"")) return -1;
int priX = dictPriority[sX+""];
int priY = dictPriority[sY+""];
return priX-priY;
}
}
 
L

Lasse Vågsæther Karlsen

Ralph said:
I'm trying to use a comparer to sort keys according to a specific
priority. After adding the keys,
there is a KeyNotFoundException when I try to read values back from the
dictionary. Even if the key is
in the SortedDictionary.Keys collection. Please help!


using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

private void butSort_Click(object sender, EventArgs e)
{
DokumentSort ds = new DokumentSort();
SortedDictionary<string, string> dict = new SortedDictionary<string,
string>(ds);

//only "pri1" is valid and should be placed first in dict
string[] sData = new string[] { "noPri0", "noPri1", "noPri2", "pri1" };

for (int i = 0; i < sData.Length; i++) {
if(dict.ContainsKey(sData+"")) continue;
dict.Add(sData+"", "anything"+i);
Debug.WriteLine("Added "+sData + " anything" + i);
}

foreach (string skey in dict.Keys){
//will fail here
Debug.WriteLine(skey + " " + dict[skey+""]);
}
}


public class DokumentSort : IComparer<string>{
Dictionary<string, int> dictPriority = new Dictionary<string, int>();

public DokumentSort(){
//Setup key priority. If unknown key, it should be placed last
string[] sOrder = new string[] { "pri0", "pri1", "pri2" };
for (int i = 0; i < sOrder.Length; i++) {
dictPriority.Add(sOrder+"", i);
}
}

public int Compare(string sX, string sY){
//Debug.WriteLine("Comparing "+sX + " " + sY);
if (sX == sY) return 0;
if(!dictPriority.ContainsKey(sX+"")) return 1;
if(!dictPriority.ContainsKey(sY+"")) return -1;
int priX = dictPriority[sX+""];
int priY = dictPriority[sY+""];
return priX-priY;
}
}
Click to expand...


There are many different ways to implement IComparer<T>. If you want to
implement it just for sorting, you can get away with multiple items
returning "equal", simply because you don't really care which order they
come in.

However, when dealing with dictionaries, the items really must be equal,
otherwise you will get false negatives or positives.

In your comparer you have determined that everything the comparer object
doesn't know about is to be sorted last, which means that a lot of keys
that the comparer object doesn't know about will give the same result
when comparing.

The dictionary, however, needs to know if they are actually equal.

One way to change your algorithm would be that if neither sX nor sY are
in the dictPriority dictionary, compare them as usual, like this:

public int Compare(string sX, string sY)
{
// Handle simple case
if (sX == sY)
return 0;

if (dictPriority.ContainsKey(sX) && dictPriority.ContainsKey(sY))
{
// both are known, calculate relative priority
// we also know that they are not equal
int priX = dictPriority[sX];
int priY = dictPriority[sY];
return priX - priY;
}
else if (dictPriority.ContainsKey(sX))
{
// only sX is known, sY is not, so sort sX first
return -1;
}
else if (dictPriority.ContainsKey(sY))
{
// sX is not known, sY is however, so sort sY first
return +1;
}
else
{
// neither is known, compare as normal strings
return Comparer<String>.Default.Compare(sX, sY);
}
}
 
R

Ralph Wiggum

It worked! Many thanks!
Ralph said:
I'm trying to use a comparer to sort keys according to a specific
priority. After adding the keys,
there is a KeyNotFoundException when I try to read values back from
the dictionary. Even if the key is
in the SortedDictionary.Keys collection. Please help!


using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

private void butSort_Click(object sender, EventArgs e)
{
DokumentSort ds = new DokumentSort();
SortedDictionary<string, string> dict = new SortedDictionary<string,
string>(ds);

//only "pri1" is valid and should be placed first in dict
string[] sData = new string[] { "noPri0", "noPri1", "noPri2",
"pri1" };
for (int i = 0; i < sData.Length; i++) {
if(dict.ContainsKey(sData+"")) continue;
dict.Add(sData+"", "anything"+i);
Debug.WriteLine("Added "+sData + " anything" + i);
}

foreach (string skey in dict.Keys){ //will fail
here Debug.WriteLine(skey + " " +
dict[skey+""]); }
}


public class DokumentSort : IComparer<string>{
Dictionary<string, int> dictPriority = new Dictionary<string,
int>();

public DokumentSort(){
//Setup key priority. If unknown key, it should be placed last
string[] sOrder = new string[] { "pri0", "pri1", "pri2" };
for (int i = 0; i < sOrder.Length; i++) {
dictPriority.Add(sOrder+"", i);
}
}

public int Compare(string sX, string sY){
//Debug.WriteLine("Comparing "+sX + " " + sY);
if (sX == sY) return 0;
if(!dictPriority.ContainsKey(sX+"")) return 1;
if(!dictPriority.ContainsKey(sY+"")) return -1;
int priX = dictPriority[sX+""];
int priY = dictPriority[sY+""]; return
priX-priY;
}
}
Click to expand...


There are many different ways to implement IComparer<T>. If you want to
implement it just for sorting, you can get away with multiple items
returning "equal", simply because you don't really care which order they
come in.

However, when dealing with dictionaries, the items really must be equal,
otherwise you will get false negatives or positives.

In your comparer you have determined that everything the comparer object
doesn't know about is to be sorted last, which means that a lot of keys
that the comparer object doesn't know about will give the same result
when comparing.

The dictionary, however, needs to know if they are actually equal.

One way to change your algorithm would be that if neither sX nor sY are
in the dictPriority dictionary, compare them as usual, like this:

public int Compare(string sX, string sY)
{
// Handle simple case
if (sX == sY)
return 0;

if (dictPriority.ContainsKey(sX) && dictPriority.ContainsKey(sY))
{
// both are known, calculate relative priority
// we also know that they are not equal
int priX = dictPriority[sX];
int priY = dictPriority[sY];
return priX - priY;
}
else if (dictPriority.ContainsKey(sX))
{
// only sX is known, sY is not, so sort sX first
return -1;
}
else if (dictPriority.ContainsKey(sY))
{
// sX is not known, sY is however, so sort sY first
return +1;
}
else
{
// neither is known, compare as normal strings
return Comparer<String>.Default.Compare(sX, sY);
}
}
Click to expand...
 
Top