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 package org.apache.commons.numbers.arrays;
18
19 /**
20 * An {@link UpdatingInterval} backed by a fixed size of bits.
21 *
22 * <p>This is a specialised class to implement a reduced API similar to a
23 * {@link java.util.BitSet}. It uses no bounds range checks and supports only
24 * the methods required to implement the {@link UpdatingInterval} API.
25 *
26 * <p>An offset is supported to allow the fixed size to cover a range of indices starting
27 * above 0 with the most efficient usage of storage.
28 *
29 * <p>See the BloomFilter code in Commons Collections for use of long[] data to store
30 * bits.
31 *
32 * @since 1.2
33 */
34 final class BitIndexUpdatingInterval implements UpdatingInterval {
35 /** All 64-bits bits set. */
36 private static final long LONG_MASK = -1L;
37 /** A bit shift to apply to an integer to divided by 64 (2^6). */
38 private static final int DIVIDE_BY_64 = 6;
39
40 /** Bit indexes. */
41 private final long[] data;
42
43 /** Index offset. */
44 private final int offset;
45 /** Left bound of the support. */
46 private int left;
47 /** Right bound of the support. */
48 private int right;
49
50 /**
51 * Create an instance to store indices within the range {@code [left, right]}.
52 * The range is not validated.
53 *
54 * @param left Lower bound (inclusive).
55 * @param right Upper bound (inclusive).
56 */
57 BitIndexUpdatingInterval(int left, int right) {
58 this.offset = left;
59 this.left = left;
60 this.right = right;
61 // Allocate storage to store index==right
62 // Note: This may allow directly writing to index > right if there
63 // is extra capacity.
64 data = new long[getLongIndex(right - offset) + 1];
65 }
66
67 /**
68 * Create an instance with the range {@code [left, right]} and reusing the provided
69 * index {@code data}.
70 *
71 * @param data Data.
72 * @param offset Index offset.
73 * @param left Lower bound (inclusive).
74 * @param right Upper bound (inclusive).
75 */
76 private BitIndexUpdatingInterval(long[] data, int offset, int left, int right) {
77 this.data = data;
78 this.offset = offset;
79 this.left = left;
80 this.right = right;
81 }
82
83 /**
84 * Gets the filter index for the specified bit index assuming the filter is using
85 * 64-bit longs to store bits starting at index 0.
86 *
87 * <p>The index is assumed to be positive. For a positive index the result will match
88 * {@code bitIndex / 64}.</p>
89 *
90 * <p><em>The divide is performed using bit shifts. If the input is negative the
91 * behavior is not defined.</em></p>
92 *
93 * @param bitIndex the bit index (assumed to be positive)
94 * @return the index of the bit map in an array of bit maps.
95 */
96 private static int getLongIndex(final int bitIndex) {
97 // An integer divide by 64 is equivalent to a shift of 6 bits if the integer is
98 // positive.
99 // We do not explicitly check for a negative here. Instead we use a
100 // signed shift. Any negative index will produce a negative value
101 // by sign-extension and if used as an index into an array it will throw an
102 // exception.
103 return bitIndex >> DIVIDE_BY_64;
104 }
105
106 /**
107 * Gets the filter bit mask for the specified bit index assuming the filter is using
108 * 64-bit longs to store bits starting at index 0. The returned value is a
109 * {@code long} with only 1 bit set.
110 *
111 * <p>The index is assumed to be positive. For a positive index the result will match
112 * {@code 1L << (bitIndex % 64)}.</p>
113 *
114 * <p><em>If the input is negative the behavior is not defined.</em></p>
115 *
116 * @param bitIndex the bit index (assumed to be positive)
117 * @return the filter bit
118 */
119 private static long getLongBit(final int bitIndex) {
120 // Bit shifts only use the first 6 bits. Thus it is not necessary to mask this
121 // using 0x3f (63) or compute bitIndex % 64.
122 // Note: If the index is negative the shift will be (64 - (bitIndex & 0x3f)) and
123 // this will identify an incorrect bit.
124 return 1L << bitIndex;
125 }
126
127 /**
128 * Sets the bit at the specified index to {@code true}.
129 *
130 * <p>Warning: This has no range checks.
131 *
132 * @param bitIndex the bit index (assumed to be positive)
133 */
134 void set(int bitIndex) {
135 // WARNING: No range checks !!!
136 final int index = bitIndex - offset;
137 final int i = getLongIndex(index);
138 final long m = getLongBit(index);
139 data[i] |= m;
140 }
141
142 /**
143 * Returns the index of the first bit that is set to {@code true} that occurs on or
144 * after the specified starting index.
145 *
146 * <p>Warning: This has no range checks. It is assumed that {@code left <= k <= right},
147 * that is there is a set bit on or after {@code k}.
148 *
149 * @param k Index to start checking from (inclusive).
150 * @return the index of the next set bit
151 */
152 private int nextIndex(int k) {
153 // left <= k <= right
154
155 final int index = k - offset;
156 int i = getLongIndex(index);
157
158 // Mask bits after the bit index
159 // mask = 11111000 = -1L << (index % 64)
160 long bits = data[i] & (LONG_MASK << index);
161 for (;;) {
162 if (bits != 0) {
163 //(i+1) i
164 // | index |
165 // | | |
166 // 0 001010000
167 return i * Long.SIZE + Long.numberOfTrailingZeros(bits) + offset;
168 }
169 // Unsupported: the interval should contain k
170 //if (++i == data.length)
171 // return right + 1
172 bits = data[++i];
173 }
174 }
175
176 /**
177 * Returns the index of the first bit that is set to {@code true} that occurs on or
178 * before the specified starting index.
179 *
180 * <p>Warning: This has no range checks. It is assumed that {@code left <= k <= right},
181 * that is there is a set bit on or before {@code k}.
182 *
183 * @param k Index to start checking from (inclusive).
184 * @return the index of the previous set bit
185 */
186 private int previousIndex(int k) {
187 // left <= k <= right
188
189 final int index = k - offset;
190 int i = getLongIndex(index);
191
192 // Mask bits before the bit index
193 // mask = 00011111 = -1L >>> (64 - ((index + 1) % 64))
194 long bits = data[i] & (LONG_MASK >>> -(index + 1));
195 for (;;) {
196 if (bits != 0) {
197 //(i+1) i
198 // | index |
199 // | | |
200 // 0 001010000
201 return (i + 1) * Long.SIZE - Long.numberOfLeadingZeros(bits) - 1 + offset;
202 }
203 // Unsupported: the interval should contain k
204 //if (i == 0)
205 // return left - 1
206 bits = data[--i];
207 }
208 }
209
210 @Override
211 public int left() {
212 return left;
213 }
214
215 @Override
216 public int right() {
217 return right;
218 }
219
220 @Override
221 public int updateLeft(int k) {
222 // Assume left < k= < right
223 return left = nextIndex(k);
224 }
225
226 @Override
227 public int updateRight(int k) {
228 // Assume left <= k < right
229 return right = previousIndex(k);
230 }
231
232 @Override
233 public UpdatingInterval splitLeft(int ka, int kb) {
234 // Assume left < ka <= kb < right
235 final int lower = left;
236 left = nextIndex(kb + 1);
237 return new BitIndexUpdatingInterval(data, offset, lower, previousIndex(ka - 1));
238 }
239 }