Read strings from standard input and generate a C
 function that returns true iff its argument is one
 of the strings seen by this program.  The code it
 generates is a ternary search tree, expressed as C
 code.  It generates approximately 10 bytes of i386
 code for each byte of string data (including NUL).

charLiteral proc (c in char) ⇒ (s out str)
   if ord(c) in [32,127) then
      s := if c = '\'' or c = '\\' then "'\\" else "'" end if @ c @ "'"
   else
      s := "0x" @ toHex(ord(c))
   end if
end proc

cChar proc (s in str, i in int) ⇒ (c out char)
   c := if i = size s then '\0' else s[i] end if
end proc

title var str
getLine(title)
sorted var []str := {}
loop
   s var str
   while getLine(s)
   j var := size sorted
   sorted @:= {s}
   loop while j ≥ 0 and sorted[j-1] > s
      sorted[j] := sorted[j-1]
      j -:= 1
   end loop
   sorted[j] := s
end loop

generate proc (
   depth in int,
   charactersProcessed in int,
   alreadyLoaded in bool,
   L in int,
   U in int
)
   if L > U then
      print "  "@@depth, "return false;"
   else
      M var := (L+U) div 2
      s const = sorted[M]
      c const = cChar(s, charactersProcessed)
      if L = U then                      
         o var := "return c == " @ charLiteral(c)
         loop for next in [charactersProcessed+1, size s)
            o @:= " && s[" @ toDec(next) @ "] == " @
                  charLiteral(cChar(s, next))
         end loop
         print "  "@@depth, o, "; // ", s
      else
         N var := M
         loop while N < U and cChar(sorted[N+1], charactersProcessed+1) = c
            N +:= 1
         end loop
         loop while M > L and cChar(sorted[M-1], charactersProcessed+1) = c
            M -:= 1
         end loop
         assert 0 ≤ L and L ≤ M and M ≤ N and N ≤ U and U ≤ size sorted
         if L = M and N = U then
            print "  "@@depth, "if (c !=", char(c) @ ") return false;"
            generate(depth, charactersProcessed+1, 0, M, N)
         else
            print "  "@@depth, "if (c < ", char(c) @ ") {"
            generate(depth+1, charactersProcessed, 1, L, M-1)
            print "  "@@depth, "} else"
            print "  "@@depth, "if (c > ", char(c) @ ") {"
            generate(depth+1, charactersProcessed, 1, N+1, U)
            print "  "@@depth, "} else {"
            generate(depth+1, charactersProcessed+1, 0, M, N)
            print "  "@@depth, "}"
         end if
      end if
   end if
end proc

print "bool ", title, "(unsigned char const *s) {"
print "  unsigned char c;"
generate("  ", 0, 0, 1, size sorted)
print "}"
print ""