Class: Doku::DancingLinks::LinkMatrix::Node

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

Overview

This class represents a normal node in Knuth’s Doku::DancingLinks::LinkMatrix. Every node belongs to a column and a row, and it represents the fact that the row (i.e. set) “covers” the column.

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

Instance Attribute Details

#column ⇒ Object

The Column object that this node belongs to.



226
227
228
 
# File 'lib/doku/dancing_links.rb', line 226

def column
  @column
end

#row_id ⇒ Object

The user-assigned ID of the row this node belongs to.



229
230
231
 
# File 'lib/doku/dancing_links.rb', line 229

def row_id
  @row_id
end

Instance Method Details

#choose ⇒ Object

Removes a row from the Doku::DancingLinks::LinkMatrix by covering every column that it touches.



254
255
256
257
258
 
# File 'lib/doku/dancing_links.rb', line 254

def choose
  nodes_rightward.each do |node|
    node.column.cover
  end
end

#choose_except_self_column ⇒ Object

Removes a row from the Doku::DancingLinks::LinkMatrix by covering every column that it touches EXCEPT self.column, which is assumed to already be covered. This represents (tentatively) choosing the node’s row to be in our exact cover. When that choice is proven to not work, this action can be efficiently undone with #unchoose_except_self_column.



267
268
269
270
271
 
# File 'lib/doku/dancing_links.rb', line 267

def choose_except_self_column
  nodes_except_self_rightward.each do |node|
    node.column.cover
  end
end

#nodes_except_self_leftward ⇒ Object

All nodes in the same row, starting with self and going to the left, but not including self.



244
245
246
 
# File 'lib/doku/dancing_links.rb', line 244

def nodes_except_self_leftward
  LinkEnumerator.new :left, self
end

#nodes_except_self_rightward ⇒ Object Also known as: nodes_except_self

All nodes in the same row, starting with self and going to the right, but not including self.



238
239
240
 
# File 'lib/doku/dancing_links.rb', line 238

def nodes_except_self_rightward
  LinkEnumerator.new :right, self
end

#nodes_rightward ⇒ Object Also known as: nodes

All nodes in the same row, starting with self and going to the right.



232
233
234
 
# File 'lib/doku/dancing_links.rb', line 232

def nodes_rightward
  LinkEnumerator.new :right, self, true
end

#unchoose_except_self_column ⇒ Object

Undoes the effect of #choose_except_self_column, putting the nodes of the row back into the Doku::DancingLinks::LinkMatrix.



275
276
277
278
279
 
# File 'lib/doku/dancing_links.rb', line 275

def unchoose_except_self_column
  nodes_except_self_leftward.each do |node|
    node.column.uncover
  end
end