Array.Sort throwing error when sorting custom objects.

Lucifer 2

I'm getting the error below when sorting an array of custom 'Content' objects in a random order. I've also included my sort classes which implement the ICompare interface.

The Content class is very straight forward.

The error is being caused by calling:
Dim Temp As New System.Collections.Generic.List(Of Content)
Temp.Sort(New Content.Random())

Sorting alphabetically and by PrefOrder work fine.
I particualy in my Random sort class note the line:

If x.Equals(y) Then Return 0

The error message seems to indicate I'm not doing this, but clearly i am.

Any help appreciated.

IComparer (or the IComparable methods it relies upon) did not return zero when Array.Sort called x. CompareTo(x). x: 'Content'  x's type: 'Content' The IComparer: 'Content+Random'.
Description: An unhandled exception occurred during the execution of the current web request. Please review the stack trace for more information about the error and where it originated in the code.

Exception Details: System.ArgumentException: IComparer (or the IComparable methods it relies upon) did not return zero when Array.Sort called x. CompareTo(x). x: 'Content'  x's type: 'Content' The IComparer: 'Content+Random'.

Source Error:

Dim Temp As New System.Collections.Generic.List(Of Content)
Temp.Sort(New Content.Random())

Class Content

Private _Name As String
Private _PrefOrder as Integer
'... removed for clarity

Class Alphabetically
        Implements System.Collections.Generic.IComparer(Of Content)
        Public Function Compare(ByVal x As Content, ByVal y As Content) As Integer Implements System.Collections.Generic.IComparer(Of Content).Compare
            Return x._Name < y._Name
        End Function
    End Class

    Class Pref
        Implements System.Collections.Generic.IComparer(Of Content)
        Public Function Compare(ByVal x As Content, ByVal y As Content) As Integer Implements System.Collections.Generic.IComparer(Of Content).Compare
            Return x._PrefOrder < y._PrefOrder
        End Function
    End Class

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

        Private Shared _R As New System.Random()

        Public Function Compare(ByVal x As Content, ByVal y As Content) As Integer Implements System.Collections.Generic.IComparer(Of Content).Compare
            Return 1
            If x Is Nothing AndAlso y Is Nothing Then Return 0
            If x Is Nothing AndAlso y IsNot Nothing Then Return -1
            If x IsNot Nothing AndAlso y Is Nothing Then Return 1
            If x.Equals(y) Then Return 0

            Select Case _R.Next() Mod 3
                Case 0 : Return -1
                Case 1 : Return 0
                Case 2 : Return 1
            End Select
        End Function
    End Class

End Class

Torak

don't really know .Net but is it because the params are ByVal and not ByRef..

So the object comparison is never made.. This is a pure java head talking so sorry if i'm way off...

Lucifer 2

The signature for the ICompare interface passes parameters byVal, so I have no choice in this matter.

However I think you could be on to something.

Basically you saying, even if the same object is passed in as both the x and y parameters to the compare function, as it's being passed byVal, the x.Equals(y) expression will always return false?

How then can I ensure I return 0 when Array.Sort calls x.CompareTo(x) as the error message seem to suggest I must?

Any ideas? I suppose I could check the value of some property on the object?

Thanks for your help!

Evil Phil

Didn't really read through all the code to work out exactly what its doing but one thing did stand out to me and that's the first thing the Random.Compare() method is doing is returning 1 (highlighted in red). Unless this is a weird vb.net default return value thingy, and it very well could be, surely that's the only code going to execute in the function. Not saying that its a fix to your problem either but it does look incorrect.

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

        Private Shared _R As New System.Random()

        Public Function Compare(ByVal x As Content, ByVal y As Content) As Integer Implements System.Collections.Generic.IComparer(Of Content).Compare
            [COLOR="Red"][B]Return 1[/B][/COLOR]
            If x Is Nothing AndAlso y Is Nothing Then Return 0
            If x Is Nothing AndAlso y IsNot Nothing Then Return -1
            If x IsNot Nothing AndAlso y Is Nothing Then Return 1
            If x.Equals(y) Then Return 0

            Select Case _R.Next() Mod 3
                Case 0 : Return -1
                Case 1 : Return 0
                Case 2 : Return 1
            End Select
        End Function
    End Class

Lucifer 2

sorry, ignore that line. I just stuck it in as I was trying to debug the problem!

Evil Phil

Heh, I've lost hours to those little debug lines. Again I'm not so sure as its .Net 2 but should nested class Random have a constructor of some sort? The constuctor would execute some code the results of which would be exposed as a property. You could then sort on this property.

Torak

try adding

If x._Name = y._Name Then Return 0

instead of If x.Equals(y) Then Return 0

One other thing.. do the objects which are being sorted all correctly override the .Equals method. Because if they don't then that would cause your problem.

Essentially anything that needs to be sorted need to have a correct override of the Equals method to work correctly due to the "identity" constraint which is essentially being placed on the objects.

Torak

Evil Phil wrote:

Heh, I've lost hours to those little debug lines. Again I'm not so sure as its .Net 2 but should nested class Random have a constructor of some sort? The constuctor would execute some code the results of which would be exposed as a property. You could then sort on this property.

I think the point is that it should randomly sort, unless the objects are the same object... but because it is ByVal the initial object references are lost so you can't call ReferencesEqual..

I should point out once more that I have NEVER written .net and haven't got a clue what I am talking about...

but it's what I'd be looking at..

Evil Phil

Torak wrote:

I think the point is that it should randomly sort, unless the objects are the same object...

Okay, quick look at the visual studio 2005 help file has clarified things a little. I was on the wrong track altogether.

<quick rtfm later/>

Class Content [color=red]Implements System.IComparable[/color]

This may fix your problem. Excuse my vb.net coding skills but it seems that System.Collections.Generic.IComparer.Compare throws an ArgumentException (which is being thrown) if the classes being sorted don't implement the IComparable interface (which it appears they don't).

Lucifer 2

Ok, here is what I've determined so far...

1. x.Equals(y) is not always false. So my original line

if x.Equals(y) then return 0

should in my mind do the trick. However it doesn't

2. I tried changing this line to be

If x.Equals(y) OrElse x.MTCode = y.MTCode Then Return 0

as MTCode 'should' be a unique integer for each content object. However, I still get the error :mad:

3. I still don't know whats causing the problem, becuase I can't determine which values of 'x' and 'y' throw the error. The values of x and y are out of scope at the earliest possible chance i get to catch the exception

Plus I don't have the patience to step through remebering the values as the error only occurs maybe every 50 or so page loads. And each page load calls Compare(,) about 10 times.

Torak

print the compares to a log

comparing <x> with <y>

should let you see exactly which values raise the error.

It is the simplest way to solve this..

Lucifer 2

There are several overloaded methods for Array.Sort. Two of which are:

Array.Sort (Array) Sorts the elements in an entire one-dimensional Array using the IComparable implementation of each element of the Array.

Array.Sort (Array, IComparer) Sorts the elements in a one-dimensional Array using the specified IComparer.

In the first case the objects in the array must imlement the IComparable interface as Evil Phil points out. However, I'm calling the second method which takes in an object which implemnts the IComparer(of Content) interface. Therefore it's not necessary for the Content class to implement the IComparable interface.

Note I originally used the first method for sorting alphabetically, however, I wanted to be able to specify the sorting method, hence the second method.

I added loggin to the Compare method of Content+Random as follows:

Public Function Compare(ByVal x As Content, ByVal y As Content) As Integer Implements System.Collections.Generic.IComparer(Of Content).Compare
            Logger.Log(BitFactory.Logging.LogSeverity.Info, Me, String.Format("Start compare: x={0}, y={1}", x, y))
            If x Is Nothing AndAlso y Is Nothing Then Return 0
            If x Is Nothing AndAlso y IsNot Nothing Then Return -1
            If x IsNot Nothing AndAlso y Is Nothing Then Return 1
            Logger.Log(BitFactory.Logging.LogSeverity.Info, Me, String.Format("MTCode: x={0}, y={1}", x.MTCode, y.MTCode))
            If x.Equals(y) OrElse x.MTCode = y.MTCode Then Return 0
            Select Case _R.Next() Mod 2
                Case 0 : Compare = -1
                Case 1 : Compare = 1
            End Select
            Logger.Log(BitFactory.Logging.LogSeverity.Info, Me, String.Format("End compare: returning {0}", Compare))
        End Function

and got the following log (I'm not sure how much I can deduce from this.
Note there are only four Content objects in the list with the folloing MTCodes (most likely, but not necessarily originally in this order):
1000611
1000612
1000613
1000614

Log:

{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- End compare: returning -1
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- MTCode: x=1000612, y=1000611
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- Start compare: x=Content, y=Content
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- End compare: returning -1
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- MTCode: x=1000612, y=1000614
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- Start compare: x=Content, y=Content
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- End compare: returning -1
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- MTCode: x=1000612, y=1000613
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- Start compare: x=Content, y=Content
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- MTCode: x=1000612, y=1000612
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- Start compare: x=Content, y=Content
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- End compare: returning -1
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- MTCode: x=1000613, y=1000612
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- Start compare: x=Content, y=Content
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- End compare: returning 1
{Content+Random} --<Info> -- 23/06/2006 13:25:27 -- MTCode: x=1000612, y=1000614
{Content+Random} --<Info> -- 23/06/2006 13:25:26 -- Start compare: x=Content, y=Content
{Content+Random} --<Info> -- 23/06/2006 13:25:26 -- MTCode: x=1000612, y=1000612
{Content+Random} --<Info> -- 23/06/2006 13:25:26 -- Start compare: x=Content, y=Content
{Content+Random} --<Info> -- 23/06/2006 13:25:26 -- End compare: returning -1
{Content+Random} --<Info> -- 23/06/2006 13:25:26 -- MTCode: x=1000611, y=1000612
{Content+Random} --<Info> -- 23/06/2006 13:25:26 -- Start compare: x=Content, y=Content

P.S The log file is in order of time descending.

Torak

If x Is Nothing AndAlso y Is Nothing Then Return 0
If x Is Nothing AndAlso y IsNot Nothing Then Return -1
If x IsNot Nothing AndAlso y Is Nothing Then Return 1

>>

If x Is Nothing Then
Logger.Log(BitFactory.Logging.LogSeverity.Info, Me, "X IS Nothing")

Return -1
End If

If y Is Nothing Then
Logger.Log(BitFactory.Logging.LogSeverity.Info, Me, "Y IS Nothing")

Return +1
End If

Lucifer 2

X and Y are never Nothing by the looks of it. Nor should they ever be.

Logger.Log(BitFactory.Logging.LogSeverity.Info, Me, String.Format("Start compare: x={0}, y={1}", x, y))

would print

Start compare: x=, y=

if they were.

Torak

Sorry dude..

Looks like i completely misread that..

Whats getting me is that the lines are not coming out in the order..

Really sorry I couldn't help more...

Lucifer 2

Ok, I've created a console test harness to try and get to the bottom to this.
I've noticed the following strange behaviour I'm hoping someone can shed some light on!

1. When the list to be sorted contains only 3 items everyone works fine, unless I remove the

if x.equals(y)

check

2. When the list contains more than 3 items the error occurs within about 3 sorts without the

if x.equals(y)

check, and after about 60 with the check.

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

Mutant_Fruit

Here's a bit of C#, i'm too lazy to attempt psuedo code. It demonstrates the point well enough i think...

Person[] people = new Person[5];
			
			people[0] = new Person();
			people[0].age = 15;
			people[0].name = "roisin";

			people[1] = new Person();
			people[1].age = 27;
			people[1].name = "dad";

			people[2] = new Person();
			people[2].age = 15;
			people[2].name = "emily";

			people[3] = new Person();
			people[3].age = 10;
			people[3].name = "ben";

			people[4] = new Person();
			people[4].age = 10;
			people[4].name = "tom";


			Array.Sort(people);
			string temp = "";
			return 0;
		}
		private class Person : IComparable
		{
			public string name;
			public int age;

			public Person()
			{
			}
			public int CompareTo(object obj)
			{
				Person person2 = (Person)obj;
				if(person2 == null)
					return 1;// The thing we're comparing too is a person, so this is greater

				if(this.age != person2.age)	// If they aren't the same age, compare by age
					return this.age - person2.age;

				return this.name.CompareTo(person2.name);	// Lastly, compare by name
			}
		}

Lucifer 2

I'm not quite sure how this is a solution to my problem. The crux of my problem seems to be (according to the exception message anyway) that my compare function isn't returning 0 when comparing an object to itself.

Although thats why I have

if x.Equals(y) then compare = 0

.

Note that I'm implementing the IComparer interface on the helper class, and not the ICompare interface on the person class.
[edit]see post above regarding Array.Sort overloads[/edit]

Also, I'm 'sorting' randomly (not sure if this is an oxymoron). So I'm not really interested in comparing the values of the object's properties.

I appreciate your help. However, I'm interested in why the code I've posted isn't working...in my mind it should.....maybe I'm misssing something.

Thanks for your help.

Mutant_Fruit

Well, could you tell me what exactly you're trying to achieve in plain ole' english. My brain is a bit fried, so deciphering VB isn't what i really want to do

BTW: Do you need to overload Equals? you're comparing x.Equals(y), but is that doing a valid comparison?

Lucifer 2

Basically I was trying to randomize the list by implementing the IComparer interface which randomly returned either 1, 0, or -1 in the compare function.

Seemingly this was never going to work properly, the problem being that during a sort there must be some consistancy, i.e. if x is compared to y and 1 is returned, then if y is later compared to x, then -1 should be returned. Randomly returning -1 or 1 screws this up to put it bluntly.

My problem was compounded by the misleading error message in the exception object being thrown.

Thanks to all those who helped, and also to the guys on the MSDN forums who pointed out the error in my ways. See the link below for their feedback.

http://msdn.microsoft.com/newsgroups/default.aspx?dg=microsoft.public.dotnet.framework&mid=1ee07964-5cdc-4afc-af2b-ef058aeedda1


My new code looks like the following:

Private Function Randomize(ByVal list As Collections.Generic.List(Of Content)) As Collections.Generic.List(Of Content)
        Randomize = New Collections.Generic.List(Of Content)
        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

Mutant_Fruit

Aye, i was thinking that could be the problem, but didn't know

The only other thing is i think you need to give a "seed" number to Random. i.e. Dim r As New Random(seed);

Seed could be DateTime.Now.Ticks or DateTime.Now.Miliseconds. You need to do this, otherwise the Random generator will always return the same "random" values.

If you start your program and run it, then restart and run again you should see that the "random" order is the same every time you restart and rerun the randomize function.