Crate contrail

Simple state restoration for backtracking search algorithms using a trail.

During a typical branching search algorithm, the search state must be cloned at each branch point in order to explore the branches independently. contrail provides a framework to create search algorithms that only require a partial clone of the search state at each branch point. This is facilitated by the trail, a struct where all search state is stored.

This library is based on the memory model used by Minion, a C++ constraint satisfaction problem solver.

Limitations

The main limitation of contrail is that once a trail has been created using a trail builder, nothing can be added to the trail. This is to prevent dangling pointers.

Modules

mem

Low-level memory management.

storage

High-level memory management.

Structs

Array

A reference to a fixed-length array of values stored on the trail.

ArrayIter

An iterator over the values of an Array.

Trail

The trail itself.

TrailBuilder

A builder to create a Trail.

Value

A reference to a value stored on the trail.

Type Aliases

BacktrackableArray

A fixed-length array stored on the trail in backtrackable memory.

BacktrackableValue

A value stored on the trail in backtrackable memory.

NonBacktrackableArray

A fixed-length array stored on the trail in non-backtrackable memory.

NonBacktrackableValue

A value stored on the trail in non-backtrackable memory.