001/*
002 * Java Genetic Algorithm Library (jenetics-8.0.0).
003 * Copyright (c) 2007-2024 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 */
020package io.jenetics;
021
022import static java.lang.Math.min;
023import static java.util.Objects.requireNonNull;
024import static io.jenetics.internal.util.Requires.probability;
025import static io.jenetics.internal.util.SerialIO.readBytes;
026import static io.jenetics.internal.util.SerialIO.readInt;
027import static io.jenetics.internal.util.SerialIO.writeBytes;
028import static io.jenetics.internal.util.SerialIO.writeInt;
029
030import java.io.DataInput;
031import java.io.DataOutput;
032import java.io.IOException;
033import java.io.InvalidObjectException;
034import java.io.ObjectInputStream;
035import java.io.Serial;
036import java.io.Serializable;
037import java.math.BigInteger;
038import java.util.BitSet;
039import java.util.function.Function;
040import java.util.stream.IntStream;
041
042import io.jenetics.internal.collection.BitArray;
043import 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 */
065public 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         * Returns a {@code BitChromosome} whose value is ({@code this & other}).
368         *
369         * @since 7.1
370         *
371         * @param other value to be AND'ed with this {@code BitChromosome}.
372         * @return {@code this & other}
373         */
374        public BitChromosome and(final BitChromosome other) {
375                final var array = _genes.copy();
376                for (int i = 0; i < Math.min(length(), other.length()); ++i) {
377                        array.set(i, array.get(i) && other._genes.get(i));
378                }
379
380                return new BitChromosome(array, _p);
381        }
382
383        /**
384         * Returns a {@code BitChromosome} whose value is ({@code this | other}).
385         *
386         * @since 7.1
387         *
388         * @param other value to be OR'ed with this {@code BitChromosome}.
389         * @return {@code this | other}
390         */
391        public BitChromosome or(final BitChromosome other) {
392                final var array = _genes.copy();
393                for (int i = 0; i < Math.min(length(), other.length()); ++i) {
394                        array.set(i, array.get(i) || other._genes.get(i));
395                }
396
397                return new BitChromosome(array, _p);
398        }
399
400        /**
401         * Returns a {@code BitChromosome} whose value is ({@code this ^ other}).
402         *
403         * @since 7.1
404         *
405         * @param other value to be XOR'ed with this {@code BitChromosome}.
406         * @return {@code this ^ other}
407         */
408        public BitChromosome xor(final BitChromosome other) {
409                final var array = _genes.copy();
410                for (int i = 0; i < Math.min(length(), other.length()); ++i) {
411                        array.set(i, array.get(i) ^ other._genes.get(i));
412                }
413
414                return new BitChromosome(array, _p);
415        }
416
417        /**
418         * Invert the ones and zeros of this bit chromosome.
419         *
420         * @return a new BitChromosome with inverted ones and zeros.
421         */
422        public BitChromosome invert() {
423                final var array = _genes.copy();
424                array.invert();
425                return new BitChromosome(array, 1.0 - _p);
426        }
427
428        /**
429         * Returns a new {@code BitChromosome} whose value is ({@code this << n}).
430         * The shift distance, n, may be negative, in which case this method performs
431         * a right shift.
432         *
433         * @param n shift distance, in bits
434         * @return {@code this << n}
435         */
436        public BitChromosome shiftLeft(final int n) {
437                final var genes = _genes.copy();
438                if (n >= 0) {
439                        genes.shiftLeft(n);
440                } else {
441                        genes.shiftRight(Math.abs(n));
442                }
443                return new BitChromosome(genes, _p);
444        }
445
446        /**
447         * Returns a new {@code BitChromosome} whose value is ({@code this >> n}). The shift
448         * distance, n, may be negative, in which case this method performs a left
449         * shift.
450         *
451         * @param n shift distance, in bits
452         * @return {@code this >> n}
453         */
454        public BitChromosome shiftRight(final int n) {
455                final var genes = _genes.copy();
456                if (n >= 0) {
457                        genes.shiftRight(n);
458                } else {
459                        genes.shiftLeft(Math.abs(n));
460                }
461                return new BitChromosome(genes, _p);
462        }
463
464        @Override
465        public int hashCode() {
466                return _genes.hashCode();
467        }
468
469        @Override
470        public boolean equals(final Object obj) {
471                return obj == this ||
472                        obj instanceof BitChromosome other &&
473                        _genes.equals(other._genes);
474        }
475
476        @Override
477        public String toString() {
478                return _genes.toByteString();
479        }
480
481
482        /* *************************************************************************
483         * Static factory methods.
484         **************************************************************************/
485
486        /**
487         * Constructing a new BitChromosome with the given {@code length} and
488         * randomly set bits. The TRUEs and FALSE in the {@code Chromosome} are
489         * equally distributed with one-probability of {@code p}.
490         *
491         * @param length Length of the BitChromosome, number of bits.
492         * @param p Probability of the TRUEs in the BitChromosome.
493         * @return a new {@code BitChromosome} with the given parameter
494         * @throws NegativeArraySizeException if the {@code length} is smaller
495         *         than one.
496         * @throws IllegalArgumentException if {@code p} is not a valid probability.
497         */
498        public static BitChromosome of(final int length, final double p) {
499                return new BitChromosome(BitArray.ofLength(length, p), p);
500        }
501
502        /**
503         * Constructing a new BitChromosome with the given {@code length} and
504         * randomly set bits. The TRUEs and FALSE in the {@code Chromosome} are
505         * equally distributed with one-probability of 0.5.
506         *
507         * @param length Length of the BitChromosome.
508         * @return a new {@code BitChromosome} with the given parameter
509         * @throws NegativeArraySizeException if the {@code length} is smaller
510         *         than one.
511         */
512        public static BitChromosome of(final int length) {
513                return of(length, DEFAULT_PROBABILITY);
514        }
515
516        /**
517         * Create a new {@code BitChromosome} with the given parameters.
518         *
519         * @param length length of the BitChromosome.
520         * @param bits the bit-set which initializes the chromosome
521         * @param p Probability of the TRUEs in the BitChromosome.
522         * @return a new {@code BitChromosome} with the given parameter
523         * @throws NegativeArraySizeException if the {@code length} is smaller than
524         *         one.
525         * @throws NullPointerException if the {@code bitSet} is {@code null}.
526         * @throws IllegalArgumentException if {@code p} is not a valid probability.
527         */
528        public static BitChromosome of(
529                final BitSet bits,
530                final int length,
531                final double p
532        ) {
533                final var array = BitArray.ofLength(length);
534                for (int i = 0; i < length; ++i) {
535                        if (bits.get(i)) {
536                                array.set(i, true);
537                        }
538                }
539
540                return new BitChromosome(array, probability(p));
541        }
542
543        /**
544         * Create a new {@code BitChromosome} with the given parameters. The
545         * {@link #oneProbability()} of the chromosome is set to {@code 0.5}.
546         *
547         * @param length length of the BitChromosome.
548         * @param bits the bit-set which initializes the chromosome
549         * @return a new {@code BitChromosome} with the given parameter
550         * @throws NegativeArraySizeException if the {@code length} is smaller
551         *         than one.
552         * @throws NullPointerException if the {@code bitSet} is
553         *         {@code null}.
554         */
555        public static BitChromosome of(final BitSet bits, final int length) {
556                return of(bits, length, DEFAULT_PROBABILITY);
557        }
558
559        /**
560         * Constructing a new BitChromosome from a given BitSet. The length of the
561         * constructed {@code BitChromosome} will be ({@link BitSet#length}).
562         *
563         * @see #of(BitSet, int, double)
564         * @see #of(BitSet, int)
565         *
566         * @param bits the bit-set which initializes the chromosome
567         * @return a new {@code BitChromosome} with the given parameter
568         * @throws NullPointerException if the {@code bitSet} is
569         *        {@code null}.
570         */
571        public static BitChromosome of(final BitSet bits) {
572                return of(bits, bits.length());
573        }
574
575        /**
576         * Create a new {@code BitChromosome} from the given big integer value and
577         * ones' probability.
578         *
579         * @param value the value of the created {@code BitChromosome}
580         * @param length length of the BitChromosome
581         * @param p Probability of the TRUEs in the BitChromosome.
582         * @return a new {@code BitChromosome} with the given parameter
583         * @throws NullPointerException if the given {@code value} is {@code null}.
584         * @throws IllegalArgumentException if {@code p} is not a valid probability.
585         */
586        public static BitChromosome of(
587                final BigInteger value,
588                final int length,
589                final double p
590        ) {
591                final var array = BitArray.of(value, length);
592                return new BitChromosome(array, probability(p));
593        }
594
595        /**
596         * Create a new {@code BitChromosome} from the given big integer value and
597         * ones' probability. The {@link #oneProbability()} of the chromosome is set
598         * to {@code 0.5}.
599         *
600         * @since 7.0
601         *
602         * @param value the value of the created {@code BitChromosome}
603         * @param length length of the BitChromosome
604         * @return a new {@code BitChromosome} with the given parameter
605         * @throws NullPointerException if the given {@code value} is {@code null}.
606         * @throws IllegalArgumentException if {@code p} is not a valid probability.
607         */
608        public static BitChromosome of(
609                final BigInteger value,
610                final int length
611        ) {
612                return of(value, length, DEFAULT_PROBABILITY);
613        }
614
615
616        /**
617         * Create a new {@code BitChromosome} from the given big integer value. The
618         * {@link #oneProbability()} of the chromosome is set to {@code 0.5}.
619         *
620         * @param value the value of the created {@code BitChromosome}
621         * @return a new {@code BitChromosome} with the given parameter
622         * @throws NullPointerException if the given {@code value} is {@code null}.
623         */
624        public static BitChromosome of(final BigInteger value) {
625                final var array = BitArray.of(value);
626                return new BitChromosome(array, DEFAULT_PROBABILITY);
627        }
628
629        /**
630         * Create a new {@code BitChromosome} from the given character sequence
631         * containing '0' and '1'; as created with the {@link #toCanonicalString()}
632         * method.
633         *
634         * @param value the input string.
635         * @param length length of the BitChromosome
636         * @param p Probability of the TRUEs in the BitChromosome.
637         * @return a new {@code BitChromosome} with the given parameter
638         * @throws NullPointerException if the {@code value} is {@code null}.
639         * @throws IllegalArgumentException if the length of the character sequence
640         *         is zero or contains other characters than '0' or '1'.
641         * @throws IllegalArgumentException if {@code p} is not a valid probability.
642         */
643        public static BitChromosome of(
644                final CharSequence value,
645                final int length,
646                final double p
647        ) {
648                final var array = BitArray.of(value, length);
649                return new BitChromosome(array, probability(p));
650        }
651
652        /**
653         * Create a new {@code BitChromosome} from the given character sequence
654         * containing '0' and '1'; as created with the {@link #toCanonicalString()}
655         * method.
656         *
657         * @param value the input string.
658         * @param p Probability of the TRUEs in the BitChromosome.
659         * @return a new {@code BitChromosome} with the given parameter
660         * @throws NullPointerException if the {@code value} is {@code null}.
661         * @throws IllegalArgumentException if the length of the character sequence
662         *         is zero or contains other characters than '0' or '1'.
663         * @throws IllegalArgumentException if {@code p} is not a valid probability.
664         */
665        public static BitChromosome of(final CharSequence value, final double p) {
666                return of(value, value.length(), p);
667        }
668
669        /**
670         * Create a new {@code BitChromosome} from the given character sequence
671         * containing '0' and '1'; as created with the {@link #toCanonicalString()}
672         * method. The {@link #oneProbability()} of the chromosome is set to
673         * {@code 0.5}.
674         *
675         * @param value the input string.
676         * @return a new {@code BitChromosome} with the given parameter
677         * @throws NullPointerException if the {@code value} is {@code null}.
678         * @throws IllegalArgumentException if the length of the character sequence
679         *         is zero or contains other characters than '0' or '1'.
680         */
681        public static BitChromosome of(final CharSequence value) {
682                return of(value, value.length(), DEFAULT_PROBABILITY);
683        }
684
685
686        /* *************************************************************************
687         *  Java object serialization
688         * ************************************************************************/
689
690        @Serial
691        private Object writeReplace() {
692                return new SerialProxy(SerialProxy.BIT_CHROMOSOME, this);
693        }
694
695        @Serial
696        private void readObject(final ObjectInputStream stream)
697                throws InvalidObjectException
698        {
699                throw new InvalidObjectException("Serialization proxy required.");
700        }
701
702        void write(final DataOutput out) throws IOException {
703                writeBytes(toByteArray(), out);
704                writeInt(length(), out);
705                out.writeDouble(oneProbability());
706        }
707
708        static BitChromosome read(final DataInput in) throws IOException {
709                final var bytes = readBytes(in);
710                final var length  = readInt(in);
711                final var p = in.readDouble();
712                final var genes = BitArray.of(bytes,0, length);
713
714                return new BitChromosome(genes, p);
715        }
716
717}