Trie.lisp

(in-package :trie)
(export '(make-trie
          trie-get
          trie-set
          trie-prefix-p))

(defun make-trie ()
  (make-hash-table))

(defun %trie-get (trie path)
  (dolist (entry path)
    (when (not (hash-table-p (gethash entry trie)))
      (setf (gethash entry trie) (make-trie)))
    (setf trie (gethash entry trie)))
  trie)

(defun trie-get (trie path)
  (gethash #\null (%trie-get trie path)))

(defun trie-set (trie path val)
  (when (not (eq (car (last path)) #\null))
    (setf path (append path '(#\null))))

  (loop for entry in path
       do
       (if (eq entry #\null)
	   (setf (gethash entry trie) val)
	   (progn
	     (setf (gethash entry trie) 
		   (or (gethash entry trie) 
		       (make-hash-table)))
	     (setf trie (gethash entry trie))))))

(defun trie-prefix-p (trie path)
  (loop for entry in path
     do
       (when (not (hash-table-p (gethash entry trie)))
	 (return))
       (setf trie (gethash entry trie))
       (setf path (rest path)))
  (list trie path))