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