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

radiate_core/genome/chromosomes/
permutation.rs
