fugue_evo/genome/
bit_string.rs

1//! Bit string genome
2//!
3//! This module provides a fixed-length bit string genome type for combinatorial optimization,
4//! with Fugue trace integration for probabilistic operations.
5
6#[cfg(feature = "ppl")]
7use fugue::{addr, ChoiceValue, Trace};
8use rand::Rng;
9use serde::{Deserialize, Serialize};
10
11use crate::error::GenomeError;
12use crate::genome::bounds::MultiBounds;
13use crate::genome::traits::{BinaryGenome, EvolutionaryGenome};
14
15/// Fixed-length bit string genome
16///
17/// This genome type represents binary optimization problems where
18/// solutions are vectors of boolean values.
19#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
20pub struct BitString {
21    /// The bits of this genome
22    bits: Vec<bool>,
23}
24
25impl BitString {
26    /// Create a new bit string with the given bits
27    pub fn new(bits: Vec<bool>) -> Self {
28        Self { bits }
29    }
30
31    /// Create an all-zeros bit string of the given length
32    pub fn zeros(length: usize) -> Self {
33        Self {
34            bits: vec![false; length],
35        }
36    }
37
38    /// Create an all-ones bit string of the given length
39    pub fn ones(length: usize) -> Self {
40        Self {
41            bits: vec![true; length],
42        }
43    }
44
45    /// Generate a random bit string of an explicit length.
46    ///
47    /// This is the honest constructor for random generation: unlike
48    /// [`EvolutionaryGenome::generate`],
49    /// which overloads `MultiBounds` and only reads its dimension count, this
50    /// takes the number of bits directly.
51    pub fn generate_with_len<R: Rng>(rng: &mut R, len: usize) -> Self {
52        Self {
53            bits: (0..len).map(|_| rng.gen()).collect(),
54        }
55    }
56
57    /// Create a bit string from a u64 with the given length
58    pub fn from_u64(value: u64, length: usize) -> Self {
59        assert!(length <= 64, "Length must be <= 64 for u64 conversion");
60        let bits = (0..length).map(|i| (value >> i) & 1 == 1).collect();
61        Self { bits }
62    }
63
64    /// Convert to a u64 (only valid for length <= 64)
65    pub fn to_u64(&self) -> Option<u64> {
66        if self.bits.len() > 64 {
67            return None;
68        }
69        let mut value = 0u64;
70        for (i, &bit) in self.bits.iter().enumerate() {
71            if bit {
72                value |= 1 << i;
73            }
74        }
75        Some(value)
76    }
77
78    /// Get the length of the bit string
79    pub fn len(&self) -> usize {
80        self.bits.len()
81    }
82
83    /// Check if the bit string is empty
84    pub fn is_empty(&self) -> bool {
85        self.bits.is_empty()
86    }
87
88    /// Get a specific bit
89    pub fn get(&self, index: usize) -> Option<bool> {
90        self.bits.get(index).copied()
91    }
92
93    /// Set a specific bit
94    pub fn set(&mut self, index: usize, value: bool) {
95        if let Some(bit) = self.bits.get_mut(index) {
96            *bit = value;
97        }
98    }
99
100    /// Flip a specific bit
101    pub fn flip(&mut self, index: usize) {
102        if let Some(bit) = self.bits.get_mut(index) {
103            *bit = !*bit;
104        }
105    }
106
107    /// Flip all bits
108    pub fn flip_all(&mut self) {
109        for bit in &mut self.bits {
110            *bit = !*bit;
111        }
112    }
113
114    /// Get the complement (all bits flipped)
115    pub fn complement(&self) -> Self {
116        Self {
117            bits: self.bits.iter().map(|b| !b).collect(),
118        }
119    }
120
121    /// Hamming distance to another bit string.
122    ///
123    /// # Panics
124    /// Panics if the two bit strings have different lengths (an invariant
125    /// violation). Use [`try_hamming_distance`](Self::try_hamming_distance) for
126    /// a fallible variant.
127    pub fn hamming_distance(&self, other: &Self) -> usize {
128        self.try_hamming_distance(other)
129            .unwrap_or_else(|e| panic!("BitString::hamming_distance: {e}"))
130    }
131
132    /// Fallible Hamming distance: returns `Err(GenomeError::DimensionMismatch)`
133    /// when the two bit strings differ in length instead of silently truncating
134    /// to the shorter one.
135    pub fn try_hamming_distance(&self, other: &Self) -> Result<usize, GenomeError> {
136        if self.bits.len() != other.bits.len() {
137            return Err(GenomeError::DimensionMismatch {
138                expected: self.bits.len(),
139                actual: other.bits.len(),
140            });
141        }
142        Ok(self
143            .bits
144            .iter()
145            .zip(other.bits.iter())
146            .filter(|(a, b)| a != b)
147            .count())
148    }
149
150    /// Bitwise AND with another bit string
151    pub fn and(&self, other: &Self) -> Result<Self, GenomeError> {
152        if self.bits.len() != other.bits.len() {
153            return Err(GenomeError::DimensionMismatch {
154                expected: self.bits.len(),
155                actual: other.bits.len(),
156            });
157        }
158        Ok(Self {
159            bits: self
160                .bits
161                .iter()
162                .zip(other.bits.iter())
163                .map(|(a, b)| *a && *b)
164                .collect(),
165        })
166    }
167
168    /// Bitwise OR with another bit string
169    pub fn or(&self, other: &Self) -> Result<Self, GenomeError> {
170        if self.bits.len() != other.bits.len() {
171            return Err(GenomeError::DimensionMismatch {
172                expected: self.bits.len(),
173                actual: other.bits.len(),
174            });
175        }
176        Ok(Self {
177            bits: self
178                .bits
179                .iter()
180                .zip(other.bits.iter())
181                .map(|(a, b)| *a || *b)
182                .collect(),
183        })
184    }
185
186    /// Bitwise XOR with another bit string
187    pub fn xor(&self, other: &Self) -> Result<Self, GenomeError> {
188        if self.bits.len() != other.bits.len() {
189            return Err(GenomeError::DimensionMismatch {
190                expected: self.bits.len(),
191                actual: other.bits.len(),
192            });
193        }
194        Ok(Self {
195            bits: self
196                .bits
197                .iter()
198                .zip(other.bits.iter())
199                .map(|(a, b)| *a ^ *b)
200                .collect(),
201        })
202    }
203}
204
205impl EvolutionaryGenome for BitString {
206    type Allele = bool;
207    type Phenotype = Vec<bool>;
208
209    fn decode(&self) -> Self::Phenotype {
210        self.bits.clone()
211    }
212
213    fn dimension(&self) -> usize {
214        self.bits.len()
215    }
216
217    /// Generate a random bit string.
218    ///
219    /// Only `bounds.dimension()` is consulted — it is the number of bits — and
220    /// the per-dimension `min`/`max` values are ignored. Prefer
221    /// [`BitString::generate_with_len`] to make the length explicit.
222    fn generate<R: Rng>(rng: &mut R, bounds: &MultiBounds) -> Self {
223        Self::generate_with_len(rng, bounds.dimension())
224    }
225
226    fn as_slice(&self) -> Option<&[bool]> {
227        Some(&self.bits)
228    }
229
230    fn as_mut_slice(&mut self) -> Option<&mut [bool]> {
231        Some(&mut self.bits)
232    }
233
234    fn distance(&self, other: &Self) -> f64 {
235        self.try_distance(other).unwrap_or_else(|e| {
236            panic!("BitString::distance: {e}; use try_distance for a fallible comparison")
237        })
238    }
239
240    fn try_distance(&self, other: &Self) -> Result<f64, GenomeError> {
241        self.try_hamming_distance(other).map(|d| d as f64)
242    }
243}
244
245#[cfg(feature = "ppl")]
246impl crate::genome::trace_genome::TraceGenome for BitString {
247    /// Convert BitString to Fugue trace.
248    ///
249    /// Each bit is stored at address "bit#i" where i is the index.
250    fn to_trace(&self) -> Trace {
251        let mut trace = Trace::default();
252        for (i, &bit) in self.bits.iter().enumerate() {
253            trace.insert_choice(addr!("bit", i), ChoiceValue::Bool(bit), 0.0);
254        }
255        trace
256    }
257
258    /// Reconstruct BitString from Fugue trace.
259    ///
260    /// Reads bits from addresses "bit#0", "bit#1", ... until no more are found.
261    /// A *missing* address terminates the scan (normal end of the sequence),
262    /// but an address that is *present with the wrong value type* is a corrupt
263    /// trace and yields [`GenomeError::TypeMismatch`] rather than silently
264    /// truncating.
265    fn from_trace(trace: &Trace) -> Result<Self, GenomeError> {
266        let mut bits = Vec::new();
267        let mut i = 0;
268        loop {
269            match trace.choices.get(&addr!("bit", i)) {
270                None => break,
271                Some(choice) => match choice.value.as_bool() {
272                    Some(val) => {
273                        bits.push(val);
274                        i += 1;
275                    }
276                    None => {
277                        return Err(GenomeError::TypeMismatch {
278                            address: format!("bit#{i}"),
279                            expected: "bool".to_string(),
280                            actual: choice.value.type_name().to_string(),
281                        });
282                    }
283                },
284            }
285        }
286        if bits.is_empty() {
287            return Err(GenomeError::InvalidStructure(
288                "No bits found in trace".to_string(),
289            ));
290        }
291        Ok(Self { bits })
292    }
293
294    fn trace_prefix() -> &'static str {
295        "bit"
296    }
297}
298
299impl BinaryGenome for BitString {
300    fn bits(&self) -> &[bool] {
301        &self.bits
302    }
303
304    fn bits_mut(&mut self) -> &mut [bool] {
305        &mut self.bits
306    }
307
308    fn from_bits(bits: Vec<bool>) -> Result<Self, GenomeError> {
309        Ok(Self { bits })
310    }
311}
312
313impl std::ops::Index<usize> for BitString {
314    type Output = bool;
315
316    fn index(&self, index: usize) -> &Self::Output {
317        &self.bits[index]
318    }
319}
320
321impl From<Vec<bool>> for BitString {
322    fn from(bits: Vec<bool>) -> Self {
323        Self { bits }
324    }
325}
326
327impl From<BitString> for Vec<bool> {
328    fn from(genome: BitString) -> Self {
329        genome.bits
330    }
331}
332
333impl<const N: usize> From<[bool; N]> for BitString {
334    fn from(arr: [bool; N]) -> Self {
335        Self { bits: arr.to_vec() }
336    }
337}
338
339impl IntoIterator for BitString {
340    type Item = bool;
341    type IntoIter = std::vec::IntoIter<bool>;
342
343    fn into_iter(self) -> Self::IntoIter {
344        self.bits.into_iter()
345    }
346}
347
348impl<'a> IntoIterator for &'a BitString {
349    type Item = &'a bool;
350    type IntoIter = std::slice::Iter<'a, bool>;
351
352    fn into_iter(self) -> Self::IntoIter {
353        self.bits.iter()
354    }
355}
356
357impl std::fmt::Display for BitString {
358    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
359        for bit in &self.bits {
360            write!(f, "{}", if *bit { '1' } else { '0' })?;
361        }
362        Ok(())
363    }
364}
365
366#[cfg(test)]
367mod tests {
368    use super::*;
369    #[cfg(feature = "ppl")]
370    use fugue::addr;
371
372    #[test]
373    fn test_bit_string_new() {
374        let bs = BitString::new(vec![true, false, true]);
375        assert_eq!(bs.len(), 3);
376        assert_eq!(bs.bits(), &[true, false, true]);
377    }
378
379    #[test]
380    fn test_bit_string_zeros() {
381        let bs = BitString::zeros(5);
382        assert_eq!(bs.len(), 5);
383        assert!(bs.bits().iter().all(|&b| !b));
384        assert_eq!(bs.count_ones(), 0);
385        assert_eq!(bs.count_zeros(), 5);
386    }
387
388    #[test]
389    fn test_bit_string_ones() {
390        let bs = BitString::ones(5);
391        assert_eq!(bs.len(), 5);
392        assert!(bs.bits().iter().all(|&b| b));
393        assert_eq!(bs.count_ones(), 5);
394        assert_eq!(bs.count_zeros(), 0);
395    }
396
397    #[test]
398    fn test_bit_string_from_u64() {
399        let bs = BitString::from_u64(0b101, 4);
400        assert_eq!(bs.bits(), &[true, false, true, false]);
401    }
402
403    #[test]
404    fn test_bit_string_to_u64() {
405        let bs = BitString::new(vec![true, false, true, false]);
406        assert_eq!(bs.to_u64(), Some(0b0101));
407
408        let long_bs = BitString::zeros(100);
409        assert_eq!(long_bs.to_u64(), None);
410    }
411
412    #[test]
413    fn test_bit_string_get_set() {
414        let mut bs = BitString::zeros(3);
415        assert_eq!(bs.get(0), Some(false));
416        assert_eq!(bs.get(3), None);
417
418        bs.set(1, true);
419        assert_eq!(bs.get(1), Some(true));
420    }
421
422    #[test]
423    fn test_bit_string_flip() {
424        let mut bs = BitString::zeros(3);
425        bs.flip(1);
426        assert_eq!(bs.bits(), &[false, true, false]);
427    }
428
429    #[test]
430    fn test_bit_string_flip_all() {
431        let mut bs = BitString::new(vec![true, false, true]);
432        bs.flip_all();
433        assert_eq!(bs.bits(), &[false, true, false]);
434    }
435
436    #[test]
437    fn test_bit_string_complement() {
438        let bs = BitString::new(vec![true, false, true]);
439        let comp = bs.complement();
440        assert_eq!(comp.bits(), &[false, true, false]);
441    }
442
443    #[test]
444    fn test_bit_string_hamming_distance() {
445        let bs1 = BitString::new(vec![true, false, true, false]);
446        let bs2 = BitString::new(vec![true, true, false, false]);
447        assert_eq!(bs1.hamming_distance(&bs2), 2);
448    }
449
450    #[test]
451    fn test_bit_string_and() {
452        let bs1 = BitString::new(vec![true, true, false, false]);
453        let bs2 = BitString::new(vec![true, false, true, false]);
454        let result = bs1.and(&bs2).unwrap();
455        assert_eq!(result.bits(), &[true, false, false, false]);
456    }
457
458    #[test]
459    fn test_bit_string_or() {
460        let bs1 = BitString::new(vec![true, true, false, false]);
461        let bs2 = BitString::new(vec![true, false, true, false]);
462        let result = bs1.or(&bs2).unwrap();
463        assert_eq!(result.bits(), &[true, true, true, false]);
464    }
465
466    #[test]
467    fn test_bit_string_xor() {
468        let bs1 = BitString::new(vec![true, true, false, false]);
469        let bs2 = BitString::new(vec![true, false, true, false]);
470        let result = bs1.xor(&bs2).unwrap();
471        assert_eq!(result.bits(), &[false, true, true, false]);
472    }
473
474    #[test]
475    fn test_bit_string_dimension_mismatch() {
476        let bs1 = BitString::zeros(3);
477        let bs2 = BitString::zeros(4);
478        assert!(bs1.and(&bs2).is_err());
479        assert!(bs1.or(&bs2).is_err());
480        assert!(bs1.xor(&bs2).is_err());
481    }
482
483    #[test]
484    fn test_bit_string_generate() {
485        let mut rng = rand::thread_rng();
486        let bounds = MultiBounds::symmetric(1.0, 10);
487        let bs = BitString::generate(&mut rng, &bounds);
488        assert_eq!(bs.len(), 10);
489    }
490
491    #[test]
492    fn test_bit_string_distance() {
493        let bs1 = BitString::new(vec![true, false, true, false]);
494        let bs2 = BitString::new(vec![true, true, false, false]);
495        assert_eq!(bs1.distance(&bs2), 2.0);
496    }
497
498    #[test]
499    fn test_bit_string_display() {
500        let bs = BitString::new(vec![true, false, true, true]);
501        assert_eq!(format!("{}", bs), "1011");
502    }
503
504    #[test]
505    fn test_bit_string_indexing() {
506        let bs = BitString::new(vec![true, false, true]);
507        assert!(bs[0]);
508        assert!(!bs[1]);
509        assert!(bs[2]);
510    }
511
512    #[test]
513    fn test_bit_string_from_array() {
514        let bs: BitString = [true, false, true].into();
515        assert_eq!(bs.bits(), &[true, false, true]);
516    }
517
518    #[test]
519    fn test_bit_string_serialization() {
520        let bs = BitString::new(vec![true, false, true]);
521        let serialized = serde_json::to_string(&bs).unwrap();
522        let deserialized: BitString = serde_json::from_str(&serialized).unwrap();
523        assert_eq!(bs, deserialized);
524    }
525
526    #[test]
527    fn test_bit_string_decode() {
528        let bs = BitString::new(vec![true, false, true]);
529        let phenotype = bs.decode();
530        assert_eq!(phenotype, vec![true, false, true]);
531    }
532
533    #[test]
534    #[cfg(feature = "ppl")]
535    fn test_bit_string_to_trace() {
536        use crate::genome::trace_genome::TraceGenome;
537        let bs = BitString::new(vec![true, false, true, false]);
538        let trace = bs.to_trace();
539
540        assert_eq!(trace.get_bool(&addr!("bit", 0)), Some(true));
541        assert_eq!(trace.get_bool(&addr!("bit", 1)), Some(false));
542        assert_eq!(trace.get_bool(&addr!("bit", 2)), Some(true));
543        assert_eq!(trace.get_bool(&addr!("bit", 3)), Some(false));
544        assert_eq!(trace.get_bool(&addr!("bit", 4)), None);
545    }
546
547    #[test]
548    #[cfg(feature = "ppl")]
549    fn test_bit_string_from_trace() {
550        use crate::genome::trace_genome::TraceGenome;
551        let mut trace = Trace::default();
552        trace.insert_choice(addr!("bit", 0), ChoiceValue::Bool(true), 0.0);
553        trace.insert_choice(addr!("bit", 1), ChoiceValue::Bool(false), 0.0);
554        trace.insert_choice(addr!("bit", 2), ChoiceValue::Bool(true), 0.0);
555
556        let bs = BitString::from_trace(&trace).unwrap();
557        assert_eq!(bs.bits(), &[true, false, true]);
558    }
559
560    #[test]
561    #[cfg(feature = "ppl")]
562    fn test_bit_string_trace_roundtrip() {
563        use crate::genome::trace_genome::TraceGenome;
564        let original = BitString::new(vec![true, false, true, true, false]);
565        let trace = original.to_trace();
566        let recovered = BitString::from_trace(&trace).unwrap();
567        assert_eq!(original, recovered);
568    }
569
570    #[test]
571    #[cfg(feature = "ppl")]
572    fn test_bit_string_from_trace_empty() {
573        use crate::genome::trace_genome::TraceGenome;
574        let trace = Trace::default();
575        let result = BitString::from_trace(&trace);
576        assert!(result.is_err());
577    }
578
579    #[test]
580    fn test_bit_string_try_hamming_distance_mismatch() {
581        // regression: EV-55 — hamming_distance previously truncated to the
582        // shorter length and reported 0 despite 4 extra set bits.
583        let bs1 = BitString::new(vec![true, true]);
584        let bs2 = BitString::new(vec![true, true, true, true, true, true]);
585        assert!(matches!(
586            bs1.try_hamming_distance(&bs2),
587            Err(GenomeError::DimensionMismatch {
588                expected: 2,
589                actual: 6
590            })
591        ));
592        assert!(bs1.try_distance(&bs2).is_err());
593    }
594
595    #[test]
596    #[should_panic(expected = "Dimension mismatch")]
597    fn test_bit_string_distance_mismatch_panics() {
598        // regression: EV-55 — distance() must loudly reject a length mismatch.
599        let bs1 = BitString::new(vec![true, true]);
600        let bs2 = BitString::new(vec![true, true, true, true, true, true]);
601        let _ = bs1.distance(&bs2);
602    }
603
604    #[test]
605    #[cfg(feature = "ppl")]
606    fn test_bit_string_from_trace_type_mismatch() {
607        // regression: EV-59 — a present-but-wrong-typed choice must raise
608        // TypeMismatch rather than silently truncating the bit string.
609        use crate::genome::trace_genome::TraceGenome;
610        let mut trace = Trace::default();
611        trace.insert_choice(addr!("bit", 0), ChoiceValue::Bool(true), 0.0);
612        trace.insert_choice(addr!("bit", 1), ChoiceValue::F64(1.0), 0.0); // wrong type
613        trace.insert_choice(addr!("bit", 2), ChoiceValue::Bool(false), 0.0);
614
615        match BitString::from_trace(&trace) {
616            Err(GenomeError::TypeMismatch {
617                address,
618                expected,
619                actual,
620            }) => {
621                assert_eq!(address, "bit#1");
622                assert_eq!(expected, "bool");
623                assert_eq!(actual, "f64");
624            }
625            other => panic!("expected TypeMismatch, got {other:?}"),
626        }
627    }
628
629    #[test]
630    fn test_bit_string_generate_with_len() {
631        // EV-94: honest constructor takes an explicit length.
632        let mut rng = rand::thread_rng();
633        let bs = BitString::generate_with_len(&mut rng, 7);
634        assert_eq!(bs.len(), 7);
635    }
636}
fugue_evo/genome/bit_string.rs

fugue_evo/genome/
bit_string.rs
