1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/clojure/contrib/seq.clj	Sat Aug 21 06:25:44 2010 -0400
     1.3 @@ -0,0 +1,238 @@
     1.4 +;;; seq_utils.clj -- Sequence utilities for Clojure
     1.5 +
     1.6 +;; by Stuart Sierra, http://stuartsierra.com/
     1.7 +;; last updated March 2, 2009
     1.8 +
     1.9 +;; Copyright (c) Stuart Sierra, 2008. All rights reserved.  The use
    1.10 +;; and distribution terms for this software are covered by the Eclipse
    1.11 +;; Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
    1.12 +;; which can be found in the file epl-v10.html at the root of this
    1.13 +;; distribution.  By using this software in any fashion, you are
    1.14 +;; agreeing to be bound by the terms of this license.  You must not
    1.15 +;; remove this notice, or any other, from this software.
    1.16 +
    1.17 +
    1.18 +;; Change Log
    1.19 +;;
    1.20 +;; January 10, 2009 (Stuart Sierra):
    1.21 +;;
    1.22 +;; * BREAKING CHANGE: "includes?" now takes collection as first
    1.23 +;;   argument.  This is more consistent with Clojure collection
    1.24 +;;   functions; see discussion at http://groups.google.com/group/clojure/browse_thread/thread/8b2c8dc96b39ddd7/a8866d34b601ff43
    1.25 +
    1.26 +
    1.27 +(ns 
    1.28 +  ^{:author "Stuart Sierra (and others)",
    1.29 +     :doc "Sequence utilities for Clojure"}
    1.30 +  clojure.contrib.seq
    1.31 +  (:import (java.util.concurrent LinkedBlockingQueue TimeUnit)
    1.32 +           (java.lang.ref WeakReference))
    1.33 +  (:refer-clojure :exclude [frequencies shuffle partition-by reductions partition-all group-by flatten]))
    1.34 +
    1.35 +
    1.36 +;; 'flatten' written by Rich Hickey,
    1.37 +;; see http://groups.google.com/group/clojure/msg/385098fabfcaad9b
    1.38 +(defn flatten
    1.39 +  "DEPRECATED. Prefer clojure.core version.
    1.40 +  Takes any nested combination of sequential things (lists, vectors,
    1.41 +  etc.) and returns their contents as a single, flat sequence.
    1.42 +  (flatten nil) returns nil."
    1.43 +  {:deprecated "1.2"}
    1.44 +  [x]
    1.45 +  (filter (complement sequential?)
    1.46 +          (rest (tree-seq sequential? seq x))))
    1.47 +
    1.48 +(defn separate
    1.49 +  "Returns a vector:
    1.50 +   [ (filter f s), (filter (complement f) s) ]"
    1.51 +  [f s]
    1.52 +  [(filter f s) (filter (complement f) s)])
    1.53 +
    1.54 +(defn indexed
    1.55 +  "Returns a lazy sequence of [index, item] pairs, where items come
    1.56 +  from 's' and indexes count up from zero.
    1.57 +
    1.58 +  (indexed '(a b c d))  =>  ([0 a] [1 b] [2 c] [3 d])"
    1.59 +  [s]
    1.60 +  (map vector (iterate inc 0) s))
    1.61 +
    1.62 +;; group-by written by Rich Hickey;
    1.63 +;; see http://paste.lisp.org/display/64190
    1.64 +(defn group-by 
    1.65 +  "DEPRECATED. Prefer clojure.core version.
    1.66 +   Returns a sorted map of the elements of coll keyed by the result of
    1.67 +  f on each element. The value at each key will be a vector of the
    1.68 +  corresponding elements, in the order they appeared in coll."
    1.69 +  {:deprecated "1.2"}
    1.70 +  [f coll]
    1.71 +  (reduce
    1.72 +   (fn [ret x]
    1.73 +     (let [k (f x)]
    1.74 +       (assoc ret k (conj (get ret k []) x))))
    1.75 +   (sorted-map) coll))
    1.76 +
    1.77 +;; partition-by originally written by Rich Hickey;
    1.78 +;; modified by Stuart Sierra
    1.79 +(defn partition-by
    1.80 +  "DEPRECATED. Prefer clojure.core version.
    1.81 +   Applies f to each value in coll, splitting it each time f returns
    1.82 +   a new value.  Returns a lazy seq of lazy seqs."
    1.83 +  {:deprecated "1.2"}
    1.84 +  [f coll]
    1.85 +  (when-let [s (seq coll)]
    1.86 +    (let [fst (first s)
    1.87 +          fv (f fst)
    1.88 +          run (cons fst (take-while #(= fv (f %)) (rest s)))]
    1.89 +      (lazy-seq
    1.90 +       (cons run (partition-by f (drop (count run) s)))))))
    1.91 +
    1.92 +(defn frequencies
    1.93 +  "DEPRECATED. Prefer clojure.core version.
    1.94 +  Returns a map from distinct items in coll to the number of times
    1.95 +  they appear."
    1.96 +  {:deprecated "1.2"}
    1.97 +  [coll]
    1.98 +  (reduce (fn [counts x]
    1.99 +              (assoc counts x (inc (get counts x 0))))
   1.100 +          {} coll))
   1.101 +
   1.102 +;; recursive sequence helpers by Christophe Grand
   1.103 +;; see http://clj-me.blogspot.com/2009/01/recursive-seqs.html
   1.104 +(defmacro rec-seq 
   1.105 + "Similar to lazy-seq but binds the resulting seq to the supplied 
   1.106 +  binding-name, allowing for recursive expressions."
   1.107 + [binding-name & body]
   1.108 +  `(let [s# (atom nil)]
   1.109 +     (reset! s# (lazy-seq (let [~binding-name @s#] ~@body)))))
   1.110 +             
   1.111 +(defmacro rec-cat 
   1.112 + "Similar to lazy-cat but binds the resulting sequence to the supplied 
   1.113 +  binding-name, allowing for recursive expressions."
   1.114 + [binding-name & exprs]
   1.115 +  `(rec-seq ~binding-name (lazy-cat ~@exprs)))
   1.116 +         
   1.117 +     
   1.118 +;; reductions by Chris Houser
   1.119 +;; see http://groups.google.com/group/clojure/browse_thread/thread/3edf6e82617e18e0/58d9e319ad92aa5f?#58d9e319ad92aa5f
   1.120 +(defn reductions
   1.121 +  "DEPRECATED. Prefer clojure.core version.
   1.122 +  Returns a lazy seq of the intermediate values of the reduction (as
   1.123 +  per reduce) of coll by f, starting with init."
   1.124 +  {:deprecated "1.2"}
   1.125 +  ([f coll]
   1.126 +   (if (seq coll)
   1.127 +     (rec-seq self (cons (first coll) (map f self (rest coll))))
   1.128 +     (cons (f) nil)))
   1.129 +  ([f init coll]
   1.130 +   (rec-seq self (cons init (map f self coll)))))
   1.131 +
   1.132 +(defn rotations
   1.133 +  "Returns a lazy seq of all rotations of a seq"
   1.134 +  [x]
   1.135 +  (if (seq x)
   1.136 +    (map
   1.137 +     (fn [n _]
   1.138 +       (lazy-cat (drop n x) (take n x)))
   1.139 +     (iterate inc 0) x)
   1.140 +    (list nil)))
   1.141 +
   1.142 +(defn partition-all
   1.143 +  "DEPRECATED. Prefer clojure.core version.
   1.144 +  Returns a lazy sequence of lists like clojure.core/partition, but may
   1.145 +  include lists with fewer than n items at the end."
   1.146 +  {:deprecated "1.2"}
   1.147 +  ([n coll]
   1.148 +     (partition-all n n coll))
   1.149 +  ([n step coll]
   1.150 +     (lazy-seq
   1.151 +      (when-let [s (seq coll)]
   1.152 +        (cons (take n s) (partition-all n step (drop step s)))))))
   1.153 +  
   1.154 +(defn shuffle
   1.155 +  "DEPRECATED. Prefer clojure.core version.
   1.156 +  Return a random permutation of coll"
   1.157 +  {:deprecated "1.2"}
   1.158 +  [coll]
   1.159 +  (let [l (java.util.ArrayList. coll)]
   1.160 +    (java.util.Collections/shuffle l)
   1.161 +    (seq l)))
   1.162 +
   1.163 +(defn rand-elt
   1.164 +  "DEPRECATED. Prefer clojure.core/rand-nth.
   1.165 +   Return a random element of this seq"
   1.166 +  {:deprecated "1.2"}
   1.167 +  [s]
   1.168 +  (nth s (rand-int (count s))))
   1.169 +
   1.170 +;; seq-on written by Konrad Hinsen
   1.171 +(defmulti seq-on
   1.172 +  "Returns a seq on the object s. Works like the built-in seq but as
   1.173 +   a multimethod that can have implementations for new classes and types."
   1.174 +  {:arglists '([s])}
   1.175 +  type)
   1.176 +
   1.177 +(defmethod seq-on :default
   1.178 +  [s]
   1.179 +  (seq s))
   1.180 +
   1.181 +
   1.182 +(defn find-first
   1.183 +  "Returns the first item of coll for which (pred item) returns logical true.
   1.184 +  Consumes sequences up to the first match, will consume the entire sequence
   1.185 +  and return nil if no match is found."
   1.186 +  [pred coll]
   1.187 +  (first (filter pred coll)))
   1.188 +
   1.189 +; based on work related to Rich Hickey's seque.
   1.190 +; blame Chouser for anything broken or ugly.
   1.191 +(defn fill-queue
   1.192 +  "filler-func will be called in another thread with a single arg
   1.193 +  'fill'.  filler-func may call fill repeatedly with one arg each
   1.194 +  time which will be pushed onto a queue, blocking if needed until
   1.195 +  this is possible.  fill-queue will return a lazy seq of the values
   1.196 +  filler-func has pushed onto the queue, blocking if needed until each
   1.197 +  next element becomes available.  filler-func's return value is ignored."
   1.198 +  ([filler-func & optseq]
   1.199 +    (let [opts (apply array-map optseq)
   1.200 +          apoll (:alive-poll opts 1)
   1.201 +          q (LinkedBlockingQueue. (:queue-size opts 1))
   1.202 +          NIL (Object.) ;nil sentinel since LBQ doesn't support nils
   1.203 +          weak-target (Object.)
   1.204 +          alive? (WeakReference. weak-target)
   1.205 +          fill (fn fill [x]
   1.206 +                 (if (.get alive?)
   1.207 +                   (if (.offer q (if (nil? x) NIL x) apoll TimeUnit/SECONDS)
   1.208 +                     x
   1.209 +                     (recur x))
   1.210 +                   (throw (Exception. "abandoned"))))
   1.211 +          f (future
   1.212 +              (try
   1.213 +                (filler-func fill)
   1.214 +                (finally
   1.215 +                  (.put q q))) ;q itself is eos sentinel
   1.216 +              nil)] ; set future's value to nil
   1.217 +      ((fn drain []
   1.218 +         weak-target ; force closing over this object
   1.219 +         (lazy-seq
   1.220 +           (let [x (.take q)]
   1.221 +             (if (identical? x q)
   1.222 +               @f  ;will be nil, touch just to propagate errors
   1.223 +               (cons (if (identical? x NIL) nil x)
   1.224 +                     (drain))))))))))
   1.225 +
   1.226 +(defn positions
   1.227 +  "Returns a lazy sequence containing the positions at which pred
   1.228 +   is true for items in coll."
   1.229 +  [pred coll]
   1.230 +  (for [[idx elt] (indexed coll) :when (pred elt)] idx))
   1.231 +
   1.232 +(defn includes?
   1.233 +  "Returns true if coll contains something equal (with =) to x,
   1.234 +  in linear time. Deprecated. Prefer 'contains?' for key testing,
   1.235 +  or 'some' for ad hoc linear searches."
   1.236 +  {:deprecated "1.2"}
   1.237 +  [coll x]
   1.238 +  (boolean (some (fn [y] (= y x)) coll)))
   1.239 +
   1.240 +
   1.241 +