1/* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18package tests.support; 19 20public class Support_BitSet { 21 private long[] bits; 22 23 private static final int ELM_SIZE = 64; // Size in bits of the data type 24 25 // being used in the bits array 26 27 /** 28 * Create a new BitSet with size equal to 64 bits 29 * 30 * @return The number of bits contained in this BitSet. 31 * 32 * @see #clear 33 * @see #set 34 */ 35 public Support_BitSet() { 36 this(64); 37 } 38 39 /** 40 * Create a new BitSet with size equal to nbits. If nbits is not a multiple 41 * of 64, then create a BitSet with size nbits rounded to the next closest 42 * multiple of 64. 43 * 44 * @exception NegativeArraySizeException 45 * if nbits < 0. 46 * @see #clear 47 * @see #set 48 */ 49 public Support_BitSet(int nbits) { 50 if (nbits >= 0) { 51 bits = new long[(nbits / ELM_SIZE) + (nbits % ELM_SIZE > 0 ? 1 : 0)]; 52 } else { 53 throw new NegativeArraySizeException(); 54 } 55 } 56 57 /** 58 * Clears the bit at index pos. Grows the BitSet if pos > size. 59 * 60 * @param pos 61 * int 62 * 63 * @exception IndexOutOfBoundsException 64 * when pos < 0 65 * @see #set 66 */ 67 public void clear(int pos) { 68 if (pos >= 0) { 69 if (pos < bits.length * ELM_SIZE) { 70 bits[pos / ELM_SIZE] &= ~(1L << (pos % ELM_SIZE)); 71 } else { 72 growBits(pos); // Bit is cleared for free if we have to grow 73 } 74 } else { 75 throw new IndexOutOfBoundsException("Negative index specified"); 76 } 77 } 78 79 /** 80 * Retrieve the bit at index pos. Grows the BitSet if pos > size. 81 * 82 * @param pos 83 * int 84 * @return A boolean value indicating whether the bit at pos has been set. 85 * Answers false if pos > size(). 86 * 87 * @exception IndexOutOfBoundsException 88 * when pos < 0 89 * @see #set 90 * @see #clear 91 */ 92 public boolean get(int pos) { 93 if (pos >= 0) { 94 if (pos < bits.length * ELM_SIZE) { 95 return (bits[pos / ELM_SIZE] & (1L << (pos % ELM_SIZE))) != 0; 96 } 97 return false; 98 } 99 throw new IndexOutOfBoundsException("Negative index specified"); 100 } 101 102 /** 103 * Increase the size of the internal array to accomodate pos bits. The new 104 * array max index will be a multiple of 64 105 * 106 * @param pos 107 * int The index the new array needs to be able to access 108 */ 109 private void growBits(int pos) { 110 pos++; // Inc to get correct bit count 111 long[] tempBits = new long[(pos / ELM_SIZE) 112 + (pos % ELM_SIZE > 0 ? 1 : 0)]; 113 System.arraycopy(bits, 0, tempBits, 0, bits.length); 114 bits = tempBits; 115 } 116 117 /** 118 * Sets the bit at index pos to 1. Grows the BitSet if pos > size. 119 * 120 * @param pos 121 * int 122 * 123 * @exception IndexOutOfBoundsException 124 * when pos < 0 125 * @see #clear 126 */ 127 public void set(int pos) { 128 if (pos >= 0) { 129 if (pos >= bits.length * ELM_SIZE) { 130 growBits(pos); 131 } 132 bits[pos / ELM_SIZE] |= 1L << (pos % ELM_SIZE); 133 } else { 134 throw new IndexOutOfBoundsException("Negative index specified"); 135 } 136 } 137 138 /** 139 * Clears the bit at index pos. 140 * 141 * @return The number of bits contained in this BitSet. 142 * 143 * @see #BitSet 144 * @see #clear 145 * @see #set 146 */ 147 public int size() { 148 return bits.length * ELM_SIZE; 149 } 150 151 /** 152 * Answers a string containing a concise, human-readable description of the 153 * receiver. 154 * 155 * @return A comma delimited list of the indices of all bits that are set. 156 */ 157 @Override 158 public String toString() { 159 StringBuffer sb = new StringBuffer(bits.length / 2); 160 int bitCount = 0; 161 sb.append('{'); 162 boolean comma = false; 163 for (long element : bits) { 164 if (element == 0) { 165 bitCount += ELM_SIZE; 166 continue; 167 } 168 for (int j = 0; j < ELM_SIZE; j++) { 169 if (((element & (1L << j)) != 0)) { 170 if (comma) { 171 sb.append(", "); 172 } 173 sb.append(bitCount); 174 comma = true; 175 } 176 bitCount++; 177 } 178 } 179 sb.append('}'); 180 return sb.toString(); 181 } 182 183 /** 184 * Returns the number of bits up to and including the highest bit set. 185 * 186 */ 187 public int length() { 188 int idx = bits.length - 1; 189 while (idx >= 0 && bits[idx] == 0) { 190 --idx; 191 } 192 if (idx == -1) { 193 return 0; 194 } 195 int i = ELM_SIZE - 1; 196 long val = bits[idx]; 197 while ((val & (1L << i)) == 0 && i > 0) { 198 i--; 199 } 200 return idx * ELM_SIZE + i + 1; 201 } 202} 203