IComparer (or the IComparable methods it relies upon) did not retu

23 Jun 2006 3:55 PM

Darragh Jones

I'm trying to figure out why I'm getting the following error message when
trying to radomly sort a list of custom objects. In particular I've noticed
the following strange behaviour I'm hoping someone could shed some light
on....

1. When the list contains only 3 objects the sort works fine, unless I
remove the 'if x.equals(y)' check in the compare function.

2. When there are more than 3 objects I get the error even when this check
is in place (albeit it usually takes a bit longer).

------------------------ERROR MESSAGE----------------------------
IComparer (or the IComparable methods it relies upon) did not return zero
when Array.Sort called x. CompareTo(x)

-------------------------CODE LISTING--------------------------------

Module Module1

    Sub Main()
        Dim People As New System.Collections.Generic.List(Of Person)
        Dim Counter As Integer = 0
        People.Add(New Person(1, "Brian"))
        People.Add(New Person(2, "Darragh"))
        People.Add(New Person(3, "Aoife"))
        People.Add(New Person(4, "Aidan")) ' when only 3 people I don't seem
to have a problem unless I remove the if x.Equals(y) check below!
        While True
            Counter += 1
            Console.WriteLine("Comparison {0}", Counter)
            People.Sort(New Person.Random())
        End While
    End Sub
End Module

Public Class Person
    Public ID As Integer
    Public Name As String

    Public Sub New(ByVal ID As Integer, ByVal Name As String)
        Me.ID = ID
        Me.Name = Name
    End Sub

    Public Overrides Function ToString() As String
        Return String.Format("ID={0}, Name={1}", Me.ID, Me.Name)
    End Function

    Class Random
        Implements System.Collections.Generic.IComparer(Of Person)

        Private Shared r As New System.Random

        Public Function Compare(ByVal x As Person, ByVal y As Person) As
Integer Implements System.Collections.Generic.IComparer(Of Person).Compare
            Console.Write("Comparing: x=[{0}], y=[{1}]", x, y)
            If x.Equals(y) Then Compare = 0 Else Compare = r.Next(-1, 2)
'removing this gives error when only 3 items
            'Compare = r.Next(-1, 2)
            Console.WriteLine("{0}Returning: {1}", vbTab, Compare)
        End Function

    End Class

End Class

23 Jun 2006 4:50 PM

sloan

I tried your code... in C#. (I'm working with IComparers this week, so I
thought Id give your randomizer a run thru)

Here is mine:

int compareValue = 0;
if (x.Equals(y))

{

compareValue = 0;

}

else

{

compareValue = m_random.Next(-1, 2);

}

//'removing this gives error when only 3 items

compareValue = m_random.Next(-1, 2);

return compareValue;

and I have a member variable:
private System.Random m_random = new System.Random();

First, you may want to put

Option Strict On
Option Explicit On

at the top of your vb code.

Private Shared r As New System.Random

needs to be rewritten as:

Private Shared r System.Random = New System.Random()

So I think its either that. or the static/shared thing you are doing.

I did not experience the issue with 2 or 3 items in my collection.

Show quote

"Darragh Jones" <Darragh Jo***@discussions.microsoft.com> wrote in message
news:1EE07964-5CDC-4AFC-AF2B-EF058AEEDDA1@microsoft.com...
> I'm trying to figure out why I'm getting the following error message when
> trying to radomly sort a list of custom objects. In particular I've
noticed
> the following strange behaviour I'm hoping someone could shed some light
> on....
>
> 1. When the list contains only 3 objects the sort works fine, unless I
> remove the 'if x.equals(y)' check in the compare function.
>
> 2. When there are more than 3 objects I get the error even when this check
> is in place (albeit it usually takes a bit longer).
>
>
>
> ------------------------ERROR MESSAGE----------------------------
> IComparer (or the IComparable methods it relies upon) did not return zero
> when Array.Sort called x. CompareTo(x)
>
> -------------------------CODE LISTING--------------------------------
>
> Module Module1
>
>     Sub Main()
>         Dim People As New System.Collections.Generic.List(Of Person)
>         Dim Counter As Integer = 0
>         People.Add(New Person(1, "Brian"))
>         People.Add(New Person(2, "Darragh"))
>         People.Add(New Person(3, "Aoife"))
>         People.Add(New Person(4, "Aidan")) ' when only 3 people I don't
seem
> to have a problem unless I remove the if x.Equals(y) check below!
>         While True
>             Counter += 1
>             Console.WriteLine("Comparison {0}", Counter)
>             People.Sort(New Person.Random())
>         End While
>     End Sub
> End Module
>
> Public Class Person
>     Public ID As Integer
>     Public Name As String
>
>     Public Sub New(ByVal ID As Integer, ByVal Name As String)
>         Me.ID = ID
>         Me.Name = Name
>     End Sub
>
>     Public Overrides Function ToString() As String
>         Return String.Format("ID={0}, Name={1}", Me.ID, Me.Name)
>     End Function
>
>     Class Random
>         Implements System.Collections.Generic.IComparer(Of Person)
>
>         Private Shared r As New System.Random
>
>         Public Function Compare(ByVal x As Person, ByVal y As Person) As
> Integer Implements System.Collections.Generic.IComparer(Of Person).Compare
>             Console.Write("Comparing: x=[{0}], y=[{1}]", x, y)
>             If x.Equals(y) Then Compare = 0 Else Compare = r.Next(-1, 2)
> 'removing this gives error when only 3 items
>             'Compare = r.Next(-1, 2)
>             Console.WriteLine("{0}Returning: {1}", vbTab, Compare)
>         End Function
>
>     End Class
>
> End Class

23 Jun 2006 5:07 PM

sloan

Actually, now I see what you're talking about.

I had to run it 3 times before I got the error. But I did get it.

One thing is that one of my objects (x or y) is null/Nothing for some
unknown reason.

Hmmm.. I'll still looking at this sucker.

Show quote

"Darragh Jones" <Darragh Jo***@discussions.microsoft.com> wrote in message
news:1EE07964-5CDC-4AFC-AF2B-EF058AEEDDA1@microsoft.com...
> I'm trying to figure out why I'm getting the following error message when
> trying to radomly sort a list of custom objects. In particular I've
noticed
> the following strange behaviour I'm hoping someone could shed some light
> on....
>
> 1. When the list contains only 3 objects the sort works fine, unless I
> remove the 'if x.equals(y)' check in the compare function.
>
> 2. When there are more than 3 objects I get the error even when this check
> is in place (albeit it usually takes a bit longer).
>
>
>
> ------------------------ERROR MESSAGE----------------------------
> IComparer (or the IComparable methods it relies upon) did not return zero
> when Array.Sort called x. CompareTo(x)
>
> -------------------------CODE LISTING--------------------------------
>
> Module Module1
>
>     Sub Main()
>         Dim People As New System.Collections.Generic.List(Of Person)
>         Dim Counter As Integer = 0
>         People.Add(New Person(1, "Brian"))
>         People.Add(New Person(2, "Darragh"))
>         People.Add(New Person(3, "Aoife"))
>         People.Add(New Person(4, "Aidan")) ' when only 3 people I don't
seem
> to have a problem unless I remove the if x.Equals(y) check below!
>         While True
>             Counter += 1
>             Console.WriteLine("Comparison {0}", Counter)
>             People.Sort(New Person.Random())
>         End While
>     End Sub
> End Module
>
> Public Class Person
>     Public ID As Integer
>     Public Name As String
>
>     Public Sub New(ByVal ID As Integer, ByVal Name As String)
>         Me.ID = ID
>         Me.Name = Name
>     End Sub
>
>     Public Overrides Function ToString() As String
>         Return String.Format("ID={0}, Name={1}", Me.ID, Me.Name)
>     End Function
>
>     Class Random
>         Implements System.Collections.Generic.IComparer(Of Person)
>
>         Private Shared r As New System.Random
>
>         Public Function Compare(ByVal x As Person, ByVal y As Person) As
> Integer Implements System.Collections.Generic.IComparer(Of Person).Compare
>             Console.Write("Comparing: x=[{0}], y=[{1}]", x, y)
>             If x.Equals(y) Then Compare = 0 Else Compare = r.Next(-1, 2)
> 'removing this gives error when only 3 items
>             'Compare = r.Next(-1, 2)
>             Console.WriteLine("{0}Returning: {1}", vbTab, Compare)
>         End Function
>
>     End Class
>
> End Class

23 Jun 2006 6:27 PM

sloan

http://msmvps.com/blogs/jon.skeet/archive/2005/12/02/77520.aspx

I think it has something to do with thread safety.

I've even tried a more anal RandomNumber getter:

I don't have an answer. As soon as you take out the Random.Next... it
doesn't blow up.

Please post a solution here if you figure it out.

class RandomNumberGetter

{

private System.Random m_random = null;//new System.Random();

//private static readonly object padlock = new object();

//private readonly object padlock = new object();

private object padlock = new object();

public RandomNumberGetter()

{

lock (padlock)

{

this.m_random = new Random();

}

}

public int GetRandomNumber(int x, int y)

{

lock (padlock)

{

return this.m_random.Next(x, y);

}

}

}

Show quote

"Darragh Jones" <Darragh Jo***@discussions.microsoft.com> wrote in message
news:1EE07964-5CDC-4AFC-AF2B-EF058AEEDDA1@microsoft.com...
> I'm trying to figure out why I'm getting the following error message when
> trying to radomly sort a list of custom objects. In particular I've
noticed
> the following strange behaviour I'm hoping someone could shed some light
> on....
>
> 1. When the list contains only 3 objects the sort works fine, unless I
> remove the 'if x.equals(y)' check in the compare function.
>
> 2. When there are more than 3 objects I get the error even when this check
> is in place (albeit it usually takes a bit longer).
>
>
>
> ------------------------ERROR MESSAGE----------------------------
> IComparer (or the IComparable methods it relies upon) did not return zero
> when Array.Sort called x. CompareTo(x)
>
> -------------------------CODE LISTING--------------------------------
>
> Module Module1
>
>     Sub Main()
>         Dim People As New System.Collections.Generic.List(Of Person)
>         Dim Counter As Integer = 0
>         People.Add(New Person(1, "Brian"))
>         People.Add(New Person(2, "Darragh"))
>         People.Add(New Person(3, "Aoife"))
>         People.Add(New Person(4, "Aidan")) ' when only 3 people I don't
seem
> to have a problem unless I remove the if x.Equals(y) check below!
>         While True
>             Counter += 1
>             Console.WriteLine("Comparison {0}", Counter)
>             People.Sort(New Person.Random())
>         End While
>     End Sub
> End Module
>
> Public Class Person
>     Public ID As Integer
>     Public Name As String
>
>     Public Sub New(ByVal ID As Integer, ByVal Name As String)
>         Me.ID = ID
>         Me.Name = Name
>     End Sub
>
>     Public Overrides Function ToString() As String
>         Return String.Format("ID={0}, Name={1}", Me.ID, Me.Name)
>     End Function
>
>     Class Random
>         Implements System.Collections.Generic.IComparer(Of Person)
>
>         Private Shared r As New System.Random
>
>         Public Function Compare(ByVal x As Person, ByVal y As Person) As
> Integer Implements System.Collections.Generic.IComparer(Of Person).Compare
>             Console.Write("Comparing: x=[{0}], y=[{1}]", x, y)
>             If x.Equals(y) Then Compare = 0 Else Compare = r.Next(-1, 2)
> 'removing this gives error when only 3 items
>             'Compare = r.Next(-1, 2)
>             Console.WriteLine("{0}Returning: {1}", vbTab, Compare)
>         End Function
>
>     End Class
>
> End Class

23 Jun 2006 11:51 PM

Jon Skeet [C# MVP]

<=?Utf-8?B?RGFycmFnaCBKb25lcw==?= <Darragh
Jo***@discussions.microsoft.com>> wrote:

> I'm trying to figure out why I'm getting the following error message when
> trying to radomly sort a list of custom objects.

I suspect the problem is in the exception message. Basically, by
implementing IComparer randomly, you're breaking the contract by not
making it reflexive. You're saying that at the samt time, x > y and
y > x can both be true. That makes it impossible to sort.

What's your actual aim here? If you want to shuffle the list, there are
much better ways of doing it.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

26 Jun 2006 10:24 AM

Darragh Jones

Thanks Jon for your help. I see now what I was doing wrong. Using Sort to
randomize the list was probably not the cleverest thing I've ever done.

I've decided to take a more straight forward approach...

Private Function Randomize(ByVal list As Collections.Generic.List(Of
Person)) As Collections.Generic.List(Of Person)
        Randomize = New Collections.Generic.List(Of Person)
        Dim index As Integer
        Dim r As New Random()
        While list.Count > 0
            index = r.Next(list.Count)
            Randomize.Add(list.Item(index))
            list.RemoveAt(index)
        End While
    End Function

Show quote

"Jon Skeet [C# MVP]" wrote:

> <=?Utf-8?B?RGFycmFnaCBKb25lcw==?= <Darragh
> Jo***@discussions.microsoft.com>> wrote:
> > I'm trying to figure out why I'm getting the following error message when
> > trying to radomly sort a list of custom objects.
>
> I suspect the problem is in the exception message. Basically, by
> implementing IComparer randomly, you're breaking the contract by not
> making it reflexive. You're saying that at the samt time, x > y and
> y > x can both be true. That makes it impossible to sort.
>
> What's your actual aim here? If you want to shuffle the list, there are
> much better ways of doing it.
>
> --
> Jon Skeet - <sk***@pobox.com>
> http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
> If replying to the group, please do not mail me too
>

26 Jun 2006 7:37 PM

Jon Skeet [C# MVP]

Darragh Jones <DarraghJo***@discussions.microsoft.com> wrote:
Show quote

> Thanks Jon for your help. I see now what I was doing wrong. Using Sort to
> randomize the list was probably not the cleverest thing I've ever done.
>
> I've decided to take a more straight forward approach...
>
> Private Function Randomize(ByVal list As Collections.Generic.List(Of
> Person)) As Collections.Generic.List(Of Person)
>         Randomize = New Collections.Generic.List(Of Person)
>         Dim index As Integer
>         Dim r As New Random()
>         While list.Count > 0
>             index = r.Next(list.Count)
>             Randomize.Add(list.Item(index))
>             list.RemoveAt(index)
>         End While
>     End Function

While that will do it, it's not a terribly nice way of doing it, as it
involves creating a new list unnecessarily. There's a really neat
technique which shuffles a list. Imagine that the list has a dividing
line between unshuffled values and shuffled values. Everything starts
unshuffled. You randomly pick one of the unshuffled values and swap it
with the first unshuffled value, then move the imaginary line to past
that element. Keep going until everything is shuffled.

It's O(n) and very simple to implement. Unfortunately I don't have time
to do it for you in VB.NET right now, but here's an implementation in
C#:

    static readonly Random rng = new Random();
    public static void Shuffle (IList list)
    {
        // Note: last element doesn't need shuffling! (Couldn't
        // pick a different one to itself anyway.)
        for (int i=0; i < list.Count-1; i++)
        {
            object x = list[i];

            int index = rng.Next(list.Count-i)+i;
            list[i]=list[index];
            list[index]=x;
        }
    }

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

23 Jun 2006 11:51 PM

Jon Skeet [C# MVP]

<=?Utf-8?B?RGFycmFnaCBKb25lcw==?= <Darragh
Jo***@discussions.microsoft.com>> wrote:

> I'm trying to figure out why I'm getting the following error message when
> trying to radomly sort a list of custom objects. In particular I've noticed
> the following strange behaviour I'm hoping someone could shed some light
> on....

<snip>

Here's a short but complete program which demonstrates the problem with
no randomness:

using System;
using System.Collections.Generic;

class Test
{
    static void Main()
    {
        List<string> list = new List<string>();
        list.Add("a");
        list.Add("b");
        list.Add("c");
        list.Add("d");

        list.Sort(new DodgyComparer<string>());
    }
}

class DodgyComparer<T> : IComparer<T>
{
    int[] results = {-1, 0, 1, -1, 0, -1, -1, -1, 100};
    int index=0;

    public int Compare(T x, T y)
    {
        Console.WriteLine (x+" "+y+" "+results[index]);
        return results[index++];
    }
}

(The 100 is there to show that it's not going off the end of the array.
As a side issue, the same exception is thrown if the comparer throws
IndexOutOfRangeException, which made this awkward to diagnose.)

I've reported it to MS:
http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?
FeedbackID=145253

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too