Announcement

Collapse
No announcement yet.

TreeVew Walk-Through in 20 Lines of Code

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • TreeVew Walk-Through in 20 Lines of Code

    The non-recursive algorithm I posted yesterday for listing subdirectories can also be used to walk through a TreeView in just about 20 lines of code - pretty short as compared to most examples I've seen on the forum.

    Here's the basic algorithm. The four basic arrays used are Items(), ItemsP(), ItemsS() and ItemsL() - handles, position, descriptions and levels of the nodes in the TreeView control.

    Code:
    Sub SearchTreeView(hTmp As Dword, ItemsCount As Long)
        Dim iPOS As Long, iLevel As Long, iOrder As Long
        ItemsL(ItemsCount) = iLevel :  Items(ItemsCount) = hTmp
    
        '1st item (starting point)
        Treeview Get Text hDlg, 100, hTmp To ItemsS(ItemsCount)
        ItemsP(ItemsCount) = "000000000000"     'use "000" for each level (1000 items max per level)
        ItemsS(ItemsCount) = ItemsP(ItemsCount) + Str$(ItemsL(ItemsCount)) + " " + ItemsS(ItemsCount)
    
        'cycles through all items, put various info in arrays
        While Items(iPOS)
            iOrder = 0
            Treeview Get Child hDlg, 100, Items(iPOS) To hTmp
            If hTmp Then iLevel = ItemsL(iPOS) + 1
            While hTmp
                Incr iOrder :  Incr ItemsCount
                Items(ItemsCount) =  hTmp
                ItemsL(ItemsCount) = iLevel
                ItemsP(ItemsCount) = ItemsP(iPOS)
                Mid$(ItemsP(ItemsCount),(iLevel-1)*3+1,3) =  Format$(iOrder,"000")
                Treeview Get Text hDlg, 100, hTMP To ItemsS(ItemsCount)
                ItemsS(ItemsCount) = ItemsP(ItemsCount) + Str$(ItemsL(ItemsCount)) + " " + ItemsS(ItemsCount)
                Treeview Get Next hDlg, 100, hTmp To hTmp
            Wend
            Incr iPOS
        Wend
        'sort the ItemsS array (tag Items along with it)
        ReDim Preserve ItemsS(ItemsCount), Items(ItemsCount)
        Array Sort ItemsS(), TagArray Items()
    End Sub
    With TreeView structures, which in my experience are relative small (a few hundreds of items), this algorithm work very fast. You may recall from the earlier posting on the algorithm that reading very large subdirectory structures (10K items) doesn't give an "instant" response. Also, since TreeView structures are in memory, the speed is especially enhanced over reading subdirectories from a disk drive. In my test, it scanned over 5K items as quickly as I could press the button - no noticeable delay.

    Another good thing about using the algorithm with a TreeView is that the maximum number of items is known, answering the question of how large to make the arrays that contain the results.

    And here's a complete example app using the algorithm. A short TreeView is created, the tree scanned, and then each node highlighted sequentially just to show that it works. An array with the node handles and an array with a text description of each node are the basic output.

    Code:
     #Compile Exe
     #Resource "pb-test.pbr"
     Global hDlg As Dword, hLst As Dword, hRoot As Dword, hItem As Dword, hTmp As Dword
     Global Items() As Dword, ItemsS() As String, ItemsP() As String, ItemsL() As Long
     Function PBMain() As Long
          Dialog New Pixels, 0, "TreeView Test",300,100,330,230, _
                                          %WS_OverlappedWindow, 0 To hDlg
        'create control
        Control Add Treeview, hDlg, 100, "", 10,40,150,175
        Control Add Button, hDlg, 101,"Start Search", 10,10,100,20
        Control Add Label, hDlg, 150,"<count>", 120,10,100,20, %WS_Border Or %SS_Center
    
        'create imagelist  w,h,depth,size
        ImageList New Icon 16,16,32,3 To hLst
        ImageList Add Icon hLst, "x"
        ImageList Add Icon hLst, "y"
        ImageList Add Icon hLst, "z"
        ImageList Add Icon hLst, "check"
    
        'attach imagelist
        Treeview Set ImageList hdlg, 100, hLst
    
        'add items  hdlg,id&,hPrnt,hIAftr,image&,selimage&,txt$ To hItem
        Treeview Insert Item hDlg,100,0,%TVI_Last,0,0,"Home" To hRoot
    
        Treeview Insert Item hDlg,100,hRoot,%TVI_Last,1,1,"One" To hTmp
            Treeview Insert Item hDlg,100,hTmp,%TVI_Last,1,1,"One-1" To hItem
            Treeview Insert Item hDlg,100,hTmp,%TVI_Last,2,2,"One-2" To hItem
    
        Treeview Insert Item hDlg,100,hRoot,%TVI_Last,2,2,"Two" To hTmp
            Treeview Insert Item hDlg,100,hTmp,%TVI_Last,1,1,"Two-1" To hItem
            Treeview Insert Item hDlg,100,hTmp,%TVI_Last,2,2,"Two-2" To hItem
    
        Treeview Insert Item hDlg,100,hRoot,%TVI_Last,3,3,"Three" To hTmp
            Treeview Insert Item hDlg,100,hTmp,%TVI_Last,1,1,"Three-1" To hItem
            Treeview Insert Item hDlg,100,hTmp,%TVI_Last,2,2,"Three-2" To hItem
    
        Dialog Show Modal hDlg Call DlgProc
     End Function
    
     CallBack Function DlgProc() As Long
          If Cb.Msg = %WM_Command And Cb.Ctl = 101 And Cb.CtlMsg = %BN_Clicked Then
              'initialize variables and dimension arrays
              Dim iCount As Long, hSelected As Dword, ItemsCount As Long
              Treeview Get Count hDlg, 100 To iCount   'max items is no more than entire tree
              ReDim Items(iCount), ItemsS(iCount), ItemsP(iCount), ItemsL(iCount)
              'Items-handles, ItemsS-sort string, ItemP-position string, ItemsL-level
    
              'get the Tree data
              Treeview Get Select hDlg, 100 To hSelected
              SearchTreeView(hSelected, ItemsCount)
    
              'Remove empty elements, sort and display the array ItemsS()
              Control Add ListBox, hDlg, 200,ItemsS(), 170,40,150,175
              Control Set Text hDlg, 150, Str$(ItemsCount+1)
              Dialog ReDraw hDlg
    
              'walk through tree from starting point, highlighting each item
              For iCount = 0 To UBound(Items)
                  Treeview Select hDlg, 100, Items(iCount)
                  Sleep 400
              Next i
    
          End If
     End Function
    
    Sub SearchTreeView(hTmp As Dword, ItemsCount As Long)
        Dim iPOS As Long, iLevel As Long, iOrder As Long
        ItemsL(ItemsCount) = iLevel :  Items(ItemsCount) = hTmp
    
        '1st item (starting point)
        Treeview Get Text hDlg, 100, hTmp To ItemsS(ItemsCount)
        ItemsP(ItemsCount) = "000000000000000"     'use "000" for each level (1000 items max per level)
        ItemsS(ItemsCount) = ItemsP(ItemsCount) + Str$(ItemsL(ItemsCount)) + " " + ItemsS(ItemsCount)
    
        'cycles through all items, put various info in arrays
        While Items(iPOS)
            iOrder = 0
            Treeview Get Child hDlg, 100, Items(iPOS) To hTmp
            If hTmp Then iLevel = ItemsL(iPOS) + 1
            While hTmp
                Incr iOrder :  Incr ItemsCount
                Items(ItemsCount) =  hTmp
                ItemsL(ItemsCount) = iLevel
                ItemsP(ItemsCount) = ItemsP(iPOS)
                Mid$(ItemsP(ItemsCount),(iLevel-1)*3+1,3) =  Format$(iOrder,"000")
                Treeview Get Text hDlg, 100, hTMP To ItemsS(ItemsCount)
                ItemsS(ItemsCount) = ItemsP(ItemsCount) + Str$(ItemsL(ItemsCount)) + " " + ItemsS(ItemsCount)
                Treeview Get Next hDlg, 100, hTmp To hTmp
            Wend
            Incr iPOS
        Wend
        'sort the ItemsS array (tag Items along with it)
        ReDim Preserve ItemsS(ItemsCount), Items(ItemsCount)
        Array Sort ItemsS(), TagArray Items()
    End Sub
    This example is set up to handle a 5-level Tree and 1000 children per item. Just extend the "00000..." string by groups of 3 zero's to support more levels.
    Last edited by Gary Beene; 18 Feb 2009, 09:44 AM.

  • #2
    Gary,
    While your code may be excellent I'll never know as I won't even look at a piece of code with more than a couple of globals. The use of globals makes it unusable as a library routine. It appears you have some coding talent but it needs a little more focus on reusable code in my opinion.
    This is NOT a rant on GLOBALS per se it's about code reuse!

    James

    Comment


    • #3
      I would also recommend posting source code samples in the source code forum. While you're free to post anyplace, it makes finding source code easier if its located in the forum most people think of as containing source code

      Software makes Hardware Happen

      Comment


      • #4
        Joe,
        Yes, you bring out an ongoing dilemma. On a couple of posts, I've had to think about where to post. I've put code in both places, depending on my intent.

        The forum descriptions say that the Source Code forum is for posting, no discussion allowed. I was interested in feedback, so here seemed more appropriate. Is there an "understood" policy within the folks here that code goes to the Source Code forum regardless?

        Mostly, I see folks post code asking "Why does it work". I would personally like to see code posted with discussion about why it works, what it's shortcomings are, why one approach is better than another - specific to PBWin9. That's more along the lines of the posts I made.

        And I'm assuming double-posting is inappropriate.

        Comment


        • #5
          James,

          And a rant it was!

          I understand, and share, your opinion on having code available in a reusable format. Having code available in a format that requires the least modification for future reuse is efficient, if nothing else. Better yet, no mods means no introduced mistakes! It's the best way to benefit from having code snippets available, as well as to maximize the ease of sharing code between peers.

          However, your no-exceptions philosophy is somewhat limiting. If someone gives you free peanut butter and bread, you ought to be willing to put them in a form you can eat more easily.

          Ditto for code. I'm willing to take (possibly) useful code and make minor modifications to it to suit my programming needs. If someone offers me free beer, I don't usually turn it down because it's not in a glass of my liking.

          (actually, I don't drink. the beer was just an analogy to get my point across)

          Comment


          • #6
            The source code forum is mainly for working code that people might find useful. Complete apps, small functions, whatever. Code posted within other forums are usually "why does this (not) work", "what am I missing", etc samples rather than code being submitted to the general public for use.

            Most of the time, people will create a thread in one of the forums like "Discussions about (code) posted in the source code forum" with a link to the actual code posting in the message body. This way, people can discuss it without "clogging" the source code forum with lots of discussion, and at the same time, the code can be easily searched on without having to search ever conceivable forum to find that "I know I saw something like this someplace"....

            There are no 'hard and fast' rules that will get you banished for breaking, but the more we stick to some kind of organization, the better it is for everyone.

            I'd also suggest Michael's recommendation of putting the compiler version and (if appropriate) Win32inc date at the top along with any other information that might help someone 5 years from now.
            Software makes Hardware Happen

            Comment


            • #7
              Ditto for code. I'm willing to take (possibly) useful code and make minor modifications to it to suit my programming needs. If someone offers me free beer, I don't usually turn it down because it's not in a glass of my liking.
              Couldn't agree with you more.

              IMO, posted code is mainly for example purposes. Unless specifically stated as "complete application, no modifications required or allowed" one should always treat 'free' code as a good (usually) example of how to do something. Taking anything verbatim and 'forcing' it to fit someplace is a recipe for disaster in my book.

              What's the old adage about looking a gift horse in the mouth?

              BTW, I don't drink adult beverages either, but I completely understood your analogy
              Software makes Hardware Happen

              Comment


              • #8
                Code:
                ' =====================================================================================
                ' actual recursing function; returns 0 = Enum Completed, 1 = Enum was terminated in callback
                ' This function enumerates the tree whose root is hStartItem. Includes hStartItem
                ' ***************************************************************************
                ' THIS FUNCTION SHOULD NOT BE CALLED BY THE USER, CALL TV_ENUMTREE or TV_ENUMTREE_SIBLINGS Instead
                ' ***************************************************************************
                FUNCTION Treeview_Enum_Recursing_Function (hTV AS LONG, hStartItem AS LONG, BYVAL CbAddress AS DWORD, _
                          BYVAL dwUserData AS LONG, BYVAL doSiblings AS LONG, BYVAL ResetStop AS LONG ) AS LONG
                
                    LOCAL hItem AS LONG, hChild AS LONG, hSibling AS LONG, tvi AS TV_ITEM
                    LOCAL DoSibs AS LONG
                    LOCAL szText AS ASCIIZ * %TV_ENUM_MAX_TEXT_LEN
                
                    LOCAL  Continue AS LONG
                    STATIC StopEnum AS LONG   ' yes, STATIC, so we can exit multiple levels of recursion
                
                    IF ResetStop THEN         ' reset stop is set on each "fresh" enumeration
                      StopEnum = %FALSE
                    END IF
                    IF StopEnum THEN    ' user forced a stop in callback (recursions are called with resetStop=false)
                       FUNCTION = 1
                       EXIT FUNCTION
                    END IF
                    ' get stuff into LOCAL vars to make sure each recursion gets own copy
                    hItem      = hStartItem
                    DoSibs     = DoSiblings  ' for first time, will be false, so will not do siblings; when
                                             ' called from restart, doSibs WILL be true!
                    DO WHILE hItem
                      ' get the tvi for this item and send it to the callback function
                      tvi.hItem       = hItem    ' we want this one
                      tvi.mask        = %TV_ENUM_MASK
                      tvi.cchTextMax  = SIZEOF(szText)
                      tvi.pszText     = VARPTR(szText)
                      TreeView_GetItem hTv, BYVAL VARPTR(tvi)
                      ' send tvi to the USER callback function
                      CALL DWORD cbAddress _
                        USING TV_Enum_User_callback  _
                           (dwUserData, tvi, htv) TO Continue
                          ' TRACE PRINT "Callback returns continue=" & STR$(Continue)
                           IF ISFALSE Continue THEN
                               StopEnum          = %TRUE     ' set the static stop flag which will be read
                                                             ' as function recurses out of itself.
                               EXIT DO
                           END IF
                      ' if any children of this node, call this function recursively.
                      hChild = TreeView_GetChild(hTV,hItem)
                      IF hChild THEN
                          ' The GetChild macro returns the first child of hItem in hTv
                          ' call ourself, but now the child is the starting item and we do siblings and do NOT reset the Stop flag
                           CALL Treeview_Enum_Recursing_Function (hTv, hChild, CbAddress, dwUserData, %TRUE, %FALSE)
                      END IF
                      IF StopEnum THEN
                          EXIT DO
                      END IF
                
                      ' and make hitem the next sibling at this level, if doing siblings
                      IF DoSibs THEN
                          hItem = TreeView_GetNextSibling (hTv, hItem)
                      ELSE
                          hItem = %NULL
                      END IF
                    LOOP
                    ' if we get here, enum completed without user action
                    FUNCTION = 0
                
                END FUNCTION
                
                ' ===============================================================================
                '                USER-CALLED TREE ENUMERATION FUNCTIONS
                ' Treeview_enumtree: Enumerate the nodes of the tree whose root is at hStartItem
                '                NOTE: does NOT do siblings of hStartItem!
                
                '================================================================================
                FUNCTION TreeView_EnumTree (hTV AS LONG, hStartItem AS LONG, BYVAL CbAddress AS DWORD, BYVAL dwUserData AS LONG) AS LONG
                  ' here we just start the recursion, FALSE, TRUE ==> NO siblings, YES reset stop flag
                   LOCAL I AS LONG
                   CALL TreeView_Enum_Recursing_Function _
                        (hTv, hStartItem, CbAddress, dwUserData, %TV_ENUM_SIBLINGS_NO, %TRUE) TO I
                   FUNCTION = I
                END FUNCTION
                MCM
                Michael Mattias
                Tal Systems Inc. (retired)
                Racine WI USA
                [email protected]
                http://www.talsystems.com

                Comment


                • #9
                  Here is an example without recursion or arrays:

                  Code:
                  Function TreeWalk(ByVal vhTreeMenu As Dword) As Long
                  ' Purpose:       example to traverse a treeview control without using recursion
                  ' Parameters:    vhTreeMenu - handle to treeview control
                  ' Example:       Call TreeWalk(GetDlgItem(hWnd, %CTL_TREEVIEW))
                      Local hItem As Dword                ' handle to current item
                      Local hPrev As Dword                ' handle to previous item
                      Local lngDepth As Long              ' count of current depth
                      Local lngUp As Long                 ' flag to determine if time to go up a level
                      Local phItem As Dword Ptr           ' pointer to array used to track treeview items
                      Local ptnmtv As NM_TREEVIEW Ptr     ' treeview notification message information
                      Local szText As Asciiz * %MAX_PATH  ' working value
                      Local ttviex As TVITEMEX            ' specifies or receives the attributes of a treeview item
                  
                      ' allocate memory for the array used to track treeview items (tip via Dominic Mitchell)
                      ' 256 * 4 allows for a depth of 256. Modify as needed. Test if depth approaches this if desired.
                      phItem = HeapAlloc(GetProcessHeap(), %HEAP_ZERO_MEMORY, 256 * 4)
                      If IsFalse(phItem) Then
                          ' could not allocate memory
                          GoTo TreeWalk_Exit
                      End If
                      ' get root item
                      hItem = SendMessage(vhTreeMenu, %TVM_GETNEXTITEM, %TVGN_ROOT, %NULL)
                      If hItem <> 0 Then
                          @phItem[0] = hItem
                          hPrev = hItem
                      Else
                          ' no root defined
                          GoTo TreeWalk_Exit
                      End If
                      While lngDepth >= 0
                          If lngUp Then
                              ' A: just came back up a level
                              lngUp = %FALSE
                              hItem = SendMessage(vhTreeMenu, %TVM_GETNEXTITEM, %TVGN_NEXT, hPrev)
                          Else
                              ' B: test if item has a child. if not, then test if there is a sibling
                              hItem = SendMessage(vhTreeMenu, %TVM_GETNEXTITEM, %TVGN_CHILD, hPrev)
                              If hItem <> 0 Then
                                  ' C: go down 1 level
                                  Incr lngDepth
                              Else
                                  ' D: check for siblings on this level
                                  hItem = SendMessage(vhTreeMenu, %TVM_GETNEXTITEM, %TVGN_NEXT, hPrev)
                              End If
                          End If
                          If hItem <> 0 Then
                              ' E: found a sibling, either on same level [D], or after coming back up a level [A]
                              ' do something. i.e. get the text of the current item:
                              ttviex.hItem = hItem
                              ttviex.mask = %TVIF_TEXT Or %TVIF_PARAM
                              ttviex.cchTextMax = SizeOf(szText)
                              ttviex.pszText = VarPtr(szText)
                              SendMessage vhTreeMenu, %TVM_GETITEM, 0, ByVal VarPtr(ttviex)
                              ' continue
                              @phItem[lngDepth] = hItem
                              hPrev = hItem
                          Else
                              ' no more siblings at this level
                              Decr lngDepth
                              If lngDepth >= 0 Then
                                  hPrev = @phItem[lngDepth]
                                  lngUp = %TRUE
                              Else
                                  ' back at top level, so exit
                                  Exit Loop
                              End If
                          End If
                      Wend
                  TreeWalk_Exit:
                      ' release memory
                      HeapFree GetProcessHeap(), 0, phItem
                  End Function
                  Last edited by Christopher Carroll; 19 Feb 2009, 01:33 AM. Reason: Tidied up indentation

                  Comment


                  • #10
                    Don't forget, there are multiple "correct" ways to walk a tree...

                    Could be...
                    Code:
                     1   
                        4 
                        5
                            10 
                            11
                            12 
                     2 
                        6 
                        7
                            13
                            14 
                            15
                     3
                        8
                        9
                    Then again, you might want ..
                    Code:
                    1
                      2
                         3
                         4 
                         5
                      6 
                         7
                         8 
                         9 
                     10 
                         11
                            12
                            13
                    MCM
                    Michael Mattias
                    Tal Systems Inc. (retired)
                    Racine WI USA
                    [email protected]
                    http://www.talsystems.com

                    Comment


                    • #11
                      Yep, good point. Luckily for me, the code I posted gives both answers.

                      The data array, unsorted, matches your first example. Sorted, it matches your second example.

                      Cool beans!

                      Comment


                      • #12
                        Christopher,

                        Thanks for the code.

                        I inserted a highlight/sleep line and it walked through perfectly.

                        Code:
                                    ttviex.hItem = hItem
                                      Treeview Select hDlg, 100, hitem
                                      Sleep 400
                                    ttviex.mask = %TVIF_TEXT Or %TVIF_PARA
                        Hating to re-invent the wheel, can I ask if you also have a version of this code that works with listing subdirectories? If not, I'll give the conversion a try.

                        A "problem" with my code is that in the 2nd example Mattias gave, my code requires that the entire structure must be walked before being able to use the results. With yours, the walk-through follows example 2, gets immediate results, and can be stopped at any point.

                        For TreeView controls, it's not an issue because reading a Tree takes almost no time at all (tree structures aren't usually that large). But with subfolder counts of >10K, not having to finish reading the entire structure can be an advantage if you're searching for that is found high in the structure.

                        In an earlier post about listing subdirectories, Edwin Knoppert noted that pidls (which I know nothing about - yet), are the fastest way to go. If you have used you code for subdirectories, how did it fare on speed?

                        Comment


                        • #13
                          Gary

                          I have not had occasion to list out files and directories. However, this code from Stuart Sanders is quite useful:
                          Treeview/Listview Select Files and Folders

                          Listing directories is reasonably fast using his code, but the loading of a large number of files within a directory is a bit slow.

                          The display (of the files in the treeview) is separate from the parsing of said files and directories. Depending on what is required, I would probably read the list of the directories (in chunks?) into a structure in memory, then dump these as a group into the treeview. And then do the same for the files in a particular directory only when that directory is selected in the treeview. The files listed could be cached, or even pre-read using threads (i.e. if a directory is selected, read the files in that directory and pre-read the files in the next n sub-directories.

                          For an example of using pidls, see this posting by Edwin Knoppert:
                          Enum a folder the com way

                          The code I posted above is suitable to search for text (i.e. a file name) within the treeview once the data are loaded to it. Just do a string comparison in section E. If a match is made, the code can be exited at that stage as you have noted.

                          Christopher

                          Comment


                          • #14
                            example Mattias gave, my code requires that the entire structure must be walked before being able to use the results. With yours, the walk-through follows example 2, gets immediate results, and can be stopped at any point.
                            So you call the enumeration twice, either to two diffferent callback functions or using a different "DwUserData" value known to your application.

                            BTW, if you return false from your callback function, the recursive enumeration stops and unrolls everything.

                            The recursive version is also not constrained to be "hard-coded" to support a finite 'depth limit.'


                            MCM
                            Michael Mattias
                            Tal Systems Inc. (retired)
                            Racine WI USA
                            [email protected]
                            http://www.talsystems.com

                            Comment

                            Working...
                            X