ferencd@0: #---
ferencd@0: # Excerpted from "Mazes for Programmers",
ferencd@0: # published by The Pragmatic Bookshelf.
ferencd@0: # Copyrights apply to this code. It may not be used to create training material, 
ferencd@0: # courses, books, articles, and the like. Contact us if you are in doubt.
ferencd@0: # We make no guarantees that this code is fit for any purpose. 
ferencd@0: # Visit http://www.pragmaticprogrammer.com/titles/jbmaze for more book information.
ferencd@0: #---
ferencd@0: class Ellers
ferencd@0: 
ferencd@0:   class RowState
ferencd@0:     def initialize(starting_set=0)
ferencd@0:       @cells_in_set = {}
ferencd@0:       @set_for_cell = []
ferencd@0:       @next_set = starting_set
ferencd@0:     end
ferencd@0: 
ferencd@0:     def record(set, cell)
ferencd@0:       @set_for_cell[cell.column] = set
ferencd@0: 
ferencd@0:       @cells_in_set[set] = [] if !@cells_in_set[set]
ferencd@0:       @cells_in_set[set].push cell
ferencd@0:     end
ferencd@0: 
ferencd@0:     def set_for(cell)
ferencd@0:       if !@set_for_cell[cell.column]
ferencd@0:         record(@next_set, cell)
ferencd@0:         @next_set += 1
ferencd@0:       end
ferencd@0: 
ferencd@0:       @set_for_cell[cell.column]
ferencd@0:     end
ferencd@0: 
ferencd@0:     def merge(winner, loser)
ferencd@0:       @cells_in_set[loser].each do |cell|
ferencd@0:         @set_for_cell[cell.column] = winner
ferencd@0:         @cells_in_set[winner].push cell
ferencd@0:       end
ferencd@0: 
ferencd@0:       @cells_in_set.delete(loser)
ferencd@0:     end
ferencd@0: 
ferencd@0:     def next
ferencd@0:       RowState.new(@next_set)
ferencd@0:     end
ferencd@0: 
ferencd@0:     def each_set
ferencd@0:       @cells_in_set.each { |set, cells| yield set, cells }
ferencd@0:       self
ferencd@0:     end
ferencd@0:   end
ferencd@0: 
ferencd@0:   def on(grid)
ferencd@0:     row_state = RowState.new
ferencd@0: 
ferencd@0:     grid.each_row do |row|
ferencd@0:       row.each do |cell| 
ferencd@0:         next unless cell.west 
ferencd@0: 
ferencd@0:         set = row_state.set_for(cell) 
ferencd@0:         prior_set = row_state.set_for(cell.west) 
ferencd@0: 
ferencd@0:         should_link = set != prior_set && 
ferencd@0:                       (cell.south.nil? || rand(2) == 0)
ferencd@0: 
ferencd@0:         if should_link
ferencd@0:           cell.link(cell.west)
ferencd@0:           row_state.merge(prior_set, set) 
ferencd@0:         end
ferencd@0:       end
ferencd@0: 
ferencd@0:       if row[0].south 
ferencd@0:         next_row = row_state.next 
ferencd@0: 
ferencd@0:         row_state.each_set do |_, list|
ferencd@0:           list.shuffle.each_with_index do |cell, index| 
ferencd@0:             if index == 0 || rand(3) == 0
ferencd@0:               cell.link(cell.south) 
ferencd@0:               next_row.record(row_state.set_for(cell), cell.south) 
ferencd@0:             end
ferencd@0:           end
ferencd@0:         end
ferencd@0: 
ferencd@0:         row_state = next_row 
ferencd@0:       end
ferencd@0:     end
ferencd@0:   end
ferencd@0: 
ferencd@0: end