solverforge_solver/heuristic/move/
metadata.rs

1use std::collections::hash_map::DefaultHasher;
2use std::fmt::Debug;
3use std::hash::{Hash, Hasher};
4
5use smallvec::{smallvec, SmallVec};
6
7pub const NONE_ID: u64 = u64::MAX;
8pub type MoveIdentity = SmallVec<[u64; 8]>;
9
10/// Canonical tabu metadata for one move candidate.
11///
12/// The canonical local-search path uses this structure to drive all tabu
13/// dimensions from one source of truth:
14/// - `entity_tokens` for entity tabu
15/// - `destination_value_tokens` for value tabu
16/// - `move_id` for exact move tabu
17/// - `undo_move_id` for reverse-move tabu
18///
19/// Exact-move identities intentionally stay as ordered raw components rather
20/// than pre-hashed scalars so exact and reverse memories retain their original
21/// structure.
22#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
23pub struct MoveTabuScope {
24    pub descriptor_index: usize,
25    pub variable_name: &'static str,
26}
27
28impl MoveTabuScope {
29    pub const fn new(descriptor_index: usize, variable_name: &'static str) -> Self {
30        Self {
31            descriptor_index,
32            variable_name,
33        }
34    }
35
36    pub const fn entity_token(self, entity_id: u64) -> ScopedEntityTabuToken {
37        ScopedEntityTabuToken {
38            scope: self,
39            entity_id,
40        }
41    }
42
43    pub const fn value_token(self, value_id: u64) -> ScopedValueTabuToken {
44        ScopedValueTabuToken {
45            scope: self,
46            value_id,
47        }
48    }
49}
50
51#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
52pub struct ScopedEntityTabuToken {
53    pub scope: MoveTabuScope,
54    pub entity_id: u64,
55}
56
57#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
58pub struct ScopedValueTabuToken {
59    pub scope: MoveTabuScope,
60    pub value_id: u64,
61}
62
63#[derive(Clone, Debug, PartialEq, Eq)]
64pub struct MoveTabuSignature {
65    pub scope: MoveTabuScope,
66    pub entity_tokens: SmallVec<[ScopedEntityTabuToken; 2]>,
67    pub destination_value_tokens: SmallVec<[ScopedValueTabuToken; 2]>,
68    pub move_id: MoveIdentity,
69    pub undo_move_id: MoveIdentity,
70}
71
72impl MoveTabuSignature {
73    pub fn new(scope: MoveTabuScope, move_id: MoveIdentity, undo_move_id: MoveIdentity) -> Self {
74        Self {
75            scope,
76            entity_tokens: SmallVec::new(),
77            destination_value_tokens: SmallVec::new(),
78            move_id,
79            undo_move_id,
80        }
81    }
82
83    pub fn with_entity_tokens<I>(mut self, entity_tokens: I) -> Self
84    where
85        I: IntoIterator<Item = ScopedEntityTabuToken>,
86    {
87        self.entity_tokens = entity_tokens.into_iter().collect();
88        self
89    }
90
91    pub fn with_destination_value_tokens<I>(mut self, destination_value_tokens: I) -> Self
92    where
93        I: IntoIterator<Item = ScopedValueTabuToken>,
94    {
95        self.destination_value_tokens = destination_value_tokens.into_iter().collect();
96        self
97    }
98}
99
100pub(crate) fn encode_usize(value: usize) -> u64 {
101    value as u64
102}
103
104pub(crate) fn encode_option_usize(value: Option<usize>) -> u64 {
105    value.map_or(NONE_ID, encode_usize)
106}
107
108pub(crate) fn hash_str(value: &str) -> u64 {
109    let mut hasher = DefaultHasher::new();
110    value.hash(&mut hasher);
111    hasher.finish()
112}
113
114pub(crate) fn hash_debug<T: Debug>(value: &T) -> u64 {
115    let mut hasher = DefaultHasher::new();
116    format!("{value:?}").hash(&mut hasher);
117    hasher.finish()
118}
119
120pub(crate) fn encode_option_debug<T: Debug>(value: Option<&T>) -> u64 {
121    value.map_or(NONE_ID, hash_debug)
122}
123
124pub(crate) const TABU_OP_SWAP: u64 = 0xF000_0000_0000_0001;
125pub(crate) const TABU_OP_PILLAR_SWAP: u64 = 0xF000_0000_0000_0002;
126pub(crate) const TABU_OP_LIST_SWAP: u64 = 0xF000_0000_0000_0003;
127pub(crate) const TABU_OP_LIST_REVERSE: u64 = 0xF000_0000_0000_0004;
128
129pub(crate) fn scoped_move_identity(
130    scope: MoveTabuScope,
131    operation_id: u64,
132    components: impl IntoIterator<Item = u64>,
133) -> MoveIdentity {
134    let mut identity = smallvec![
135        operation_id,
136        encode_usize(scope.descriptor_index),
137        hash_str(scope.variable_name),
138    ];
139    identity.extend(components);
140    identity
141}
142
143pub(crate) fn ordered_coordinate_pair(first: (u64, u64), second: (u64, u64)) -> [(u64, u64); 2] {
144    if first <= second {
145        [first, second]
146    } else {
147        [second, first]
148    }
149}
150
151pub(crate) fn append_canonical_usize_slice_pair(
152    identity: &mut MoveIdentity,
153    left: &[usize],
154    right: &[usize],
155) {
156    let (first, second) = if left <= right {
157        (left, right)
158    } else {
159        (right, left)
160    };
161    identity.push(encode_usize(first.len()));
162    identity.push(encode_usize(second.len()));
163    identity.extend(first.iter().map(|&idx| encode_usize(idx)));
164    identity.push(NONE_ID);
165    identity.extend(second.iter().map(|&idx| encode_usize(idx)));
166}
167
168fn append_unique_tokens<T>(target: &mut SmallVec<[T; 2]>, tokens: &[T])
169where
170    T: Copy + PartialEq,
171{
172    for &token in tokens {
173        if !target.contains(&token) {
174            target.push(token);
175        }
176    }
177}
178
179pub(crate) fn compose_sequential_tabu_signature(
180    prefix: &'static str,
181    left: &MoveTabuSignature,
182    right: &MoveTabuSignature,
183) -> MoveTabuSignature {
184    let mut entity_tokens = left.entity_tokens.clone();
185    append_unique_tokens(&mut entity_tokens, &right.entity_tokens);
186
187    let mut destination_value_tokens = left.destination_value_tokens.clone();
188    append_unique_tokens(
189        &mut destination_value_tokens,
190        &right.destination_value_tokens,
191    );
192
193    let mut move_id = smallvec![hash_str(prefix)];
194    move_id.extend(left.move_id.iter().copied());
195    move_id.extend(right.move_id.iter().copied());
196
197    let mut undo_move_id = smallvec![hash_str(prefix)];
198    undo_move_id.extend(right.undo_move_id.iter().copied());
199    undo_move_id.extend(left.undo_move_id.iter().copied());
200
201    let scope = if left.scope == right.scope {
202        left.scope
203    } else {
204        MoveTabuScope::new(left.scope.descriptor_index, prefix)
205    };
206
207    MoveTabuSignature::new(scope, move_id, undo_move_id)
208        .with_entity_tokens(entity_tokens)
209        .with_destination_value_tokens(destination_value_tokens)
210}
solverforge_solver/heuristic/move/metadata.rs

solverforge_solver/heuristic/move/
metadata.rs
