\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: % -> Integer
	    ++ ord(c) provides an integral code corresponding to the
	    ++ character c.  It is always true that \spad{char ord c = c}.
	char: Integer  -> %
	    ++ 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
	Rep := SingleInteger	  -- 0..255

	CC ==> CharacterClass()
	import CC

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

	OutChars:PrimitiveArray(OutputForm) :=
	   construct [NUM2CHAR(i)$Lisp for i in 0..255]

	minChar := minIndex OutChars

	a = b		       == a =$Rep b
	a < b		       == a <$Rep b
	size()		       == 256
	index n		       == char((n - 1)::Integer)
	lookup c	       == (1 + ord c)::PositiveInteger
	char(n:Integer)	       == n::%
	ord c		       == convert(c)$Rep
	random()	       == char(random()$Integer rem size())
	space		       == QENUM("   ", 0$Lisp)$Lisp
	quote		       == QENUM("_" ", 0$Lisp)$Lisp
	escape		       == QENUM("__ ", 0$Lisp)$Lisp
	coerce(c:%):OutputForm == OutChars(minChar + ord c)
	digit? c	       == member?(c pretend Character, digit())
	hexDigit? c	       == member?(c pretend Character, hexDigit())
	upperCase? c	       == member?(c pretend Character, upperCase())
	lowerCase? c	       == member?(c pretend Character, lowerCase())
	alphabetic? c	       == member?(c pretend Character, alphabetic())
	alphanumeric? c	       == member?(c pretend Character, alphanumeric())

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

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

	upperCase c ==
	  QENUM(PNAME(UPCASE(NUM2CHAR(ord c)$Lisp)$Lisp)$Lisp,
		0$Lisp)$Lisp

	lowerCase c ==
	  QENUM(PNAME(DOWNCASE(NUM2CHAR(ord c)$Lisp)$Lisp)$Lisp,
		0$Lisp)$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 (QUOTE |CHAR;=;2$B;1|) (QUOTE |SPADreplace|) (QUOTE EQL)) 

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

(PUT (QUOTE |CHAR;<;2$B;2|) (QUOTE |SPADreplace|) (QUOTE QSLESSP)) 

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

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

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

(DEFUN |CHAR;index;Pi$;4| (|n| |$|) (SPADCALL (|-| |n| 1) (QREFELT |$| 18))) 

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

(DEFUN |CHAR;char;I$;6| (|n| |$|) (SPADCALL |n| (QREFELT |$| 23))) 

(PUT (QUOTE |CHAR;ord;$I;7|) (QUOTE |SPADreplace|) (QUOTE (XLAM (|c|) |c|))) 

(DEFUN |CHAR;ord;$I;7| (|c| |$|) |c|) 

(DEFUN |CHAR;random;$;8| (|$|) (SPADCALL (REMAINDER2 (|random|) (SPADCALL (QREFELT |$| 16))) (QREFELT |$| 18))) 

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

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

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

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

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

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

(DEFUN |CHAR;coerce;$Of;12| (|c| |$|) (ELT (QREFELT |$| 10) (|+| (QREFELT |$| 11) (SPADCALL |c| (QREFELT |$| 21))))) 

(DEFUN |CHAR;digit?;$B;13| (|c| |$|) (SPADCALL |c| (|spadConstant| |$| 31) (QREFELT |$| 33))) 

(DEFUN |CHAR;hexDigit?;$B;14| (|c| |$|) (SPADCALL |c| (|spadConstant| |$| 35) (QREFELT |$| 33))) 

(DEFUN |CHAR;upperCase?;$B;15| (|c| |$|) (SPADCALL |c| (|spadConstant| |$| 37) (QREFELT |$| 33))) 

(DEFUN |CHAR;lowerCase?;$B;16| (|c| |$|) (SPADCALL |c| (|spadConstant| |$| 39) (QREFELT |$| 33))) 

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

(DEFUN |CHAR;alphanumeric?;$B;18| (|c| |$|) (SPADCALL |c| (|spadConstant| |$| 43) (QREFELT |$| 33))) 

(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 |$| 47)) (QREFELT |$| 48))) ((QUOTE T) (|error| "String is not a single character")))) 

(DEFUN |CHAR;upperCase;2$;21| (|c| |$|) (QENUM (PNAME (UPCASE (NUM2CHAR (SPADCALL |c| (QREFELT |$| 21))))) 0)) 

(DEFUN |CHAR;lowerCase;2$;22| (|c| |$|) (QENUM (PNAME (DOWNCASE (NUM2CHAR (SPADCALL |c| (QREFELT |$| 21))))) 0)) 

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

(DEFUN |Character;| NIL (PROG (|dv$| |$| |pv$| #1=#:G90939 |i|) (RETURN (SEQ (PROGN (LETT |dv$| (QUOTE (|Character|)) . #2=(|Character|)) (LETT |$| (GETREFV 53) . #2#) (QSETREFV |$| 0 |dv$|) (QSETREFV |$| 3 (LETT |pv$| (|buildPredVector| 0 0 NIL) . #2#)) (|haddProp| |$ConstructorCache| (QUOTE |Character|) NIL (CONS 1 |$|)) (|stuffDomainSlots| |$|) (QSETREFV |$| 6 (|SingleInteger|)) (QSETREFV |$| 10 (SPADCALL (PROGN (LETT #1# NIL . #2#) (SEQ (LETT |i| 0 . #2#) G190 (COND ((QSGREATERP |i| 255) (GO G191))) (SEQ (EXIT (LETT #1# (CONS (NUM2CHAR |i|) #1#) . #2#))) (LETT |i| (QSADD1 |i|) . #2#) (GO G190) G191 (EXIT (NREVERSE0 #1#)))) (QREFELT |$| 9))) (QSETREFV |$| 11 0) |$|))))) 

(MAKEPROP (QUOTE |Character|) (QUOTE |infovec|) (LIST (QUOTE #(NIL NIL NIL NIL NIL NIL (QUOTE |Rep|) (|List| 28) (|PrimitiveArray| 28) (0 . |construct|) (QUOTE |OutChars|) (QUOTE |minChar|) (|Boolean|) |CHAR;=;2$B;1| |CHAR;<;2$B;2| (|NonNegativeInteger|) |CHAR;size;Nni;3| (|Integer|) |CHAR;char;I$;6| (|PositiveInteger|) |CHAR;index;Pi$;4| |CHAR;ord;$I;7| |CHAR;lookup;$Pi;5| (5 . |coerce|) |CHAR;random;$;8| |CHAR;space;$;9| |CHAR;quote;$;10| |CHAR;escape;$;11| (|OutputForm|) |CHAR;coerce;$Of;12| (|CharacterClass|) (10 . |digit|) (|Character|) (14 . |member?|) |CHAR;digit?;$B;13| (20 . |hexDigit|) |CHAR;hexDigit?;$B;14| (24 . |upperCase|) |CHAR;upperCase?;$B;15| (28 . |lowerCase|) |CHAR;lowerCase?;$B;16| (32 . |alphabetic|) |CHAR;alphabetic?;$B;17| (36 . |alphanumeric|) |CHAR;alphanumeric?;$B;18| (|String|) |CHAR;latex;$S;19| (40 . |minIndex|) (45 . |elt|) |CHAR;char;S$;20| |CHAR;upperCase;2$;21| |CHAR;lowerCase;2$;22| (|SingleInteger|))) (QUOTE #(|~=| 51 |upperCase?| 57 |upperCase| 62 |space| 67 |size| 71 |random| 75 |quote| 79 |ord| 83 |min| 88 |max| 94 |lowerCase?| 100 |lowerCase| 105 |lookup| 110 |latex| 115 |index| 120 |hexDigit?| 125 |hash| 130 |escape| 135 |digit?| 139 |coerce| 144 |char| 149 |alphanumeric?| 159 |alphabetic?| 164 |>=| 169 |>| 175 |=| 181 |<=| 187 |<| 193)) (QUOTE NIL) (CONS (|makeByteWordVec2| 1 (QUOTE (0 0 0 0 0 0))) (CONS (QUOTE #(NIL |OrderedSet&| NIL |SetCategory&| |BasicType&| NIL)) (CONS (QUOTE #((|OrderedFinite|) (|OrderedSet|) (|Finite|) (|SetCategory|) (|BasicType|) (|CoercibleTo| 28))) (|makeByteWordVec2| 52 (QUOTE (1 8 0 7 9 1 6 0 17 23 0 30 0 31 2 30 12 32 0 33 0 30 0 35 0 30 0 37 0 30 0 39 0 30 0 41 0 30 0 43 1 45 17 0 47 2 45 32 0 17 48 2 0 12 0 0 1 1 0 12 0 38 1 0 0 0 50 0 0 0 25 0 0 15 16 0 0 0 24 0 0 0 26 1 0 17 0 21 2 0 0 0 0 1 2 0 0 0 0 1 1 0 12 0 40 1 0 0 0 51 1 0 19 0 22 1 0 45 0 46 1 0 0 19 20 1 0 12 0 36 1 0 52 0 1 0 0 0 27 1 0 12 0 34 1 0 28 0 29 1 0 0 45 49 1 0 0 17 18 1 0 12 0 44 1 0 12 0 42 2 0 12 0 0 1 2 0 12 0 0 1 2 0 12 0 0 13 2 0 12 0 0 1 2 0 12 0 0 14)))))) (QUOTE |lookupComplete|))) 

(MAKEPROP (QUOTE |Character|) (QUOTE 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    ==> QENUM$Lisp
    Qequal  ==> EQUAL$Lisp
    Qsetelt ==> QESET$Lisp
    Qsize   ==> QCSIZE$Lisp
    Cheq    ==> EQL$Lisp
    Chlt    ==> QSLESSP$Lisp
    Chgt    ==> QSGREATERP$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 (QUOTE |ISTRING;new;NniC$;1|) (QUOTE |SPADreplace|) (QUOTE |MAKE-FULL-CVEC|)) 

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

(PUT (QUOTE |ISTRING;empty;$;2|) (QUOTE |SPADreplace|) (QUOTE (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 (QUOTE |ISTRING;#;$Nni;4|) (QUOTE |SPADreplace|) (QUOTE QCSIZE)) 

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

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

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

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

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

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

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

(PUT (QUOTE |ISTRING;copy;2$;8|) (QUOTE |SPADreplace|) (QUOTE |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| #1=#:G91425 |r| #2=#:G91433 #3=#:G91432 |i| #4=#:G91431 |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))) ((QUOTE 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 #1# (|+| (|-| |m| (|+| (|-| |h| |l|) 1)) |n|) |ISTRING;replace;$Us2$;15|) (|check-subtype| (|>=| #1# 0) (QUOTE (|NonNegativeInteger|)) #1#)) (SPADCALL (QREFELT |$| 43)) (QREFELT |$| 9)) |ISTRING;replace;$Us2$;15|) (SEQ (LETT |i| 0 |ISTRING;replace;$Us2$;15|) (LETT #2# (|-| |l| 1) |ISTRING;replace;$Us2$;15|) (LETT |k| 0 |ISTRING;replace;$Us2$;15|) G190 (COND ((QSGREATERP |i| #2#) (GO G191))) (SEQ (EXIT (QESET |r| |k| (QENUM |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 #3# (|-| |n| 1) |ISTRING;replace;$Us2$;15|) (LETT |k| |k| |ISTRING;replace;$Us2$;15|) G190 (COND ((QSGREATERP |i| #3#) (GO G191))) (SEQ (EXIT (QESET |r| |k| (QENUM |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 #4# (|-| |m| 1) |ISTRING;replace;$Us2$;15|) (LETT |k| |k| |ISTRING;replace;$Us2$;15|) G190 (COND ((|>| |i| #4#) (GO G191))) (SEQ (EXIT (QESET |r| |k| (QENUM |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")) ((QUOTE T) (SEQ (QESET |s| (|-| |i| (QREFELT |$| 6)) |c|) (EXIT |c|)))))) 

(DEFUN |ISTRING;substring?;2$IB;17| (|part| |whole| |startpos| |$|) (PROG (|np| |nw| |iw| |ip| #1=#:G91443 #2=#:G91442 #3=#:G91438) (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|) (QUOTE NIL)) ((QUOTE T) (SEQ (SEQ (EXIT (SEQ (LETT |iw| |startpos| |ISTRING;substring?;2$IB;17|) (LETT |ip| 0 |ISTRING;substring?;2$IB;17|) (LETT #1# (|-| |np| 1) |ISTRING;substring?;2$IB;17|) G190 (COND ((QSGREATERP |ip| #1#) (GO G191))) (SEQ (EXIT (COND ((NULL (EQL (QENUM |part| |ip|) (QENUM |whole| |iw|))) (PROGN (LETT #3# (PROGN (LETT #2# (QUOTE NIL) |ISTRING;substring?;2$IB;17|) (GO #2#)) |ISTRING;substring?;2$IB;17|) (GO #3#)))))) (LETT |ip| (PROG1 (QSADD1 |ip|) (LETT |iw| (|+| |iw| 1) |ISTRING;substring?;2$IB;17|)) |ISTRING;substring?;2$IB;17|) (GO G190) G191 (EXIT NIL))) #3# (EXIT #3#)) (EXIT (QUOTE T)))))))) #2# (EXIT #2#))))) 

(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)) ((QUOTE T) (SEQ (LETT |r| (STRPOS |s| |t| |startpos| NIL) |ISTRING;position;2$2I;18|) (EXIT (COND ((EQ |r| NIL) (|-| (QREFELT |$| 6) 1)) ((QUOTE T) (|+| |r| (QREFELT |$| 6))))))))))))) 

(DEFUN |ISTRING;position;C$2I;19| (|c| |t| |startpos| |$|) (PROG (|r| #1=#:G91454 #2=#:G91453) (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)) ((QUOTE T) (SEQ (SEQ (LETT |r| |startpos| |ISTRING;position;C$2I;19|) (LETT #1# (QSDIFFERENCE (QCSIZE |t|) 1) |ISTRING;position;C$2I;19|) G190 (COND ((|>| |r| #1#) (GO G191))) (SEQ (EXIT (COND ((EQL (QENUM |t| |r|) |c|) (PROGN (LETT #2# (|+| |r| (QREFELT |$| 6)) |ISTRING;position;C$2I;19|) (GO #2#)))))) (LETT |r| (|+| |r| 1) |ISTRING;position;C$2I;19|) (GO G190) G191 (EXIT NIL)) (EXIT (|-| (QREFELT |$| 6) 1)))))))) #2# (EXIT #2#))))) 

(DEFUN |ISTRING;position;Cc$2I;20| (|cc| |t| |startpos| |$|) (PROG (|r| #1=#:G91461 #2=#:G91460) (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)) ((QUOTE T) (SEQ (SEQ (LETT |r| |startpos| |ISTRING;position;Cc$2I;20|) (LETT #1# (QSDIFFERENCE (QCSIZE |t|) 1) |ISTRING;position;Cc$2I;20|) G190 (COND ((|>| |r| #1#) (GO G191))) (SEQ (EXIT (COND ((SPADCALL (QENUM |t| |r|) |cc| (QREFELT |$| 49)) (PROGN (LETT #2# (|+| |r| (QREFELT |$| 6)) |ISTRING;position;Cc$2I;20|) (GO #2#)))))) (LETT |r| (|+| |r| 1) |ISTRING;position;Cc$2I;20|) (GO G190) G191 (EXIT NIL)) (EXIT (|-| (QREFELT |$| 6) 1)))))))) #2# (EXIT #2#))))) 

(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|) (QUOTE NIL)) ((QUOTE 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|) (QUOTE NIL)) ((QUOTE T) (SEQ (LETT |j| (SPADCALL |c| |s| |i| (QREFELT |$| 48)) |ISTRING;split;$CL;22|) (EXIT (COND ((|<| |j| (QREFELT |$| 6)) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))))))) (GO G191))) (SEQ (LETT |l| (SPADCALL (SPADCALL |s| (SPADCALL |i| (|-| |j| 1) (QREFELT |$| 20)) (QREFELT |$| 21)) |l| (QREFELT |$| 56)) |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 |$| 56)) |ISTRING;split;$CL;22|))) (EXIT (SPADCALL |l| (QREFELT |$| 57))))))) 

(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|) (QUOTE NIL)) ((QUOTE T) (SEQ (LETT |j| (SPADCALL |cc| |s| |i| (QREFELT |$| 50)) |ISTRING;split;$CcL;23|) (EXIT (COND ((|<| |j| (QREFELT |$| 6)) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))))))) (GO G191))) (SEQ (LETT |l| (SPADCALL (SPADCALL |s| (SPADCALL |i| (|-| |j| 1) (QREFELT |$| 20)) (QREFELT |$| 21)) |l| (QREFELT |$| 56)) |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 |$| 56)) |ISTRING;split;$CcL;23|))) (EXIT (SPADCALL |l| (QREFELT |$| 57))))))) 

(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| #1=#:G91487) (RETURN (SEQ (SEQ (LETT |j| (SPADCALL |s| (QREFELT |$| 42)) |ISTRING;rightTrim;$C$;26|) (LETT #1# (QREFELT |$| 6) |ISTRING;rightTrim;$C$;26|) G190 (COND ((OR (|<| |j| #1#) (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| #1=#:G91491) (RETURN (SEQ (SEQ (LETT |j| (SPADCALL |s| (QREFELT |$| 42)) |ISTRING;rightTrim;$Cc$;27|) (LETT #1# (QREFELT |$| 6) |ISTRING;rightTrim;$Cc$;27|) G190 (COND ((OR (|<| |j| #1#) (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 (#1=#:G91500 #2=#:G91494 #3=#:G91492 #4=#:G91493 |t| |s| #5=#:G91499 |i|) (RETURN (SEQ (LETT |t| (SPADCALL (PROGN (LETT #4# NIL |ISTRING;concat;L$;28|) (SEQ (LETT |s| NIL |ISTRING;concat;L$;28|) (LETT #1# |l| |ISTRING;concat;L$;28|) G190 (COND ((OR (ATOM #1#) (PROGN (LETT |s| (CAR #1#) |ISTRING;concat;L$;28|) NIL)) (GO G191))) (SEQ (EXIT (PROGN (LETT #2# (SPADCALL |s| (QREFELT |$| 13)) |ISTRING;concat;L$;28|) (COND (#4# (LETT #3# (|+| #3# #2#) |ISTRING;concat;L$;28|)) ((QUOTE T) (PROGN (LETT #3# #2# |ISTRING;concat;L$;28|) (LETT #4# (QUOTE T) |ISTRING;concat;L$;28|))))))) (LETT #1# (CDR #1#) |ISTRING;concat;L$;28|) (GO G190) G191 (EXIT NIL)) (COND (#4# #3#) ((QUOTE 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 #5# |l| |ISTRING;concat;L$;28|) G190 (COND ((OR (ATOM #5#) (PROGN (LETT |s| (CAR #5#) |ISTRING;concat;L$;28|) NIL)) (GO G191))) (SEQ (SPADCALL |t| |s| |i| (QREFELT |$| 65)) (EXIT (LETT |i| (|+| |i| (SPADCALL |s| (QREFELT |$| 13))) |ISTRING;concat;L$;28|))) (LETT #5# (CDR #5#) |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")) ((QUOTE T) (QENUM |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))) ((QUOTE 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 |$| 67))) ((QUOTE T) (|*| (|*| (SPADCALL (SPADCALL |s| (QREFELT |$| 6) (QREFELT |$| 52)) (QREFELT |$| 67)) (SPADCALL (SPADCALL |s| (|-| (|+| (QREFELT |$| 6) |n|) 1) (QREFELT |$| 52)) (QREFELT |$| 67))) (SPADCALL (SPADCALL |s| (|+| (QREFELT |$| 6) (QUOTIENT2 |n| 2)) (QREFELT |$| 52)) (QREFELT |$| 67)))))))))) 

(PUT (QUOTE |ISTRING;match;2$CNni;33|) (QUOTE |SPADreplace|) (QUOTE |stringMatch|)) 

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

(DEFUN |ISTRING;match?;2$CB;34| (|pattern| |target| |dontcare| |$|) (PROG (|n| |m| #1=#:G91514 #2=#:G91516 |s| #3=#:G91518 #4=#:G91526 |i| |p| #5=#:G91519 |q|) (RETURN (SEQ (EXIT (SEQ (LETT |n| (SPADCALL |pattern| (QREFELT |$| 42)) |ISTRING;match?;2$CB;34|) (LETT |p| (PROG1 (LETT #1# (SPADCALL |dontcare| |pattern| (LETT |m| (SPADCALL |pattern| (QREFELT |$| 28)) |ISTRING;match?;2$CB;34|) (QREFELT |$| 48)) |ISTRING;match?;2$CB;34|) (|check-subtype| (|>=| #1# 0) (QUOTE (|NonNegativeInteger|)) #1#)) |ISTRING;match?;2$CB;34|) (EXIT (COND ((EQL |p| (|-| |m| 1)) (SPADCALL |pattern| |target| (QREFELT |$| 14))) ((QUOTE T) (SEQ (COND ((NULL (EQL |p| |m|)) (COND ((NULL (SPADCALL (SPADCALL |pattern| (SPADCALL |m| (|-| |p| 1) (QREFELT |$| 20)) (QREFELT |$| 21)) |target| (QREFELT |$| 70))) (EXIT (QUOTE NIL)))))) (LETT |i| |p| |ISTRING;match?;2$CB;34|) (LETT |q| (PROG1 (LETT #2# (SPADCALL |dontcare| |pattern| (|+| |p| 1) (QREFELT |$| 48)) |ISTRING;match?;2$CB;34|) (|check-subtype| (|>=| #2# 0) (QUOTE (|NonNegativeInteger|)) #2#)) |ISTRING;match?;2$CB;34|) (SEQ G190 (COND ((NULL (COND ((EQL |q| (|-| |m| 1)) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) (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 #3# (SPADCALL |s| |target| |i| (QREFELT |$| 47)) |ISTRING;match?;2$CB;34|) (|check-subtype| (|>=| #3# 0) (QUOTE (|NonNegativeInteger|)) #3#)) |ISTRING;match?;2$CB;34|) (EXIT (COND ((EQL |i| (|-| |m| 1)) (PROGN (LETT #4# (QUOTE NIL) |ISTRING;match?;2$CB;34|) (GO #4#))) ((QUOTE 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 #5# (SPADCALL |dontcare| |pattern| (|+| |q| 1) (QREFELT |$| 48)) |ISTRING;match?;2$CB;34|) (|check-subtype| (|>=| #5# 0) (QUOTE (|NonNegativeInteger|)) #5#)) |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 (QUOTE NIL)))))) (EXIT (QUOTE T)))))))) #4# (EXIT #4#))))) 

(DEFUN |IndexedString| (#1=#:G91535) (PROG NIL (RETURN (PROG (#2=#:G91536) (RETURN (COND ((LETT #2# (|lassocShiftWithFunction| (LIST (|devaluate| #1#)) (HGET |$ConstructorCache| (QUOTE |IndexedString|)) (QUOTE |domainEqualList|)) |IndexedString|) (|CDRwithIncrement| #2#)) ((QUOTE T) (|UNWIND-PROTECT| (PROG1 (|IndexedString;| #1#) (LETT #2# T |IndexedString|)) (COND ((NOT #2#) (HREM |$ConstructorCache| (QUOTE |IndexedString|)))))))))))) 

(DEFUN |IndexedString;| (|#1|) (PROG (|DV$1| |dv$| |$| #1=#:G91534 #2=#:G91533 |pv$|) (RETURN (PROGN (LETT |DV$1| (|devaluate| |#1|) . #3=(|IndexedString|)) (LETT |dv$| (LIST (QUOTE |IndexedString|) |DV$1|) . #3#) (LETT |$| (GETREFV 83) . #3#) (QSETREFV |$| 0 |dv$|) (QSETREFV |$| 3 (LETT |pv$| (|buildPredVector| 0 0 (LIST (|HasCategory| (|Character|) (QUOTE (|SetCategory|))) (|HasCategory| (|Character|) (QUOTE (|ConvertibleTo| (|InputForm|)))) (LETT #1# (|HasCategory| (|Character|) (QUOTE (|OrderedSet|))) . #3#) (OR #1# (|HasCategory| (|Character|) (QUOTE (|SetCategory|)))) (|HasCategory| (|Integer|) (QUOTE (|OrderedSet|))) (LETT #2# (AND (|HasCategory| (|Character|) (QUOTE (|Evalable| (|Character|)))) (|HasCategory| (|Character|) (QUOTE (|SetCategory|)))) . #3#) (OR (AND (|HasCategory| (|Character|) (QUOTE (|Evalable| (|Character|)))) #1#) #2#))) . #3#)) (|haddProp| |$ConstructorCache| (QUOTE |IndexedString|) (LIST |DV$1|) (CONS 1 |$|)) (|stuffDomainSlots| |$|) (QSETREFV |$| 6 |#1|) |$|)))) 

(MAKEPROP (QUOTE |IndexedString|) (QUOTE |infovec|) (LIST (QUOTE #(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 . |concat|) (86 . |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| (91 . |ord|) |ISTRING;hash;$I;32| |ISTRING;match;2$CNni;33| (96 . |prefix?|) |ISTRING;match?;2$CB;34| (|List| 8) (|List| 74) (|Equation| 8) (|Mapping| 8 8 8) (|InputForm|) (|SingleInteger|) (|Mapping| 11 8) (|Mapping| 11 8 8) (|Void|) (|Union| 8 (QUOTE "failed")) (|List| 18))) (QUOTE #(|~=| 102 |upperCase!| 108 |upperCase| 113 |trim| 118 |swap!| 130 |suffix?| 137 |substring?| 143 |split| 150 |sorted?| 162 |sort!| 173 |sort| 184 |size?| 195 |setelt| 201 |select| 215 |sample| 221 |rightTrim| 225 |reverse!| 237 |reverse| 242 |replace| 247 |removeDuplicates| 254 |remove| 259 |reduce| 271 |qsetelt!| 292 |qelt| 299 |prefix?| 305 |position| 311 |parts| 344 |new| 349 |more?| 355 |minIndex| 361 |min| 366 |merge| 372 |members| 385 |member?| 390 |maxIndex| 396 |max| 401 |match?| 407 |match| 414 |map!| 421 |map| 427 |lowerCase!| 440 |lowerCase| 445 |less?| 450 |leftTrim| 456 |latex| 468 |insert| 473 |indices| 487 |index?| 492 |hash| 498 |first| 508 |find| 513 |fill!| 519 |every?| 525 |eval| 531 |eq?| 557 |entry?| 563 |entries| 569 |empty?| 574 |empty| 579 |elt| 583 |delete| 608 |count| 620 |copyInto!| 632 |copy| 639 |convert| 644 |construct| 649 |concat| 654 |coerce| 677 |any?| 687 |>=| 693 |>| 699 |=| 705 |<=| 711 |<| 717 |#| 723)) (QUOTE ((|shallowlyMutable| . 0) (|finiteAggregate| . 0))) (CONS (|makeByteWordVec2| 7 (QUOTE (0 0 0 0 0 0 0 3 0 0 7 4 0 0 7 1 2 4))) (CONS (QUOTE #(|StringAggregate&| |OneDimensionalArrayAggregate&| |FiniteLinearAggregate&| |LinearAggregate&| |IndexedAggregate&| |Collection&| |HomogeneousAggregate&| |OrderedSet&| |Aggregate&| |EltableAggregate&| |Evalable&| |SetCategory&| NIL NIL |InnerEvalable&| NIL NIL |BasicType&|)) (CONS (QUOTE #((|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| 76) (|BasicType|))) (|makeByteWordVec2| 82 (QUOTE (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 2 54 0 2 0 56 1 54 0 0 57 1 8 18 0 67 2 0 11 0 0 70 2 1 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 80 0 18 18 1 2 0 11 0 0 51 3 0 11 0 0 18 46 2 0 58 0 29 60 2 0 58 0 8 59 1 3 11 0 1 2 0 11 79 0 1 1 3 0 0 1 2 0 0 79 0 1 1 3 0 0 1 2 0 0 79 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 78 0 1 0 0 0 1 2 0 0 0 8 63 2 0 0 0 29 64 1 0 0 0 1 1 0 0 0 1 3 0 0 0 19 0 44 1 1 0 0 1 2 1 0 8 0 1 2 0 0 78 0 1 4 1 8 75 0 8 8 1 3 0 8 75 0 8 1 2 0 8 75 0 1 3 0 8 0 18 8 1 2 0 8 0 18 1 2 0 11 0 0 70 3 1 18 8 0 18 48 2 1 18 8 0 1 3 0 18 29 0 18 50 3 0 18 0 0 18 47 2 0 18 78 0 1 1 0 72 0 1 2 0 0 7 8 9 2 0 11 0 7 1 1 5 18 0 28 2 3 0 0 0 1 2 3 0 0 0 1 3 0 0 79 0 0 1 1 0 72 0 1 2 1 11 8 0 1 1 5 18 0 42 2 3 0 0 0 1 3 0 11 0 0 8 71 3 0 7 0 0 8 69 2 0 0 32 0 33 3 0 0 75 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 61 2 0 0 0 29 62 1 1 24 0 38 3 0 0 8 0 18 1 3 0 0 0 0 18 23 1 0 82 0 1 2 0 11 18 0 1 1 1 77 0 1 1 0 18 0 68 1 5 8 0 1 2 0 81 78 0 1 2 0 0 0 8 1 2 0 11 78 0 1 3 6 0 0 72 72 1 3 6 0 0 8 8 1 2 6 0 0 73 1 2 6 0 0 74 1 2 0 11 0 0 1 2 1 11 8 0 1 1 0 72 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 1 7 8 0 1 2 0 7 78 0 1 3 0 0 0 0 18 65 1 0 0 0 17 1 2 76 0 1 1 0 0 72 1 1 0 0 58 66 2 0 0 0 0 16 2 0 0 0 8 1 2 0 0 8 0 1 1 1 25 0 27 1 0 0 8 1 2 0 11 78 0 1 2 3 11 0 0 1 2 3 11 0 0 1 2 1 11 0 0 14 2 3 11 0 0 1 2 3 11 0 0 15 1 0 7 0 13)))))) (QUOTE |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}