alw.sp RAP Version 2 29/07/07 

----------xxxxxxxxxx----------xxxxxxxxxx----------xxxxxxxxxx----------xx

General.

alw is a simple module to hold a list of words in alphabetical order.
There may be several implementations of alw, depending on the relative
importance of the performance under difference circumstances.  The
module does not store the words themselves, and when an insert is called
to put a word onto the list, the pointer handed at that time may be
copied into the arrays, so the calling routine must not change that word
either.  Hence the storage of the library of words is the responsibilty
of the calling module.
The "handles" are the indices into the arrays in ALW, and indices of
proper words shall be at least 3.  Index 1 is a virtual word (not in
the list) that is earlier than all words, and index 2 is similarly a
virtual word later than all words in the list.
At first sight it might be thought that as alwinsert must be given the
handle of where to insert the word, this module can manage words in any
order.  This is not the case, as alw is entitled to rely on the
alphabetical ordering for its operation.
To compare two strings in alpabetical order, each int of the two strngs
are compared in turn, and if a difference is found, that decides the
comparison.  If one string is an initial substring of the other, the
shorter word is considered earlier.  In other words, both strings are
considered to be followed by indefinitely many zeros for the purposes
of the comparison.
The pointers in the ALW struct shall be changed only by alwcons, and
calling modules are entiteld to copy them out at any time and rely on
them being unchanged.  In particular the nty module is expected to do
so.
Similarly the handles of words shall not be changed after being 
allocated by awlinsert, except if the handle itself is deleted by 
alwdelete, or if alwstart is called (rendering all handles invalid).

----------xxxxxxxxxx----------xxxxxxxxxx----------xxxxxxxxxx----------xx

1    the alw module shall provide a header file alw.h that shall

1.1  typedef a struct of type ALW suitable for holding all the context
     necessary for running an alw.  The ALW struct shall have all the
     members specified in section 3.

1.2  provide prototypes of all the modules mentioned in section 2.

----------xxxxxxxxxx----------xxxxxxxxxx----------xxxxxxxxxx----------xx

2   The module shall provide source files suitable to execute the 
    following routines

2.1 a routine void alwcons (ALW * a, int maxword) to construct and
    allocate the arrays necessary to administer the alphabetical list
    of words.

2.2 a routine void alwstart (ALW * a) to set the constructed ALW a to
    be the empty set of words.

2.3 a routine int alwfind (ALW *a, int * word, int len) to locate the
    last word of the list that is less than or equal to the given
    word.  If the word is found exactly, the handle of that word is
    returned, otherwise the handle of the immediately preceeding word
    is negated and returned.

2.4 a routine int alwinsert (ALW *a, int * word, int len, int han) to
    insert the given word immediately after the handle han.  The 
    handle given to the inserted word is returned.  Normally this
    routine is called immediately after alwfind, and han is the return
    value of that function negated.  In any case, the parameter han
    must be the handle of the immediately preceeding word in alpabetical
    ordering and the word inserted must not be already present.

2.5 a routine void alwdelete (ALW *a, int han) to remove the word whose
    handle is han from the list.

----------xxxxxxxxxx----------xxxxxxxxxx----------xxxxxxxxxx----------xx

3   The struct ALW shall have at least the members listed below.

3.1 .nex as a pointer to int (an array of ints) where alw.nex[i] shall 
    be the handle of the next word in alphabetical order.

3.2 .prev as a pointer to int (an array of ints) where alw.prev[i] shall 
    be the handle of the previous word in alphabetical order.

3.3 .word as a pointer to int * (an array of pointers to ints) where 
    alw.word[i] shall be a pointer to the first int of the word. 

3.4 .len as a pointer to int (an array of ints) where alw.len[i] shall 
    be the length of the word in ints.

----------xxxxxxxxxx----------xxxxxxxxxx----------xxxxxxxxxx----------xx

end of alw.sp