Class: Doku::DancingLinks::LinkMatrix::Column

Inherits:
Object
  • Object
show all
Includes:
HorizontalLinks, VerticalLinks
Defined in:
lib/doku/dancing_links.rb

Overview

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from HorizontalLinks

included, #insert_left, #reinsert_horizontal, #remove_horizontal

Methods included from Uninspectable

#inspect

Methods included from VerticalLinks

included, #insert_above, #reinsert_vertical, #remove_vertical

Constructor Details

#initialize(id) ⇒ Column

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



161
162
163
164
165
 
# File 'lib/doku/dancing_links.rb', line 161

def initialize(id)
  @up = @down = self
  @id = id
  @size = 0
end

Instance Attribute Details

#id ⇒ Object (readonly)

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.



152
153
154
 
# File 'lib/doku/dancing_links.rb', line 152

def id
  @id
end

#size ⇒ 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.



157
158
159
 
# File 'lib/doku/dancing_links.rb', line 157

def size
  @size
end

Instance Method Details

#cover ⇒ Object

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.



189
190
191
192
193
194
195
196
197
 
# 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? ⇒ Boolean

True if there are no more nodes in this column.

Returns:

  • (Boolean) 


214
215
216
 
# File 'lib/doku/dancing_links.rb', line 214

def empty?
  size == 0   # Equivalent to (down == self)
end

#nodes_downward ⇒ Object Also known as: nodes

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



168
169
170
 
# File 'lib/doku/dancing_links.rb', line 168

def nodes_downward
  LinkEnumerator.new :down, self
end

#nodes_upward ⇒ Object

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



173
174
175
 
# File 'lib/doku/dancing_links.rb', line 173

def nodes_upward
  LinkEnumerator.new :up, self
end

#uncover ⇒ Object

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



202
203
204
205
206
207
208
209
210
 
# 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