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                 public RLE(long from, long nbits) {\r
  50                         this.start = from;\r
  51                         this.nbits = (nbits > 0) ? nbits : 0;\r
  52                 }\r
  53                 /**\r
  54                  * Returns the index of the first set bit in this RLE.\r
  55                  * @return the index\r
  56                  */\r
  57                 public long firstBit() {\r
  58                         return start;\r
  59                 }\r
  60                 /**\r
  61                  * Returns the index of the last set bit in this RLE.\r
  62                  * @return the index\r
  63                  */\r
  64                 public long lastBit() {\r
  65                         return start+nbits-1;\r
  66                 }\r
  67                 public boolean intersects(RLE b2) {\r
  68                         if (b2.lastBit() < this.firstBit())\r
  69                                 return false;\r
  70                         if (b2.firstBit() > this.lastBit())\r
  71                                 return false;\r
  72                         return true;\r
  73                 }\r
  74                 public boolean isSubset(RLE b2) {\r
  75                         if (firstBit() < b2.firstBit())\r
  76                                 return false;\r
  77                         if (firstBit() > b2.lastBit())\r
  78                                 return false;\r
  79                         if (lastBit() < b2.firstBit())\r
  80                                 return false;\r
  81                         if (lastBit() > b2.lastBit())\r
  82                                 return false;\r
  83                         return true;\r
  84                 }\r
  85                 public RLE union(RLE b2) {\r
  86                         RLE b1 = this;\r
  87                         if (b1.firstBit() > b2.firstBit()) {\r
  88                                 b1 = b2;\r
  89                                 b2 = this;\r
  90                         }\r
  91                         long end = b1.lastBit();\r
  92                         if (b2.lastBit() > b1.lastBit())\r
  93                                 end = b2.lastBit();\r
  94                         return new RLE(b1.firstBit(), end-b1.firstBit()+1);\r
  95                 }\r
  96                 /**\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
  99                  */\r
 100                 public int cardinality() {\r
 101                         return (int) nbits;\r
 102                 }\r
 103                 @Override\r
 104                 public int compareTo(RLE o) {\r
 105                         if (this.equals(o))\r
 106                                 return 0;\r
 107                         return (start < o.start) ? -1 : 1;\r
 108                 }\r
 109                 @Override\r
 110                 public boolean equals(Object obj) {\r
 111                         if (obj instanceof RLE) {\r
 112                                 RLE b = (RLE) obj;\r
 113                                 return (start == b.start) && (nbits == b.nbits);\r
 114                         }\r
 115                         return false;\r
 116                 }\r
 117                 @Override\r
 118                 public int hashCode() {\r
 119                         return new Long(start ^ nbits).hashCode();\r
 120                 }\r
 121                 @Override\r
 122                 public String toString() {\r
 123                         return "["+firstBit()+".."+lastBit()+"]";\r
 124                 }\r
 125         }\r
 126         private SortedSet<RLE> bitsets;\r
 127 \r
 128         /**\r
 129          * Creates a new bit set. All bits are initially <code>false</code>.\r
 130          */\r
 131         public RLEBitSet() {\r
 132                 bitsets = new TreeSet<RLE>();\r
 133         }\r
 134         /**\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
 137          */\r
 138         public RLEBitSet(String s) {\r
 139                 bitsets = new TreeSet<RLE>();\r
 140                 set(s);\r
 141         }\r
 142         /**\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
 146          */\r
 147         public long length() {\r
 148                 if (isEmpty())\r
 149                         return 0;\r
 150                 return bitsets.last().lastBit()+1;\r
 151         }\r
 152         /**\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
 157          */\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
 162                                         return true;\r
 163                         }\r
 164                 }\r
 165                 return false;\r
 166         }\r
 167         /**\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
 175          */\r
 176         public void set(String s) throws NumberFormatException {\r
 177                 s = s.trim();\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
 184                                         set(f, t+1);\r
 185                                 } else\r
 186                                         set(Long.parseLong(s2));\r
 187                         }\r
 188                 }\r
 189         }\r
 190         /**\r
 191          * Sets the bit at the specified index to {@code true}.\r
 192          * @param bit a bit index\r
 193          */\r
 194         public void set(long bit) {\r
 195                 set(bit, bit+1);\r
 196         }\r
 197         /**\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
 205          */\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
 215                                                 coalesce();\r
 216                                         }\r
 217                                         return;\r
 218                                 }\r
 219                         }\r
 220                         bitsets.add(newbits);\r
 221                 }\r
 222                 coalesce();\r
 223         }\r
 224         /**\r
 225          * Sets all of the bits in this BitSet to {@code false}.\r
 226          */\r
 227         public void clear() {\r
 228                 synchronized (bitsets) {\r
 229                         bitsets.clear();\r
 230                 }\r
 231         }\r
 232         /**\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
 235          */\r
 236         public void clear(long bit) {\r
 237                 clear(bit, bit+1);\r
 238         }\r
 239         /**\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
 247          */\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
 257                                         if (len > 0)\r
 258                                                 newranges.add(new RLE(bs.firstBit(), len));\r
 259                                         len = bs.lastBit() - newbits.lastBit();\r
 260                                         if (len > 0)\r
 261                                                 newranges.add(new RLE(newbits.lastBit()+1, len));\r
 262                                         bs.nbits = 0;\r
 263                                 }\r
 264                         }\r
 265                         if (!newranges.isEmpty()) {\r
 266                                 for (RLE bs : newranges) {\r
 267                                         bitsets.add(bs);\r
 268                                 }\r
 269                         }\r
 270                 }\r
 271                 coalesce();\r
 272         }\r
 273         /** Combine abutting RLEBitSets, and remove 0 length RLEBitSets. */\r
 274         private void coalesce() {\r
 275                 RLE last = null;\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
 282                                         iter.remove();\r
 283                                 } else if (bs.nbits == 0) {\r
 284                                         iter.remove();\r
 285                                 } else {\r
 286                                         last = bs;\r
 287                                 }\r
 288                         }\r
 289                 }\r
 290         }\r
 291         /**\r
 292          * Checks that fromIndex ... toIndex is a valid range of bit indices.\r
 293          */\r
 294         private static void checkRange(long from, long to) {\r
 295                 if (from < 0)\r
 296                         throw new IndexOutOfBoundsException("fromIndex < 0: " + from);\r
 297                 if (to < 0)\r
 298                         throw new IndexOutOfBoundsException("toIndex < 0: " + to);\r
 299                 if (from > to)\r
 300                         throw new IndexOutOfBoundsException("fromIndex: " + from + " > toIndex: " + to);\r
 301         }\r
 302         /**\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
 308          */\r
 309         public void and(RLEBitSet set) {\r
 310                 long last = 0;\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
 315                         }\r
 316                 }\r
 317                 clear(last, Long.MAX_VALUE);\r
 318         }\r
 319         /**\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
 323          */\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
 328                         }\r
 329                 }\r
 330         }\r
 331         /**\r
 332          * Returns true if this {@code RLEBitSet} contains no bits that are set\r
 333          * to {@code true}.\r
 334          *\r
 335          * @return boolean indicating whether this {@code BitSet} is empty\r
 336          */\r
 337         public boolean isEmpty() {\r
 338                 return bitsets.isEmpty();\r
 339         }\r
 340         /**\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
 343          */\r
 344         public int cardinality() {\r
 345                 int n = 0;\r
 346                 synchronized (bitsets) {\r
 347                         for (RLE bs : bitsets) {\r
 348                                 n += bs.cardinality();\r
 349                         }\r
 350                 }\r
 351                 return n;\r
 352         }\r
 353         /**\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
 357          */\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
 363                         }\r
 364                 }\r
 365                 return rv;\r
 366         }\r
 367         /**\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
 374          */\r
 375         @Override\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
 381                                 sb.append(prefix);\r
 382                                 prefix = ",";\r
 383                                 long s = bs.firstBit();\r
 384                                 long e = bs.lastBit();\r
 385                                 sb.append(s);\r
 386                                 if (s != e)\r
 387                                         sb.append('-').append(e);\r
 388                         }\r
 389                 }\r
 390                 return sb.toString();\r
 391         }\r
 392         /**\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
 396          */\r
 397         public Iterator<Long[]> getRangeIterator() {\r
 398                 return new Iterator<Long[]>() {\r
 399                         private Iterator<RLE> i = bitsets.iterator();\r
 400 \r
 401                         @Override\r
 402                         public boolean hasNext() {\r
 403                                 return i.hasNext();\r
 404                         }\r
 405 \r
 406                         @Override\r
 407                         public Long[] next() {\r
 408                                 RLE bs = i.next();\r
 409                                 return new Long[] { bs.firstBit(), bs.lastBit() };\r
 410                         }\r
 411 \r
 412                         @Override\r
 413                         public void remove() {\r
 414                                 throw new UnsupportedOperationException();\r
 415                         }\r
 416                 };\r
 417         }\r
 418 }\r