* lib/generator.rb: A new library which converts an internal

  iterator to an external iterator.

* lib/abbrev.rb: A new library which creates an abbreviation table
  from a list.


git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@4767 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

4 files changed, 383 insertions, 0 deletions

diff --git a/ChangeLog b/ChangeLog
index cdce974c09..7b4e8677cd 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+Wed Oct 15 05:05:53 2003  Akinori MUSHA  <knu@iDaemons.org>
+
+	* lib/generator.rb: A new library which converts an internal
+	  iterator to an external iterator.
+
+	* lib/abbrev.rb: A new library which creates an abbreviation table
+	  from a list.
+
 Wed Oct 15 04:31:51 2003  Hidetoshi NAGAI  <nagai@ai.kyutech.ac.jp>
 
 	* ext/tk/sample/demos-en/entry3.rb, ext/tk/sample/demos-jp/entry3.rb : 
diff --git a/doc/NEWS b/doc/NEWS
index 2ff874f81d..b4445fa59f 100644
--- a/doc/NEWS
+++ b/doc/NEWS
@@ -691,6 +691,10 @@
 
   fast YAML parser.
 
+: lib/abbrev
+
+  creates an abbreviation table from a list
+
 : lib/benchmark
 
   Ruby scripts benchmarker
@@ -715,6 +719,10 @@
 
   file utility library.
 
+: lib/generator
+
+  converts an internal iterator to an external iterator
+
 : lib/gserver
 
   generic server used by xmlrpc
diff --git a/lib/abbrev.rb b/lib/abbrev.rb
new file mode 100644
index 0000000000..9cd3a71e40
--- /dev/null
+++ b/lib/abbrev.rb
@@ -0,0 +1,65 @@
+#!/usr/bin/env ruby
+#
+# Copyright (c) 2001,2003 Akinori MUSHA <knu@iDaemons.org>
+#
+# All rights reserved.  You can redistribute and/or modify it under
+# the same terms as Ruby.
+#
+# $Idaemons: /home/cvs/rb/abbrev.rb,v 1.2 2001/05/30 09:37:45 knu Exp $
+# $RoughId: abbrev.rb,v 1.4 2003/10/14 19:45:42 knu Exp $
+# $Id$
+
+module Abbrev
+  def abbrev(words, pattern = nil)
+    table = {}
+    seen = Hash.new(0)
+
+    if pattern.is_a?(String)
+      pattern = /^#{Regexp.quote(pattern)}/	# regard as a prefix
+    end
+
+    words.each do |word|
+      next if (abbrev = word).empty?
+      while (len = abbrev.rindex(/[\w\W]\z/)) > 0
+	abbrev = word[0,len]
+
+	next if pattern && pattern !~ abbrev
+
+	case seen[abbrev] += 1
+	when 1
+	  table[abbrev] = word
+	when 2
+	  table.delete(abbrev)
+	else
+	  break
+	end
+      end
+    end
+
+    words.each do |word|
+      next if pattern && pattern !~ word
+
+      table[word] = word
+    end
+
+    table
+  end
+
+  module_function :abbrev
+end
+
+class Array
+  def abbrev(pattern = nil)
+    Abbrev::abbrev(self, pattern)
+  end
+end
+
+if $0 == __FILE__
+  while line = gets
+    hash = line.split.abbrev
+
+    hash.sort.each do |k, v|
+      puts "#{k} => #{v}"
+    end
+  end
+end
diff --git a/lib/generator.rb b/lib/generator.rb
new file mode 100644
index 0000000000..7e49f3cda0
--- /dev/null
+++ b/lib/generator.rb
@@ -0,0 +1,302 @@
+#!/usr/bin/env ruby
+#
+# Copyright (c) 2001,2003 Akinori MUSHA <knu@iDaemons.org>
+#
+# All rights reserved.  You can redistribute and/or modify it under
+# the same terms as Ruby.
+#
+# $Idaemons: /home/cvs/rb/generator.rb,v 1.8 2001/10/03 08:54:32 knu Exp $
+# $RoughId: generator.rb,v 1.10 2003/10/14 19:36:58 knu Exp $
+# $Id$
+
+#
+# class Generator - converts an internal iterator to an external iterator
+#
+
+class Generator
+  include Enumerable
+
+  def initialize(enum = nil, &block)
+    if enum
+      @block = proc { |g|
+	enum.each { |x| g.yield x }
+      }
+    else
+      @block = block
+    end
+
+    @index = 0
+    @queue = []
+    @cont_next = @cont_yield = @cont_endp = nil
+
+    if @cont_next = callcc { |c| c }
+      @block.call(self)
+
+      @cont_endp.call(nil) if @cont_endp
+    end
+
+    self
+  end
+
+  def yield(value)
+    if @cont_yield = callcc { |c| c }
+      @queue << value
+      @cont_next.call(nil)
+    end
+
+    self
+  end
+
+  def end?()
+    if @cont_endp = callcc { |c| c }
+      @cont_yield.nil? && @queue.empty?
+    else
+      @queue.empty?
+    end
+  end
+
+  def next?()
+    !end?
+  end
+
+  def index()
+    @index
+  end
+
+  def pos()
+    @index
+  end
+
+  def next()
+    if end?
+      raise EOFError, "no more element is supplied"
+    end
+
+    if @cont_next = callcc { |c| c }
+      @cont_yield.call(nil) if @cont_yield
+    end
+
+    @index += 1
+
+    @queue.shift
+  end
+
+  def current()
+    if @queue.empty?
+      raise EOFError, "no more element is supplied"
+    end
+
+    @queue.first
+  end
+
+  def rewind()
+    initialize(nil, &@block) if @index.nonzero?
+
+    self
+  end
+
+  def each
+    rewind
+
+    until end?
+      yield self.next
+    end
+
+    self
+  end
+end
+
+#
+# class SyncEnumerator - enumerates multiple internal iterators synchronously
+#
+
+class SyncEnumerator
+  include Enumerable
+
+  def initialize(*enums)
+    @gens = enums.map { |e| Generator.new(e) }
+  end
+
+  def size
+    @gens.size
+  end
+
+  def length
+    @gens.length
+  end
+
+  def end?(i = nil)
+    if i.nil?
+      @gens.detect { |g| g.end? } ? true : false
+    else
+      @gens[i].end?
+    end
+  end
+
+  def each
+    @gens.each { |g| g.rewind }
+
+    loop do
+      count = 0
+
+      ret = @gens.map { |g|
+	if g.end?
+	  count += 1
+	  nil
+	else
+	  g.next
+	end
+      }
+
+      if count == @gens.size
+	break
+      end
+
+      yield ret
+    end
+
+    self
+  end
+end
+
+if $0 == __FILE__
+  eval DATA.read, nil, $0, __LINE__+4
+end
+
+__END__
+
+require 'test/unit'
+
+class TC_Generator < Test::Unit::TestCase
+  def test_block1
+    g = Generator.new { |g|
+      # no yield's
+    }
+
+    assert_equal(0, g.pos)
+    assert_raises(EOFError) { g.current }
+  end
+
+  def test_block2
+    g = Generator.new { |g|
+      for i in 'A'..'C'
+        g.yield i
+      end
+
+      g.yield 'Z'
+    }
+
+    assert_equal(0, g.pos)
+    assert_equal('A', g.current)
+
+    assert_equal(true, g.next?)
+    assert_equal(0, g.pos)
+    assert_equal('A', g.current)
+    assert_equal(0, g.pos)
+    assert_equal('A', g.next)
+
+    assert_equal(1, g.pos)
+    assert_equal(true, g.next?)
+    assert_equal(1, g.pos)
+    assert_equal('B', g.current)
+    assert_equal(1, g.pos)
+    assert_equal('B', g.next)
+
+    assert_equal(g, g.rewind)
+
+    assert_equal(0, g.pos)
+    assert_equal('A', g.current)
+
+    assert_equal(true, g.next?)
+    assert_equal(0, g.pos)
+    assert_equal('A', g.current)
+    assert_equal(0, g.pos)
+    assert_equal('A', g.next)
+
+    assert_equal(1, g.pos)
+    assert_equal(true, g.next?)
+    assert_equal(1, g.pos)
+    assert_equal('B', g.current)
+    assert_equal(1, g.pos)
+    assert_equal('B', g.next)
+
+    assert_equal(2, g.pos)
+    assert_equal(true, g.next?)
+    assert_equal(2, g.pos)
+    assert_equal('C', g.current)
+    assert_equal(2, g.pos)
+    assert_equal('C', g.next)
+
+    assert_equal(3, g.pos)
+    assert_equal(true, g.next?)
+    assert_equal(3, g.pos)
+    assert_equal('Z', g.current)
+    assert_equal(3, g.pos)
+    assert_equal('Z', g.next)
+
+    assert_equal(4, g.pos)
+    assert_equal(false, g.next?)
+    assert_raises(EOFError) { g.next }
+  end
+
+  def test_each
+    a = [5, 6, 7, 8, 9]
+
+    g = Generator.new(a)
+
+    i = 0
+
+    g.each { |x|
+      assert_equal(a[i], x)
+
+      i += 1
+
+      break if i == 3
+    }
+
+    assert_equal(3, i)
+
+    i = 0
+
+    g.each { |x|
+      assert_equal(a[i], x)
+
+      i += 1
+    }
+
+    assert_equal(5, i)
+  end
+end
+
+class TC_SyncEnumerator < Test::Unit::TestCase
+  def test_each
+    r = ['a'..'f', 1..10, 10..20]
+    ra = r.map { |x| x.to_a }
+
+    a = (0...(ra.map {|x| x.size}.max)).map { |i| ra.map { |x| x[i] } }
+
+    s = SyncEnumerator.new(*r)
+
+    i = 0
+
+    s.each { |x|
+      assert_equal(a[i], x)
+
+      i += 1
+
+      break if i == 3
+    }
+
+    assert_equal(3, i)
+
+    i = 0
+
+    s.each { |x|
+      assert_equal(a[i], x)
+
+      i += 1
+    }
+
+    assert_equal(a.size, i)
+  end
+end