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
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.
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
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
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
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
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
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
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