1 /*******************************************************************************
\r
2 * ============LICENSE_START==================================================
\r
4 * * ===========================================================================
\r
5 * * Copyright © 2017 AT&T Intellectual Property. All rights reserved.
\r
6 * * ===========================================================================
\r
7 * * Licensed under the Apache License, Version 2.0 (the "License");
\r
8 * * you may not use this file except in compliance with the License.
\r
9 * * You may obtain a copy of the License at
\r
11 * * http://www.apache.org/licenses/LICENSE-2.0
\r
13 * * Unless required by applicable law or agreed to in writing, software
\r
14 * * distributed under the License is distributed on an "AS IS" BASIS,
\r
15 * * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
\r
16 * * See the License for the specific language governing permissions and
\r
17 * * limitations under the License.
\r
18 * * ============LICENSE_END====================================================
\r
20 * * ECOMP is a trademark and service mark of AT&T Intellectual Property.
\r
22 ******************************************************************************/
\r
25 package org.onap.dmaap.datarouter.provisioning.utils;
\r
27 import java.util.ArrayList;
\r
28 import java.util.Iterator;
\r
29 import java.util.List;
\r
30 import java.util.SortedSet;
\r
31 import java.util.TreeSet;
\r
34 * This class provides operations similar to the standard Java {@link java.util.BitSet} class.
\r
35 * It is designed for bit sets where there are long runs of 1s and 0s; it is not appropriate
\r
36 * for sparsely populated bits sets. In addition, this class uses <code>long</code>s rather
\r
37 * than <code>int</code>s to represent the indices of the bits.
\r
39 * @author Robert Eby
\r
42 public class RLEBitSet {
\r
44 * Used to represent a continues set of <i>nbits</i> 1 bits starting at <i>start</i>.
\r
46 private class RLE implements Comparable<RLE> {
\r
47 private final long start;
\r
49 public RLE(long from, long nbits) {
\r
51 this.nbits = (nbits > 0) ? nbits : 0;
\r
54 * Returns the index of the first set bit in this RLE.
\r
57 public long firstBit() {
\r
61 * Returns the index of the last set bit in this RLE.
\r
64 public long lastBit() {
\r
65 return start+nbits-1;
\r
67 public boolean intersects(RLE b2) {
\r
68 if (b2.lastBit() < this.firstBit())
\r
70 if (b2.firstBit() > this.lastBit())
\r
74 public boolean isSubset(RLE b2) {
\r
75 if (firstBit() < b2.firstBit())
\r
77 if (firstBit() > b2.lastBit())
\r
79 if (lastBit() < b2.firstBit())
\r
81 if (lastBit() > b2.lastBit())
\r
85 public RLE union(RLE b2) {
\r
87 if (b1.firstBit() > b2.firstBit()) {
\r
91 long end = b1.lastBit();
\r
92 if (b2.lastBit() > b1.lastBit())
\r
94 return new RLE(b1.firstBit(), end-b1.firstBit()+1);
\r
97 * Returns the number of bits set to {@code true} in this {@code RLE}.
\r
98 * @return the number of bits set to {@code true} in this {@code RLE}.
\r
100 public int cardinality() {
\r
101 return (int) nbits;
\r
104 public int compareTo(RLE o) {
\r
105 if (this.equals(o))
\r
107 return (start < o.start) ? -1 : 1;
\r
110 public boolean equals(Object obj) {
\r
111 if (obj instanceof RLE) {
\r
113 return (start == b.start) && (nbits == b.nbits);
\r
118 public int hashCode() {
\r
119 return new Long(start ^ nbits).hashCode();
\r
122 public String toString() {
\r
123 return "["+firstBit()+".."+lastBit()+"]";
\r
126 private SortedSet<RLE> bitsets;
\r
129 * Creates a new bit set. All bits are initially <code>false</code>.
\r
131 public RLEBitSet() {
\r
132 bitsets = new TreeSet<RLE>();
\r
135 * Creates a new bit set, with bits set according to the value of <code>s</code>.
\r
136 * @param s the initialization String
\r
138 public RLEBitSet(String s) {
\r
139 bitsets = new TreeSet<RLE>();
\r
143 * Returns the "logical size" of this {@code RLEBitSet}: the index of the highest set bit
\r
144 * in the {@code RLEBitSet} plus one. Returns zero if the {@code RLEBitSet} contains no set bits.
\r
145 * @return the logical size of this {@code RLEBitSet}
\r
147 public long length() {
\r
150 return bitsets.last().lastBit()+1;
\r
153 * Returns the value of the bit with the specified index. The value is {@code true} if the bit
\r
154 * with the index bit is currently set in this BitSet; otherwise, the result is {@code false}.
\r
155 * @param bit the bit index
\r
156 * @return the value of the bit with the specified index
\r
158 public boolean get(long bit) {
\r
159 synchronized (bitsets) {
\r
160 for (RLE bs : bitsets) {
\r
161 if (bit >= bs.firstBit() && bit <= bs.lastBit())
\r
168 * Set one or more bits to true, based on the value of <code>s</code>.
\r
169 * @param s the initialization String, which consists of a comma or space separated list of
\r
170 * non-negative numbers and ranges. An individual number represents the bit index to set.
\r
171 * A range (two numbers separated by a dash) causes all bit indexes between the two numbers
\r
172 * (inclusive) to be set.
\r
173 * @exception NumberFormatException - if a number is incorrectly formatted
\r
174 * @exception IndexOutOfBoundsException - if an index is negative
\r
176 public void set(String s) throws NumberFormatException {
\r
178 if (!s.isEmpty()) {
\r
179 for (String s2 : s.split("[, \n]+")) {
\r
180 if (s2.indexOf('-') >= 0) {
\r
181 String[] pp = s2.split("-");
\r
182 long f = Long.parseLong(pp[0]);
\r
183 long t = Long.parseLong(pp[1]);
\r
186 set(Long.parseLong(s2));
\r
191 * Sets the bit at the specified index to {@code true}.
\r
192 * @param bit a bit index
\r
194 public void set(long bit) {
\r
198 * Sets the bits from the specified {@code from} (inclusive) to the
\r
199 * specified {@code to} (exclusive) to {@code true}.
\r
200 * @param from index of the first bit to be set
\r
201 * @param to index after the last bit to be set
\r
202 * @throws IndexOutOfBoundsException if {@code from} is negative,
\r
203 * or {@code to} is negative,
\r
204 * or {@code from} is larger than {@code to}
\r
206 public void set(long from, long to) {
\r
207 checkRange(from, to);
\r
208 RLE newbits = new RLE(from, to-from);
\r
209 synchronized (bitsets) {
\r
210 for (RLE bs : bitsets) {
\r
211 if (bs.intersects(newbits)) {
\r
212 if (!newbits.isSubset(bs)) {
\r
213 bitsets.remove(bs);
\r
214 bitsets.add(newbits.union(bs));
\r
220 bitsets.add(newbits);
\r
225 * Sets all of the bits in this BitSet to {@code false}.
\r
227 public void clear() {
\r
228 synchronized (bitsets) {
\r
233 * Sets the bit specified by the index to {@code false}.
\r
234 * @param bit the index of the bit to be cleared
\r
236 public void clear(long bit) {
\r
240 * Sets the bits from the specified {@code from} (inclusive) to the
\r
241 * specified {@code to} (exclusive) to {@code false}.
\r
242 * @param from index of the first bit to be cleared
\r
243 * @param to index after the last bit to be cleared
\r
244 * @throws IndexOutOfBoundsException if {@code from} is negative,
\r
245 * or {@code to} is negative,
\r
246 * or {@code from} is larger than {@code to}
\r
248 public void clear(long from, long to) {
\r
249 checkRange(from, to);
\r
250 RLE newbits = new RLE(from, to-from);
\r
251 List<RLE> newranges = new ArrayList<RLE>();
\r
252 synchronized (bitsets) {
\r
253 for (RLE bs : bitsets) {
\r
254 if (bs.intersects(newbits)) {
\r
255 // preserve the bits that are not being cleared
\r
256 long len = newbits.firstBit() - bs.firstBit();
\r
258 newranges.add(new RLE(bs.firstBit(), len));
\r
259 len = bs.lastBit() - newbits.lastBit();
\r
261 newranges.add(new RLE(newbits.lastBit()+1, len));
\r
265 if (!newranges.isEmpty()) {
\r
266 for (RLE bs : newranges) {
\r
273 /** Combine abutting RLEBitSets, and remove 0 length RLEBitSets. */
\r
274 private void coalesce() {
\r
276 synchronized (bitsets) {
\r
277 Iterator<RLE> iter = bitsets.iterator();
\r
278 while (iter.hasNext()) {
\r
279 RLE bs = iter.next();
\r
280 if (last != null && (last.lastBit()+1 == bs.firstBit())) {
\r
281 last.nbits += bs.nbits;
\r
283 } else if (bs.nbits == 0) {
\r
292 * Checks that fromIndex ... toIndex is a valid range of bit indices.
\r
294 private static void checkRange(long from, long to) {
\r
296 throw new IndexOutOfBoundsException("fromIndex < 0: " + from);
\r
298 throw new IndexOutOfBoundsException("toIndex < 0: " + to);
\r
300 throw new IndexOutOfBoundsException("fromIndex: " + from + " > toIndex: " + to);
\r
303 * Performs a logical <b>AND</b> of this target bit set with the argument bit set.
\r
304 * This bit set is modified so that each bit in it has the value {@code true} if and only if
\r
305 * it both initially had the value {@code true} and the corresponding bit in the bit set
\r
306 * argument also had the value {@code true}.
\r
307 * @param set a {@code RLEBitSet}
\r
309 public void and(RLEBitSet set) {
\r
311 synchronized (set.bitsets) {
\r
312 for (RLE bs : set.bitsets) {
\r
313 clear(last, bs.start);
\r
314 last = bs.start + bs.nbits;
\r
317 clear(last, Long.MAX_VALUE);
\r
320 * Clears all of the bits in this {@code RLEBitSet} whose corresponding bit is set in
\r
321 * the specified {@code RLEBitSet}.
\r
322 * @param set the {@code RLEBitSet} with which to mask this {@code RLEBitSet}
\r
324 public void andNot(RLEBitSet set) {
\r
325 synchronized (set.bitsets) {
\r
326 for (RLE bs : set.bitsets) {
\r
327 clear(bs.start, bs.start + bs.nbits);
\r
332 * Returns true if this {@code RLEBitSet} contains no bits that are set
\r
335 * @return boolean indicating whether this {@code BitSet} is empty
\r
337 public boolean isEmpty() {
\r
338 return bitsets.isEmpty();
\r
341 * Returns the number of bits set to {@code true} in this {@code RLEBitSet}.
\r
342 * @return the number of bits set to {@code true} in this {@code RLEBitSet}.
\r
344 public int cardinality() {
\r
346 synchronized (bitsets) {
\r
347 for (RLE bs : bitsets) {
\r
348 n += bs.cardinality();
\r
354 * Cloning this RLEBitSet produces a new RLEBitSet that is equal to it. The clone of the
\r
355 * bit set is another bit set that has exactly the same bits set to true as this bit set.
\r
356 * @return a clone of this bit set
\r
358 public Object clone() {
\r
359 RLEBitSet rv = new RLEBitSet();
\r
360 synchronized (bitsets) {
\r
361 for (RLE bs : bitsets) {
\r
362 rv.bitsets.add(new RLE(bs.start, bs.nbits));
\r
368 * Returns a string representation of this bit set, using the same notation as is required for
\r
369 * the String constructor. For every index for which this {@code RLEBitSet} contains a bit in
\r
370 * the set state, the decimal representation of that index is included in the result. Such
\r
371 * indices are listed in order from lowest to highest, separated by ",". Ranges of set bits are
\r
372 * indicated by <i>lobit</i>-<i>hibit</i>.
\r
373 * @return the String
\r
376 public String toString() {
\r
377 StringBuilder sb = new StringBuilder();
\r
378 String prefix = "";
\r
379 synchronized (bitsets) {
\r
380 for (RLE bs : bitsets) {
\r
383 long s = bs.firstBit();
\r
384 long e = bs.lastBit();
\r
387 sb.append('-').append(e);
\r
390 return sb.toString();
\r
393 * Return an Iterator which provides pairs of {@code Long}s representing the beginning and
\r
394 * ending index of a range of set bits in this {@code RLEBitSet}.
\r
395 * @return the Iterator
\r
397 public Iterator<Long[]> getRangeIterator() {
\r
398 return new Iterator<Long[]>() {
\r
399 private Iterator<RLE> i = bitsets.iterator();
\r
402 public boolean hasNext() {
\r
403 return i.hasNext();
\r
407 public Long[] next() {
\r
409 return new Long[] { bs.firstBit(), bs.lastBit() };
\r
413 public void remove() {
\r
414 throw new UnsupportedOperationException();
\r