A Native TreeView (Part V)

Version: 1.01.05 - Last Update: Tuesday the 12th, April 2011 - 11:25:00

---

FoxPro Rocks! This is all about how to create complex controls using native VFP only!

Intro

After all, the TreeShow must go on now…

Last year I decided to publish some VFP demo application without source code you still can find  here.  The only reason for not supplying you with the VFP source code was, I dropped those fully functional sources somewhere (on an old memory stick) and didn’t remember exactly where I dropped that one… As I started working on a new (improved!) version of my native VFP-TreeView, I only was able to recover the compiled demo app which is using an outdated driver table structure and many more odd things. Well, in between I decided not to create a PRO-version (available only for a fee) but publish my final release under a Creative Commons License. I hope you will enjoy it!

The long and winding road…

During the last years I worked on some more or less challenging projects. One of those was (and still is) my implementation of the (one and only?) Native VFP-TreeView. I’m sorry but I have to tell you (again) that there is no “final thing” at the end of this post waiting for you – nope, still no final download is available! Instead, we have to talk about some features and (interesting?) aspects of my final implementation, first. Believe me, I’m going to show you some really cool stuff in the next chapters. I am sure you will benefit from some tips!

Back to school!

After I went back to the drawing board I started thinking about how to approach the pending performance optimization issues. As I told you, those days the number one reason to rethink my first approach was the lack of speed when working with large datasets; the bigger the record count of the driving cursor, the slower most of the collapse/expand actions became. Another bottleneck was the complexity of the tree item class. The more features I implemented there, the more time was wasted during refresh/repaint for jumping through endless IF…ELSE…ENDIF and other DO CASE constructs just to find out which part of the object had to be made visible or hidden or re-colored and so on. Finally, I got stuck with a wonderful implementation of a cool looking tree item class (with dozens of features) that ate up too much refresh-cycle time.
More than ten visible TreeView items rendered my good looking tree useless. At that point in time I knew two things: 1st., It was possible to build a native VFP TreeView and 2nd.: it was abundantly clear that some extraordinary speed optimizations had to be applied to the key parts of the design.

Let’s examine the “roots”!

My initial idea to use a VFP GRID class as the basic container vehicle, I didn’t want to discard. Thus, I couldn’t discard using a driving cursor, either. The driving table/cursor was the logical starting point of my speed optimization efforts, then. If you read  Part IV-b of this thread, you should have seen my old driving table structure which was pretty complex. The tree cursor got more and more columns over times, but the first 5 columns of my driving table’s structure listing in Part IV-b dealt with the hierarchical aspects of tree display.
Well, we all know how to setup and store parent-child relationships of hierarchical related data in a dbf table, don’t we? I’m sure, you recognize the fields of my driving cursor immediately: pNodeID and pParentID hold the primary and foreign key values implementing that parent-child aspect.

  
The entries shown in the browse window above correspond to the screenshot of my demo TreeView in Part VI-b below.

As long as we are using a Microsoft ActiveX TreeView control storing the relationship within two columns (one holding the primary key and the other holding the grouping/parental foreign key) is sufficient. There are several ways to reload the parent-child information of such a cursor back into an ActiveX TreeView: you may want to use a couple of SQL-Select statements within a recursive SCAN loop to select all sets of child entries to fill up your TreeView. Again, there are other ways to refill an OLE-TreeView, it is up to you to decide what approach fits best within your environment!
Now(!) Try to create a native VFP index that can be employed with SET ORDER TO to display the node records (shown above in the browse window screenshot) in hierarchical sorted sequence like in the screenshot below (where I SET OREDER TO ‘piorder’)!

This should be the resulting browse window after your “very special” - index is active

Any ideas? I’m waiting!
I’m waiting!
I’m still waiting!
Again, I’m still waiting!
Right, you are! Without having a single sort order column containing sorting expressions in the correct hierarchical sequence there is no easy trick to solve our dilemma! The following source code fragment shows my old implementation to rebuild the Piorder column values of my driver table:

*\\ Rebuild_SortOrder() gets called from .RebuildMetaData() or recursively(!)
*\\
LPARAMETERS tcParentID As String, tiOrderNo As Integer @
   *\\      tcParentID :== id of parent node for which all children are processed now
   *\\      tiOrderNo :== next Piorder value to be set (passed in by reference!)
IF this.lReadOnlyMetadata
   RETURN
ENDIF
*//
*[BS]: NOTE>> No parameter checking any more coz we'll have done that
*\\ already in interface method "this.RebuildMetaData()"!
*\\
LOCAL lnRecNo AS Integer ,;
      lnOldRecNo AS Integer ,;
      liIndent AS Integer
*//
*\\ remember from where we started
lnOldRecNo = RECNO()
*//
*\\ Set OrderNo for current record
REPLACE PiOrder WITH m.tiOrderNo
*//
IF THIS.lSort && sub-sort children on PCCAPTION string
   SET ORDER TO PCCAPTION
ENDIF
*\\ process all children on the same level (siblings)
SCAN ALL FOR Pparentid == m.tcParentID
   *\\ increment sort order value
   tiOrderNo = m.tiOrderNo + 1
   REPLACE Piorder WITH m.tiOrderNo
   *//
   *\\ remember record number
   lnRecNo = RECNO()
   IF Pichildcnt > 0
      *\\ drill down recursively
      THIS.Rebuild_SortOrder(Pnodeid, @m.tiOrderNo)
      *//
   ENDIF
   GOTO RECORD (m.lnRecNo)
   *//
ENDSCAN
IF THIS.lSort
   SET ORDER TO
ENDIF
*//
GOTO RECORD (m.lnOldRecNo)
RETURN

Those days I did not change the cursor structure, but tried to solve the hierarchical-sorting problem using a more or less pragmatic approach. Sure you already can see the weakness of my solution:
Adding new items to the TreeView (into the cursor) results in a, at least partial, rewrite of the Piorder column. The closer to the root element an item is inserted, the more Piorder value REPLACEments have to be done. Typical “CRUD” ( Create, Replace, Update, Delete) operations can get really sluggish when applied to large TreeViews (with a lot of nodes > 10.000). On the other hand, my Rebuild_SortOrder() method is the perfect place to implement any additional sub-sorting (optional, I’m sorting all sibling child-nodes based on their caption).

 

All for One, One for All

If we, at least, want to dynamically retrieved each node caption from our driving cursor, then our three musketeers (Pnodeid, Pparentid and Piorder) finally meet D’Artagnan (Pccaption). Thus, my first approach started with a “four column minimum” driving table. Many more supporting columns were added to (1)speed up the TreeView refresh. Other column were added to (2)enhance flexibility at runtime. Columns such as Piindent and Pichildcnt belong to the first group; if we always instantly know how many levels deep a given node has to be “indented” before it can be displayed, this can be a big timesaver compared to always re-compute the indentation level for all tree nodes. Same is true for knowing about the number of children a tree node has. If we know the node’s child count during refresh in advance, this speeds up things a lot, especially, if we know that a given node doesn’t have any children (Pichildcnt == 0).
In contrast to  Microsoft’s ActiveX TreeView control we cannot store additional  information inside each node object itself, because each VFP node object is a single class instance that is shared inside a grid column between all rows (roughly speaking:-). To get closer, let’s eye the checkbox implementation. If we have our TreeView displaying checkboxes before each of it’s nodes, we can query the checked-state of each node object. This true/false value is stored in a property of each node object of an ActiveX-TreeView directly. An ActiveX-TreeView with, let’s say, 1000 nodes has 1000 node objects each capable of storing the checked/unchecked information on its own.
In contrast, our native VFP TreeView has only one real node class instance. The other 1000 nodes of our TreeView grid are virtual class instances only. They only get painted during refresh sharing the one and only real node object as some kind of punching tool for that. Since all node objects are more or less virtual, they must hold their “property” values stored in the fields of the corresponding (1000) rows of the driving cursor to make them persistent. That’s exactly what a VFP grid originally was designed for: display data stored in a cursor (an not property values of object collections :-)
The screenshot below shows some of the additional columns that were added later in the game. BTW: the Pnmark column just stores the checkbox values just discussed. As my native VFP TreeView can have OptionGroups (the famous radio button groups) the Pnmark column accepts values greater then 2 (to be able to hold radio button groups of any member-count).


Finally I’m going to explain another column “Pllastitem” you can see in the above screenshot. This flag (true/false) is used to simplify the implementation of the tree-lines algorithm a little bit. Below, you see a part of the screenshot my TreeView-Editor TreeView. The so called “Last items” are marked with red circles. The grid rows containing those definitions (see above) show the flag value 1 in their Pllastitem field.

A “last item“ is the last node on it’s indentation level. Either, the following node (the one with Piorder+1) is a child node (then that node’s Piindent value is higher), or it is a sibling of the “last item’s node” parent node (then that node’s Piindent value is lower). There are two other extremes: either there is no next node, then our “last item” node is the last node of the whole TreeView (with the highest Piorder value), or it is the first node in the TreeView, a so called root node (with the lowest Piorder value). If the node in question is a real “last item” node, then the vertical tree line of the indentation level ends on that grid row and must only be drawn to the mid of the row. Otherwise, for all other items, the grid line on the level has to be continued down to the next row. Watch the red circled spots to get the clue. Well, how would you implement fast refreshing vertical and horizontal tree lines up to over 30 levels of indentation? Either you drop all these lines like Vista explorer does (see below :-)

… or you have to store the needed information (is the current node the last on it’s own/current indentation level) in a separate column of your driving table. Next you have to figure out when and how to update that information. I leave it to you to check my implementation shown below.

*\\ Rebuild_LastNodeFlag()
*\\
*\\ Note: any ORDER that was SET gets released on exit!
*\\
IF this.lReadOnlyMetadata
   RETURN
ENDIF
*//
LOCAL lcParent AS String ,;
      liIndent As Integer ,;
      lnRecNo  AS Integer

*\\ Important: BLANK ALL PlLastItem metadata column entries first!
*\\          BITTEST(pbit_state,4) := exclude root node(s)
BLANK FIELDS Pllastitem ALL FOR NOT BITTEST(pbit_state,4)
*//
*\\ This gets a little bit tricky now:


SET ORDER TO PIORDER DESCENDING && TreeView definition now upside-down
GO TOP && we are on the last TreeView node now *\\ Scan from bottom to top!
*\\ ISBLANK() serves as a "virtual" flag field value: “not visited”
SCAN ALL FOR ISBLANK(Pllastitem)
   lnRecNo = RECNO()
   lcParent = Pparentid
   liIndent = Piindent
   *\\ Two simple rules apply here:    
   *\\ 1st: The last node (the one with the highest Piorder value) of each level of indentation must 
   *\\      be flagged TRUE in Pllastitem field!
   *\\ 2nd: Each trailing sibling node (all nodes with the same Piindent value and the same Pparentid 
   *\\      value that have a Piorder value less than the current node) can NOT be the "last-node"
   *\\ Thus:
   *\\    Running from bottom to top traversing our metadata cursor processing only BLANKed fields
   *\\    the first node record we'll find has to be the "last-node" of his 
   *\\    indentation level/(child)group.
   REPLACE Pllastitem WITH .T.
   *\\ Now skip from the bottom of the TreeView cursor "up" one line due to DESCENDING ordering
   SKIP
   *\\ from there walk up the TreeView definition and replace all sibling nodes’ Pllastitem 
   *\\ field with .F. (coz they all belong to the same group of siblings of our just flagged 
   *\\ “last node” in the code above). Writing .T. or .F. to the cursor clears the BLANK state.
   *\\ This will exclude the group of sibling nodes just processed from the next SCAN loop
   REPLACE REST Pllastitem WITH .F. FOR Pparentid == m.lcParent AND Piindent = m.liIndent
   *\\ finally reposition record pointer (set back to initial position >> last TreeView node)
   GOTO RECORD (m.lnRecNo)
   *// That's it. The SCAN now again goes "up" the treedef cursor until it finds another 
   *// BLANK record (group). Otherwise we're done.
ENDSCAN
*\\
SET ORDER TO

Wherever there is light, there are shadows

After all those days and nights I’ve tried to create an (almost) perfect native VFP TreeView, I can say, that both types (the ActiveX AND the native VFP one) have their pros & cons! I don’t want to repeat all OLE-control related facts I already talked about in the past in detail. Today I want to concentrate on the downsides a VFP Grid-based solution has. To make a long story short:
Displaying & manipulating hierarchical ordered records (based on a one-to-many parent-child relationship) with good performance using a VFP GRID definitely is no straight forward task! Below you see a screenshot of VFP’s document view window with my so called ‘DynaGridController’ class opened in VFP’s class designer. The dynaGridController is the workhorse class “behind the scenes“ that implements (and encapsulate) all basic TreeView engine behavior.

A lot of functionality only is necessary to collapse/expand tree nodes, to indent items correctly, to navigate the TreeView using keystrokes and other stuff. I am sure, the implementation of most of all these ‘odd things’ was much easier for Microsoft while creating their ActiveX version!

 

What comes next

Next time I will present you my own “hierarchical indexing” technique. You can utilize a slightly varied version of it when working with SQL Server 2008. Yep, they got it there, too! But you can only see there how to use it. I will show you how to implement it! The tricky and (copyright) protected part is, that you do not have to use multiple fields to create a TreeView like hierarchical sequence!  Be prepared to learn something new ;-)

<To be continued…>

---