diff options
Diffstat (limited to 'morphology/src')
| -rw-r--r-- | morphology/src/set.rs | 29 |
1 files changed, 23 insertions, 6 deletions
diff --git a/morphology/src/set.rs b/morphology/src/set.rs index 5376f65..b3adbbc 100644 --- a/morphology/src/set.rs +++ b/morphology/src/set.rs @@ -10,6 +10,8 @@ use crate::value::{Value, get_minimum_derivation_path}; use std::collections::HashSet; +use std::hash::{Hash, Hasher}; +use std::collections::hash_map::DefaultHasher; /// Represents a valid set in meta-affine space. #[derive(Debug, Clone, PartialEq, Eq)] @@ -17,6 +19,24 @@ pub struct ValidSet { values: HashSet<Value>, } +impl Hash for ValidSet { + fn hash<H: Hasher>(&self, state: &mut H) { + // Hash using XOR of individual value hashes (commutative, O(n)) + // This avoids sorting while ensuring equal sets produce equal hashes + let combined_hash = self.values.iter() + .map(|v| { + let mut hasher = DefaultHasher::new(); + v.hash(&mut hasher); + hasher.finish() + }) + .fold(0u64, |acc, h| acc ^ h); + + // Hash both the XOR result and size to avoid collisions + combined_hash.hash(state); + self.values.len().hash(state); + } +} + impl ValidSet { /// Creates an empty valid set. /// @@ -261,7 +281,7 @@ pub fn generate_valid_sets(max_size: usize) -> Vec<ValidSet> { // Generate sets of increasing size for size in 2..=max_size { - let mut new_sets = Vec::new(); + let mut new_sets = HashSet::new(); // For each set of size-1 for prev_set in &sets_by_size[size - 1] { @@ -271,12 +291,9 @@ pub fn generate_valid_sets(max_size: usize) -> Vec<ValidSet> { for candidate in candidates { let new_set = prev_set.add_value_with_dependencies(candidate); - // Only keep if size matches and we haven't seen it + // Only keep if size matches (HashSet automatically deduplicates) if new_set.size() == size { - // Check if we already have this set - if !new_sets.iter().any(|s| s == &new_set) { - new_sets.push(new_set); - } + new_sets.insert(new_set); } } } |