Класс DancingLinksMatrix

#include <dancing_links_matrix.h>

Классы
struct	Node

Открытые члены
	DancingLinksMatrix (int num_columns)
	Конструктор матрицы с заданным количеством столбцов
	~DancingLinksMatrix ()
	Деструктор, освобождает всю память
	DancingLinksMatrix (const DancingLinksMatrix &)=delete
DancingLinksMatrix &	operator= (const DancingLinksMatrix &)=delete
	DancingLinksMatrix (DancingLinksMatrix &&other) noexcept
	Конструктор перемещения
DancingLinksMatrix &	operator= (DancingLinksMatrix &&other) noexcept
	Оператор перемещения
void	addRow (std::span< const int > col_indices, int row_id)
	Добавляет строку в матрицу
void	cover (int col_idx)
	Покрывает столбец и все конфликтующие с ним строки
void	uncover (int col_idx)
	Восстанавливает ранее покрытый столбец (LIFO порядок).
std::optional< std::vector< int > >	search (int expected_solution_size=0)
	Поиск точного покрытия (алгоритм X).
bool	isCovered (int col_idx) const
	Проверяет, покрыт ли столбец
bool	isFullyUncovered () const
	Проверяет, все ли столбцы раскрыты
int	countColumns () const
	Возвращает количество столбцов в матрице

Конструктор(ы)

DancingLinksMatrix() [1/3]

DancingLinksMatrix::DancingLinksMatrix ( int num_columns )

explicit

Конструктор матрицы с заданным количеством столбцов

Аргументы

num_columns

количество столбцов в матрице

~DancingLinksMatrix()

DancingLinksMatrix::~DancingLinksMatrix

(

)

Деструктор, освобождает всю память

DancingLinksMatrix() [2/3]

DancingLinksMatrix::DancingLinksMatrix ( const DancingLinksMatrix & )

delete

DancingLinksMatrix() [3/3]

DancingLinksMatrix::DancingLinksMatrix ( DancingLinksMatrix && other )

noexcept

Конструктор перемещения

Методы

addRow()

void DancingLinksMatrix::addRow	(	std::span< const int >	col_indices,
		int	row_id )

Добавляет строку в матрицу

Аргументы

col_indices	список индексов столбцов, в которых в этой строке стоят единицы
row_id	уникальный идентификатор строки (возвращается в решении)

countColumns()

int DancingLinksMatrix::countColumns

(

)

const

Возвращает количество столбцов в матрице

cover()

void DancingLinksMatrix::cover

(

int

col_idx

)

Покрывает столбец и все конфликтующие с ним строки

Аргументы

col_idx

индекс столбца

isCovered()

bool DancingLinksMatrix::isCovered

(

int

col_idx

)

const

Проверяет, покрыт ли столбец

Аргументы

col_idx

индекс столбца

Возвращает

true если столбец уже покрыт, false иначе

isFullyUncovered()

bool DancingLinksMatrix::isFullyUncovered

(

)

const

Проверяет, все ли столбцы раскрыты

Возвращает

true если нет покрытых столбцов

operator=() [1/2]

DancingLinksMatrix & DancingLinksMatrix::operator= ( const DancingLinksMatrix & )

delete

operator=() [2/2]

DancingLinksMatrix & DancingLinksMatrix::operator= ( DancingLinksMatrix && other )

noexcept

Оператор перемещения

search()

std::optional< std::vector< int > > DancingLinksMatrix::search

(

int

expected_solution_size = 0

)

Поиск точного покрытия (алгоритм X).

Аргументы

expected_solution_size

ожидаемый размер решения (для резервирования памяти)

Возвращает

решение в виде списка row_id, либо std::nullopt если решения нет

uncover()

void DancingLinksMatrix::uncover

(

int

col_idx

)

Восстанавливает ранее покрытый столбец (LIFO порядок).

Аргументы

col_idx

индекс столбца

---

Объявления и описания членов классов находятся в файлах:

• include/dancing_links/dancing_links_matrix.h
• src/dancing_links/dancing_links_matrix.cpp