Question Advanced sorting problem

[Adagio]

Hi, having a bit of a sorting problem here, hoping some kind sould can help me with it

Situation: I have a class with three properties:
A (integer), B (string), C (integer)

I have added a list of these items in random sequence to a list:

A B C
3 Bacon 1
1 Doom 3
2 Even 2
1 Abe 1
2 Zebra 1
1 True 2

At first it has to group them together on property A:

1 Doom 3
1 Abe 1
1 True 2
2 Even 2
2 Zebra 1
3 Bacon 1

The next part is sorting on property C, still keep them in a group:

1 Abe 1
1 True 2
1 Doom 3
2 Zebra 1
2 Even 2
3 Bacon 1


The last part is sorting on property B for groups. In the above situation group 1 is using "Abe" for sorting, group 2 is using "Zebra" and group 3 is using "Bacon". This way group 3 should be after group 1, but before group 2:

1 Abe 1
1 True 2
1 Doom 3
3 Bacon 1
2 Zebra 1
2 Even 2


Would it be possible to sort like this?

In my class I have Implemented IComparable, but I can't seem to figure out what I would need to write in CompareTo. Or do I need to take another aproach to sorting this list?

 

[jmcilhinney]

IComparable won't really help you here because it can only compare by a set property or list of properties. The way you compare items can't change depending on the circumstances, which is what you need. You will need to define a method that compares instances of your class in a variable way. That method must either be a member of a class that implements the IComparer interface or else it must be invoked via a Comparison delegate. Following are code examples of each.

Using Comparison(Of T) delegate:

Module Module1

    Sub Main()
        Dim arr As Thing() = {New Thing(3, "Bacon", 1), _
                              New Thing(1, "Doom", 3), _
                              New Thing(2, "Even", 2), _
                              New Thing(1, "Abe", 1), _
                              New Thing(2, "Zebra", 1), _
                              New Thing(1, "True", 2)}

        Console.WriteLine("Original order:")

        For Each t As Thing In arr
            Console.WriteLine(t.ToString())
        Next

        Console.WriteLine()
        Array.Sort(arr, New Comparison(Of Thing)(AddressOf CompareByA))
        Console.WriteLine("Sorted by A:")

        For Each t As Thing In arr
            Console.WriteLine(t.ToString())
        Next

        Console.WriteLine()
        Array.Sort(arr, New Comparison(Of Thing)(AddressOf CompareByB))
        Console.WriteLine("Sorted by B:")

        For Each t As Thing In arr
            Console.WriteLine(t.ToString())
        Next

        Console.WriteLine()
        Array.Sort(arr, New Comparison(Of Thing)(AddressOf CompareByC))
        Console.WriteLine("Sorted by C:")

        For Each t As Thing In arr
            Console.WriteLine(t.ToString())
        Next

        Console.ReadLine()
    End Sub

    Private Function CompareByA(ByVal x As Thing, ByVal y As Thing) As Integer
        Return x.A.CompareTo(y.A)
    End Function

    Private Function CompareByB(ByVal x As Thing, ByVal y As Thing) As Integer
        Return x.B.CompareTo(y.B)
    End Function

    Private Function CompareByC(ByVal x As Thing, ByVal y As Thing) As Integer
        Return x.C.CompareTo(y.C)
    End Function

End Module


Public Class Thing

    Private _a As Integer
    Private _b As String
    Private _c As Integer

    Public Property A() As Integer
        Get
            Return _a
        End Get
        Set(ByVal value As Integer)
            _a = value
        End Set
    End Property

    Public Property B() As String
        Get
            Return _b
        End Get
        Set(ByVal value As String)
            _b = value
        End Set
    End Property

    Public Property C() As Integer
        Get
            Return _c
        End Get
        Set(ByVal value As Integer)
            _c = value
        End Set
    End Property

    Public Sub New(ByVal a As Integer, ByVal b As String, ByVal c As Integer)
        Me.A = a
        Me.B = b
        Me.C = c
    End Sub

    Public Overrides Function ToString() As String
        Return String.Format("Thing {{A = {0}, B = {1}, C = {2}}}", Me.A, Me.B, Me.C)
    End Function

End Class

Using IComparer(Of T) interface:

Module Module1

    Sub Main()
        Dim arr As Thing() = {New Thing(3, "Bacon", 1), _
                              New Thing(1, "Doom", 3), _
                              New Thing(2, "Even", 2), _
                              New Thing(1, "Abe", 1), _
                              New Thing(2, "Zebra", 1), _
                              New Thing(1, "True", 2)}
        Dim comparer As New ThingComparer

        Console.WriteLine("Original order:")

        For Each t As Thing In arr
            Console.WriteLine(t.ToString())
        Next

        Console.WriteLine()
        comparer.SortPropertyName = ThingComparer.SortProperty.A
        Array.Sort(arr, comparer)
        Console.WriteLine("Sorted by A:")

        For Each t As Thing In arr
            Console.WriteLine(t.ToString())
        Next

        Console.WriteLine()
        comparer.SortPropertyName = ThingComparer.SortProperty.B
        Array.Sort(arr, comparer)
        Console.WriteLine("Sorted by B:")

        For Each t As Thing In arr
            Console.WriteLine(t.ToString())
        Next

        Console.WriteLine()
        comparer.SortPropertyName = ThingComparer.SortProperty.C
        Array.Sort(arr, comparer)
        Console.WriteLine("Sorted by C:")

        For Each t As Thing In arr
            Console.WriteLine(t.ToString())
        Next

        Console.ReadLine()
    End Sub

End Module


Public Class Thing

    Private _a As Integer
    Private _b As String
    Private _c As Integer

    Public Property A() As Integer
        Get
            Return _a
        End Get
        Set(ByVal value As Integer)
            _a = value
        End Set
    End Property

    Public Property B() As String
        Get
            Return _b
        End Get
        Set(ByVal value As String)
            _b = value
        End Set
    End Property

    Public Property C() As Integer
        Get
            Return _c
        End Get
        Set(ByVal value As Integer)
            _c = value
        End Set
    End Property

    Public Sub New(ByVal a As Integer, ByVal b As String, ByVal c As Integer)
        Me.A = a
        Me.B = b
        Me.C = c
    End Sub

    Public Overrides Function ToString() As String
        Return String.Format("Thing {{A = {0}, B = {1}, C = {2}}}", Me.A, Me.B, Me.C)
    End Function

End Class


Public Class ThingComparer
    Implements IComparer(Of Thing)

    Public Enum SortProperty
        A
        B
        C
    End Enum


    Private _sortPropertyName As SortProperty

    Public Property SortPropertyName() As SortProperty
        Get
            Return _sortPropertyName
        End Get
        Set(ByVal value As SortProperty)
            _sortPropertyName = value
        End Set
    End Property

    Public Function Compare(ByVal x As Thing, _
                            ByVal y As Thing) As Integer Implements IComparer(Of Thing).Compare
        Select Case SortPropertyName
            Case SortProperty.A
                Return x.A.CompareTo(y.A)
            Case SortProperty.B
                Return x.B.CompareTo(y.B)
            Case SortProperty.C
                Return x.C.CompareTo(y.C)
        End Select
    End Function

End Class

You can run those code examples in a Console Application project. Just replace all the code with either of those two snippets.

 

[InertiaM]

I've varied jmcilhinney's code slightly (and it may have some bad practices which I'm sure he'll correct for me ) but I think it does what you want:

Option Explicit On
Option Strict On

Module Module1

    Sub Main()
        Dim ListOfThings As New List(Of Thing)
        ListOfThings.Add(New Thing(3, "Bacon", 1))
        ListOfThings.Add(New Thing(1, "Doom", 3))
        ListOfThings.Add(New Thing(2, "Even", 2))
        ListOfThings.Add(New Thing(1, "Abe", 1))
        ListOfThings.Add(New Thing(2, "Zebra", 1))
        ListOfThings.Add(New Thing(1, "True", 2))

        Console.WriteLine("Original order:")
        For Each t As Thing In ListOfThings
            Console.WriteLine(t.ToString())
        Next

        Console.WriteLine()
        Console.WriteLine("Sorted by A:")
        ListOfThings.Sort(Thing.CompareBy_A)
        For Each t As Thing In ListOfThings
            Console.WriteLine(t.ToString())
        Next

        Console.WriteLine()
        Console.WriteLine("Sorted by B:")
        ListOfThings.Sort(Thing.CompareBy_B)
        For Each t As Thing In ListOfThings
            Console.WriteLine(t.ToString())
        Next

        Console.WriteLine()
        Console.WriteLine("Sorted by C:")
        ListOfThings.Sort(Thing.CompareBy_C)
        For Each t As Thing In ListOfThings
            Console.WriteLine(t.ToString())
        Next

        Console.WriteLine()
        Console.WriteLine("Sorted by ACB:")
        ListOfThings.Sort(Thing.CompareBy_A_C_B)
        For Each t As Thing In ListOfThings
            Console.WriteLine(t.ToString())
        Next


        Console.ReadLine()
    End Sub

End Module


Public Class Thing

    Private _a As Integer
    Private _b As String
    Private _c As Integer

    Public Property A() As Integer
        Get
            Return _a
        End Get
        Set(ByVal value As Integer)
            _a = value
        End Set
    End Property

    Public Property B() As String
        Get
            Return _b
        End Get
        Set(ByVal value As String)
            _b = value
        End Set
    End Property

    Public Property C() As Integer
        Get
            Return _c
        End Get
        Set(ByVal value As Integer)
            _c = value
        End Set
    End Property

    Public Sub New(ByVal a As Integer, ByVal b As String, ByVal c As Integer)
        Me.A = a
        Me.B = b
        Me.C = c
    End Sub

    Public Overrides Function ToString() As String
        Return String.Format("Thing {{A = {0}, B = {1}, C = {2}}}", Me.A, Me.B, Me.C)
    End Function

    Shared Function CompareBy_A() As IComparer(Of Thing)
        Return New ThingComparer(ThingComparer.SortProperty.A)
    End Function

    Shared Function CompareBy_B() As IComparer(Of Thing)
        Return New ThingComparer(ThingComparer.SortProperty.B)
    End Function

    Shared Function CompareBy_C() As IComparer(Of Thing)
        Return New ThingComparer(ThingComparer.SortProperty.C)
    End Function

    Shared Function CompareBy_A_C_B() As IComparer(Of Thing)
        Return New ThingComparer(ThingComparer.SortProperty.ACB)
    End Function

End Class


Public Class ThingComparer
    Implements IComparer(Of Thing)

    Public Enum SortProperty
        A
        B
        C
        ACB
    End Enum


    Private _sortPropertyName As SortProperty

    Public Property SortPropertyName() As SortProperty
        Get
            Return _sortPropertyName
        End Get
        Set(ByVal value As SortProperty)
            _sortPropertyName = value
        End Set
    End Property

    Sub New(ByVal WhatSortOrder As SortProperty)
        _sortPropertyName = WhatSortOrder
    End Sub


    Public Function Compare(ByVal x As Thing, _
                            ByVal y As Thing) As Integer Implements IComparer(Of Thing).Compare
        Select Case SortPropertyName
            Case SortProperty.A
                Return x.A.CompareTo(y.A)
            Case SortProperty.B
                Return x.B.CompareTo(y.B)
            Case SortProperty.C
                Return x.C.CompareTo(y.C)
            Case SortProperty.ACB
                If x.A < y.A Then
                    Return -1
                ElseIf x.A > y.A Then
                    Return 1
                ElseIf x.A = y.A Then
                    If x.C < y.C Then
                        Return -1
                    ElseIf x.C > y.C Then
                        Return 1
                    Else
                        If x.B < y.B Then
                            Return -1
                        ElseIf x.B > y.B Then
                            Return 1
                        Else
                            Return 0 'A=A and C=C and B=B
                        End If
                    End If
                End If
        End Select
    End Function

End Class

 

[Adagio]

Thank you, both of you, this is very close to what I'm looking for. Except that it's B, (group of A), C

I have an idea that might be able to take care of the last problem:

Make a new class called GroupThing, which contains a list of all items where A is the same, then sort the list of these GroupThing objects on B (in the example three instances of GroupThing would be created). The items in a GroupThing will be sorted on C

I'll try to whip something up and see if I can make it work

 

[InertiaM]

Edit: re-read post, and it didnt answer the question.

 

[Adagio]

This code seems to solve the last problem... it could probably be done a lot better

Public Class GroupThing
    Implements IComparable

    Private _lst As New List(Of Thing)

    Public Sub New(ByVal t As Thing)
        _lst.Add(t)
    End Sub

    Public Sub Add(ByVal t As Thing)
        If _lst(0).A <> t.A Then Throw New Exception("Wrong item")

        _lst.Add(t)
    End Sub

    Public ReadOnly Property lst() As List(Of Thing)
        Get
            Return _lst
        End Get
    End Property

    Public Function CompareTo(ByVal obj As Object) As Integer Implements System.IComparable.CompareTo
        Dim item As GroupThing = DirectCast(obj, GroupThing)

        If item._lst(0).B > Me._lst(0).B Then
            Return -1
        Else
            Return 1
        End If
    End Function

End Class


Sub Main()

 Dim ListOfThings As New List(Of Thing)
        ListOfThings.Add(New Thing(3, "Bacon", 1))
        ListOfThings.Add(New Thing(1, "Doom", 3))
        ListOfThings.Add(New Thing(2, "Even", 2))
        ListOfThings.Add(New Thing(1, "Abe", 1))
        ListOfThings.Add(New Thing(2, "Zebra", 1))
        ListOfThings.Add(New Thing(1, "True", 2))

        Console.WriteLine("Original order:")
        For Each t As Thing In ListOfThings
            Console.WriteLine(t.ToString())
        Next

 ListOfThings.Sort(Thing.CompareBy_A_C_B)

 Dim lastA As Integer = ListOfThings(0).A
        Dim lstGroupThing As New List(Of GroupThing)
        Dim lastGroupThing As New GroupThing(ListOfThings(0))

        For index As Integer = 1 To ListOfThings.Count - 1
            Dim item As Thing = ListOfThings(index)

            If lastA = item.A Then
                'Console.WriteLine("Adding item to group: " & lastA.ToString)
                lastGroupThing.Add(item)
            Else
                'Console.WriteLine("Creating new group: " & item.A.ToString)
                lstGroupThing.Add(lastGroupThing)
                lastA = item.A
                lastGroupThing = New GroupThing(item)
            End If
        Next

        lstGroupThing.Add(lastGroupThing)

        lstGroupThing.Sort()

        For Each gt As GroupThing In lstGroupThing
            For Each t As Thing In gt.lst
                Console.WriteLine(t.ToString())
            Next
        Next
End Sub

 

[jmcilhinney]

I think I may have misunderstood what you wanted. I thought you wanted to be able to sort on each property individually but now I think you're saying you want to sort on all three at the same time. In that case IComparable is the answer. Your CompareTo method would just look like this:

Public Function CompareTo(ByVal obj As Object) As Integer Implements System.IComparable.CompareTo
    Dim other As Thing = DirectCast(obj, Thing)
    Dim result As Integer = Me.A.CompareTo(other.A)

    If result = 0 Then
        result = Me.C.CompareTo(other.C)

        If result = 0 Then
            result = Me.B.CompareTo(other.B)
        End If
    End If

    Return result
End Function

Public Function CompareTo(ByVal other As Thing) As Integer Implements System.IComparable(Of Thing).CompareTo
    Dim result As Integer = Me.A.CompareTo(other.A)

    If result = 0 Then
        result = Me.C.CompareTo(other.C)

        If result = 0 Then
            result = Me.B.CompareTo(other.B)
        End If
    End If

    Return result
End Function

Note that I've included the standard and generic implementations, for implementing the standard and generic interfaces.

 

[Adagio]

Thanks a lot for the help, initial results shows that it works

 

[cjard]

I think I may have misunderstood what you wanted. I thought you wanted to be able to sort on each property individually but now I think you're saying you want to sort on all three at the same time. In that case IComparable is the answer. Your CompareTo method would just look like this:

Public Function CompareTo(ByVal obj As Object) As Integer Implements System.IComparable.CompareTo
    Dim other As Thing = DirectCast(obj, Thing)
    Dim result As Integer = Me.A.CompareTo(other.A)

    If result = 0 Then
        result = Me.C.CompareTo(other.C)

        If result = 0 Then
            result = Me.B.CompareTo(other.B)
        End If
    End If

    Return result
End Function

Public Function CompareTo(ByVal other As Thing) As Integer Implements System.IComparable(Of Thing).CompareTo
    Dim result As Integer = Me.A.CompareTo(other.A)

    If result = 0 Then
        result = Me.C.CompareTo(other.C)

        If result = 0 Then
            result = Me.B.CompareTo(other.B)
        End If
    End If

    Return result
End Function

Note that I've included the standard and generic implementations, for implementing the standard and generic interfaces.

Just a quick question here.. How does this satisfy the final requirement? This isnt quite a simple sort op of A, then C, then B because If you sort by A, you get:

1
1
1
2
2
3


But ultimately the OP wants:

1
1
1
3
2
2

whereby the 3 has risen up the sorted results by virtue of the fact that it shares the same C as Abe and Zebra, and being Bacon it sorts after Abe but before Zebra.


The OP says it works.. what I want to know is how? How can a comparator that sorts A then C then B actually reorder the list so that A becomes out-of-order?

 

[JohnH]

The kind of thing that makes you wish you had VB2008 and used LINQ

Dim things As Thing() = {New Thing(3, "Bacon", 1), _
                     New Thing(1, "Doom", 3), _
                     New Thing(2, "Even", 2), _
                     New Thing(1, "Abe", 1), _
                     New Thing(2, "Zebra", 1), _
                     New Thing(1, "True", 2)}

Dim groups = From t In things _
             Order By t.C _
             Group By t.A Into g = Group _
             Select g Order By g(0).B

For Each group As Thing() In groups
    For Each t As Thing In group
        Console.WriteLine(t.ToString)
    Next t
Next group

 

[jmcilhinney]

Just a quick question here.. How does this satisfy the final requirement? This isnt quite a simple sort op of A, then C, then B because If you sort by A, you get:

1
1
1
2
2
3


But ultimately the OP wants:

1
1
1
3
2
2

whereby the 3 has risen up the sorted results by virtue of the fact that it shares the same C as Abe and Zebra, and being Bacon it sorts after Abe but before Zebra.


The OP says it works.. what I want to know is how? How can a comparator that sorts A then C then B actually reorder the list so that A becomes out-of-order?

Hmmm... I really should read more carefully, shouldn't I? You're quite right, so the third round of sorting would have to be completely custom because each comparison depends on other values, not just those being compared.

 

[JohnH]

Without Linq the grouping can be done using dictionaries, here is a sample doing that:

Private Function sortC(ByVal x As Thing, ByVal y As Thing) As Integer
    Return x.C.CompareTo(y.C)
End Function

Private Sub groupsortsample()
    Dim things As Thing() = {New Thing(3, "Bacon", 1), _
                         New Thing(1, "Doom", 3), _
                         New Thing(2, "Even", 2), _
                         New Thing(1, "Abe", 1), _
                         New Thing(2, "Zebra", 1), _
                         New Thing(1, "True", 2)}

    'group by A
    Dim groups1 As New Dictionary(Of Integer, List(Of Thing))
    For Each t As Thing In things
        If Not groups1.ContainsKey(t.A) Then
            groups1.Add(t.A, New List(Of Thing))
        End If
        groups1(t.A).Add(t)
    Next

    'sort group internally by C
    For Each group As List(Of Thing) In groups1.Values
        group.Sort(New Comparison(Of Thing)(AddressOf sortC))
    Next

    'sort the groups themselves by B of first group item
    Dim groups2 As New SortedDictionary(Of String, List(Of Thing))
    For Each group As List(Of Thing) In groups1.Values
        groups2.Add(group(0).B, group)
    Next

    'display
    For Each group As List(Of Thing) In groups2.Values
        For Each t As Thing In group
            Console.WriteLine(t.ToString)
        Next t
    Next
End Sub

 

[cjard]

The kind of thing that makes you wish you had VB2008 and used LINQ

I knew someone would eventually come up with a use for it

 

[InertiaM]

I knew someone would eventually come up with a use for it

Can LINQ be used to calculate cjard's real age (he's been 64 for a long time now ).

If it can, I'll make it my New Years resolution to upgrade to VB2008

 

[jmcilhinney]

I knew someone would eventually come up with a use for it

If you haven't found a use for LINQ yet then you haven't looked because it's way cool and makes operations that can be otherwise quite cumbersome succinct in code and efficient in execution. Just minutes ago I wrote this code to populate a ComboBox with all the values under a Registry key:

Using key As RegistryKey = Registry.CurrentUser.OpenSubKey("Software\Microsoft\Internet Explorer\TypedURLs")
    Me.ComboBox1.DataSource = (From valueName In key.GetValueNames() _
                               Select key.GetValue(valueName)).ToArray()
End Using

Tell me that doesn't rock.