7.4 示例：字符串代换 (Example: String Substitution)

作为一个 I/O 的示例，本节演示如何写一个简单的程序来对文本文件做字符串替换。我们即将写一个可以将一个文件中，旧的字符串 old 换成某个新的字符串 new 的函数。最简单的实现方式是将输入文件里的每一个字符与 old 的第一个字符比较。如果没有匹配，我们可以直接印出该字符至输出。如果匹配了，我们可以将输入的下一个字符与 old 的第二个字符比较，等等。如果输入字符与 old 完全相等时，我们有一个成功的匹配，则我们印出 new 至文件。

而要是 old 在匹配途中失败了，会发生什么事呢？举例来说，假设我们要找的模式 (pattern)是 "abac" ，而输入文件包含的是 "ababac" 。输入会一直到第四个字符才发现不匹配，也就是在模式中的 c 以及输入的 b 才发现。在此时我们可以将原本的 a 写至输出文件，因为我们已经知道这里没有匹配。但有些我们从输入读入的字符还是需要留着: 举例来说，第三个 a ，确实是成功匹配的开始。所以在我们要实现这个算法之前，我们需要一个地方来储存，我们已经从输入读入的字符，但之后仍然需要的字符。

一个暂时储存输入的队列 (queue)称作缓冲区 (buffer)。在这个情况里，因为我们知道我们不需要储存超过一个预定的字符量，我们可以使用一个叫做环状缓冲区 ring buffer 的资料结构。一个环状缓冲区实际上是一个向量。是使用的方式使其成为环状: 我们将之后的元素所输入进来的值储存起来，而当我们到达向量结尾时，我们重头开始。如果我们不需要储存超过 n 个值，则我们只需要一个长度为 n 或是大于 n 的向量，这样我们就不需要覆写正在用的值。

在图 7.1 的代码，实现了环状缓冲区的操作。 buf 有五个字段 (field): 一个包含存入缓冲区的向量，四个其它字段用来放指向向量的索引 (indices)。两个索引是 start 与 end ，任何环状缓冲区的使用都会需要这两个索引: start 指向缓冲区的第一个值，当我们取出一个值时， start 会递增 (incremented)； end 指向缓冲区的最后一个值，当我们插入一个新值时， end 会递增。

另外两个索引， used 以及 new ，是我们需要给这个应用的基本环状缓冲区所加入的东西。它们会介于 start 与 end 之间。实际上，它总是符合

  1. start ≤ used ≤ new ≤ end

你可以把 used 与 new 想成是当前匹配 (current match) 的 start 与 end 。当我们开始一轮匹配时， used 会等于 start 而 new 会等于 end 。当下一个字符 (successive character)匹配时，我们需要递增 used 。当 used 与 new 相等时，我们将开始匹配时，所有存在缓冲区的字符读入。我们不想要使用超过从匹配时所存在缓冲区的字符，或是重复使用同样的字符。因此这个 new 索引，开始等于 end ，但它不会在一轮匹配我们插入新字符至缓冲区一起递增。

函数 bref 接受一个缓冲区与一个索引，并返回索引所在位置的元素。借由使用 index 对向量的长度取 mod ，我们可以假装我们有一个任意长的缓冲区。调用 (new-buf n) 会产生一个新的缓冲区，能够容纳 n 个对象。

要插入一个新值至缓冲区，我们将使用 buf-insert 。它将 end 递增，并把新的值放在那个位置 (译注: 递增完的位置)。相反的 buf-pop 返回一个缓冲区的第一个数值，接着将 start 递增。任何环状缓冲区都会有这两个函数。

  1. (defstruct buf
  2.   vec (start -1) (used -1) (new -1) (end -1))
  4. (defun bref (buf n)
  5.   (svref (buf-vec buf)
  6.          (mod n (length (buf-vec buf)))))
  8. (defun (setf bref) (val buf n)
  9.   (setf (svref (buf-vec buf)
  10.                (mod n (length (buf-vec buf))))
  11.         val))
  13. (defun new-buf (len)
  14.   (make-buf :vec (make-array len)))
  16. (defun buf-insert (x b)
  17.   (setf (bref b (incf (buf-end b))) x))
  19. (defun buf-pop (b)
  20.   (prog1
  21.     (bref b (incf (buf-start b)))
  22.     (setf (buf-used b) (buf-start b)
  23.           (buf-new  b) (buf-end   b))))
  25. (defun buf-next (b)
  26.   (when (< (buf-used b) (buf-new b))
  27.     (bref b (incf (buf-used b)))))
  29. (defun buf-reset (b)
  30.   (setf (buf-used b) (buf-start b)
  31.         (buf-new  b) (buf-end   b)))
  33. (defun buf-clear (b)
  34.   (setf (buf-start b) -1 (buf-used  b) -1
  35.         (buf-new   b) -1 (buf-end   b) -1))
  37. (defun buf-flush (b str)
  38.   (do ((i (1+ (buf-used b)) (1+ i)))
  39.       ((> i (buf-end b)))
  40.     (princ (bref b i) str)))

图 7.1 环状缓冲区的操作

接下来我们需要两个特别为这个应用所写的函数: buf-next 从缓冲区读取一个值而不取出，而 buf-reset 重置 used 与 new 到初始值，分别是 start 与 end 。如果我们已经把至 new 的值全部读取完毕时， buf-next 返回 nil 。区别这个值与实际的值不会产生问题，因为我们只把值存在缓冲区。

最后 buf-flush 透过将所有作用的元素，写至由第二个参数所给入的流，而 buf-clear 通过重置所有的索引至 -1 将缓冲区清空。

在图 7.1 定义的函数被图 7.2 所使用，包含了字符串替换的代码。函数 file-subst 接受四个参数；一个查询字符串，一个替换字符串，一个输入文件以及一个输出文件。它创建了代表每个文件的流，然后调用 stream-subst 来完成实际的工作。

第二个函数 stream-subst 使用本节开始所勾勒的算法。它一次从输入流读一个字符。直到输入字符匹配要寻找的字符串时，直接写至输出流 (1)。当一个匹配开始时，有关字符在缓冲区 buf 排队等候 (2)。

变数 pos 指向我们想要匹配的字符在寻找字符串的所在位置。如果 pos 等于这个字符串的长度，我们有一个完整的匹配，则我们将替换字符串写至输出流，并清空缓冲区 (3)。如果在这之前匹配失败，我们可以将缓冲区的第一个元素取出，并写至输出流，之后我们重置缓冲区，并从 pos 等于 0 重新开始 (4)。

  1. (defun file-subst (old new file1 file2)
  2.   (with-open-file (in file1 :direction :input)
  3.      (with-open-file (out file2 :direction :output
  4.                                 :if-exists :supersede)
  5.        (stream-subst old new in out))))
  7. (defun stream-subst (old new in out)
  8.   (let* ((pos 0)
  9.          (len (length old))
  10.          (buf (new-buf len))
  11.          (from-buf nil))
  12.     (do ((c (read-char in nil :eof)
  13.             (or (setf from-buf (buf-next buf))
  14.                 (read-char in nil :eof))))
  15.         ((eql c :eof))
  16.       (cond ((char= c (char old pos))
  17.              (incf pos)
  18.              (cond ((= pos len)            ; 3
  19.                     (princ new out)
  20.                     (setf pos 0)
  21.                     (buf-clear buf))
  22.                    ((not from-buf)         ; 2
  23.                     (buf-insert c buf))))
  24.             ((zerop pos)                   ; 1
  25.              (princ c out)
  26.              (when from-buf
  27.                (buf-pop buf)
  28.                (buf-reset buf)))
  29.             (t                             ; 4
  30.              (unless from-buf
  31.                (buf-insert c buf))
  32.              (princ (buf-pop buf) out)
  33.              (buf-reset buf)
  34.              (setf pos 0))))
  35.     (buf-flush buf out)))

图 7.2 字符串替换

下列表格展示了当我们将文件中的 "baro" 替换成 "baric" 所发生的事，其中文件只有一个单字 "barbarous" :

CHARACTERSOURCEMATCHCASEOUTPUTBUFFER
bfileb2 b
afilea2 b a
rfiler2 b a r
bfileo4bb.a r b.
abufferb1aa.r b.
rbufferb1rr.b.
bbufferb1 r b:
afilea2 r b:a
rfiler2 r b:a
ofileo3baricr b:a r
ufileb1u 
afileb1s 

第一栏是当前字符 ── c 的值；第二栏显示是从缓冲区或是直接从输入流读取；第三栏显示需要匹配的字符 ── old 的第 posth 字符；第四栏显示那一个条件式 (case)被求值作为结果；第五栏显示被写至输出流的字符；而最后一栏显示缓冲区之后的内容。在最后一栏里， used 与 new 的位置一样，由一个冒号 ( : colon)表示。

在文件 "test1" 里有如下文字：

  1. The struggle between Liberty and Authority is the most conspicuous feature
  2. in the portions of history with which we are earliest familiar, particularly
  3. in that of Greece, Rome, and England.

在我们对 (file-subst " th" " z" "test1" "test2") 求值之后，读取文件 "test2" 为:

  1. The struggle between Liberty and Authority is ze most conspicuous feature
  2. in ze portions of history with which we are earliest familiar, particularly
  3. in zat of Greece, Rome, and England.

为了使这个例子尽可能的简单，图 7.2 的代码只将一个字符串换成另一个字符串。很容易扩展为搜索一个模式而不是一个字面字符串。你只需要做的是，将 char= 调用换成一个你想要的更通用的匹配函数调用。