BitSet.java revision 953:221a84ef44c0
1/* 2 * Permission is hereby granted, free of charge, to any person obtaining a copy of 3 * this software and associated documentation files (the "Software"), to deal in 4 * the Software without restriction, including without limitation the rights to 5 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies 6 * of the Software, and to permit persons to whom the Software is furnished to do 7 * so, subject to the following conditions: 8 * 9 * The above copyright notice and this permission notice shall be included in all 10 * copies or substantial portions of the Software. 11 * 12 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 13 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 14 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 15 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 16 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 17 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 18 * SOFTWARE. 19 */ 20package jdk.nashorn.internal.runtime.regexp.joni; 21 22public final class BitSet { 23 static final int BITS_PER_BYTE = 8; 24 public static final int SINGLE_BYTE_SIZE = (1 << BITS_PER_BYTE); 25 private static final int BITS_IN_ROOM = 4 * BITS_PER_BYTE; 26 static final int BITSET_SIZE = (SINGLE_BYTE_SIZE / BITS_IN_ROOM); 27 static final int ROOM_SHIFT = log2(BITS_IN_ROOM); 28 29 final int[] bits = new int[BITSET_SIZE]; 30 31 private static final int BITS_TO_STRING_WRAP = 4; 32 @Override 33 public String toString() { 34 final StringBuilder buffer = new StringBuilder(); 35 buffer.append("BitSet"); 36 for (int i=0; i<SINGLE_BYTE_SIZE; i++) { 37 if ((i % (SINGLE_BYTE_SIZE / BITS_TO_STRING_WRAP)) == 0) buffer.append("\n "); 38 buffer.append(at(i) ? "1" : "0"); 39 } 40 return buffer.toString(); 41 } 42 43 public boolean at(final int pos) { 44 return (bits[pos >>> ROOM_SHIFT] & bit(pos)) != 0; 45 } 46 47 public void set(final int pos) { 48 bits[pos >>> ROOM_SHIFT] |= bit(pos); 49 } 50 51 public void clear(final int pos) { 52 bits[pos >>> ROOM_SHIFT] &= ~bit(pos); 53 } 54 55 public void clear() { 56 for (int i=0; i<BITSET_SIZE; i++) bits[i]=0; 57 } 58 59 public boolean isEmpty() { 60 for (int i=0; i<BITSET_SIZE; i++) { 61 if (bits[i] != 0) return false; 62 } 63 return true; 64 } 65 66 public void setRange(final int from, final int to) { 67 for (int i=from; i<=to && i < SINGLE_BYTE_SIZE; i++) set(i); 68 } 69 70 public void invert() { 71 for (int i=0; i<BITSET_SIZE; i++) bits[i] = ~bits[i]; 72 } 73 74 public void invertTo(final BitSet to) { 75 for (int i=0; i<BITSET_SIZE; i++) to.bits[i] = ~bits[i]; 76 } 77 78 public void and(final BitSet other) { 79 for (int i=0; i<BITSET_SIZE; i++) bits[i] &= other.bits[i]; 80 } 81 82 public void or(final BitSet other) { 83 for (int i=0; i<BITSET_SIZE; i++) bits[i] |= other.bits[i]; 84 } 85 86 public void copy(final BitSet other) { 87 for (int i=0; i<BITSET_SIZE; i++) bits[i] = other.bits[i]; 88 } 89 90 public int numOn() { 91 int num = 0; 92 for (int i=0; i<SINGLE_BYTE_SIZE; i++) { 93 if (at(i)) num++; 94 } 95 return num; 96 } 97 98 static int bit(final int pos){ 99 return 1 << (pos % SINGLE_BYTE_SIZE); 100 } 101 102 private static int log2(int n){ 103 int log = 0; 104 while ((n >>>= 1) != 0) log++; 105 return log; 106 } 107 108} 109