core.clj

(ns trie.core
  (:refer-clojure :exclude (merge contains?))
  (:use clojure.test))

;; some generic trie (prefix tree) functions

(def box list)

(defn trie
  "Returns trie for single seq s"
  [s]
  (reduce (fn [m c] {c m})
	  {::end true}
	  (map box (reverse s))))

(defn merge
  "Merge tries. Used to build up a trie from many sequences.
  Example:

    (apply merge (map trie \"some\" \"list\" \"of\" \"strings\"))
  "
  [& tries]
  (apply merge-with merge tries))

(defn suffixes
  "Returns the trie of suffixes matching prefix string s"
  [trie s]
  (reduce get trie (map box s)))

(defn contains?
  "Returns true if trie contains seq s exactly"
  [trie s]
  (true? (::end (suffixes trie s))))

;; one test to rule them all

(deftest tries
  (let [trie-1 (trie "hi")
	trie-2 (merge trie-1 (trie "ho"))]
    (is (contains? trie-2 "ho"))
    (is (contains? trie-2 "hi"))
    (is (suffixes trie-2 "h"))
    (is (not (contains? trie-2 "h")))
    (is (not (contains? trie-2 "barf")))))