#!/usr/bin/env ruby
#
#  Created by Reginald Braithwaite on 2007-02-21.
#
#            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
#                    Version 2, December 2004
# 
# Copyright (C) 2004 Sam Hocevar
#  22 rue de Plaisance, 75014 Paris, France
# Everyone is permitted to copy and distribute verbatim or modified
# copies of this license document, and changing it is allowed as long
# as the name is changed.
# 
#            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
#   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
# 
#  0. You just DO WHAT THE FUCK YOU WANT TO.
#
# See http://sam.zoy.org/wtfpl/ for full license details
#
# Requires certain Ruby Facets: http://facets.rubyforge.org/

require 'rubygems'
require 'facets'
require 'array/tail'

# = LazyList
#
# A lazy collection that is accessed from the head. It isn't really an enumerable.
# key methods are first and tail.
# tail returns an empty list when it reaches the end

class LazyList

  # ==================
  # = The Lazy Value =
  # ==================

  class << self

    # =======================================
    # = Delay and force convenience methods =
    # =======================================

    def delay &block
      Lazy.new(block)
    end

    def force obj
      if obj.nil?
        nil
      elsif obj.kind_of?(Lazy)
        force obj.value
      else
        obj
      end
    end

  end

  class Lazy
    MEMOIZE = false
    class << self
      def is_memoized?
        MEMOIZE
      end
    end
    def initialize block
      @block = block
    end
    def method_missing( *args, &block ) #:nodoc:
      value.__send__( *args, &block )
    end
    def __value
      v = @block.call
      if v.kind_of?(Lazy)
        v.value
      else
        v
      end
    end
    if MEMOIZE
      def value
        @value ||= __value
      end
    else
      alias :value :__value
    end
  end  

  # ================
  # = Constructors =
  # ================

  # performs a wrapping construction
  def initialize one = nil, two = nil, &block
    unless one.nil? && two.nil?
      raise ArgumentError, 'deprecated: list car cannot be lazy' if one.kind_of?(Lazy)
      raise ArgumentError, 'tail must be lazy' unless two.nil? or two.kind_of?(Lazy)
    end
    @first = one
    if block_given?
      @tail = LazyList.delay(&block)
    else
      @tail = two
    end
  end
  
  # The canonical empty list. also signals a list's end

  EMPTY = LazyList.new(nil, nil)

  class << self

    # ==========================
    # = Infinite list builders =
    # ==========================

    # builds a list from a seed value and a block

    def unfoldr seed = EMPTY, &block
      LazyList.new(seed) { unfoldr block.call(seed), &block }
    end
    
    # builds a list that searches a space, including the seed values
    
    def binary_search seed1, seed2, &block
      bisection_block = block || lambda { |x, y| (x-y)/2 + y }
      LazyList.cons(
        seed1,
        LazyList.new(
          seed2,
          delay {
            bisect(seed1, seed2, &bisection_block)
          }
        )
      )
    end
    
    # infinitely bisects a space, exclusive of the seed values
    
    def bisect seed1, seed2, &block
      return EMPTY if seed1 == seed2
      half = block.call(seed1, seed2)
      LazyList.new(
        half,
        delay {
          merge(
            bisect(seed1, half, &block),
            bisect(half, seed2, &block)
          )
        }
      )
    end
    
    # ==========================
    # = Canonical smaple lists =
    # ==========================  
    
    def wholes
      unfoldr(0) { |n| n + 1 }
    end
    
    def integers
      cons(
        0,
        merge(
          unfoldr(1) { |n| n + 1 },
          unfoldr(-1) { |n| n - 1 }
        )
      )
    end

    # =============================================
    # = Building lists from other data structures =
    # =============================================

    # build a list from anything that responds to first and tail, one level deep
    # so [[1, 2], 3] => ([1, 2] 3)

    def from_list list
      if list.empty?
        EMPTY
      else
        LazyList.new(list.first) { LazyList.from_list(list.tail) }
      end
    end

    # build a list from anything that responds to first and tail, recursively
    # so [[1, 2], 3] => ((1 2) 3)

    def from_list_recursive list_or_element
      if list_or_element.respond_to?(:first) && list_or_element.respond_to?(:tail) && list_or_element.respond_to?(:empty?)
        if list_or_element.empty?
          EMPTY
        else
          LazyList.new(from_list_recursive(list_or_element.first)) { LazyList.from_list_recursive(list_or_element.tail) }
        end
      else
        list_or_element
      end
    end

    # Handy notation for from_list_recursive

    def [] *args
      from_list_recursive args
    end

    # build a list from anything that responds to succ

    def from_range range
      if range.first == range.last
        LazyList.new(range.first) { EMPTY }
      else
        LazyList.new(range.first) { LazyList.from_range(range.first.succ..range.last) }
      end
    end

    # build a list with just one element in it, synonymous with bulding a list from a list with one element

    def from_element el
      LazyList.new(el)  { EMPTY }
    end
    
    # generic builder
    
    def from whatsis, &block
      if block_given?
        unfoldr(whatsis, &block)
      elsif whatsis.respond_to?(:tail) && whatsis.respond_to?(:first)
        from_list(whatsis)
      elsif whatsis.respond_to?(:first) && whatsis.respond_to?(:last) && whatsis.first.respond_to?(:succ)
        from_range(whatsis)
      else
        from_element(whatsis)
      end
    end

    # =======================
    # = Operations on lists =
    # =======================

    # "cons" an element onto the front of an existing list

    def cons el, list
      LazyList.new(el) { list }
    end

    # merges an arbitrary number of lists together

    def merge *lists
      # p lists.map { |l| force(l) }
      if lists.empty? or lists.nil?
        EMPTY
      elsif lists.size == 1
        force lists.first
      elsif lists.first.nil?
        merge(*(lists.tail))
      else
        head = force(lists.first)
        if head.empty?
          merge(*(lists.tail))
        else
          LazyList.new(head.first) do
            unless head.tail.empty?
              merge(*(lists.tail.push(delay { head.tail })))
            else
              merge(*(lists.tail))
            end
          end
        end
      end
    end

    # Danger, Will Robinson: does not terminate for infinite lists
    # TODO: a flag for known finite lists

    def append l1, l2
      l1.empty? && force(l2) || LazyList.new(l1.first, delay { append(l1.tail, force(l2)) })
    end
    
    # the cartesian product of two or more lists. use instead of the product instance method
    # when you want to supply a block that operates on three or more lists
    
    def cartesian_product *lists, &block
      if lists.empty?
        EMPTY
      elsif lists.size == 1 && block_given?
        lists.first.map(&block)
      elsif lists.size == 1
        lists.first
      else
        # opportunity to clean this up with a single unwrapping
        product = lists[2..-1].inject(lists[0].product(lists[1])) do |intermediate_product, list| 
          intermediate_product.product(list) { |existing_product, new_element| existing_product + [new_element] }
        end
        if block_given?
          product.map { |tuple| block.call(*tuple) }
        else
          product
        end
      end
    end
    
    alias :cart :cartesian_product
    
    # ===================================================================
    # = Cross product is more expensive but gives a better distribution =
    # ===================================================================
    
    def combinations_by_sum i, n, *lists
      if lists.empty?
        EMPTY
      elsif lists.size == 1
        LazyList.from_element([ lists.first[n] ])
      else
        from(0..n).mapr(:append) do |nn| 
          combinations_by_sum(i + 1, n - nn, *(lists.tail) ).map { |ec| [ lists.first[nn] ] + ec }
        end
      end 
    end
    
    def cross_product *lists, &block
      if block_given?
        wholes.mapr(:append) do |n|
          combinations_by_sum(0, n, *lists).map { |combo| yield combo }
        end
      else
        wholes.mapr(:append) do |n|
          combinations_by_sum(0, n, *lists)
        end
      end
    end

  end

  # =============
  # = Accessors =
  # =============

  def first
    LazyList.force @first
  end

  def tail
    LazyList.force @tail
  end

  # =======================
  # = Axiomatic operators =
  # =======================

  def empty?
    @first.nil? && @tail.nil?
  end

  # may not terminate!

  def == other_list
    empty? && other_list.empty? or first == other_list.first && tail == other_list.tail
  end
  
  def inner_foldr seed, &block
    unless empty?
      tail.inner_foldr(yield(seed, first), &block)
    else
      seed
    end
  end

  def foldr seed = nil, &block
    unless empty?
      if seed.nil?
        tail.inner_foldr(first, &block)
      else
        tail.inner_foldr(yield(seed, first), &block)
      end
    else
      if seed.nil?
        EMPTY
      else
        seed
      end
    end
  end
  
  def each args = {}, &block
    while_block = args[:while] || lambda { |element| true }
    unless empty?
      if while_block.call(first)
        yield first
        tail.each(args, &block)
      end
    end
  end

  alias :inject :foldr

  # may not terminate!

  def detect &block
    if empty?
      nil
    elsif block.call(first)
      first
    elsif tail.empty?
      nil
    else
      tail.detect(&block)
    end
  end

  # maps a list to another list. generalized above and beyond a regular map
  # to support filtering and inflation

  def mapr operation = :cons, &block
    if empty?
      EMPTY
    else
      first_result = if block.arity == 1
          block.call(first)
        else
          block.call(first, @tail)
        end
      delayed_tail = LazyList.delay {
        tail.map(operation, &block)
      }
      if operation.respond_to?(:call)
        operation.call(first_result, delayed_tail)
      else
        LazyList.method(operation).call(first_result, delayed_tail)
      end
    end
  end

  alias :collect :mapr
  alias :map :mapr

  # ==========================================
  # = Operators expressed in terms of axioms =
  # ==========================================

  # unpacks lists that are made of lists, using merge semantics

  def merge_all
    mapr :merge do |element|
      if element.respond_to?(:first)
        element
      else
        LazyList.from_element(element)
      end
    end
  end

  # pairs two lists up

  def pairwise other_list, &block
    unless empty? or other_list.empty?
      operation = block || lambda { |*args| args }
      LazyList.new(
        operation.call(first, other_list.first),
        LazyList.delay { tail.pairwise(other_list.tail, &block) }
      )
    else
      EMPTY
    end
  end
  
  def half_product other_list, &block
    if empty? or other_list.empty?
      EMPTY
    else
      LazyList.merge(
        LazyList.delay{ pairwise(other_list, &block) },
        LazyList.delay{ tail.half_product(other_list, &block) }
      )
    end
  end

  # lazily creates the cartesian product of two lists.

  def product other_list, &block
    raise ArgumentError, 'both items must be lists, not nil' if other_list.nil?
    if empty? or other_list.empty?
      EMPTY
    else
      other_block = block_given? && lambda { |you, me| block.call(me, you) } || lambda { |you, me| [me, you] }
      LazyList.merge(
        LazyList.delay{ half_product(other_list, &block) },
        LazyList.delay{ other_list.tail.half_product(self, &other_block) }
      )
    end
  end

  alias :* :product
  
  # index
  
  def at index
    if index.respond_to?(:-)
      raise ArgumentError, "#{index} must be >= 0" if index < 0
      if index == 0
        self.first
      else
        self.tail.at(index - 1)
      end
    elsif index.respond_to?(:first) && index.respond_to?(:last)
      from = index.first
      to = index.last
      raise ArgumentError, "#{from} must be >= 0" if from < 0
      raise ArgumentError, "#{to} must be >= 0" if to < 0
      raise ArgumentError, "#{to} must be >= from" if to < from
      if from == to
        LazyList.from_element(self.at(from))
      elsif from > 0
        self.tail.at(from - 1..to - 1)
      elsif to > 1
        LazyList.new(self.first) do
          self.tail.at(0..(to - 1))
        end
      else # 0..1
        LazyList.new(self.first) do
          LazyList.cons(self.tail.first, EMPTY)
        end
      end
    else
      raise ArgumentError, "what shall I do with #{index.inspect}?"
    end
  end
  
  alias :[] :at

  # may not terminate!
  # TODO: Map implementation

  def to_s
    if empty?
      '()'
    else
      "#{first.to_s} . #{tail.to_s}"
    end
  end

  class Demo
    class << self
      # run this and watch Ruby's memory allocation. On my MacBook, it uses about 33MB with memoization turned off.
      # it grows uncontrollably with memoization on and grinds to a halt after reaching about the 500,000th element
      # and consuming approximately 1GB of memory.
      def stress_lazy_memoization
        s = ss = LazyList.from_range(1..1000000)
        until s.empty?
          n = s.first
          s = s.tail
          if n % 10000 == 0
            p n
            GC.start
          end
        end
      end
    end
  end

end

module LazyListTestCase

  def assert_contains_all expected, list, message = nil
    expected.each do |item|
      assert list.detect { |el| el == item }, message || "expected list to contain #{item.to_s}"
    end
  end

end

#!/usr/bin/env ruby
#
#  Created by Reginald Braithwaite on 2007-02-21.
#
#            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
#                    Version 2, December 2004
# 
# Copyright (C) 2004 Sam Hocevar
#  22 rue de Plaisance, 75014 Paris, France
# Everyone is permitted to copy and distribute verbatim or modified
# copies of this license document, and changing it is allowed as long
# as the name is changed.
# 
#            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
#   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
# 
#  0. You just DO WHAT THE FUCK YOU WANT TO.
#
# See http://sam.zoy.org/wtfpl/ for full license details
#
# Requires certain Ruby Facets: http://facets.rubyforge.org/

require "test/unit"
require "lazy_lists"
require 'ostruct'
require 'facets/core/enumerable/self/combinations'

class LazyListTest < Test::Unit::TestCase
  
  include LazyListTestCase
  
  ONE_TO_TEN = 1..10
  
  def test_basic_stream
    s = LazyList.from(ONE_TO_TEN)
    assert_equal(1, s.first)
    assert_equal(2, s.tail.first)
  end
  
  def test_laziness
    a = ONE_TO_TEN.map { |e| e }
    def a.[] index
      assert_equal(0, index, 'should never be indexing anything except the head of an array')
    end
    s = LazyList.from(a)
    assert_equal(1, s.first)
    assert_equal(2, s.tail.first)
  end
  
  def test_lazy_mapping
    s = LazyList.from(ONE_TO_TEN)
    s_never_accessed = s.map { |e| fail('mapping should be lazy') if e > 1 }
    s_accessed = s.map { |e| e * 2 }
    assert_equal(2, s_accessed.first)
    assert_equal(4, s_accessed.tail.first)
    assert_equal(LazyList.new, LazyList.new.map { |e| e })
  end
  
  def test_stream_edge_cases
    assert LazyList.from([]).empty?
    assert_nil LazyList.from([]).first
    assert LazyList.from([1]).tail.empty?
    assert_nil(LazyList.new.first)
    assert_nil(LazyList.new.tail)
    assert LazyList.new.empty?
  end
  
  def test_detect
    s = LazyList.from(ONE_TO_TEN)
    assert_equal(8, s.detect { |e| e == 8 })
    assert_nil(s.detect { |e| false })
    assert_nil(LazyList.new.detect { |e| true })
  end
  
  def test_equality
    assert_equal(LazyList.from([1, 2, 3]), LazyList.from([3, 2, 1].sort))
    assert_equal(LazyList.from([1, 2, 3]), [1, 2, 3])
    assert_equal(LazyList.from([[1], [2], [3]]), [[1], [2], [3]])
    
    assert_equal(LazyList.new, LazyList.from([]))
    assert_equal(LazyList.from([]), LazyList.new)
    
    assert_not_equal(LazyList.new, LazyList.from([1]))
    assert_not_equal(LazyList.from([]), LazyList.from([1]))
    assert_not_equal(LazyList.from([1]), LazyList.new)
    assert_not_equal(LazyList.from([1]), LazyList.from([]))
  end
  
  def test_range
    assert_equal(LazyList.from([1]), LazyList.from(1..1))
    assert_equal(LazyList.from(ONE_TO_TEN), LazyList.from(1..10))
  end
  
  def test_cons
    assert_equal(LazyList.from([1, 2, 3]), LazyList.cons(1, LazyList.from([2, 3])))
  end
  
  def test_merge_all
    assert_equal(LazyList.from_element(:x).merge_all, LazyList.from_element(:x), LazyList.from_element(:x).merge_all.to_s)
    assert_equal(LazyList.from([:x, :y]), LazyList.from([:x, :y]).merge_all)
    assert_equal(LazyList.from([:x, :y]), LazyList.from([:x, [:y]]).merge_all)
    assert_equal(LazyList.from([:x, :y]), LazyList.from([[:x], [:y]]).merge_all)
    one_to_ten = LazyList.from([LazyList.from(1..3), LazyList.from(4..6), LazyList.from(7..10)]).merge_all
    (1..10).each do |n|
      assert one_to_ten.detect { |x| x == n }
    end
  end
  
  def test_foldr
    assert_equal(15, LazyList[1, 2, 3, 4, 5].foldr { |acc, n| acc + n })
    assert_equal([1, 2, 3, 4, 5], LazyList.from(1..5).foldr([]) { |acc, n| acc.push(n) })
    LazyList.from(1..2).foldr() { |acc, n| fail if acc != 1 || n != 2 }
  end
  
  def test_unfoldr
    assert_equal(5, LazyList.unfoldr(0) { |last| last + 1 }.tail.tail.tail.tail.tail.first)
  end
  
   def test_product
     numbers = 1..10
     letters = 'a'..'j'
     l1 = LazyList.from(numbers)
     l2 = LazyList.from(letters)
     numbers_and_letters = l1 * l2 # { |n, l| fail if n > 1 }
     histogram = numbers_and_letters.foldr({}) do |hist, el|
       hist[el] ||= 0
       hist[el] = hist[el] + 1
       hist
     end
     assert_nil(histogram.values.detect { |n| n != 1 }, "there should be no repeated values: #{histogram.inspect}")
     assert_equal(numbers.to_a.size * letters.to_a.size, histogram.values.size)
   end
   
   def test_huge_pairwise
     wholes = LazyList.unfoldr(0) { |n| n + 1 }
     twins = wholes.pairwise(wholes)
     assert twins.detect { |arr| arr == [1000, 1000] }
   end
   
   def test_cartesian_product_binary
     numbers = 1..10
     letters = 'a'..'j'
     l1 = LazyList.from(numbers)
     l2 = LazyList.from(letters)
     numbers_and_letters = LazyList.cartesian_product(l1, l2) # { |n, l| fail if n > 1 }
     histogram = numbers_and_letters.foldr({}) do |hist, el|
       hist[el] ||= 0
       hist[el] = hist[el] + 1
       hist
     end
     assert_nil(histogram.values.detect { |n| n != 1 }, "there should be no repeated values: #{histogram.inspect}")
     assert_equal(numbers.to_a.size * letters.to_a.size, histogram.values.size)
   end
   
   def test_cartesian_product_ternary
     result = LazyList.cartesian_product LazyList.from('a'..'c'), LazyList.from(1..3), LazyList.from('x'..'y')
     assert_nil(result.detect { |r| r.size != 3 })
     assert_nil(result.detect { |r| !(1..3 === r[1]) })
     wholes = LazyList.unfoldr(0) { |n| n + 1 }
     result = LazyList.cartesian_product(wholes, wholes) { |x, y| OpenStruct.new(:x => x, :y => y)}
     h = {}
     1.upto(100) do
       element = result.first;
       result = result.tail;
       assert_nil(h[element], "#{element} is not unique")
       h[element] = true
       assert_not_nil(element.x);
       assert_not_nil(element.y);
     end
   end
   
   def test_product_maintains_order
     LazyList.from(1..3).product(LazyList.from(4..6)).foldr { |acc, arr| assert arr[0] < arr[1], "#{arr.inspect} is out of order" }
   end
   
   # contains_all is very expensive!
   def _____________________test_medium_product
     a = (1..5).to_a
     expected = Enumerable.combinations(a, a, a)
     prod = LazyList.cart(LazyList.from(a), LazyList.from(a), LazyList.from(a))
     assert_contains_all(expected, prod)
   end
  
    def test_at
      wholes = LazyList.unfoldr(0) { |n| n + 1 }
      assert_equal(6, wholes[6])
      six_to_ten = wholes[6..10]
      assert_equal(6, six_to_ten.first)
      assert_equal(10, six_to_ten.tail.tail.tail.tail.first)
      assert six_to_ten.tail.tail.tail.tail.tail.empty?
    end
    
    def test_at_edge_cases
      assert_equal(6,LazyList.wholes[6])
      assert_contains_all([6],LazyList.wholes[6..6])
    end
    
    def test_binary_search
      expected = [0.0, 0.0625, 0.125, 0.1875, 0.25, 0.3125, 0.375, 0.4375, 0.5, 0.5625, 0.625, 0.6875, 0.75, 0.8125, 0.875, 0.9375, 1.0]
      assert_contains_all(expected, LazyList.binary_search(0.0, 1.0)[0..16])
    end
    
    def test_cross_product
      whole_squared = LazyList.cross_product(LazyList.wholes, LazyList.wholes)
      assert_equal([0, 0], whole_squared[0])
      assert_contains_all([ [0, 0], [1, 0], [0, 1] ], whole_squared[0..2])
      assert_contains_all([ [0, 0], [1, 0], [0, 1], [2, 0], [1, 1], [0, 2] ], whole_squared[0..5])
    end
    
    def test_cross_product_block
      sums = LazyList.cross_product(LazyList.wholes, LazyList.wholes, LazyList.wholes) { |a, b, c| a + b + c }
      sums[1..3].each { |sum| assert_equal(1, sum) }
    end
    
    def test_while
      arr = []
      LazyList.wholes.each(:while => lambda { |n| n < 10 }) { |n| arr << n }
      assert_equal((0..9).to_a, arr)
    end
    
end