(set! *warn-on-reflection* true)

(defn bfs-seq [branch? children root]
  "Same as tree-seq but walks the tree breadth-first instead
   of depth-first."
  (let [walk (fn walk [queue]
               (when-let [node (peek queue)]
                 (lazy-seq
                  (cons node (walk (into (pop queue)
                                         (when (branch? node)
                                           (children node))))))))]
    (walk (conj clojure.lang.PersistentQueue/EMPTY root))))

;; Not lazy! Just for comparing against bfs-seq.
(defn bfs-unlazy [branch? children root]
  (loop [branches []
         queue (conj clojure.lang.PersistentQueue/EMPTY root)]
    (if-let [node (peek queue)]
      (recur (conj branches node)
             (into (pop queue) (children node)))
      branches)))

(defn bfs-file-seq [dir]
  "Like file-seq but walks the file tree breadth-first instead
   of depth-first"
  (bfs-seq
   (fn [#^java.io.File f] (.isDirectory f))
   (fn [#^java.io.File d] (seq (.listFiles d)))
   dir))

;; TODO: strict dot file & wildcard matching; use StringBuilder?
(defn glob->regex [s]
  "Takes a glob-format string and returns a regex."
  (let [stream (java.io.StringReader. s)]
    (loop [i (.read stream)
           re ""
           curly-depth 0]
      (let [c (char i)
            j (.read stream)]
        (cond
         (= i -1) (re-pattern re)
         (= c \\) (recur (.read stream) (str re c (char j)) curly-depth)
         (= c \*) (recur j (str re ".*") curly-depth)
         (= c \?) (recur j (str re \.) curly-depth)
         (= c \{) (recur j (str re \() (inc curly-depth))
         (= c \}) (recur j (str re \)) (dec curly-depth))
         (and (= c \,) (< 0 curly-depth)) (recur j (str re \|) curly-depth)
         (#{\. \( \) \| \+ \^ \$ \@ \%} c) (recur j (str re \\ c) curly-depth) 
         :else (recur j (str re c) curly-depth))))))

;; TODO: be smarter about path elements that have no patterns in them
(defn glob [pat]
  "Takes a glob pattern and returns a list of files that match, recursing
   as much as necessary. The current directory is assumed unless an
   absolute path is given."
  (let [re (glob->regex pat)
        start-path (if (= \/ (first pat)) "/" ".")
        levels #(count (.split #"/" %))
        pat-levels (if (= start-path ".") (inc (levels pat)) (levels pat))]
    (filter (fn [#^java.io.File f]
              (and (= pat-levels (levels (.getPath f)))
                   (re-matches re (.getPath f))))
            (take-while (fn [#^java.io.File f]
                          (>= pat-levels (levels (.getPath f))))
                        (bfs-file-seq (java.io.File. start-path))))))