Class: LazyList

Inherits:
Object show all
Extended by:
ModuleFunctions
Includes:
Enumerable, ModuleFunctions
Defined in:
lib/lazylist.rb,
lib/lazylist/version.rb,
lib/lazylist/enumerable.rb,
lib/lazylist/list_builder.rb,
lib/lazylist/thread_queue.rb,
lib/lazylist/enumerator_queue.rb

Defined Under Namespace

Modules: Enumerable, ModuleFunctions, ObjectMethods Classes: Exception, ListBuilder, MemoPromise, Promise, ReadQueue

Constant Summary collapse

Identity =

Identity lambda expression, mostly used as a default.

lambda { |x| x }
All =

This block returns true.

lambda { |x| true }
Tuple =

Create an array tuple from argument list.

lambda { |*t| t }
LessThan =

Returns true, if a less than b.

lambda { |a, b| a < b }
SwapTuple =

Swaps you and me and returns an Array tuple of both.

lambda { |you, me| [ me, you ] }
VERSION =

LazyList version

'0.3.2'
VERSION_ARRAY =

:nodoc:

VERSION.split(/\./).map { |x| x.to_i }
VERSION_MAJOR =

:nodoc:

VERSION_ARRAY[0]
VERSION_MINOR =

:nodoc:

VERSION_ARRAY[1]
VERSION_BUILD =

:nodoc:

VERSION_ARRAY[2]

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from ModuleFunctions

delay, force, mix

Methods included from Enumerable

#combine, #each_with_index, #filter, #grep, #map, #mapper, #partition, #reject, #select, #sort, #sort_by, #zip

Constructor Details

#initialize(head = nil, tail = nil, &block) ⇒ LazyList

Creates a new LazyList element. The tail can be given either as second argument or as block.



106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
# File 'lib/lazylist.rb', line 106

def initialize(head = nil, tail = nil, &block)
  @cached = true
  @ref_cache = {}
  if tail
    if block
      raise LazyList::Exception,
        "Use block xor second argument for constructor"
    end
    @head, @tail = head, tail
  elsif block
    @head, @tail = head, delay(&block)
  else
    @head, @tail = nil, nil
  end
end

Instance Attribute Details

#cached=(value) ⇒ Object (writeonly)

Set this to false, if index references into the lazy list shouldn’t be cached for fast access (while spending some memory on this). This value defaults to true.



125
126
127
 
# File 'lib/lazylist.rb', line 125

def cached=(value)
  @cached = value
end

#head ⇒ Object

Returns the head of this list by computing its value.



147
148
149
 
# File 'lib/lazylist.rb', line 147

def head
  @head = force @head
end

#tail ⇒ Object

Returns the next element by computing its value if necessary.



162
163
164
 
# File 'lib/lazylist.rb', line 162

def tail
  @tail = force @tail
end

Class Method Details

.[](a, n = nil) ⇒ Object

Returns a lazy list which is generated from the Enumerable a or LazyList.span(a, n), if n was given as an argument.



189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
 
# File 'lib/lazylist.rb', line 189

def self.[](a, n = nil)
  case
  when n
    span(a, n)
  when a.respond_to?(:to_io)
    io(a.to_io)
  when a.respond_to?(:to_ary)
    from_queue(a.to_ary)
  when Range === a
    from_range(a)
  when a.respond_to?(:each)
    from_enum(a)
  else
    list(a)
  end
end

.const_missing(id) ⇒ Object

If the constant Empty is requested return a new empty list object.



134
135
136
137
138
139
140
 
# File 'lib/lazylist.rb', line 134

def self.const_missing(id)
  if id == :Empty
    new(nil, nil)
  else
    super
  end
end

.empty ⇒ Object

Returns an empty list.



94
95
96
 
# File 'lib/lazylist.rb', line 94

def self.empty
  new(nil, nil)
end

.from(n = 0) ⇒ Object

Returns a list of all elements succeeding n (that is created by calling the #succ method) and starting from n.



259
260
261
 
# File 'lib/lazylist.rb', line 259

def self.from(n = 0)
  tabulate(n)
end

.from_enum(e) ⇒ Object

Generates a lazy list from any data structure e which responds to the #each method.



208
209
210
 
# File 'lib/lazylist.rb', line 208

def self.from_enum(e)
  from_queue ReadQueue.new(e)
end

.from_queue(rq) ⇒ Object

Generates a lazyx list by popping elements from a queue.



213
214
215
216
 
# File 'lib/lazylist.rb', line 213

def self.from_queue(rq)
  return empty if rq.empty?
  new(delay { rq.shift }) { from_queue(rq) }
end

.from_range(r) ⇒ Object

Generates a lazy list from a Range instance r.



219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
 
# File 'lib/lazylist.rb', line 219

def self.from_range(r)
  if r.exclude_end?
    if r.begin >= r.end
      empty
    else
      new(delay { r.begin }) { from_range(r.begin.succ...r.end) }
    end
  else
    case
    when r.begin > r.end
      empty
    when r.begin == r.end
      new(delay { r.begin }) { empty }
    else
      new(delay { r.begin }) { from_range(r.begin.succ..r.end) }
    end
  end
end

.io(input, &f) ⇒ Object

Generates a lazy list of a give IO-object using a given block or Proc object to read from this object.



271
272
273
274
275
276
277
 
# File 'lib/lazylist.rb', line 271

def self.io(input, &f)
  if f
    input.eof? ? empty : new(delay { f[input] }) { io(input, &f) }
  else
    input.eof? ? empty : new(delay { input.readline }) { io(input) }
  end
end

.iterate(i = 0, &f) ⇒ Object

Generates a lazy list which iterates over its previous values computing something like: f(i), f(f(i)), f(f(f(i))), …



265
266
267
 
# File 'lib/lazylist.rb', line 265

def self.iterate(i = 0, &f)
  new(delay { i }) { iterate(f[i], &f) }
end

.span(a, n) ⇒ Object

Generates a finite lazy list beginning with element a and spanning n elements. The data structure members have to support the successor method succ.



241
242
243
244
245
246
247
 
# File 'lib/lazylist.rb', line 241

def self.span(a, n)
  if n > 0
    new(delay { a }) { span(a.succ, n - 1) }
  else
    empty
  end
end

.tabulate(n = 0, &f) ⇒ Object

Generates a lazy list which tabulates every element beginning with n and succeding with succ by calling the Proc object f or the given block. If none is given the identity function is computed instead.



252
253
254
255
 
# File 'lib/lazylist.rb', line 252

def self.tabulate(n = 0, &f)
  f = Identity unless f
  new(delay { f[n] }) { tabulate(n.succ, &f) }
end

Instance Method Details

#[](n, m = nil) ⇒ Object

If n is a Range every element in this range is returned. If n isn’t a Range object the element at index n is returned. If m is given the next m elements beginning the n-th element are returned.



344
345
346
347
348
349
350
351
352
353
354
355
 
# File 'lib/lazylist.rb', line 344

def [](n, m = nil)
  case
  when Range === n
    sublist(n)
  when n < 0
    nil
  when m
    sublist(n, m)
  else
    ref(n).head
  end
end

#append(*other) ⇒ Object Also known as: +

Append this lazy list to the _*other_ lists, creating a new lists that consists of the elements of this list and the elements of the lists other1, other2, … If any of the lists is infinite, the elements of the following lists will never occur in the result list.



421
422
423
424
425
426
427
428
429
430
431
 
# File 'lib/lazylist.rb', line 421

def append(*other)
  if empty?
    if other.empty?
      empty
    else
      other.first.append(*other[1..-1])
    end
  else
    self.class.new(delay { head }) { tail.append(*other) }
  end
end

#cached? ⇒ Boolean

Returns true, if index references into the lazy list are cached for fast access to the referenced elements.

Returns:

  • (Boolean) 


129
130
131
 
# File 'lib/lazylist.rb', line 129

def cached?
  !!@cached
end

#cartesian_product(*others) ⇒ Object

Returns the cartesian_product of this LazyList and the others as a LazyList of Array tuples. A block can be given to yield to all the created tuples and create a LazyList out of the block results.



585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
 
# File 'lib/lazylist.rb', line 585

def cartesian_product(*others) # :yields: tuple
  case
  when empty?
    self
  when others.empty?
    block_given? ? map(&Proc.new) : map
  else
    product = others[1..-1].inject(product(others[0])) do |intermediate, list| 
      intermediate.product(list) do |existing, new_element|
        existing + [ new_element ]
      end
    end
    if block_given?
      block = Proc.new
      product.map { |tuple| block[*tuple] }
    else
      product
    end
  end
end

#do_build(lb, others) ⇒ Object

:nodoc:



4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/lazylist/list_builder.rb', line 4

def do_build(lb, others) # :nodoc:
  if empty? or others.any? { |o| o.empty? }
    Empty
  else
    variables = [ head ].concat others.map { |o| o.head }
    if lb.filter
      if lb.filter[*variables]
        self.class.new(lb.transform[*variables]) do
          tail.do_build(lb, others.map { |o| o.tail })
        end
      else
        tail.do_build(lb, others.map { |o| o.tail })
      end
    else
      self.class.new(lb.transform[*variables]) do
        tail.do_build(lb, others.map { |o| o.tail })
      end
    end
  end
end

#do_comprehend(lb, others) ⇒ Object

:nodoc:



25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/lazylist/list_builder.rb', line 25

def do_comprehend(lb, others) # :nodoc:
  if lb.filter
    cartesian_product(*others).select do |variables|
      lb.filter[*variables]
    end.map do |variables|
      lb.transform[*variables]
    end
  else
    cartesian_product(*others).map do |variables|
      lb.transform[*variables]
    end
  end
end

#drop(n = 1) ⇒ Object

Drops the next n elements and returns the rest of this lazy list. n defaults to 1.



467
468
469
 
# File 'lib/lazylist.rb', line 467

def drop(n = 1)
  each(n) { }
end

#drop!(n = 1) ⇒ Object

Drops the next n elements, destroys them in the lazy list and returns the rest of this lazy list. Also see #each! .



473
474
475
 
# File 'lib/lazylist.rb', line 473

def drop!(n = 1)
  each!(n) { }
end

#each(n = nil) ⇒ Object

Iterates over all elements. If n is given only n iterations are done. If self is a finite lazy list each returns also if there are no more elements to iterate over.



360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
 
# File 'lib/lazylist.rb', line 360

def each(n = nil)
  s = self
  if n
    until n <= 0 or s.empty?
      yield s.head
      s = s.tail
      n -= 1 unless n.nil?
    end
  else
    until s.empty?
      yield s.head
      s = s.tail
    end
  end
  s
end

#each!(n = nil) ⇒ Object

Similar to LazyList#each but destroys elements from past iterations perhaps saving some memory. Try to call GC.start from time to time in your block.



379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
 
# File 'lib/lazylist.rb', line 379

def each!(n = nil)
  s = self
  if n
    until n <= 0 or s.empty?
      yield s.head
      s = s.tail
      n -= 1 unless n.nil?
      @head, @tail = s.head, s.tail
    end
  else
    until s.empty?
      yield s.head
      s = s.tail
      @head, @tail = s.head, s.tail
    end
  end
  self
end

#empty ⇒ Object

Returns an empty list.



99
100
101
102
 
# File 'lib/lazylist.rb', line 99

def empty
  @klass ||= self.class
  @klass.new(nil, nil)
end

#empty? ⇒ Boolean

Returns true if this is the empty lazy list.

Returns:

  • (Boolean) 


492
493
494
 
# File 'lib/lazylist.rb', line 492

def empty?
  self.peek_head == nil && self.peek_tail == nil
end

#eql?(other) ⇒ Boolean Also known as: ==

Returns true, if this lazy list and the other lazy list consist of only equal elements. This is only sensible, if the lazy lists are finite and you can spare the memory.

Returns:

  • (Boolean) 


499
500
501
502
503
504
 
# File 'lib/lazylist.rb', line 499

def eql?(other)
  other.is_a? self.class or return false
  size == other.size or return false
  to_a.zip(other.to_a) { |x, y| x == y or return false }
  true
end

#half_product(other, &block) ⇒ Object

Returns one “half” of the product of this LazyList and the other:

list(1,2,3).half_product(list(1,2)).to_a # => [[1, 1], [2, 1], [2, 2], [3, 1], [3, 2]]

block can be used to yield to every pair generated and create a new list element out of it. It defaults to Tuple.



542
543
544
545
546
547
548
549
550
551
552
 
# File 'lib/lazylist.rb', line 542

def half_product(other, &block)
  block ||= Tuple
  if empty? or other.empty?
    empty
  else
    mix(
      delay { zip(other, &block) },
      delay { tail.half_product(other, &block) }
    )
  end
end

#inspect ⇒ Object Also known as: to_s

Inspects the list as far as it has been computed by returning a string of the form [1, 2, 3,… ].



509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
 
# File 'lib/lazylist.rb', line 509

def inspect
  return '[]' if empty?
  result = '['
  first = true
  s = self
  seen = {}
  until s.empty? or Promise === s.peek_head or seen[s.__id__]
    seen[s.__id__] = true
    if first
      first = false
    else
      result << ', '
    end
    result << s.head.inspect
    Promise === s.peek_tail and break
    s = s.tail
  end
  unless empty?
    if first
      result << '... '
    elsif !s.empty?
      result << ',... '
    end
  end
  result << ']'
end

#last(n = 1) ⇒ Object

Return the last n elements of the lazy list. This is only sensible if the lazy list is finite of course.



479
480
481
 
# File 'lib/lazylist.rb', line 479

def last(n = 1)
  to_a.last n
end

#merge(other, &compare) ⇒ Object

Merges this lazy list with the other. It uses the &compare block to decide which elements to place first in the result lazy list. If no compare block is given lambda { |a,b| a < b } is used as a default value.



401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
 
# File 'lib/lazylist.rb', line 401

def merge(other, &compare)
  compare ||= LessThan
  case
  when empty?
    other
  when other.empty?
    self
  when compare[head, other.head]
    self.class.new(head) { tail.merge(other, &compare) }
  when compare[other.head, head]
    self.class.new(other.head) { merge(other.tail, &compare) }
  else
    self.class.new(head) { tail.merge(other.tail, &compare) }
  end
end

#product(other, &block) ⇒ Object Also known as: *

Returns the (cartesian) product of this LazyList instance and the other. block can be used to yield to every pair generated and create a new list element out of it, but it’s useful to at least return the default Tuple from the block.



563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
 
# File 'lib/lazylist.rb', line 563

def product(other, &block)
  if empty? or other.empty?
    empty
  else
    other_block =
      if block
        swap block
      else
        block = Tuple
        SwapTuple
      end
    mix(
      delay { half_product(other, &block)},
      delay { other.tail.half_product(self, &other_block) }
    )
  end
end

#size ⇒ Object Also known as: length

Returns the size. This is only sensible if the lazy list is finite of course.



485
486
487
 
# File 'lib/lazylist.rb', line 485

def size
  inject(0) { |s,| s += 1 }
end

#sublist(n, m = nil) ⇒ Object

Returns the result of sublist_range(n), if n is a Range. The result of sublist_span(n, m), if otherwise.



307
308
309
310
311
312
313
 
# File 'lib/lazylist.rb', line 307

def sublist(n, m = nil)
  if n.is_a? Range
    sublist_range(n)
  else
    sublist_span(n, m)
  end
end

#sublist_range(range) ⇒ Object

Returns the sublist, constructed from the Range range indexed elements, of this lazy list.



281
282
283
284
285
 
# File 'lib/lazylist.rb', line 281

def sublist_range(range)
  f = range.first
  l = range.exclude_end? ? range.last - 1 : range.last
  sublist_span(f, l - f + 1)
end

#sublist_span(n, m = nil) ⇒ Object

Returns the sublist, that spans m elements starting from the n-th element of this lazy list, if m was given. If m is non­positive, the empty lazy list LazyList::Empty is returned.

If m wasn’t given returns the n long sublist starting from the first (index = 0) element. If n is non­positive, the empty lazy list LazyList::Empty is returned.



294
295
296
297
298
299
300
301
302
303
 
# File 'lib/lazylist.rb', line 294

def sublist_span(n, m = nil)
  if not m
    sublist_span(0, n)
  elsif m > 0
    l = ref(n)
    self.class.new(delay { l.head }) { l.tail.sublist_span(0, m - 1) }
  else
    empty
  end
end

#take(n = 1) ⇒ Object Also known as: first

Takes the next n elements and returns them as an array.



436
437
438
439
440
 
# File 'lib/lazylist.rb', line 436

def take(n = 1)
  result = []
  each(n) { |x| result << x }
  result
end

#take!(n = 1) ⇒ Object

Takes the next n elements and returns them as an array. It destroys these elements in this lazy list. Also see #each! .



459
460
461
462
463
 
# File 'lib/lazylist.rb', line 459

def take!(n = 1)
  result = []
  each!(n) { |x| result << x }
  result
end

#take_range(range) ⇒ Object

Takes the range indexes of elements from this lazylist and returns them as an array.



446
447
448
 
# File 'lib/lazylist.rb', line 446

def take_range(range) 
  range.map { |i| ref(i).head }
end

#take_span(n, m) ⇒ Object

Takes the m elements starting at index n of this lazy list and returns them as an array.



452
453
454
455
 
# File 'lib/lazylist.rb', line 452

def take_span(n, m)
  s = ref(n)
  s ? s.take(m) : nil
end