tags:

views:

47

answers:

3

I have a list of keys and values that I would like sorted by key via a custom Comparer(Of T).

I tried using a SortedDictionary, but kept getting incorrect results because it used the comparer to see if the items were the same. For example calling SortedDictionary.ContainsKey() would return false, even though it did contain the key.

When I stepped through the code after calling ContainsKey(), it would go to the comparer.Compare(x, y) function. It would then only compare against a few of the keys in the dicionary, and somehow skip the matching item (which I ensured did exist). I take it that this is some sort of optimization, where some items are skipped depending on what is returned by the comparer.Compare() function?

Is it possible to have a dictionary that only uses the comparer for sorting? Or any ideas on some way to overcome this?

Thanks a lot!

EDIT: I am using a Type object for the dictionary's key

EDIT: The comparer code: (Renderer's for a game engine that get sorted depending on their DrawOrder Property (if they have it))

Public Class RendererComparer
    Inherits Comparer(Of Type)

    Public Overrides Function Compare(ByVal x As Type, ByVal y As Type) As Integer
        If x Is y Then Return 0
        If x Is Nothing Then
            Return -1
        Else

            Dim draworderx As Integer = GetDrawOrder(x)
            Dim drawordery As Integer = GetDrawOrder(y)
            If draworderx < drawordery Then
                Return -1
            Else
                Return 1
            End If

        End If
    End Function

    Private Function GetDrawOrder(ByVal t As Type) As Integer
        Dim p As PropertyInfo = t.GetProperty("DrawOrder")

        If p Is Nothing Then Return 0

        Dim o As Object = p.GetValue(Nothing, Nothing)
        Return CInt(o)
    End Function

End Class
A: 

It sounds like you might need to override GetHashcode() to hash matching values onto the same hash key. Dictionary classes typically use hashcodes before equality testing first before comparing values for an exact match.

Hightechrider
I am using a Type object as the key, so I don't think it can be overridden?
Homeliss
I think this only applies to data-structures which are based on IEqualityComparer(i.e. hashtables). Most ordered Datastructures only use IComparer and thus the Compare method and not GetHashCode/Equals.
CodeInChaos
@CodeInChaos - you are right, Reflector confirms it's not used in this case. I'll leave the answer here though for anyone else having similar issues with dictionary related structures.
Hightechrider
+1  A: 

If you have two different items with the same GetDrawOrder then you violate the contract of comparer. As a result the sorting can break and you get undefined behavior.

In particular you violate Compare(a,b) == -Compare(b,a)

CodeInChaos
Ok, I understand. And if I make it return 0 when the GetDrawOrders are equal then I break if further. Any ideas on how else I can solve this?
Homeliss
You need to introduce some other criterion to order them by when GetDrawOrder is equal. Since you don't seem to care about their ordering how about just using the Type.FullName property(note that this changes the ordering when you rename classes, which is ugly)? Or you use a Dictionary<Type,int> together with a counter so you can order them by the order in qhich they were added. Or just require the DrawOrder to be unique and throw an exception.
CodeInChaos
I don't think that you can return Compare(a,b)=0 because then you are trying to insert the same key into the sorted dictionary twice. Keys must be unique in a SortedDictionary.
Eyal
@CodeInChaos: Thanks, that's exactly what I needed! I ordered by type name when the draworders were equal and it worked perfectly! I might switch over to something more constant in the future though. Thanks!
Homeliss
+1  A: 

Your implementation of GetDrawOrder is suspect. Are you hoping to get a static property on the class and then get its value? If so you ought to use BindingFlags.Static when you get the PropertyInfo.

If you want to add a property to a type it would be much cleaner to add a custom attribute.

e.g.

[DrawOrder(5)]
public class MyType { ...}

Then, instead, just ask for the attributes on the type that are OfType DrawOrder to get the integer draw order values and return the result from comparing them.

Hightechrider
I used a static property because it was faster than reading an attribute in my tests. And using `BindingFlags.Static` makes it even faster, thanks!
Homeliss