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