<commit_before>require_relative 'header'
require_relative 'node'

module Dlx
  class SparseMatrix
    attr_reader :header_index, :width, :height

    def initialize
      @header_index = Dlx::Header.new(0, -1)
      @string_rows = Array.new
      @width = @height = 0
    end

    def <<(string)
      add(string)
    end

    def add(string)
      raise ArgumentError, "Empty string" if string.empty?
      if @width == 0
        @width = string.length
      elsif string.length != @width
        raise ArgumentError, "Width is: #{string.length}, expected: #{@width}"
      end
      @string_rows << string
      @height += 1
      self
    end

    def solve(&block)
      @solution = Array.new
      create_matrix
      if block
        search(&block)
      else
        solutions = Array.new
        search { |solution| solutions << solution }
        solutions
      end
    end

    # Yields each solution, if any.
    def search(&b)
      if next_header.nil?
        b.call(@solution.dup)
      else
        header = next_header
        cover(header)

        header.each_in(:down) do |rowNode|
          @solution.push(@string_rows[rowNode.row - 1])

          rowNode.each_in(:right) do |rightNode|
            cover(rightNode)
          end

          search(&b)
          @solution.pop

          rowNode.each_in(:left) do |leftNode|
            uncover(leftNode)
          end
        end
        uncover(header)
      end
    end

    # Returns header with least total.
    def next_header
      unless defined? @matrix
        create_matrix
      end

      min_header = nil
      @header_index.each_in(:right) do |header|
        if !min_header || header.total < min_header.total
          min_header = header
        end
      end
      min_header
    end

    # Removes given node's column from matrix. Removes each node in same row as
    # given node from their columns
    def cover(node)
      node.header.remove(:row)
      node.header.each_in(:down) do |row|
        row.each_in(:right) do |n|
          n.remove(:column)
        end
      end
    end

    # Reverses cover.
    def uncover(node)
      node.header.each_in(:up) do |row|
        row.each_in(:left) do |n|
          n.restore(:column)
        end
      end
      node.header.restore(:row)
    end

    def create_matrix
      raise ArgumentError, "No rows added!" if @height == 0

      @matrix = Hash.new { |h,k| h[k] = Hash.new }

      # Set column headers.
      (0...@width).each { |j| @matrix[0][j] = Dlx::Header.new(0, j) }

      # Create nodes
      @string_rows.each.with_index(1) do |row, i|
        row.each_char.with_index do |letter, j|
          @matrix[i][j] = Dlx::Node.new(i, j) if letter == "1"
        end
      end

      # Link header index.
      @header_index.right = @matrix[0][0]
      @header_index.left  = @matrix[0][@width - 1]

      # Link nodes
      (0..@height).each do |i|
        (0...@width).each do |j|
          next unless node = @matrix[i][j]
          node.up    = next_in(:up,    i, j)
          node.right = next_in(:right, i, j)
          node.down  = next_in(:down,  i, j)
          node.left  = next_in(:left,  i, j)
        end
      end

      # (Re)link first and last to header
      @matrix[0][0].left    = @header_index if @matrix[0][0]
      @matrix[0][@width - 1].right = @header_index if header_end = @matrix[0][@width - 1]

      @matrix
    end

    private

    # Find next node in dir, starting from node.
    def next_in(dir, i, j)
      node = nil
      loop do
        case dir
        when :up
          i = (i - 1) % (@height + 1)
        when :right
          j = (j + 1) % @width
        when :down
          i = (i + 1) % (@height + 1)
        when :left
          j = (j - 1) % @width
        end
        return node if node = @matrix[i][j]
      end
    end
  end
end<commit_msg>Refactor sparse_matrix<commit_after>require_relative 'header'
require_relative 'node'

module Dlx
  class SparseMatrix
    attr_reader :header_index, :width, :height

    def initialize
      @header_index = Dlx::Header.new(0, -1)
      @string_rows = Array.new
      @width = @height = 0
    end

    def <<(string)
      add(string)
    end

    def add(string)
      raise ArgumentError, "Empty string" if string.empty?
      if @width == 0
        @width = string.length
      elsif string.length != @width
        raise ArgumentError, "Width is: #{string.length}, expected: #{@width}"
      end
      @string_rows << string
      @height += 1
      self
    end

    def solve(&block)
      @solution = Array.new
      create_matrix
      if block
        search(&block)
      else
        solutions = Array.new
        search { |solution| solutions << solution }
        solutions
      end
    end

    # Returns header with least total.
    def next_header
      unless defined? @matrix
        create_matrix
      end

      min_header = nil
      @header_index.each_in(:right) do |header|
        if !min_header || header.total < min_header.total
          min_header = header
        end
      end
      min_header
    end

    # Removes given node's column from matrix. Removes each node in same row as
    # given node from their columns
    def cover(node)
      node.header.remove(:row)
      node.header.each_in(:down) do |row|
        row.each_in(:right) do |n|
          n.remove(:column)
        end
      end
    end

    # Reverses cover.
    def uncover(node)
      node.header.each_in(:up) do |row|
        row.each_in(:left) do |n|
          n.restore(:column)
        end
      end
      node.header.restore(:row)
    end

    # Creates a matrix from the added rows.  @header_index is created at row=0,
    # col=-1.  It also adds a row of header nodes at row=0, starting at col=1.
    def create_matrix
      raise ArgumentError, "No rows added!" if @height == 0

      @matrix = Hash.new { |h,k| h[k] = Hash.new }

      # Set column headers.
      (0...@width).each { |j| @matrix[0][j] = Dlx::Header.new(0, j) }

      # Create nodes
      @string_rows.each.with_index(1) do |row, i|
        row.each_char.with_index do |letter, j|
          @matrix[i][j] = Dlx::Node.new(i, j) if letter == "1"
        end
      end

      # Link header index.
      @header_index.right = @matrix[0][0]
      @header_index.left  = @matrix[0][@width - 1]

      # Link nodes
      (0..@height).each do |i|
        (0...@width).each do |j|
          next unless node = @matrix[i][j]
          node.up    = next_in(:up,    i, j)
          node.right = next_in(:right, i, j)
          node.down  = next_in(:down,  i, j)
          node.left  = next_in(:left,  i, j)
        end
      end

      # (Re)link first and last to header
      @matrix[0][0].left    = @header_index if @matrix[0][0]
      @matrix[0][@width - 1].right = @header_index if header_end = @matrix[0][@width - 1]

      @matrix
    end

    # Find next node in dir, starting from position i, j in the matrix.
    def next_in(dir, i, j)
      node = nil
      loop do
        case dir
        when :up
          i = (i - 1) % (@height + 1)
        when :right
          j = (j + 1) % @width
        when :down
          i = (i + 1) % (@height + 1)
        when :left
          j = (j - 1) % @width
        end
        return node if node = @matrix[i][j]
      end
    end

    private

    def search(&b)
      if next_header.nil?
        b.call(@solution.dup)
      else
        header = next_header
        cover(header)

        header.each_in(:down) do |rowNode|
          @solution.push(@string_rows[rowNode.row - 1])

          rowNode.each_in(:right) do |rightNode|
            cover(rightNode)
          end

          search(&b)
          @solution.pop

          rowNode.each_in(:left) do |leftNode|
            uncover(leftNode)
          end
        end
        uncover(header)
      end
    end
  end
end
{'fraction_non_alphanumeric': 0.11482948013794865, 'fraction_numerical': 0.008685655894750288, 'mean_word_length': 1.7551020408163265, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5685508', 'n_tokens_mistral': 2600, 'n_tokens_neox': 2500, 'n_words': 698}