Module: Tb::ExEnumerator

Defined in:
lib/tb/ex_enumerator.rb

Overview

Copyright © 2012 Tanaka Akira <[email protected]>

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above
   copyright notice, this list of conditions and the following
   disclaimer in the documentation and/or other materials provided
   with the distribution.
3. The name of the author may not be used to endorse or promote
   products derived from this software without specific prior
   written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Class Method Summary collapse

Class Method Details

.merge_sorted(*enumerators) ⇒ Object

:call-seq:

Tb::ExEnumerator.merge_sorted(enumerator1, ...) {|key, enumerator1_or_nil, ...| ... }

iterates over enumerators specified by arguments.

The enumerators should yield an array which first element is a comparable key. The enumerators should be sorted by the key in ascending order.

Tb::Enumerator.merge_sorted iterates keys in all of the enumerators. It yields an array which contains a key and enumerators which has the key. The array contains nil if corresponding enumerator don’t have the key.

The block may or may not use next method to advance enumerators. Anyway Tb::Enumerator.merge_sorted advance enumerators until peeked key is greater than the yielded key.

If a enumerator has multiple elements with same key, the block can read them using next method. peek method should also be used to determine the key of the next element has the current key or not. Be careful to not consume extra elements with different key.



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/tb/ex_enumerator.rb', line 53

def (Tb::ExEnumerator).merge_sorted(*enumerators) # :yields: [key, enumerator1_or_nil, ...]
  while true
    has_min = false
    min = nil
    min_enumerators = []
    enumerators.each {|kpe|
      begin
        key, = kpe.peek
      rescue StopIteration
        min_enumerators << nil
        next
      end
      if !has_min
        has_min = true
        min = key
        min_enumerators << kpe
      else
        cmp = key <=> min
        if cmp < 0
          min_enumerators.fill(nil)
          min_enumerators << kpe
          min = key
        elsif cmp == 0
          min_enumerators << kpe
        else
          min_enumerators << nil
        end
      end
    }
    if !has_min
      return
    end
    yield [min, *min_enumerators]
    min_enumerators.each {|kpe|
      next if !kpe
      while true
        begin
          key, = kpe.peek
        rescue StopIteration
          break
        end
        if (min <=> key) < 0
          break
        end
        kpe.next
      end
    }
  end
end