Struct TrailedDomains 

pub struct TrailedDomains { /* private fields */ }

A HashMap<VariableId, Domain> that records the pre-mutation value of every domain accessed mutably, so a search node can be undone in O(changed) by restoring only the domains that were actually touched — instead of an O(N) full-map clone of all N domains at every node.

Reference:

• Schulte, C. (1999). Comparing trailing and copying for constraint programming. ICLP 1999, 275-289. (Trailing vs. copying as the two classical state-restoration strategies for CSP search; this type implements trailing.)

Read access is available via std::ops::Deref to the underlying HashMap, so existing read-only call sites (domains.get(&var), domains.contains_key(&var), …) work unchanged. There is deliberately no DerefMut: mutation must go through Self::get_mut, the only way to record an undo entry, so Self::undo_to can never miss a change.

Implementations

impl TrailedDomains

pub fn new(domains: HashMap<VariableId, Domain>) -> Self

Wraps domains with an empty trail.

Complexity

Time & Space: O(1) (takes ownership; no copy).

pub fn get_mut(&mut self, var: &VariableId) -> Option<&mut Domain>

Returns a mutable reference to var’s domain, first recording its current value on the trail so Self::undo_to can restore it later. Returns None if var is untracked.

Shadows HashMap::get_mut (an inherent method takes priority over the Deref target’s), so existing domains.get_mut(&var) call sites route through here automatically.

Complexity

Time: O(1) amortized, plus the cost of cloning the domain being recorded (O(1) for Domain::Range, O(D) for Domain::Explicit).

pub fn mutate( &mut self, var: VariableId, narrow: impl FnOnce(&mut Domain) -> bool, ) -> Option<bool>

Applies narrow to var’s domain, recording an undo entry only if narrow reports (via its bool return) that it actually modified the domain.

Prefer this over Self::get_mut when a call site probes many variables per propagation step but expects only a few to actually change (e.g. a newly-fixed value pruned from every other variable in a wide AllDifferent scope, most of which don’t contain it anyway): get_mut would record — and later have to undo — an entry for every probed variable regardless of whether anything changed.

Returns None if var is untracked, Some(changed) otherwise.

Complexity

Time: O(1) amortized, plus the cost of cloning the domain being probed (O(1) for Domain::Range, O(D) for Domain::Explicit) — paid once per call regardless of whether narrow reports a change, since the pre-mutation value must be captured before narrow runs.

pub fn checkpoint(&self) -> usize

Returns a checkpoint identifying the current trail position, to later pass to Self::undo_to.

Complexity

Time & Space: O(1).

pub fn undo_to(&mut self, checkpoint: usize)

Restores every domain mutated since checkpoint, in reverse order, back to its pre-mutation value.

Complexity

Time: O(K) where K is the number of mutations recorded since checkpoint (not O(N)).

pub fn changed_since( &self, checkpoint: usize, ) -> impl Iterator<Item = VariableId> + '_

Returns the distinct variables with a trail entry recorded since checkpoint, i.e. the variables Self::get_mut/Self::mutate touched. Used by the propagation engine’s event-based re-enqueueing (see plan/11-search-heuristics-and-global-constraints.md, part B) to learn exactly which of a constraint’s scope variables it modified during a propagate() call — reusing the trail already recorded for undo instead of re-deriving the same information via extra domain lookups.

May over-report a variable whose net effect was a no-op if a caller used Self::get_mut (which records unconditionally) rather than Self::mutate (which only records on a confirmed change) — callers that need exactness should prefer mutate.

Panics

If checkpoint exceeds the current trail length. Valid checkpoints are values previously returned by Self::checkpoint on this same instance — as with Self::undo_to, a checkpoint from before an intervening undo_to call is no longer valid.

Complexity

Time: O(K) where K = trail entries since checkpoint. Space: O(distinct variables touched).

Methods from Deref<Target = HashMap<VariableId, Domain>>

pub fn capacity(&self) -> usize

Returns the number of elements the map can hold without reallocating.

This number is a lower bound; the HashMap<K, V> might be able to hold more, but is guaranteed to be able to hold at least this many.

Examples

use std::collections::HashMap;
let map: HashMap<i32, i32> = HashMap::with_capacity(100);
assert!(map.capacity() >= 100);

pub fn keys(&self) -> Keys<'_, K, V>

An iterator visiting all keys in arbitrary order. The iterator element type is &'a K.

Examples

use std::collections::HashMap;

let map: HashMap<&str, i32> = HashMap::from([
    ("a", 1),
    ("b", 2),
    ("c", 3),
]);

let mut values: Vec<_> = map.keys().copied().collect();
values.sort();

assert_eq!(values, vec!["a", "b", "c"]);

Performance

In the current implementation, iterating over keys takes O(capacity) time instead of O(len) because it internally visits empty buckets too.

pub fn values(&self) -> Values<'_, K, V>

An iterator visiting all values in arbitrary order. The iterator element type is &'a V.

Examples

use std::collections::HashMap;

let map: HashMap<&str, i32> = HashMap::from([
    ("a", 1),
    ("b", 2),
    ("c", 3),
]);

let mut values: Vec<_> = map.values().copied().collect();
values.sort();

assert_eq!(values, vec![1, 2, 3]);

Performance

In the current implementation, iterating over values takes O(capacity) time instead of O(len) because it internally visits empty buckets too.

pub fn iter(&self) -> Iter<'_, K, V>

An iterator visiting all key-value pairs in arbitrary order. The iterator element type is (&'a K, &'a V).

Examples

use std::collections::HashMap;

let map = HashMap::from([
    ("a", 1),
    ("b", 2),
    ("c", 3),
]);

let mut count = 0;

for (_key, _val) in map.iter() {
    count += 1;
}

assert_eq!(count, 3);

Performance

In the current implementation, iterating over map takes O(capacity) time instead of O(len) because it internally visits empty buckets too.

pub fn len(&self) -> usize

Returns the number of elements in the map.

Examples

use std::collections::HashMap;

let mut a = HashMap::new();
assert_eq!(a.len(), 0);
a.insert(1, "a");
assert_eq!(a.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

Examples

use std::collections::HashMap;

let mut a = HashMap::new();
assert!(a.is_empty());
a.insert(1, "a");
assert!(!a.is_empty());

pub fn hasher(&self) -> &S

Returns a reference to the map’s BuildHasher.

Examples

use std::collections::HashMap;
use std::hash::RandomState;

let hasher = RandomState::new();
let map: HashMap<i32, i32> = HashMap::with_hasher(hasher);
let hasher: &RandomState = map.hasher();

pub fn get<Q>(&self, k: &Q) -> Option<&V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a reference to the value corresponding to the key.

The key may be any borrowed form of the map’s key type, but Hash and Eq on the borrowed form must match those for the key type.

Examples

use std::collections::HashMap;

let mut map = HashMap::new();
map.insert(1, "a");
assert_eq!(map.get(&1), Some(&"a"));
assert_eq!(map.get(&2), None);

pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns the key-value pair corresponding to the supplied key. This is potentially useful:

• for key types where non-identical keys can be considered equal;
• for getting the &K stored key value from a borrowed &Q lookup key; or
• for getting a reference to a key with the same lifetime as the collection.

The supplied key may be any borrowed form of the map’s key type, but Hash and Eq on the borrowed form must match those for the key type.

Examples

use std::collections::HashMap;
use std::hash::{Hash, Hasher};

#[derive(Clone, Copy, Debug)]
struct S {
    id: u32,
    name: &'static str, // ignored by equality and hashing operations
}

impl PartialEq for S {
    fn eq(&self, other: &S) -> bool {
        self.id == other.id
    }
}

impl Eq for S {}

impl Hash for S {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.id.hash(state);
    }
}

let j_a = S { id: 1, name: "Jessica" };
let j_b = S { id: 1, name: "Jess" };
let p = S { id: 2, name: "Paul" };
assert_eq!(j_a, j_b);

let mut map = HashMap::new();
map.insert(j_a, "Paris");
assert_eq!(map.get_key_value(&j_a), Some((&j_a, &"Paris")));
assert_eq!(map.get_key_value(&j_b), Some((&j_a, &"Paris"))); // the notable case
assert_eq!(map.get_key_value(&p), None);

pub fn contains_key<Q>(&self, k: &Q) -> bool

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns true if the map contains a value for the specified key.

The key may be any borrowed form of the map’s key type, but Hash and Eq on the borrowed form must match those for the key type.

Examples

use std::collections::HashMap;

let mut map = HashMap::new();
map.insert(1, "a");
assert_eq!(map.contains_key(&1), true);
assert_eq!(map.contains_key(&2), false);

Trait Implementations

impl Clone for TrailedDomains

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for TrailedDomains

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for TrailedDomains

fn default() -> Self

Returns the “default value” for a type.

impl Deref for TrailedDomains

type Target = HashMap<VariableId, Domain>

The resulting type after dereferencing.

fn deref(&self) -> &HashMap<VariableId, Domain>

Dereferences the value.