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