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