A Better Mousetrap...

How to update Les Bell's year-old telephone directory program.

by Lloyd R Borrett
Your Computer, August 1983

After taking delivery of my IBM-PC microcomputer, I had plenty to do. There were manuals to read and examples to practise with. Finally, I sat down and attempted to program the beast.

Unfortunately, the only programming language available was BASIC, and the IBM-PC dialect was new to me. After searching through magazines for a suitable example, I decided to implement an indexed telephone directory program, written by Your Computer editor Les Bell. The program had been developed for the "BASIC for Birdwatchers" tutorial in the July 1982 edition.

It proved to be a simple task to convert the program for the IBM-PC. However, I wasn't pleased with the program's structure and, once running, some operational limitations became obvious.

I proceeded to created an improved version of the program by changing to a more efficient sort algorithm, moditying the user interface, making allowance for duplicated names and re-structuring the program to use more sub-routines.

Code that is written in BASIC can be difficult to understand and maintain at the best of times. Effective use of the GOSUB statement is one of the easiest ways to improve the structure of a BASIC program.

The GOSUB statement can also reduce the amount of duplicated code. For example, the code to display a file record is duplicated in four places in the original program.

The major sub-routines l've used are:

620 ' *** Add a name to file ***
1090 ' *** Sorted list of file to screen ***
1170 ' *** Display specified names ***
1360 ' *** Delete name from file ***
1590 ' *** Find comment ***

The minor sub-routines used are:

1740 ' *** Routine to display a record ***
1850 ' *** Binary Search ***
2040 ' *** Sort KEYS$ and POSN ***
2180 ' *** Pack pointer arrays and file ***
2400 ' *** Find next record with same name ***
2510 ' *** Hold or Quit display ***
2580 ' *** Put uppercase 1$ in UPPER$ ***

The RETURN statement is only used as the last executable statement of these "sub-routines". This forces a 1-in, 1-out control structure.

In his original version of the program, Les Bell made no allowance for duplicated names. The binary search would always locate the same entry if there was more than one with the same name.

I have added some code which, upon finding a match, steps back through the index to find the first name that matches (lines 1940 to 1960). A pointer to that name is returned. It was then necessary to add a "sub-routine" to return a pointer to the next name that matches (lines 2400 to 2500). These "sub-routines" are used in the sections which find surnames (lines 1170 to 1350) and delete names (lines 1360 to 1580).

Les Bell described the sort used in the original version as a standard Shellsort. While it worked, it was s-l-o-w...

After consulting Algorithms Plus Data Structures Equals Programs (Niklaus Wirth, Prentice-Hall, 1976) and The Art of Computer Programming, Volume 3, Sorting and Searching (Donald Knuth, Addison-Wesley), I decided to try a shuttle interchange sort.

I set up an array of 250 randomly ordered names and ran the two procedures over them. The shuttle interchange sort took 493 seconds, and the Shellsort took 560 seconds. Only a minor improvement.

But in this program, the typical case is a few names being sorted into the existing list. So I ran a procedure which would add five names to a list of 250 sorted names.

The shuttle interchange sort took 20 seconds, and the Shellsort took 506 seconds. Now, that's some difference! I decided to use the shuttle interchange sort!

I can think of ways to speed up the sort even further, and it's possible that another algorithm may also prove faster, but for the time being I shall stick with what l've got.

While there are many ways in which this program could be further improved, I've achieved the goals I set for myself when I started modifying it. So, for the time being, I'll concentrate on using it, instead of playing with it.

While working on a program, there comes a point in time when you feel any extra effort on your part can't be adequately returned. Les Bell probably felt he'd reached that point when he finished the original version.

I've reached that point now. How much further can you take it?

'teldir.bas', listed on 03-15-1983 at 13:26:13

10 '      *** Address / Telephone Directory ***
20 '   TELDIR Revision 1.00
30 '   Written by Lloyd Borrett, March 1983.
40 '   Based on a progran by Les Bell, "Your Coaputer",
       July 1982.
50 '   "BASIC For Birdwatchers", Part IX, page 54.
60 '
70 '      *** Initialize ***
80 DEFINT A - Z
90 DEF FILN$(L) = STRING$(L,95)
       ' Used to produce a string of L underscores.
100 MAXREC = 256  ' Maximum number of records per file
110 TDELAY = 500  ' Time delay constant
120 NONE = 0
       ' No records constant, not in range 1 to maxrec
130 DELETED = NONE  ' Used to flag a record as deleted.
140 NO = 0    ' Constant value for NO
150 YES = 1   ' Constant value for YES
160 DIGO = ASC("0*)
170 DIM KEYS$(256), POSN(256)

180 '    *** Open the files ***
190 ' Get the file name
200 CLS : LOCATE 3,1
210 INPUT "Enter the directory nases (TELDIR) ";FILE$
220 IF FILE$="" THEN FILE$="TELDIR"

230 '    Read the index file
240 ON ERROR GOTO 510
250 OPEN "1", #1, FILE$+".IND"
260 TOPREC = 1  ' Pointer to the next available record
270 IF EOF(1) THEN CLOSE 1 : GOTO 290
280 INPUT #1, KEYS$(TOPREC), POSN(TOPREC) :
      TOPREC = TOPREC + 1 : GOTO 270
290 LOCATE 5,1 :
      PRINT TOPREC-1;" entries in directory ";FILE$;"."
300 FOR I = 1 TO TDELAY : NEXT I

310 '    Open the directory file
320 OPEN "R", #2, FILE$+".TDR", 128
330 FIELD #2, 20 AS FSAME$, 20 AS FCNAME$, 30 AS FADDR$,
      20 AS FCITY$, 4 AS FPSTCD$, 15 AS FTEL$, 19 AS
      FCOMNT$

340 ' *** Display Menu ***
350 SCREEN 0,1 : COLOR 7,0 : CLS
360 LOCATE 3,1 :
      PRINT "TELDIR Revision 1.00 on ";DATE$;" at °;TIME$
370 LOCATE 5,1 :
      PRINT "*** Address / Telephone Directory ***" :
      LOCATE 8,1
380 PRINT "    1. Find name        (Search directory for 
      a surnane)"
100 PRINT "    2. Find comment     (Search directory for
      a comment)"
400 PRINT "    3. View directory   (Display the full
      directory)"
410 PRINT "    4. Add Name         (Create new directory
      entries)"
420 PRINT "    5. Delete name      (Remove directory
      entries)"
430 PRINT "    6. Exit             (Quit and return to
      DOS)"
440 PRINT: PRINT "Press choice: ";

450 '  Get and process the choice.
460 I$ = INKEY$ : IF I$ = "" THEN 460
470 IF 1$ < "1" OR I$ > "6" THEN BEEP : GOTO 460
480 ON ASC(I$) -DI60 GOSUB 1180,1600,1100,640,1370,570
490 GOTO 350

500 ' *** Handle errors ***
510 BEEP: IF ERR <> 53 THEN 540
520 CLOSE:
      PRINT "Directory ";FILE$;
      " doesn't exist. Creating it."
530 TOPREC = 1 : RESUME 320
540 LOCATE 23,20 :
      PRINT "*** Error";ERR;"in line";ERL;"." : STOP

550 ' *** Exit to DOS ***
550 ' Write index file
570 OPEN "0", #1, FILE$+".IND"
580 FOR I = 1 TO TOPREC-1 : WRITE #1, KEYS$(I), POSN(I) : 
      NEXT I : CLOSE
590 REM
600 CLS: SYSTEM

620 ' *** Routine to add a name to rile file ***
630 REM
640 ADDFLG = NO

650 ' Is there roon for more ?

Download/view the "A Better Mousetrap..." article as a PDF file.