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;
128pub(crate) const TABU_OP_LIST_PERMUTE: u64 = 0xF000_0000_0000_0005;
129pub(crate) const TABU_OP_LIST_MULTI_SWAP: u64 = 0xF000_0000_0000_0006;
130
131pub(crate) fn scoped_move_identity(
132    scope: MoveTabuScope,
133    operation_id: u64,
134    components: impl IntoIterator<Item = u64>,
135) -> MoveIdentity {
136    let mut identity = smallvec![
137        operation_id,
138        encode_usize(scope.descriptor_index),
139        hash_str(scope.variable_name),
140    ];
141    identity.extend(components);
142    identity
143}
144
145pub(crate) fn ordered_coordinate_pair(first: (u64, u64), second: (u64, u64)) -> [(u64, u64); 2] {
146    if first <= second {
147        [first, second]
148    } else {
149        [second, first]
150    }
151}
152
153pub(crate) fn append_canonical_usize_slice_pair(
154    identity: &mut MoveIdentity,
155    left: &[usize],
156    right: &[usize],
157) {
158    let (first, second) = if left <= right {
159        (left, right)
160    } else {
161        (right, left)
162    };
163    identity.push(encode_usize(first.len()));
164    identity.push(encode_usize(second.len()));
165    identity.extend(first.iter().map(|&idx| encode_usize(idx)));
166    identity.push(NONE_ID);
167    identity.extend(second.iter().map(|&idx| encode_usize(idx)));
168}
169
170fn append_unique_tokens<T>(target: &mut SmallVec<[T; 2]>, tokens: &[T])
171where
172    T: Copy + PartialEq,
173{
174    for &token in tokens {
175        if !target.contains(&token) {
176            target.push(token);
177        }
178    }
179}
180
181pub(crate) fn compose_sequential_tabu_signature(
182    prefix: &'static str,
183    left: &MoveTabuSignature,
184    right: &MoveTabuSignature,
185) -> MoveTabuSignature {
186    let mut entity_tokens = left.entity_tokens.clone();
187    append_unique_tokens(&mut entity_tokens, &right.entity_tokens);
188
189    let mut destination_value_tokens = left.destination_value_tokens.clone();
190    append_unique_tokens(
191        &mut destination_value_tokens,
192        &right.destination_value_tokens,
193    );
194
195    let mut move_id = smallvec![hash_str(prefix)];
196    move_id.extend(left.move_id.iter().copied());
197    move_id.extend(right.move_id.iter().copied());
198
199    let mut undo_move_id = smallvec![hash_str(prefix)];
200    undo_move_id.extend(right.undo_move_id.iter().copied());
201    undo_move_id.extend(left.undo_move_id.iter().copied());
202
203    let scope = if left.scope == right.scope {
204        left.scope
205    } else {
206        MoveTabuScope::new(left.scope.descriptor_index, prefix)
207    };
208
209    MoveTabuSignature::new(scope, move_id, undo_move_id)
210        .with_entity_tokens(entity_tokens)
211        .with_destination_value_tokens(destination_value_tokens)
212}
solverforge_solver/heuristic/move/metadata.rs

solverforge_solver/heuristic/move/
metadata.rs
