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