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         public boolean intersects(RLE b2) {\r
  74             if (b2.lastBit() < this.firstBit())\r
  75                 return false;\r
  76             if (b2.firstBit() > this.lastBit())\r
  77                 return false;\r
  78             return true;\r
  79         }\r
  80 \r
  81         public boolean isSubset(RLE b2) {\r
  82             if (firstBit() < b2.firstBit())\r
  83                 return false;\r
  84             if (firstBit() > b2.lastBit())\r
  85                 return false;\r
  86             if (lastBit() < b2.firstBit())\r
  87                 return false;\r
  88             if (lastBit() > b2.lastBit())\r
  89                 return false;\r
  90             return true;\r
  91         }\r
  92 \r
  93         public RLE union(RLE b2) {\r
  94             RLE b1 = this;\r
  95             if (b1.firstBit() > b2.firstBit()) {\r
  96                 b1 = b2;\r
  97                 b2 = this;\r
  98             }\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
 103         }\r
 104 \r
 105         /**\r
 106          * Returns the number of bits set to {@code true} in this {@code RLE}.\r
 107          *\r
 108          * @return the number of bits set to {@code true} in this {@code RLE}.\r
 109          */\r
 110         public int cardinality() {\r
 111             return (int) nbits;\r
 112         }\r
 113 \r
 114         @Override\r
 115         public int compareTo(RLE o) {\r
 116             if (this.equals(o))\r
 117                 return 0;\r
 118             return (start < o.start) ? -1 : 1;\r
 119         }\r
 120 \r
 121         @Override\r
 122         public boolean equals(Object obj) {\r
 123             if (obj instanceof RLE) {\r
 124                 RLE b = (RLE) obj;\r
 125                 return (start == b.start) && (nbits == b.nbits);\r
 126             }\r
 127             return false;\r
 128         }\r
 129 \r
 130         @Override\r
 131         public int hashCode() {\r
 132             return Long.valueOf(start ^ nbits).hashCode();\r
 133         }\r
 134 \r
 135         @Override\r
 136         public String toString() {\r
 137             return "[" + firstBit() + ".." + lastBit() + "]";\r
 138         }\r
 139     }\r
 140 \r
 141     private SortedSet<RLE> bitsets;\r
 142 \r
 143     /**\r
 144      * Creates a new bit set. All bits are initially <code>false</code>.\r
 145      */\r
 146     public RLEBitSet() {\r
 147         bitsets = new TreeSet<>();\r
 148     }\r
 149 \r
 150     /**\r
 151      * Creates a new bit set, with bits set according to the value of <code>s</code>.\r
 152      *\r
 153      * @param s the initialization String\r
 154      */\r
 155     public RLEBitSet(String s) {\r
 156         bitsets = new TreeSet<>();\r
 157         set(s);\r
 158     }\r
 159 \r
 160     /**\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
 163      *\r
 164      * @return the logical size of this {@code RLEBitSet}\r
 165      */\r
 166     public long length() {\r
 167         if (isEmpty())\r
 168             return 0;\r
 169         return bitsets.last().lastBit() + 1;\r
 170     }\r
 171 \r
 172     /**\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
 175      *\r
 176      * @param bit the bit index\r
 177      * @return the value of the bit with the specified index\r
 178      */\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
 183                     return true;\r
 184             }\r
 185         }\r
 186         return false;\r
 187     }\r
 188 \r
 189     /**\r
 190      * Set one or more bits to true, based on the value of <code>s</code>.\r
 191      *\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
 198      */\r
 199     public void set(String s) {\r
 200         s = s.trim();\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
 207                     set(f, t + 1);\r
 208                 } else\r
 209                     set(Long.parseLong(s2));\r
 210             }\r
 211         }\r
 212     }\r
 213 \r
 214     /**\r
 215      * Sets the bit at the specified index to {@code true}.\r
 216      *\r
 217      * @param bit a bit index\r
 218      */\r
 219     public void set(long bit) {\r
 220         set(bit, bit + 1);\r
 221     }\r
 222 \r
 223     /**\r
 224      * Sets the bits from the specified {@code from} (inclusive) to the\r
 225      * specified {@code to} (exclusive) to {@code true}.\r
 226      *\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
 232      */\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
 242                         coalesce();\r
 243                     }\r
 244                     return;\r
 245                 }\r
 246             }\r
 247             bitsets.add(newbits);\r
 248         }\r
 249         coalesce();\r
 250     }\r
 251 \r
 252     /**\r
 253      * Sets all of the bits in this BitSet to {@code false}.\r
 254      */\r
 255     public void clear() {\r
 256         synchronized (bitsets) {\r
 257             bitsets.clear();\r
 258         }\r
 259     }\r
 260 \r
 261     /**\r
 262      * Sets the bit specified by the index to {@code false}.\r
 263      *\r
 264      * @param bit the index of the bit to be cleared\r
 265      */\r
 266     public void clear(long bit) {\r
 267         clear(bit, bit + 1);\r
 268     }\r
 269 \r
 270     /**\r
 271      * Sets the bits from the specified {@code from} (inclusive) to the\r
 272      * specified {@code to} (exclusive) to {@code false}.\r
 273      *\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
 279      */\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<>();\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
 289                     if (len > 0)\r
 290                         newranges.add(new RLE(bs.firstBit(), len));\r
 291                     len = bs.lastBit() - newbits.lastBit();\r
 292                     if (len > 0)\r
 293                         newranges.add(new RLE(newbits.lastBit() + 1, len));\r
 294                     bs.nbits = 0;\r
 295                 }\r
 296             }\r
 297             if (!newranges.isEmpty()) {\r
 298                 for (RLE bs : newranges) {\r
 299                     bitsets.add(bs);\r
 300                 }\r
 301             }\r
 302         }\r
 303         coalesce();\r
 304     }\r
 305 \r
 306     /**\r
 307      * Combine abutting RLEBitSets, and remove 0 length RLEBitSets.\r
 308      */\r
 309     private void coalesce() {\r
 310         RLE last = null;\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
 317                     iter.remove();\r
 318                 } else if (bs.nbits == 0) {\r
 319                     iter.remove();\r
 320                 } else {\r
 321                     last = bs;\r
 322                 }\r
 323             }\r
 324         }\r
 325     }\r
 326 \r
 327     /**\r
 328      * Checks that fromIndex ... toIndex is a valid range of bit indices.\r
 329      */\r
 330     private static void checkRange(long from, long to) {\r
 331         if (from < 0)\r
 332             throw new IndexOutOfBoundsException("fromIndex < 0: " + from);\r
 333         if (to < 0)\r
 334             throw new IndexOutOfBoundsException("toIndex < 0: " + to);\r
 335         if (from > to)\r
 336             throw new IndexOutOfBoundsException("fromIndex: " + from + " > toIndex: " + to);\r
 337     }\r
 338 \r
 339     /**\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
 344      *\r
 345      * @param set a {@code RLEBitSet}\r
 346      */\r
 347     public void and(RLEBitSet set) {\r
 348         long last = 0;\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
 353             }\r
 354         }\r
 355         clear(last, Long.MAX_VALUE);\r
 356     }\r
 357 \r
 358     /**\r
 359      * Clears all of the bits in this {@code RLEBitSet} whose corresponding bit is set in\r
 360      * the specified {@code RLEBitSet}.\r
 361      *\r
 362      * @param set the {@code RLEBitSet} with which to mask this {@code RLEBitSet}\r
 363      */\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
 368             }\r
 369         }\r
 370     }\r
 371 \r
 372     /**\r
 373      * Returns true if this {@code RLEBitSet} contains no bits that are set\r
 374      * to {@code true}.\r
 375      *\r
 376      * @return boolean indicating whether this {@code BitSet} is empty\r
 377      */\r
 378     public boolean isEmpty() {\r
 379         return bitsets.isEmpty();\r
 380     }\r
 381 \r
 382     /**\r
 383      * Returns the number of bits set to {@code true} in this {@code RLEBitSet}.\r
 384      *\r
 385      * @return the number of bits set to {@code true} in this {@code RLEBitSet}.\r
 386      */\r
 387     public int cardinality() {\r
 388         int n = 0;\r
 389         synchronized (bitsets) {\r
 390             for (RLE bs : bitsets) {\r
 391                 n += bs.cardinality();\r
 392             }\r
 393         }\r
 394         return n;\r
 395     }\r
 396 \r
 397     /**\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
 400      *\r
 401      * @return a clone of this bit set\r
 402      */\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
 408             }\r
 409         }\r
 410         return rv;\r
 411     }\r
 412 \r
 413     /**\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
 419      *\r
 420      * @return the String\r
 421      */\r
 422     @Override\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
 428                 sb.append(prefix);\r
 429                 prefix = ",";\r
 430                 long s = bs.firstBit();\r
 431                 long e = bs.lastBit();\r
 432                 sb.append(s);\r
 433                 if (s != e)\r
 434                     sb.append('-').append(e);\r
 435             }\r
 436         }\r
 437         return sb.toString();\r
 438     }\r
 439 \r
 440     /**\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
 443      *\r
 444      * @return the Iterator\r
 445      */\r
 446     public Iterator<Long[]> getRangeIterator() {\r
 447         return new Iterator<Long[]>() {\r
 448             private Iterator<RLE> i = bitsets.iterator();\r
 449 \r
 450             @Override\r
 451             public boolean hasNext() {\r
 452                 return i.hasNext();\r
 453             }\r
 454 \r
 455             @Override\r
 456             public Long[] next() {\r
 457                 RLE bs = i.next();\r
 458                 return new Long[]{bs.firstBit(), bs.lastBit()};\r
 459             }\r
 460 \r
 461             @Override\r
 462             public void remove() {\r
 463                 throw new UnsupportedOperationException();\r
 464             }\r
 465         };\r
 466     }\r
 467 }\r