BitChromosome.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-6.0.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 6.0
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     @Override
170     public BitGene gene() {
171         return BitGene.of(Bits.get(_genes, 0));
172     }
173 
174     /**
175      * Return the value of the first gene of this chromosome.
176      *
177      @since 4.2
178      *
179      @return the first value of this chromosome.
180      */
181     public boolean booleanValue() {
182         return Bits.get(_genes, 0);
183     }
184 
185     @Override
186     public BitGene get(final int index) {
187         rangeCheck(index);
188         return BitGene.of(Bits.get(_genes, index));
189     }
190 
191     @Override
192     public int length() {
193         return _length;
194     }
195 
196     /**
197      * Return the value on the specified index.
198      *
199      @since 4.2
200      *
201      @param index the gene index
202      @return the wanted gene value
203      @throws IndexOutOfBoundsException if the index is out of range
204      *          (index &lt; 1 || index &gt;= length()).
205      */
206     public boolean booleanValue(final int index) {
207         rangeCheck(index);
208         return Bits.get(_genes, index);
209     }
210 
211     /**
212      * Returns the number of bits set to true in this {@code BitChromosome}.
213      *
214      @return the number of bits set to true in this {@code BitChromosome}
215      */
216     public int bitCount() {
217         return Bits.count(_genes);
218     }
219 
220     /**
221      * Return a list iterator over the bit-genes of this chromosome.
222      *
223      @return a list iterator over the bit-genes of this chromosome
224      */
225     public ListIterator<BitGene> listIterator() {
226         return _seq.listIterator();
227     }
228 
229     /**
230      * Return the long value this BitChromosome represents.
231      *
232      @return long value this BitChromosome represents.
233      */
234     @Override
235     public int intValue() {
236         return (int)longValue();
237     }
238 
239     /**
240      * Return the long value this BitChromosome represents.
241      *
242      @return long value this BitChromosome represents.
243      */
244     @Override
245     public long longValue() {
246         return toBigInteger().longValue();
247     }
248 
249     /**
250      * Return the float value this BitChromosome represents.
251      *
252      @return float value this BitChromosome represents.
253      */
254     @Override
255     public float floatValue() {
256         return (float)longValue();
257     }
258 
259     /**
260      * Return the double value this BitChromosome represents.
261      *
262      @return double value this BitChromosome represents.
263      */
264     @Override
265     public double doubleValue() {
266         return longValue();
267     }
268 
269     /**
270      * Return always {@code true}.
271      *
272      @return {@code true}, always
273      */
274     @Override
275     public boolean isValid() {
276         return true;
277     }
278 
279     /**
280      * Return the {@code BigInteger} value this {@code BitChromosome} represents.
281      *
282      @return {@code BigInteger} value this {@code BitChromosome} represents.
283      */
284     public BigInteger toBigInteger() {
285         return new BigInteger(_genes);
286     }
287 
288     /**
289      * Returns the two's-complement binary representation of this
290      * large integer. The output array is in <i>big-endian</i>
291      * byte-order: the most significant byte is at the offset position.
292      *
293      <p>Note: This representation is consistent with {@code java.lang.BigInteger
294      *          } byte array representation and can be used for conversion
295      *          between the two classes.</p>
296      *
297      @param bytes the bytes to hold the binary representation
298      *           (two's-complement) of this large integer.
299      @return the number of bytes written.
300      @throws IndexOutOfBoundsException
301      *         if {@code bytes.length < (int)Math.ceil(length()/8.0)}
302      @throws NullPointerException it the give array is {@code null}.
303      */
304     public int toByteArray(final byte[] bytes) {
305         if (bytes.length < _genes.length) {
306             throw new IndexOutOfBoundsException();
307         }
308 
309         System.arraycopy(_genes, 0, bytes, 0, _genes.length);
310         return _genes.length;
311     }
312 
313     /**
314      @return a byte array which represents this {@code BitChromosome}. The
315      *         length of the array is {@code (int)Math.ceil(length()/8.0)}.
316      *
317      @see #toByteArray(byte[])
318      */
319     public byte[] toByteArray() {
320         final byte[] data = new byte[_genes.length];
321         toByteArray(data);
322         return data;
323     }
324 
325     /**
326      * Return the corresponding BitSet of this BitChromosome.
327      *
328      @return The corresponding BitSet of this BitChromosome.
329      */
330     public BitSet toBitSet() {
331         final BitSet set = new BitSet(length());
332         for (int i = 0, n = length(); i < n; ++i) {
333             set.set(i, get(i).bit());
334         }
335         return set;
336     }
337 
338     /**
339      * Return the indexes of the <i>ones</i> of this bit-chromosome as stream.
340      *
341      @since 3.0
342      *
343      @return the indexes of the <i>ones</i> of this bit-chromosome
344      */
345     public IntStream ones() {
346         return IntStream.range(0, length())
347             .filter(index -> Bits.get(_genes, index));
348     }
349 
350     /**
351      * Return the indexes of the <i>zeros</i> of this bit-chromosome as stream.
352      *
353      @since 3.0
354      *
355      @return the indexes of the <i>zeros</i> of this bit-chromosome
356      */
357     public IntStream zeros() {
358         return IntStream.range(0, length())
359             .filter(index -> !Bits.get(_genes, index));
360     }
361 
362     @Override
363     public BitChromosome newInstance(final ISeq<BitGene> genes) {
364         requireNonNull(genes, "Genes");
365         if (genes.isEmpty()) {
366             throw new IllegalArgumentException(
367                 "The genes sequence must contain at least one gene."
368             );
369         }
370 
371         final BitChromosome chromosome = new BitChromosome(
372             Bits.newArray(genes.length()), genes.length()
373         );
374         int ones = 0;
375 
376         if (genes instanceof BitGeneISeq) {
377             final BitGeneISeq iseq = (BitGeneISeq)genes;
378             iseq.copyTo(chromosome._genes);
379             ones = Bits.count(chromosome._genes);
380         else {
381             for (int i = genes.length(); --i >= 0;) {
382                 if (genes.get(i).booleanValue()) {
383                     Bits.set(chromosome._genes, i);
384                     ++ones;
385                 }
386             }
387         }
388 
389         chromosome._p = (double)ones/(double)genes.length();
390         return chromosome;
391     }
392 
393     @Override
394     public BitChromosome newInstance() {
395         return of(_length, _p);
396     }
397 
398     /**
399      * Return the BitChromosome as String. A TRUE is represented by a 1 and
400      * a FALSE by a 0. The returned string can be used to create a new
401      * chromosome with the {@link #of(CharSequence)} constructor.
402      *
403      @return String representation (containing only '1' and '0') of the
404      *         BitChromosome.
405      */
406     public String toCanonicalString() {
407         return stream()
408             .map(g -> g.booleanValue() "1" "0")
409             .collect(joining());
410     }
411 
412     @Override
413     public int compareTo(final BitChromosome that) {
414         return toBigInteger().compareTo(that.toBigInteger());
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 byte[] data = _genes.clone();
424         Bits.invert(data);
425         return new BitChromosome(data, _length, 1.0 - _p);
426     }
427 
428     /**
429      * Construct a new BitChromosome with the given _length.
430      *
431      @param length Length of the BitChromosome, number of bits.
432      @param p Probability of the TRUEs in the BitChromosome.
433      @return a new {@code BitChromosome} with the given parameter
434      @throws NegativeArraySizeException if the {@code length} is smaller
435      *         than one.
436      @throws IllegalArgumentException if {@code p} is not a valid probability.
437      */
438     public static BitChromosome of(final int length, final double p) {
439         return new BitChromosome(Bits.newArray(length, p), length, p);
440     }
441 
442     /**
443      * Constructing a new BitChromosome with the given _length. The TRUEs and
444      * FALSE in the {@code Chromosome} are equally distributed.
445      *
446      @param length Length of the BitChromosome.
447      @return a new {@code BitChromosome} with the given parameter
448      @throws NegativeArraySizeException if the {@code _length} is smaller
449      *         than one.
450      */
451     public static BitChromosome of(final int length) {
452         return new BitChromosome(Bits.newArray(length, 0.5), length, 0.5);
453     }
454 
455     /**
456      * Create a new {@code BitChromosome} with the given parameters.
457      *
458      @param length length of the BitChromosome.
459      @param bits the bit-set which initializes the chromosome
460      @return a new {@code BitChromosome} with the given parameter
461      @throws NegativeArraySizeException if the {@code length} is smaller
462      *         than one.
463      @throws NullPointerException if the {@code bitSet} is
464      *         {@code null}.
465      */
466     public static BitChromosome of(final BitSet bits, final int length) {
467         final byte[] bytes = Bits.newArray(length);
468         for (int i = 0; i < length; ++i) {
469             if (bits.get(i)) {
470                 Bits.set(bytes, i);
471             }
472         }
473         final double p = (doubleBits.count(bytes)/(double)length;
474 
475         return new BitChromosome(bytes, length, p);
476     }
477 
478     /**
479      * Create a new {@code BitChromosome} with the given parameters.
480      *
481      @param length length of the BitChromosome.
482      @param bits the bit-set which initializes the chromosome
483      @param p Probability of the TRUEs in the BitChromosome.
484      @return a new {@code BitChromosome} with the given parameter
485      @throws NegativeArraySizeException if the {@code length} is smaller than
486      *         one.
487      @throws NullPointerException if the {@code bitSet} is {@code null}.
488      @throws IllegalArgumentException if {@code p} is not a valid probability.
489      */
490     public static BitChromosome of(
491         final BitSet bits,
492         final int length,
493         final double p
494     ) {
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 
502         return new BitChromosome(bytes, length, Requires.probability(p));
503     }
504 
505     /**
506      * Constructing a new BitChromosome from a given BitSet.
507      * The BitSet is copied while construction. The length of the constructed
508      * BitChromosome will be {@code bitSet.length()} ({@link BitSet#length}).
509      *
510      @param bits the bit-set which initializes the chromosome
511      @return a new {@code BitChromosome} with the given parameter
512      @throws NullPointerException if the {@code bitSet} is
513      *        {@code null}.
514      */
515     public static BitChromosome of(final BitSet bits) {
516         return new BitChromosome(bits.toByteArray(), -1);
517     }
518 
519     /**
520      * Create a new {@code BitChromosome} from the given big integer value.
521      *
522      @param value the value of the created {@code BitChromosome}
523      @return a new {@code BitChromosome} with the given parameter
524      @throws NullPointerException if the given {@code value} is {@code null}.
525      */
526     public static BitChromosome of(final BigInteger value) {
527         return new BitChromosome(value.toByteArray(), -1);
528     }
529 
530     /**
531      * Create a new {@code BitChromosome} from the given big integer value and
532      * ones probability.
533      *
534      @param value the value of the created {@code BitChromosome}
535      @param p Probability of the TRUEs in the BitChromosome.
536      @return a new {@code BitChromosome} with the given parameter
537      @throws NullPointerException if the given {@code value} is {@code null}.
538      @throws IllegalArgumentException if {@code p} is not a valid probability.
539      */
540     public static BitChromosome of(final BigInteger value, final double p) {
541         final byte[] bits = value.toByteArray();
542         return new BitChromosome(bits, bits.length*8, Requires.probability(p));
543     }
544 
545     /**
546      * Create a new {@code BitChromosome} from the given character sequence
547      * containing '0' and '1'; as created with the {@link #toCanonicalString()}
548      * method.
549      *
550      @param value the input string.
551      @return a new {@code BitChromosome} with the given parameter
552      @throws NullPointerException if the {@code value} is {@code null}.
553      @throws IllegalArgumentException if the length of the character sequence
554      *         is zero or contains other characters than '0' or '1'.
555      */
556     public static BitChromosome of(final CharSequence value) {
557         return new BitChromosome(toByteArray(requireNonNull(value, "Input")), -1);
558     }
559 
560     /**
561      * Create a new {@code BitChromosome} from the given character sequence
562      * containing '0' and '1'; as created with the {@link #toCanonicalString()}
563      * method.
564      *
565      @param value the input string.
566      @param p Probability of the TRUEs in the BitChromosome.
567      @return a new {@code BitChromosome} with the given parameter
568      @throws NullPointerException if the {@code value} is {@code null}.
569      @throws IllegalArgumentException if the length of the character sequence
570      *         is zero or contains other characters than '0' or '1'.
571      @throws IllegalArgumentException if {@code p} is not a valid probability.
572      */
573     public static BitChromosome of(final CharSequence value, final double p) {
574         final byte[] bits = toByteArray(requireNonNull(value, "Input"));
575         return new BitChromosome(bits, bits.length*8, Requires.probability(p));
576     }
577 
578     /**
579      * Create a new {@code BitChromosome} from the given character sequence
580      * containing '0' and '1'; as created with the {@link #toCanonicalString()}
581      * method.
582      *
583      @param value the input string.
584      @param length length of the BitChromosome
585      @param p Probability of the TRUEs in the BitChromosome.
586      @return a new {@code BitChromosome} with the given parameter
587      @throws NullPointerException if the {@code value} is {@code null}.
588      @throws IllegalArgumentException if the length of the character sequence
589      *         is zero or contains other characters than '0' or '1'.
590      @throws IllegalArgumentException if {@code p} is not a valid probability.
591      */
592     public static BitChromosome of(
593         final CharSequence value,
594         final int length,
595         final double p
596     ) {
597         final byte[] bits = toByteArray(requireNonNull(value, "Input"));
598         return new BitChromosome(bits, length, Requires.probability(p));
599     }
600 
601     @Override
602     public int hashCode() {
603         return hash(_genes, hash(getClass()));
604     }
605 
606     @Override
607     public boolean equals(final Object obj) {
608         return obj == this ||
609             obj != null &&
610             getClass() == obj.getClass() &&
611             length() == ((BitChromosome)obj).length() &&
612             Arrays.equals(_genes, ((BitChromosome)obj)._genes);
613     }
614 
615     @Override
616     public String toString() {
617         return Bits.toByteString(_genes);
618     }
619 
620 
621     /* *************************************************************************
622      *  Java object serialization
623      * ************************************************************************/
624 
625     private Object writeReplace() {
626         return new Serial(Serial.BIT_CHROMOSOME, this);
627     }
628 
629     private void readObject(final ObjectInputStream stream)
630         throws InvalidObjectException
631     {
632         throw new InvalidObjectException("Serialization proxy required.");
633     }
634 
635     void write(final DataOutput outthrows IOException {
636         writeInt(_length, out);
637         out.writeDouble(_p);
638         writeInt(_genes.length, out);
639         out.write(_genes);
640     }
641 
642     static BitChromosome read(final DataInput inthrows IOException {
643         final int length = readInt(in);
644         final double p = in.readDouble();
645         final byte[] genes = new byte[readInt(in)];
646         in.readFully(genes);
647 
648         return new BitChromosome(genes, length, p);
649     }
650 
651 }