[RESOLVED] Sorting a Listview acting as treeview (topmost parent only)

[dee-u]

I have come across the LVItemTree of Brad Martinez here. I want to add a sorting capability to it even with the topmost parent only but I'm not sure how to do it, can anyone give me some ideas of workarounds?

Thanks!

[WoF]

Well, I took a look at the LVItemTree control you are referring to.
The ListView has a "Sorted" property and if you activate this you will easily see, that the sorting will completely destroy the hierarchy of the construction, since it is no real hierarchical TreeView.
You would have to implement an own sorting algorithm which will only compare the items which are designated as parents.

If I'd have to do this, I'd approach like this:
1.) Create an array with the indexes of the "parent" items, together with the number of their child items.
2.) Sort this array using a sort algorithm of your choice, comparing the indexed items, but swapping only the indexes (and number of children) in your array.
3.) Append all items in the new sequence to the end of the current ListView.ItemList
4.) Delete the items as they were previously in the old sequence.

If you really need that, and you find my elaborations yet not clear enough, I could help you to develope such a sorting function on a given sample.

[dee-u]

I am also thinking along that line though your procedure are clearer than mine. Instead of appending them can't it be done that their indexes are just updated according to their position in the sorted list? As such it should be faster since appending them would mean appending also all their child items. If the indexes are just updated then the opened nodes would be preserved. What do you think?

[WoF]

Unfortunately, the .Index property of a listitem is write protected, which seems only logical if you consider that it represents its absolute position within the item list.
Think about what would happen if this was allowed:

LV.ListItems(1).Index = 2 'can't be done

What should happen to the item which currently has an index of 2?
What if item 1 is the only item? Then there will be no more item with index 1? The indices of all items must remain subsequent. No gaps allowed.
The index is created when an item is added with .ListItems.Add , , "NewItem"
If you use LV.ListItems.Add 2,, "NewItem", the new item is inserted at position 2. All subsequent existing items move up one position. So shuffling a group of items by adding and removing them one after the other seems to be troublesome.

But there is more: You also want to keep the sequence of the children, because the only means they are assigned to a parent is that they immediately follow an item which is marked as a parent. If you want to move the position of a parent, all its children have to follow on subsequent positions or the pseudo-hierarchie of the items is lost. You always have to know that this is NOT a real TreeView. In a TreeView, when you move a node to another position, it takes all its children with it. In this ListView it does not so, automatically. Only the programmer has to care of that.

The idea of sorting first, without actually moving the items within the ListViews ItemList, came up for speed. We only shuffle numbers in an array and not complex items in a list.
Once the new sorted sequence is established, you have to rearrange the items in the .ItemList
I thought, just appending the items again in the new sequence and then deleting the first n items which represented the old sequence would do the trick neatly.

Another Idea could be, to load all items in an array, clear the ItemList and then re-append them in the new sequence, but I would tend to the other solution.

Edit: Personally I have worked a lot with the real TreeView which, after understanding it seems to offer quite a variety of structuring possibilities. What is the reason you want to "abuse" a ListView for kind of a TreeView? Maybe the real TreeView is actually what you want.

[WoF]

In addition I invite you to study the LVTreeView sample program a little closer:
When expanding/collapsing a "node" it simply adds/removes dummy child items which are not managed at all in no respect. Usually you will want to have "real" child items which will be kept stored somewhere. This little demo sample does not seem to cope with that. It simply creates a new set of dummy children whenever you expand a node and deletes them when you collapse it.
To use this priciple you would have to implement an own storage management to maintain real child items somewhere in your program (in a collection or an array).

[dee-u]

If it is not too much to ask then could I ask for a sample solution from you Sir? Yes I want to use the LVItemTree since it accomodates my requirement, no problem with the dynamic addition and deletion of child nodes, it is exactly what I want it to be.

TIA

[WoF]

Right. I shall find some time later today and will make a short sample.

[WoF]

Well. I've taken the LVItemTree sample and wrote a module Sorting.bas which copes the parent sorting.

I have made minor changes to the existing code only to show which parent a child item belongs to and to create an initial sequence in a reverse order.
To test it, you have to restart everytime you have sorted once.

You can test, by starting, then expanding one or more "nodes" and then sort by clicking on one of the column headers.
You will note that the parent items will get sorted, while the child items stay with their respective parent. It might be not so obvious, but the children get NOT sorted.

The responsible sub to call is

Public Sub SortParentItems(LV As ListView)

  IndicateParents LV      'make a list of all parent item indexes

  BubbleSortIndexes LV 'sort them
  
  RearrangeItems LV
 
End Sub

IndicateParents makes a list of all items which are obviously parents and counts their children if there are any

BubbleSortIndexes is a simple little sorting algorithm to sort the indexes (yes, yes could be done better )

RearrangeItems works as described before, like: the items are duplicated in the new sequence to the end of the list and then the old sequence is removed.

These subs are all private to Sorting.bas together with some auxilliary functions like DuplicateItem which i have to say was not too trivial to figure out how to maintain all properties of an item (image, indentation) when duplicating it.

Have fun studying it. It is not too complicated and if you have questions how something works, feel free to ask.

[dee-u]

Just had time now to play with your sample and I was able to make it work with all the columns and it can now sort ascending and descending.

Just one thing, in your code you are using two loops, why is this? I cannot find anywhere the usage of the variable i.

For i = 0 To NumParents - 2
    For j = 0 To NumParents - 2

Thank you so much for providing me a baseline code for this one, really appreciated!

[WoF]

You're welcome. It was just a matter of a few lines of code, so it was not perfect.

To explain how the bubblesort works:

The inner loop is running through all (remaining) elements once to make sure, the largest element is now the last one in the list.
This loop has to be iterated once for each remaining element of the list to sort, because one iteration only moves the largest element of the remaining elements to the end of the list.

The outer loop, thus, makes sure the inner loop is iterated once for each element.

Imagine a sequence 3, 4, 2, 1 to be sortet.
If you walk the inner loop step by step, it will find 4 > 2 and swap them, then it will find 4 > 1 and swap them.
After the first pass of the inner loop, the sequence is 3, 2, 1, 4, the largest element having been moved to the end.
The outer loop makes sure there is one pass for each element of the list to be sorted.
After the second pass of the inner loop the sequence is 2, 1, 3, 4, having dragged the 3 to its proper position.

Usually you do not need to walk the second pass to the end of the list, because tha largest element is already determinded. Third pass needs only to walk up to n-3, and so on

To improve the little sorting algorithm (I simply hacked together in very short time) you can make use of i to shorten each consecutive inner loop by one step:

For i = 0 To NumParents - 2
    For j = 0 To NumParents - 2 - i

This would make the sorting run faster, but with that little amount of data you wouldn't even notice.
I simply didn't notice that I forgot that little detail, which makes the bubble sort a leeetle more efficient.

But if you are interested in really quick sorting I should point out that there are much more efficient algorithms "on the market". Just look for "quicksort"

[dee-u]

Using a QuickSort procedure I found in vbforums.com I came up with this. The only thing missing is that upon sorting a certain column and upon clicking another columnheader it won't sort immediately, I know it is just a logic flaw, could you help me sort it out? Somehow, I think I need to determine if a certain column is already sorted or not and if I need to sort it ascendingly or descendingly but I am at loss on how to do that.

'ColumnClick
Private Sub ListView1_ColumnClick(ByVal ColumnHeader As ComctlLib.ColumnHeader)
    SortParentItems ListView1, bolAsc, ColumnHeader.index
    bolAsc = Not bolAsc
End Sub

'Sorting module
Option Explicit

Private ParentIndex()   As Long
Private NumChildren()   As Long
Private NumParents      As Long
Private ItemText()      As String

' this is the public sort routine to be called for an LVItemTree
' it will sort the parent items only and leave the children untouched
' nevertheless all children stay behind their respective parent

Public Sub SortParentItems(LV As ListView, ByVal ascending As Boolean, ByVal ColumnIndex As Long)
    
    IndicateParents LV, ColumnIndex 'make a list of all parent item indexes
    
    QuickSortIndexes
    If ascending = True Then
        RearrangeItemsAscending LV
    Else
        RearrangeItemsDescending LV
    End If
End Sub

Private Sub RearrangeItemsAscending(LV As ListView)
    ' this assumes that the index array has been sorted
    Dim i As Long
    Dim C As Long
    Dim n As Long
  
    'first append all items in sorted order
    'c counts the duplicated items to be deleted afterwards
    For i = 0 To NumParents - 1
        DuplicateItem LV, ParentIndex(i)
        n = n + 1
        For C = 1 To NumChildren(i)
            DuplicateItem LV, ParentIndex(i) + C
            n = n + 1
        Next
    Next

    'now delete the unsorted bunch of items
    For i = 1 To n
        LV.ListItems.Remove 1
    Next
End Sub

Private Sub RearrangeItemsDescending(LV As ListView)
    ' this assumes that the index array has been sorted
    Dim i As Long
    Dim C As Long
    Dim n As Long
  
    'first append all items in sorted order
    'c counts the duplicated items to be deleted afterwards
    For i = NumParents - 1 To 0 Step -1
        DuplicateItem LV, ParentIndex(i)
        n = n + 1
        For C = 1 To NumChildren(i)
            DuplicateItem LV, ParentIndex(i) + C
            n = n + 1
        Next
    Next

    'now delete the unsorted bunch of items
    For i = 1 To n
        LV.ListItems.Remove 1
    Next
End Sub

Private Sub DuplicateItem(LV As ListView, iItem As Long)
    ' duplicates an indexed item to the end of the list
    Dim lit As ListItem 'to-item
    Dim lif As ListItem 'from-item
    Dim ind As Long
    Dim lvs As LVItemStates
    Dim s&
  
    Set lif = LV.ListItems(iItem)
    Set lit = LV.ListItems.Add(, , lif.Text, , lif.SmallIcon)
  
    'when duplicating an item we have to take care of the subitems/columns
    For s = 1 To LV.ColumnHeaders.Count - 1
        lit.SubItems(s) = lif.SubItems(s)
    Next
  
    'and we have to duplicate the extended item state or we lose indentation
    lvs = Listview_GetItemStateEx(LV.hWnd, iItem - 1, ind)
    Listview_SetItemStateEx LV.hWnd, lit.index - 1, ind, lvs

End Sub

Private Sub IndicateParents(LV As ListView, ByVal ColumnIndex As Long)
    'count the parent items in LV and make a list of parent indexes
    Dim p As Long
    Dim i As Long
    Dim n As Long

    For i = 1 To LV.ListItems.Count
        If IsParent(LV, i) Then p = p + 1
    Next
    NumParents = p
  
    ReDim ParentIndex(p - 1)
    ReDim NumChildren(p - 1)
    ReDim ItemText(p - 1)
    
    n = 0
  
    'collect all parent item indexes
    For i = 1 To LV.ListItems.Count
        If IsParent(LV, i) Then
            ParentIndex(n) = i 'store index of this parent
            If ColumnIndex = 1 Then
                ItemText(n) = LV.ListItems.Item(i)
            Else
                ItemText(n) = LV.ListItems.Item(i).SubItems(ColumnIndex - 1)
            End If
            If n > 0 Then
                'determine the number of children of the PREVIOUS parent
                NumChildren(n - 1) = ParentIndex(n) - ParentIndex(n - 1) - 1
            End If
            n = n + 1
        End If
    Next
    'get number of children of the last parent
    NumChildren(p - 1) = LV.ListItems.Count - ParentIndex(p - 1)

    ' now we have an array of indexes of all parent items and
    ' one array with all child items of each parent
  
End Sub

Private Function IsParent(LV As ListView, iItem As Long) As Boolean
    ' this returns true if the indentation of an item is 0, which indicates a parent
    Dim iIndent As Long
    Listview_GetItemStateEx LV.hWnd, iItem - 1, iIndent
    IsParent = iIndent < 1
End Function

Private Sub QuickSortIndexes()
    If NumParents < 2 Then Exit Sub 'nothing to sort then
    QuickSort ItemText, LBound(ItemText), UBound(ItemText)
End Sub

Private Sub QuickSort(C() As String, ByVal First As Long, ByVal Last As Long)
    '
    '  Made by Michael Ciurescu (CVMichael from vbforums.com)
    '  Original thread: http://www.vbforums.com/showthread.php?t=231925
    '
    Dim Low         As Long
    Dim High        As Long
    Dim MidValue    As String
    
    Low = First
    High = Last
    MidValue = C((First + Last) \ 2)
    
    Do
        While C(Low) < MidValue
            Low = Low + 1
        Wend
        
        While C(High) > MidValue
            High = High - 1
        Wend
        
        If Low <= High Then
            Swap C(Low), C(High)
            'modification
            SwapLong ParentIndex(Low), ParentIndex(High)
            SwapLong NumChildren(Low), NumChildren(High)
            Low = Low + 1
            High = High - 1
        End If
    Loop While Low <= High
    
    If First < High Then QuickSort C, First, High
    If Low < Last Then QuickSort C, Low, Last
End Sub
 
Private Sub Swap(ByRef A As String, ByRef B As String)
    Dim T As String
    
    T = A
    A = B
    B = T
End Sub
 
Private Sub SwapLong(ByRef A As Long, ByRef B As Long)
    Dim T As Long
    
    T = A
    A = B
    B = T
End Sub

[WoF]

Well yes, I shall look at it tonight. Don't have the code here now.

[WoF]

Please tell me: As I recall the sorting I wrote does only take care of parent items. To see how you took care of child items and how you manage them, I'd have to see more of your personal code. My version did not care of the subitems, but if you wanna sort the subitems ther must be special provision in the sorting scheme.
I don't quite understand yet, where your problem lies.

Sorry, I got a little problem here, I have to take care of. So for more details I have to come back to you tomorrow.

[dee-u]

I did not change much of the code, I only took account on sorting the subitems (not child items) also when their columnheaders are clicked. The problem lies when the items in the columns are already sorted but I don't know if ascendingly or descendingly so that if I clicked the columnheaders then they are supposed to be sorted descendingly if they are already sorted ascendingly and vice versa.

I am not sure if a flag will do or that I still have to loop through the items to determine how they are sorted?

[dglienna]

Check any two in sequence, and see if one is > or < than the next