lib/generator.rb

   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 <knu@iDaemons.org>
  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