BitChromosome.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.Math.min;
023 import static java.lang.String.format;
024 import static java.util.Objects.requireNonNull;
025 
026 import java.io.IOException;
027 import java.io.ObjectInputStream;
028 import java.io.ObjectOutputStream;
029 import java.io.Serializable;
030 import java.math.BigInteger;
031 import java.util.BitSet;
032 import java.util.Iterator;
033 import java.util.ListIterator;
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.XmlRootElement;
039 import javax.xml.bind.annotation.XmlType;
040 import javax.xml.bind.annotation.XmlValue;
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.internalbit;
046 
047 import org.jenetics.util.ISeq;
048 import org.jenetics.util.bit;
049 
050 /**
051  * Implementation of the <i>classical</i> BitChromosome.
052  *
053  @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
054  @since 1.0
055  @version 2.0 &mdash; <em>$Date: 2014-04-02 $</em>
056  */
057 @XmlJavaTypeAdapter(BitChromosome.Model.Adapter.class)
058 public class BitChromosome extends Number
059     implements
060         Chromosome<BitGene>,
061         Comparable<BitChromosome>,
062         Serializable
063 {
064     private static final long serialVersionUID = 2L;
065 
066 
067     /**
068      * The one's probability of the randomly generated Chromosome.
069      */
070     protected double _p;
071 
072     /**
073      * The length of the chromosomes (number of bits).
074      */
075     protected int _length;
076 
077     /**
078      * The boolean array which holds the {@link BitGene}s.
079      */
080     protected byte[] _genes;
081 
082     // Wraps the genes byte array into a Seq<BitGene>.
083     private transient BitGeneArray _seq;
084 
085     // Private primary constructor.
086     private BitChromosome(final byte[] bits, final int length, final double p) {
087         _genes = bits;
088         _length = length;
089         _p = p;
090         _seq = new BitGeneArray(_genes, 0, _length);
091 
092     }
093 
094     /**
095      * Create a new bit chromosome from the given bit (byte) array.
096      *
097      @param bits the bit values of the new chromosome gene.
098      @param start the initial (bit) index of the range to be copied, inclusive
099      @param end the final (bit) index of the range to be copied, exclusive.
100      *        (This index may lie outside the array.)
101      @throws java.lang.ArrayIndexOutOfBoundsException if {@code start < 0} or
102      *         {@code start > bits.length*8}
103      @throws java.lang.IllegalArgumentException if {@code start > end}
104      @throws java.lang.NullPointerException if the {@code bits} array is
105      *         {@code null}.
106      */
107     public BitChromosome(final byte[] bits, final int start, final int end) {
108         this(
109             internalbit.copy(bits, start, end),
110             min(bits.length << 3, end- start,
111             0.0
112         );
113         _p = (double)bit.count(_genes)/(double)_length;
114     }
115 
116     /**
117      * Create a new {@code BitChromosome} from the given {@code byte} array.
118      * This is a shortcut for {@code new BitChromosome(bits, 0, bits.length*8)}.
119      *
120      @param bits the {@code byte} array.
121      */
122     public BitChromosome(final byte[] bits) {
123         this(bits, 0, bits.length << 3);
124     }
125 
126     private BitChromosome(final byte[] bits, final int length) {
127         this(
128             bits,
129             length == -? bits.length*: length,
130             (double)bit.count(bits)/
131             (double)(length == -? bits.length*: length)
132         );
133     }
134 
135     private static byte[] toByteArray(final CharSequence value) {
136         final byte[] bytes = bit.newArray(value.length());
137         for (int i = value.length(); --i >= 0;) {
138             final char c = value.charAt(i);
139             if (c == '1') {
140                 bit.set(bytes, i);
141             else if (c != '0') {
142                 throw new IllegalArgumentException(format(
143                     "Illegal character '%s' at position %d", c, i
144                 ));
145             }
146         }
147 
148         return bytes;
149     }
150 
151     private void rangeCheck(final int index) {
152         if (index < || index >= _length) {
153             throw new IndexOutOfBoundsException(
154                 "Index: " + index + ", Length: " + _length
155             );
156         }
157     }
158 
159     /**
160      * Return the one probability of this chromosome.
161      *
162      @return the one probability of this chromosome.
163      */
164     double getOneProbability() {
165         return _p;
166     }
167 
168     @Override
169     public BitGene getGene() {
170         assert (_genes != null);
171         assert (_genes.length > 0);
172         return BitGene.of(bit.get(_genes, 0));
173     }
174 
175     /**
176      * Return the value of the first gene of this chromosome.
177      *
178      @since 2.0
179      @return the first value of this chromosome.
180      */
181     public boolean get() {
182         return bit.get(_genes, 0);
183     }
184 
185     @Override
186     public BitGene getGene(final int index) {
187         rangeCheck(index);
188         assert(_genes != null);
189         return BitGene.of(bit.get(_genes, index));
190     }
191 
192     /**
193      * Return the value on the specified index.
194      *
195      @since 2.0
196      @param index the gene index
197      @return the wanted gene value
198      @throws IndexOutOfBoundsException if the index is out of range
199      *          (index &lt; 1 || index &gt;= length()).
200      */
201     public boolean get(final int index) {
202         rangeCheck(index);
203         return bit.get(_genes, index);
204     }
205 
206     @Override
207     public ISeq<BitGene> toSeq() {
208         return _seq.toISeq();
209     }
210 
211     @Override
212     public int length() {
213         return _length;
214     }
215 
216     /**
217      * Returns the number of bits set to true in this {@code BitChromosome}.
218      *
219      @return the number of bits set to true in this {@code BitChromosome}
220      */
221     public int bitCount() {
222         return bit.count(_genes);
223     }
224 
225     @Override
226     public Iterator<BitGene> iterator() {
227         return _seq.iterator();
228     }
229 
230     public ListIterator<BitGene> listIterator() {
231         return _seq.listIterator();
232     }
233 
234     /**
235      * Return the long value this BitChromosome represents.
236      *
237      @return long value this BitChromosome represents.
238      */
239     @Override
240     public int intValue() {
241         return (int)longValue();
242     }
243 
244     /**
245      * Return the long value this BitChromosome represents.
246      *
247      @return long value this BitChromosome represents.
248      */
249     @Override
250     public long longValue() {
251         return toBigInteger().longValue();
252     }
253 
254     /**
255      * Return the float value this BitChromosome represents.
256      *
257      @return float value this BitChromosome represents.
258      */
259     @Override
260     public float floatValue() {
261         return (float)longValue();
262     }
263 
264     /**
265      * Return the double value this BitChromosome represents.
266      *
267      @return double value this BitChromosome represents.
268      */
269     @Override
270     public double doubleValue() {
271         return longValue();
272     }
273 
274     @Override
275     public boolean isValid() {
276         return true;
277     }
278 
279     /**
280      * Return the {@code BigInteger} value this {@code BitChromosome} represents.
281      *
282      @return {@code BigInteger} value this {@code BitChromosome} represents.
283      */
284     public BigInteger toBigInteger() {
285         return new BigInteger(_genes);
286     }
287 
288     /**
289      * Returns the two's-complement binary representation of this
290      * large integer. The output array is in <i>big-endian</i>
291      * byte-order: the most significant byte is at the offset position.
292      *
293      <p>Note: This representation is consistent with {@code java.lang.BigInteger
294      *          } byte array representation and can be used for conversion
295      *          between the two classes.</p>
296      *
297      @param bytes the bytes to hold the binary representation
298      *           (two's-complement) of this large integer.
299      @return the number of bytes written.
300      @throws IndexOutOfBoundsException
301      *         if {@code bytes.length < (int)Math.ceil(length()/8.0)}
302      @throws NullPointerException it the give array is {@code null}.
303      */
304     public int toByteArray(final byte[] bytes) {
305         if (bytes.length < _genes.length) {
306             throw new IndexOutOfBoundsException();
307         }
308 
309         System.arraycopy(_genes, 0, bytes, 0, _genes.length);
310 
311         return _genes.length;
312     }
313 
314     /**
315      @return a byte array which represents this {@code BitChromosome}. The
316      *         length of the array is {@code (int)Math.ceil(length()/8.0)}.
317      *
318      @see #toByteArray(byte[])
319      */
320     public byte[] toByteArray() {
321         final byte[] data = new byte[_genes.length];
322         toByteArray(data);
323         return data;
324     }
325 
326     /**
327      * Return the corresponding BitSet of this BitChromosome.
328      *
329      @return The corresponding BitSet of this BitChromosome.
330      */
331     public BitSet toBitSet() {
332         final BitSet set = new BitSet(length());
333         for (int i = 0, n = length(); i < n; ++i) {
334             set.set(i, getGene(i).getBit());
335         }
336         return set;
337     }
338 
339     @Override
340     public BitChromosome newInstance(final ISeq<BitGene> genes) {
341         requireNonNull(genes, "Genes");
342 
343         final BitChromosome chromosome = new BitChromosome(
344             bit.newArray(genes.length()), genes.length()
345         );
346         int ones = 0;
347 
348         if (genes instanceof BitGeneArray.BitGeneISeq) {
349             final BitGeneArray.BitGeneISeq iseq = (BitGeneArray.BitGeneISeq)genes;
350             iseq.copyTo(chromosome._genes);
351             ones = bit.count(chromosome._genes);
352         else {
353             for (int i = genes.length(); --i >= 0;) {
354                 if (genes.get(i).booleanValue()) {
355                     bit.set(chromosome._genes, i);
356                     ++ones;
357                 }
358             }
359         }
360 
361         chromosome._p = (double)ones/(double)genes.length();
362         return chromosome;
363     }
364 
365     @Override
366     public BitChromosome newInstance() {
367         return of(_length, _p);
368     }
369 
370     /**
371      * Return the BitChromosome as String. A TRUE is represented by a 1 and
372      * a FALSE by a 0. The returned string can be used to create a new
373      * chromosome with the {@link #of(CharSequence)} constructor.
374      *
375      @return String representation (containing only '1' and '0') of the
376      *         BitChromosome.
377      */
378     public String toCanonicalString() {
379         final StringBuilder out = new StringBuilder(length());
380         for (int i = 0; i < _length; ++i) {
381             out.append(bit.get(_genes, i'1' '0');
382         }
383         return out.toString();
384     }
385 
386     @Override
387     public int compareTo(final BitChromosome that) {
388         return toBigInteger().compareTo(that.toBigInteger());
389     }
390 
391     /**
392      * Invert the ones and zeros of this bit chromosome.
393      *
394      @return a new BitChromosome with inverted ones and zeros.
395      */
396     public BitChromosome invert() {
397         final byte[] data = _genes.clone();
398         bit.invert(data);
399         return new BitChromosome(data, _length, 1.0 - _p);
400     }
401 
402     /**
403      * Construct a new BitChromosome with the given _length.
404      *
405      @param length Length of the BitChromosome, number of bits.
406      @param p Probability of the TRUEs in the BitChromosome.
407      @return a new {@code BitChromosome} with the given parameter
408      @throws NegativeArraySizeException if the {@code length} is smaller
409      *         than one.
410      @throws IllegalArgumentException if {@code p} is not a valid probability.
411      */
412     public static BitChromosome of(final int length, final double p) {
413         return new BitChromosome(bit.newArray(length, p), length, p);
414     }
415 
416     /**
417      * Constructing a new BitChromosome with the given _length. The TRUEs and
418      * FALSE in the {@code Chromosome} are equally distributed.
419      *
420      @param length Length of the BitChromosome.
421      @return a new {@code BitChromosome} with the given parameter
422      @throws NegativeArraySizeException if the {@code _length} is smaller
423      *         than one.
424      */
425     public static BitChromosome of(final int length) {
426         return new BitChromosome(bit.newArray(length, 0.5), length, 0.5);
427     }
428 
429     /**
430      @param length length of the BitChromosome.
431      @param bits the bit-set which initializes the chromosome
432      @return a new {@code BitChromosome} with the given parameter
433      @throws NegativeArraySizeException if the {@code length} is smaller
434      *         than one.
435      @throws NullPointerException if the {@code bitSet} is
436      *         {@code null}.
437      */
438     public static BitChromosome of(final BitSet bits, final int length) {
439         final byte[] bytes = bit.newArray(length);
440         for (int i = 0; i < length; ++i) {
441             if (bits.get(i)) {
442                 bit.set(bytes, i);
443             }
444         }
445         final double p = (double)bit.count(bytes)/(double)length;
446 
447         return new BitChromosome(bytes, length, p);
448     }
449 
450     /**
451      * Constructing a new BitChromosome from a given BitSet.
452      * The BitSet is copied while construction. The length of the constructed
453      * BitChromosome will be {@code bitSet.length()}
454      * (@see BitSet#length).
455      *
456      @param bits the bit-set which initializes the chromosome
457      @return a new {@code BitChromosome} with the given parameter
458      @throws NullPointerException if the {@code bitSet} is
459      *        {@code null}.
460      */
461     public static BitChromosome of(final BitSet bits) {
462         return new BitChromosome(bits.toByteArray(), -1);
463     }
464 
465     /**
466      * Create a new {@code BitChromosome} from the given big integer value.
467      *
468      @param value the value of the created {@code BitChromosome}
469      @return a new {@code BitChromosome} with the given parameter
470      @throws NullPointerException if the given {@code value} is {@code null}.
471      */
472     public static BitChromosome of(final BigInteger value) {
473         return new BitChromosome(value.toByteArray(), -1);
474     }
475 
476     /**
477      * Create a new {@code BitChromosome} from the given character sequence
478      * containing '0' and '1'; as created with the {@link #toCanonicalString()}
479      * method.
480      *
481      @param value the input string.
482      @return a new {@code BitChromosome} with the given parameter
483      @throws NullPointerException if the {@code value} is {@code null}.
484      @throws IllegalArgumentException if the length of the character sequence
485      *         is zero or contains other characters than '0' or '1'.
486      */
487     public static BitChromosome of(final CharSequence value) {
488         return new BitChromosome(toByteArray(requireNonNull(value, "Input")), -1);
489     }
490 
491     @Override
492     public int hashCode() {
493         return HashBuilder.of(getClass()).and(_genes).value();
494     }
495 
496     @Override
497     public boolean equals(final Object o) {
498         if (o == this) {
499             return true;
500         }
501         if (o == null || getClass() != o.getClass()) {
502             return false;
503         }
504 
505         final BitChromosome c = (BitChromosome)o;
506         boolean equals = length() == c.length();
507         for (int i = 0, n = length(); equals && i < n; ++i) {
508             equals = getGene(i== c.getGene(i);
509         }
510         return equals;
511     }
512 
513     @Override
514     public String toString() {
515         return bit.toByteString(_genes);
516     }
517 
518     /* *************************************************************************
519      *  Java object serialization
520      * ************************************************************************/
521 
522     private void writeObject(final ObjectOutputStream out)
523         throws IOException
524     {
525         out.defaultWriteObject();
526 
527         out.writeInt(_length);
528         out.writeDouble(_p);
529         out.writeInt(_genes.length);
530         out.write(_genes);
531     }
532 
533     private void readObject(final ObjectInputStream in)
534         throws IOException, ClassNotFoundException
535     {
536         in.defaultReadObject();
537 
538         _length = in.readInt();
539         _p = in.readDouble();
540 
541         final int bytes = in.readInt();
542         _genes = new byte[bytes];
543         in.readFully(_genes);
544 
545         _seq = new BitGeneArray(_genes, 0, _length);
546     }
547 
548     /* *************************************************************************
549      *  JAXB object serialization
550      * ************************************************************************/
551 
552     @XmlRootElement(name = "bit-chromosome")
553     @XmlType(name = "org.jenetics.BitChromosome")
554     @XmlAccessorType(XmlAccessType.FIELD)
555     final static class Model {
556 
557         @XmlAttribute(name = "length", required = true)
558         public int length;
559 
560         @XmlAttribute(name = "ones-probability", required = true)
561         public double probability;
562 
563         @XmlValue
564         public String value;
565 
566         public final static class Adapter
567             extends XmlAdapter<Model, BitChromosome>
568         {
569             @Override
570             public Model marshal(final BitChromosome chromosome) {
571                 final Model model = new Model();
572                 model.length = chromosome._length;
573                 model.probability = chromosome._p;
574                 model.value = chromosome.toCanonicalString();
575                 return model;
576             }
577 
578             @Override
579             public BitChromosome unmarshal(final Model model) {
580                 return new BitChromosome(
581                     toByteArray(model.value),
582                     model.length,
583                     model.probability
584                 );
585             }
586         }
587     }
588 
589 }