PermutationChromosome.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-1.5.0).
003  * Copyright (c) 2007-2013 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 org.jenetics.EnumGene.Gene;
023 import static org.jenetics.util.factories.Int;
024 import static org.jenetics.util.functions.StringToInteger;
025 import static org.jenetics.util.object.hashCodeOf;
026 
027 import java.io.IOException;
028 import java.io.ObjectInputStream;
029 import java.io.ObjectOutputStream;
030 import java.util.Arrays;
031 
032 import javolution.xml.XMLFormat;
033 import javolution.xml.XMLSerializable;
034 import javolution.xml.stream.XMLStreamException;
035 
036 import org.jenetics.internal.util.cast;
037 
038 import org.jenetics.util.Array;
039 import org.jenetics.util.Factory;
040 import org.jenetics.util.Function;
041 import org.jenetics.util.ISeq;
042 import org.jenetics.util.bit;
043 
044 
045 /**
046  * The mutable methods of the {@link AbstractChromosome} has been overridden so
047  * that no invalid permutation will be created.
048  *
049  @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
050  @since 1.0
051  @version 1.5 &mdash; <em>$Date: 2013-12-02 $</em>
052  */
053 public final class PermutationChromosome<T>
054     extends AbstractChromosome<EnumGene<T>>
055     implements XMLSerializable
056 {
057     private static final long serialVersionUID = 1L;
058 
059     private ISeq<T> _validAlleles;
060 
061     PermutationChromosome(final int length, final ISeq<? extends EnumGene<T>> genes) {
062         super(genes);
063         _validAlleles = genes.get(0).getValidAlleles();
064         _valid = true;
065     }
066 
067     /**
068      * Create a new, random chromosome with the given valid alleles.
069      *
070      @param validAlleles the valid alleles used for this permutation arrays.
071      */
072     public PermutationChromosome(final ISeq<? extends T> validAlleles) {
073         super(
074             new Array<EnumGene<T>>(
075                 validAlleles.length()
076             ).fill(Gene(validAlleles)).shuffle().toISeq()
077         );
078         _validAlleles = cast.apply(validAlleles);
079     }
080 
081     public ISeq<T> getValidAlleles() {
082         return _validAlleles;
083     }
084 
085     /**
086      * Check if this chromosome represents still a valid permutation.
087      */
088     @Override
089     public boolean isValid() {
090         if (_valid == null) {
091             byte[] check = new byte[length()/1];
092             Arrays.fill(check, (byte)0);
093 
094             boolean valid = super.isValid();
095             for (int i = 0; i < length() && valid; ++i) {
096                 final int value = _genes.get(i).getAlleleIndex();
097                 if (value >= && value < length()) {
098                     if (bit.get(check, value)) {
099                         valid = false;
100                     else {
101                         bit.set(check, value, true);
102                     }
103                 else {
104                     valid = false;
105                 }
106             }
107 
108             _valid = valid;
109         }
110 
111         return _valid;
112     }
113 
114     /**
115      * Return a more specific view of this chromosome factory.
116      *
117      @return a more specific view of this chromosome factory.
118      *
119      @deprecated No longer needed after adding new factory methods to the
120      *             {@link Array} class.
121      */
122     @Deprecated
123     @SuppressWarnings("unchecked")
124     public Factory<PermutationChromosome<T>> asFactory() {
125         return (Factory<PermutationChromosome<T>>)(Object)this;
126     }
127 
128     /**
129      * Create a new, <em>random</em> chromosome.
130      */
131     @Override
132     public PermutationChromosome<T> newInstance() {
133         return new PermutationChromosome<>(_validAlleles);
134     }
135 
136     @Override
137     public PermutationChromosome<T> newInstance(final ISeq<EnumGene<T>> genes) {
138         return new PermutationChromosome<>(genes.length(), genes);
139     }
140 
141     @Override
142     public int hashCode() {
143         return hashCodeOf(getClass())
144                 .and(super.hashCode())
145                 .value();
146     }
147 
148     @Override
149     public boolean equals(final Object obj) {
150         if (obj == this) {
151             return true;
152         }
153         if (obj == null || getClass() != obj.getClass()) {
154             return false;
155         }
156         return super.equals(obj);
157     }
158 
159     @Override
160     public String toString() {
161         final StringBuilder out = new StringBuilder();
162         out.append(_genes.get(0).getAllele());
163         for (int i = 1; i < length(); ++i) {
164             out.append("|").append(_genes.get(i).getAllele());
165         }
166         return out.toString();
167     }
168 
169     /**
170      * Create a new PermutationChromosome from the given genes.
171      *
172      @param genes the genes of this chromosome.
173      @return a new PermutationChromosome from the given genes.
174      */
175     public static <T> PermutationChromosome<T> valueOf(
176         final ISeq<EnumGene<T>> genes
177     ) {
178         return new PermutationChromosome<>(genes.length(), genes);
179     }
180 
181     /**
182      * Create a integer permutation chromosome with the given length.
183      *
184      @param length the chromosome length.
185      @return a integer permutation chromosome with the given length.
186      */
187     public static PermutationChromosome<Integer> ofInteger(final int length) {
188         final ISeq<Integer> alleles = new Array<Integer>(length).fill(Int()).toISeq();
189         return new PermutationChromosome<>(alleles);
190     }
191 
192     /* *************************************************************************
193      *  XML object serialization
194      * ************************************************************************/
195 
196     @SuppressWarnings("rawtypes")
197     static final XMLFormat<PermutationChromosome>
198     XML = new XMLFormat<PermutationChromosome>(PermutationChromosome.class) {
199 
200         private static final String LENGTH = "length";
201         private static final String ALLELE_INDEXES = "allele-indexes";
202 
203         @SuppressWarnings("unchecked")
204         @Override
205         public PermutationChromosome newInstance(
206             final Class<PermutationChromosome> cls, final InputElement xml
207         throws XMLStreamException
208         {
209             final int length = xml.getAttribute(LENGTH, 0);
210             final Array<Object> alleles = new Array<>(length);
211             for (int i = 0; i < length; ++i) {
212                 alleles.set(i, xml.getNext());
213             }
214 
215             final ISeq<Object> ialleles = alleles.toISeq();
216 
217             final Array<Integer> indexes = Array.valueOf(
218                 xml.get(ALLELE_INDEXES, String.class
219             ).split(",")).map(StringToInteger);
220 
221             final Array<Object> genes = new Array<>(length);
222             for (int i = 0; i < length; ++i) {
223                 genes.set(i, EnumGene.valueOf(ialleles, indexes.get(i)));
224             }
225 
226             return new PermutationChromosome(genes.length(), genes.toISeq());
227         }
228 
229         @Override
230         public void write(final PermutationChromosome chromosome, final OutputElement xml)
231             throws XMLStreamException
232         {
233             xml.setAttribute(LENGTH, chromosome.length());
234             for (Object allele : chromosome.getValidAlleles()) {
235                 xml.add(allele);
236             }
237 
238             final PermutationChromosome<?> pc = chromosome;
239             final String indexes = pc.toSeq().map(new Function<Object, Integer>() {
240                 @Override public Integer apply(final Object value) {
241                     return ((EnumGene<?>)value).getAlleleIndex();
242                 }
243             }).toString(",");
244             xml.add(indexes, ALLELE_INDEXES);
245         }
246         @Override
247         public void read(
248             final InputElement element, final PermutationChromosome chromosome
249         )
250             throws XMLStreamException
251         {
252         }
253     };
254 
255     /* *************************************************************************
256      *  Java object serialization
257      * ************************************************************************/
258 
259     private void writeObject(final ObjectOutputStream out)
260         throws IOException
261     {
262         out.defaultWriteObject();
263 
264         out.writeObject(_validAlleles);
265         for (EnumGene<?> gene : _genes) {
266             out.writeInt(gene.getAlleleIndex());
267         }
268     }
269 
270     @SuppressWarnings("unchecked")
271     private void readObject(final ObjectInputStream in)
272         throws IOException, ClassNotFoundException
273     {
274         in.defaultReadObject();
275 
276         _validAlleles = (ISeq<T>)in.readObject();
277 
278         final Array<EnumGene<T>> genes = new Array<>(_validAlleles.length());
279         for (int i = 0; i < _validAlleles.length(); ++i) {
280             genes.set(i, EnumGene.valueOf(_validAlleles, in.readInt()));
281         }
282 
283         _genes = genes.toISeq();
284     }
285 
286 }
287 
288 
289