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
22@SuppressWarnings("javadoc")
23public final class BitSet {
24    static final int BITS_PER_BYTE = 8;
25    public static final int SINGLE_BYTE_SIZE = (1 << BITS_PER_BYTE);
26    private static final int BITS_IN_ROOM = 4 * BITS_PER_BYTE;
27    static final int BITSET_SIZE = (SINGLE_BYTE_SIZE / BITS_IN_ROOM);
28    static final int ROOM_SHIFT = log2(BITS_IN_ROOM);
29
30    final int[] bits = new int[BITSET_SIZE];
31
32    private static final int BITS_TO_STRING_WRAP = 4;
33    @Override
34    public String toString() {
35        final StringBuilder buffer = new StringBuilder();
36        buffer.append("BitSet");
37        for (int i=0; i<SINGLE_BYTE_SIZE; i++) {
38            if ((i % (SINGLE_BYTE_SIZE / BITS_TO_STRING_WRAP)) == 0) {
39                buffer.append("\n  ");
40            }
41            buffer.append(at(i) ? "1" : "0");
42        }
43        return buffer.toString();
44    }
45
46    public boolean at(final int pos) {
47        return (bits[pos >>> ROOM_SHIFT] & bit(pos)) != 0;
48    }
49
50    public void set(final int pos) {
51        bits[pos >>> ROOM_SHIFT] |= bit(pos);
52    }
53
54    public void clear(final int pos) {
55        bits[pos >>> ROOM_SHIFT] &= ~bit(pos);
56    }
57
58    public void clear() {
59        for (int i=0; i<BITSET_SIZE; i++) {
60            bits[i]=0;
61        }
62    }
63
64    public boolean isEmpty() {
65        for (int i=0; i<BITSET_SIZE; i++) {
66            if (bits[i] != 0) {
67                return false;
68            }
69        }
70        return true;
71    }
72
73    public void setRange(final int from, final int to) {
74        for (int i=from; i<=to && i < SINGLE_BYTE_SIZE; i++) {
75            set(i);
76        }
77    }
78
79    public void invert() {
80        for (int i=0; i<BITSET_SIZE; i++) {
81            bits[i] = ~bits[i];
82        }
83    }
84
85    public void invertTo(final BitSet to) {
86        for (int i=0; i<BITSET_SIZE; i++) {
87            to.bits[i] = ~bits[i];
88        }
89    }
90
91    public void and(final BitSet other) {
92        for (int i=0; i<BITSET_SIZE; i++) {
93            bits[i] &= other.bits[i];
94        }
95    }
96
97    public void or(final BitSet other) {
98        for (int i=0; i<BITSET_SIZE; i++) {
99            bits[i] |= other.bits[i];
100        }
101    }
102
103    public void copy(final BitSet other) {
104        System.arraycopy(other.bits, 0, bits, 0, BITSET_SIZE);
105    }
106
107    public int numOn() {
108        int num = 0;
109        for (int i=0; i<SINGLE_BYTE_SIZE; i++) {
110            if (at(i)) {
111                num++;
112            }
113        }
114        return num;
115    }
116
117    static int bit(final int pos){
118        return 1 << (pos % SINGLE_BYTE_SIZE);
119    }
120
121    private static int log2(final int np) {
122        int log = 0;
123        int n = np;
124        while ((n >>>= 1) != 0) {
125            log++;
126        }
127        return log;
128    }
129
130}
131