Struct xcov::Dlx

pub struct Dlx { /* private fields */ }

Lower level “dancing links” data structure described by Knuth for solving exact cover problems.

You probably don’t need to work with this type directly unless you are creating a custom implementation of ExactCoverProblem. See module documentation for additional details on how to use the default implementation.

Dlx supports optional secondary items which can be covered 0 or 1 times in a valid solution, as the ExactCoverProblem::search algorithm needs no modifications to support this extension.

Because this data structure involves rewriting linked list pointers on the fly, calling its methods in the wrong order will likely silently corrupt the links and yield garbage results. Read the documentation on its methods carefully. Enable debug_assert! for some additional sanity checks when debugging.

Implementations

impl Dlx

pub fn select_item(&mut self, item: usize)

Covers item and sets it as the current item.

Covering an item removes it from the set of outstanding uncovered items and marks all options that contain it as unavailabe for covering other options.

The selected item must not already be covered, and there must not be a current item already set.

Note that this method does not actually select an option, so in general, the next step after calling this method should be to select_option or undo_item if no more options are available.

pub fn undo_item(&mut self)

Undoes select_item.

pub fn next_option(&self, prev: Option<DlxOption>) -> Option<DlxOption>

Returns the next available option that includes the current item. Returns the first available option if prev is None. Returns None if prev is the last available option for the item.

This method must not be called if there is no current item.

pub fn select_option(&mut self, option: DlxOption)

Adds option to the candidate solution and covers all uncovered items included in the option.

This method must only be called when there is a current item set, and the option argument must include the current item. When called it unsets the current item.

pub fn try_undo_option(&mut self) -> Option<DlxOption>

Undoes the most recent select_option and returns the option that was deselected, or does nothing and returns None if there was nothing to undo.

This method must not be called when there is a current item. It restores the previous current item if an option was undone.

pub fn primary_items(&self) -> impl Iterator<Item = usize> + '_

Returns an iterator over the remaining uncovered primary items.

pub fn options_len(&self, item: usize) -> usize

Returns the number of currently available options that include item.

pub fn current_solution(&self) -> Option<&[DlxOption]>

Returns a slice of options in the currently selected solution, or None if not in a solved state. Use option_items to get the items in the option.

pub fn option_items(&self, option: DlxOption) -> &[usize]

Returns a slice of item indices in the given option.

Trait Implementations

impl AsRef<Dlx> for DlxBuilder

Provides a read-only view into the underlying Dlx

fn as_ref(&self) -> &Dlx

Converts this type into a shared reference of the (usually inferred) input type.