151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/* 251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Copyright (c) 1997, 2006, Oracle and/or its affiliates. All rights reserved. 351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is free software; you can redistribute it and/or modify it 651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * under the terms of the GNU General Public License version 2 only, as 751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * published by the Free Software Foundation. Oracle designates this 851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * particular file as subject to the "Classpath" exception as provided 951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * by Oracle in the LICENSE file that accompanied this code. 1051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is distributed in the hope that it will be useful, but WITHOUT 1251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * version 2 for more details (a copy is included in the LICENSE file that 1551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * accompanied this code). 1651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * You should have received a copy of the GNU General Public License version 1851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2 along with this work; if not, write to the Free Software Foundation, 1951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * or visit www.oracle.com if you need additional information or have any 2351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * questions. 2451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 2551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 2651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipackage sun.security.util; 2751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 2851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskiimport java.io.ByteArrayOutputStream; 2951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskiimport java.util.Arrays; 3051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 3151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/** 3251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * A packed array of booleans. 3351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 3451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Joshua Bloch 3551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Douglas Hoover 3651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 3751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 3851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipublic class BitArray { 3951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 4051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private byte[] repn; 4151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private int length; 4251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 4351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int BITS_PER_UNIT = 8; 4451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 4551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static int subscript(int idx) { 4651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return idx / BITS_PER_UNIT; 4751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 4851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 4951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static int position(int idx) { // bits big-endian in each unit 5051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return 1 << (BITS_PER_UNIT - 1 - (idx % BITS_PER_UNIT)); 5151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 5251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 5351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 5451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Creates a BitArray of the specified size, initialized to zeros. 5551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 5651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public BitArray(int length) throws IllegalArgumentException { 5751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (length < 0) { 5851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IllegalArgumentException("Negative length for BitArray"); 5951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 6051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 6151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.length = length; 6251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 6351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski repn = new byte[(length + BITS_PER_UNIT - 1)/BITS_PER_UNIT]; 6451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 6551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 6651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 6751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 6851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Creates a BitArray of the specified size, initialized from the 6951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * specified byte array. The most significant bit of a[0] gets 7051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * index zero in the BitArray. The array a must be large enough 7151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to specify a value for every bit in the BitArray. In other words, 7251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 8*a.length <= length. 7351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 7451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public BitArray(int length, byte[] a) throws IllegalArgumentException { 7551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 7651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (length < 0) { 7751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IllegalArgumentException("Negative length for BitArray"); 7851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 7951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (a.length * BITS_PER_UNIT < length) { 8051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IllegalArgumentException("Byte array too short to represent " + 8151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski "bit array of given length"); 8251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 8351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 8451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.length = length; 8551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 8651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int repLength = ((length + BITS_PER_UNIT - 1)/BITS_PER_UNIT); 8751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int unusedBits = repLength*BITS_PER_UNIT - length; 8851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski byte bitMask = (byte) (0xFF << unusedBits); 8951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 9051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 9151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski normalize the representation: 9251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 1. discard extra bytes 9351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 2. zero out extra bits in the last byte 9451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 9551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski repn = new byte[repLength]; 9651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski System.arraycopy(a, 0, repn, 0, repLength); 9751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (repLength > 0) { 9851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski repn[repLength - 1] &= bitMask; 9951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 10051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 10151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 10251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 10351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Create a BitArray whose bits are those of the given array 10451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of Booleans. 10551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 10651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public BitArray(boolean[] bits) { 10751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski length = bits.length; 10851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski repn = new byte[(length + 7)/8]; 10951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 11051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i=0; i < length; i++) { 11151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski set(i, bits[i]); 11251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 11351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 11451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 11551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 11651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 11751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Copy constructor (for cloning). 11851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 11951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private BitArray(BitArray ba) { 12051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski length = ba.length; 12151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski repn = ba.repn.clone(); 12251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 12351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 12451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 12551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the indexed bit in this BitArray. 12651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 12751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean get(int index) throws ArrayIndexOutOfBoundsException { 12851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (index < 0 || index >= length) { 12951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new ArrayIndexOutOfBoundsException(Integer.toString(index)); 13051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 13151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 13251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return (repn[subscript(index)] & position(index)) != 0; 13351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 13451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 13551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 13651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Sets the indexed bit in this BitArray. 13751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 13851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void set(int index, boolean value) 13951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throws ArrayIndexOutOfBoundsException { 14051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (index < 0 || index >= length) { 14151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new ArrayIndexOutOfBoundsException(Integer.toString(index)); 14251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 14351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int idx = subscript(index); 14451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int bit = position(index); 14551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 14651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (value) { 14751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski repn[idx] |= bit; 14851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 14951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski repn[idx] &= ~bit; 15051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 15151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 15251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 15351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 15451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the length of this BitArray. 15551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 15651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int length() { 15751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return length; 15851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 15951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 16051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 16151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns a Byte array containing the contents of this BitArray. 16251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The bit stored at index zero in this BitArray will be copied 16351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * into the most significant bit of the zeroth element of the 16451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * returned byte array. The last byte of the returned byte array 16551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * will be contain zeros in any bits that do not have corresponding 16651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * bits in the BitArray. (This matters only if the BitArray's size 16751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * is not a multiple of 8.) 16851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 16951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public byte[] toByteArray() { 17051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return repn.clone(); 17151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 17251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 17351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean equals(Object obj) { 17451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (obj == this) return true; 17551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (obj == null || !(obj instanceof BitArray)) return false; 17651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 17751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski BitArray ba = (BitArray) obj; 17851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 17951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (ba.length != length) return false; 18051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 18151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = 0; i < repn.length; i += 1) { 18251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (repn[i] != ba.repn[i]) return false; 18351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 18451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return true; 18551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 18651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 18751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 18851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Return a boolean array with the same bit values a this BitArray. 18951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 19051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean[] toBooleanArray() { 19151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean[] bits = new boolean[length]; 19251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 19351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i=0; i < length; i++) { 19451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski bits[i] = get(i); 19551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 19651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return bits; 19751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 19851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 19951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 20051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns a hash code value for this bit array. 20151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 20251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return a hash code value for this bit array. 20351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 20451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int hashCode() { 20551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int hashCode = 0; 20651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 20751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = 0; i < repn.length; i++) 20851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski hashCode = 31*hashCode + repn[i]; 20951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 21051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return hashCode ^ length; 21151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 21251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 21351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 21451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public Object clone() { 21551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new BitArray(this); 21651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 21751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 21851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 21951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final byte[][] NYBBLE = { 22051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'0',(byte)'0',(byte)'0',(byte)'0'}, 22151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'0',(byte)'0',(byte)'0',(byte)'1'}, 22251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'0',(byte)'0',(byte)'1',(byte)'0'}, 22351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'0',(byte)'0',(byte)'1',(byte)'1'}, 22451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'0',(byte)'1',(byte)'0',(byte)'0'}, 22551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'0',(byte)'1',(byte)'0',(byte)'1'}, 22651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'0',(byte)'1',(byte)'1',(byte)'0'}, 22751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'0',(byte)'1',(byte)'1',(byte)'1'}, 22851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'1',(byte)'0',(byte)'0',(byte)'0'}, 22951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'1',(byte)'0',(byte)'0',(byte)'1'}, 23051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'1',(byte)'0',(byte)'1',(byte)'0'}, 23151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'1',(byte)'0',(byte)'1',(byte)'1'}, 23251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'1',(byte)'1',(byte)'0',(byte)'0'}, 23351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'1',(byte)'1',(byte)'0',(byte)'1'}, 23451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'1',(byte)'1',(byte)'1',(byte)'0'}, 23551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski { (byte)'1',(byte)'1',(byte)'1',(byte)'1'} 23651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski }; 23751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 23851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int BYTES_PER_LINE = 8; 23951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 24051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 24151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns a string representation of this BitArray. 24251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 24351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public String toString() { 24451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ByteArrayOutputStream out = new ByteArrayOutputStream(); 24551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 24651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = 0; i < repn.length - 1; i++) { 24751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski out.write(NYBBLE[(repn[i] >> 4) & 0x0F], 0, 4); 24851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski out.write(NYBBLE[repn[i] & 0x0F], 0, 4); 24951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 25051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (i % BYTES_PER_LINE == BYTES_PER_LINE - 1) { 25151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski out.write('\n'); 25251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 25351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski out.write(' '); 25451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 25551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 25651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 25751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // in last byte of repn, use only the valid bits 25851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = BITS_PER_UNIT * (repn.length - 1); i < length; i++) { 25951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski out.write(get(i) ? '1' : '0'); 26051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 26151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 26251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new String(out.toByteArray()); 26351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 26451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 26551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 26651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public BitArray truncate() { 26751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i=length-1; i>=0; i--) { 26851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (get(i)) { 26951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new BitArray(i+1, Arrays.copyOf(repn, (i + BITS_PER_UNIT)/BITS_PER_UNIT)); 27051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 27151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 27251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new BitArray(1); 27351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 27451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 27551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski} 276