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