rlm@10: ;;; seq_utils.clj -- Sequence utilities for Clojure
rlm@10: 
rlm@10: ;; by Stuart Sierra, http://stuartsierra.com/
rlm@10: ;; last updated March 2, 2009
rlm@10: 
rlm@10: ;; Copyright (c) Stuart Sierra, 2008. All rights reserved.  The use
rlm@10: ;; and distribution terms for this software are covered by the Eclipse
rlm@10: ;; Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
rlm@10: ;; which can be found in the file epl-v10.html at the root of this
rlm@10: ;; distribution.  By using this software in any fashion, you are
rlm@10: ;; agreeing to be bound by the terms of this license.  You must not
rlm@10: ;; remove this notice, or any other, from this software.
rlm@10: 
rlm@10: 
rlm@10: ;; Change Log
rlm@10: ;;
rlm@10: ;; DEPRECATED in 1.2. Some functions promoted to clojure.core and some
rlm@10: ;; moved to c.c.seq
rlm@10: ;;
rlm@10: ;; January 10, 2009 (Stuart Sierra):
rlm@10: ;;
rlm@10: ;; * BREAKING CHANGE: "includes?" now takes collection as first
rlm@10: ;;   argument.  This is more consistent with Clojure collection
rlm@10: ;;   functions; see discussion at http://groups.google.com/group/clojure/browse_thread/thread/8b2c8dc96b39ddd7/a8866d34b601ff43
rlm@10: ;;
rlm@10: 
rlm@10: (ns 
rlm@10:   ^{:author "Stuart Sierra (and others)",
rlm@10:     :deprecated "1.2"
rlm@10:     :doc "Sequence utilities for Clojure"}
rlm@10:   clojure.contrib.seq-utils
rlm@10:   (:import (java.util.concurrent LinkedBlockingQueue TimeUnit)
rlm@10:            (java.lang.ref WeakReference))
rlm@10:   (:refer-clojure :exclude [frequencies shuffle partition-by reductions partition-all group-by flatten]))
rlm@10: 
rlm@10: 
rlm@10: ;; 'flatten' written by Rich Hickey,
rlm@10: ;; see http://groups.google.com/group/clojure/msg/385098fabfcaad9b
rlm@10: (defn flatten
rlm@10:   "DEPRECATED. Prefer clojure.core version.
rlm@10:   Takes any nested combination of sequential things (lists, vectors,
rlm@10:   etc.) and returns their contents as a single, flat sequence.
rlm@10:   (flatten nil) returns nil."
rlm@10:   {:deprecated "1.2"}
rlm@10:   [x]
rlm@10:   (filter (complement sequential?)
rlm@10:           (rest (tree-seq sequential? seq x))))
rlm@10: 
rlm@10: (defn separate
rlm@10:   "Returns a vector:
rlm@10:    [ (filter f s), (filter (complement f) s) ]"
rlm@10:   [f s]
rlm@10:   [(filter f s) (filter (complement f) s)])
rlm@10: 
rlm@10: (defn indexed
rlm@10:   "Returns a lazy sequence of [index, item] pairs, where items come
rlm@10:   from 's' and indexes count up from zero.
rlm@10: 
rlm@10:   (indexed '(a b c d))  =>  ([0 a] [1 b] [2 c] [3 d])"
rlm@10:   [s]
rlm@10:   (map vector (iterate inc 0) s))
rlm@10: 
rlm@10: ;; group-by written by Rich Hickey;
rlm@10: ;; see http://paste.lisp.org/display/64190
rlm@10: (defn group-by 
rlm@10:   "DEPRECATED. Prefer clojure.core version.
rlm@10:    Returns a sorted map of the elements of coll keyed by the result of
rlm@10:   f on each element. The value at each key will be a vector of the
rlm@10:   corresponding elements, in the order they appeared in coll."
rlm@10:   {:deprecated "1.2"}
rlm@10:   [f coll]
rlm@10:   (reduce
rlm@10:    (fn [ret x]
rlm@10:      (let [k (f x)]
rlm@10:        (assoc ret k (conj (get ret k []) x))))
rlm@10:    (sorted-map) coll))
rlm@10: 
rlm@10: ;; partition-by originally written by Rich Hickey;
rlm@10: ;; modified by Stuart Sierra
rlm@10: (defn partition-by
rlm@10:   "DEPRECATED. Prefer clojure.core version.
rlm@10:    Applies f to each value in coll, splitting it each time f returns
rlm@10:    a new value.  Returns a lazy seq of lazy seqs."
rlm@10:   {:deprecated "1.2"}
rlm@10:   [f coll]
rlm@10:   (when-let [s (seq coll)]
rlm@10:     (let [fst (first s)
rlm@10:           fv (f fst)
rlm@10:           run (cons fst (take-while #(= fv (f %)) (rest s)))]
rlm@10:       (lazy-seq
rlm@10:        (cons run (partition-by f (drop (count run) s)))))))
rlm@10: 
rlm@10: (defn frequencies
rlm@10:   "DEPRECATED. Prefer clojure.core version.
rlm@10:   Returns a map from distinct items in coll to the number of times
rlm@10:   they appear."
rlm@10:   {:deprecated "1.2"}
rlm@10:   [coll]
rlm@10:   (reduce (fn [counts x]
rlm@10:               (assoc counts x (inc (get counts x 0))))
rlm@10:           {} coll))
rlm@10: 
rlm@10: ;; recursive sequence helpers by Christophe Grand
rlm@10: ;; see http://clj-me.blogspot.com/2009/01/recursive-seqs.html
rlm@10: (defmacro rec-seq 
rlm@10:  "Similar to lazy-seq but binds the resulting seq to the supplied 
rlm@10:   binding-name, allowing for recursive expressions."
rlm@10:  [binding-name & body]
rlm@10:   `(let [s# (atom nil)]
rlm@10:      (reset! s# (lazy-seq (let [~binding-name @s#] ~@body)))))
rlm@10:              
rlm@10: (defmacro rec-cat 
rlm@10:  "Similar to lazy-cat but binds the resulting sequence to the supplied 
rlm@10:   binding-name, allowing for recursive expressions."
rlm@10:  [binding-name & exprs]
rlm@10:   `(rec-seq ~binding-name (lazy-cat ~@exprs)))
rlm@10:          
rlm@10:      
rlm@10: ;; reductions by Chris Houser
rlm@10: ;; see http://groups.google.com/group/clojure/browse_thread/thread/3edf6e82617e18e0/58d9e319ad92aa5f?#58d9e319ad92aa5f
rlm@10: (defn reductions
rlm@10:   "DEPRECATED. Prefer clojure.core version.
rlm@10:   Returns a lazy seq of the intermediate values of the reduction (as
rlm@10:   per reduce) of coll by f, starting with init."
rlm@10:   {:deprecated "1.2"}
rlm@10:   ([f coll]
rlm@10:    (if (seq coll)
rlm@10:      (rec-seq self (cons (first coll) (map f self (rest coll))))
rlm@10:      (cons (f) nil)))
rlm@10:   ([f init coll]
rlm@10:    (rec-seq self (cons init (map f self coll)))))
rlm@10: 
rlm@10: (defn rotations
rlm@10:   "Returns a lazy seq of all rotations of a seq"
rlm@10:   [x]
rlm@10:   (if (seq x)
rlm@10:     (map
rlm@10:      (fn [n _]
rlm@10:        (lazy-cat (drop n x) (take n x)))
rlm@10:      (iterate inc 0) x)
rlm@10:     (list nil)))
rlm@10: 
rlm@10: (defn partition-all
rlm@10:   "DEPRECATED. Prefer clojure.core version.
rlm@10:   Returns a lazy sequence of lists like clojure.core/partition, but may
rlm@10:   include lists with fewer than n items at the end."
rlm@10:   {:deprecated "1.2"}
rlm@10:   ([n coll]
rlm@10:      (partition-all n n coll))
rlm@10:   ([n step coll]
rlm@10:      (lazy-seq
rlm@10:       (when-let [s (seq coll)]
rlm@10:         (cons (take n s) (partition-all n step (drop step s)))))))
rlm@10:   
rlm@10: (defn shuffle
rlm@10:   "DEPRECATED. Prefer clojure.core version.
rlm@10:   Return a random permutation of coll"
rlm@10:   {:deprecated "1.2"}
rlm@10:   [coll]
rlm@10:   (let [l (java.util.ArrayList. coll)]
rlm@10:     (java.util.Collections/shuffle l)
rlm@10:     (seq l)))
rlm@10: 
rlm@10: (defn rand-elt
rlm@10:   "DEPRECATED. Prefer clojure.core/rand-nth.
rlm@10:    Return a random element of this seq"
rlm@10:   {:deprecated "1.2"}
rlm@10:   [s]
rlm@10:   (nth s (rand-int (count s))))
rlm@10: 
rlm@10: 
rlm@10: ;; seq-on written by Konrad Hinsen
rlm@10: (defmulti seq-on
rlm@10:   "Returns a seq on the object s. Works like the built-in seq but as
rlm@10:    a multimethod that can have implementations for new classes and types."
rlm@10:   {:arglists '([s])}
rlm@10:   type)
rlm@10: 
rlm@10: (defmethod seq-on :default
rlm@10:   [s]
rlm@10:   (seq s))
rlm@10: 
rlm@10: 
rlm@10: (defn find-first
rlm@10:   "Returns the first item of coll for which (pred item) returns logical true.
rlm@10:   Consumes sequences up to the first match, will consume the entire sequence
rlm@10:   and return nil if no match is found."
rlm@10:   [pred coll]
rlm@10:   (first (filter pred coll)))
rlm@10: 
rlm@10: ; based on work related to Rich Hickey's seque.
rlm@10: ; blame Chouser for anything broken or ugly.
rlm@10: (defn fill-queue
rlm@10:   "filler-func will be called in another thread with a single arg
rlm@10:   'fill'.  filler-func may call fill repeatedly with one arg each
rlm@10:   time which will be pushed onto a queue, blocking if needed until
rlm@10:   this is possible.  fill-queue will return a lazy seq of the values
rlm@10:   filler-func has pushed onto the queue, blocking if needed until each
rlm@10:   next element becomes available.  filler-func's return value is ignored."
rlm@10:   ([filler-func & optseq]
rlm@10:     (let [opts (apply array-map optseq)
rlm@10:           apoll (:alive-poll opts 1)
rlm@10:           q (LinkedBlockingQueue. (:queue-size opts 1))
rlm@10:           NIL (Object.) ;nil sentinel since LBQ doesn't support nils
rlm@10:           weak-target (Object.)
rlm@10:           alive? (WeakReference. weak-target)
rlm@10:           fill (fn fill [x]
rlm@10:                  (if (.get alive?)
rlm@10:                    (if (.offer q (if (nil? x) NIL x) apoll TimeUnit/SECONDS)
rlm@10:                      x
rlm@10:                      (recur x))
rlm@10:                    (throw (Exception. "abandoned"))))
rlm@10:           f (future
rlm@10:               (try
rlm@10:                 (filler-func fill)
rlm@10:                 (finally
rlm@10:                   (.put q q))) ;q itself is eos sentinel
rlm@10:               nil)] ; set future's value to nil
rlm@10:       ((fn drain []
rlm@10:          weak-target ; force closing over this object
rlm@10:          (lazy-seq
rlm@10:            (let [x (.take q)]
rlm@10:              (if (identical? x q)
rlm@10:                @f  ;will be nil, touch just to propagate errors
rlm@10:                (cons (if (identical? x NIL) nil x)
rlm@10:                      (drain))))))))))
rlm@10: 
rlm@10: (defn positions
rlm@10:   "Returns a lazy sequence containing the positions at which pred
rlm@10:    is true for items in coll."
rlm@10:   [pred coll]
rlm@10:   (for [[idx elt] (indexed coll) :when (pred elt)] idx))
rlm@10: 
rlm@10: (defn includes?
rlm@10:   "Returns true if coll contains something equal (with =) to x,
rlm@10:   in linear time. Deprecated. Prefer 'contains?' for key testing,
rlm@10:   or 'some' for ad hoc linear searches."
rlm@10:   {:deprecated "1.2"}
rlm@10:   [coll x]
rlm@10:   (boolean (some (fn [y] (= y x)) coll)))
rlm@10: 
rlm@10: 
rlm@10: 
rlm@10: