\documentclass{article}
\usepackage{axiom}
\begin{document}
\title{\$SPAD/src/algebra string.spad}
\author{Stephen M. Watt, Michael Monagan, Manuel Bronstein}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{domain CHAR Character}
<<domain CHAR Character>>=
)abbrev domain CHAR Character
++ Author: Stephen M. Watt
++ Date Created: July 1986
++ Date Last Updated: June 20, 1991
++ Basic Operations: char
++ Related Domains:
++ Also See:
++ AMS Classifications:
++ Keywords: character, string
++ Examples:
++ References:
++ Description:
++   This domain provides the basic character data type.

Character: OrderedFinite() with
	ord: % -> NonNegativeInteger
	    ++ ord(c) provides an integral code corresponding to the
	    ++ character c.  It is always true that \spad{char ord c = c}.
	char: NonNegativeInteger  -> %
	    ++ char(i) provides a character corresponding to the integer
	    ++ code i.	It is always true that \spad{ord char i = i}.
	char: String   -> %
	    ++ char(s) provides a character from a string s of length one.
	space:	() -> %
	    ++ space() provides the blank character.
	quote:	() -> %
	    ++ quote() provides the string quote character, \spad{"}.
	escape: () -> %
	    ++ escape() provides the escape character, \spad{_}, which
	    ++ is used to allow quotes and other characters {\em within}
	    ++ strings.
	upperCase: % -> %
	    ++ upperCase(c) converts a lower case letter to the corresponding
	    ++ upper case letter.  If c is not a lower case letter, then
	    ++ it is returned unchanged.
	lowerCase: % -> %
	    ++ lowerCase(c) converts an upper case letter to the corresponding
	    ++ lower case letter.  If c is not an upper case letter, then
	    ++ it is returned unchanged.
	digit?: % -> Boolean
	    ++ digit?(c) tests if c is a digit character,
	    ++ i.e. one of 0..9.
	hexDigit?: % -> Boolean
	    ++ hexDigit?(c) tests if c is a hexadecimal numeral,
	    ++ i.e. one of 0..9, a..f or A..F.
	alphabetic?: % -> Boolean
	    ++ alphabetic?(c) tests if c is a letter,
	    ++ i.e. one of a..z or A..Z.
	upperCase?: % -> Boolean
	    ++ upperCase?(c) tests if c is an upper case letter,
	    ++ i.e. one of A..Z.
	lowerCase?: % -> Boolean
	    ++ lowerCase?(c) tests if c is an lower case letter,
	    ++ i.e. one of a..z.
	alphanumeric?: % -> Boolean
	    ++ alphanumeric?(c) tests if c is either a letter or number,
	    ++ i.e. one of 0..9, a..z or A..Z.

    == add
        -- We use the base Lisp's system base-char as a
        -- the representation for this class.
	CC ==> CharacterClass()
        NNI ==> NonNegativeInteger
	import CC

	--cl: Record(dig:CC,hex:CC,upp:CC,low:CC,alpha:CC,alnum:CC) :=
	--    [ digit(), hexDigit(),
	--	upperCase(), lowerCase(), alphabetic(), alphanumeric() ]

	a = b		       == CHAR_=(a,b)$Lisp
	a < b		       == CHAR_<(a,b)$Lisp
	size()		       == 256
	index n		       == char((n - 1)::NNI)
	lookup c	       == (1 + ord c)::PositiveInteger
	char(n: NNI)	       == CODE_-CHAR(n)$Lisp
	ord c		       == CHAR_-CODE(c)$Lisp
	random()	       == char(random(size())$NNI)
	space		       == CHAR("   ", 0$Lisp)$Lisp
	quote		       == CHAR("_" ", 0$Lisp)$Lisp
	escape		       == CHAR("__ ", 0$Lisp)$Lisp
	coerce(c:%):OutputForm == c : OutputForm
	digit? c	       == member?(c, digit())
	hexDigit? c	       == member?(c, hexDigit())
	upperCase? c	       == member?(c, upperCase())
	lowerCase? c	       == member?(c, lowerCase())
	alphabetic? c	       == member?(c, alphabetic())
	alphanumeric? c	       == member?(c, alphanumeric())

	latex c ==
	  concat("\mbox{`", concat(new(1,c)$String, "'}")$String)$String

	char(s:String) ==
--	  one?(#s) => s(minIndex s)
	  (#s) = 1 => s(minIndex s)
	  userError "String is not a single character"

	upperCase c ==
	  CHAR_-UPCASE(c)$Lisp : %

	lowerCase c ==
	  CHAR_-DOWNCASE(c)$Lisp : %

@
\section{CHAR.lsp BOOTSTRAP} 
{\bf CHAR} depends on a chain of
files. We need to break this cycle to build the algebra. So we keep a
cached copy of the translated {\bf CHAR} category which we can write
into the {\bf MID} directory. We compile the lisp code and copy the
{\bf CHAR.o} file to the {\bf OUT} directory.  This is eventually
forcibly replaced by a recompiled version.

Note that this code is not included in the generated catdef.spad file.

<<CHAR.lsp BOOTSTRAP>>=

(/VERSIONCHECK 2) 

(PUT '|CHAR;=;2$B;1| '|SPADreplace| 'CHAR=) 

(DEFUN |CHAR;=;2$B;1| (|a| |b| $) (CHAR= |a| |b|)) 

(PUT '|CHAR;<;2$B;2| '|SPADreplace| 'CHAR<) 

(DEFUN |CHAR;<;2$B;2| (|a| |b| $) (CHAR< |a| |b|)) 

(PUT '|CHAR;size;Nni;3| '|SPADreplace| '(XLAM NIL 256)) 

(DEFUN |CHAR;size;Nni;3| ($) 256) 

(DEFUN |CHAR;index;Pi$;4| (|n| $)
  (PROG (#0=#:G1389)
    (RETURN
      (SPADCALL
          (PROG1 (LETT #0# (- |n| 1) |CHAR;index;Pi$;4|)
            (|check-subtype| (>= #0# 0) '(|NonNegativeInteger|) #0#))
          (QREFELT $ 11))))) 

(DEFUN |CHAR;lookup;$Pi;5| (|c| $)
  (PROG (#0=#:G1391)
    (RETURN
      (PROG1 (LETT #0# (+ 1 (SPADCALL |c| (QREFELT $ 14)))
                   |CHAR;lookup;$Pi;5|)
        (|check-subtype| (> #0# 0) '(|PositiveInteger|) #0#))))) 

(PUT '|CHAR;char;Nni$;6| '|SPADreplace| 'CODE-CHAR) 

(DEFUN |CHAR;char;Nni$;6| (|n| $) (CODE-CHAR |n|)) 

(PUT '|CHAR;ord;$Nni;7| '|SPADreplace| 'CHAR-CODE) 

(DEFUN |CHAR;ord;$Nni;7| (|c| $) (CHAR-CODE |c|)) 

(DEFUN |CHAR;random;$;8| ($)
  (SPADCALL (RANDOM (SPADCALL (QREFELT $ 10))) (QREFELT $ 11))) 

(PUT '|CHAR;space;$;9| '|SPADreplace| '(XLAM NIL (CHAR "   " 0))) 

(DEFUN |CHAR;space;$;9| ($) (CHAR "   " 0)) 

(PUT '|CHAR;quote;$;10| '|SPADreplace| '(XLAM NIL (CHAR "\" " 0))) 

(DEFUN |CHAR;quote;$;10| ($) (CHAR "\" " 0)) 

(PUT '|CHAR;escape;$;11| '|SPADreplace| '(XLAM NIL (CHAR "_ " 0))) 

(DEFUN |CHAR;escape;$;11| ($) (CHAR "_ " 0)) 

(PUT '|CHAR;coerce;$Of;12| '|SPADreplace| '(XLAM (|c|) |c|)) 

(DEFUN |CHAR;coerce;$Of;12| (|c| $) |c|) 

(DEFUN |CHAR;digit?;$B;13| (|c| $)
  (SPADCALL |c| (|spadConstant| $ 23) (QREFELT $ 25))) 

(DEFUN |CHAR;hexDigit?;$B;14| (|c| $)
  (SPADCALL |c| (|spadConstant| $ 27) (QREFELT $ 25))) 

(DEFUN |CHAR;upperCase?;$B;15| (|c| $)
  (SPADCALL |c| (|spadConstant| $ 29) (QREFELT $ 25))) 

(DEFUN |CHAR;lowerCase?;$B;16| (|c| $)
  (SPADCALL |c| (|spadConstant| $ 31) (QREFELT $ 25))) 

(DEFUN |CHAR;alphabetic?;$B;17| (|c| $)
  (SPADCALL |c| (|spadConstant| $ 33) (QREFELT $ 25))) 

(DEFUN |CHAR;alphanumeric?;$B;18| (|c| $)
  (SPADCALL |c| (|spadConstant| $ 35) (QREFELT $ 25))) 

(DEFUN |CHAR;latex;$S;19| (|c| $)
  (STRCONC "\\mbox{`" (STRCONC (MAKE-FULL-CVEC 1 |c|) "'}"))) 

(DEFUN |CHAR;char;S$;20| (|s| $)
  (COND
    ((EQL (QCSIZE |s|) 1)
     (SPADCALL |s| (SPADCALL |s| (QREFELT $ 40)) (QREFELT $ 41)))
    ('T (|userError| "String is not a single character")))) 

(PUT '|CHAR;upperCase;2$;21| '|SPADreplace| 'CHAR-UPCASE) 

(DEFUN |CHAR;upperCase;2$;21| (|c| $) (CHAR-UPCASE |c|)) 

(PUT '|CHAR;lowerCase;2$;22| '|SPADreplace| 'CHAR-DOWNCASE) 

(DEFUN |CHAR;lowerCase;2$;22| (|c| $) (CHAR-DOWNCASE |c|)) 

(DEFUN |Character| ()
  (PROG ()
    (RETURN
      (PROG (#0=#:G1412)
        (RETURN
          (COND
            ((LETT #0# (HGET |$ConstructorCache| '|Character|)
                   |Character|)
             (|CDRwithIncrement| (CDAR #0#)))
            ('T
             (UNWIND-PROTECT
               (PROG1 (CDDAR (HPUT |$ConstructorCache| '|Character|
                                   (LIST
                                    (CONS NIL (CONS 1 (|Character;|))))))
                 (LETT #0# T |Character|))
               (COND
                 ((NOT #0#) (HREM |$ConstructorCache| '|Character|))))))))))) 

(DEFUN |Character;| ()
  (PROG (|dv$| $ |pv$|)
    (RETURN
      (PROGN
        (LETT |dv$| '(|Character|) . #0=(|Character|))
        (LETT $ (|newShell| 46) . #0#)
        (QSETREFV $ 0 |dv$|)
        (QSETREFV $ 3 (LETT |pv$| (|buildPredVector| 0 0 NIL) . #0#))
        (|haddProp| |$ConstructorCache| '|Character| NIL (CONS 1 $))
        (|stuffDomainSlots| $)
        $)))) 

(MAKEPROP '|Character| '|infovec|
    (LIST '#(NIL NIL NIL NIL NIL NIL (|Boolean|) |CHAR;=;2$B;1|
             |CHAR;<;2$B;2| (|NonNegativeInteger|) |CHAR;size;Nni;3|
             |CHAR;char;Nni$;6| (|PositiveInteger|) |CHAR;index;Pi$;4|
             |CHAR;ord;$Nni;7| |CHAR;lookup;$Pi;5| |CHAR;random;$;8|
             |CHAR;space;$;9| |CHAR;quote;$;10| |CHAR;escape;$;11|
             (|OutputForm|) |CHAR;coerce;$Of;12| (|CharacterClass|)
             (0 . |digit|) (|Character|) (4 . |member?|)
             |CHAR;digit?;$B;13| (10 . |hexDigit|)
             |CHAR;hexDigit?;$B;14| (14 . |upperCase|)
             |CHAR;upperCase?;$B;15| (18 . |lowerCase|)
             |CHAR;lowerCase?;$B;16| (22 . |alphabetic|)
             |CHAR;alphabetic?;$B;17| (26 . |alphanumeric|)
             |CHAR;alphanumeric?;$B;18| (|String|) |CHAR;latex;$S;19|
             (|Integer|) (30 . |minIndex|) (35 . |elt|)
             |CHAR;char;S$;20| |CHAR;upperCase;2$;21|
             |CHAR;lowerCase;2$;22| (|SingleInteger|))
          '#(~= 41 |upperCase?| 47 |upperCase| 52 |space| 57 |size| 61
             |random| 65 |quote| 69 |ord| 73 |min| 78 |max| 84
             |lowerCase?| 90 |lowerCase| 95 |lookup| 100 |latex| 105
             |index| 110 |hexDigit?| 115 |hash| 120 |escape| 125
             |digit?| 129 |coerce| 134 |char| 139 |alphanumeric?| 149
             |alphabetic?| 154 >= 159 > 165 = 171 <= 177 < 183)
          'NIL
          (CONS (|makeByteWordVec2| 1 '(0 0 0 0 0 0))
                (CONS '#(NIL |OrderedSet&| NIL |SetCategory&|
                         |BasicType&| NIL)
                      (CONS '#((|OrderedFinite|) (|OrderedSet|)
                               (|Finite|) (|SetCategory|) (|BasicType|)
                               (|CoercibleTo| 20))
                            (|makeByteWordVec2| 45
                                '(0 22 0 23 2 22 6 24 0 25 0 22 0 27 0
                                  22 0 29 0 22 0 31 0 22 0 33 0 22 0 35
                                  1 37 39 0 40 2 37 24 0 39 41 2 0 6 0
                                  0 1 1 0 6 0 30 1 0 0 0 43 0 0 0 17 0
                                  0 9 10 0 0 0 16 0 0 0 18 1 0 9 0 14 2
                                  0 0 0 0 1 2 0 0 0 0 1 1 0 6 0 32 1 0
                                  0 0 44 1 0 12 0 15 1 0 37 0 38 1 0 0
                                  12 13 1 0 6 0 28 1 0 45 0 1 0 0 0 19
                                  1 0 6 0 26 1 0 20 0 21 1 0 0 37 42 1
                                  0 0 9 11 1 0 6 0 36 1 0 6 0 34 2 0 6
                                  0 0 1 2 0 6 0 0 1 2 0 6 0 0 7 2 0 6 0
                                  0 1 2 0 6 0 0 8)))))
          '|lookupComplete|)) 

(MAKEPROP '|Character| 'NILADIC T) 
@
\section{domain CCLASS CharacterClass}
<<domain CCLASS CharacterClass>>=
)abbrev domain CCLASS CharacterClass
++ Author: Stephen M. Watt
++ Date Created: July 1986
++ Date Last Updated: June 20, 1991
++ Basic Operations: charClass
++ Related Domains: Character, Bits
++ Also See:
++ AMS Classifications:
++ Keywords:
++ Examples:
++ References:
++ Description:
++   This domain allows classes of characters to be defined and manipulated
++   efficiently.


CharacterClass: Join(SetCategory, ConvertibleTo String,
  FiniteSetAggregate Character, ConvertibleTo List Character) with
	charClass: String -> %
	    ++ charClass(s) creates a character class which contains
	    ++ exactly the characters given in the string s.
	charClass: List Character -> %
	    ++ charClass(l) creates a character class which contains
	    ++ exactly the characters given in the list l.
	digit:	constant -> %
	    ++ digit() returns the class of all characters
	    ++ for which \spadfunFrom{digit?}{Character} is true.
	hexDigit: constant -> %
	    ++ hexDigit() returns the class of all characters for which
	    ++ \spadfunFrom{hexDigit?}{Character} is true.
	upperCase: constant -> %
	    ++ upperCase() returns the class of all characters for which
	    ++ \spadfunFrom{upperCase?}{Character} is true.
	lowerCase:  constant -> %
	    ++ lowerCase() returns the class of all characters for which
	    ++ \spadfunFrom{lowerCase?}{Character} is true.
	alphabetic  :  constant -> %
	    ++ alphabetic() returns the class of all characters for which
	    ++ \spadfunFrom{alphabetic?}{Character} is true.
	alphanumeric:  constant -> %
	    ++ alphanumeric() returns the class of all characters for which
	    ++ \spadfunFrom{alphanumeric?}{Character} is true.

    == add
	Rep := IndexedBits(0)
	N   := size()$Character

	a, b: %

	digit()		== charClass "0123456789"
	hexDigit()	== charClass "0123456789abcdefABCDEF"
	upperCase()	== charClass "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
	lowerCase()	== charClass "abcdefghijklmnopqrstuvwxyz"
	alphabetic()	== union(upperCase(), lowerCase())
	alphanumeric()	== union(alphabetic(), digit())

	a = b		== a =$Rep b

	member?(c, a)	== a(ord c)
	union(a,b)	== Or(a, b)
	intersect (a,b) == And(a, b)
	difference(a,b) == And(a, Not b)
	complement a	== Not a

	convert(cl):String ==
	  construct(convert(cl)@List(Character))
	convert(cl:%):List(Character) ==
	  [char(i) for i in 0..N-1 | cl.i]

	charClass(s: String) ==
	  cl := new(N, false)
	  for i in minIndex(s)..maxIndex(s) repeat cl(ord s.i) := true
	  cl

	charClass(l: List Character) ==
	  cl := new(N, false)
	  for c in l repeat cl(ord c) := true
	  cl

	coerce(cl):OutputForm == (convert(cl)@String)::OutputForm

	-- Stuff to make a legal SetAggregate view
	# a		== (n := 0; for i in 0..N-1 | a.i repeat n := n+1; n)
	empty():%	== charClass []
	brace():%	== charClass []

	insert_!(c, a)	== (a(ord c) := true; a)
	remove_!(c, a)	== (a(ord c) := false; a)

	inspect(a) ==
	    for i in 0..N-1 | a.i repeat
		 return char i
	    error "Cannot take a character from an empty class."
	extract_!(a) ==
	    for i in 0..N-1 | a.i repeat
		 a.i := false
		 return char i
	    error "Cannot take a character from an empty class."

	map(f, a) ==
	    b := new(N, false)
	    for i in 0..N-1 | a.i repeat b(ord f char i) := true
	    b

	temp: % := new(N, false)$Rep
	map_!(f, a) ==
	    fill_!(temp, false)
	    for i in 0..N-1 | a.i repeat temp(ord f char i) := true
	    copyInto_!(a, temp, 0)

	parts a ==
	    [char i for i in 0..N-1 | a.i]

@
\section{domain ISTRING IndexedString}
<<domain ISTRING IndexedString>>=
)abbrev domain ISTRING IndexedString
++ Authors: Stephen Watt, Michael Monagan, Manuel Bronstein 1986 .. 1991
-- The following Lisp dependencies are divided into two groups
-- Those that are required
-- QENUM QESET QCSIZE MAKE-FULL-CVEC EQ QSLESSP QSGREATERP
-- Those that can are included for efficiency only
-- COPY STRCONC SUBSTRING STRPOS RPLACSTR DOWNCASE UPCASE CGREATERP
++ Description:
++ This domain implements low-level strings

IndexedString(mn:Integer): Export == Implementation where
  B ==> Boolean
  C ==> Character
  I ==> Integer
  N ==> NonNegativeInteger
  U ==> UniversalSegment Integer

  Export ==> StringAggregate() with
      hash: % -> I
	++ hash(x) provides a hashing function for strings

  Implementation ==> add
    -- These assume Character's Rep is Small I
    Qelt    ==> CHAR$Lisp
    Qequal  ==> EQUAL$Lisp
    Qsetelt ==> QESET$Lisp
    Qsize   ==> QCSIZE$Lisp
    Cheq    ==> CHAR_=$Lisp

    c:	Character
    cc: CharacterClass

--  new n		   == MAKE_-FULL_-CVEC(n, space$C)$Lisp
    new(n, c)		   == MAKE_-FULL_-CVEC(n, c)$Lisp
    empty()		   == MAKE_-FULL_-CVEC(0$Lisp)$Lisp
    empty?(s)		   == Qsize(s) = 0
    #s			   == Qsize(s)
    s = t		   == Qequal(s, t)
    s < t		   == CGREATERP(t,s)$Lisp
    concat(s:%,t:%)	   == STRCONC(s,t)$Lisp
    copy s		   == COPY_-SEQ(s)$Lisp
    insert(s:%, t:%, i:I)  == concat(concat(s(mn..i-1), t), s(i..))
    coerce(s:%):OutputForm == outputForm(s pretend String)
    minIndex s		   == mn
    upperCase_! s	   == map_!(upperCase, s)
    lowerCase_! s	   == map_!(lowerCase, s)

    latex s		   == concat("\mbox{``", concat(s pretend String, "''}"))

    replace(s, sg, t) ==
	l := lo(sg) - mn
	m := #s
	n := #t
	h:I := if hasHi sg then hi(sg) - mn else maxIndex s - mn
	l < 0 or h >= m or h < l-1 => error "index out of range"
	r := new((m-(h-l+1)+n)::N, space$C)
	for k in 0.. for i in 0..l-1 repeat Qsetelt(r, k, Qelt(s, i))
	for k in k.. for i in 0..n-1 repeat Qsetelt(r, k, Qelt(t, i))
	for k in k.. for i in h+1..m-1 repeat Qsetelt(r, k, Qelt(s, i))
	r

    setelt(s:%, i:I, c:C) ==
	i < mn or i > maxIndex(s) => error "index out of range"
	Qsetelt(s, i - mn, c)
	c

    substring?(part, whole, startpos) ==
	np:I := Qsize part
	nw:I := Qsize whole
	(startpos := startpos - mn) < 0 => error "index out of bounds"
	np > nw - startpos => false
	for ip in 0..np-1 for iw in startpos.. repeat
	    not Cheq(Qelt(part, ip), Qelt(whole, iw)) => return false
	true

    position(s:%, t:%, startpos:I) ==
	(startpos := startpos - mn) < 0 => error "index out of bounds"
	startpos >= Qsize t => mn - 1
	r:I := STRPOS(s, t, startpos, NIL$Lisp)$Lisp
	EQ(r, NIL$Lisp)$Lisp => mn - 1
	r + mn
    position(c: Character, t: %, startpos: I) ==
	(startpos := startpos - mn) < 0 => error "index out of bounds"
	startpos >= Qsize t => mn - 1
	for r in startpos..Qsize t - 1 repeat
	    if Cheq(Qelt(t, r), c) then return r + mn
	mn - 1
    position(cc: CharacterClass, t: %, startpos: I) ==
	(startpos := startpos - mn) < 0 => error "index out of bounds"
	startpos >= Qsize t => mn - 1
	for r in startpos..Qsize t - 1 repeat
	    if member?(Qelt(t,r), cc) then return r + mn
	mn - 1

    suffix?(s, t) ==
	(m := maxIndex s) > (n := maxIndex t) => false
	substring?(s, t, mn + n - m)

    split(s, c) ==
	n := maxIndex s
	for i in mn..n while s.i = c repeat 0
	l := empty()$List(%)
	j:Integer -- j is conditionally intialized
	while i <= n and (j := position(c, s, i)) >= mn repeat
	    l := concat(s(i..j-1), l)
	    for i in j..n while s.i = c repeat 0
	if i <= n then l := concat(s(i..n), l)
	reverse_! l
    split(s, cc) ==
	n := maxIndex s
	for i in mn..n while member?(s.i,cc) repeat 0
	l := empty()$List(%)
	j:Integer -- j is conditionally intialized
	while i <= n and (j := position(cc, s, i)) >= mn repeat
	    l := concat(s(i..j-1), l)
	    for i in j..n while member?(s.i,cc) repeat 0
	if i <= n then l := concat(s(i..n), l)
	reverse_! l

    leftTrim(s, c) ==
	n := maxIndex s
	for i in mn .. n while s.i = c repeat 0
	s(i..n)
    leftTrim(s, cc) ==
	n := maxIndex s
	for i in mn .. n while member?(s.i,cc) repeat 0
	s(i..n)

    rightTrim(s, c) ==
	for j in maxIndex s .. mn by -1 while s.j = c repeat 0
	s(minIndex(s)..j)
    rightTrim(s, cc) ==
	for j in maxIndex s .. mn by -1 while member?(s.j, cc) repeat 0
	s(minIndex(s)..j)

    concat l ==
	t := new(+/[#s for s in l], space$C)
	i := mn
	for s in l repeat
	    copyInto_!(t, s, i)
	    i := i + #s
	t

    copyInto_!(y, x, s) ==
	m := #x
	n := #y
	s := s - mn
	s < 0 or s+m > n => error "index out of range"
	RPLACSTR(y, s, m, x, 0, m)$Lisp
	y

    elt(s:%, i:I) ==
	i < mn or i > maxIndex(s) => error "index out of range"
	Qelt(s, i - mn)

    elt(s:%, sg:U) ==
	l := lo(sg) - mn
	h := if hasHi sg then hi(sg) - mn else maxIndex s - mn
	l < 0 or h >= #s => error "index out of bound"
	SUBSTRING(s, l, max(0, h-l+1))$Lisp

    hash(s:$):Integer ==
	n:I := Qsize s
	zero? n => 0
--	one? n => ord(s.mn)
	(n = 1) => ord(s.mn)
	ord(s.mn) * ord s(mn+n-1) * ord s(mn + n quo 2)

    match(pattern,target,wildcard) == stringMatch(pattern,target,CHARACTER(wildcard)$Lisp)$Lisp
 
@

Up to [[patch--40]] this read

\begin{verbatim}
    match(pattern,target,wildcard) == stringMatch(pattern,target,wildcard)$Lisp
\end{verbatim}

which did not work (Issue~\#97), since [[wildcard]] is an Axiom-[[Character]],
not a Lisp-[[Character]]. The operation [[CHARACTER]] from [[Lisp]] performs
the coercion.

<<domain ISTRING IndexedString>>=
    match?(pattern, target, dontcare) ==
	n := maxIndex pattern
	p := position(dontcare, pattern, m := minIndex pattern)::N
	p = m-1 => pattern = target
	(p ^= m) and not prefix?(pattern(m..p-1), target) => false
	i := p	-- index into target
	q := position(dontcare, pattern, p + 1)::N
	while q ^= m-1 repeat
	   s := pattern(p+1..q-1)
	   i := position(s, target, i)::N
	   i = m-1 => return false
	   i := i + #s
	   p := q
	   q := position(dontcare, pattern, q + 1)::N
	(p ^= n) and not suffix?(pattern(p+1..n), target) => false
	true

@
\section{ISTRING.lsp BOOTSTRAP} 
{\bf ISTRING} depends on a chain of
files. We need to break this cycle to build the algebra. So we keep a
cached copy of the translated {\bf ISTRING} category which we can write
into the {\bf MID} directory. We compile the lisp code and copy the
{\bf ISTRING.o} file to the {\bf OUT} directory.  This is eventually
forcibly replaced by a recompiled version.

Note that this code is not included in the generated catdef.spad file.

<<ISTRING.lsp BOOTSTRAP>>=

(/VERSIONCHECK 2) 

(PUT '|ISTRING;new;NniC$;1| '|SPADreplace| 'MAKE-FULL-CVEC) 

(DEFUN |ISTRING;new;NniC$;1| (|n| |c| $) (MAKE-FULL-CVEC |n| |c|)) 

(PUT '|ISTRING;empty;$;2| '|SPADreplace|
     '(XLAM NIL (MAKE-FULL-CVEC 0))) 

(DEFUN |ISTRING;empty;$;2| ($) (MAKE-FULL-CVEC 0)) 

(DEFUN |ISTRING;empty?;$B;3| (|s| $) (EQL (QCSIZE |s|) 0)) 

(PUT '|ISTRING;#;$Nni;4| '|SPADreplace| 'QCSIZE) 

(DEFUN |ISTRING;#;$Nni;4| (|s| $) (QCSIZE |s|)) 

(PUT '|ISTRING;=;2$B;5| '|SPADreplace| 'EQUAL) 

(DEFUN |ISTRING;=;2$B;5| (|s| |t| $) (EQUAL |s| |t|)) 

(PUT '|ISTRING;<;2$B;6| '|SPADreplace|
     '(XLAM (|s| |t|) (CGREATERP |t| |s|))) 

(DEFUN |ISTRING;<;2$B;6| (|s| |t| $) (CGREATERP |t| |s|)) 

(PUT '|ISTRING;concat;3$;7| '|SPADreplace| 'STRCONC) 

(DEFUN |ISTRING;concat;3$;7| (|s| |t| $) (STRCONC |s| |t|)) 

(PUT '|ISTRING;copy;2$;8| '|SPADreplace| 'COPY-SEQ) 

(DEFUN |ISTRING;copy;2$;8| (|s| $) (COPY-SEQ |s|)) 

(DEFUN |ISTRING;insert;2$I$;9| (|s| |t| |i| $)
  (SPADCALL
      (SPADCALL
          (SPADCALL |s|
              (SPADCALL (QREFELT $ 6) (- |i| 1) (QREFELT $ 20))
              (QREFELT $ 21))
          |t| (QREFELT $ 16))
      (SPADCALL |s| (SPADCALL |i| (QREFELT $ 22)) (QREFELT $ 21))
      (QREFELT $ 16))) 

(DEFUN |ISTRING;coerce;$Of;10| (|s| $) (SPADCALL |s| (QREFELT $ 26))) 

(DEFUN |ISTRING;minIndex;$I;11| (|s| $) (QREFELT $ 6)) 

(DEFUN |ISTRING;upperCase!;2$;12| (|s| $)
  (SPADCALL (ELT $ 31) |s| (QREFELT $ 33))) 

(DEFUN |ISTRING;lowerCase!;2$;13| (|s| $)
  (SPADCALL (ELT $ 36) |s| (QREFELT $ 33))) 

(DEFUN |ISTRING;latex;$S;14| (|s| $)
  (STRCONC "\\mbox{``" (STRCONC |s| "''}"))) 

(DEFUN |ISTRING;replace;$Us2$;15| (|s| |sg| |t| $)
  (PROG (|l| |m| |n| |h| #0=#:G1770 |r| #1=#:G1776 #2=#:G1777 |i|
             #3=#:G1778 |k|)
    (RETURN
      (SEQ (LETT |l| (- (SPADCALL |sg| (QREFELT $ 39)) (QREFELT $ 6))
                 |ISTRING;replace;$Us2$;15|)
           (LETT |m| (SPADCALL |s| (QREFELT $ 13))
                 |ISTRING;replace;$Us2$;15|)
           (LETT |n| (SPADCALL |t| (QREFELT $ 13))
                 |ISTRING;replace;$Us2$;15|)
           (LETT |h|
                 (COND
                   ((SPADCALL |sg| (QREFELT $ 40))
                    (- (SPADCALL |sg| (QREFELT $ 41)) (QREFELT $ 6)))
                   ('T (- (SPADCALL |s| (QREFELT $ 42)) (QREFELT $ 6))))
                 |ISTRING;replace;$Us2$;15|)
           (COND
             ((OR (OR (< |l| 0) (NULL (< |h| |m|))) (< |h| (- |l| 1)))
              (EXIT (|error| "index out of range"))))
           (LETT |r|
                 (SPADCALL
                     (PROG1 (LETT #0# (+ (- |m| (+ (- |h| |l|) 1)) |n|)
                                  |ISTRING;replace;$Us2$;15|)
                       (|check-subtype| (>= #0# 0)
                           '(|NonNegativeInteger|) #0#))
                     (SPADCALL (QREFELT $ 43)) (QREFELT $ 9))
                 |ISTRING;replace;$Us2$;15|)
           (SEQ (LETT |i| 0 |ISTRING;replace;$Us2$;15|)
                (LETT #1# (- |l| 1) |ISTRING;replace;$Us2$;15|)
                (LETT |k| 0 |ISTRING;replace;$Us2$;15|) G190
                (COND ((QSGREATERP |i| #1#) (GO G191)))
                (SEQ (EXIT (QESET |r| |k| (CHAR |s| |i|))))
                (LETT |k|
                      (PROG1 (QSADD1 |k|)
                        (LETT |i| (QSADD1 |i|)
                              |ISTRING;replace;$Us2$;15|))
                      |ISTRING;replace;$Us2$;15|)
                (GO G190) G191 (EXIT NIL))
           (SEQ (LETT |i| 0 |ISTRING;replace;$Us2$;15|)
                (LETT #2# (- |n| 1) |ISTRING;replace;$Us2$;15|)
                (LETT |k| |k| |ISTRING;replace;$Us2$;15|) G190
                (COND ((QSGREATERP |i| #2#) (GO G191)))
                (SEQ (EXIT (QESET |r| |k| (CHAR |t| |i|))))
                (LETT |k|
                      (PROG1 (+ |k| 1)
                        (LETT |i| (QSADD1 |i|)
                              |ISTRING;replace;$Us2$;15|))
                      |ISTRING;replace;$Us2$;15|)
                (GO G190) G191 (EXIT NIL))
           (SEQ (LETT |i| (+ |h| 1) |ISTRING;replace;$Us2$;15|)
                (LETT #3# (- |m| 1) |ISTRING;replace;$Us2$;15|)
                (LETT |k| |k| |ISTRING;replace;$Us2$;15|) G190
                (COND ((> |i| #3#) (GO G191)))
                (SEQ (EXIT (QESET |r| |k| (CHAR |s| |i|))))
                (LETT |k|
                      (PROG1 (+ |k| 1)
                        (LETT |i| (+ |i| 1) |ISTRING;replace;$Us2$;15|))
                      |ISTRING;replace;$Us2$;15|)
                (GO G190) G191 (EXIT NIL))
           (EXIT |r|))))) 

(DEFUN |ISTRING;setelt;$I2C;16| (|s| |i| |c| $)
  (SEQ (COND
         ((OR (< |i| (QREFELT $ 6))
              (< (SPADCALL |s| (QREFELT $ 42)) |i|))
          (|error| "index out of range"))
         ('T (SEQ (QESET |s| (- |i| (QREFELT $ 6)) |c|) (EXIT |c|)))))) 

(DEFUN |ISTRING;substring?;2$IB;17| (|part| |whole| |startpos| $)
  (PROG (|np| |nw| |iw| |ip| #0=#:G1788 #1=#:G1787 #2=#:G1783)
    (RETURN
      (SEQ (EXIT (SEQ (LETT |np| (QCSIZE |part|)
                            |ISTRING;substring?;2$IB;17|)
                      (LETT |nw| (QCSIZE |whole|)
                            |ISTRING;substring?;2$IB;17|)
                      (LETT |startpos| (- |startpos| (QREFELT $ 6))
                            |ISTRING;substring?;2$IB;17|)
                      (EXIT (COND
                              ((< |startpos| 0)
                               (|error| "index out of bounds"))
                              ((< (- |nw| |startpos|) |np|) 'NIL)
                              ('T
                               (SEQ (SEQ
                                     (EXIT
                                      (SEQ
                                       (LETT |iw| |startpos|
                                        |ISTRING;substring?;2$IB;17|)
                                       (LETT |ip| 0
                                        |ISTRING;substring?;2$IB;17|)
                                       (LETT #0# (- |np| 1)
                                        |ISTRING;substring?;2$IB;17|)
                                       G190
                                       (COND
                                         ((QSGREATERP |ip| #0#)
                                          (GO G191)))
                                       (SEQ
                                        (EXIT
                                         (COND
                                           ((NULL
                                             (CHAR= (CHAR |part| |ip|)
                                              (CHAR |whole| |iw|)))
                                            (PROGN
                                              (LETT #2#
                                               (PROGN
                                                 (LETT #1# 'NIL
                                                  |ISTRING;substring?;2$IB;17|)
                                                 (GO #1#))
                                               |ISTRING;substring?;2$IB;17|)
                                              (GO #2#))))))
                                       (LETT |ip|
                                        (PROG1 (QSADD1 |ip|)
                                          (LETT |iw| (+ |iw| 1)
                                           |ISTRING;substring?;2$IB;17|))
                                        |ISTRING;substring?;2$IB;17|)
                                       (GO G190) G191 (EXIT NIL)))
                                     #2# (EXIT #2#))
                                    (EXIT 'T)))))))
           #1# (EXIT #1#))))) 

(DEFUN |ISTRING;position;2$2I;18| (|s| |t| |startpos| $)
  (PROG (|r|)
    (RETURN
      (SEQ (LETT |startpos| (- |startpos| (QREFELT $ 6))
                 |ISTRING;position;2$2I;18|)
           (EXIT (COND
                   ((< |startpos| 0) (|error| "index out of bounds"))
                   ((NULL (< |startpos| (QCSIZE |t|)))
                    (- (QREFELT $ 6) 1))
                   ('T
                    (SEQ (LETT |r| (STRPOS |s| |t| |startpos| NIL)
                               |ISTRING;position;2$2I;18|)
                         (EXIT (COND
                                 ((EQ |r| NIL) (- (QREFELT $ 6) 1))
                                 ('T (+ |r| (QREFELT $ 6))))))))))))) 

(DEFUN |ISTRING;position;C$2I;19| (|c| |t| |startpos| $)
  (PROG (|r| #0=#:G1799 #1=#:G1798)
    (RETURN
      (SEQ (EXIT (SEQ (LETT |startpos| (- |startpos| (QREFELT $ 6))
                            |ISTRING;position;C$2I;19|)
                      (EXIT (COND
                              ((< |startpos| 0)
                               (|error| "index out of bounds"))
                              ((NULL (< |startpos| (QCSIZE |t|)))
                               (- (QREFELT $ 6) 1))
                              ('T
                               (SEQ (SEQ
                                     (LETT |r| |startpos|
                                      |ISTRING;position;C$2I;19|)
                                     (LETT #0#
                                      (QSDIFFERENCE (QCSIZE |t|) 1)
                                      |ISTRING;position;C$2I;19|)
                                     G190
                                     (COND ((> |r| #0#) (GO G191)))
                                     (SEQ
                                      (EXIT
                                       (COND
                                         ((CHAR= (CHAR |t| |r|) |c|)
                                          (PROGN
                                            (LETT #1#
                                             (+ |r| (QREFELT $ 6))
                                             |ISTRING;position;C$2I;19|)
                                            (GO #1#))))))
                                     (LETT |r| (+ |r| 1)
                                      |ISTRING;position;C$2I;19|)
                                     (GO G190) G191 (EXIT NIL))
                                    (EXIT (- (QREFELT $ 6) 1))))))))
           #1# (EXIT #1#))))) 

(DEFUN |ISTRING;position;Cc$2I;20| (|cc| |t| |startpos| $)
  (PROG (|r| #0=#:G1806 #1=#:G1805)
    (RETURN
      (SEQ (EXIT (SEQ (LETT |startpos| (- |startpos| (QREFELT $ 6))
                            |ISTRING;position;Cc$2I;20|)
                      (EXIT (COND
                              ((< |startpos| 0)
                               (|error| "index out of bounds"))
                              ((NULL (< |startpos| (QCSIZE |t|)))
                               (- (QREFELT $ 6) 1))
                              ('T
                               (SEQ (SEQ
                                     (LETT |r| |startpos|
                                      |ISTRING;position;Cc$2I;20|)
                                     (LETT #0#
                                      (QSDIFFERENCE (QCSIZE |t|) 1)
                                      |ISTRING;position;Cc$2I;20|)
                                     G190
                                     (COND ((> |r| #0#) (GO G191)))
                                     (SEQ
                                      (EXIT
                                       (COND
                                         ((SPADCALL (CHAR |t| |r|) |cc|
                                           (QREFELT $ 49))
                                          (PROGN
                                            (LETT #1#
                                             (+ |r| (QREFELT $ 6))
                                             |ISTRING;position;Cc$2I;20|)
                                            (GO #1#))))))
                                     (LETT |r| (+ |r| 1)
                                      |ISTRING;position;Cc$2I;20|)
                                     (GO G190) G191 (EXIT NIL))
                                    (EXIT (- (QREFELT $ 6) 1))))))))
           #1# (EXIT #1#))))) 

(DEFUN |ISTRING;suffix?;2$B;21| (|s| |t| $)
  (PROG (|n| |m|)
    (RETURN
      (SEQ (LETT |n| (SPADCALL |t| (QREFELT $ 42))
                 |ISTRING;suffix?;2$B;21|)
           (LETT |m| (SPADCALL |s| (QREFELT $ 42))
                 |ISTRING;suffix?;2$B;21|)
           (EXIT (COND
                   ((< |n| |m|) 'NIL)
                   ('T
                    (SPADCALL |s| |t| (- (+ (QREFELT $ 6) |n|) |m|)
                        (QREFELT $ 46))))))))) 

(DEFUN |ISTRING;split;$CL;22| (|s| |c| $)
  (PROG (|n| |j| |i| |l|)
    (RETURN
      (SEQ (LETT |n| (SPADCALL |s| (QREFELT $ 42))
                 |ISTRING;split;$CL;22|)
           (SEQ (LETT |i| (QREFELT $ 6) |ISTRING;split;$CL;22|) G190
                (COND
                  ((OR (> |i| |n|)
                       (NULL (SPADCALL
                                 (SPADCALL |s| |i| (QREFELT $ 52)) |c|
                                 (QREFELT $ 53))))
                   (GO G191)))
                (SEQ (EXIT 0))
                (LETT |i| (+ |i| 1) |ISTRING;split;$CL;22|) (GO G190)
                G191 (EXIT NIL))
           (LETT |l| (SPADCALL (QREFELT $ 55)) |ISTRING;split;$CL;22|)
           (SEQ G190
                (COND
                  ((NULL (COND
                           ((< |n| |i|) 'NIL)
                           ('T
                            (SPADCALL
                                (< (LETT |j|
                                    (SPADCALL |c| |s| |i|
                                     (QREFELT $ 48))
                                    |ISTRING;split;$CL;22|)
                                   (QREFELT $ 6))
                                (QREFELT $ 56)))))
                   (GO G191)))
                (SEQ (LETT |l|
                           (SPADCALL
                               (SPADCALL |s|
                                   (SPADCALL |i| (- |j| 1)
                                    (QREFELT $ 20))
                                   (QREFELT $ 21))
                               |l| (QREFELT $ 57))
                           |ISTRING;split;$CL;22|)
                     (EXIT (SEQ (LETT |i| |j| |ISTRING;split;$CL;22|)
                                G190
                                (COND
                                  ((OR (> |i| |n|)
                                    (NULL
                                     (SPADCALL
                                      (SPADCALL |s| |i| (QREFELT $ 52))
                                      |c| (QREFELT $ 53))))
                                   (GO G191)))
                                (SEQ (EXIT 0))
                                (LETT |i| (+ |i| 1)
                                      |ISTRING;split;$CL;22|)
                                (GO G190) G191 (EXIT NIL))))
                NIL (GO G190) G191 (EXIT NIL))
           (COND
             ((NULL (< |n| |i|))
              (LETT |l|
                    (SPADCALL
                        (SPADCALL |s| (SPADCALL |i| |n| (QREFELT $ 20))
                            (QREFELT $ 21))
                        |l| (QREFELT $ 57))
                    |ISTRING;split;$CL;22|)))
           (EXIT (SPADCALL |l| (QREFELT $ 58))))))) 

(DEFUN |ISTRING;split;$CcL;23| (|s| |cc| $)
  (PROG (|n| |j| |i| |l|)
    (RETURN
      (SEQ (LETT |n| (SPADCALL |s| (QREFELT $ 42))
                 |ISTRING;split;$CcL;23|)
           (SEQ (LETT |i| (QREFELT $ 6) |ISTRING;split;$CcL;23|) G190
                (COND
                  ((OR (> |i| |n|)
                       (NULL (SPADCALL
                                 (SPADCALL |s| |i| (QREFELT $ 52)) |cc|
                                 (QREFELT $ 49))))
                   (GO G191)))
                (SEQ (EXIT 0))
                (LETT |i| (+ |i| 1) |ISTRING;split;$CcL;23|) (GO G190)
                G191 (EXIT NIL))
           (LETT |l| (SPADCALL (QREFELT $ 55)) |ISTRING;split;$CcL;23|)
           (SEQ G190
                (COND
                  ((NULL (COND
                           ((< |n| |i|) 'NIL)
                           ('T
                            (SPADCALL
                                (< (LETT |j|
                                    (SPADCALL |cc| |s| |i|
                                     (QREFELT $ 50))
                                    |ISTRING;split;$CcL;23|)
                                   (QREFELT $ 6))
                                (QREFELT $ 56)))))
                   (GO G191)))
                (SEQ (LETT |l|
                           (SPADCALL
                               (SPADCALL |s|
                                   (SPADCALL |i| (- |j| 1)
                                    (QREFELT $ 20))
                                   (QREFELT $ 21))
                               |l| (QREFELT $ 57))
                           |ISTRING;split;$CcL;23|)
                     (EXIT (SEQ (LETT |i| |j| |ISTRING;split;$CcL;23|)
                                G190
                                (COND
                                  ((OR (> |i| |n|)
                                    (NULL
                                     (SPADCALL
                                      (SPADCALL |s| |i| (QREFELT $ 52))
                                      |cc| (QREFELT $ 49))))
                                   (GO G191)))
                                (SEQ (EXIT 0))
                                (LETT |i| (+ |i| 1)
                                      |ISTRING;split;$CcL;23|)
                                (GO G190) G191 (EXIT NIL))))
                NIL (GO G190) G191 (EXIT NIL))
           (COND
             ((NULL (< |n| |i|))
              (LETT |l|
                    (SPADCALL
                        (SPADCALL |s| (SPADCALL |i| |n| (QREFELT $ 20))
                            (QREFELT $ 21))
                        |l| (QREFELT $ 57))
                    |ISTRING;split;$CcL;23|)))
           (EXIT (SPADCALL |l| (QREFELT $ 58))))))) 

(DEFUN |ISTRING;leftTrim;$C$;24| (|s| |c| $)
  (PROG (|n| |i|)
    (RETURN
      (SEQ (LETT |n| (SPADCALL |s| (QREFELT $ 42))
                 |ISTRING;leftTrim;$C$;24|)
           (SEQ (LETT |i| (QREFELT $ 6) |ISTRING;leftTrim;$C$;24|) G190
                (COND
                  ((OR (> |i| |n|)
                       (NULL (SPADCALL
                                 (SPADCALL |s| |i| (QREFELT $ 52)) |c|
                                 (QREFELT $ 53))))
                   (GO G191)))
                (SEQ (EXIT 0))
                (LETT |i| (+ |i| 1) |ISTRING;leftTrim;$C$;24|)
                (GO G190) G191 (EXIT NIL))
           (EXIT (SPADCALL |s| (SPADCALL |i| |n| (QREFELT $ 20))
                     (QREFELT $ 21))))))) 

(DEFUN |ISTRING;leftTrim;$Cc$;25| (|s| |cc| $)
  (PROG (|n| |i|)
    (RETURN
      (SEQ (LETT |n| (SPADCALL |s| (QREFELT $ 42))
                 |ISTRING;leftTrim;$Cc$;25|)
           (SEQ (LETT |i| (QREFELT $ 6) |ISTRING;leftTrim;$Cc$;25|)
                G190
                (COND
                  ((OR (> |i| |n|)
                       (NULL (SPADCALL
                                 (SPADCALL |s| |i| (QREFELT $ 52)) |cc|
                                 (QREFELT $ 49))))
                   (GO G191)))
                (SEQ (EXIT 0))
                (LETT |i| (+ |i| 1) |ISTRING;leftTrim;$Cc$;25|)
                (GO G190) G191 (EXIT NIL))
           (EXIT (SPADCALL |s| (SPADCALL |i| |n| (QREFELT $ 20))
                     (QREFELT $ 21))))))) 

(DEFUN |ISTRING;rightTrim;$C$;26| (|s| |c| $)
  (PROG (|j| #0=#:G1830)
    (RETURN
      (SEQ (SEQ (LETT |j| (SPADCALL |s| (QREFELT $ 42))
                      |ISTRING;rightTrim;$C$;26|)
                (LETT #0# (QREFELT $ 6) |ISTRING;rightTrim;$C$;26|)
                G190
                (COND
                  ((OR (< |j| #0#)
                       (NULL (SPADCALL
                                 (SPADCALL |s| |j| (QREFELT $ 52)) |c|
                                 (QREFELT $ 53))))
                   (GO G191)))
                (SEQ (EXIT 0))
                (LETT |j| (+ |j| -1) |ISTRING;rightTrim;$C$;26|)
                (GO G190) G191 (EXIT NIL))
           (EXIT (SPADCALL |s|
                     (SPADCALL (SPADCALL |s| (QREFELT $ 28)) |j|
                         (QREFELT $ 20))
                     (QREFELT $ 21))))))) 

(DEFUN |ISTRING;rightTrim;$Cc$;27| (|s| |cc| $)
  (PROG (|j| #0=#:G1834)
    (RETURN
      (SEQ (SEQ (LETT |j| (SPADCALL |s| (QREFELT $ 42))
                      |ISTRING;rightTrim;$Cc$;27|)
                (LETT #0# (QREFELT $ 6) |ISTRING;rightTrim;$Cc$;27|)
                G190
                (COND
                  ((OR (< |j| #0#)
                       (NULL (SPADCALL
                                 (SPADCALL |s| |j| (QREFELT $ 52)) |cc|
                                 (QREFELT $ 49))))
                   (GO G191)))
                (SEQ (EXIT 0))
                (LETT |j| (+ |j| -1) |ISTRING;rightTrim;$Cc$;27|)
                (GO G190) G191 (EXIT NIL))
           (EXIT (SPADCALL |s|
                     (SPADCALL (SPADCALL |s| (QREFELT $ 28)) |j|
                         (QREFELT $ 20))
                     (QREFELT $ 21))))))) 

(DEFUN |ISTRING;concat;L$;28| (|l| $)
  (PROG (#0=#:G1842 #1=#:G1837 #2=#:G1835 #3=#:G1836 |t| |s| #4=#:G1843
            |i|)
    (RETURN
      (SEQ (LETT |t|
                 (SPADCALL
                     (PROGN
                       (LETT #3# NIL |ISTRING;concat;L$;28|)
                       (SEQ (LETT |s| NIL |ISTRING;concat;L$;28|)
                            (LETT #0# |l| |ISTRING;concat;L$;28|) G190
                            (COND
                              ((OR (ATOM #0#)
                                   (PROGN
                                     (LETT |s| (CAR #0#)
                                      |ISTRING;concat;L$;28|)
                                     NIL))
                               (GO G191)))
                            (SEQ (EXIT (PROGN
                                         (LETT #1#
                                          (SPADCALL |s| (QREFELT $ 13))
                                          |ISTRING;concat;L$;28|)
                                         (COND
                                           (#3#
                                            (LETT #2# (+ #2# #1#)
                                             |ISTRING;concat;L$;28|))
                                           ('T
                                            (PROGN
                                              (LETT #2# #1#
                                               |ISTRING;concat;L$;28|)
                                              (LETT #3# 'T
                                               |ISTRING;concat;L$;28|)))))))
                            (LETT #0# (CDR #0#) |ISTRING;concat;L$;28|)
                            (GO G190) G191 (EXIT NIL))
                       (COND (#3# #2#) ('T 0)))
                     (SPADCALL (QREFELT $ 43)) (QREFELT $ 9))
                 |ISTRING;concat;L$;28|)
           (LETT |i| (QREFELT $ 6) |ISTRING;concat;L$;28|)
           (SEQ (LETT |s| NIL |ISTRING;concat;L$;28|)
                (LETT #4# |l| |ISTRING;concat;L$;28|) G190
                (COND
                  ((OR (ATOM #4#)
                       (PROGN
                         (LETT |s| (CAR #4#) |ISTRING;concat;L$;28|)
                         NIL))
                   (GO G191)))
                (SEQ (SPADCALL |t| |s| |i| (QREFELT $ 66))
                     (EXIT (LETT |i|
                                 (+ |i| (SPADCALL |s| (QREFELT $ 13)))
                                 |ISTRING;concat;L$;28|)))
                (LETT #4# (CDR #4#) |ISTRING;concat;L$;28|) (GO G190)
                G191 (EXIT NIL))
           (EXIT |t|))))) 

(DEFUN |ISTRING;copyInto!;2$I$;29| (|y| |x| |s| $)
  (PROG (|m| |n|)
    (RETURN
      (SEQ (LETT |m| (SPADCALL |x| (QREFELT $ 13))
                 |ISTRING;copyInto!;2$I$;29|)
           (LETT |n| (SPADCALL |y| (QREFELT $ 13))
                 |ISTRING;copyInto!;2$I$;29|)
           (LETT |s| (- |s| (QREFELT $ 6)) |ISTRING;copyInto!;2$I$;29|)
           (COND
             ((OR (< |s| 0) (< |n| (+ |s| |m|)))
              (EXIT (|error| "index out of range"))))
           (RPLACSTR |y| |s| |m| |x| 0 |m|) (EXIT |y|))))) 

(DEFUN |ISTRING;elt;$IC;30| (|s| |i| $)
  (COND
    ((OR (< |i| (QREFELT $ 6)) (< (SPADCALL |s| (QREFELT $ 42)) |i|))
     (|error| "index out of range"))
    ('T (CHAR |s| (- |i| (QREFELT $ 6)))))) 

(DEFUN |ISTRING;elt;$Us$;31| (|s| |sg| $)
  (PROG (|l| |h|)
    (RETURN
      (SEQ (LETT |l| (- (SPADCALL |sg| (QREFELT $ 39)) (QREFELT $ 6))
                 |ISTRING;elt;$Us$;31|)
           (LETT |h|
                 (COND
                   ((SPADCALL |sg| (QREFELT $ 40))
                    (- (SPADCALL |sg| (QREFELT $ 41)) (QREFELT $ 6)))
                   ('T (- (SPADCALL |s| (QREFELT $ 42)) (QREFELT $ 6))))
                 |ISTRING;elt;$Us$;31|)
           (COND
             ((OR (< |l| 0)
                  (NULL (< |h| (SPADCALL |s| (QREFELT $ 13)))))
              (EXIT (|error| "index out of bound"))))
           (EXIT (SUBSTRING |s| |l| (MAX 0 (+ (- |h| |l|) 1)))))))) 

(DEFUN |ISTRING;hash;$I;32| (|s| $)
  (PROG (|n|)
    (RETURN
      (SEQ (LETT |n| (QCSIZE |s|) |ISTRING;hash;$I;32|)
           (EXIT (COND
                   ((ZEROP |n|) 0)
                   ((EQL |n| 1)
                    (SPADCALL
                        (SPADCALL |s| (QREFELT $ 6) (QREFELT $ 52))
                        (QREFELT $ 68)))
                   ('T
                    (* (* (SPADCALL
                              (SPADCALL |s| (QREFELT $ 6)
                                  (QREFELT $ 52))
                              (QREFELT $ 68))
                          (SPADCALL
                              (SPADCALL |s| (- (+ (QREFELT $ 6) |n|) 1)
                                  (QREFELT $ 52))
                              (QREFELT $ 68)))
                       (SPADCALL
                           (SPADCALL |s|
                               (+ (QREFELT $ 6) (QUOTIENT2 |n| 2))
                               (QREFELT $ 52))
                           (QREFELT $ 68)))))))))) 

(DEFUN |ISTRING;match;2$CNni;33| (|pattern| |target| |wildcard| $)
  (|stringMatch| |pattern| |target| (CHARACTER |wildcard|))) 

(DEFUN |ISTRING;match?;2$CB;34| (|pattern| |target| |dontcare| $)
  (PROG (|n| |m| #0=#:G1857 #1=#:G1859 |s| #2=#:G1860 #3=#:G1868 |i|
             |p| #4=#:G1861 |q|)
    (RETURN
      (SEQ (EXIT (SEQ (LETT |n| (SPADCALL |pattern| (QREFELT $ 42))
                            |ISTRING;match?;2$CB;34|)
                      (LETT |p|
                            (PROG1 (LETT #0#
                                    (SPADCALL |dontcare| |pattern|
                                     (LETT |m|
                                      (SPADCALL |pattern|
                                       (QREFELT $ 28))
                                      |ISTRING;match?;2$CB;34|)
                                     (QREFELT $ 48))
                                    |ISTRING;match?;2$CB;34|)
                              (|check-subtype| (>= #0# 0)
                                  '(|NonNegativeInteger|) #0#))
                            |ISTRING;match?;2$CB;34|)
                      (EXIT (COND
                              ((EQL |p| (- |m| 1))
                               (SPADCALL |pattern| |target|
                                   (QREFELT $ 14)))
                              ('T
                               (SEQ (COND
                                      ((NULL (EQL |p| |m|))
                                       (COND
                                         ((NULL
                                           (SPADCALL
                                            (SPADCALL |pattern|
                                             (SPADCALL |m| (- |p| 1)
                                              (QREFELT $ 20))
                                             (QREFELT $ 21))
                                            |target| (QREFELT $ 71)))
                                          (EXIT 'NIL)))))
                                    (LETT |i| |p|
                                     |ISTRING;match?;2$CB;34|)
                                    (LETT |q|
                                     (PROG1
                                      (LETT #1#
                                       (SPADCALL |dontcare| |pattern|
                                        (+ |p| 1) (QREFELT $ 48))
                                       |ISTRING;match?;2$CB;34|)
                                       (|check-subtype| (>= #1# 0)
                                        '(|NonNegativeInteger|) #1#))
                                     |ISTRING;match?;2$CB;34|)
                                    (SEQ G190
                                     (COND
                                       ((NULL
                                         (SPADCALL (EQL |q| (- |m| 1))
                                          (QREFELT $ 56)))
                                        (GO G191)))
                                     (SEQ
                                      (LETT |s|
                                       (SPADCALL |pattern|
                                        (SPADCALL (+ |p| 1) (- |q| 1)
                                         (QREFELT $ 20))
                                        (QREFELT $ 21))
                                       |ISTRING;match?;2$CB;34|)
                                      (LETT |i|
                                       (PROG1
                                        (LETT #2#
                                         (SPADCALL |s| |target| |i|
                                          (QREFELT $ 47))
                                         |ISTRING;match?;2$CB;34|)
                                         (|check-subtype| (>= #2# 0)
                                          '(|NonNegativeInteger|) #2#))
                                       |ISTRING;match?;2$CB;34|)
                                      (EXIT
                                       (COND
                                         ((EQL |i| (- |m| 1))
                                          (PROGN
                                            (LETT #3# 'NIL
                                             |ISTRING;match?;2$CB;34|)
                                            (GO #3#)))
                                         ('T
                                          (SEQ
                                           (LETT |i|
                                            (+ |i|
                                             (SPADCALL |s|
                                              (QREFELT $ 13)))
                                            |ISTRING;match?;2$CB;34|)
                                           (LETT |p| |q|
                                            |ISTRING;match?;2$CB;34|)
                                           (EXIT
                                            (LETT |q|
                                             (PROG1
                                              (LETT #4#
                                               (SPADCALL |dontcare|
                                                |pattern| (+ |q| 1)
                                                (QREFELT $ 48))
                                               |ISTRING;match?;2$CB;34|)
                                               (|check-subtype|
                                                (>= #4# 0)
                                                '(|NonNegativeInteger|)
                                                #4#))
                                             |ISTRING;match?;2$CB;34|)))))))
                                     NIL (GO G190) G191 (EXIT NIL))
                                    (COND
                                      ((NULL (EQL |p| |n|))
                                       (COND
                                         ((NULL
                                           (SPADCALL
                                            (SPADCALL |pattern|
                                             (SPADCALL (+ |p| 1) |n|
                                              (QREFELT $ 20))
                                             (QREFELT $ 21))
                                            |target| (QREFELT $ 51)))
                                          (EXIT 'NIL)))))
                                    (EXIT 'T)))))))
           #3# (EXIT #3#))))) 

(DEFUN |IndexedString| (#0=#:G1875)
  (PROG ()
    (RETURN
      (PROG (#1=#:G1876)
        (RETURN
          (COND
            ((LETT #1#
                   (|lassocShiftWithFunction| (LIST (|devaluate| #0#))
                       (HGET |$ConstructorCache| '|IndexedString|)
                       '|domainEqualList|)
                   |IndexedString|)
             (|CDRwithIncrement| #1#))
            ('T
             (UNWIND-PROTECT
               (PROG1 (|IndexedString;| #0#)
                 (LETT #1# T |IndexedString|))
               (COND
                 ((NOT #1#)
                  (HREM |$ConstructorCache| '|IndexedString|))))))))))) 

(DEFUN |IndexedString;| (|#1|)
  (PROG (|dv$1| |dv$| $ |pv$|)
    (RETURN
      (PROGN
        (LETT |dv$1| (|devaluate| |#1|) . #0=(|IndexedString|))
        (LETT |dv$| (LIST '|IndexedString| |dv$1|) . #0#)
        (LETT $ (|newShell| 84) . #0#)
        (QSETREFV $ 0 |dv$|)
        (QSETREFV $ 3
            (LETT |pv$|
                  (|buildPredVector| 0 0
                      (LIST (OR (AND (|HasCategory| (|Character|)
                                      '(|OrderedSet|))
                                     (|HasCategory| (|Character|)
                                      '(|Evalable| (|Character|))))
                                (AND (|HasCategory| (|Character|)
                                      '(|SetCategory|))
                                     (|HasCategory| (|Character|)
                                      '(|Evalable| (|Character|)))))
                            (OR (|HasCategory| (|Character|)
                                    '(|CoercibleTo| (|OutputForm|)))
                                (AND (|HasCategory| (|Character|)
                                      '(|SetCategory|))
                                     (|HasCategory| (|Character|)
                                      '(|Evalable| (|Character|)))))
                            (|HasCategory| (|Character|)
                                '(|ConvertibleTo| (|InputForm|)))
                            (OR (|HasCategory| (|Character|)
                                    '(|OrderedSet|))
                                (|HasCategory| (|Character|)
                                    '(|SetCategory|)))
                            (|HasCategory| (|Character|)
                                '(|OrderedSet|))
                            (|HasCategory| (|Integer|) '(|OrderedSet|))
                            (|HasCategory| (|Character|)
                                '(|SetCategory|))
                            (AND (|HasCategory| (|Character|)
                                     '(|SetCategory|))
                                 (|HasCategory| (|Character|)
                                     '(|Evalable| (|Character|))))
                            (|HasCategory| (|Character|)
                                '(|CoercibleTo| (|OutputForm|))))) . #0#))
        (|haddProp| |$ConstructorCache| '|IndexedString| (LIST |dv$1|)
            (CONS 1 $))
        (|stuffDomainSlots| $)
        (QSETREFV $ 6 |#1|)
        $)))) 

(MAKEPROP '|IndexedString| '|infovec|
    (LIST '#(NIL NIL NIL NIL NIL NIL (|local| |#1|)
             (|NonNegativeInteger|) (|Character|) |ISTRING;new;NniC$;1|
             |ISTRING;empty;$;2| (|Boolean|) |ISTRING;empty?;$B;3|
             |ISTRING;#;$Nni;4| |ISTRING;=;2$B;5| |ISTRING;<;2$B;6|
             |ISTRING;concat;3$;7| |ISTRING;copy;2$;8| (|Integer|)
             (|UniversalSegment| 18) (0 . SEGMENT)
             |ISTRING;elt;$Us$;31| (6 . SEGMENT)
             |ISTRING;insert;2$I$;9| (|String|) (|OutputForm|)
             (11 . |outputForm|) |ISTRING;coerce;$Of;10|
             |ISTRING;minIndex;$I;11| (|CharacterClass|)
             (16 . |upperCase|) (20 . |upperCase|) (|Mapping| 8 8)
             (25 . |map!|) |ISTRING;upperCase!;2$;12|
             (31 . |lowerCase|) (35 . |lowerCase|)
             |ISTRING;lowerCase!;2$;13| |ISTRING;latex;$S;14|
             (40 . |lo|) (45 . |hasHi|) (50 . |hi|) (55 . |maxIndex|)
             (60 . |space|) |ISTRING;replace;$Us2$;15|
             |ISTRING;setelt;$I2C;16| |ISTRING;substring?;2$IB;17|
             |ISTRING;position;2$2I;18| |ISTRING;position;C$2I;19|
             (64 . |member?|) |ISTRING;position;Cc$2I;20|
             |ISTRING;suffix?;2$B;21| |ISTRING;elt;$IC;30| (70 . =)
             (|List| $$) (76 . |empty|) (80 . |not|) (85 . |concat|)
             (91 . |reverse!|) (|List| $) |ISTRING;split;$CL;22|
             |ISTRING;split;$CcL;23| |ISTRING;leftTrim;$C$;24|
             |ISTRING;leftTrim;$Cc$;25| |ISTRING;rightTrim;$C$;26|
             |ISTRING;rightTrim;$Cc$;27| |ISTRING;copyInto!;2$I$;29|
             |ISTRING;concat;L$;28| (96 . |ord|) |ISTRING;hash;$I;32|
             |ISTRING;match;2$CNni;33| (101 . |prefix?|)
             |ISTRING;match?;2$CB;34| (|List| 8) (|List| 75)
             (|Equation| 8) (|Mapping| 8 8 8) (|InputForm|)
             (|SingleInteger|) (|Mapping| 11 8) (|Mapping| 11 8 8)
             (|Void|) (|Union| 8 '"failed") (|List| 18))
          '#(~= 107 |upperCase!| 113 |upperCase| 118 |trim| 123 |swap!|
             135 |suffix?| 142 |substring?| 148 |split| 155 |sorted?|
             167 |sort!| 178 |sort| 189 |size?| 200 |setelt| 206
             |select| 220 |sample| 226 |rightTrim| 230 |reverse!| 242
             |reverse| 247 |replace| 252 |removeDuplicates| 259
             |remove| 264 |reduce| 276 |qsetelt!| 297 |qelt| 304
             |prefix?| 310 |position| 316 |parts| 349 |new| 354 |more?|
             360 |minIndex| 366 |min| 371 |merge| 377 |members| 390
             |member?| 395 |maxIndex| 401 |max| 406 |match?| 412
             |match| 419 |map!| 426 |map| 432 |lowerCase!| 445
             |lowerCase| 450 |less?| 455 |leftTrim| 461 |latex| 473
             |insert| 478 |indices| 492 |index?| 497 |hash| 503 |first|
             513 |find| 518 |fill!| 524 |every?| 530 |eval| 536 |eq?|
             562 |entry?| 568 |entries| 574 |empty?| 579 |empty| 584
             |elt| 588 |delete| 613 |count| 625 |copyInto!| 637 |copy|
             644 |convert| 649 |construct| 654 |concat| 659 |coerce|
             682 |any?| 692 >= 698 > 704 = 710 <= 716 < 722 |#| 728)
          '((|shallowlyMutable| . 0) (|finiteAggregate| . 0))
          (CONS (|makeByteWordVec2| 5
                    '(0 0 0 0 0 0 0 5 0 0 1 4 0 0 1 2 3 4))
                (CONS '#(|StringAggregate&|
                         |OneDimensionalArrayAggregate&|
                         |FiniteLinearAggregate&| |LinearAggregate&|
                         |IndexedAggregate&| |Collection&|
                         |HomogeneousAggregate&| |OrderedSet&|
                         |Aggregate&| |EltableAggregate&| |Evalable&|
                         |SetCategory&| NIL NIL |InnerEvalable&| NIL
                         NIL |BasicType&|)
                      (CONS '#((|StringAggregate|)
                               (|OneDimensionalArrayAggregate| 8)
                               (|FiniteLinearAggregate| 8)
                               (|LinearAggregate| 8)
                               (|IndexedAggregate| 18 8)
                               (|Collection| 8)
                               (|HomogeneousAggregate| 8)
                               (|OrderedSet|) (|Aggregate|)
                               (|EltableAggregate| 18 8) (|Evalable| 8)
                               (|SetCategory|) (|Type|)
                               (|Eltable| 18 8) (|InnerEvalable| 8 8)
                               (|CoercibleTo| 25) (|ConvertibleTo| 77)
                               (|BasicType|))
                            (|makeByteWordVec2| 83
                                '(2 19 0 18 18 20 1 19 0 18 22 1 25 0
                                  24 26 0 29 0 30 1 8 0 0 31 2 0 0 32 0
                                  33 0 29 0 35 1 8 0 0 36 1 19 18 0 39
                                  1 19 11 0 40 1 19 18 0 41 1 0 18 0 42
                                  0 8 0 43 2 29 11 8 0 49 2 8 11 0 0 53
                                  0 54 0 55 1 11 0 0 56 2 54 0 2 0 57 1
                                  54 0 0 58 1 8 7 0 68 2 0 11 0 0 71 2
                                  7 11 0 0 1 1 0 0 0 34 1 0 0 0 1 2 0 0
                                  0 8 1 2 0 0 0 29 1 3 0 81 0 18 18 1 2
                                  0 11 0 0 51 3 0 11 0 0 18 46 2 0 59 0
                                  29 61 2 0 59 0 8 60 1 5 11 0 1 2 0 11
                                  80 0 1 1 5 0 0 1 2 0 0 80 0 1 1 5 0 0
                                  1 2 0 0 80 0 1 2 0 11 0 7 1 3 0 8 0
                                  19 8 1 3 0 8 0 18 8 45 2 0 0 79 0 1 0
                                  0 0 1 2 0 0 0 8 64 2 0 0 0 29 65 1 0
                                  0 0 1 1 0 0 0 1 3 0 0 0 19 0 44 1 7 0
                                  0 1 2 7 0 8 0 1 2 0 0 79 0 1 4 7 8 76
                                  0 8 8 1 3 0 8 76 0 8 1 2 0 8 76 0 1 3
                                  0 8 0 18 8 1 2 0 8 0 18 1 2 0 11 0 0
                                  71 3 7 18 8 0 18 48 2 7 18 8 0 1 3 0
                                  18 29 0 18 50 3 0 18 0 0 18 47 2 0 18
                                  79 0 1 1 0 73 0 1 2 0 0 7 8 9 2 0 11
                                  0 7 1 1 6 18 0 28 2 5 0 0 0 1 2 5 0 0
                                  0 1 3 0 0 80 0 0 1 1 0 73 0 1 2 7 11
                                  8 0 1 1 6 18 0 42 2 5 0 0 0 1 3 0 11
                                  0 0 8 72 3 0 7 0 0 8 70 2 0 0 32 0 33
                                  3 0 0 76 0 0 1 2 0 0 32 0 1 1 0 0 0
                                  37 1 0 0 0 1 2 0 11 0 7 1 2 0 0 0 8
                                  62 2 0 0 0 29 63 1 7 24 0 38 3 0 0 8
                                  0 18 1 3 0 0 0 0 18 23 1 0 83 0 1 2 0
                                  11 18 0 1 1 7 78 0 1 1 0 18 0 69 1 6
                                  8 0 1 2 0 82 79 0 1 2 0 0 0 8 1 2 0
                                  11 79 0 1 3 8 0 0 73 73 1 3 8 0 0 8 8
                                  1 2 8 0 0 74 1 2 8 0 0 75 1 2 0 11 0
                                  0 1 2 7 11 8 0 1 1 0 73 0 1 1 0 11 0
                                  12 0 0 0 10 2 0 0 0 0 1 2 0 0 0 19 21
                                  2 0 8 0 18 52 3 0 8 0 18 8 1 2 0 0 0
                                  18 1 2 0 0 0 19 1 2 7 7 8 0 1 2 0 7
                                  79 0 1 3 0 0 0 0 18 66 1 0 0 0 17 1 3
                                  77 0 1 1 0 0 73 1 1 0 0 59 67 2 0 0 0
                                  0 16 2 0 0 0 8 1 2 0 0 8 0 1 1 9 25 0
                                  27 1 0 0 8 1 2 0 11 79 0 1 2 5 11 0 0
                                  1 2 5 11 0 0 1 2 7 11 0 0 14 2 5 11 0
                                  0 1 2 5 11 0 0 15 1 0 7 0 13)))))
          '|lookupComplete|)) 
@
\section{domain STRING String}
<<domain STRING String>>=
)abbrev domain STRING String
++ Description:
++   This is the domain of character strings.
MINSTRINGINDEX ==> 1	      -- as of 3/14/90.

String(): StringCategory == IndexedString(MINSTRINGINDEX) add 
    string n == STRINGIMAGE(n)$Lisp

    OMwrite(x: %): String ==
      s: String := ""
      sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
      dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML)
      OMputObject(dev)
      OMputString(dev, x pretend String)
      OMputEndObject(dev)
      OMclose(dev)
      s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
      s

    OMwrite(x: %, wholeObj: Boolean): String ==
      s: String := ""
      sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
      dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML)
      if wholeObj then
        OMputObject(dev)
      OMputString(dev, x pretend String)
      if wholeObj then
        OMputEndObject(dev)
      OMclose(dev)
      s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
      s

    OMwrite(dev: OpenMathDevice, x: %): Void ==
      OMputObject(dev)
      OMputString(dev, x pretend String)
      OMputEndObject(dev)

    OMwrite(dev: OpenMathDevice, x: %, wholeObj: Boolean): Void ==
      if wholeObj then
        OMputObject(dev)
      OMputString(dev, x pretend String)
      if wholeObj then
        OMputEndObject(dev)

@
\section{category STRICAT StringCategory}
<<category STRICAT StringCategory>>=
)abbrev category STRICAT StringCategory
-- Note that StringCategory is built into the old compiler
-- redundant SetCategory added to help A# compiler
++ Description:
++ A category for string-like objects

StringCategory():Category == Join(StringAggregate(), SetCategory, OpenMath) with
  string: Integer -> %
    ++ string(i) returns the decimal representation of i in a string

@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>

<<domain CHAR Character>>
<<domain CCLASS CharacterClass>>
<<domain ISTRING IndexedString>>
<<category STRICAT StringCategory>>
<<domain STRING String>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}