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