1 | #!/usr/bin/env ruby
|
---|
2 | #--
|
---|
3 | # $Idaemons: /home/cvs/rb/generator.rb,v 1.8 2001/10/03 08:54:32 knu Exp $
|
---|
4 | # $RoughId: generator.rb,v 1.10 2003/10/14 19:36:58 knu Exp $
|
---|
5 | # $Id: generator.rb 11708 2007-02-12 23:01:19Z shyouhei $
|
---|
6 | #++
|
---|
7 | #
|
---|
8 | # = generator.rb: convert an internal iterator to an external one
|
---|
9 | #
|
---|
10 | # Copyright (c) 2001,2003 Akinori MUSHA <[email protected]>
|
---|
11 | #
|
---|
12 | # All rights reserved. You can redistribute and/or modify it under
|
---|
13 | # the same terms as Ruby.
|
---|
14 | #
|
---|
15 | # == Overview
|
---|
16 | #
|
---|
17 | # This library provides the Generator class, which converts an
|
---|
18 | # internal iterator (i.e. an Enumerable object) to an external
|
---|
19 | # iterator. In that form, you can roll many iterators independently.
|
---|
20 | #
|
---|
21 | # The SyncEnumerator class, which is implemented using Generator,
|
---|
22 | # makes it easy to roll many Enumerable objects synchronously.
|
---|
23 | #
|
---|
24 | # See the respective classes for examples of usage.
|
---|
25 |
|
---|
26 |
|
---|
27 | #
|
---|
28 | # Generator converts an internal iterator (i.e. an Enumerable object)
|
---|
29 | # to an external iterator.
|
---|
30 | #
|
---|
31 | # Note that it is not very fast since it is implemented using
|
---|
32 | # continuations, which are currently slow.
|
---|
33 | #
|
---|
34 | # == Example
|
---|
35 | #
|
---|
36 | # require 'generator'
|
---|
37 | #
|
---|
38 | # # Generator from an Enumerable object
|
---|
39 | # g = Generator.new(['A', 'B', 'C', 'Z'])
|
---|
40 | #
|
---|
41 | # while g.next?
|
---|
42 | # puts g.next
|
---|
43 | # end
|
---|
44 | #
|
---|
45 | # # Generator from a block
|
---|
46 | # g = Generator.new { |g|
|
---|
47 | # for i in 'A'..'C'
|
---|
48 | # g.yield i
|
---|
49 | # end
|
---|
50 | #
|
---|
51 | # g.yield 'Z'
|
---|
52 | # }
|
---|
53 | #
|
---|
54 | # # The same result as above
|
---|
55 | # while g.next?
|
---|
56 | # puts g.next
|
---|
57 | # end
|
---|
58 | #
|
---|
59 | class Generator
|
---|
60 | include Enumerable
|
---|
61 |
|
---|
62 | # Creates a new generator either from an Enumerable object or from a
|
---|
63 | # block.
|
---|
64 | #
|
---|
65 | # In the former, block is ignored even if given.
|
---|
66 | #
|
---|
67 | # In the latter, the given block is called with the generator
|
---|
68 | # itself, and expected to call the +yield+ method for each element.
|
---|
69 | def initialize(enum = nil, &block)
|
---|
70 | if enum
|
---|
71 | @block = proc { |g|
|
---|
72 | enum.each { |x| g.yield x }
|
---|
73 | }
|
---|
74 | else
|
---|
75 | @block = block
|
---|
76 | end
|
---|
77 |
|
---|
78 | @index = 0
|
---|
79 | @queue = []
|
---|
80 | @cont_next = @cont_yield = @cont_endp = nil
|
---|
81 |
|
---|
82 | if @cont_next = callcc { |c| c }
|
---|
83 | @block.call(self)
|
---|
84 |
|
---|
85 | @cont_endp.call(nil) if @cont_endp
|
---|
86 | end
|
---|
87 |
|
---|
88 | self
|
---|
89 | end
|
---|
90 |
|
---|
91 | # Yields an element to the generator.
|
---|
92 | def yield(value)
|
---|
93 | if @cont_yield = callcc { |c| c }
|
---|
94 | @queue << value
|
---|
95 | @cont_next.call(nil)
|
---|
96 | end
|
---|
97 |
|
---|
98 | self
|
---|
99 | end
|
---|
100 |
|
---|
101 | # Returns true if the generator has reached the end.
|
---|
102 | def end?()
|
---|
103 | if @cont_endp = callcc { |c| c }
|
---|
104 | @cont_yield.nil? && @queue.empty?
|
---|
105 | else
|
---|
106 | @queue.empty?
|
---|
107 | end
|
---|
108 | end
|
---|
109 |
|
---|
110 | # Returns true if the generator has not reached the end yet.
|
---|
111 | def next?()
|
---|
112 | !end?
|
---|
113 | end
|
---|
114 |
|
---|
115 | # Returns the current index (position) counting from zero.
|
---|
116 | def index()
|
---|
117 | @index
|
---|
118 | end
|
---|
119 |
|
---|
120 | # Returns the current index (position) counting from zero.
|
---|
121 | def pos()
|
---|
122 | @index
|
---|
123 | end
|
---|
124 |
|
---|
125 | # Returns the element at the current position and moves forward.
|
---|
126 | def next()
|
---|
127 | if end?
|
---|
128 | raise EOFError, "no more elements available"
|
---|
129 | end
|
---|
130 |
|
---|
131 | if @cont_next = callcc { |c| c }
|
---|
132 | @cont_yield.call(nil) if @cont_yield
|
---|
133 | end
|
---|
134 |
|
---|
135 | @index += 1
|
---|
136 |
|
---|
137 | @queue.shift
|
---|
138 | end
|
---|
139 |
|
---|
140 | # Returns the element at the current position.
|
---|
141 | def current()
|
---|
142 | if @queue.empty?
|
---|
143 | raise EOFError, "no more elements available"
|
---|
144 | end
|
---|
145 |
|
---|
146 | @queue.first
|
---|
147 | end
|
---|
148 |
|
---|
149 | # Rewinds the generator.
|
---|
150 | def rewind()
|
---|
151 | initialize(nil, &@block) if @index.nonzero?
|
---|
152 |
|
---|
153 | self
|
---|
154 | end
|
---|
155 |
|
---|
156 | # Rewinds the generator and enumerates the elements.
|
---|
157 | def each
|
---|
158 | rewind
|
---|
159 |
|
---|
160 | until end?
|
---|
161 | yield self.next
|
---|
162 | end
|
---|
163 |
|
---|
164 | self
|
---|
165 | end
|
---|
166 | end
|
---|
167 |
|
---|
168 | #
|
---|
169 | # SyncEnumerator creates an Enumerable object from multiple Enumerable
|
---|
170 | # objects and enumerates them synchronously.
|
---|
171 | #
|
---|
172 | # == Example
|
---|
173 | #
|
---|
174 | # require 'generator'
|
---|
175 | #
|
---|
176 | # s = SyncEnumerator.new([1,2,3], ['a', 'b', 'c'])
|
---|
177 | #
|
---|
178 | # # Yields [1, 'a'], [2, 'b'], and [3,'c']
|
---|
179 | # s.each { |row| puts row.join(', ') }
|
---|
180 | #
|
---|
181 | class SyncEnumerator
|
---|
182 | include Enumerable
|
---|
183 |
|
---|
184 | # Creates a new SyncEnumerator which enumerates rows of given
|
---|
185 | # Enumerable objects.
|
---|
186 | def initialize(*enums)
|
---|
187 | @gens = enums.map { |e| Generator.new(e) }
|
---|
188 | end
|
---|
189 |
|
---|
190 | # Returns the number of enumerated Enumerable objects, i.e. the size
|
---|
191 | # of each row.
|
---|
192 | def size
|
---|
193 | @gens.size
|
---|
194 | end
|
---|
195 |
|
---|
196 | # Returns the number of enumerated Enumerable objects, i.e. the size
|
---|
197 | # of each row.
|
---|
198 | def length
|
---|
199 | @gens.length
|
---|
200 | end
|
---|
201 |
|
---|
202 | # Returns true if the given nth Enumerable object has reached the
|
---|
203 | # end. If no argument is given, returns true if any of the
|
---|
204 | # Enumerable objects has reached the end.
|
---|
205 | def end?(i = nil)
|
---|
206 | if i.nil?
|
---|
207 | @gens.detect { |g| g.end? } ? true : false
|
---|
208 | else
|
---|
209 | @gens[i].end?
|
---|
210 | end
|
---|
211 | end
|
---|
212 |
|
---|
213 | # Enumerates rows of the Enumerable objects.
|
---|
214 | def each
|
---|
215 | @gens.each { |g| g.rewind }
|
---|
216 |
|
---|
217 | loop do
|
---|
218 | count = 0
|
---|
219 |
|
---|
220 | ret = @gens.map { |g|
|
---|
221 | if g.end?
|
---|
222 | count += 1
|
---|
223 | nil
|
---|
224 | else
|
---|
225 | g.next
|
---|
226 | end
|
---|
227 | }
|
---|
228 |
|
---|
229 | if count == @gens.size
|
---|
230 | break
|
---|
231 | end
|
---|
232 |
|
---|
233 | yield ret
|
---|
234 | end
|
---|
235 |
|
---|
236 | self
|
---|
237 | end
|
---|
238 | end
|
---|
239 |
|
---|
240 | if $0 == __FILE__
|
---|
241 | eval DATA.read, nil, $0, __LINE__+4
|
---|
242 | end
|
---|
243 |
|
---|
244 | __END__
|
---|
245 |
|
---|
246 | require 'test/unit'
|
---|
247 |
|
---|
248 | class TC_Generator < Test::Unit::TestCase
|
---|
249 | def test_block1
|
---|
250 | g = Generator.new { |g|
|
---|
251 | # no yield's
|
---|
252 | }
|
---|
253 |
|
---|
254 | assert_equal(0, g.pos)
|
---|
255 | assert_raises(EOFError) { g.current }
|
---|
256 | end
|
---|
257 |
|
---|
258 | def test_block2
|
---|
259 | g = Generator.new { |g|
|
---|
260 | for i in 'A'..'C'
|
---|
261 | g.yield i
|
---|
262 | end
|
---|
263 |
|
---|
264 | g.yield 'Z'
|
---|
265 | }
|
---|
266 |
|
---|
267 | assert_equal(0, g.pos)
|
---|
268 | assert_equal('A', g.current)
|
---|
269 |
|
---|
270 | assert_equal(true, g.next?)
|
---|
271 | assert_equal(0, g.pos)
|
---|
272 | assert_equal('A', g.current)
|
---|
273 | assert_equal(0, g.pos)
|
---|
274 | assert_equal('A', g.next)
|
---|
275 |
|
---|
276 | assert_equal(1, g.pos)
|
---|
277 | assert_equal(true, g.next?)
|
---|
278 | assert_equal(1, g.pos)
|
---|
279 | assert_equal('B', g.current)
|
---|
280 | assert_equal(1, g.pos)
|
---|
281 | assert_equal('B', g.next)
|
---|
282 |
|
---|
283 | assert_equal(g, g.rewind)
|
---|
284 |
|
---|
285 | assert_equal(0, g.pos)
|
---|
286 | assert_equal('A', g.current)
|
---|
287 |
|
---|
288 | assert_equal(true, g.next?)
|
---|
289 | assert_equal(0, g.pos)
|
---|
290 | assert_equal('A', g.current)
|
---|
291 | assert_equal(0, g.pos)
|
---|
292 | assert_equal('A', g.next)
|
---|
293 |
|
---|
294 | assert_equal(1, g.pos)
|
---|
295 | assert_equal(true, g.next?)
|
---|
296 | assert_equal(1, g.pos)
|
---|
297 | assert_equal('B', g.current)
|
---|
298 | assert_equal(1, g.pos)
|
---|
299 | assert_equal('B', g.next)
|
---|
300 |
|
---|
301 | assert_equal(2, g.pos)
|
---|
302 | assert_equal(true, g.next?)
|
---|
303 | assert_equal(2, g.pos)
|
---|
304 | assert_equal('C', g.current)
|
---|
305 | assert_equal(2, g.pos)
|
---|
306 | assert_equal('C', g.next)
|
---|
307 |
|
---|
308 | assert_equal(3, g.pos)
|
---|
309 | assert_equal(true, g.next?)
|
---|
310 | assert_equal(3, g.pos)
|
---|
311 | assert_equal('Z', g.current)
|
---|
312 | assert_equal(3, g.pos)
|
---|
313 | assert_equal('Z', g.next)
|
---|
314 |
|
---|
315 | assert_equal(4, g.pos)
|
---|
316 | assert_equal(false, g.next?)
|
---|
317 | assert_raises(EOFError) { g.next }
|
---|
318 | end
|
---|
319 |
|
---|
320 | def test_each
|
---|
321 | a = [5, 6, 7, 8, 9]
|
---|
322 |
|
---|
323 | g = Generator.new(a)
|
---|
324 |
|
---|
325 | i = 0
|
---|
326 |
|
---|
327 | g.each { |x|
|
---|
328 | assert_equal(a[i], x)
|
---|
329 |
|
---|
330 | i += 1
|
---|
331 |
|
---|
332 | break if i == 3
|
---|
333 | }
|
---|
334 |
|
---|
335 | assert_equal(3, i)
|
---|
336 |
|
---|
337 | i = 0
|
---|
338 |
|
---|
339 | g.each { |x|
|
---|
340 | assert_equal(a[i], x)
|
---|
341 |
|
---|
342 | i += 1
|
---|
343 | }
|
---|
344 |
|
---|
345 | assert_equal(5, i)
|
---|
346 | end
|
---|
347 | end
|
---|
348 |
|
---|
349 | class TC_SyncEnumerator < Test::Unit::TestCase
|
---|
350 | def test_each
|
---|
351 | r = ['a'..'f', 1..10, 10..20]
|
---|
352 | ra = r.map { |x| x.to_a }
|
---|
353 |
|
---|
354 | a = (0...(ra.map {|x| x.size}.max)).map { |i| ra.map { |x| x[i] } }
|
---|
355 |
|
---|
356 | s = SyncEnumerator.new(*r)
|
---|
357 |
|
---|
358 | i = 0
|
---|
359 |
|
---|
360 | s.each { |x|
|
---|
361 | assert_equal(a[i], x)
|
---|
362 |
|
---|
363 | i += 1
|
---|
364 |
|
---|
365 | break if i == 3
|
---|
366 | }
|
---|
367 |
|
---|
368 | assert_equal(3, i)
|
---|
369 |
|
---|
370 | i = 0
|
---|
371 |
|
---|
372 | s.each { |x|
|
---|
373 | assert_equal(a[i], x)
|
---|
374 |
|
---|
375 | i += 1
|
---|
376 | }
|
---|
377 |
|
---|
378 | assert_equal(a.size, i)
|
---|
379 | end
|
---|
380 | end
|
---|