class ExactCover::MatrixPreprocessor
Transforms an array into a linked list of data and column objects
Attributes
col_count[R]
matrix[R]
row_count[R]
Public Class Methods
new(matrix)
click to toggle source
# File lib/exact_cover/matrix_preprocessor.rb, line 8 def initialize(matrix) @matrix = matrix @row_count = matrix.size @col_count = matrix[0].size end
Public Instance Methods
call()
click to toggle source
# File lib/exact_cover/matrix_preprocessor.rb, line 14 def call # Generates the column objects headers = [] (0..col_count - 1).each do |col| col_size = size(col) headers[col] = ColumnObject.new(col_size, col.to_s) end # Fill the left and right for each header object prev = headers[-1] headers.each do |current| current.left = prev prev.right = current prev = current end # Generates the data objects (one for each 1 in the matrix) data_objects = [] row_objects_array = [] col_objects_array = [] (0..row_count - 1).each do |row| data_objects[row] = [] row_objects_array[row] = [] (0..col_count - 1).each do |col| column = headers[col] col_objects_array[col] = [column] if col_objects_array[col].nil? next unless matrix[row][col] == 1 data_object = DataObject.new(column) data_objects[row][col] = data_object row_objects_array[row] << data_object col_objects_array[col] << data_object end end # Fill the left and right fields row_objects_array.each do |row_objects| prev = row_objects[-1] loop do break if row_objects.empty? current = row_objects.shift current.left = prev prev.right = current prev = current end end # Fill the up and down fields col_objects_array.each do |col_objects| prev = col_objects[-1] loop do break if col_objects.empty? current = col_objects.shift current.up = prev prev.down = current prev = current end end # insert the root between headers[-1] and headers[0] root = ColumnObject.new(0, "root") headers[-1].right = root headers[0].left = root root.right = headers[0] root.left = headers[-1] root end
Private Instance Methods
size(col)
click to toggle source
@return [Integer] Number of 1 in the given column
# File lib/exact_cover/matrix_preprocessor.rb, line 88 def size(col) size = 0 (0..row_count - 1).each do |row| size += 1 if matrix[row][col] == 1 end size end