BitChromosome.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-1.5.0).
003  * Copyright (c) 2007-2013 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.String.format;
023 import static java.util.Objects.requireNonNull;
024 import static org.jenetics.util.object.checkProbability;
025 import static org.jenetics.util.object.hashCodeOf;
026 
027 import java.io.IOException;
028 import java.io.ObjectInputStream;
029 import java.io.ObjectOutputStream;
030 import java.util.BitSet;
031 import java.util.Iterator;
032 import java.util.ListIterator;
033 
034 import javolution.text.Text;
035 import javolution.xml.XMLFormat;
036 import javolution.xml.XMLSerializable;
037 import javolution.xml.stream.XMLStreamException;
038 
039 import org.jscience.mathematics.number.LargeInteger;
040 import org.jscience.mathematics.number.Number;
041 
042 import org.jenetics.util.ISeq;
043 import org.jenetics.util.bit;
044 
045 /**
046  * Implementation of the <i>classical</i> BitChromosome.
047  *
048  @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
049  @since 1.0
050  @version 1.5 &mdash; <em>$Date: 2013-12-05 $</em>
051  */
052 public class BitChromosome extends Number<BitChromosome>
053     implements
054         Chromosome<BitGene>,
055         XMLSerializable
056 {
057     private static final long serialVersionUID = 1L;
058 
059 
060     /**
061      * The one's probability of the randomly generated Chromosome.
062      */
063     protected double _p;
064 
065     /**
066      * The length of the chromosomes (number of bits).
067      */
068     protected int _length;
069 
070     /**
071      * The boolean array which holds the {@link BitGene}s.
072      */
073     protected byte[] _genes;
074     private transient BitGeneArray _seq;
075 
076 
077     private BitChromosome(final byte[] bits, final int length, final double p) {
078         if (bits.length != bit.toByteLength(length)) {
079             throw new IllegalArgumentException(String.format(
080                 "The byte array must has at least a length of " +
081                 "%d to contain %d bits.",
082                 bit.toByteLength(length), length
083             ));
084         }
085 
086         _length = length;
087         _p = checkProbability(p);
088         _genes = bits;
089         _seq = new BitGeneArray(_genes, 0, _length);
090 
091     }
092 
093     private BitChromosome(final byte[] bits, final int length) {
094         this(
095             bits,
096             length == -? bits.length*: length,
097             (double)bit.count(bits)/
098             (double)(length == -? bits.length*: length)
099         );
100     }
101 
102     /**
103      * Create a new {@code BitChromosome} from the given {@code byte} array.
104      *
105      @param bits the {@code byte} array.
106      */
107     public BitChromosome(final byte[] bits) {
108         this(bits.clone(), bits.length*8);
109     }
110 
111     /**
112      * Construct a new BitChromosome with the given _length.
113      *
114      @param length Length of the BitChromosome, number of bits.
115      @param p Probability of the TRUEs in the BitChromosome.
116      @throws NegativeArraySizeException if the {@code length} is smaller
117      *         than one.
118      @throws IllegalArgumentException if {@code p} is not a valid probability.
119      */
120     public BitChromosome(final int length, final double p) {
121         this(bit.newArray(length, p), length, p);
122     }
123 
124     /**
125      * Constructing a new BitChromosome with the given _length. The TRUEs and
126      * FALSE in the {@code Chromosome} are equally distributed.
127      *
128      @param length Length of the BitChromosome.
129      @throws NegativeArraySizeException if the {@code _length} is smaller
130      *         than one.
131      */
132     public BitChromosome(final int length) {
133         this(length, 0.5);
134     }
135 
136     /**
137      @param length Length of the BitChromosome.
138      @param bits the bit-set which initializes the chromosome
139      @throws NegativeArraySizeException if the {@code length} is smaller
140      *         than one.
141      @throws NullPointerException if the {@code bitSet} is
142      *         {@code null}.
143      */
144     public BitChromosome(final int length, final BitSet bits) {
145         this(toByteArray(requireNonNull(bits, "BitSet"), length));
146     }
147 
148     private static byte[] toByteArray(final BitSet bits, final int length) {
149         final byte[] bytes = bit.newArray(length);
150         for (int i = 0; i < length; ++i) {
151             if (bits.get(i)) {
152                 bit.set(bytes, i);
153             }
154         }
155         return bytes;
156     }
157 
158     /**
159      * Constructing a new BitChromosome from a given BitSet.
160      * The BitSet is copied while construction. The length of the constructed
161      * BitChromosome will be {@code bitSet.length()}
162      * (@see BitSet#length).
163      *
164      @param bits the bit-set which initializes the chromosome
165      @throws NullPointerException if the {@code bitSet} is
166      *         {@code null}.
167      */
168     public BitChromosome (final BitSet bits) {
169         this(bits.toByteArray(), -1);
170     }
171 
172     /**
173      * Create a new {@code BitChromosome} from the given large integer value.
174      *
175      @param value the value of the created {@code BitChromosome}
176      @throws NullPointerException if the given {@code value} is {@code null}.
177      */
178     public BitChromosome(final LargeInteger value) {
179         this(bit.toByteArray(value), -1);
180     }
181 
182     /**
183      * Create a new {@code BitChromosome} from the given character sequence
184      * containing '0' and '1'; as created with the {@link #toCanonicalString()}
185      * method.
186      *
187      @param value the input string.
188      @throws NullPointerException if the {@code value} is {@code null}.
189      @throws IllegalArgumentException if the length of the character sequence
190      *         is zero or contains other characters than '0' or '1'.
191      */
192     public BitChromosome (final CharSequence value) {
193         this(toByteArray(requireNonNull(value, "Input")), -1);
194     }
195 
196     private static byte[] toByteArray(final CharSequence value) {
197         final byte[] bytes = bit.newArray(value.length());
198         for (int i = value.length(); --i >= 0;) {
199             final char c = value.charAt(i);
200             if (c == '1') {
201                 bit.set(bytes, i);
202             else if (c != '0') {
203                 throw new IllegalArgumentException(format(
204                     "Illegal character '%s' at position %d", c, i
205                 ));
206             }
207         }
208 
209         return bytes;
210     }
211 
212     private void rangeCheck(final int index) {
213         assert(_length >= 0);
214         if (index < || index >= _length) {
215             throw new IndexOutOfBoundsException(
216                 "Index: " + index + ", Length: " + _length
217             );
218         }
219     }
220 
221     @Override
222     public BitGene getGene() {
223         assert (_genes != null);
224         assert (_genes.length > 0);
225         return BitGene.valueOf(bit.get(_genes, 0));
226     }
227 
228     @Override
229     public BitGene getGene(final int index) {
230         rangeCheck(index);
231         assert(_genes != null);
232         return BitGene.valueOf(bit.get(_genes, index));
233     }
234 
235     @Override
236     public ISeq<BitGene> toSeq() {
237         return _seq.toISeq();
238     }
239 
240     @Override
241     public int length() {
242         return _length;
243     }
244 
245     /**
246      * Returns the number of bits set to true in this {@code BitChromosome}.
247      *
248      @return the number of bits set to true in this {@code BitChromosome}
249      */
250     public int bitCount() {
251         return bit.count(_genes);
252     }
253 
254     @Override
255     public Iterator<BitGene> iterator() {
256         return _seq.iterator();
257     }
258 
259     public ListIterator<BitGene> listIterator() {
260         return _seq.listIterator();
261     }
262 
263     /**
264      * Return the long value this BitChromosome represents.
265      *
266      @return Long value this BitChromosome represents.
267      */
268     @Override
269     public long longValue() {
270         return toLargeInteger().longValue();
271     }
272 
273     /**
274      * Return the double value this BitChromosome represents.
275      *
276      @return Double value this BitChromosome represents.
277      */
278     @Override
279     public double doubleValue() {
280         return longValue();
281     }
282 
283     @Override
284     public boolean isValid() {
285         return true;
286     }
287 
288     /**
289      * Return the LargeInteger value this BitChromosome represents.
290      *
291      @return LargeInteger value this BitChromosome represents.
292      */
293     public LargeInteger toLargeInteger() {
294         return bit.toLargeInteger(_genes);
295     }
296 
297     /**
298      * Returns the two's-complement binary representation of this
299      * large integer. The output array is in <i>big-endian</i>
300      * byte-order: the most significant byte is at the offset position.
301      *
302      <p>Note: This representation is consistent with {@code java.lang.BigInteger
303      *          } byte array representation and can be used for conversion
304      *          between the two classes.</p>
305      *
306      @param bytes the bytes to hold the binary representation
307      *           (two's-complement) of this large integer.
308      @return the number of bytes written.
309      @throws IndexOutOfBoundsException
310      *         if {@code bytes.length < (int)Math.ceil(length()/8.0)}
311      @throws NullPointerException it the give array is {@code null}.
312      */
313     public int toByteArray(final byte[] bytes) {
314         if (bytes.length < _genes.length) {
315             throw new IndexOutOfBoundsException();
316         }
317 
318         System.arraycopy(_genes, 0, bytes, 0, _genes.length);
319 
320         return _genes.length;
321     }
322 
323     /**
324      @return a byte array which represents this {@code BitChromosome}. The
325      *         length of the array is {@code (int)Math.ceil(length()/8.0)}.
326      *
327      @see #toByteArray(byte[])
328      */
329     public byte[] toByteArray() {
330         final byte[] data = new byte[_genes.length];
331         toByteArray(data);
332         return data;
333     }
334 
335     /**
336      * Return the corresponding BitSet of this BitChromosome.
337      *
338      @return The corresponding BitSet of this BitChromosome.
339      */
340     public BitSet toBitSet() {
341         final BitSet set = new BitSet(length());
342         for (int i = 0, n = length(); i < n; ++i) {
343             set.set(i, getGene(i).getBit());
344         }
345         return set;
346     }
347 
348     @Override
349     public BitChromosome newInstance(final ISeq<BitGene> genes) {
350         requireNonNull(genes, "Genes");
351 
352         final BitChromosome chromosome = new BitChromosome(
353             bit.newArray(genes.length()), genes.length()
354         );
355         int ones = 0;
356 
357         if (genes instanceof BitGeneArray.BitGeneISeq) {
358             final BitGeneArray.BitGeneISeq iseq = (BitGeneArray.BitGeneISeq)genes;
359             iseq.copyTo(chromosome._genes);
360             ones = bit.count(chromosome._genes);
361         else {
362             for (int i = genes.length(); --i >= 0;) {
363                 if (genes.get(i).booleanValue()) {
364                     ++ones;
365                 }
366                 bit.set(chromosome._genes, i, genes.get(i).booleanValue());
367             }
368         }
369 
370         chromosome._p = (double)ones/(double)genes.length();
371         return chromosome;
372     }
373 
374     @Override
375     public BitChromosome newInstance() {
376         return new BitChromosome(_length, _p);
377     }
378 
379     /**
380      * Return the BitChromosome as String. A TRUE is represented by a 1 and
381      * a FALSE by a 0. The returned string can be used to create a new
382      * chromosome with the {@link #BitChromosome(CharSequence)} constructor.
383      *
384      @return String representation (containing only '1' and '0') of the
385      *         BitChromosome.
386      */
387     public String toCanonicalString() {
388         final StringBuilder out = new StringBuilder(length());
389         for (int i = 0; i < _length; ++i) {
390             out.append(bit.get(_genes, i'1' '0');
391         }
392         return out.toString();
393     }
394 
395     @Override
396     public int compareTo(final BitChromosome that) {
397         return toLargeInteger().compareTo(that.toLargeInteger());
398     }
399 
400     @Override
401     public boolean isLargerThan(final BitChromosome that) {
402         return toLargeInteger().isLargerThan(that.toLargeInteger());
403     }
404 
405     public LargeInteger sqrt() {
406         return toLargeInteger().sqrt();
407     }
408 
409     @Override
410     public BitChromosome plus(final BitChromosome that) {
411         return new BitChromosome(toLargeInteger().plus(that.toLargeInteger()));
412     }
413 
414     @Override
415     public BitChromosome opposite() {
416         return new BitChromosome(toLargeInteger().opposite());
417     }
418 
419     /**
420      * Invert the ones and zeros of this bit chromosome.
421      *
422      @return a new BitChromosome with inverted ones and zeros.
423      */
424     public BitChromosome invert() {
425         final BitChromosome copy = copy();
426         bit.invert(copy._genes);
427         return copy;
428     }
429 
430     @Override
431     public BitChromosome times(final BitChromosome that) {
432         return new BitChromosome(toLargeInteger().times(that.toLargeInteger()));
433     }
434 
435     @Override
436     public int hashCode() {
437         return hashCodeOf(getClass()).and(_genes).value();
438     }
439 
440     @Override
441     public boolean equals(final Object o) {
442         if (o == this) {
443             return true;
444         }
445         if (o == null || getClass() != o.getClass()) {
446             return false;
447         }
448 
449         final BitChromosome c = (BitChromosome)o;
450         boolean equals = length() == c.length();
451         for (int i = 0, n = length(); equals && i < n; ++i) {
452             equals = getGene(i== c.getGene(i);
453         }
454         return equals;
455     }
456 
457     @Override
458     public Text toText() {
459         return Text.valueOf(bit.toByteString(toByteArray()));
460     }
461 
462     @Override
463     public BitChromosome copy() {
464         final BitChromosome chromosome = new BitChromosome(_length, _p);
465         System.arraycopy(_genes, 0, chromosome._genes, 0, chromosome._genes.length);
466         return chromosome;
467     }
468 
469     /* *************************************************************************
470      *  XML object serialization
471      * ************************************************************************/
472 
473     static final XMLFormat<BitChromosome>
474     XML = new XMLFormat<BitChromosome>(BitChromosome.class)
475     {
476         private static final String LENGTH = "length";
477         private static final String PROBABILITY = "probability";
478 
479         @Override
480         public BitChromosome newInstance(
481             final Class<BitChromosome> cls, final InputElement xml
482         )
483             throws XMLStreamException
484         {
485             final int length = xml.getAttribute(LENGTH, 1);
486             final double probability = xml.getAttribute(PROBABILITY, 0.5);
487             final byte[] data = bit.fromByteString(xml.getText().toString());
488             final BitChromosome chromosome = new BitChromosome(data);
489             chromosome._p = probability;
490             chromosome._length = length;
491             return chromosome;
492         }
493         @Override
494         public void write(final BitChromosome chromosome, final OutputElement xml)
495             throws XMLStreamException
496         {
497             xml.setAttribute(LENGTH, chromosome._length);
498             xml.setAttribute(PROBABILITY, chromosome._p);
499             xml.addText(bit.toByteString(chromosome.toByteArray()));
500         }
501         @Override
502         public void read(final InputElement element, final BitChromosome gene) {
503         }
504     };
505 
506     /* *************************************************************************
507      *  Java object serialization
508      * ************************************************************************/
509 
510     private void writeObject(final ObjectOutputStream out)
511         throws IOException
512     {
513         out.defaultWriteObject();
514 
515         out.writeInt(_length);
516         out.writeDouble(_p);
517         out.writeInt(_genes.length);
518         out.write(_genes);
519     }
520 
521     private void readObject(final ObjectInputStream in)
522         throws IOException, ClassNotFoundException
523     {
524         in.defaultReadObject();
525 
526         _length = in.readInt();
527         _p = in.readDouble();
528 
529         final int bytes = in.readInt();
530         _genes = new byte[bytes];
531         in.readFully(_genes);
532 
533         _seq = new BitGeneArray(_genes, 0, _length);
534     }
535 
536 }
537 
538