BitChromosome.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-5.2.0).
003  * Copyright (c) 2007-2020 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 import static io.jenetics.internal.util.Hashes.hash;
027 import static io.jenetics.internal.util.SerialIO.readInt;
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.Serializable;
036 import java.math.BigInteger;
037 import java.util.Arrays;
038 import java.util.BitSet;
039 import java.util.ListIterator;
040 import java.util.stream.IntStream;
041 
042 import io.jenetics.internal.util.Bits;
043 import io.jenetics.internal.util.Requires;
044 import io.jenetics.util.ISeq;
045 
046 /**
047  * Implementation of the <i>classical</i> BitChromosome.
048  *
049  @see BitGene
050  *
051  * @implSpec
052  * This class is immutable and thread-safe.
053  *
054  @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
055  @since 1.0
056  @version 5.2
057  */
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 ones 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 final int _length;
076 
077     /**
078      * The boolean array which holds the {@link BitGene}s.
079      */
080     protected final byte[] _genes;
081 
082     // Wraps the genes byte array into a Seq<BitGene>.
083     private final transient BitGeneISeq _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 = BitGeneMSeq.of(_genes, length).toISeq();
091     }
092 
093     /**
094      * Create a new bit chromosome from the given bit (byte) array.
095      *
096      @param bits the bit values of the new chromosome gene.
097      @param start the initial (bit) index of the range to be copied, inclusive
098      @param end the final (bit) index of the range to be copied, exclusive.
099      *        (This index may lie outside the array.)
100      @throws java.lang.ArrayIndexOutOfBoundsException if {@code start < 0} or
101      *         {@code start > bits.length*8}
102      @throws java.lang.IllegalArgumentException if {@code start > end}
103      @throws java.lang.NullPointerException if the {@code bits} array is
104      *         {@code null}.
105      */
106     public BitChromosome(final byte[] bits, final int start, final int end) {
107         this(
108             Bits.copy(bits, start, end),
109             min(bits.length << 3, end- start,
110             0.0
111         );
112         _p = (doubleBits.count(_genes)/(double)_length;
113     }
114 
115     /**
116      * Create a new {@code BitChromosome} from the given {@code byte} array.
117      * This is a shortcut for {@code new BitChromosome(bits, 0, bits.length*8)}.
118      *
119      @param bits the {@code byte} array.
120      */
121     public BitChromosome(final byte[] bits) {
122         this(bits, 0, bits.length << 3);
123     }
124 
125     private BitChromosome(final byte[] bits, final int length) {
126         this(
127             bits,
128             length == -? bits.length*: length,
129             (doubleBits.count(bits)/
130             (double)(length == -? bits.length*: length)
131         );
132     }
133 
134     private static byte[] toByteArray(final CharSequence value) {
135         final byte[] bytes = Bits.newArray(value.length());
136         for (int i = value.length(); --i >= 0;) {
137             final char c = value.charAt(i);
138             if (c == '1') {
139                 Bits.set(bytes, i);
140             else if (c != '0') {
141                 throw new IllegalArgumentException(format(
142                     "Illegal character '%s' at position %d", c, i
143                 ));
144             }
145         }
146 
147         return bytes;
148     }
149 
150     private void rangeCheck(final int index) {
151         if (index < || index >= _length) {
152             throw new IndexOutOfBoundsException(
153                 "Index: " + index + ", Length: " + _length
154             );
155         }
156     }
157 
158     /**
159      * Return the one probability of this chromosome.
160      *
161      @since 5.2
162      *
163      @return the one probability of this chromosome.
164      */
165     public double oneProbability() {
166         return _p;
167     }
168 
169     /**
170      * Return the one probability of this chromosome.
171      *
172      @since 3.9
173      *
174      @return the one probability of this chromosome.
175      @deprecated Use {@link #oneProbability()} instead
176      */
177     @Deprecated
178     public double getOneProbability() {
179         return _p;
180     }
181 
182     @Override
183     public BitGene gene() {
184         assert _genes != null;
185         assert _genes.length > 0;
186         return BitGene.of(Bits.get(_genes, 0));
187     }
188 
189     /**
190      * Return the value of the first gene of this chromosome.
191      *
192      @since 4.2
193      *
194      @return the first value of this chromosome.
195      */
196     public boolean booleanValue() {
197         return Bits.get(_genes, 0);
198     }
199 
200     @Override
201     public BitGene get(final int index) {
202         rangeCheck(index);
203         assert _genes != null;
204         return BitGene.of(Bits.get(_genes, index));
205     }
206 
207     @Deprecated
208     @Override
209     public BitGene getGene(final int index) {
210         return get(index);
211     }
212 
213     /**
214      * Return the value on the specified index.
215      *
216      @since 4.2
217      *
218      @param index the gene index
219      @return the wanted gene value
220      @throws IndexOutOfBoundsException if the index is out of range
221      *          (index &lt; 1 || index &gt;= length()).
222      */
223     public boolean booleanValue(final int index) {
224         rangeCheck(index);
225         return Bits.get(_genes, index);
226     }
227 
228     @Override
229     @Deprecated
230     public ISeq<BitGene> toSeq() {
231         return _seq;
232     }
233 
234     @Override
235     public int length() {
236         return _length;
237     }
238 
239     /**
240      * Returns the number of bits set to true in this {@code BitChromosome}.
241      *
242      @return the number of bits set to true in this {@code BitChromosome}
243      */
244     public int bitCount() {
245         return Bits.count(_genes);
246     }
247 
248     /**
249      * Return a list iterator over the bit-genes of this chromosome.
250      *
251      @return a list iterator over the bit-genes of this chromosome
252      */
253     public ListIterator<BitGene> listIterator() {
254         return _seq.listIterator();
255     }
256 
257     /**
258      * Return the long value this BitChromosome represents.
259      *
260      @return long value this BitChromosome represents.
261      */
262     @Override
263     public int intValue() {
264         return (int)longValue();
265     }
266 
267     /**
268      * Return the long value this BitChromosome represents.
269      *
270      @return long value this BitChromosome represents.
271      */
272     @Override
273     public long longValue() {
274         return toBigInteger().longValue();
275     }
276 
277     /**
278      * Return the float value this BitChromosome represents.
279      *
280      @return float value this BitChromosome represents.
281      */
282     @Override
283     public float floatValue() {
284         return (float)longValue();
285     }
286 
287     /**
288      * Return the double value this BitChromosome represents.
289      *
290      @return double value this BitChromosome represents.
291      */
292     @Override
293     public double doubleValue() {
294         return longValue();
295     }
296 
297     /**
298      * Return always {@code true}.
299      *
300      @return {@code true}, always
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, get(i).bit());
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 -> Bits.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 -> !Bits.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             Bits.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 = Bits.count(chromosome._genes);
408         else {
409             for (int i = genes.length(); --i >= 0;) {
410                 if (genes.get(i).booleanValue()) {
411                     Bits.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 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         Bits.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(Bits.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(Bits.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 = Bits.newArray(length);
496         for (int i = 0; i < length; ++i) {
497             if (bits.get(i)) {
498                 Bits.set(bytes, i);
499             }
500         }
501         final double p = (doubleBits.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 = Bits.newArray(length);
524         for (int i = 0; i < length; ++i) {
525             if (bits.get(i)) {
526                 Bits.set(bytes, i);
527             }
528         }
529 
530         return new BitChromosome(bytes, length, Requires.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, Requires.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, Requires.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, Requires.probability(p));
627     }
628 
629     @Override
630     public int hashCode() {
631         return hash(_genes, hash(getClass()));
632     }
633 
634     @Override
635     public boolean equals(final Object obj) {
636         return obj == this ||
637             obj != null &&
638             getClass() == obj.getClass() &&
639             length() == ((BitChromosome)obj).length() &&
640             Arrays.equals(_genes, ((BitChromosome)obj)._genes);
641     }
642 
643     @Override
644     public String toString() {
645         return Bits.toByteString(_genes);
646     }
647 
648 
649     /* *************************************************************************
650      *  Java object serialization
651      * ************************************************************************/
652 
653     private Object writeReplace() {
654         return new Serial(Serial.BIT_CHROMOSOME, this);
655     }
656 
657     private void readObject(final ObjectInputStream stream)
658         throws InvalidObjectException
659     {
660         throw new InvalidObjectException("Serialization proxy required.");
661     }
662 
663     void write(final DataOutput outthrows IOException {
664         writeInt(_length, out);
665         out.writeDouble(_p);
666         writeInt(_genes.length, out);
667         out.write(_genes);
668     }
669 
670     static BitChromosome read(final DataInput inthrows IOException {
671         final int length = readInt(in);
672         final double p = in.readDouble();
673         final byte[] genes = new byte[readInt(in)];
674         in.readFully(genes);
675 
676         return new BitChromosome(genes, length, p);
677     }
678 
679 }