Feature

When I took a class on data structures with C++ at Brooklyn College, one of the topics emphasized was recursion. At first it didn't make much sense, and I wondered why we even bothered when other techniques were more understandable.

Recursion is an extremely abstract concept, and most people have a hard time visualizing the notion, let alone writing the recursive functions. The Towers of Hanoi and the Fibonacci sequence are the most common examples used to explain recursion, and their connection to the work environment isn't readily apparent. Fortunately, I grasped the theory - and even ended up with an A- in the course! Today I realize that Data Structures is probably one of the most beneficial classes I've ever taken. It's not often - if ever - that you'll encounter a problem that can only be solved recursively, but as you'll see, recursion is a nifty tool.

Nature of the Problem
Recently I began working for the City of New York's Department of Youth and Community Development. This agency has developed a fully integrated contract management system that takes wide advantage of treeviews in its information display screens. My curiosity was sparked when one of the first assignments I received was to stop the treeview from collapsing.

You see, various functions can be invoked at each level of indentation by right-clicking on records of a given "branch." For example, if a user wants to insert a record through the treeview, he or she selects Add a record from the right-click menu. This opens a new window and the user is presented with a blank input screen. Once the record is saved, the user closes the update window and the focus is returned to the window with the treeview. To show the new data, the treeview has to be refreshed and the new data retrieved. For the user, the display collapses and hides all levels below the parent item of the one created. If the user had to insert another record at the lower levels, or just view the contents of lower items, he or she had to reopen the tree to do so. Users really hated this behavior, and after experiencing it myself I totally understood why. They wanted the tree display to stay the same no matter what they did, with the newly inserted records shown in the tree immediately after their creation. Clearly, something had to be done.

In the existing code the data refresh was accomplished by calling the pfc_refreshitem event of the inv_levelsource, which is an instance of the n_cst_tvsrv_levelsource service. This event takes as an argument the handle of the treeview item that was modified and retrieves the data from the DataStore that's used as the source to feed that level of the treeview. The parent item and all child items are then populated with a fresh set of records. If the parent item or any of the child items are expanded prior to the refresh, they're all collapsed after the refresh is applied.

Solution Planning
Since the application was already in production, instead of rewriting existing code for numerous treeview controls, I decided to write a service that programmers could simply plug into existing code. As the service doesn't need visual properties, it will be inherited from the custom nonvisual object. The purpose of the service is to remember the tree layout and then restore it, so I named it n_cst_tv_remember. I also wanted this service to be applicable to any treeview in the PFC-based application.

This solved a specific problem, but I set yet another goal for the service: reusability. We as developers should always aim for efficiency and productivity. The best way to achieve this is by having reusable objects.

To make the service remember the treeview layout, I decided to record only expanded items that are below the item being modified. An example is the treeview in Figure 1; items to be recorded are indicated by an arrow. I declared the instance variable itvi_items[], an array to store the expanded treeview items. Each treeview item has descriptive properties (itemhandle, data, label, etc.) and n_cst_tv_remember will use these properties to restore the treeview to its pre-refresh state. Initially I leaned toward recording just the handles of treeview items, but as you'll see, this would affect the ability of n_cst_tv_remember to restore the tree layout.

At the heart of the service are three functions that perform all the magic: of_Initialize (see Listing 1), of_LoadArray (see Listing 2) and of_Restore (see Listing 3), plus a few instance variables in addition to itvi_items[]. of_Initalize and of_Restore are both declared as public functions, while of_LoadArray is a private function and a recursive function and the real workhorse of the n_cst_tv_remember service. All of the instance variables are declared as private. I'm emphasizing scope (access) here because as a PowerBuilder developer you want to follow the rules of object-oriented programming

How to Use n_cst_tv_remember
To explain how to use n_cst_tv_remember, I'll walk you through the modifications I made to treeview controls in our application. Window w_activity_tree (see Figure 1) contains a treeview control that displays various contracted activities. When a user wants to modify an activity, he or she selects it in the treeview and, by right-clicking on it, invokes a popup menu. The menu lists options to Create, Modify or Sort records. Let's say the user selects modify. By doing so, ue_modify event of w_activity_tree window is fired. The developer placed the following code in ue_modify:

IF not isnull(ii_activity_id) THEN
lstruct_gen_tree_activity.activity_id = &
ii_activity_id
openwithparm(w_activity_link_modify, &
lstruct_gen_tree_activity)
li_i = 0
this.event ue_refreshitem()
ELSE
messagebox("Note" , "Select the Activity" &
+" you want to modify")
RETURN
END IF

ue_modify will open response window w_activity_link_modify (see Figure 2) and pass structure lstruct_gen_tree_activity to it. Window w_activity_link_modify is where the user modifies the data. When the user finishes with modifications and closes w_activity_link_modify, ue_refreshitem event of w_activity_tree is fired. This event in fact refreshes the treeview, and that's where I placed my n_cst_tv_remember service. This is code from ue_refresh that I've modified to use remember service:

long ll_itemhandle,ll_Row
n_ds lds_DataStore
n_cst_tv_remember lnvo_remember
long ll_rtn

ll_itemhandle = tv_1.FindItem(CurrentTreeItem!, 0)
//Initalize remember service
lnvo_ remember = CREATE n_cst_tv_remember
lnvo_ remember.of_Initalize ( tv_1, ll_itemhandle)

tv_1.inv_levelsource.event &
pfc_refreshitem(ll_itemhandle)
//now that we refreshed restore to old view
IF IsValid(lnvo_ remember) THEN
lnvo_ remember.of_restore()
DESTROY lnvo_ remember
END IF

Let's walk through this code. First I obtain the handle of the item being modified (see Figure 1). This is the current item, which I'll refer to as the parent item. I then create an instance of n_cst_tv_remember, using CREATE syntax. To register the treeview with the instance of n_cst_tv_remember, I call of_Initalize(Ref TreeView, Long ItemHandle). If you look at Listing 1, you'll see that of_Initalize takes two arguments: TreeView by reference and long by value (handle of parent item). After recording instance variables, of_Initalize will make a call to of_LoadArray(Long itemHandle). of_LoadArray is a recursive function that will search the parent item branch for all expanded treeview items and store them in the itvi_items[];array of treeview items. (More about of_LoadArray and recursion is coming up.) After I initialize the remember service, I can call the pfc_refreshitem event. To call this event, inv_levelsource has to be turned on. This is done in the constructor event of tv_1 by coding of_SetLevelSource(TRUE). All that's left is to call up of_Restore and destroy the remember service. (Later I'll show you a small matter that of_Restore has to take care of before restoring the treeview layout.)

You might ask why I use the IsValid() when I know that the instance of n_cst_tv_remember exists. I find it useful to check every nonvisual object's existence before calling its events/functions, especially with PB7 and its garbage collection facility. This practice is very useful if you're using PB6.5 and will migrate to 7.0.

of_LoadArray and Recursion
I mentioned that of_LoadArray is a recursive function and the workhorse for the n_cst_tv_remember service. In my experience I've found treeview control especially well suited for recursive solutions. Recursion is the concept of well-defined self-reference. In simple English this means that the function calls itself one or more times. The most important consideration for recursive function is that there has to be a clear end point or stop state where the function stops calling itself. If there is no end point, we'll end up with an infinite loop and subsequently a GPF. Recursion is used mainly to replace the use of nested loops. As with a loop, you must have a clear stop point in your recursive call. Other considerations for recursion are space (size of the stack) and time (number of recursive calls).

Mathematics functions are often defined recursively. The classic example is the factorial function:

factorial(0) = 1
factorial(n) = n * factorial(n-1) [for every n>0]

Mathematics explains recursive definition in two parts. There's a base case that tells us directly what the answer is (factorial(0) = 1), and there's a recursive case that defines the answer in terms of the answer to some other related problem (factorial(n) = n * factorial(n-1). The recursive case doesn't lead directly to the answer, but explains how to construct the answer for factorial(n) on the basis of the answer to the related problem, factorial(n-1). For you as a developer it's important to do recursive planning before writing recursive function. That is, you should first come up with some sort of formal definition of the recursive process. This involves two parts:

• Define the stopping condition (base case).
• Try to keep things going (just like that little Energizer bunny).

Since I, like many others, believe what I see, not what I hear, consider this PowerBuilder example.

Problem to solve: write a function to sum the elements of integer array.

of_SumIntegers (ai_array, ai_itteration) Returns Integer
Integer li_count
li_count = UpperBound(ai_array)
IF (ai_itteration = li_count) THEN
RETURN (ai_array[ai_itteration]) //END POINT
ELSE
//lets make recursive call keep going
RETURN ai_array[ai_itteration] + of_SumIntegers(ai_array,(ai_itteration + 1))
END IF

If you take a look at of_LoadArray in Listing 2 and the problem above, you'll see that the end point is clearly defined. In of_LoadArray I used as the end point the fact that treeview can have a certain number of levels. I don't know how many, but I know it isn't excessive. I also know there has to be an item that doesn't have any children. With this in mind I start from the parent item to check whether the item has children. If it doesn't, I reach my end point. If it does, I go to the first child and check whether it's expanded. If it is, I call of_LoadArray again. At this point the child becomes a parent, and I search for its child items. What I'm doing basically is drilling down through the tree, searching for expanded items, until I hit the last level of the treeview. In this process of drilling I record each item that's expanded and store it in my array of expanded items. What of_LoadArray does is represented in Figure 3.

Restoring TreeView Considerations
After I solved my problem of recording the tree layout prior to refreshing, I thought the restoration would be simple and straightforward. After all, I have treeview items stored in my array, and by accessing each item's handle property, I can simply go ahead and expand each item. Or so I thought.

What happens is that after refreshing the item that was modified (parent item), all child items are refreshed as well. This means that properties of the items are being updated. The handles of the child items aren't necessarily the same before the refresh and after it. I'm not saying this is the case for every item, because I've also seen items that were assigned the same handle before and after the refresh. For n_cst_tv_remember to work properly, this has to be taken care of.

From itvi_items[], array of treeview items, I can obtain the data and label properties for each tr eeview item that was expanded before the refresh. If I go through the refreshed tree, I can compare items from itvi_items[] against the items in the treeview. Therefore I can obtain the new handle. If you look at of_Initalize, you'll notice that I passed tv_1 by reference and stored it in instance variable itv_treeview. Basically, itv_treeview is pointing to tv_1, which was refreshed before calling of_Restore().

Now you're thinking: "Didn't the parent item handle change too?" After numerous tryouts and tests, what I determined was that the parent item handle never changes after a refresh. If you find this isn't true, please let me know as I spent a lot of time ensuring that it is. If you find I'm wrong, you can change of_Initalize not to record parent item in itvi_items[]. In your code, after you refresh the tree, you can obtain the handle of parent item: ll_itemhandle = tv_1.FindItem(CurrentTreeItem!, 0). Once you obtain the handle, you can expand item tv_1.ExpandItem(ll_itemhandle). You then need to modify of_Restore not to expand the parent item at once but to loop through the itvi_items[] and expand the items found.

In Listing 3 for of_Restore() you can see that I expand the parent item at once. If you don't like this, you can modify of_Restore to suit your needs. Now that I took care of the parent, I know that the child items still have the same label and data property. Why? Because the item being modified is always designated as the parent item, and I know only one item can be modified between calls. I also know that child items still have the same labels and data even though these properties were also refreshed. What changes for the child items are their handles. Knowing this, I go through itvi_items[], grab the label of the item and put it in la_itemsearch. I go into itv_treeview and look for a match for la_itemsearch. I'm searching only the branch below the parent item in order to avoid finding the same label at a different level of the treeview and thereby confusing the items. If I find a match, I get the handle of that item, expand it and proceed to the next one.

Closing Thoughts
Recursion is an interesting concept, and as you've seen, worth exploring. If you try to rewrite of_LoadArray function using loops, you'll be pulling your hair out. As a moral to the story, let me say this: recursion provides a concise and elegant algorithm with no explicit loop controls. On the other hand, there are disadvantages: the stack is finite, and operations on it are costly. Though recursion is often not the most time- or memory-efficient algorithm at runtime, recursive functions can be considerably easier to code.

Add Your Feedback

In order to post a comment you need to be registered and logged in.

Register | Log in

Please wait while we process your request...