how to do Generic.List.BinarySearch on byRef data?


B

Buky

So, Let's say that I have an class with properies like Name, LastName & ID.
I put them into List(of myClass) and I would like to search through that
List based on my search criteria (Name & Id for example).
So, I create an Comparer, and provide it's 'reference' to an BinarySearch
functio, but each time I got incorrect results.
Where could be problem in following code?

Public Class myClass
Public Id As Int32
Public Name As String
Public LastName As String

Public Sub New()
End Sub
Protected Overrides Sub Finalize()
MyBase.Finalize()
End Sub
End Class

Public Sub test_novi()
Dim Lista As New List(Of myClass)
Dim y As Int32
Dim C As IComparer(Of MyClass)
C = New MyCompare
Dim T As New MyClass

T.Id = 1
T.Name = 2
Lista.Add(T)
T = New MyClass
T.Id = 2
T.Name = 4
Lista.Add(T)
T = New MyClass
T.Id = 3
T.Name = 6
Lista.Add(T)

Lista.Sort()
Dim T1 As New MyClass
T1.Id = 1
T1.Name = 2

y = Lista.BinarySearch(T1, C)
End Sub
End Module

Public Class MyCompare
Implements IComparer(Of MyClass)
Public Sub New()
End Sub

Protected Overrides Sub Finalize()
MyBase.Finalize()
End Sub
Public Function Compare(ByVal x As MyClass,byVal y As MyClass) As
Integer Implements IComparer(Of MyClass).Compare
If x.Id = y.Id Then
If x.Name = y.Name Then
Return 0
Else
Return -1
End If
Else
Return -2
End If
End Function
End Class
 
Ad

Advertisements

J

Jon Skeet [C# MVP]

Buky said:
So, Let's say that I have an class with properies like Name, LastName & ID.
I put them into List(of myClass) and I would like to search through that
List based on my search criteria (Name & Id for example).
So, I create an Comparer, and provide it's 'reference' to an BinarySearch
functio, but each time I got incorrect results.
Where could be problem in following code?

Well:

1) BinarySearch only works if the list is already ordered to start
with, in an order which is consistent with the comparer you use.
2) Your comparer is inconsistent - in particular, if you do
Compare(x, y) and Compare(y, x) it could return a negative number
both times - meaning that x < y and y < x.
3) You appear to have finalizers for no reason, which is a generally
bad thing to do. (You also have public fields, but I'll assume
you wouldn't do that normally.)

If you make your comparer more sensible, and sort *passing in the
comparer* before calling BinarySearch it should work.
 
B

Buky

Jon Skeet said:
Well:

1) BinarySearch only works if the list is already ordered to start
with, in an order which is consistent with the comparer you use.

does it means that I need to make some 'ordering' before binarySearch?
2) Your comparer is inconsistent - in particular, if you do
Compare(x, y) and Compare(y, x) it could return a negative number
both times - meaning that x < y and y < x.

At this moment, it's not so important for me... I would like just to make it
work :(
3) You appear to have finalizers for no reason, which is a generally
bad thing to do. (You also have public fields, but I'll assume
you wouldn't do that normally.)
yea, this is just an example...
If you make your comparer more sensible, and sort *passing in the
comparer* before calling BinarySearch it should work.

I tried to call Sort sub before it, but it gave me an exception
(InvalidOperationException - failed to compare two elements in the array)
 
Ad

Advertisements

J

Jon Skeet [C# MVP]

Buky said:
does it means that I need to make some 'ordering' before binarySearch?

so that things are said:
At this moment, it's not so important for me... I would like just to make it
work :(

Well it's important to the framework!

Think about it - binary searches only work if the items are in a
consistent order to start with. It's impossible for the items to *be*
in a consistent order when one item is simulataneously greater than and
less than another.
I tried to call Sort sub before it, but it gave me an exception
(InvalidOperationException - failed to compare two elements in the array)

You need to pass in the IComparer<T> you're going to use for the binary
search, but it will need to be consistent.
 

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