solverforge_core/domain/supply/
inverse.rs

1//! Inverse variable supply for O(1) "who points to this value?" lookups.
2//!
3//! In chained variables, we often need to know what entity points TO a given value.
4//! Without an inverse supply, this requires scanning all entities (O(n)).
5//! The inverse supply maintains a mapping for O(1) lookups.
6
7use std::any::TypeId;
8use std::collections::HashMap;
9use std::hash::Hash;
10use std::sync::RwLock;
11
12use super::{DemandKey, Supply, SupplyDemand};
13
14/// Supply that provides O(1) lookup of the entity pointing to a value.
15///
16/// For a chained variable where `entity.previous = value`, this supply answers:
17/// "Given `value`, which `entity` has `entity.previous == value`?"
18///
19/// This is essential for efficient chain manipulation in moves.
20pub trait SingletonInverseVariableSupply<V, E>: Supply
21where
22    V: Eq + Hash + Clone + Send + Sync + 'static,
23    E: Clone + Send + Sync + 'static,
24{
25    /// Gets the entity that points to the given value, if any.
26    ///
27    /// Returns `None` if no entity currently points to this value.
28    fn get_inverse_singleton(&self, value: &V) -> Option<E>;
29
30    /// Registers that an entity now points to a value.
31    ///
32    /// Called when a variable change causes `entity.var = value`.
33    fn insert(&self, value: V, entity: E);
34
35    /// Removes the mapping for a value.
36    ///
37    /// Called when the entity that pointed to this value changes.
38    fn remove(&self, value: &V) -> Option<E>;
39
40    /// Updates the mapping: removes old value mapping, adds new.
41    fn update(&self, old_value: Option<&V>, new_value: V, entity: E) {
42        if let Some(old) = old_value {
43            self.remove(old);
44        }
45        self.insert(new_value, entity);
46    }
47
48    /// Clears all mappings.
49    fn clear(&self);
50
51    /// Returns the number of tracked mappings.
52    fn len(&self) -> usize;
53
54    /// Returns true if no mappings exist.
55    fn is_empty(&self) -> bool {
56        self.len() == 0
57    }
58}
59
60/// Hash-based implementation of inverse variable supply.
61///
62/// Uses a `HashMap` internally for O(1) average-case lookups.
63/// Thread-safe via `RwLock`.
64pub struct ExternalizedSingletonInverseVariableSupply<V, E>
65where
66    V: Eq + Hash + Clone + Send + Sync + 'static,
67    E: Clone + Send + Sync + 'static,
68{
69    /// The variable name this supply tracks.
70    variable_name: String,
71    /// Mapping from value to the entity pointing to it.
72    inverse_map: RwLock<HashMap<V, E>>,
73}
74
75impl<V, E> ExternalizedSingletonInverseVariableSupply<V, E>
76where
77    V: Eq + Hash + Clone + Send + Sync + 'static,
78    E: Clone + Send + Sync + 'static,
79{
80    /// Creates a new externalized inverse variable supply.
81    pub fn new(variable_name: impl Into<String>) -> Self {
82        Self {
83            variable_name: variable_name.into(),
84            inverse_map: RwLock::new(HashMap::new()),
85        }
86    }
87
88    /// Returns the variable name this supply tracks.
89    pub fn variable_name(&self) -> &str {
90        &self.variable_name
91    }
92}
93
94impl<V, E> Supply for ExternalizedSingletonInverseVariableSupply<V, E>
95where
96    V: Eq + Hash + Clone + Send + Sync + 'static,
97    E: Clone + Send + Sync + 'static,
98{
99    fn supply_type_id(&self) -> TypeId {
100        TypeId::of::<Self>()
101    }
102}
103
104impl<V, E> SingletonInverseVariableSupply<V, E> for ExternalizedSingletonInverseVariableSupply<V, E>
105where
106    V: Eq + Hash + Clone + Send + Sync + 'static,
107    E: Clone + Send + Sync + 'static,
108{
109    fn get_inverse_singleton(&self, value: &V) -> Option<E> {
110        self.inverse_map.read().unwrap().get(value).cloned()
111    }
112
113    fn insert(&self, value: V, entity: E) {
114        self.inverse_map.write().unwrap().insert(value, entity);
115    }
116
117    fn remove(&self, value: &V) -> Option<E> {
118        self.inverse_map.write().unwrap().remove(value)
119    }
120
121    fn clear(&self) {
122        self.inverse_map.write().unwrap().clear();
123    }
124
125    fn len(&self) -> usize {
126        self.inverse_map.read().unwrap().len()
127    }
128}
129
130impl<V, E> std::fmt::Debug for ExternalizedSingletonInverseVariableSupply<V, E>
131where
132    V: Eq + Hash + Clone + Send + Sync + 'static,
133    E: Clone + Send + Sync + 'static,
134{
135    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
136        f.debug_struct("ExternalizedSingletonInverseVariableSupply")
137            .field("variable_name", &self.variable_name)
138            .field("size", &self.len())
139            .finish()
140    }
141}
142
143/// Demand for a singleton inverse variable supply.
144pub struct SingletonInverseVariableDemand<V, E>
145where
146    V: Eq + Hash + Clone + Send + Sync + 'static,
147    E: Clone + Send + Sync + 'static,
148{
149    /// The variable name to track.
150    pub variable_name: String,
151    /// Phantom data for type parameters.
152    _phantom: std::marker::PhantomData<(V, E)>,
153}
154
155impl<V, E> SingletonInverseVariableDemand<V, E>
156where
157    V: Eq + Hash + Clone + Send + Sync + 'static,
158    E: Clone + Send + Sync + 'static,
159{
160    /// Creates a new demand for an inverse variable supply.
161    pub fn new(variable_name: impl Into<String>) -> Self {
162        Self {
163            variable_name: variable_name.into(),
164            _phantom: std::marker::PhantomData,
165        }
166    }
167}
168
169impl<V, E> SupplyDemand for SingletonInverseVariableDemand<V, E>
170where
171    V: Eq + Hash + Clone + Send + Sync + 'static,
172    E: Clone + Send + Sync + 'static,
173{
174    type Output = ExternalizedSingletonInverseVariableSupply<V, E>;
175
176    fn demand_key(&self) -> DemandKey {
177        DemandKey::new::<Self::Output>(&self.variable_name)
178    }
179
180    fn create_supply(&self) -> Self::Output {
181        ExternalizedSingletonInverseVariableSupply::new(&self.variable_name)
182    }
183}
184
185#[cfg(test)]
186mod tests {
187    use super::*;
188
189    #[test]
190    fn test_inverse_supply_insert_and_get() {
191        let supply: ExternalizedSingletonInverseVariableSupply<i32, String> =
192            ExternalizedSingletonInverseVariableSupply::new("previous");
193
194        supply.insert(1, "entity_a".to_string());
195        supply.insert(2, "entity_b".to_string());
196
197        assert_eq!(
198            supply.get_inverse_singleton(&1),
199            Some("entity_a".to_string())
200        );
201        assert_eq!(
202            supply.get_inverse_singleton(&2),
203            Some("entity_b".to_string())
204        );
205        assert_eq!(supply.get_inverse_singleton(&3), None);
206    }
207
208    #[test]
209    fn test_inverse_supply_remove() {
210        let supply: ExternalizedSingletonInverseVariableSupply<i32, String> =
211            ExternalizedSingletonInverseVariableSupply::new("previous");
212
213        supply.insert(1, "entity_a".to_string());
214        assert_eq!(supply.len(), 1);
215
216        let removed = supply.remove(&1);
217        assert_eq!(removed, Some("entity_a".to_string()));
218        assert_eq!(supply.len(), 0);
219        assert_eq!(supply.get_inverse_singleton(&1), None);
220    }
221
222    #[test]
223    fn test_inverse_supply_update() {
224        let supply: ExternalizedSingletonInverseVariableSupply<i32, String> =
225            ExternalizedSingletonInverseVariableSupply::new("previous");
226
227        supply.insert(1, "entity_a".to_string());
228        supply.update(Some(&1), 2, "entity_a".to_string());
229
230        assert_eq!(supply.get_inverse_singleton(&1), None);
231        assert_eq!(
232            supply.get_inverse_singleton(&2),
233            Some("entity_a".to_string())
234        );
235    }
236
237    #[test]
238    fn test_inverse_supply_clear() {
239        let supply: ExternalizedSingletonInverseVariableSupply<i32, String> =
240            ExternalizedSingletonInverseVariableSupply::new("previous");
241
242        supply.insert(1, "a".to_string());
243        supply.insert(2, "b".to_string());
244        supply.insert(3, "c".to_string());
245
246        assert_eq!(supply.len(), 3);
247
248        supply.clear();
249
250        assert!(supply.is_empty());
251    }
252
253    #[test]
254    fn test_inverse_supply_demand() {
255        let mut manager = super::super::SupplyManager::new();
256        let demand: SingletonInverseVariableDemand<i32, String> =
257            SingletonInverseVariableDemand::new("previous");
258
259        let supply = manager.demand(&demand);
260        supply.insert(42, "test_entity".to_string());
261
262        // Get the same supply again
263        let supply2 = manager.demand(&demand);
264        assert_eq!(
265            supply2.get_inverse_singleton(&42),
266            Some("test_entity".to_string())
267        );
268    }
269
270    #[test]
271    fn test_inverse_supply_thread_safety() {
272        use std::sync::Arc;
273        use std::thread;
274
275        let supply: Arc<ExternalizedSingletonInverseVariableSupply<i32, i32>> =
276            Arc::new(ExternalizedSingletonInverseVariableSupply::new("var"));
277
278        let supply_clone = supply.clone();
279        let handle = thread::spawn(move || {
280            for i in 0..100 {
281                supply_clone.insert(i, i * 10);
282            }
283        });
284
285        handle.join().unwrap();
286
287        assert_eq!(supply.len(), 100);
288        assert_eq!(supply.get_inverse_singleton(&50), Some(500));
289    }
290}
solverforge_core/domain/supply/inverse.rs

solverforge_core/domain/supply/
inverse.rs
