Mercurial > lasercutter

annotate src/clojure/contrib/seq_utils.clj @ 10:ef7dbbd6452c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added clojure source goodness
author Robert McIntyre <rlm@mit.edu>
date Sat, 21 Aug 2010 06:25:44 -0400
parents
children
rev   line source
rlm@10 1 ;;; seq_utils.clj -- Sequence utilities for Clojure
rlm@10 2
rlm@10 3 ;; by Stuart Sierra, http://stuartsierra.com/
rlm@10 4 ;; last updated March 2, 2009
rlm@10 5
rlm@10 6 ;; Copyright (c) Stuart Sierra, 2008. All rights reserved. The use
rlm@10 7 ;; and distribution terms for this software are covered by the Eclipse
rlm@10 8 ;; Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
rlm@10 9 ;; which can be found in the file epl-v10.html at the root of this
rlm@10 10 ;; distribution. By using this software in any fashion, you are
rlm@10 11 ;; agreeing to be bound by the terms of this license. You must not
rlm@10 12 ;; remove this notice, or any other, from this software.
rlm@10 13
rlm@10 14
rlm@10 15 ;; Change Log
rlm@10 16 ;;
rlm@10 17 ;; DEPRECATED in 1.2. Some functions promoted to clojure.core and some
rlm@10 18 ;; moved to c.c.seq
rlm@10 19 ;;
rlm@10 20 ;; January 10, 2009 (Stuart Sierra):
rlm@10 21 ;;
rlm@10 22 ;; * BREAKING CHANGE: "includes?" now takes collection as first
rlm@10 23 ;; argument. This is more consistent with Clojure collection
rlm@10 24 ;; functions; see discussion at http://groups.google.com/group/clojure/browse_thread/thread/8b2c8dc96b39ddd7/a8866d34b601ff43
rlm@10 25 ;;
rlm@10 26
rlm@10 27 (ns
rlm@10 28 ^{:author "Stuart Sierra (and others)",
rlm@10 29 :deprecated "1.2"
rlm@10 30 :doc "Sequence utilities for Clojure"}
rlm@10 31 clojure.contrib.seq-utils
rlm@10 32 (:import (java.util.concurrent LinkedBlockingQueue TimeUnit)
rlm@10 33 (java.lang.ref WeakReference))
rlm@10 34 (:refer-clojure :exclude [frequencies shuffle partition-by reductions partition-all group-by flatten]))
rlm@10 35
rlm@10 36
rlm@10 37 ;; 'flatten' written by Rich Hickey,
rlm@10 38 ;; see http://groups.google.com/group/clojure/msg/385098fabfcaad9b
rlm@10 39 (defn flatten
rlm@10 40 "DEPRECATED. Prefer clojure.core version.
rlm@10 41 Takes any nested combination of sequential things (lists, vectors,
rlm@10 42 etc.) and returns their contents as a single, flat sequence.
rlm@10 43 (flatten nil) returns nil."
rlm@10 44 {:deprecated "1.2"}
rlm@10 45 [x]
rlm@10 46 (filter (complement sequential?)
rlm@10 47 (rest (tree-seq sequential? seq x))))
rlm@10 48
rlm@10 49 (defn separate
rlm@10 50 "Returns a vector:
rlm@10 51 [ (filter f s), (filter (complement f) s) ]"
rlm@10 52 [f s]
rlm@10 53 [(filter f s) (filter (complement f) s)])
rlm@10 54
rlm@10 55 (defn indexed
rlm@10 56 "Returns a lazy sequence of [index, item] pairs, where items come
rlm@10 57 from 's' and indexes count up from zero.
rlm@10 58
rlm@10 59 (indexed '(a b c d)) => ([0 a] [1 b] [2 c] [3 d])"
rlm@10 60 [s]
rlm@10 61 (map vector (iterate inc 0) s))
rlm@10 62
rlm@10 63 ;; group-by written by Rich Hickey;
rlm@10 64 ;; see http://paste.lisp.org/display/64190
rlm@10 65 (defn group-by
rlm@10 66 "DEPRECATED. Prefer clojure.core version.
rlm@10 67 Returns a sorted map of the elements of coll keyed by the result of
rlm@10 68 f on each element. The value at each key will be a vector of the
rlm@10 69 corresponding elements, in the order they appeared in coll."
rlm@10 70 {:deprecated "1.2"}
rlm@10 71 [f coll]
rlm@10 72 (reduce
rlm@10 73 (fn [ret x]
rlm@10 74 (let [k (f x)]
rlm@10 75 (assoc ret k (conj (get ret k []) x))))
rlm@10 76 (sorted-map) coll))
rlm@10 77
rlm@10 78 ;; partition-by originally written by Rich Hickey;
rlm@10 79 ;; modified by Stuart Sierra
rlm@10 80 (defn partition-by
rlm@10 81 "DEPRECATED. Prefer clojure.core version.
rlm@10 82 Applies f to each value in coll, splitting it each time f returns
rlm@10 83 a new value. Returns a lazy seq of lazy seqs."
rlm@10 84 {:deprecated "1.2"}
rlm@10 85 [f coll]
rlm@10 86 (when-let [s (seq coll)]
rlm@10 87 (let [fst (first s)
rlm@10 88 fv (f fst)
rlm@10 89 run (cons fst (take-while #(= fv (f %)) (rest s)))]
rlm@10 90 (lazy-seq
rlm@10 91 (cons run (partition-by f (drop (count run) s)))))))
rlm@10 92
rlm@10 93 (defn frequencies
rlm@10 94 "DEPRECATED. Prefer clojure.core version.
rlm@10 95 Returns a map from distinct items in coll to the number of times
rlm@10 96 they appear."
rlm@10 97 {:deprecated "1.2"}
rlm@10 98 [coll]
rlm@10 99 (reduce (fn [counts x]
rlm@10 100 (assoc counts x (inc (get counts x 0))))
rlm@10 101 {} coll))
rlm@10 102
rlm@10 103 ;; recursive sequence helpers by Christophe Grand
rlm@10 104 ;; see http://clj-me.blogspot.com/2009/01/recursive-seqs.html
rlm@10 105 (defmacro rec-seq
rlm@10 106 "Similar to lazy-seq but binds the resulting seq to the supplied
rlm@10 107 binding-name, allowing for recursive expressions."
rlm@10 108 [binding-name & body]
rlm@10 109 `(let [s# (atom nil)]
rlm@10 110 (reset! s# (lazy-seq (let [~binding-name @s#] ~@body)))))
rlm@10 111
rlm@10 112 (defmacro rec-cat
rlm@10 113 "Similar to lazy-cat but binds the resulting sequence to the supplied
rlm@10 114 binding-name, allowing for recursive expressions."
rlm@10 115 [binding-name & exprs]
rlm@10 116 `(rec-seq ~binding-name (lazy-cat ~@exprs)))
rlm@10 117
rlm@10 118
rlm@10 119 ;; reductions by Chris Houser
rlm@10 120 ;; see http://groups.google.com/group/clojure/browse_thread/thread/3edf6e82617e18e0/58d9e319ad92aa5f?#58d9e319ad92aa5f
rlm@10 121 (defn reductions
rlm@10 122 "DEPRECATED. Prefer clojure.core version.
rlm@10 123 Returns a lazy seq of the intermediate values of the reduction (as
rlm@10 124 per reduce) of coll by f, starting with init."
rlm@10 125 {:deprecated "1.2"}
rlm@10 126 ([f coll]
rlm@10 127 (if (seq coll)
rlm@10 128 (rec-seq self (cons (first coll) (map f self (rest coll))))
rlm@10 129 (cons (f) nil)))
rlm@10 130 ([f init coll]
rlm@10 131 (rec-seq self (cons init (map f self coll)))))
rlm@10 132
rlm@10 133 (defn rotations
rlm@10 134 "Returns a lazy seq of all rotations of a seq"
rlm@10 135 [x]
rlm@10 136 (if (seq x)
rlm@10 137 (map
rlm@10 138 (fn [n _]
rlm@10 139 (lazy-cat (drop n x) (take n x)))
rlm@10 140 (iterate inc 0) x)
rlm@10 141 (list nil)))
rlm@10 142
rlm@10 143 (defn partition-all
rlm@10 144 "DEPRECATED. Prefer clojure.core version.
rlm@10 145 Returns a lazy sequence of lists like clojure.core/partition, but may
rlm@10 146 include lists with fewer than n items at the end."
rlm@10 147 {:deprecated "1.2"}
rlm@10 148 ([n coll]
rlm@10 149 (partition-all n n coll))
rlm@10 150 ([n step coll]
rlm@10 151 (lazy-seq
rlm@10 152 (when-let [s (seq coll)]
rlm@10 153 (cons (take n s) (partition-all n step (drop step s)))))))
rlm@10 154
rlm@10 155 (defn shuffle
rlm@10 156 "DEPRECATED. Prefer clojure.core version.
rlm@10 157 Return a random permutation of coll"
rlm@10 158 {:deprecated "1.2"}
rlm@10 159 [coll]
rlm@10 160 (let [l (java.util.ArrayList. coll)]
rlm@10 161 (java.util.Collections/shuffle l)
rlm@10 162 (seq l)))
rlm@10 163
rlm@10 164 (defn rand-elt
rlm@10 165 "DEPRECATED. Prefer clojure.core/rand-nth.
rlm@10 166 Return a random element of this seq"
rlm@10 167 {:deprecated "1.2"}
rlm@10 168 [s]
rlm@10 169 (nth s (rand-int (count s))))
rlm@10 170
rlm@10 171
rlm@10 172 ;; seq-on written by Konrad Hinsen
rlm@10 173 (defmulti seq-on
rlm@10 174 "Returns a seq on the object s. Works like the built-in seq but as
rlm@10 175 a multimethod that can have implementations for new classes and types."
rlm@10 176 {:arglists '([s])}
rlm@10 177 type)
rlm@10 178
rlm@10 179 (defmethod seq-on :default
rlm@10 180 [s]
rlm@10 181 (seq s))
rlm@10 182
rlm@10 183
rlm@10 184 (defn find-first
rlm@10 185 "Returns the first item of coll for which (pred item) returns logical true.
rlm@10 186 Consumes sequences up to the first match, will consume the entire sequence
rlm@10 187 and return nil if no match is found."
rlm@10 188 [pred coll]
rlm@10 189 (first (filter pred coll)))
rlm@10 190
rlm@10 191 ; based on work related to Rich Hickey's seque.
rlm@10 192 ; blame Chouser for anything broken or ugly.
rlm@10 193 (defn fill-queue
rlm@10 194 "filler-func will be called in another thread with a single arg
rlm@10 195 'fill'. filler-func may call fill repeatedly with one arg each
rlm@10 196 time which will be pushed onto a queue, blocking if needed until
rlm@10 197 this is possible. fill-queue will return a lazy seq of the values
rlm@10 198 filler-func has pushed onto the queue, blocking if needed until each
rlm@10 199 next element becomes available. filler-func's return value is ignored."
rlm@10 200 ([filler-func & optseq]
rlm@10 201 (let [opts (apply array-map optseq)
rlm@10 202 apoll (:alive-poll opts 1)
rlm@10 203 q (LinkedBlockingQueue. (:queue-size opts 1))
rlm@10 204 NIL (Object.) ;nil sentinel since LBQ doesn't support nils
rlm@10 205 weak-target (Object.)
rlm@10 206 alive? (WeakReference. weak-target)
rlm@10 207 fill (fn fill [x]
rlm@10 208 (if (.get alive?)
rlm@10 209 (if (.offer q (if (nil? x) NIL x) apoll TimeUnit/SECONDS)
rlm@10 210 x
rlm@10 211 (recur x))
rlm@10 212 (throw (Exception. "abandoned"))))
rlm@10 213 f (future
rlm@10 214 (try
rlm@10 215 (filler-func fill)
rlm@10 216 (finally
rlm@10 217 (.put q q))) ;q itself is eos sentinel
rlm@10 218 nil)] ; set future's value to nil
rlm@10 219 ((fn drain []
rlm@10 220 weak-target ; force closing over this object
rlm@10 221 (lazy-seq
rlm@10 222 (let [x (.take q)]
rlm@10 223 (if (identical? x q)
rlm@10 224 @f ;will be nil, touch just to propagate errors
rlm@10 225 (cons (if (identical? x NIL) nil x)
rlm@10 226 (drain))))))))))
rlm@10 227
rlm@10 228 (defn positions
rlm@10 229 "Returns a lazy sequence containing the positions at which pred
rlm@10 230 is true for items in coll."
rlm@10 231 [pred coll]
rlm@10 232 (for [[idx elt] (indexed coll) :when (pred elt)] idx))
rlm@10 233
rlm@10 234 (defn includes?
rlm@10 235 "Returns true if coll contains something equal (with =) to x,
rlm@10 236 in linear time. Deprecated. Prefer 'contains?' for key testing,
rlm@10 237 or 'some' for ad hoc linear searches."
rlm@10 238 {:deprecated "1.2"}
rlm@10 239 [coll x]
rlm@10 240 (boolean (some (fn [y] (= y x)) coll)))
rlm@10 241
rlm@10 242
rlm@10 243
rlm@10 244