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