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
6use fugue::{addr, ChoiceValue, Trace};
7use rand::Rng;
8use serde::{Deserialize, Serialize};
9
10use crate::error::GenomeError;
11use crate::genome::bounds::MultiBounds;
12use crate::genome::traits::{BinaryGenome, EvolutionaryGenome};
13
14/// Fixed-length bit string genome
15///
16/// This genome type represents binary optimization problems where
17/// solutions are vectors of boolean values.
18#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
19pub struct BitString {
20    /// The bits of this genome
21    bits: Vec<bool>,
22}
23
24impl BitString {
25    /// Create a new bit string with the given bits
26    pub fn new(bits: Vec<bool>) -> Self {
27        Self { bits }
28    }
29
30    /// Create an all-zeros bit string of the given length
31    pub fn zeros(length: usize) -> Self {
32        Self {
33            bits: vec![false; length],
34        }
35    }
36
37    /// Create an all-ones bit string of the given length
38    pub fn ones(length: usize) -> Self {
39        Self {
40            bits: vec![true; length],
41        }
42    }
43
44    /// Create a bit string from a u64 with the given length
45    pub fn from_u64(value: u64, length: usize) -> Self {
46        assert!(length <= 64, "Length must be <= 64 for u64 conversion");
47        let bits = (0..length).map(|i| (value >> i) & 1 == 1).collect();
48        Self { bits }
49    }
50
51    /// Convert to a u64 (only valid for length <= 64)
52    pub fn to_u64(&self) -> Option<u64> {
53        if self.bits.len() > 64 {
54            return None;
55        }
56        let mut value = 0u64;
57        for (i, &bit) in self.bits.iter().enumerate() {
58            if bit {
59                value |= 1 << i;
60            }
61        }
62        Some(value)
63    }
64
65    /// Get the length of the bit string
66    pub fn len(&self) -> usize {
67        self.bits.len()
68    }
69
70    /// Check if the bit string is empty
71    pub fn is_empty(&self) -> bool {
72        self.bits.is_empty()
73    }
74
75    /// Get a specific bit
76    pub fn get(&self, index: usize) -> Option<bool> {
77        self.bits.get(index).copied()
78    }
79
80    /// Set a specific bit
81    pub fn set(&mut self, index: usize, value: bool) {
82        if let Some(bit) = self.bits.get_mut(index) {
83            *bit = value;
84        }
85    }
86
87    /// Flip a specific bit
88    pub fn flip(&mut self, index: usize) {
89        if let Some(bit) = self.bits.get_mut(index) {
90            *bit = !*bit;
91        }
92    }
93
94    /// Flip all bits
95    pub fn flip_all(&mut self) {
96        for bit in &mut self.bits {
97            *bit = !*bit;
98        }
99    }
100
101    /// Get the complement (all bits flipped)
102    pub fn complement(&self) -> Self {
103        Self {
104            bits: self.bits.iter().map(|b| !b).collect(),
105        }
106    }
107
108    /// Hamming distance to another bit string
109    pub fn hamming_distance(&self, other: &Self) -> usize {
110        self.bits
111            .iter()
112            .zip(other.bits.iter())
113            .filter(|(a, b)| a != b)
114            .count()
115    }
116
117    /// Bitwise AND with another bit string
118    pub fn and(&self, other: &Self) -> Result<Self, GenomeError> {
119        if self.bits.len() != other.bits.len() {
120            return Err(GenomeError::DimensionMismatch {
121                expected: self.bits.len(),
122                actual: other.bits.len(),
123            });
124        }
125        Ok(Self {
126            bits: self
127                .bits
128                .iter()
129                .zip(other.bits.iter())
130                .map(|(a, b)| *a && *b)
131                .collect(),
132        })
133    }
134
135    /// Bitwise OR with another bit string
136    pub fn or(&self, other: &Self) -> Result<Self, GenomeError> {
137        if self.bits.len() != other.bits.len() {
138            return Err(GenomeError::DimensionMismatch {
139                expected: self.bits.len(),
140                actual: other.bits.len(),
141            });
142        }
143        Ok(Self {
144            bits: self
145                .bits
146                .iter()
147                .zip(other.bits.iter())
148                .map(|(a, b)| *a || *b)
149                .collect(),
150        })
151    }
152
153    /// Bitwise XOR with another bit string
154    pub fn xor(&self, other: &Self) -> Result<Self, GenomeError> {
155        if self.bits.len() != other.bits.len() {
156            return Err(GenomeError::DimensionMismatch {
157                expected: self.bits.len(),
158                actual: other.bits.len(),
159            });
160        }
161        Ok(Self {
162            bits: self
163                .bits
164                .iter()
165                .zip(other.bits.iter())
166                .map(|(a, b)| *a ^ *b)
167                .collect(),
168        })
169    }
170}
171
172impl EvolutionaryGenome for BitString {
173    type Allele = bool;
174    type Phenotype = Vec<bool>;
175
176    /// Convert BitString to Fugue trace.
177    ///
178    /// Each bit is stored at address "bit#i" where i is the index.
179    fn to_trace(&self) -> Trace {
180        let mut trace = Trace::default();
181        for (i, &bit) in self.bits.iter().enumerate() {
182            trace.insert_choice(addr!("bit", i), ChoiceValue::Bool(bit), 0.0);
183        }
184        trace
185    }
186
187    /// Reconstruct BitString from Fugue trace.
188    ///
189    /// Reads bits from addresses "bit#0", "bit#1", ... until no more are found.
190    fn from_trace(trace: &Trace) -> Result<Self, GenomeError> {
191        let mut bits = Vec::new();
192        let mut i = 0;
193        while let Some(val) = trace.get_bool(&addr!("bit", i)) {
194            bits.push(val);
195            i += 1;
196        }
197        if bits.is_empty() {
198            return Err(GenomeError::InvalidStructure(
199                "No bits found in trace".to_string(),
200            ));
201        }
202        Ok(Self { bits })
203    }
204
205    fn decode(&self) -> Self::Phenotype {
206        self.bits.clone()
207    }
208
209    fn dimension(&self) -> usize {
210        self.bits.len()
211    }
212
213    fn generate<R: Rng>(rng: &mut R, bounds: &MultiBounds) -> Self {
214        let bits = (0..bounds.dimension()).map(|_| rng.gen()).collect();
215        Self { bits }
216    }
217
218    fn as_slice(&self) -> Option<&[bool]> {
219        Some(&self.bits)
220    }
221
222    fn as_mut_slice(&mut self) -> Option<&mut [bool]> {
223        Some(&mut self.bits)
224    }
225
226    fn distance(&self, other: &Self) -> f64 {
227        self.hamming_distance(other) as f64
228    }
229
230    fn trace_prefix() -> &'static str {
231        "bit"
232    }
233}
234
235impl BinaryGenome for BitString {
236    fn bits(&self) -> &[bool] {
237        &self.bits
238    }
239
240    fn bits_mut(&mut self) -> &mut [bool] {
241        &mut self.bits
242    }
243
244    fn from_bits(bits: Vec<bool>) -> Result<Self, GenomeError> {
245        Ok(Self { bits })
246    }
247}
248
249impl std::ops::Index<usize> for BitString {
250    type Output = bool;
251
252    fn index(&self, index: usize) -> &Self::Output {
253        &self.bits[index]
254    }
255}
256
257impl From<Vec<bool>> for BitString {
258    fn from(bits: Vec<bool>) -> Self {
259        Self { bits }
260    }
261}
262
263impl From<BitString> for Vec<bool> {
264    fn from(genome: BitString) -> Self {
265        genome.bits
266    }
267}
268
269impl<const N: usize> From<[bool; N]> for BitString {
270    fn from(arr: [bool; N]) -> Self {
271        Self { bits: arr.to_vec() }
272    }
273}
274
275impl IntoIterator for BitString {
276    type Item = bool;
277    type IntoIter = std::vec::IntoIter<bool>;
278
279    fn into_iter(self) -> Self::IntoIter {
280        self.bits.into_iter()
281    }
282}
283
284impl<'a> IntoIterator for &'a BitString {
285    type Item = &'a bool;
286    type IntoIter = std::slice::Iter<'a, bool>;
287
288    fn into_iter(self) -> Self::IntoIter {
289        self.bits.iter()
290    }
291}
292
293impl std::fmt::Display for BitString {
294    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
295        for bit in &self.bits {
296            write!(f, "{}", if *bit { '1' } else { '0' })?;
297        }
298        Ok(())
299    }
300}
301
302#[cfg(test)]
303mod tests {
304    use super::*;
305    use fugue::addr;
306
307    #[test]
308    fn test_bit_string_new() {
309        let bs = BitString::new(vec![true, false, true]);
310        assert_eq!(bs.len(), 3);
311        assert_eq!(bs.bits(), &[true, false, true]);
312    }
313
314    #[test]
315    fn test_bit_string_zeros() {
316        let bs = BitString::zeros(5);
317        assert_eq!(bs.len(), 5);
318        assert!(bs.bits().iter().all(|&b| !b));
319        assert_eq!(bs.count_ones(), 0);
320        assert_eq!(bs.count_zeros(), 5);
321    }
322
323    #[test]
324    fn test_bit_string_ones() {
325        let bs = BitString::ones(5);
326        assert_eq!(bs.len(), 5);
327        assert!(bs.bits().iter().all(|&b| b));
328        assert_eq!(bs.count_ones(), 5);
329        assert_eq!(bs.count_zeros(), 0);
330    }
331
332    #[test]
333    fn test_bit_string_from_u64() {
334        let bs = BitString::from_u64(0b101, 4);
335        assert_eq!(bs.bits(), &[true, false, true, false]);
336    }
337
338    #[test]
339    fn test_bit_string_to_u64() {
340        let bs = BitString::new(vec![true, false, true, false]);
341        assert_eq!(bs.to_u64(), Some(0b0101));
342
343        let long_bs = BitString::zeros(100);
344        assert_eq!(long_bs.to_u64(), None);
345    }
346
347    #[test]
348    fn test_bit_string_get_set() {
349        let mut bs = BitString::zeros(3);
350        assert_eq!(bs.get(0), Some(false));
351        assert_eq!(bs.get(3), None);
352
353        bs.set(1, true);
354        assert_eq!(bs.get(1), Some(true));
355    }
356
357    #[test]
358    fn test_bit_string_flip() {
359        let mut bs = BitString::zeros(3);
360        bs.flip(1);
361        assert_eq!(bs.bits(), &[false, true, false]);
362    }
363
364    #[test]
365    fn test_bit_string_flip_all() {
366        let mut bs = BitString::new(vec![true, false, true]);
367        bs.flip_all();
368        assert_eq!(bs.bits(), &[false, true, false]);
369    }
370
371    #[test]
372    fn test_bit_string_complement() {
373        let bs = BitString::new(vec![true, false, true]);
374        let comp = bs.complement();
375        assert_eq!(comp.bits(), &[false, true, false]);
376    }
377
378    #[test]
379    fn test_bit_string_hamming_distance() {
380        let bs1 = BitString::new(vec![true, false, true, false]);
381        let bs2 = BitString::new(vec![true, true, false, false]);
382        assert_eq!(bs1.hamming_distance(&bs2), 2);
383    }
384
385    #[test]
386    fn test_bit_string_and() {
387        let bs1 = BitString::new(vec![true, true, false, false]);
388        let bs2 = BitString::new(vec![true, false, true, false]);
389        let result = bs1.and(&bs2).unwrap();
390        assert_eq!(result.bits(), &[true, false, false, false]);
391    }
392
393    #[test]
394    fn test_bit_string_or() {
395        let bs1 = BitString::new(vec![true, true, false, false]);
396        let bs2 = BitString::new(vec![true, false, true, false]);
397        let result = bs1.or(&bs2).unwrap();
398        assert_eq!(result.bits(), &[true, true, true, false]);
399    }
400
401    #[test]
402    fn test_bit_string_xor() {
403        let bs1 = BitString::new(vec![true, true, false, false]);
404        let bs2 = BitString::new(vec![true, false, true, false]);
405        let result = bs1.xor(&bs2).unwrap();
406        assert_eq!(result.bits(), &[false, true, true, false]);
407    }
408
409    #[test]
410    fn test_bit_string_dimension_mismatch() {
411        let bs1 = BitString::zeros(3);
412        let bs2 = BitString::zeros(4);
413        assert!(bs1.and(&bs2).is_err());
414        assert!(bs1.or(&bs2).is_err());
415        assert!(bs1.xor(&bs2).is_err());
416    }
417
418    #[test]
419    fn test_bit_string_generate() {
420        let mut rng = rand::thread_rng();
421        let bounds = MultiBounds::symmetric(1.0, 10);
422        let bs = BitString::generate(&mut rng, &bounds);
423        assert_eq!(bs.len(), 10);
424    }
425
426    #[test]
427    fn test_bit_string_distance() {
428        let bs1 = BitString::new(vec![true, false, true, false]);
429        let bs2 = BitString::new(vec![true, true, false, false]);
430        assert_eq!(bs1.distance(&bs2), 2.0);
431    }
432
433    #[test]
434    fn test_bit_string_display() {
435        let bs = BitString::new(vec![true, false, true, true]);
436        assert_eq!(format!("{}", bs), "1011");
437    }
438
439    #[test]
440    fn test_bit_string_indexing() {
441        let bs = BitString::new(vec![true, false, true]);
442        assert!(bs[0]);
443        assert!(!bs[1]);
444        assert!(bs[2]);
445    }
446
447    #[test]
448    fn test_bit_string_from_array() {
449        let bs: BitString = [true, false, true].into();
450        assert_eq!(bs.bits(), &[true, false, true]);
451    }
452
453    #[test]
454    fn test_bit_string_serialization() {
455        let bs = BitString::new(vec![true, false, true]);
456        let serialized = serde_json::to_string(&bs).unwrap();
457        let deserialized: BitString = serde_json::from_str(&serialized).unwrap();
458        assert_eq!(bs, deserialized);
459    }
460
461    #[test]
462    fn test_bit_string_decode() {
463        let bs = BitString::new(vec![true, false, true]);
464        let phenotype = bs.decode();
465        assert_eq!(phenotype, vec![true, false, true]);
466    }
467
468    #[test]
469    fn test_bit_string_to_trace() {
470        let bs = BitString::new(vec![true, false, true, false]);
471        let trace = bs.to_trace();
472
473        assert_eq!(trace.get_bool(&addr!("bit", 0)), Some(true));
474        assert_eq!(trace.get_bool(&addr!("bit", 1)), Some(false));
475        assert_eq!(trace.get_bool(&addr!("bit", 2)), Some(true));
476        assert_eq!(trace.get_bool(&addr!("bit", 3)), Some(false));
477        assert_eq!(trace.get_bool(&addr!("bit", 4)), None);
478    }
479
480    #[test]
481    fn test_bit_string_from_trace() {
482        let mut trace = Trace::default();
483        trace.insert_choice(addr!("bit", 0), ChoiceValue::Bool(true), 0.0);
484        trace.insert_choice(addr!("bit", 1), ChoiceValue::Bool(false), 0.0);
485        trace.insert_choice(addr!("bit", 2), ChoiceValue::Bool(true), 0.0);
486
487        let bs = BitString::from_trace(&trace).unwrap();
488        assert_eq!(bs.bits(), &[true, false, true]);
489    }
490
491    #[test]
492    fn test_bit_string_trace_roundtrip() {
493        let original = BitString::new(vec![true, false, true, true, false]);
494        let trace = original.to_trace();
495        let recovered = BitString::from_trace(&trace).unwrap();
496        assert_eq!(original, recovered);
497    }
498
499    #[test]
500    fn test_bit_string_from_trace_empty() {
501        let trace = Trace::default();
502        let result = BitString::from_trace(&trace);
503        assert!(result.is_err());
504    }
505}
fugue_evo/genome/bit_string.rs

fugue_evo/genome/
bit_string.rs
