%Aug 1995, modified Feb 1996
%Paradigm: Searching
%C.G. van der laan, cgl@rc.service.rig.nl
\input blue.tex  \loadtocmacros%\tolerance500\hbadness=499\hfuzz=5pt
                 %\parindent=1pc
\everyverbatim{\emc}
\bluetitle Paradigms: Searching

\blueissue \maps{96}2

%\blueauthor Kees van der Laan

\beginscript

\bluehead BLUe's Design VIII

Hi folks. 
I started using \LaTeX{} for my hobby bridge, to typeset
bid sequences and plays. Important in these kind of plays
is  data integrity, i.e.\ the system should remember
that a card has been played.
In \TeX nical terms it comes down to update the computer memory. 
This is precisely what makes computer-assisted typography different 
from previous formatting techniques. We can update memory.

This is a common phenomenon and the problem can be formulated
in general terms as deleting an element from a set.

The central macro in BLUe's format searching is \cs{loc},
and for selective loading \cs{lst} must be defined appropriately.

Before delving into the details where I have needed searching, I'll
touch upon searching \TeX niques, as used in \TB.

\bluehead Searching in \TB

The examples of searching are about balancing columns. 

On page {\oldstyle387} it is applied to adjusting the column widths when we have
the  English text in column one and the same text in another language
in column two. With fixed column widths the column lengths are different.

On page {\oldstyle417} the manmac macro \cs{balancecolumns} is given to
balance two columns on the last page of the index of \TB. 
These \TeX niques and macros have been used\Dash and customized a little\Dash
for typesetting BLUe's format indexes.\ftn{My major contribution in this area
   is that I process indexes on the fly, in one-pass.}

\bluehead Salomon's procrusting

Salomon\ftn{Advanced \TeX, Springer, {\oldstyle1995}, page {\oldstyle189}.} 
looks for the optimal font size in fitting text to a box of prescribed size. 
The essence of the search process is given stripped from other aspects. 
I modified his example as follows.
\thisverbatim{\unmc}
\beginverbatim
%Salomn's fitting text to a box
%Sept 95, cgl@rc.service.rug.nl
\begingroup
%Text
\toks0{Leentje leerde lotje lopen 
       langs de lange lindenlaan.}
%Restrictions 
\hsize=3cm \dimen1=20pt%\vsize=20pt
\def\showresult{\rlap{\f 
    Fontsize=\the\dimen0\quad
    ht, dp=\the\ht0, \the \dp0}
    \copy0\smallbreak}
%Start: first estimate size of font
\dimen0=5pt
\loop\font\f=cmr10 at\dimen0
   \setbox0=\vbox{\tolerance10000 
   \baselineskip\dimen0 
   \f \the\toks0 }
\showresult
\ifdim\ht0<\dimen1 %next, linear search
   \advance\dimen0 by1pt
\repeat
%make the best fit
\advance\dimen0 by-1pt
\font\f=cmr10 at\dimen0
   \setbox0=\vbox to\dimen1{\tolerance10000 
   \baselineskip\dimen0 plus 1pt minus1pt
   \f \the\toks0 }
\showresult
\endgroup
%Remark: extension to adjust for total size 
%of box is left to the reader, and the 
%context
\bye
!endverbatim

\bluehead Finding an element

The basic functionality is to locate an element in a set. 
The result is the value of the Boolean \cs{iffound}.
BLUe's format uses the following approach.\ftn{Assumed is
    that the set does not contain a period.}
\beginverbatim
\def\loc#1#2{%locate #1 in #2 a def
  \def\locate##1#1##2\end{\ifx\empty##2\empty
    \foundfalse\else\foundtrue\fi}%
  \ea\locate#2.#1\end}
!endverbatim

To append the searched for element at the end of the arguments for \cs{locate}
is related to the sentinel technique in programming.

\blueexample Printing vowels in bold

Schwarz {\oldstyle1987} coined the problem to print vowels
in bold face.\ftn{His solution mixes up the picking up of list
   elements and the process to be applied. Moreover, his nesting of
   {\tt\char92if}-s
   in order to determine whether a character is a vowel or not, 
   is not elegant.}

The problem can be split into two parts. First, the general part of going
character by character through a string, and second, decide whether the
character at hand is a vowel or not.

For the first part use \cs{fifo}.

For the second part, combine the vowels into a string, |aeiou|,
and the problem can be reduced
to the question $\langle char\rangle\in{}$|aeiou|?

With \cs{process} appropriately defined\Dash 
   locate the argument in the string of vowels\Dash
|\fifo Audacious\ofif| yields
\newif\iffound%
\def\loc#1#2{%locate #1 in #2
  \def\locate##1#1##2\end{\ifx\empty##2\empty
    \foundfalse\else\foundtrue\fi}%
  \locate#2#1\end}%
\def\process#1{\uppercase{\loc#1}{AEIOU}%
\iffound{\bf#1}\else#1\fi}%
\fifo Audacious\ofif,
with
\beginverbatim
\def\process#1{\uppercase{\loc#1}%
  {AEIOU}\iffound{\bf#1}\else#1\fi}
!endverbatim

\blueexample Searching a set of accent strings
 
In sorting in \TeX{} I determine whether a control symbol belongs to the set of
accents\Dash|\def\accstr{\`\'\"\^\c}|. 
In the macro \cs{nxtw} the relevant invoke reads as follows.
\beginverbatim
\ea\loc\head\accstr
!endverbatim
The same approach has been applied in my BLUe-2-MAPS convertor
assistant.

\blueexample Searching a set of Pascal reserved words
 
In typesetting PASCAL fragments I  determine whether a word belongs to the set
of reserved words. 
The set of reserved words reads
\beginverbatim
\reservedset{and array begin case const 
 div do downto else end. end; file for 
 function goto if in label mod nil not of 
 or packed procedure program record repeat 
 set then to type until var while with}
!endverbatim
The relevant invoke in \cs{processw} reads
\beginverbatim
\loc{#1}{\the\reservedset}%
!endverbatim
The Pascal environment scans the program fragment line-by-line and 
each line word-by-word.
Each word is tested against the set of reserved words.

\bluehead Deleting an element 

The functionality is to delete an element from a set.
It consists of two steps: finding and deleting.
It can be coded as a variant of \cs{loc}, with as result not a 
Boolean but the modified set. A template might read as follows.
\beginverbatim
\def\delete#1#2{%Delete #1 from #2 a def
  \def\locate##1#1##2\end{\ifx\empty##2\empty
    \else\def#2{##1##2}\fi}%
  \ea\locate#2#1\end}
!endverbatim
Addition of an element to a set can be done as follows.\ftn
{This is not so much about searching but added for your convenience.}
\beginverbatim
\def\add#1#2{%Add #1 to #2 a def
   \ea\def\ea#2\ea{#2#1}}
%or when #2 consists of unexpandable tokens
\def\add#1#2{%Add #1 to #2 a def
   \xdef#2{#2#1}}
!endverbatim

\blueexample Updating a hand in bridge

Bridge is an elimination play like most games.
From the start elements are removed.
The deletion of a card is a little special 
because we know that the card is there.
The macro is called \cs{strip} and has been adapted.
The hand is a definition instead of a token variable. 
\beginverbatim
\def\strip#1#2{%Function:
% delete card value #1, is AKQJT9...2
% from #2, a def.
  \def\wis##1#1##2\siw{\gdef#2{##1##2}%
   \ifx#2\empty\gdef#2{--}\fi}%
  \ea\wis#2\siw}
!endverbatim

Remarks. In the above example the searching (and deleting) is a side-effect of the printing. 
It is merely there to guarantee data integrity. 
If only attention is paid to the main issues,
the searching would have been remained hidden, under a `pile of cards'\smiley.
It is worth it to make some kind of library macro out of it\Dash
at least a template\Dash ready for reuse.

Realize that the searched for element is supplied dynamically.

\blueexample Modifying \cs{dospecials} 

Inspired upon the Babel macros the following
alternatives which also obey the locality character.
\beginverbatim
%Variant \bbl@add@specials
%No grouping, nor edef, 
%assumed \dospecials, \sanitize are defined.
%
\let\sanitize\empty \let\dospecials\empty
%
\def\addspecials#1{\ea\def\ea
  \dospecials\ea{\dospecials\do#1}%
                   \ea\def\ea
  \sanitize\ea{\sanitize\makeother#1}
}
%
%Variant \bbl@remove@specials 
%No grouping, nor edef, 
%assumed \dodefault available
%
\let\dodefault\empty
%
\def\removespecials#1{%
   \def\do##1{\ifnum`#1=`##1 
              \else\nx\do\nx##1\fi}
   \edef\dospecials{\dospecials}
   \def\makeother##1{\ifnum`#1=`##1 
              \else\nx\makeother\nx##1\fi}
   \edef\sanitize{\sanitize}
\let\do\dodefault 
\let\makeother\makeotherdefault
}
!endverbatim

\bluehead \DeK's set macros

In \TB{} the locating of an element\Dash and delete it\Dash
is done as follows.

\DeK{} provides \cs{remequivalent},\ftn
{As part of a suite of set macros.}
\TB{} {\oldstyle380}, which uses a very general \TeX nique. 
I'll untangle and recast the coding in the FIFO\Dash First In First Out\Dash notation.

\blueexample A set is just a list of defs

Suppose the set reads |\def\set{\a\b\c}|. Then
\beginverbatim
%Assume #2 not empty
\def\remequivalent#1\from#2{%
   \def\process##1{\ifx#1##1\else\nx##1\fi}
   \xdef#2{\ea\fifo#2\ofif}}
\def\fifo#1{\ifx\ofif#1\ofif\fi
   \process{#1}\fifo}
\def\ofif#1\fifo{\fi}
!endverbatim

\blueexample A set is a list of defs with list element tags

Suppose the set reads |\def\set{\\\a\\\b\\\c}|. Then
\beginverbatim
%Assume #2 not empty
\def\remequivalent#1\from#2{%
   \def\\##1{\ifx#1##1\else\nx\\\nx##1\fi}%
   \edef#2{#2}}
!endverbatim
Once we use list element tags we can also have more general
elements, as \DeK{} put it `control sequences which are \cs{ifx}-equivalent
to a given control sequence.'

\blueexample A set is a more general list of control sequences 

Suppose the set reads |\def\set{\\\a\\\b\\\c}|. Then
\beginverbatim
%Assume #2 not empty
\def\remequivalent#1\from#2{\let\given=#1%
\def\\##1{\ifx#1##1\else\nx\\\nx##1\fi}%
   \edef#2{\ea\fifola#2\alofif}}
\def\fifola\\#1#2{\ifx#1\given\else\nx\\\nx#1\fi
   \ifx#2\alofif\alofif\fi\fifola#2}
\def\alofif#1\alofif{\fi}
!endverbatim
Finally, it can be extended by the test for the emptiness of \cs{set}.

\bluehead Database use

While developing BLUe's format system and using the database idea
other search \TeX niques have been coded.
Needed are facilities for browsing a database next to 
macros for selective loading of 
   addresses, 
   a format, 
   pictures, 
   references, or 
   tools.

The browse macros are based on \cs{loc}, and can be associated  with the 
keyword pattern recognition.

The selective loading macros are based on the proper definition of the
list element tag.

Below the searching aspects have been put together.
`BLUe's Databases' treats the use and coding of BLUe's format databases in depth.

\bluesubhead Pattern recognition

A nice application is mail-merge, merging addresses with a letter.

\blueexample Match addresses for the pattern RUSSIA

\beginverbatim
\input blue.tex \letter \searchfile{address}
\search{RUSSIA}
\bye
!endverbatim
To send a letter to all those persons or to make all address labels
insert \cs{makesearchletters}, respectively \cs{makesearchlabels}
before \cs{bye}.

\blueexample Coding the search macro

At the heart lies the earlier mentioned \cs{loc} macro.
Because we need to do more with found entries than just knowing that they are there,
their names, preceded by the list element tag for further action,
are collected in the toks variable \cs{namelst}.
For convenience the names are also written to the log file, 
in order that we can follow what is going on.
\beginverbatim
\def\search#1{\def\loc##1##2{%
   \def\locate####1##1####2\end
   {\ifx\empty####2\empty\foundfalse
   \else\foundtrue\fi}\ea\locate##2.##1\end}
   \def\lst##1##2{\loc{#1}{##2}\iffound
   \immediate\write16{\nx##1}%log file
   \namelst\ea{\the\namelst\lst##1}
   \def##1{##2}%define found element
   \fi}\input\the\searchfile.dat\relax}
!endverbatim

\bluesubhead Selective loading

This is also a search activity. 
The file is scanned and when an entry is found it will be loaded.
The details of the selective loading process depend
on the entries of the database.
I call them class I and class II databases.

\bluesubsubhead Formats and tools

The idea is that for example \cs{letter} only loads the letter 
macros from |fmt.dat|. 
In the examples below use is made of \cs{tool},
with the functionality that when the tag after is known
the control sequences which follow the tag until \cs{endinput}
will be loaded, otherwise all in between the tag and 
\cs{endinput} will be gobbled. 
\beginverbatim
\long\def\tool#1{\ifx#1\undefined
          \bgroup\unouterdefs
            \ea\gobbletool\fi}
\long\def\gobbletool#1\endinput{\egroup}
!endverbatim

\blueexample Coding the loading of the letter macros

\thisverbatim{\emc}
\beginverbatim
%From blue.tex
\def\letter{\ifx\undefined\letterfmt
   \let\letterfmt=x\fi
   \loadformat
   \let\letterfmt\undefined}
\def\loadformat{\input fmt.dat \relax}
%from fmt.dat
\tool\letterfmt
<lettermacros>
\endinput
!endverbatim

Similarly, a tool can be loaded as follows. 

\blueexample Coding the loading of the smiley macros

\thisverbatim{\emc}
\beginverbatim
%From blue.tex
\newbox\smileybox
\newcount\smileysloadcount
\def\smiley{\loadsmileys\raise.5ex
   \hbox{\unitlength.01pt
   \copy\smileybox
   \eyes\mouth
   \kern1000\unitlength} }
\def\winksmiley{<similar>}
\def\sadsmiley{<similar>}
\def\loadsmileys{\ifx\undefined\smileystool
   \let\smileystool=x\fi
   \ifnum\smileysloadcount=0 \ea\loadtool
   \else\message{--- smileys already 
                     loaded---}\fi
   \advance\smileysloadcount1
   \let\smileystool\undefined}
%from tools.dat
\tool\smileystool
<smileymacros>
\endinput
!endverbatim


Remark. 
Whenever suited a load counter is maintained such that 
dubble loading is inhibited.

\bluesubsubhead Addresses, pictures and references

The entries of these database obey the syntax
\beginverbatim
\lst\<name>{<entryproper>}
!endverbatim
The selective loading comes down to a proper definition of \cs{lst}.
Moreover, the names of the entries  to be selected must be defined
with whatever you wish as replacement text.\ftn{This approach is the opposite of 
   preventing reloading. 
   We tacitly want to redefine the fancy entries by the meaningful ones.
   My fancy replacement text is an error message.}
\beginverbatim
\def\loadselectivefrom#1{%#1 lit etc.
 \def\lst##1{\ifx##1\undefined\ea\gobble
         \else \ea\gdef\ea##1\fi}
 \input #1.dat \relax%e.g. lit.dat
 }              
\def\gobble#1{}
!endverbatim
Because of the scanning \cs{outer} defs are not allowed, nor are \cs{par}-s.
The selective loading macro is embedded in the user macros \cs{references}
and its ilks. In detail the meaning of `loading' is adapted to the application.
For references this means that the specified entries are set in a box and their names
redefined by numbers. 
The names can be used for cross-referencing purposes while the
box can be pasted up at your place of choice. 
However, the underlying searching methodology is the same for 
addresses, references and pictures.

\blueexample Coding the handling %(searching and some more) 
                of references

\beginverbatim
\def\references#1{\beginreferences#1%
   \endreferences}
\def\bluereferences#1\par
   {\beginreferences#1\endreferences}
\def\loadreferences{\loadselectivefrom
   {\the\referencesfile}}
\def\beginreferences#1\endreferences{%
  \bgroup\def\process##1{\ifx\undefined##1
     \global\let##1\referenceserror\else
     \message{***\tt\string##1 
             already loaded.***}
  \fi\namelst\ea{\the\namelst\lst##1}}%
  \fifo#1\ofif
  \if]#1]\else\ea\loadreferences\fi
  %formatting
  \ifstore\global\setbox\referencesbox=
    \vbox\bgroup\fi\prenum{}\postnum{}
  \lsams%Default ls
  \the\thisreferences
  \def\lst##1{\ls{##1}
    \xdef##1{\the\itemno}}
  \the\namelst\endreferences}
!endverbatim
Remark.
BLUe's format style of coding is centred along two-part macros with a one-part
macro on top, enriched by a convenient alias such as \cs{bluereferences}, for the
user interface.

\bluesubsubhead Max D\'\i az' \TeX nique

\TB{} {\oldstyle382}\dash{\oldstyle384}
mentions the fast loading \TeX nique of Max D\'\i az, which requires that
every line is preceded by a special character.
The process comes down to the following.
\thisverbatim{\emc}
\beginverbatim
%The TeXbook, Appendix D 4.Selective loading.
%The Max Diaz fast selective loading process.
%(A little simplified, and combined with 
% my list element tag, \lst.)
\def\lst#1{\catcode`\~=
   \ifx#1\undefined14    %comment   
              \else9 \fi}%ignore char
%We want to load the cgl part. 
\def\cgl{<anything>}

\lst\name
~a
~b
~c
\lst\cgl
~aa
~bb
~cc
\lst\erik
~aaa
~bbb
~ccc
\catcode`\~13
%
<Commonpart>
\bye
%Explanation: the list element tag toggles the 
%catcode for ~ such that either the first 
%character is ignored (and the rest of the line 
%loaded) or the line is a comment line.
!endverbatim
In the above one can replace  |\lst\name...| by 
|\input <filetobeloadedfrom>|.

\bluesubsubhead Variant document parts

The idea is that a script is marked up also with markup 
tags which have a selection/omission function.
For example an abridged version is interspersed within the script.
The idea is that the owner can either ask for an abridged or a 
full version. 
Another example is documentation with details for various computer 
operating systems.
Given a customer with a specific operating system only the
relevant parts will be printed.\ftn
{In real-life this is hardly done. 
 When I buy a TV it contains the information in several languages.}

With the new hype HTML this functionality may enjoy a second youth.

\bluehead Tree search

When I implemented trees in \TeX{} especially the Pythagorean trees\Dash to illustrate
   turtle graphics\Dash
I played a little longer with it and could use \TeX{} in `dialogue mode' to
search for a name by answering questions.

\bluesubhead Interactive path through binary tree

The following is inspired upon Greene's `Playing in \TeX's mind.'\ftn
{Courtesy Bernd Raichle for node representation.}
\beginverbatim
%Guess what? August 1995, cgl@rc.service.rug.nl
%Idea biased by A.M.Greene's 
%Playing in TeX's mind, TUG 89. 
%Interactive binary tree traversal.
%Interactive TeX ing, 
%TeX as an engine to play with.
\input blue.tex 
\def\bintree{\message{\csname\node\endcsname}
   \ea\ifx\csname\node0\endcsname\relax\eertnib\fi
   \read0to\yorn
   \edef\node{\node\if n\yorn1\else0\fi}
   \bintree}
\def\eertnib#1\bintree{\fi\def\node{1}
   \immediate\write0{Hope this is the one 
                you are looking for :-) }
   \immediate\write0{}
   \message{Another play?}
   \read0to\yorn
   \if y\yorn\ea\bintree\fi
   \immediate\write0{Thank you, bye}}
%Rules of the game
\immediate\write0{Guess game. 
 The system asks questions to be answered}
\immediate\write0{by *** y or n ***}
\immediate\write0{The following play 
              guesses an NTG member}
\immediate\write0{}
%
%Data (a tree structure)
\begingroup\obeylines
\def\lst#1 #2
   {\ea\def\csname#1\endcsname{#2}}
\lst 1 NTG member?
\lst 10 Plain TeX ie?
\lst 100 Honoured?
\lst 1000 Kees
\lst 1001 HH
\lst 101 On board?
\lst 1010 Chair?
\lst 10100 Erik
\lst 10101 Secretary?
\lst 101010 Gerard
\lst 101011 Treasurer?
\lst 1010110 Wietse
\lst 1010111 Dark?
\lst 10101110 Johannes
\lst 10101111 Frans
\lst 1011 Anonymous
\lst 11 Just a friend
%
%Start the play
\endlinechar-1 %TB20.18
\def\node{1}\bintree
\endgroup
%
%Typesetting the data
\onecol
Pretext
\thisbt{\xoffset{-400}}
\beginbt1 NTG member?
10 Plain TeX ie?
100 Honoured?
1000 cgl
1001 HH
101 On board?
1010 Chair?
10100 Erik
10101 Secretary?
101010 Gerard
101011 Treasurer?
1010110 Wietse
1010111 Dark?
10101110 JLB
10101111 FG
1011 Anonymous
11 Just a friend
8 \endbt
Posttext
\bye
!endverbatim

A typical log file looks as follows.
\beginverbatim
Guess game. The system asks questions to 
be answered by *** y or n ***
The following play guesses an NTG member

NTG member?
\yorn=y
 Plain TeX ie?
\yorn=y
 Honoured?
\yorn=y
 Kees
Hope this is the one you are looking for :-) 

Another play?
\yorn=y
 NTG member?
\yorn=n
 Just a friend
Hope this is the one you are looking for :-) 

Another play?
\yorn=y
 NTG member?
\yorn=y
 Plain TeX ie?
\yorn=n
 On board?
\yorn=y
 Chair?
\yorn=y
 Erik
Hope this is the one you are looking for :-) 

Another play?
\yorn=y
 NTG member?
\yorn=y
 Plain TeX ie?
\yorn=n
 On board?
\yorn=y
 Chair?
\yorn=n
 Secretary?
\yorn=y
 Gerard
Hope this is the one you are looking for :-) 

Another play?
\yorn=y
 NTG member?
\yorn=y
 Plain TeX ie?
\yorn=n
 On board?
\yorn=n
 Anonymous
Hope this is the one you are looking for :-) 

Another play?
\yorn=n
!endverbatim
Remarks. The first version used a counter to represent the
nodes with the restriction of $2^{16}$. 

Robustness with respect to mistypes of the user after the prompt\Dash
   the user does not supply `y' or `n'\Dash
has been treated in Paradigms: Loops.

\bluesubhead The tree

The typesetting of the binary tree
visualizes the data for your convenience.
Within BLUe's format this goes as follows
\beginverbatim
\thisbt{\xoffset{-400}}
\beginbt 1 NTG member?
10 Plain \TeX ie?
...
11 Just a friend
8 \endbt
!endverbatim
\thisbt{\xoffset{-400}}
\beginbt 1 NTG member?
10 Plain \TeX ie?
100 Honoured?
1000 cgl
1001 HH
101 On board?
1010 Chair?
10100 Erik
10101 Secretary?
101010 Gerard
101011 Treasurer?
1010110 Wietse
1010111 Dark?
10101110 JLB
10101111 FG
1011 Anonymous
11 Just a friend
8 \endbt

Have fun, and all the best 
\makesignature
\pasteuptoc
\endscript