datarouter-prov/src/main/java/org/onap/dmaap/datarouter/provisioning/utils/RLEBitSet.java

   1 /*******************************************************************************\r
   2  * ============LICENSE_START==================================================\r
   3  * * org.onap.dmaap\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
  10  * *\r
  11  *  *      http://www.apache.org/licenses/LICENSE-2.0\r
  12  * *\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
  19  * *\r
  20  * * ECOMP is a trademark and service mark of AT&T Intellectual Property.\r
  21  * *\r
  22  ******************************************************************************/\r
  23 \r
  24 \r
  25 package org.onap.dmaap.datarouter.provisioning.utils;\r
  26 \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
  32 \r
  33 /**\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
  38  *\r
  39  * @author Robert Eby\r
  40  * @version $Id$\r
  41  */\r
  42 public class RLEBitSet {\r
  43     /**\r
  44      * Used to represent a continues set of <i>nbits</i> 1 bits starting at <i>start</i>.\r
  45      */\r
  46     private class RLE implements Comparable<RLE> {\r
  47         private final long start;\r
  48         private long nbits;\r
  49 \r
  50         public RLE(long from, long nbits) {\r
  51             this.start = from;\r
  52             this.nbits = (nbits > 0) ? nbits : 0;\r
  53         }\r
  54 \r
  55         /**\r
  56          * Returns the index of the first set bit in this RLE.\r
  57          *\r
  58          * @return the index\r
  59          */\r
  60         public long firstBit() {\r
  61             return start;\r
  62         }\r
  63 \r
  64         /**\r
  65          * Returns the index of the last set bit in this RLE.\r
  66          *\r
  67          * @return the index\r
  68          */\r
  69         public long lastBit() {\r
  70             return start + nbits - 1;\r
  71         }\r
  72 \r
  73 \r
  74         public boolean intersects(RLE b2) {\r
  75             if (b2.lastBit() < this.firstBit()) {\r
  76                 return false;\r
  77             }\r
  78             if (b2.firstBit() > this.lastBit()) {\r
  79                 return false;\r
  80             }\r
  81             return true;\r
  82         }\r
  83 \r
  84         public boolean isSubset(RLE b2) {\r
  85             if (firstBit() < b2.firstBit()) {\r
  86                 return false;\r
  87             }\r
  88             if (firstBit() > b2.lastBit()) {\r
  89                 return false;\r
  90             }\r
  91             if (lastBit() < b2.firstBit()) {\r
  92                 return false;\r
  93             }\r
  94             if (lastBit() > b2.lastBit()) {\r
  95                 return false;\r
  96             }\r
  97             return true;\r
  98         }\r
  99 \r
 100         public RLE union(RLE b2) {\r
 101             RLE b1 = this;\r
 102             if (b1.firstBit() > b2.firstBit()) {\r
 103                 b1 = b2;\r
 104                 b2 = this;\r
 105             }\r
 106             long end = b1.lastBit();\r
 107             if (b2.lastBit() > b1.lastBit()) {\r
 108                 end = b2.lastBit();\r
 109             }\r
 110             return new RLE(b1.firstBit(), end - b1.firstBit() + 1);\r
 111         }\r
 112 \r
 113         /**\r
 114          * Returns the number of bits set to {@code true} in this {@code RLE}.\r
 115          *\r
 116          * @return the number of bits set to {@code true} in this {@code RLE}.\r
 117          */\r
 118         public int cardinality() {\r
 119             return (int) nbits;\r
 120         }\r
 121 \r
 122         @Override\r
 123         public int compareTo(RLE rle) {\r
 124             if (this.equals(rle)) {\r
 125                 return 0;\r
 126             }\r
 127             return (start < rle.start) ? -1 : 1;\r
 128         }\r
 129 \r
 130         @Override\r
 131         public boolean equals(Object obj) {\r
 132             if (obj instanceof RLE) {\r
 133                 RLE rle = (RLE) obj;\r
 134                 return (start == rle.start) && (nbits == rle.nbits);\r
 135             }\r
 136             return false;\r
 137         }\r
 138 \r
 139         @Override\r
 140         public int hashCode() {\r
 141             return Long.valueOf(start ^ nbits).hashCode();\r
 142         }\r
 143 \r
 144         @Override\r
 145         public String toString() {\r
 146             return "[" + firstBit() + ".." + lastBit() + "]";\r
 147         }\r
 148     }\r
 149 \r
 150     private SortedSet<RLE> bitsets;\r
 151 \r
 152     /**\r
 153      * Creates a new bit set. All bits are initially <code>false</code>.\r
 154      */\r
 155     public RLEBitSet() {\r
 156         bitsets = new TreeSet<>();\r
 157     }\r
 158 \r
 159     /**\r
 160      * Creates a new bit set, with bits set according to the value of <code>s</code>.\r
 161      *\r
 162      * @param str the initialization String\r
 163      */\r
 164     public RLEBitSet(String str) {\r
 165         bitsets = new TreeSet<>();\r
 166         set(str);\r
 167     }\r
 168 \r
 169     /**\r
 170      * Returns the "logical size" of this {@code RLEBitSet}: the index of the highest set bit\r
 171      * in the {@code RLEBitSet} plus one. Returns zero if the {@code RLEBitSet} contains no set bits.\r
 172      *\r
 173      * @return the logical size of this {@code RLEBitSet}\r
 174      */\r
 175     public long length() {\r
 176         if (isEmpty()) {\r
 177             return 0;\r
 178         }\r
 179         return bitsets.last().lastBit() + 1;\r
 180     }\r
 181 \r
 182     /**\r
 183      * Returns the value of the bit with the specified index. The value is {@code true} if the bit\r
 184      * with the index bit is currently set in this BitSet; otherwise, the result is {@code false}.\r
 185      *\r
 186      * @param bit the bit index\r
 187      * @return the value of the bit with the specified index\r
 188      */\r
 189     public boolean get(long bit) {\r
 190         synchronized (bitsets) {\r
 191             for (RLE bs : bitsets) {\r
 192                 if (bit >= bs.firstBit() && bit <= bs.lastBit()) {\r
 193                     return true;\r
 194                 }\r
 195             }\r
 196         }\r
 197         return false;\r
 198     }\r
 199 \r
 200     /**\r
 201      * Set one or more bits to true, based on the value of <code>s</code>.\r
 202      *\r
 203      * @param str the initialization String, which consists of a comma or space separated list of\r
 204      *          non-negative numbers and ranges.  An individual number represents the bit index to set.\r
 205      *          A range (two numbers separated by a dash) causes all bit indexes between the two numbers\r
 206      *          (inclusive) to be set.\r
 207      * @throws NumberFormatException     - if a number is incorrectly formatted\r
 208      * @throws IndexOutOfBoundsException - if an index is negative\r
 209      */\r
 210     public void set(String str) {\r
 211         str = str.trim();\r
 212         if (!str.isEmpty()) {\r
 213             for (String s2 : str.split("[, \n]+")) {\r
 214                 if (s2.indexOf('-') >= 0) {\r
 215                     String[] pp = s2.split("-");\r
 216                     long l1 = Long.parseLong(pp[0]);\r
 217                     long l2 = Long.parseLong(pp[1]);\r
 218                     set(l1, l2 + 1);\r
 219                 } else {\r
 220                     set(Long.parseLong(s2));\r
 221                 }\r
 222             }\r
 223         }\r
 224     }\r
 225 \r
 226     /**\r
 227      * Sets the bit at the specified index to {@code true}.\r
 228      *\r
 229      * @param bit a bit index\r
 230      */\r
 231     public void set(long bit) {\r
 232         set(bit, bit + 1);\r
 233     }\r
 234 \r
 235     /**\r
 236      * Sets the bits from the specified {@code from} (inclusive) to the\r
 237      * specified {@code to} (exclusive) to {@code true}.\r
 238      *\r
 239      * @param from index of the first bit to be set\r
 240      * @param to   index after the last bit to be set\r
 241      * @throws IndexOutOfBoundsException if {@code from} is negative,\r
 242      *                                   or {@code to} is negative,\r
 243      *                                   or {@code from} is larger than {@code to}\r
 244      */\r
 245     public void set(long from, long to) {\r
 246         checkRange(from, to);\r
 247         RLE newbits = new RLE(from, to - from);\r
 248         synchronized (bitsets) {\r
 249             for (RLE bs : bitsets) {\r
 250                 if (bs.intersects(newbits)) {\r
 251                     if (!newbits.isSubset(bs)) {\r
 252                         bitsets.remove(bs);\r
 253                         bitsets.add(newbits.union(bs));\r
 254                         coalesce();\r
 255                     }\r
 256                     return;\r
 257                 }\r
 258             }\r
 259             bitsets.add(newbits);\r
 260         }\r
 261         coalesce();\r
 262     }\r
 263 \r
 264     /**\r
 265      * Sets all of the bits in this BitSet to {@code false}.\r
 266      */\r
 267     public void clear() {\r
 268         synchronized (bitsets) {\r
 269             bitsets.clear();\r
 270         }\r
 271     }\r
 272 \r
 273     /**\r
 274      * Sets the bit specified by the index to {@code false}.\r
 275      *\r
 276      * @param bit the index of the bit to be cleared\r
 277      */\r
 278     public void clear(long bit) {\r
 279         clear(bit, bit + 1);\r
 280     }\r
 281 \r
 282     /**\r
 283      * Sets the bits from the specified {@code from} (inclusive) to the\r
 284      * specified {@code to} (exclusive) to {@code false}.\r
 285      *\r
 286      * @param from index of the first bit to be cleared\r
 287      * @param to   index after the last bit to be cleared\r
 288      * @throws IndexOutOfBoundsException if {@code from} is negative,\r
 289      *                                   or {@code to} is negative,\r
 290      *                                   or {@code from} is larger than {@code to}\r
 291      */\r
 292     public void clear(long from, long to) {\r
 293         checkRange(from, to);\r
 294         RLE newbits = new RLE(from, to - from);\r
 295         List<RLE> newranges = new ArrayList<>();\r
 296         synchronized (bitsets) {\r
 297             for (RLE bs : bitsets) {\r
 298                 if (bs.intersects(newbits)) {\r
 299                     // preserve the bits that are not being cleared\r
 300                     long len = newbits.firstBit() - bs.firstBit();\r
 301                     if (len > 0) {\r
 302                         newranges.add(new RLE(bs.firstBit(), len));\r
 303                     }\r
 304                     len = bs.lastBit() - newbits.lastBit();\r
 305                     if (len > 0) {\r
 306                         newranges.add(new RLE(newbits.lastBit() + 1, len));\r
 307                     }\r
 308                     bs.nbits = 0;\r
 309                 }\r
 310             }\r
 311             if (!newranges.isEmpty()) {\r
 312                 for (RLE bs : newranges) {\r
 313                     bitsets.add(bs);\r
 314                 }\r
 315             }\r
 316         }\r
 317         coalesce();\r
 318     }\r
 319 \r
 320     /**\r
 321      * Combine abutting RLEBitSets, and remove 0 length RLEBitSets.\r
 322      */\r
 323     private void coalesce() {\r
 324         RLE last = null;\r
 325         synchronized (bitsets) {\r
 326             Iterator<RLE> iter = bitsets.iterator();\r
 327             while (iter.hasNext()) {\r
 328                 RLE bs = iter.next();\r
 329                 if (last != null && (last.lastBit() + 1 == bs.firstBit())) {\r
 330                     last.nbits += bs.nbits;\r
 331                     iter.remove();\r
 332                 } else if (bs.nbits == 0) {\r
 333                     iter.remove();\r
 334                 } else {\r
 335                     last = bs;\r
 336                 }\r
 337             }\r
 338         }\r
 339     }\r
 340 \r
 341     /**\r
 342      * Checks that fromIndex ... toIndex is a valid range of bit indices.\r
 343      */\r
 344     private static void checkRange(long from, long to) {\r
 345         if (from < 0) {\r
 346             throw new IndexOutOfBoundsException("fromIndex < 0: " + from);\r
 347         }\r
 348         if (to < 0) {\r
 349             throw new IndexOutOfBoundsException("toIndex < 0: " + to);\r
 350         }\r
 351         if (from > to) {\r
 352             throw new IndexOutOfBoundsException("fromIndex: " + from + " > toIndex: " + to);\r
 353         }\r
 354     }\r
 355 \r
 356     /**\r
 357      * Performs a logical <b>AND</b> of this target bit set with the argument bit set.\r
 358      * This bit set is modified so that each bit in it has the value {@code true} if and only if\r
 359      * it both initially had the value {@code true} and the corresponding bit in the bit set\r
 360      * argument also had the value {@code true}.\r
 361      *\r
 362      * @param set a {@code RLEBitSet}\r
 363      */\r
 364     public void and(RLEBitSet set) {\r
 365         long last = 0;\r
 366         synchronized (set.bitsets) {\r
 367             for (RLE bs : set.bitsets) {\r
 368                 clear(last, bs.start);\r
 369                 last = bs.start + bs.nbits;\r
 370             }\r
 371         }\r
 372         clear(last, Long.MAX_VALUE);\r
 373     }\r
 374 \r
 375     /**\r
 376      * Clears all of the bits in this {@code RLEBitSet} whose corresponding bit is set in\r
 377      * the specified {@code RLEBitSet}.\r
 378      *\r
 379      * @param set the {@code RLEBitSet} with which to mask this {@code RLEBitSet}\r
 380      */\r
 381     public void andNot(RLEBitSet set) {\r
 382         synchronized (set.bitsets) {\r
 383             for (RLE bs : set.bitsets) {\r
 384                 clear(bs.start, bs.start + bs.nbits);\r
 385             }\r
 386         }\r
 387     }\r
 388 \r
 389     /**\r
 390      * Returns true if this {@code RLEBitSet} contains no bits that are set\r
 391      * to {@code true}.\r
 392      *\r
 393      * @return boolean indicating whether this {@code BitSet} is empty\r
 394      */\r
 395     public boolean isEmpty() {\r
 396         return bitsets.isEmpty();\r
 397     }\r
 398 \r
 399     /**\r
 400      * Returns the number of bits set to {@code true} in this {@code RLEBitSet}.\r
 401      *\r
 402      * @return the number of bits set to {@code true} in this {@code RLEBitSet}.\r
 403      */\r
 404     public int cardinality() {\r
 405         int trueCount = 0;\r
 406         synchronized (bitsets) {\r
 407             for (RLE bs : bitsets) {\r
 408                 trueCount += bs.cardinality();\r
 409             }\r
 410         }\r
 411         return trueCount;\r
 412     }\r
 413 \r
 414     /**\r
 415      * Cloning this RLEBitSet produces a new RLEBitSet that is equal to it. The clone of the\r
 416      * bit set is another bit set that has exactly the same bits set to true as this bit set.\r
 417      *\r
 418      * @return a clone of this bit set\r
 419      */\r
 420     public Object clone() {\r
 421         RLEBitSet rv = new RLEBitSet();\r
 422         synchronized (bitsets) {\r
 423             for (RLE bs : bitsets) {\r
 424                 rv.bitsets.add(new RLE(bs.start, bs.nbits));\r
 425             }\r
 426         }\r
 427         return rv;\r
 428     }\r
 429 \r
 430     /**\r
 431      * Returns a string representation of this bit set, using the same notation as is required for\r
 432      * the String constructor. For every index for which this {@code RLEBitSet} contains a bit in\r
 433      * the set state, the decimal representation of that index is included in the result. Such\r
 434      * indices are listed in order from lowest to highest, separated by ",". Ranges of set bits are\r
 435      * indicated by <i>lobit</i>-<i>hibit</i>.\r
 436      *\r
 437      * @return the String\r
 438      */\r
 439     @Override\r
 440     public String toString() {\r
 441         StringBuilder sb = new StringBuilder();\r
 442         String prefix = "";\r
 443         synchronized (bitsets) {\r
 444             for (RLE bs : bitsets) {\r
 445                 sb.append(prefix);\r
 446                 prefix = ",";\r
 447                 long bit1 = bs.firstBit();\r
 448                 long bit2 = bs.lastBit();\r
 449                 sb.append(bit1);\r
 450                 if (bit1 != bit2) {\r
 451                     sb.append('-').append(bit2);\r
 452                 }\r
 453             }\r
 454         }\r
 455         return sb.toString();\r
 456     }\r
 457 \r
 458     /**\r
 459      * Return an Iterator which provides pairs of {@code Long}s representing the beginning and\r
 460      * ending index of a range of set bits in this {@code RLEBitSet}.\r
 461      *\r
 462      * @return the Iterator\r
 463      */\r
 464     public Iterator<Long[]> getRangeIterator() {\r
 465         return new Iterator<Long[]>() {\r
 466             private Iterator<RLE> iterator = bitsets.iterator();\r
 467 \r
 468             @Override\r
 469             public boolean hasNext() {\r
 470                 return iterator.hasNext();\r
 471             }\r
 472 \r
 473             @Override\r
 474             public Long[] next() {\r
 475                 RLE bs = iterator.next();\r
 476                 return new Long[]{bs.firstBit(), bs.lastBit()};\r
 477             }\r
 478 \r
 479             @Override\r
 480             public void remove() {\r
 481                 throw new UnsupportedOperationException();\r
 482             }\r
 483         };\r
 484     }\r
 485 }\r