This article contains the following executables: KING.EXE KING.OBJ
Todd King
Todd is a programmer/analyst with the Institute of Geophysics and Planetary Physics at UCLA where he works on various software projects. He is writing a book, Dynamic Data Structures, which will be published by Academic Press, late in 1990. Todd can be reached at 1104N. Orchard, Burbank, CA 91506.
The history of the idea of hypertext systems dates back as far as 1945. The first true implementations didn't emerge until about 20 years later and hypertext systems have evolved continually ever since. Hypertext-related concepts have found their way into a variety of applications ranging from context-sensitive help to document-management systems to user-programmable systems such as Apple's HyperCard. Even multimedia hypertext systems (which are the purest form of hypertext) are now within our reach.
In this article, I'll discuss how you can build a hypertext system that can be used for the development of a context-sensitive help system or for the display of hypertext documents. The type of hypertext system presented is a "text-based" (no graphics or sound) system. This type of system is sufficient for many applications, and is easy to implement.
At the level of plain text, a hypertext document differs from an ordinary document in that links in a hypertext document are established between various parts of the document. These links allow you to reposition yourself within the document by navigating along the links. In some ways, a link is an iconic bookmark to which you can move at any time. In the case of a graphical or multimedia hypertext system, other actions may also be associated with a link. For example, a link may display a particular photograph, or even produce music.
Just as a variety of hypertext systems exist, a variety of methods for establishing the links within a hypertext document also exist. In the application presented here, I establish the links at the time when the document is displayed. This step is accomplished as follows: Each topic in the hypertext document has a phrase associated with it. This phrase serves as a tag which, if referenced in another topic, automatically establishes a link. This type of approach allows you to build up your hypertext document either by adding topics when you need them or when you find that certain words or phrases require elucidation. Because the new topics will automatically be linked to all other topics that reference them, you don't have to spend time managing the links -- all you do is write the document.
The Code
The code for the hypertext document display program (which I call hyper_d) is presented in Listing One, page 92. hyper_d is invoked without any command-line arguments (for the sake of simplicity). When the program is invoked it first opens the document file called "HYPER.TXT." hyper_d then calls the function build_hyperbase( ). This function builds an index of topic tags for all of the topics in the file, and stores the location of the beginning of each topic within the file. This tag data base, called "Hyperbase," is used by the display and navigation routines to establish links and to move within the document. The definition for the Hyperbase structure, as well as other definitions, can he found in Listing Two, page 94.
The next function called by hyper_d is enter_text( ). This function references a given topic by its tag, vectors to that topic in the document, and then allows navigation within the document. enter_text( ) returns each time a tag is selected within a document, and then evaluates to the index in Hyperbase of the selected tag. As long as the Esc key is not pr ssed (which returns a special tag ID of - 1), enter_text( ) is called with the tag that represents the current selection. This step repositions you in the document and begins the entire cycle again. If the Esc key is pressed, the application performs some cleanup operations and then exits.
enter_text( ) could also have been implemented as a recursive call, rather than placing it in a while( ) loop. This function was placed in a while( ) loop because this approach minimizes the demands for stack space. Imagine the results of making each topic a separate function, or calling enter_text( ) as the navigational step rather than using looping. You are free to navigate through the document and jump along links as many times as you like, so at some point a recursive implementation would exceed the limits of the application's stack.
Several other functions and structures are used in the application. Rather than describe each one here, I created a hypertext document that describes the entire application. The text for this document is contained in Listing Three, page 94. The structure of the hypertext documents used by this system is very similar to the structure of a conventional document. The listing is quite readable without using hyper_d, but the use of hyper_d makes the process of reading the listing more efficient and more fun.
Using the System
When you've created a hypertext document that you'd like to view, simply place the document in a file called "HYPER.TXT" and run hyper_d. Provided that your document is structured properly, you will be placed at the first item in the first topic, and then set free to navigate through the document. Each link to another topic is displayed as bold type on monochrome screens, and as yellow type on color screens. The currently selected item is displayed in inverse video. To move the highlight around within the document, press either the left or the right cursor key. This step will move you either backward one item (left cursor) or forward one item (right cursor). Once you've highlighted a tag of a topic to which you'd like to move, press the Enter key.
To create a new document, you have to follow some simple rules so that hyper_d can locate each topic. A topic begins with a line that consists of a form feed that is followed by a new line. The next line that follows is the tag string for the topic. Everything that follows the tag line is text for the topic. You can insert any characters into the text portion of a topic, including the graphic characters in the PC's character set. Graphic characters are handy because they give the appearance of being graphically based, when in fact they're only character based.
The way in which you embed a form feed into your document differs from editor to editor. Here's how to do it using a few of the editors that I use regularly. In Turbo C, press Ctrl-P and then press Ctrl-L. In vi, press Ctrl-L while the program is in insert mode. In Microsoft Word, insert a page break by pressing Shift-Ctrl-Return.
Extensions
Many obvious improvements could be made to hyper_d. Only a minimal set of functions has heen implemented in order to present the elements of a hypertext system in the clearest possible way. One obvious improvement would be to add support for a full range of navigational keystrokes, such as the up and down cursor motions. Another improvement would be to "compile" the text, rather than take the "interpreter" approach that was done in this article. This technique would involve the processes of calculating the links (as performed by build_hyperbase( )) and then recording the calculation in some way so that navigation can begin immediately when the document is called.
Some features of more powerful hypertext systems include navigation history lists, which allow you to retrace your steps through a document; the possibility of integrated text and graphics; and scrollable windows. Even though these features (and many more) are expected of hypertext systems today, applications for text-only hypertext still exist. The hypertext system for the documentation of the source code presented in this article is one example.
Conclusion
I think Apple will be remembered fondly for bringing hypertext systems into the hands of the average person -- not so much because the company developed HyperCard, but because Apple gave it away for free, bundled with every Mac. Even though a PC is just as capable of running hypertext systems as a Mac, there isn't a single (as far as I know) PC-based hypertext development system that is given away free or almost free. The PC-based application presented in this article is available for anyone to use, free of charge. You are also welcome to use it as a seed for the development of a more fully featured display system. If you do expand this code directly, please keep the results in the public domain.
This code was developed and tested using Turbo C 2.0. It also uses certain library functions that are unique to Turbo C and are related to screen output. These functions are: clrscr( ), cputs( ), gotoxy( ), textbackground( ), and textcolor( ).
_A SELF-REFERENTIAL HYPERTEXT ENGINE_ by Todd King
[LISTING ONE]<a name="0139_0009">
/*-----------------------------------------
Demonstrates basic principles of hypertext
document construction and management.
(c) Copyright 1989 Todd King
All Rights Reserved
Written: Todd King
-------------------------------------------*/
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <ctype.h>
#include "hyper_d.h"
main()
{
int n;
clrscr();
printf("(c) Copyright 1989 Todd King. All Rights Reserved\n");
sleep(2);
if((Hyper_fptr = fopen("HYPER.TXT", "r")) == NULL)
{
perror("fopen");
exit(1);
}
build_hyperbase();
n = 0;
while((n = enter_text(Hyperbase[n].tag)) != -1) ;
clrscr();
fclose(Hyper_fptr);
}
/*-----------------------------------------
Builds the global index data base for the
hypertext document.
Written: Todd King
-------------------------------------------*/
build_hyperbase()
{
char buffer[MAX_HYPER_LINE];
HYPERITEM *hitem;
int n;
for(;;)
{
if(fgets(buffer, sizeof(buffer), Hyper_fptr) == NULL)
{
break;
}
switch(buffer[0])
{
case '\f':
if((hitem = make_item()) == NULL)
{
fprintf(stderr, "No more room in the Hyperbase\n");
exit(0);
}
fgets(buffer, sizeof(buffer), Hyper_fptr);
n = strlen(buffer);
if(buffer[n - 1] == '\n') buffer[n - 1] = '\0';
set_tag(hitem, buffer);
set_position(hitem, ftell(Hyper_fptr));
break;
}
}
return(Hyper_cnt);
}
/*-----------------------------------------
Enters the hypertext document at a specific
tag location. It then allows navigation within
the document.
Written: Todd King
-------------------------------------------*/
enter_text(tag)
char tag[];
{
int c, n;
HYPERITEM *hitem;
char *bptr;
char *pptr;
char *tptr;
int i;
char buffer[MAX_HYPER_LINE];
int line_put;
int line_cnt = 3;
int col_cnt = 0;
int ref_cnt = 0;
int hidx;
HYPER_REF hyper_ref[MAX_HYPER];
hitem = find_item(tag);
if(hitem == NULL)
{
fprintf(stderr,
"No hypertext subject by the name of '%s' exists\n", tag);
return(-1);
}
hidx = hyper_idx(tag);
clrscr();
fseek(Hyper_fptr, hitem->position, SEEK_SET);
bptr = fgets(buffer, sizeof(buffer), Hyper_fptr);
textcolor(LIGHTGRAY);
gotoxy(1,24);
cputs("ESCAPE: to exit; UP ARROW, DOWN ARROW: to navigate");
gotoxy(1,1);
cputs(tag); cputs("\r\n"); cputs("\r\n");
while(bptr != NULL) /* For all lines in the current hypercard */
{
col_cnt = 1;
for(i = 0; i < Hyper_cnt; i++)
{
if((pptr = strstr(bptr, Hyperbase[i].tag)) != NULL)
{
if( i == hidx) continue; /* no self-referencing */
if(pptr != bptr)
{
if(!ispunct(*(pptr - 1)) && !isspace(*(pptr - 1))) continue;
}
tptr = pptr + strlen(Hyperbase[i].tag);
if(ispunct(*tptr) || isspace(*tptr) || *tptr == '\0')
{
/* Deliniator */
} else { /* No good */
continue;
}
/* If we reach here we've found a genuine tag */
pptr[0] ='\0';
col_cnt += strlen(bptr);
hyper_ref[ref_cnt].line = line_cnt;
hyper_ref[ref_cnt].column = col_cnt;
hyper_ref[ref_cnt].tag = Hyperbase[i].tag;
cputs(bptr);
textcolor(YELLOW);
cputs(Hyperbase[i].tag);
textcolor(LIGHTGRAY);
bptr = pptr + strlen(Hyperbase[i].tag);
col_cnt += strlen(Hyperbase[i].tag);
ref_cnt++;
}
}
cputs(bptr);
cprintf("\r");
if(line_cnt >= 23) { /* What to do at the end of a screen */
break;
}
bptr = fgets(buffer, sizeof(buffer), Hyper_fptr);
if(buffer[0] == '\f') bptr = NULL;
line_cnt++;
col_cnt = 0;
}
if((n = nav_ref(hyper_ref, ref_cnt)) >= 0) return(n);
}
/*-----------------------------------------
The function which performs the actual
navigation within a hypertext document.
Written: Todd King
-------------------------------------------*/
nav_ref(hyper_ptr, max_ref)
HYPER_REF hyper_ptr[];
int max_ref;
{
int advance = 0;
int selected = -1;
int cur_ref = 0;
for(;;)
{
cur_ref += advance;
if(cur_ref < 0) cur_ref = max_ref - 1;
if(cur_ref >= max_ref) cur_ref = 0;
advance = 0;
gotoxy(hyper_ptr[cur_ref].column, hyper_ptr[cur_ref].line);
textbackground(LIGHTGRAY);
textcolor(BLACK);
cputs(hyper_ptr[cur_ref].tag);
switch(getch())
{
case 0:
switch(getch())
{
case DOWN_ARROW:
advance = 1;
break;
case UP_ARROW:
advance = -1;
break;
}
break;
case '\r':
case '\n':
selected = cur_ref;
break;
case ESC:
textbackground(BLACK);
textcolor(LIGHTGRAY);
return(-1);
}
gotoxy(hyper_ptr[cur_ref].column, hyper_ptr[cur_ref].line);
textcolor(YELLOW);
textbackground(BLACK);
cputs(hyper_ptr[cur_ref].tag);
if(selected != -1) return(hyper_idx(hyper_ptr[selected].tag));
}
}
/*-----------------------------------------
Determines the index of a hypertext tag
within the global database.
Written: Todd King
-------------------------------------------*/
hyper_idx(tag_str)
char tag_str[];
{
int i;
for(i = 0; i < Hyper_cnt; i++) {
if(strcmp(tag_str, Hyperbase[i].tag) == 0) return(i);
}
return(-1);
}
/*-----------------------------------------
Locates an item in the global database
with the tag as a key. Returns a pointer
to the entry or NULL if one does not exist.
Written: Todd King
-------------------------------------------*/
HYPERITEM *find_item(tag)
char tag[];
{
HYPERITEM *hitem;
int i;
for(i = 0; i < Hyper_cnt; i++)
{
hitem = &Hyperbase[i];
if(strcmp(tag, hitem->tag) == 0) return(hitem);
}
return(NULL);
}
/*-----------------------------------------
Sets the tag portion of a database entry to
the contents in a passed string
Written: Todd King
-------------------------------------------*/
set_tag(hitem, buffer)
HYPERITEM *hitem;
char buffer[];
{
char *malloc();
hitem->tag = malloc(strlen(buffer) + 1);
if(hitem->tag == NULL)
{
perror("malloc");
exit(2);
}
strcpy(hitem->tag, buffer);
}
/*-----------------------------------------
Makes (extracts) a new database entry item
from the item pool.
Written: Todd King
-------------------------------------------*/
HYPERITEM *make_item()
{
if(Hyper_cnt >= MAX_HYPER) return(NULL);
return(&Hyperbase[Hyper_cnt++]);
}
<a name="0139_000a"><a name="0139_000a">
<a name="0139_000b">[LISTING TWO]<a name="0139_000b">
#define UP_ARROW 72
#define DOWN_ARROW 80
#define ESC 27
typedef struct {
char *tag;
int position;
} HYPERITEM;
typedef struct {
int line;
int column;
char *tag;
} HYPER_REF;
#define MAX_HYPER 1024
HYPERITEM Hyperbase[MAX_HYPER];
int Hyper_cnt = 0;
FILE *Hyper_fptr;
HYPERITEM *make_item();
HYPERITEM *find_item();
#define set_position(h, p) h->position = p
#define TRUE 1
#define FALSE 0
#define MAX_HYPER_LINE 80
<a name="0139_000c"><a name="0139_000c">
<a name="0139_000d">[LISTING THREE]<a name="0139_000d">
.................................................................
Function Flow Diagram
main() build_hyperbase() make_item()
set_tag()
set_position()
enter_text() find_item()
hyper_idx()
nav_ref()
.................................................................
main()
This is an application which displays a hypertext document.
It automatically creates a list of hyper-items (or cards)
which are in the hypertext document. Then it creates the
appropriate links so that you can navigate to any item
which is referenced by any other item. It uses the contents
of the file "HYPER.TXT" as the hypertext document and begins
at the first item in the document.
Function Flow Diagram
.................................................................
build_hyperbase()
build_hyperbase()
This function builds the global database for the hypertext
document. It scans the entire document an assembles a list
of all cards in the document and stores their location
within the file and the tag which the card is to be known
by. This database is stored in the global variable
"Hyperbase".
Function Flow Diagram
.................................................................
enter_text()
enter_text(tag)
char tag[];
Enters the hypertext document at a specific
tag location. The tag (a string) is passed in the variable
first variable called "tag". It then allows navigation
within the document.
Function Flow Diagram
.................................................................
nav_ref()
nav_ref(cur_ref, hyper_ptr, max_ref)
int cur_ref;
HYPER_REF hyper_ptr[];
int max_ref;
This function performs the actual navigation within a
single card. It returns the index of the hyper-item within
the card which was selected. A special code (-1) is returned
if a request to exit is entered. "cur_ref" is the index of
the current card, "hyper_ptr" is a pointer to a structure
containing the list of references in the card and "max_ref
is the number of references in "hyper_ptr".
Function Flow Diagram
.................................................................
hyper_idx()
hyper_idx(tag_str)
char tag_str();
Returns the index of the tag "tag_str". The global
database ("Hyperbase") is searched for the existence of
the tag.
Function Flow Diagram
.................................................................
find_item()
HYPERITEM *find_item(tag)
char tag[];
Locates an item in the global database ("Hyperbase")
with the tag as a key. Returns a pointer
to the entry or NULL if one does not exist.
Function Flow Diagram
.................................................................
set_tag()
set_tag(hitem, buffer)
HYPERITEM *hitem;
char buffer[];
Sets the tag portion of the database entry pointed
to by "hitem" to the contents in the string "buffer".
Function Flow Diagram
.................................................................
make_item()
HYPERITEM *make_item()
Makes a new database entry. Actually it extracts
the next available entry for a pool and returns a pointer
to the entry.
Function Flow Diagram
.................................................................
set_position()
set_position(h, p)
HYPERITEM *h;
int p;
Actually a psuedo-function (created with a define) which
assigns an location of an item in a file to the item
definition.
Function Flow Diagram
.................................................................
HYPERITEM
A structure which contains a complete description a single
item (or card) with the hypertext document. It is of the
form:
typedef struct {
char *tag;
int position;
} HYPERITEM;
Function Flow Diagram
.................................................................
HYPER_REF
A structure of the form:
typedef struct {
int line;
int column;
char *tag;
} HYPER_REF;
Function Flow Diagram
.................................................................
HYPER.TXT
The text file which contains the hypertext document. The
beginning of an item is marked by a special line. This line
is a formfeed followed by a newline. The next line after
this is considerd to be the name of the item (the item tag).
If this name appears in any other tag then navigation to
the item is allowed by selecting the tag in the item.
Function Flow Diagram
