problem with icomparer or hashtable in .net2.0??

G

Guest

Hi

I had written code to sort a hashtable in .net 1.1 based on the values by
implementing the IComparer interface. Lets say the Hashtable contained the
following values item, values

"A", 1
"B", 1
"C", 2

When I sort the hastable in Ascending order I get a result as

"A"
"B"
"C"

But when I execute the same code in .net 2.0, I am getting a result as

"B"
"A"
"C"

Why is this order changing for items having the same value? Has anybody
encountered this problem? This is really driving me nuts... please help !!

Thanks in advance!!
 
J

Jon Skeet [C# MVP]

arvind said:
I had written code to sort a hashtable in .net 1.1 based on the values by
implementing the IComparer interface. Lets say the Hashtable contained the
following values item, values

"A", 1
"B", 1
"C", 2

When I sort the hastable in Ascending order I get a result as

"A"
"B"
"C"

But when I execute the same code in .net 2.0, I am getting a result as

"B"
"A"
"C"

Why is this order changing for items having the same value? Has anybody
encountered this problem? This is really driving me nuts... please help !!

How were you sorting the hashtable?

Could you post a short but complete program which demonstrates the
problem?

See http://www.pobox.com/~skeet/csharp/complete.html for details of
what I mean by that.
 
G

Guest

Jon

Sorry for the wrong info. I am actually using an ArrayList and not a
Hashtable.
I use the ArrayList.Sort(Comparer) method and face this problem.

I used the reflector to see whether there are changes made in the 2.0 base
libraries and find that the ArrayList.Sort method calls the Array.Sort()
method.
I see that this is where the change lies. In 2.0 this method seems to be
calling a new method called GetPivotValue while in 1.1 this method does not
exist. Do you think it has something to do with this?
 
J

Jon Skeet [C# MVP]

arvind said:
Sorry for the wrong info. I am actually using an ArrayList and not a
Hashtable.
I use the ArrayList.Sort(Comparer) method and face this problem.

Then it sounds like your comparer is broken.
I used the reflector to see whether there are changes made in the 2.0 base
libraries and find that the ArrayList.Sort method calls the Array.Sort()
method.
I see that this is where the change lies. In 2.0 this method seems to be
calling a new method called GetPivotValue while in 1.1 this method does not
exist. Do you think it has something to do with this?

I suspect your previous comparer was broken but the implementation let
you get away with it - I've seen that before.

As I said earlier, could you post a short but complete program which
demonstrates the problem?

See http://www.pobox.com/~skeet/csharp/complete.html for details of
what I mean by that.
 
G

Guest

Hi Jon

Here is the code. Please create a Console App to test this. You will see
that Items C and G gets swapped when executed in 1.1 and 2.0 respectively

Class 1
=================

class Class1
{

/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
Class2 c2 = new Class2();
c2.Test();
}
}



Class 2
=================


/// <summary>
/// Summary description for Class2.
/// </summary>
public class Class2
{

private ArrayList m_itemList = new ArrayList();
private Hashtable m_items = new Hashtable();

/// <summary>
/// The main entry point for the application.
/// </summary>
public void Test()
{
Item item1 = new Item("A",10.444444444);
Item item2 = new Item("B", 10.33333333333333);
Item item3 = new Item("C", 4.33333333333333);
Item item4 = new Item("E", 4.33333333333333);
Item item5 = new Item("F", 4.33333333333333);
Item item6 = new Item("G", 4.33333333333333);
Item item7 = new Item("D",30);



// Add items to ArrayList
m_itemList.Add(item1);
m_itemList.Add(item2);
m_itemList.Add(item3);
m_itemList.Add(item4);
m_itemList.Add(item5);
m_itemList.Add(item6);
m_itemList.Add(item7);

// Create a Hashtable with ItemCode and Quantity as Key and value
m_items.Add(item1.ItemCode, item1.Quantity);
m_items.Add(item2.ItemCode, item2.Quantity);
m_items.Add(item3.ItemCode, item3.Quantity);
m_items.Add(item4.ItemCode, item4.Quantity);
m_items.Add(item5.ItemCode, item5.Quantity);
m_items.Add(item6.ItemCode, item6.Quantity);
m_items.Add(item7.ItemCode, item7.Quantity);

m_itemList.Sort(new ItemComparer(m_items));

//m_itemList.Reverse();

foreach(Item item in m_itemList)
{
Console.WriteLine(item.ItemCode.ToString());
}

Console.ReadLine();
}
}

class ItemComparer : IComparer
{
private Hashtable m_items = null;

public ItemComparer(Hashtable items)
{
m_items = items;
}

public int Compare(object x, object y)
{
if (! (x is Item && y is Item) )
{
throw new ArgumentException("aDS");
}
else
{
return ((IComparable)
(m_items[((Item)x).ItemCode])).CompareTo(m_items[((Item)y).ItemCode]);
}
}

}


class Item
{
private double m_qty = 0;
private string m_itemCode = "";

public Item(string code, double Quantity)
{
m_itemCode = code;
m_qty = Quantity;
}

public string ItemCode
{
get { return m_itemCode; }
set { m_itemCode = value; }
}

public double Quantity
{
get { return m_qty; }
set { m_qty = value; }
}
}
 
J

Jon Skeet [C# MVP]

Here is the code. Please create a Console App to test this. You will see
that Items C and G gets swapped when executed in 1.1 and 2.0 respectively

Ah, I see the issue now. Right - you're sorting by volume, not ID.
That wasn't clear from your original post. The sort in .NET 2.0 isn't
stable - in other words, two equal items (i.e. anything with the same
volume) aren't guaranteed to stay in the same order.

If you want to guarantee a particular ordering, you'll need to find
some way of comparing items such that two inequal items will *always*
return a non-zero value from the comparison.

The easiest way of doing this in your case would be to use the item
ID, IMO. So basically, compare by volume first, and if that returns 0
then compare the item IDs and return the result of that comparison.

Jon
 
G

Guest

Jon Thanks. Is there a URL where it states that the Sort method is unstable?
I am unable to find this information anywhere. Any help would be really
appreciated
 
J

Jon Skeet [C# MVP]

Jon Thanks. Is there a URL where it states that the Sort method is unstable?
I am unable to find this information anywhere. Any help would be really
appreciated
From the remarks section of the MSDN ArrayList.Sort(int, int,
IComparer) method:

<quote>
This method uses Array.Sort, which uses the QuickSort algorithm. This
implementation performs an unstable sort; that is, if two elements are
equal, their order might not be preserved. In contrast, a stable sort
preserves the order of elements that are equal.
</quote>

Jon
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top