Browsing the NAMES file

Now that three B-trees have been created by the BUILD program for the NAMES file, it is possible to search and display the file in a variety of ways. This is done with a "browser" program like the following:

    BROWSE.NAMES
001 * Define the fields in our file items
002 EQU AMC$FNAME TO 1
003 EQU AMC$LNAME TO 2
004 EQU AMC$COMP TO 3
005 EQU AMC$ADR TO 4
006 EQU AMC$ZIP TO 6
007 *
008 * Define the three available b-tree roots
009 EQU root1 TO "ZIP"
010 EQU root2 TO "COMP"
011 EQU root3 TO "LNAME"
012 *
013 OPEN "NAMES" TO NFILE ELSE STOP
014 OPEN "B-TREE" TO BFILE ELSE STOP
015 *
016 clear = @(-1) ;* Chars for clearing the screen
017 bell = CHAR(7) ;* ...for sounding the alarm
018 eos = @(-3) ;* ...clear to end of screen
019 eol = @(-4) ;* ...clear to end of line
020 center.line = 11 ;* Middle row on screen
021 *
022 CRT clear: ;* Clear the screen
023 WIDTH.SET = 1 ;* Choose std width settings
024 *
025 * Choose one of the three b-trees to start
026 ROOT = root1 ; FRAG = AMC$ZIP
027 * ROOT = root2 ; FRAG = AMC$COMP
028 * ROOT = root3 ; FRAG = AMC$LNAME
029 *
030 100 * Pick the starting item id out of the root
031 READ ROOT.ID FROM BFILE,ROOT ELSE STOP "Build!"
032 READ ROOT.NODE FROM BFILE,ROOT.ID ELSE STOP "Build!"
033 * Pick the id in the middle of the node
034 CURR.ID = ROOT.NODE<2, INT(ROOT.NODE<1>+2)/2>
035 *
036 200 * Get the item with the current id
037 READ ITEM FROM NFILE, CURR.ID ELSE GO TO 100
038 *
039 300 * Find the node holding the current id
040 CALL BTPFIND(ROOT, BFILE, NFILE, CURR.ID, ITEM, NODE.ID, NODE.POS)
041 *
042 400 * Remember the node with the current id
043 CURR.NODE = NODE.ID ; CURR.POS = NODE.POS
044 *
045 500 * Define all data and column formats
046 BEGIN CASE
047 CASE WIDTH.SET = 1 ;* Standard width settings
048   NAME.LEN = 11 ;* Width of name field
049   FNAME.LEN = 2 ;* Width of first name only
050   COMP.LEN = 15 ;* Width of company name
051   ADR.LEN = 26 ;* Width of address field
052   ZIP.LEN = 5 ;* Width of ZIP field
053   ABOVE.BELOW = 9 ;* How many above/below center
054 CASE 1 ;* WIDTH.SET must be 2, widen the name
055   NAME.LEN = 26 ;* Width of name field
056   FNAME.LEN = 11 ;* Width of first name only
057   COMP.LEN = 11 ;* Width of company name
058   ADR.LEN = 15 ;* Width of address field
059   ZIP.LEN = 5 ;* Width of ZIP field
060   ABOVE.BELOW = 9 ;* How many above/below center
061 END CASE
062 *
063 * Define positions for V's at top of columns
064 COMP.TAB = NAME.LEN+7
065 ZIP.TAB = COMP.TAB+COMP.LEN+ADR.LEN+2
066 TOTAL.WIDTH = ZIP.TAB+ZIP.LEN ;* For hyphens
067 *
068 600 CRT @(0,0): ;* Show V's at top of sorted column
069 BEGIN CASE
070 CASE ROOT = root1; CRT SPACE(ZIP.TAB):STR("V",ZIP.LEN):eol:
071 CASE ROOT = root2; CRT SPACE(COMP.TAB):STR("V",COMP.LEN):eol:
072 CASE 1; CRT STR("V",NAME.LEN):eol:
073 END CASE
074 *
075 I = 1 ; CRT @(0,center.line): ;* Move to display ctr
076 NEXT.ID=CURR.ID;NODE.ID=CURR.NODE;NODE.POS=CURR.POS
077 LOOP ;* Paint lower half of tube
078   READ ITEM FROM NFILE, NEXT.ID ELSE GO TO 100
079   GOSUB 700 ;* Display one item
080   * Remember last line painted for quick jumps
081   BOTTOM.ID=NEXT.ID ; BOTTOM.NODE=NODE.ID ; BOTTOM.POS=NODE.POS
082   IF I = 1 THEN ;* First item
083     CRT ; CRT STR("-",TOTAL.WIDTH):eol:
084     TOP.ID = NEXT.ID ; TOP.NODE = NODE.ID ; TOP.POS = NODE.POS
085     CALL BTPSEQ(BFILE, NODE.ID, NODE.POS, "PREV", PREV.ID)
086     PREV.NID = NODE.ID ; PREV.NPOS = NODE.POS
087     NODE.ID = CURR.NODE ; NODE.POS = CURR.POS
088     END
089   CRT ;* Done with this line, go to next
090   CALL BTPSEQ(BFILE, NODE.ID, NODE.POS, "NEXT", NEXT.ID)
091 WHILE (NEXT.ID # "") AND (I <= ABOVE.BELOW) DO
092   I = I+1
093 REPEAT
094 CRT eos: ;* Clear to end of screen
095 *
096 * Reposition for top half of display
097 ROW = center.line-1
098 CRT @(0,ROW):STR("-",TOTAL.WIDTH):eol:
099 NEXT.ID = PREV.ID ;* GOSUB expects NEXT.ID
100 NODE.ID = PREV.NID ; NODE.POS = PREV.NPOS
101 I = ABOVE.BELOW ;* How many loops to make
102 LOOP WHILE (NEXT.ID # "") AND (I>0) DO ;* Top half
103   READ ITEM FROM NFILE, NEXT.ID ELSE GO TO 100
104   ROW=ROW-1; CRT @(0,ROW): ; GOSUB 700 ;* Show item
105   * Remember top line painted for future quick jumps
106   TOP.ID=NEXT.ID; TOP.NODE=NODE.ID; TOP.POS=NODE.POS
107   CALL BTPSEQ(BFILE,NODE.ID,NODE.POS,"PREV",NEXT.ID)
108   I = I-1 ;* Move up to previous item
109 REPEAT
110 *
111 LOOP ;* Clear remaining top of screen if any
112   ROW = ROW-1
113 WHILE ROW > 0 DO
114   CRT @(0,ROW):eol: ;* Clear to end of line
115 REPEAT
116 *
117 CRT @(0,23): ;* Go to corner and show commands
118 CRT "N/U/UU/D/DD/W1/W2/Z/C/L/X/return/chars/lname(;fname)/(.)id #":
119 INPUT COMMAND: ;* Get a command
120 CRT @(0,23):eol: ;* Erase commands while processing
121 BEGIN CASE
122 CASE COMMAND = "U" ;* Move up to previous item
123   NODE.ID = CURR.NODE ; NODE.POS = CURR.POS
124   CALL BTPSEQ(BFILE,NODE.ID,NODE.POS,"PREV",PREV.ID)
125   IF PREV.ID = "" THEN CRT bell: ELSE
126     CURR.ID=PREV.ID ; CURR.NODE=NODE.ID ; CURR.POS=NODE.POS
127     END
128 CASE COMMAND = "UU" ;* Move up to top item
129   CURR.ID=TOP.ID ; CURR.NODE=TOP.NODE ; CURR.POS=TOP.POS
130 CASE COMMAND = "D" ;* Move down to next item
131   NODE.ID = CURR.NODE ; NODE.POS = CURR.POS
132   CALL BTPSEQ(BFILE,NODE.ID,NODE.POS,"NEXT",NEXT.ID)
133   IF NEXT.ID = "" THEN CRT bell: ELSE
134     CURR.ID=NEXT.ID ; CURR.NODE=NODE.ID ; CURR.POS=NODE.POS
135     END
136 CASE (COMMAND = "DD") OR (COMMAND = "") ;* Move down to last item
137   CURR.ID=BOTTOM.ID ; CURR.NODE=BOTTOM.NODE ; CURR.POS=BOTTOM.POS
138 CASE COMMAND = "W1" ;* Use standard widths
139   WIDTH.SET = 1 ; GO TO 500
140 CASE COMMAND = "W2" ;* Use wide names
141   WIDTH.SET = 2 ; GO TO 500
142 CASE COMMAND = "Z" ;* Use the ZIP b-tree
143   ROOT = root1 ; FRAG = AMC$ZIP ; GO TO 200
144 CASE COMMAND = "C";* Use the COMP b-tree
145   ROOT = root2 ; FRAG = AMC$COMP ; GO TO 200
146 CASE COMMAND = "L" ;* Use the LNAME b-tree
147   ROOT = root3 ; FRAG = AMC$LNAME ; GO TO 200
148 CASE COMMAND = "N" ;* Find different value
149   READV PREV.FRAG FROM NFILE, CURR.ID, FRAG ELSE GO TO 100
150   LOOP ;* Step through items until value changes
151     READ ITEM FROM NFILE, CURR.ID ELSE GO TO 100
152     NODE.ID = CURR.NODE ; NODE.POS = CURR.POS
153     CALL BTPSEQ(BFILE, NODE.ID, NODE.POS, "NEXT", NEXT.ID)
154     CHANGE = (PREV.FRAG # ITEM<FRAG>)
155   UNTIL (NEXT.ID = "") OR CHANGE DO
156     CURR.ID=NEXT.ID ; CURR.NODE=NODE.ID ; CURR.POS=NODE.POS
157   REPEAT
158 CASE COMMAND = "X" ; STOP
159 CASE ((ROOT=root1) & NOT(COMMAND MATCHES"5N")) OR
      (COMMAND MATCHES "'.'0N") OR ((ROOT#root1) AND (COMMAND MATCHES "0N"))
160   GOOD.ID = CURR.ID ;* Remember good ID number
161   CURR.ID = OCONV(COMMAND,"MCN")
162   FOUND = 1 ;* Assume new ID exists
163   READ ITEM FROM NFILE, CURR.ID ELSE FOUND = 0
164   IF FOUND THEN GO TO 300 ELSE CURR.ID = GOOD.ID ; CRT bell:
165 CASE 1 ;* Search for arbitrary string
166   DUMMY.ID="";DUMMY.ITEM="";*Start w/ nothing
167   BEGIN CASE ;* Put string in approp dummy pos
168   CASE ROOT=root1;DUMMY.ITEM<AMC$ZIP>=COMMAND
169   CASE ROOT=root2;DUMMY.ITEM<AMC$COMP>=COMMAND
170   CASE 1 ;* Must be root3, split into names
171    DUMMY.ITEM<AMC$LNAME>=OCONV(COMMAND,"G;1")
172    DUMMY.ITEM<AMC$FNAME>=OCONV(COMMAND,"G1;1")
173   END CASE
174   CALL BTPFIND(ROOT,BFILE,NFILE,DUMMY.ID, DUMMY.ITEM,NODE.ID,NODE.POS)
175   CURR.ID = DUMMY.ID
176   GO TO 400
177 END CASE
178 GO TO 600
179 *
180 700 * Display a name and address item
181 NAME.STR = ITEM<AMC$FNAME> ("L#":FNAME.LEN):" ":ITEM<AMC$LNAME>
182 CRT NAME.STR ("L#":NAME.LEN):" ":
183 CRT NEXT.ID "R#5":" ":
184 CRT ITEM<AMC$COMP> ("L#":COMP.LEN):" ":
185 CRT ITEM<AMC$ADR> ("L#":ADR.LEN):" ":
186 CRT ITEM<AMC$ZIP> ("L#":ZIP.LEN):eol:
187 RETURN
188 *
189 END

Use the Editor to type in the above code for the BROWSE.NAMES program, then compile and catalog the program.

BROWSE.NAMES calls two more B-TREE-P subroutines that help it traverse B-trees: BTPFIND is a subroutine that finds the position of a given file item in a B-tree. BTPSEQ is a subroutine that, given the position of an item previously found with BTPFIND, locates the previous or next item in the B-tree. (BTPSEQ is short for BTP Sequential.) Like BTPINS, the code in BTPFIND and BTPSEQ will never have to be modified, regardless of the application files being used or the way in which files are sorted and searched.

Use the Editor to type in the following code for BTPFIND and BTPSEQ, then compile and catalog the programs:

    BTPFIND
001 SUBROUTINE BTPFIND(ROOT, BFILE, DFILE, ID, ITEM, NODE.ID, NODE.POS)
002 CALL BTPKEY(ROOT, ID, ITEM, FK)
003 READ NODE.ID FROM BFILE, ROOT ELSE STOP "BTP8"
004 100 READ N FROM BFILE, NODE.ID ELSE STOP "BTP9"
005 L = 0 ; R = N<1>+1
006 IF R = 1 THEN NODE.POS = 1 ELSE
007   LOOP
008     NODE.POS = INT((L+R)/2)
009     UID = N<2, NODE.POS>
010     IF UID = ID THEN RETURN
011     READ IT FROM DFILE, UID ELSE STOP "BTP10"
012     CALL BTPKEY(ROOT, UID, IT, KEY)
013     IG = (FK > KEY)
014     IF IG THEN L = NODE.POS ELSE R = NODE.POS
015   UNTIL (R-L) <= 1 DO REPEAT
016   IF IG THEN NODE.POS = R
017   END
018 NNID = N<3, NODE.POS>
019 IF NNID # "" THEN
020   NODE.ID = NNID
021   GO TO 100
022   END
023 IF NODE.POS > N<1> THEN NODE.POS = N<1>
024 ID = N<2, NODE.POS>
025 RETURN
026 END

    BTPSEQ
001 SUBROUTINE BTPSEQ(BFILE,NODE.ID,NODE.POS,PN,ADJKEY)
002 PREV = (PN="PREV")
003 IF PREV THEN P = NODE.POS ELSE P = NODE.POS+1
004 READ N FROM BFILE, NODE.ID ELSE STOP "BTP11"
005 I = N<2, NODE.POS>
006 100 NNID = N<3, P>
007 IF NNID # "" THEN
008   NODE.ID = NNID
009   READ N FROM BFILE, NODE.ID ELSE STOP "BTP12"
010   IF PREV THEN P = N<1>+1 ELSE P = 1
011   GO TO 100
012   END
013 IF N<2, NODE.POS> # I THEN
014   IF PREV THEN NODE.POS = N<1> ELSE NODE.POS=1
015   ADJKEY = N<2, NODE.POS>
016   RETURN
017   END
018 IF PREV AND (NODE.POS > 1) THEN
019   NODE.POS = NODE.POS-1
020   ADJKEY = N<2, NODE.POS>
021   RETURN
022   END
023 IF NOT(PREV) AND (NODE.POS < N<1>) THEN
024   NODE.POS = NODE.POS+1
025   ADJKEY = N<2, NODE.POS>
026   RETURN
027   END
028 200 PID = N<4>
029 IF PID # "" THEN
030   READ F FROM BFILE, PID ELSE STOP "BTP13"
031   LOCATE(NODE.ID,F,3;NODE.POS) ELSE STOP"BTP14"
032   IF (PREV AND (NODE.POS=1)) OR (NOT(PREV) AND NODE.POS > F<1>) THEN
033     NODE.ID = PID
034     N = F
035     GO TO 200
036     END
037   IF PREV THEN NODE.POS = NODE.POS-1
038   ADJKEY = F<2, NODE.POS>
039   NODE.ID = PID
040   END ELSE ADJKEY = ""
041 RETURN
042 END

Note that BTPSEQ uses a LOCATE in line 031 to make an unsorted search for NODE.ID in the third attribute of F, setting NODE.POS accordingly. The syntax of the LOCATE statement may have to be slightly different for your compiler.

Now that you have filled the NAMES file with items created with the GET.NAMES program, and have filled the B-TREE file with three B-trees using the BUILD program, you are ready to search and display the NAMES file using the browser program. Give the command BROWSE.NAMES to execute the cataloged BROWSE.NAMES program.

Your terminal will display the NAMES items, sorted by ZIP code. The file items will appear in five columns: names, id numbers, companies, addresses, and ZIP codes. A line of V's at the top of the display indicates that the ZIP column is the currently sorted column. Two horizontal lines of hyphens through the center of the display surround the center "anchor" item. The bottom of the display shows a prompt for one of the fifteen different possible browser commands. You must hit the Return key after any command you type.

Type a U to scroll the display up by one line. Type UU to scroll up ten lines at once. Similarly, type D to scroll down one line, or DD or just the Return key to scroll down ten lines at once.

Type W2 to widen the name column and use less space in the company and address columns. Type W1 to return the name column back to its original width.

Type an L to show the names sorted by last name instead of ZIP code. The name and address in the center of the display remains in position as an anchor, and the rest of the names are resorted above and below. Note that the V's at the top of the display are now over the name column to indicate it is the currently sorted column.

Type a C to show the names sorted by company. As always, the center name and address stays in position, and the remaining items are sorted around it. Type a Z to return to the ZIP code sort.

Typing any string of characters that is not a reserved command finds the first item with that string in the currently selected column, and shows the item at the center of the display. For example, if the company column is currently selected and sorted (designated by V's at the top of the column), and you type MAT, the display will jump to the companies starting with the characters MAT. If no item matches the string you typed, the item that most closely matches is displayed.

Typing a number at any time changes the center anchor item on the display to the item with the ID number you just typed. But if the ZIP column is currently selected with V's and you type a five-digit number, the browser assumes you are searching for a ZIP code, and displays the first item with that ZIP. Precede a five-digit ID with a period (.) to force the browser to treat the number as an ID instead of as a ZIP code when the ZIP column is selected.

If the name column is selected with V's and you type two strings separated by a semicolon (;), the browser treats the string as last name;first name. For example, typing SMITH jumps to the first SMITH, but typing SMITH;T jumps to the first SMITH that also has a first name starting with T.

Type an N to find the next item with a different value in the currently selected column. For example, if the ZIP column is selected and the N command is given, the browser will search starting at the anchor item down the ZIP column until an item with a different ZIP code is found. That item then becomes the new anchor item. The N command is handy for skipping by long runs of identical names or ZIP codes, without having to know what the next different value is.

Finally, the X command will terminate BROWSE.NAMES and exit the program. Type BROWSE.NAMES to restart browsing.