summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--morphology/src/set.rs29
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);
}
}
}