;; The markov chain algorithm from "The Practice of Programming"
;; by Brian W. Kernighan and Rob Pike
;;
;; Jeremy English 27-September-2006

(defpackage :markov
  (:use :cl)
  (:export :run-markov))

(in-package :markov)

(defun string-split (string char)
  "Returns a list of substrings of string
divided by char."
  (loop for i = 0 then (1+ j)
        as j = (position char string :start i)
        collect (subseq string i j)
        while j))

(defun load-hash (stream non-word)
  (let ((hash (make-hash-table :test 'equal))
        (w1 non-word)
        (w2 non-word))
    (loop for line = (read-line stream nil) while (not (null line)) do
          (let ((split-line (string-split line #\space)))
            (dolist (suf split-line)
              (let ((hash-value (gethash (cons w1 w2) hash)))
                (setf (gethash (cons w1 w2) hash)
                      (if hash-value
                          (cons suf hash-value)
                          (list suf))))
              (setf w1 w2) (setf w2 suf))))
    hash))

(defun run-markov (stream max-gen non-word)
  (let ((hash (load-hash stream non-word))
        (state (make-random-state t)))
    (labels ((print-word (count w1 w2)
               (cond ((= count max-gen) nil)
                     (t
                      (let* ((suf (gethash (cons w1 w2) hash))
                             (word (nth (random (length suf) state) suf)))
                        (unless (eq word non-word)
                          (format t "~a " word)
                          (print-word (1+ count) w2 word)))))))
      (print-word 0 non-word non-word))))