Population.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.util.Objects.requireNonNull;
023 import static org.jenetics.internal.util.object.eq;
024 
025 import java.io.Serializable;
026 import java.util.ArrayList;
027 import java.util.Collection;
028 import java.util.Collections;
029 import java.util.Comparator;
030 import java.util.Iterator;
031 import java.util.List;
032 import java.util.ListIterator;
033 import java.util.RandomAccess;
034 
035 import javax.xml.bind.annotation.XmlAccessType;
036 import javax.xml.bind.annotation.XmlAccessorType;
037 import javax.xml.bind.annotation.XmlAttribute;
038 import javax.xml.bind.annotation.XmlElement;
039 import javax.xml.bind.annotation.XmlRootElement;
040 import javax.xml.bind.annotation.XmlType;
041 import javax.xml.bind.annotation.adapters.XmlAdapter;
042 import javax.xml.bind.annotation.adapters.XmlJavaTypeAdapter;
043 
044 import org.jenetics.internal.util.HashBuilder;
045 import org.jenetics.internal.util.jaxb;
046 
047 import org.jenetics.util.Array;
048 import org.jenetics.util.Copyable;
049 import org.jenetics.util.Factory;
050 import org.jenetics.util.ISeq;
051 
052 /**
053  * A population is a collection of Phenotypes.
054  *
055  <p>
056  <strong>This class is not synchronized.</strong> If multiple threads access
057  * a {@code Population} concurrently, and at least one of the threads modifies
058  * it, it <strong>must</strong> be synchronized externally.
059  *
060  @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
061  @since 1.0
062  @version 2.0 &mdash; <em>$Date: 2014-03-28 $</em>
063  */
064 @XmlJavaTypeAdapter(Population.Model.Adapter.class)
065 public class Population<G extends Gene<?, G>, C extends Comparable<? super C>>
066     implements
067         List<Phenotype<G, C>>,
068         Copyable<Population<G, C>>,
069         RandomAccess,
070         Serializable
071 {
072     private static final long serialVersionUID = 2L;
073 
074     private final List<Phenotype<G, C>> _population;
075 
076     private Population(final List<Phenotype<G, C>> population, boolean a) {
077         _population = population;
078     }
079 
080     /**
081      * Constructs a population containing the elements of the specified collection,
082      * in the order they are returned by the collection's iterator.
083      *
084      @param population the collection whose elements are to be placed into
085      *         this list.
086      @throws NullPointerException if the specified population is {@code null}.
087      */
088     public Population(final Collection<Phenotype<G, C>> population) {
089         this(new ArrayList<>(population)true);
090     }
091 
092     /**
093      * Creating a new {@code Population} with the pre-allocated population
094      * size.
095      *
096      @param size Pre-allocated population size.
097      @throws IllegalArgumentException if the specified initial capacity is
098      *         negative
099      */
100     public Population(final int size) {
101         this(new ArrayList<Phenotype<G, C>>(size + 1)true);
102     }
103 
104     /**
105      * Creating a new {@code Population}.
106      */
107     public Population() {
108         this(new ArrayList<Phenotype<G, C>>()true);
109     }
110 
111     /**
112      * Fills the population with individuals created by the given factory.
113      *
114      @param factory the {@code Phenotype} factory.
115      @param count the number of individuals to add to this population.
116      @return return this population, for command chaining.
117      */
118     public Population<G, C> fill(
119         final Factory<Phenotype<G, C>> factory,
120         final int count
121     ) {
122         for (int i = count; --i >= 0;) {
123             _population.add(factory.newInstance());
124         }
125         //lists.fill(_population, factory, count);
126         return this;
127     }
128 
129     /**
130      * Add {@code Phenotype} to the {@code Population}.
131      *
132      @param phenotype {@code Phenotype} to be add.
133      @throws NullPointerException if the given {@code phenotype} is
134      *         {@code null}.
135      */
136     @Override
137     public boolean add(final Phenotype<G, C> phenotype) {
138         requireNonNull(phenotype, "Phenotype");
139         return _population.add(phenotype);
140     }
141 
142     /**
143      * Add {@code Phenotype} to the {@code Population}.
144      *
145      @param index Index of the
146      @param phenotype {@code Phenotype} to be add.
147      @throws NullPointerException if the given {@code phenotype} is
148      *         {@code null}.
149      */
150     @Override
151     public void add(final int index, final Phenotype<G, C> phenotype) {
152         requireNonNull(phenotype, "Phenotype");
153         _population.add(index, phenotype);
154     }
155 
156     @Override
157     public boolean addAll(final Collection<? extends Phenotype<G, C>> c) {
158         return _population.addAll(c);
159     }
160 
161     @Override
162     public boolean addAll(int index, Collection<? extends Phenotype<G, C>> c) {
163         return _population.addAll(index, c);
164     }
165 
166     @Override
167     public Phenotype<G, C> get(final int index) {
168         return _population.get(index);
169     }
170 
171     @Override
172     public Phenotype<G, C> set(final int index, final Phenotype<G, C> pt) {
173         requireNonNull(pt, "Phenotype");
174         return _population.set(index, pt);
175     }
176 
177     public void remove(final Phenotype<G, C> phenotype) {
178         requireNonNull(phenotype, "Phenotype");
179         _population.remove(phenotype);
180     }
181 
182     @Override
183     public boolean remove(final Object o) {
184         return _population.remove(o);
185     }
186 
187     @Override
188     public boolean removeAll(final Collection<?> c) {
189         return _population.removeAll(c);
190     }
191 
192     @Override
193     public Phenotype<G, C> remove(final int index) {
194         return _population.remove(index);
195     }
196 
197     @Override
198     public void clear() {
199         _population.clear();
200     }
201 
202     /**
203      * Sorting the phenotypes in this population according to its fitness
204      * value in descending order.
205      */
206     public void sort() {
207         sortWith(Optimize.MAXIMUM.<C>descending());
208     }
209 
210     /**
211      * Sort this population according the order defined by the given
212      * {@code comparator}.
213      *
214      @param comparator the comparator which defines the sorting order.
215      @throws java.lang.NullPointerException if the {@code comparator} is
216      *         {@code null}.
217      */
218     public void sortWith(final Comparator<? super C> comparator) {
219         quickSort(0, size() 1, comparator);
220     }
221 
222 
223     private void quickSort(
224         final int left, final int right,
225         final Comparator<? super C> comparator
226     ) {
227         if (right > left) {
228             final int j = partition(left, right, comparator);
229             quickSort(left, j - 1, comparator);
230             quickSort(j + 1, right, comparator);
231         }
232     }
233 
234     private int partition(
235         final int left, final int right,
236         final Comparator<? super C> comparator
237     ) {
238         final C pivot = _population.get(left).getFitness();
239         int i = left;
240         int j = right + 1;
241         while (true) {
242             do {
243                 ++i;
244             while (
245                 i < right &&
246                 comparator.compare(_population.get(i).getFitness(), pivot0
247             );
248 
249             do {
250                 --j;
251             while (
252                 j > left &&
253                 comparator.compare(_population.get(j).getFitness(), pivot0
254             );
255             if (j <= i) {
256                 break;
257             }
258             swap(i, j);
259         }
260         swap(left, j);
261 
262         return j;
263     }
264 
265     private void swap(final int i, final int j) {
266         _population.set(i, _population.set(j, _population.get(i)));
267     }
268 
269     /**
270      * Reverse the order of the population.
271      */
272     public void reverse() {
273         Collections.reverse(_population);
274     }
275 
276     @Override
277     public Iterator<Phenotype<G, C>> iterator() {
278         return _population.iterator();
279     }
280 
281     @Override
282     public ListIterator<Phenotype<G, C>> listIterator() {
283         return _population.listIterator();
284     }
285 
286     @Override
287     public ListIterator<Phenotype<G, C>> listIterator(final int index) {
288         return _population.listIterator(index);
289     }
290 
291     @Override
292     public int size() {
293         return _population.size();
294     }
295 
296     @Override
297     public boolean isEmpty() {
298         return _population.isEmpty();
299     }
300 
301     @Override
302     public boolean contains(final Object o) {
303         return _population.contains(o);
304     }
305 
306     @Override
307     public boolean containsAll(final Collection<?> c) {
308         return _population.containsAll(c);
309     }
310 
311     @Override
312     public int indexOf(final Object o) {
313         return _population.indexOf(o);
314     }
315 
316     @Override
317     public int lastIndexOf(final Object o) {
318         return _population.lastIndexOf(o);
319     }
320 
321     @Override
322     public boolean retainAll(final Collection<?> c) {
323         return _population.retainAll(c);
324     }
325 
326     @Override
327     public List<Phenotype<G, C>> subList(final int fromIndex, final int toIndex) {
328         return _population.subList(fromIndex, toIndex);
329     }
330 
331     @Override
332     public Object[] toArray() {
333         return _population.toArray();
334     }
335 
336     @Override
337     public <A> A[] toArray(final A[] a) {
338         return _population.toArray(a);
339     }
340 
341     public List<Genotype<G>> getGenotypes() {
342         final List<Genotype<G>> genotypes = new ArrayList<>(_population.size());
343         for (Phenotype<G, C> phenotype : _population) {
344             genotypes.add(phenotype.getGenotype());
345         }
346         return genotypes;
347     }
348 
349     @Override
350     public Population<G, C> copy() {
351         return new Population<>(new ArrayList<>(_population)true);
352     }
353 
354     @Override
355     public int hashCode() {
356         return HashBuilder.of(getClass()).and(_population).value();
357     }
358 
359     @Override
360     public boolean equals(final Object object) {
361         if (object == this) {
362             return true;
363         }
364         if (!(object instanceof Population<?, ?>)) {
365             return false;
366         }
367 
368         final Population<?, ?> population = (Population<?, ?>)object;
369         return eq(_population, population._population);
370     }
371 
372     @Override
373     public String toString() {
374         StringBuilder out = new StringBuilder();
375 
376         for (Phenotype<?, ?> pt : this) {
377             out.append(pt).append("\n");
378         }
379 
380         return out.toString();
381     }
382 
383     /* *************************************************************************
384      *  JAXB object serialization
385      * ************************************************************************/
386 
387     @XmlRootElement(name = "population")
388     @XmlType(name = "org.jenetics.Population")
389     @XmlAccessorType(XmlAccessType.FIELD)
390     @SuppressWarnings({"unchecked""rawtypes"})
391     static final class Model {
392 
393         @XmlAttribute(name = "size", required = true)
394         public int size;
395 
396         @XmlElement(name = "phenotype", required = true)
397         public List phenotypes;
398 
399         public static final class Adapter
400             extends XmlAdapter<Model, Population>
401         {
402             @Override
403             public Model marshal(final Population pthrows Exception {
404                 final Model model = new Model();
405                 model.size = p.size();
406                 if (!p.isEmpty()) {
407                     model.phenotypes = Array.of(p)
408                         .map(jaxb.Marshaller(p.get(0)))
409                         .asList();
410                 }
411 
412                 return model;
413             }
414 
415             @Override
416             public Population unmarshal(final Model modelthrows Exception {
417                 Population population = new Population();
418                 if (model.size > 0) {
419                     final ISeq pt = Array.of(model.phenotypes)
420                         .map(jaxb.Unmarshaller(model.phenotypes.get(0)))
421                         .toISeq();
422 
423                     population = new Population(pt.asList());
424                 }
425 
426                 return population;
427             }
428         }
429 
430     }
431 }