In the
previous entry
on this topic, I explained what a device tree is. In Priority, I defined a
simple table (TEST_SERNTREE) that has three main fields: FATHER, SON and
ANCESTOR. Using the previous example of a car and its engine, this table
would hold the following tuple {Father: car serial number; Son: engine
serial number; Ancestor: car serial number}. The Ancestor field* may not be
needed for a strict implementation of device trees, but it helps in order to
identify all the serials for a given tree. As I explained before, this is a
simple one-level representation of data; it is required to write a procedure
that turns this simple data into hierarchical data. A recursive procedure to
create the hierarchical data in pseudocode would be something like
Descend (ancestor); Procedure Descend (sern); begin if sern does not exist then exit; save data about this sern; node = first son of this sern that has yet to be accessed descend (node) end
As computer science tells us, any recursive algorithm can be replaced by an iterative one, and of course that is what is necessary for Priority. The above pseudocode requires some database definitions. "Save data about this sern" means saving it in a table such as STACK4. Initially I wrote a step procedure to display a hierarchical report where the data is saved in STACK4 but afterwards converted the procedure to a form trigger in order to display the data in a form; the trigger uses a dedicated table for this named TEST_SHOWSERNTREE.
The second database definition needed handles the "sern that has yet to be accessed" requirement. Originally I saved the serns that have been accessed in a linked copy of STACK but for some reason this didn't work too well, so eventually I cheated somewhat and added a new field to the TEST_SERNTREE table, USER*. Initially the trigger sets this field to zero for every entry that has the given serial number as ancestor, then sets the value for each device encountered.
Priority programmers are conditioned to use cursors as the primary means of extracting multiple tuples of data from the database. This is the correct means for 99.99% of all procedures, but for this particular procedure, a cursor is not the way to obtain the data. First, we have to obtain data for the first son/sern of the ancestor that has yet to be accessed (i.e. USER = 0), then use this sern in order to obtain data for its first son that has yet to be accessed, then use that sern in order to obtain data for its first son. If there is no unaccessed son left, then the procedure must back up a level and continue from there.
Here is the tree that I am using as the example:
| Father | Son |
|---|---|
| A | B1 |
| A | B2 |
| A | B3 |
| B1 | B1C1 |
| B1 | B1C2 |
| B2 | B2C1 |
| B2 | B2C2 |
| B3 | B3C1 |
| B3 | B3C2 |
| B1C1 | B1C1D1 |
The output should be (ignoring A): B1, B1C1, B1C1D1, B1C2, B2, B2C1, B2C2, B3, B3C1, B3C2.
Going back to computer science, turning recursion into iteration requires a table to retain the depth of recursion. This table gets accessed when the procedure has to backtrack, i.e. after the sern B1C1D1 is accessed, the procedure would try to access the next unaccessed son of B1C1, but as there isn't one, the backtracking table is required in order to 'let the procedure know' that it should continue with B1C2. As this sern has no sons, again the procedure has to backtrack in order to know that is required to continue with B2, then the sons of B2, etc.
Let's write a little code that will be the start of the procedure.
LINK STACK4 TO :$.STK; ERRMSG 1 WHERE :RETVAL <= 0; LINK STACK2 TO :$.ST2; ERRMSG 1 WHERE :RETVAL <= 0; :LINE = 0; :LEVEL = 1; INSERT INTO STACK2 (ELEMENT, TYPE) VALUES (:ANCESTOR, 1); :NODE = :ANCESTOR; UPDATE TEST_SERNTREE SET USER = 0 WHERE ANCESTOR = :ANCESTOR; /********************************/ LABEL 10; SELECT SON INTO :SON FROM TEST_SERNTREE WHERE FATHER = :NODE AND USER = 0; GOTO 20 WHERE :RETVAL <= 0; INSERT INTO STACK2 (ELEMENT, TYPE) VALUES (:SON, :LEVEL + 1); :LINE = :LINE + 1; INSERT INTO STACK4 (KEY, INTDATA, INTDATA2) VALUES (:LINE, :SON, :LEVEL + 1); UPDATE TEST_SERNTREE SET USER = SQL.USER WHERE SON = :SON; :NODE = :SON; :LEVEL = :LEVEL + 1; LOOP 10; LABEL 20;
The code prior to label 10 sets everything up. The variable :NODE will hold 'the current device' and initially is the ancestor. The SELECT statement after LABEL 10 gets 'the first unaccessed son' of :NODE into the variable :SON. If there is no such device, then :RETVAL will be 0 and the code will leave this loop and go to label 20. Assuming that there is a son, it will be stored in STACK2 (this table is the backtrack table), then the son is stored in STACK4. Note that this table has a simple incrementing key - this will ensure that the table will hold the data in the hierarchical order as required. Then the actual sern in the real table TEST_SERNTREE has its USER field updated to show that this sern has been accessed*. Finally :NODE is set to the value of :SON, the level is incremented and the loop continues.
Thus, the first time that LABEL 10 is reached, the value of :NODE will be :ANCESTOR (i.e. A). The SELECT statement will return B1; this serial is entered into both STACK2 and STACK4 as well as being marked as used. Finally :NODE is changed from :A to :B1. The second time that LABEL 10 is reached, the SELECT statement will return B1C1. The third time around, the SELECT statement will return B1C1D1. The fourth time around, the SELECT statement will fail as B1C1D1 has no sons (or one could say that there is no tuple in which FATHER = B1C1D1). So execution jumps to LABEL 20, but I'll leave what happens there for another day.
* This is not optimal and will be corrected in the next installment.
No comments:
Post a Comment