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
50 public RLE(long from, long nbits) {
\r
52 this.nbits = (nbits > 0) ? nbits : 0;
\r
56 * Returns the index of the first set bit in this RLE.
\r
60 public long firstBit() {
\r
65 * Returns the index of the last set bit in this RLE.
\r
69 public long lastBit() {
\r
70 return start + nbits - 1;
\r
73 public boolean intersects(RLE b2) {
\r
74 if (b2.lastBit() < this.firstBit())
\r
76 if (b2.firstBit() > this.lastBit())
\r
81 public boolean isSubset(RLE b2) {
\r
82 if (firstBit() < b2.firstBit())
\r
84 if (firstBit() > b2.lastBit())
\r
86 if (lastBit() < b2.firstBit())
\r
88 if (lastBit() > b2.lastBit())
\r
93 public RLE union(RLE b2) {
\r
95 if (b1.firstBit() > b2.firstBit()) {
\r
99 long end = b1.lastBit();
\r
100 if (b2.lastBit() > b1.lastBit())
\r
101 end = b2.lastBit();
\r
102 return new RLE(b1.firstBit(), end - b1.firstBit() + 1);
\r
106 * Returns the number of bits set to {@code true} in this {@code RLE}.
\r
108 * @return the number of bits set to {@code true} in this {@code RLE}.
\r
110 public int cardinality() {
\r
111 return (int) nbits;
\r
115 public int compareTo(RLE o) {
\r
116 if (this.equals(o))
\r
118 return (start < o.start) ? -1 : 1;
\r
122 public boolean equals(Object obj) {
\r
123 if (obj instanceof RLE) {
\r
125 return (start == b.start) && (nbits == b.nbits);
\r
131 public int hashCode() {
\r
132 return new Long(start ^ nbits).hashCode();
\r
136 public String toString() {
\r
137 return "[" + firstBit() + ".." + lastBit() + "]";
\r
141 private SortedSet<RLE> bitsets;
\r
144 * Creates a new bit set. All bits are initially <code>false</code>.
\r
146 public RLEBitSet() {
\r
147 bitsets = new TreeSet<RLE>();
\r
151 * Creates a new bit set, with bits set according to the value of <code>s</code>.
\r
153 * @param s the initialization String
\r
155 public RLEBitSet(String s) {
\r
156 bitsets = new TreeSet<RLE>();
\r
161 * Returns the "logical size" of this {@code RLEBitSet}: the index of the highest set bit
\r
162 * in the {@code RLEBitSet} plus one. Returns zero if the {@code RLEBitSet} contains no set bits.
\r
164 * @return the logical size of this {@code RLEBitSet}
\r
166 public long length() {
\r
169 return bitsets.last().lastBit() + 1;
\r
173 * Returns the value of the bit with the specified index. The value is {@code true} if the bit
\r
174 * with the index bit is currently set in this BitSet; otherwise, the result is {@code false}.
\r
176 * @param bit the bit index
\r
177 * @return the value of the bit with the specified index
\r
179 public boolean get(long bit) {
\r
180 synchronized (bitsets) {
\r
181 for (RLE bs : bitsets) {
\r
182 if (bit >= bs.firstBit() && bit <= bs.lastBit())
\r
190 * Set one or more bits to true, based on the value of <code>s</code>.
\r
192 * @param s the initialization String, which consists of a comma or space separated list of
\r
193 * non-negative numbers and ranges. An individual number represents the bit index to set.
\r
194 * A range (two numbers separated by a dash) causes all bit indexes between the two numbers
\r
195 * (inclusive) to be set.
\r
196 * @throws NumberFormatException - if a number is incorrectly formatted
\r
197 * @throws IndexOutOfBoundsException - if an index is negative
\r
199 public void set(String s) throws NumberFormatException {
\r
201 if (!s.isEmpty()) {
\r
202 for (String s2 : s.split("[, \n]+")) {
\r
203 if (s2.indexOf('-') >= 0) {
\r
204 String[] pp = s2.split("-");
\r
205 long f = Long.parseLong(pp[0]);
\r
206 long t = Long.parseLong(pp[1]);
\r
209 set(Long.parseLong(s2));
\r
215 * Sets the bit at the specified index to {@code true}.
\r
217 * @param bit a bit index
\r
219 public void set(long bit) {
\r
224 * Sets the bits from the specified {@code from} (inclusive) to the
\r
225 * specified {@code to} (exclusive) to {@code true}.
\r
227 * @param from index of the first bit to be set
\r
228 * @param to index after the last bit to be set
\r
229 * @throws IndexOutOfBoundsException if {@code from} is negative,
\r
230 * or {@code to} is negative,
\r
231 * or {@code from} is larger than {@code to}
\r
233 public void set(long from, long to) {
\r
234 checkRange(from, to);
\r
235 RLE newbits = new RLE(from, to - from);
\r
236 synchronized (bitsets) {
\r
237 for (RLE bs : bitsets) {
\r
238 if (bs.intersects(newbits)) {
\r
239 if (!newbits.isSubset(bs)) {
\r
240 bitsets.remove(bs);
\r
241 bitsets.add(newbits.union(bs));
\r
247 bitsets.add(newbits);
\r
253 * Sets all of the bits in this BitSet to {@code false}.
\r
255 public void clear() {
\r
256 synchronized (bitsets) {
\r
262 * Sets the bit specified by the index to {@code false}.
\r
264 * @param bit the index of the bit to be cleared
\r
266 public void clear(long bit) {
\r
267 clear(bit, bit + 1);
\r
271 * Sets the bits from the specified {@code from} (inclusive) to the
\r
272 * specified {@code to} (exclusive) to {@code false}.
\r
274 * @param from index of the first bit to be cleared
\r
275 * @param to index after the last bit to be cleared
\r
276 * @throws IndexOutOfBoundsException if {@code from} is negative,
\r
277 * or {@code to} is negative,
\r
278 * or {@code from} is larger than {@code to}
\r
280 public void clear(long from, long to) {
\r
281 checkRange(from, to);
\r
282 RLE newbits = new RLE(from, to - from);
\r
283 List<RLE> newranges = new ArrayList<RLE>();
\r
284 synchronized (bitsets) {
\r
285 for (RLE bs : bitsets) {
\r
286 if (bs.intersects(newbits)) {
\r
287 // preserve the bits that are not being cleared
\r
288 long len = newbits.firstBit() - bs.firstBit();
\r
290 newranges.add(new RLE(bs.firstBit(), len));
\r
291 len = bs.lastBit() - newbits.lastBit();
\r
293 newranges.add(new RLE(newbits.lastBit() + 1, len));
\r
297 if (!newranges.isEmpty()) {
\r
298 for (RLE bs : newranges) {
\r
307 * Combine abutting RLEBitSets, and remove 0 length RLEBitSets.
\r
309 private void coalesce() {
\r
311 synchronized (bitsets) {
\r
312 Iterator<RLE> iter = bitsets.iterator();
\r
313 while (iter.hasNext()) {
\r
314 RLE bs = iter.next();
\r
315 if (last != null && (last.lastBit() + 1 == bs.firstBit())) {
\r
316 last.nbits += bs.nbits;
\r
318 } else if (bs.nbits == 0) {
\r
328 * Checks that fromIndex ... toIndex is a valid range of bit indices.
\r
330 private static void checkRange(long from, long to) {
\r
332 throw new IndexOutOfBoundsException("fromIndex < 0: " + from);
\r
334 throw new IndexOutOfBoundsException("toIndex < 0: " + to);
\r
336 throw new IndexOutOfBoundsException("fromIndex: " + from + " > toIndex: " + to);
\r
340 * Performs a logical <b>AND</b> of this target bit set with the argument bit set.
\r
341 * This bit set is modified so that each bit in it has the value {@code true} if and only if
\r
342 * it both initially had the value {@code true} and the corresponding bit in the bit set
\r
343 * argument also had the value {@code true}.
\r
345 * @param set a {@code RLEBitSet}
\r
347 public void and(RLEBitSet set) {
\r
349 synchronized (set.bitsets) {
\r
350 for (RLE bs : set.bitsets) {
\r
351 clear(last, bs.start);
\r
352 last = bs.start + bs.nbits;
\r
355 clear(last, Long.MAX_VALUE);
\r
359 * Clears all of the bits in this {@code RLEBitSet} whose corresponding bit is set in
\r
360 * the specified {@code RLEBitSet}.
\r
362 * @param set the {@code RLEBitSet} with which to mask this {@code RLEBitSet}
\r
364 public void andNot(RLEBitSet set) {
\r
365 synchronized (set.bitsets) {
\r
366 for (RLE bs : set.bitsets) {
\r
367 clear(bs.start, bs.start + bs.nbits);
\r
373 * Returns true if this {@code RLEBitSet} contains no bits that are set
\r
376 * @return boolean indicating whether this {@code BitSet} is empty
\r
378 public boolean isEmpty() {
\r
379 return bitsets.isEmpty();
\r
383 * Returns the number of bits set to {@code true} in this {@code RLEBitSet}.
\r
385 * @return the number of bits set to {@code true} in this {@code RLEBitSet}.
\r
387 public int cardinality() {
\r
389 synchronized (bitsets) {
\r
390 for (RLE bs : bitsets) {
\r
391 n += bs.cardinality();
\r
398 * Cloning this RLEBitSet produces a new RLEBitSet that is equal to it. The clone of the
\r
399 * bit set is another bit set that has exactly the same bits set to true as this bit set.
\r
401 * @return a clone of this bit set
\r
403 public Object clone() {
\r
404 RLEBitSet rv = new RLEBitSet();
\r
405 synchronized (bitsets) {
\r
406 for (RLE bs : bitsets) {
\r
407 rv.bitsets.add(new RLE(bs.start, bs.nbits));
\r
414 * Returns a string representation of this bit set, using the same notation as is required for
\r
415 * the String constructor. For every index for which this {@code RLEBitSet} contains a bit in
\r
416 * the set state, the decimal representation of that index is included in the result. Such
\r
417 * indices are listed in order from lowest to highest, separated by ",". Ranges of set bits are
\r
418 * indicated by <i>lobit</i>-<i>hibit</i>.
\r
420 * @return the String
\r
423 public String toString() {
\r
424 StringBuilder sb = new StringBuilder();
\r
425 String prefix = "";
\r
426 synchronized (bitsets) {
\r
427 for (RLE bs : bitsets) {
\r
430 long s = bs.firstBit();
\r
431 long e = bs.lastBit();
\r
434 sb.append('-').append(e);
\r
437 return sb.toString();
\r
441 * Return an Iterator which provides pairs of {@code Long}s representing the beginning and
\r
442 * ending index of a range of set bits in this {@code RLEBitSet}.
\r
444 * @return the Iterator
\r
446 public Iterator<Long[]> getRangeIterator() {
\r
447 return new Iterator<Long[]>() {
\r
448 private Iterator<RLE> i = bitsets.iterator();
\r
451 public boolean hasNext() {
\r
452 return i.hasNext();
\r
456 public Long[] next() {
\r
458 return new Long[]{bs.firstBit(), bs.lastBit()};
\r
462 public void remove() {
\r
463 throw new UnsupportedOperationException();
\r