A Tree in One File

Posted September 1 1997

Printer-friendly version

I don't know if you have ever felt the need for a file organized as a tree? My wish for one rests on a long-standing desire to find a general solution to the problem of representing a chart of accounts. By 'general' I mean scaleable - simple, shallow structures for small organizations and complex, deep structures for larger ones.

As users of Clarion for Windows, you will be familiar with the Relational Tree template. In this template, each level in the tree is a separate file. The complete tree is defined by a chain of many-to-one relations, which begin with the file at the top of the tree and work down to the bottom. This method has many uses, but because each level is a file, it has a determined number of levels.

A chart of accounts, however, can have any number of levels. It can be shallow in some parts and deep in others. What follows are some ideas for implementing such a tree using a conventional TopSpeed file (such as the *.tps file). Before setting out a possible solution, let's consider some requirements. What follows is my wish list, in no particular order of priority.

Requirements

Browsing the file using its special tree structure to be as simple for the user as any other kind of browse.

1. No practical limit to the number of levels available.
2. Additional, conventional keys on the file are allowed for browsing it by account name, for instance, and for accessing it randomly by name.
3. When browsing by tree, the user is able to collapse and expand levels as in a Relational Tree.
4. The entries at all levels in a tree are dynamic; that is, the user is able to move entries up and down within a given level by pressing an Up or Down button.
5. The levels themselves are dynamic; that is, the user is allowed to promote and demote levels simply by highlighting an entry and pressing a button. A promoted set of records moves up a level, a demoted set moves down one.
6. All of the keys used to order the tree must be conventional keys. One of them must be able to be used randomly to directly locate any record in the file as well as being used for the special purpose of arranging it as a tree. User re-ordering of entries using up/down buttons or promotion/demotion buttons is to have no effect on this key.
7. Coding the tree structure is to require no more than the writing of a purpose-built set of routines within a conventional browse. The main difference between these routines and the conventional ones is that they have a different way of finding the next and previous records.

What follows is not a description of a working solution, it is a sketch of a possible one. I offer it for discussion and further refinement. Perhaps there are undiscovered (by me at any rate) flaws in the suggested solution that make it unworkable. If you are reading this article in Clarion Online then it has already passed the Moseley filter and you may feel it worthwhile to ponder whether it is indeed workable.

Note - While I have examined this article and feel that the concept and idea is technically feasible, I don't filter articles based on my own judgement of the feasability of the ideas. That said, I did review David's text and was prepared to write a template that compliments this design. Time and resource constraints made this impossible. - Tom Moseley, Publisher

A Possible Solution

Five special fields are required in the records in a file containing a tree:

• Level LONG
• Entry LONG
• Sequence REAL
• PrevLevel LONG
• Collapsed BYTE

Three special keys are constructed, each using two of the above fields:

• Key_LevelEntry - Level and Entry (both ascending)
• Key_LevelSeqAsc - Level and Sequence (both ascending)
• Key_LevelSeqDesc - Level and Sequence (both descending)

The Key_LevelSeq keys are used to construct one part of the order in which a tree browse is presented. Note the word 'construct'. A tree browse is not presented in the simple order which this key would give to a conventional browse. The key orders records within one level only. The minor field in this key is the one that changes its value in response to the user pressing the Up and Down buttons mentioned above.

The Entry field is used to make links between tree levels. When the last record in a level set has been read using Key_LevelSeqAsc then this field is used to determine where the first record in the next level set is to be found. It is never used to decide the presented order of a browse.

A tree file has a root record with the following values:

• Level zero
• Entry the Level number of the highest level in the tree
• Sequence the Level number of the highest level in the tree
• PrevLevel zero
• Collapsed zero

The root record (found by a SET/NEXT) provides the starting values for a further SET instruction that will get us ready to read the highest level in the file, using Key_LevelSeqAsc. Once this first record in the file has been read, its Entry field permits a SET/NEXT probe (using Key_LevelSeqAsc) to see if it has any child records. If so, the first of these records is the second record in the file to appear in the browse.

A probe for a grandchild record is then done, and, if it is present, it becomes the third record to be displayed. If there are no more grandchildren then the second child record (as per Key_LevelSeqAsc) is the fourth record.

If a record at any level is marked as Collapsed, then this inhibits the probe for its child records.

The diagram in Figure 1 follows the above example exactly. The five values in each box show the values of the five special fields.

Using the Tree Fields

Root record

The Root values allow a SET/NEXT probe for the first record at the highest level in the tree. This record, in turn, allows a probe for a grandchild record, whose Level field content is given by the Entry field in the level above. When there are no more grand- children, the next record in the child sequence is read.

The above process is recursive - the same simple logic is used repetitively to proceed down the tree, no matter what level that logic is dealing with.

The Five Fields - their usage explained

The value in an Entry field never changes during the lifetime of a record. The Entry field is unique. Other files can hold its value and always recover a given record at random from a tree file. Subsequent movement forwards or backwards in the tree file can in principle begin from any such random beginning point.

In all but one instance, the values in Level and PrevLevel are also unchanging. That instance is when a level promotion or demotion takes place.

The PrevLevel field allows the writing of a special-purpose PreviousRecord routine. With it, the routine can find its way backwards, all the way to the first record in the tree. In effect, the file is a doubly-linked list, with the Entry field serving the purpose of the forward link whilst PrevLevel provides the backwards link.

When a tree file is first loaded with data the Level and Entry fields are allocated in a simple sequence starting at zero (0) for the root record and working upwards one at a time. So it makes sense that, if some part of the file has a preferred order (say alphabetic by name), then it should be loaded in that order in the first instance. On the first load, all Sequence fields are set to the value of their respective Entry fields.

The Sequence field is REAL to allow arithmetic on the field when the Up or Down button is pressed. To move a record above its neighbor, first add together its Sequence field and that of its neighbor's neighbor. Divide the result by two and write this back into the record's Sequence field. The special cases that arise at the top and bottom of a level are easily dealt with. The important point is that the above simple method works regardless of the level being re-ordered by changes to the Sequence field.

The Collapsed field is a TRUE/FALSE indicator that all the children under a given record have been collapsed and are not to be visible in a browse.

I should note that this article does not consider the possibility of range and filter limits. Filtering is fraught with difficulty since filtered records might, by their absence, break the link between records. A range limit that allowed only one branch of a tree to be shown is, however, a possibility.

Climbing back up the Tree

This example shows how going backwards up a tree uses the Key_LevelSeqDesc key.

Root record
  A level record*
    B level record
      C level record
      C level record
      C level record
    B level record
      C level record
      C level record**
  A level record
    B level record

Let us suppose that we are positioned on the second A level record and we execute the PreviousRecord routine. If we are going backwards in a fully expanded tree, we will want it to find the last C level record (marked with a double asterisk). The steps are as follows:

1. A SET/NEXT on Key_LevelSeqDesc finds the preceding A level record
2. Using the Entry field in this record, we find that it has child (B) records
3. Using Key_LevelSeqDesc we retrieve the last B level record
4. Using the Entry field in this record, we find that it has child (C) records
5. Using Key_LevelSeqDesc we retrieve the last level C record
6. It has no child records. We have found the correct previous record.
7. We can then repeat this recursive process as we move up another record. It is much simpler this time:
8. A SET/ NEXT on Key_LevelSeqDesc finds the preceding C level record
9. It has no child records. We have found the correct previous record.
10. Now, suppose that the A level record marked with a single asterisk is in fact Collapsed. Then, Step 1. above will read that record, determine that it is collapsed, and not do a probe for child records. The correct previous record has been found in one step.

Promotion and Demotion

We will use the same diagram from above to illustrate promotion and demotion:

Root record
  A level record
    B level record
      C level record
      C level record
      C level record
    B level record *
      C level record *
      C level record *
  A level record
    B level record

Let us say the user wishes to promote the three asterisked records. The B record is to become an A and its C records are to become B's. The user does this by highlighting the B level record and pressing the Promote button. The steps that follow are:

1. Find the PrevLevel of the A level record (B's parent). In this case it is the root record (zero). This value is needed when we change the PrevLevel field in the promoted B record.
2. Change the PrevLevel and Level fields in the promoted B record. In this case, PrevLevel becomes zero and Level takes on the value of the A record's Level field. No change is made to Entry or Sequence.
3. Proceed to change all the children, grandchildren etc. of the promoted record in the same manner.
4. Promotion of all children applies regardless of the setting of the Collapsed byte.

Demotion of the above boxed records would mean demoting the highlighted B record to become the last in the list of C records immediately above it and demoting its child records to become D records. There are obvious restrictions. The last record in the diagram (a B record) cannot be demoted as it has nowhere to go.

Without spelling out a detailed procedure, it is clear that demotion is as easy to do as promotion.

Inserting and Deleting records

Insertion of a record occurs at the level of the highlighted record and immediately below it. To insert the first of a set of child records below a highlighted parent, first insert it at the parent's level and then demote it. Keep the highlight bar on the just-demoted record and the next insertion will be at the same (i.e. child) level. The Entry field must receive the next highest value available.

Deletion of a record with children has to follow the rules set in the browse; that is, it is either restricted or cascaded. Since all the relations between records occur within one file, it stands to reason that a template for a tree browse would allow for this choice.

Conclusion

Failing the discovery of a fatal objection to the above method, a tree of any practical number of levels can be held within a *.tps file (or in any of the comparable files with Clarion drivers). The extra overhead caused by the special purpose routines needed to browse and maintain the tree should not be excessive. The extra fields needed in every record do not occupy that much space.

I have given no consideration to multi-user issues. Promotion and demotion, either of which involves cascading a change through an unknown number of child records, would also require file locking. Changing the relative order of a record would entail locking only that record (and perhaps two adjacent ones). Cascading deletions may also require file locking.

Note - It was originally the intent of Clarion Online to have an article detailing the construction of a template to compliment this specification accompany this article. This turned out not to be feasable because of the complexity of the design, and Mr. Podger's desire that the template be a page-loaded affair, like the BrowseBox. - Publisher

Article comments