class Doku::DancingLinks::LinkMatrix::Column

The Column Header object from Knuth. This object represents a requirement that needs to be satisfied at least once in the exact coer problem.

Attributes

id[R]

An ID object provided by the user to give meaning to the column. This is the N relation from Knuth. The ID can be any object.

size[RW]

The current number of nodes in this column. If this is zero, it means the column can not be covered, given choices that have already been made.

Public Class Methods

new(id) click to toggle source

Initializes an empty column with the specified id. The ID can be any object.

# File lib/doku/dancing_links.rb, line 161
def initialize(id)
  @up = @down = self
  @id = id
  @size = 0
end

Public Instance Methods

cover() click to toggle source

Covers the column. This algorithm comes from page 6 of Knuth’s paper. This operation removes the column from the list of columns that needs to be covered and it removes all rows that would cover this column. This can be efficiently undone with {#uncover}.

The word “cover” here means the same thing it does in the phrase “exact cover problem”. Our goal is to cover every column exactly once using this method.

# File lib/doku/dancing_links.rb, line 189
def cover
  remove_horizontal
  nodes_downward.each do |i|
    i.nodes_except_self_rightward.each do |j|
      j.remove_vertical
      j.column.size -= 1
    end
  end
end
empty?() click to toggle source

True if there are no more nodes in this column. @return (Boolean)

# File lib/doku/dancing_links.rb, line 214
def empty?
  size == 0   # Equivalent to (down == self)
end
nodes()
Alias for: nodes_downward
nodes_downward() click to toggle source

All the nodes in this column, starting at the top one and going down.

# File lib/doku/dancing_links.rb, line 168
def nodes_downward
  LinkEnumerator.new :down, self
end
Also aliased as: nodes
nodes_upward() click to toggle source

All the nodes in this column, starting at the bottom one and going up.

# File lib/doku/dancing_links.rb, line 173
def nodes_upward
  LinkEnumerator.new :up, self
end
uncover() click to toggle source

Uncovers the column. This algorithm comes from page 6 of Knuth’s paper. This operation undoes the effects of {#cover}.

# File lib/doku/dancing_links.rb, line 202
def uncover
  nodes_upward.each do |i|
    i.nodes_except_self_leftward.each do |j|
      j.column.size += 1
      j.reinsert_vertical
    end
  end
  reinsert_horizontal
end