PermutationChromosome.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-2.0.2).
003  * Copyright (c) 2007-2014 Franz Wilhelmstötter
004  *
005  * Licensed under the Apache License, Version 2.0 (the "License");
006  * you may not use this file except in compliance with the License.
007  * You may obtain a copy of the License at
008  *
009  *      http://www.apache.org/licenses/LICENSE-2.0
010  *
011  * Unless required by applicable law or agreed to in writing, software
012  * distributed under the License is distributed on an "AS IS" BASIS,
013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014  * See the License for the specific language governing permissions and
015  * limitations under the License.
016  *
017  * Author:
018  *    Franz Wilhelmstötter (franz.wilhelmstoetter@gmx.at)
019  */
020 package org.jenetics;
021 
022 import static java.lang.String.format;
023 import static org.jenetics.EnumGene.Gene;
024 
025 import java.io.IOException;
026 import java.io.ObjectInputStream;
027 import java.io.ObjectOutputStream;
028 import java.io.Serializable;
029 import java.util.Arrays;
030 import java.util.List;
031 
032 import javax.xml.bind.annotation.XmlAccessType;
033 import javax.xml.bind.annotation.XmlAccessorType;
034 import javax.xml.bind.annotation.XmlAttribute;
035 import javax.xml.bind.annotation.XmlElement;
036 import javax.xml.bind.annotation.XmlElementWrapper;
037 import javax.xml.bind.annotation.XmlList;
038 import javax.xml.bind.annotation.XmlRootElement;
039 import javax.xml.bind.annotation.XmlType;
040 import javax.xml.bind.annotation.adapters.XmlAdapter;
041 import javax.xml.bind.annotation.adapters.XmlJavaTypeAdapter;
042 
043 import org.jenetics.internal.util.HashBuilder;
044 import org.jenetics.internal.util.cast;
045 import org.jenetics.internal.util.jaxb;
046 
047 import org.jenetics.util.Array;
048 import org.jenetics.util.Factory;
049 import org.jenetics.util.Function;
050 import org.jenetics.util.ISeq;
051 import org.jenetics.util.bit;
052 
053 
054 /**
055  * The mutable methods of the {@link AbstractChromosome} has been overridden so
056  * that no invalid permutation will be created.
057  *
058  @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
059  @since 1.0
060  @version 2.0 &mdash; <em>$Date: 2014-04-13 $</em>
061  */
062 @XmlJavaTypeAdapter(PermutationChromosome.Model.Adapter.class)
063 public final class PermutationChromosome<T>
064     extends AbstractChromosome<EnumGene<T>>
065     implements Serializable
066 {
067     private static final long serialVersionUID = 2L;
068 
069     private ISeq<T> _validAlleles;
070 
071     public PermutationChromosome(final ISeq<EnumGene<T>> genes) {
072         super(genes);
073         _validAlleles = genes.get(0).getValidAlleles();
074         _valid = true;
075     }
076 
077     public ISeq<T> getValidAlleles() {
078         return _validAlleles;
079     }
080 
081     /**
082      * Check if this chromosome represents still a valid permutation.
083      */
084     @Override
085     public boolean isValid() {
086         if (_valid == null) {
087             byte[] check = new byte[length()/1];
088             Arrays.fill(check, (byte)0);
089 
090             boolean valid = super.isValid();
091             for (int i = 0; i < length() && valid; ++i) {
092                 final int value = _genes.get(i).getAlleleIndex();
093                 if (value >= && value < length()) {
094                     if (bit.get(check, value)) {
095                         valid = false;
096                     else {
097                         bit.set(check, value, true);
098                     }
099                 else {
100                     valid = false;
101                 }
102             }
103 
104             _valid = valid;
105         }
106 
107         return _valid;
108     }
109 
110     /**
111      * Create a new, <em>random</em> chromosome.
112      */
113     @Override
114     public PermutationChromosome<T> newInstance() {
115         return of(_validAlleles);
116     }
117 
118     @Override
119     public PermutationChromosome<T> newInstance(final ISeq<EnumGene<T>> genes) {
120         return new PermutationChromosome<>(genes);
121     }
122 
123     @Override
124     public int hashCode() {
125         return HashBuilder.of(getClass())
126                 .and(super.hashCode())
127                 .value();
128     }
129 
130     @Override
131     public boolean equals(final Object obj) {
132         if (obj == this) {
133             return true;
134         }
135         if (obj == null || getClass() != obj.getClass()) {
136             return false;
137         }
138         return super.equals(obj);
139     }
140 
141     @Override
142     public String toString() {
143         final StringBuilder out = new StringBuilder();
144         out.append(_genes.get(0).getAllele());
145         for (int i = 1; i < length(); ++i) {
146             out.append("|").append(_genes.get(i).getAllele());
147         }
148         return out.toString();
149     }
150 
151     /**
152      * Create a new, random chromosome with the given valid alleles.
153      *
154      @param <T> the gene type of the chromosome
155      @param alleles the valid alleles used for this permutation arrays.
156      @return a new chromosome with the given alleles
157      */
158     public static <T> PermutationChromosome<T> of(final ISeq<? extends T> alleles) {
159         final PermutationChromosome<T> chromosome = new PermutationChromosome<>(
160             new Array<EnumGene<T>>(alleles.length())
161                     .fill(Gene(alleles))
162                     .shuffle()
163                     .toISeq()
164         );
165         chromosome._validAlleles = cast.apply(alleles);
166 
167         return chromosome;
168     }
169 
170     /**
171      * Create a new, random chromosome with the given valid alleles.
172      *
173      @since 2.0
174      @param <T> the gene type of the chromosome
175      @param alleles the valid alleles used for this permutation arrays.
176      @return a new chromosome with the given alleles
177      */
178     @SafeVarargs
179     public static <T> PermutationChromosome<T> of(final T... alleles) {
180         return of(Array.of(alleles).toISeq());
181     }
182 
183     /**
184      * Create a integer permutation chromosome with the given length.
185      *
186      @param length the chromosome length.
187      @return a integer permutation chromosome with the given length.
188      */
189     public static PermutationChromosome<Integer> ofInteger(final int length) {
190         return ofInteger(0, length);
191     }
192 
193     /**
194      * Create a integer permutation chromosome with the given length.
195      *
196      @since 2.0
197      @param start the start of the integer range (inclusively) of the returned
198      *        chromosome.
199      @param end the end of the integer range (exclusively) of the returned
200      *        chromosome.
201      @return a integer permutation chromosome with the given integer range
202      *         values.
203      @throws java.lang.IllegalArgumentException if {@code end <= start}
204      */
205     public static PermutationChromosome<Integer>
206     ofInteger(final int start, final int end) {
207         if (end <= start) {
208             throw new IllegalArgumentException(format(
209                 "end <= start: %d <= %d", end, start
210             ));
211         }
212         return of(new Array<Integer>(end - start).fill(Int(start, 1)).toISeq());
213     }
214 
215     private static Factory<Integer> Int(final int start, final int step) {
216         return new Factory<Integer>() {
217             private int _value = start;
218 
219             @Override
220             public Integer newInstance() {
221                 return next();
222             }
223 
224             private int next() {
225                 final int next = _value;
226                 _value += step;
227                 return next;
228             }
229         };
230     }
231 
232     /* *************************************************************************
233      *  Java object serialization
234      * ************************************************************************/
235 
236     private void writeObject(final ObjectOutputStream out)
237         throws IOException
238     {
239         out.defaultWriteObject();
240 
241         out.writeObject(_validAlleles);
242         for (EnumGene<?> gene : _genes) {
243             out.writeInt(gene.getAlleleIndex());
244         }
245     }
246 
247     @SuppressWarnings("unchecked")
248     private void readObject(final ObjectInputStream in)
249         throws IOException, ClassNotFoundException
250     {
251         in.defaultReadObject();
252 
253         _validAlleles = (ISeq<T>)in.readObject();
254 
255         final Array<EnumGene<T>> genes = new Array<>(_validAlleles.length());
256         for (int i = 0; i < _validAlleles.length(); ++i) {
257             genes.set(i, new EnumGene<>(in.readInt(), _validAlleles));
258         }
259 
260         _genes = genes.toISeq();
261     }
262 
263     /* *************************************************************************
264      *  JAXB object serialization
265      * ************************************************************************/
266 
267     @XmlRootElement(name = "permutation-chromosome")
268     @XmlType(name = "org.jenetics.PermutationChromosome")
269     @XmlAccessorType(XmlAccessType.FIELD)
270     @SuppressWarnings({"unchecked""rawtypes"})
271     static final class Model {
272 
273         @XmlAttribute
274         public int length;
275 
276         @XmlElementWrapper(name = "valid-alleles")
277         @XmlElement(name = "allele")
278         public List<Object> alleles;
279 
280         @XmlList
281         @XmlElement(name = "order")
282         public List<Integer> order;
283 
284         public static final class Adapter
285             extends XmlAdapter<Model, PermutationChromosome>
286         {
287             @Override
288             public Model marshal(final PermutationChromosome pc)
289                 throws Exception
290             {
291                 final Model model = new Model();
292                 model.length = pc.length();
293                 model.alleles = pc.getValidAlleles()
294                     .map(jaxb.Marshaller(pc.getValidAlleles().get(0)))
295                     .asList();
296                 model.order = pc.toSeq().map(AlleleIndex).asList();
297 
298                 return model;
299             }
300 
301             @Override
302             public PermutationChromosome unmarshal(final Model model)
303                 throws Exception
304             {
305                 final ISeq alleles = Array.of(model.alleles)
306                     .map(jaxb.Unmarshaller(model.alleles.get(0)))
307                     .toISeq();
308 
309                 return new PermutationChromosome(
310                     Array.of(model.order).map(Gene(alleles)).toISeq()
311                 );
312             }
313         }
314 
315         private static final Function<EnumGene<?>, Integer> AlleleIndex =
316             new Function<EnumGene<?>, Integer>() {
317                 @Override
318                 public Integer apply(final EnumGene<?> value) {
319                     return value.getAlleleIndex();
320                 }
321             };
322 
323         private static Function<Integer, EnumGene<Object>>
324         Gene(final ISeq<Object> alleles) {
325             return new Function<Integer, EnumGene<Object>>() {
326                 @Override
327                 public EnumGene<Object> apply(final Integer value) {
328                     return new EnumGene<>(value, alleles);
329                 }
330             };
331         }
332     }
333 }