radiate_core/genome/chromosomes/
permutation.rs

1use super::{Chromosome, Gene, Valid};
2#[cfg(feature = "serde")]
3use serde::{Deserialize, Serialize};
4use std::{fmt::Debug, sync::Arc};
5
6/// The [PermutationGene] is a gene that represents a permutation of a set of alleles. The gene has an index
7/// that represents the position of the allele in the alleles vector. The alleles vector is a set of unique
8/// values. The gene is valid if the index is less than the length of the alleles vector. This gene is useful
9/// for representing permutations of values, such as the order of cities in a TSP problem.
10///
11/// # Type Parameters
12/// - `A`: The type of the alleles.
13#[derive(Debug, Clone, PartialEq)]
14pub struct PermutationGene<A: PartialEq + Clone> {
15    index: usize,
16    alleles: Arc<[A]>,
17}
18
19impl<A: PartialEq + Clone> PermutationGene<A> {
20    pub fn new(index: usize, alleles: Arc<[A]>) -> Self {
21        PermutationGene { index, alleles }
22    }
23
24    pub fn index(&self) -> usize {
25        self.index
26    }
27
28    pub fn with_index(&self, index: usize) -> Self {
29        PermutationGene {
30            index,
31            alleles: Arc::clone(&self.alleles),
32        }
33    }
34}
35
36impl<A: PartialEq + Clone> Gene for PermutationGene<A> {
37    type Allele = A;
38
39    fn allele(&self) -> &Self::Allele {
40        &self.alleles[self.index]
41    }
42
43    fn allele_mut(&mut self) -> &mut Self::Allele {
44        panic!(
45            "Cannot mutate allele of PermutationGene directly. Create a new gene with `with_allele` or `with_index`."
46        );
47    }
48
49    fn new_instance(&self) -> Self {
50        PermutationGene {
51            index: self.index,
52            alleles: Arc::clone(&self.alleles),
53        }
54    }
55
56    fn with_allele(&self, allele: &Self::Allele) -> Self {
57        // Find the index of the allele in the alleles vector - this implies that `self.alleles`
58        // is a set of unique values.
59        let index = self.alleles.iter().position(|x| x == allele).unwrap();
60        PermutationGene {
61            index,
62            alleles: Arc::clone(&self.alleles),
63        }
64    }
65}
66
67impl<A: PartialEq + Clone> Valid for PermutationGene<A> {
68    fn is_valid(&self) -> bool {
69        self.index < self.alleles.len()
70    }
71}
72
73#[cfg(feature = "serde")]
74impl<A: PartialEq + Clone> Serialize for PermutationGene<A> {
75    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
76    where
77        S: serde::Serializer,
78    {
79        serializer.serialize_u64(self.index as u64)
80    }
81}
82
83#[cfg(feature = "serde")]
84impl<'de, A: PartialEq + Clone> Deserialize<'de> for PermutationGene<A> {
85    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
86    where
87        D: serde::Deserializer<'de>,
88    {
89        let index =
90            usize::try_from(u64::deserialize(deserializer)?).map_err(serde::de::Error::custom)?;
91        Ok(PermutationGene {
92            index,
93            alleles: vec![].into_boxed_slice().into(),
94        })
95    }
96}
97
98#[derive(Debug, Clone, PartialEq, Default)]
99pub struct PermutationChromosome<A: PartialEq + Clone> {
100    pub genes: Vec<PermutationGene<A>>,
101    alleles: Arc<[A]>,
102}
103
104impl<A: PartialEq + Clone> PermutationChromosome<A> {
105    pub fn new(genes: Vec<PermutationGene<A>>, alleles: Arc<[A]>) -> Self {
106        PermutationChromosome { genes, alleles }
107    }
108
109    pub fn alleles(&self) -> &Arc<[A]> {
110        &self.alleles
111    }
112}
113
114impl<A: PartialEq + Clone> Chromosome for PermutationChromosome<A> {
115    type Gene = PermutationGene<A>;
116
117    fn as_slice(&self) -> &[Self::Gene] {
118        &self.genes
119    }
120
121    fn as_mut_slice(&mut self) -> &mut [Self::Gene] {
122        &mut self.genes
123    }
124}
125
126impl<A: PartialEq + Clone> Valid for PermutationChromosome<A> {
127    fn is_valid(&self) -> bool {
128        // Check if the genes are a valid permutation of the alleles
129        let mut bit_set = vec![false; self.alleles.len()];
130        self.genes.iter().all(|gene| {
131            let index = gene.index;
132            if bit_set[index] {
133                return false;
134            }
135            bit_set[index] = true;
136            true
137        })
138    }
139}
140
141impl<A: PartialEq + Clone> From<Vec<PermutationGene<A>>> for PermutationChromosome<A> {
142    fn from(genes: Vec<PermutationGene<A>>) -> Self {
143        let alleles = genes
144            .first()
145            .map(|g| Arc::clone(&g.alleles))
146            .unwrap_or_default();
147        PermutationChromosome { genes, alleles }
148    }
149}
150
151impl<A: PartialEq + Clone> IntoIterator for PermutationChromosome<A> {
152    type Item = PermutationGene<A>;
153    type IntoIter = std::vec::IntoIter<PermutationGene<A>>;
154
155    fn into_iter(self) -> Self::IntoIter {
156        self.genes.into_iter()
157    }
158}
159
160#[cfg(feature = "serde")]
161impl<A: PartialEq + Clone + Serialize> Serialize for PermutationChromosome<A> {
162    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
163    where
164        S: serde::Serializer,
165    {
166        use serde::ser::SerializeStruct;
167        let mut state = serializer.serialize_struct("PermutationChromosome", 2)?;
168        state.serialize_field("alleles", &*self.alleles)?;
169        let gene_indices: Vec<usize> = self.genes.iter().map(|g| g.index).collect();
170        state.serialize_field("indices", &gene_indices)?;
171        state.end()
172    }
173}
174
175#[cfg(feature = "serde")]
176impl<'de, A: PartialEq + Clone + Deserialize<'de>> Deserialize<'de> for PermutationChromosome<A> {
177    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
178    where
179        D: serde::Deserializer<'de>,
180    {
181        #[derive(Deserialize)]
182        struct PermutationChromosomeData<A> {
183            alleles: Vec<A>,
184            indices: Vec<usize>,
185        }
186
187        let data = PermutationChromosomeData::<A>::deserialize(deserializer)?;
188        let alleles = data.alleles.into_boxed_slice().into();
189        let genes = data
190            .indices
191            .into_iter()
192            .map(|index| PermutationGene {
193                index,
194                alleles: Arc::clone(&alleles),
195            })
196            .collect();
197
198        Ok(PermutationChromosome { genes, alleles })
199    }
200}
201
202#[cfg(test)]
203mod test {
204    use super::*;
205    use std::sync::Arc;
206
207    #[test]
208    fn test_permutation_gene() {
209        let alleles = Arc::new([1, 2, 3, 4]);
210        let gene = PermutationGene::new(0, alleles);
211
212        assert_eq!(gene.allele(), &1);
213        assert!(gene.is_valid());
214    }
215
216    #[test]
217    fn test_permutation_chromosome() {
218        let alleles: Arc<[i32]> = Arc::new([1, 2, 3, 4]);
219        let genes = vec![
220            PermutationGene::new(0, Arc::clone(&alleles)),
221            PermutationGene::new(1, Arc::clone(&alleles)),
222            PermutationGene::new(2, Arc::clone(&alleles)),
223            PermutationGene::new(3, Arc::clone(&alleles)),
224        ];
225        let chromosome = PermutationChromosome::new(genes.clone(), Arc::clone(&alleles));
226
227        assert_eq!(chromosome.genes.len(), 4);
228        assert!(chromosome.is_valid());
229        for (i, gene) in chromosome.genes.iter().enumerate() {
230            assert_eq!(gene.index, i);
231            assert_eq!(gene.allele(), &alleles[i]);
232        }
233    }
234
235    #[cfg(feature = "serde")]
236    #[test]
237    fn test_serialize_deserialize_gene() {
238        let alleles: Arc<[char]> = Arc::new(['A', 'B', 'C']);
239        let gene = PermutationGene::new(1, Arc::clone(&alleles));
240
241        // Serialize
242        let encoded = serde_json::to_string(&gene).expect("serialize gene failed");
243
244        // Deserialize
245        let mut deserialized: PermutationGene<char> =
246            serde_json::from_str(&encoded).expect("deserialize gene failed");
247
248        // Manually reattach alleles (since PermutationGene deserialization uses dummy alleles)
249        deserialized.alleles = Arc::clone(&alleles);
250
251        assert_eq!(deserialized.index, gene.index);
252        assert_eq!(deserialized.allele(), gene.allele());
253        assert!(deserialized.is_valid());
254    }
255
256    #[cfg(feature = "serde")]
257    #[test]
258    fn test_serialize_deserialize_chromosome() {
259        let alleles: Arc<[char]> = Arc::new(['X', 'Y', 'Z']);
260        let genes = vec![
261            PermutationGene::new(2, Arc::clone(&alleles)),
262            PermutationGene::new(0, Arc::clone(&alleles)),
263            PermutationGene::new(1, Arc::clone(&alleles)),
264        ];
265        let chromosome = PermutationChromosome::new(genes, Arc::clone(&alleles));
266
267        let encoded = serde_json::to_string(&chromosome).expect("serialize chromosome failed");
268        let deserialized: PermutationChromosome<char> =
269            serde_json::from_str(&encoded).expect("deserialize chromosome failed");
270
271        assert_eq!(deserialized.alleles.as_ref(), alleles.as_ref());
272        assert_eq!(deserialized.genes.len(), chromosome.genes.len());
273        assert!(deserialized.is_valid());
274
275        for (gene, expected_gene) in deserialized.genes.iter().zip(chromosome.genes.iter()) {
276            assert_eq!(gene.index, expected_gene.index);
277            assert_eq!(gene.allele(), expected_gene.allele());
278        }
279    }
280}
radiate_core/genome/chromosomes/permutation.rs

radiate_core/genome/chromosomes/
permutation.rs
