* * Licensed under the Apache License, Version 2.0 (the "License");\r
* * you may not use this file except in compliance with the License.\r
* * You may obtain a copy of the License at\r
- * * \r
+ * *\r
* * http://www.apache.org/licenses/LICENSE-2.0\r
- * * \r
+ * *\r
* * Unless required by applicable law or agreed to in writing, software\r
* * distributed under the License is distributed on an "AS IS" BASIS,\r
* * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
* @version $Id$\r
*/\r
public class RLEBitSet {\r
- /**\r
- * Used to represent a continues set of <i>nbits</i> 1 bits starting at <i>start</i>.\r
- */\r
- private class RLE implements Comparable<RLE> {\r
- private final long start;\r
- private long nbits;\r
- public RLE(long from, long nbits) {\r
- this.start = from;\r
- this.nbits = (nbits > 0) ? nbits : 0;\r
- }\r
- /**\r
- * Returns the index of the first set bit in this RLE.\r
- * @return the index\r
- */\r
- public long firstBit() {\r
- return start;\r
- }\r
- /**\r
- * Returns the index of the last set bit in this RLE.\r
- * @return the index\r
- */\r
- public long lastBit() {\r
- return start+nbits-1;\r
- }\r
- public boolean intersects(RLE b2) {\r
- if (b2.lastBit() < this.firstBit())\r
- return false;\r
- if (b2.firstBit() > this.lastBit())\r
- return false;\r
- return true;\r
- }\r
- public boolean isSubset(RLE b2) {\r
- if (firstBit() < b2.firstBit())\r
- return false;\r
- if (firstBit() > b2.lastBit())\r
- return false;\r
- if (lastBit() < b2.firstBit())\r
- return false;\r
- if (lastBit() > b2.lastBit())\r
- return false;\r
- return true;\r
- }\r
- public RLE union(RLE b2) {\r
- RLE b1 = this;\r
- if (b1.firstBit() > b2.firstBit()) {\r
- b1 = b2;\r
- b2 = this;\r
- }\r
- long end = b1.lastBit();\r
- if (b2.lastBit() > b1.lastBit())\r
- end = b2.lastBit();\r
- return new RLE(b1.firstBit(), end-b1.firstBit()+1);\r
- }\r
- /**\r
- * Returns the number of bits set to {@code true} in this {@code RLE}.\r
- * @return the number of bits set to {@code true} in this {@code RLE}.\r
- */\r
- public int cardinality() {\r
- return (int) nbits;\r
- }\r
- @Override\r
- public int compareTo(RLE o) {\r
- if (this.equals(o))\r
- return 0;\r
- return (start < o.start) ? -1 : 1;\r
- }\r
- @Override\r
- public boolean equals(Object obj) {\r
- if (obj instanceof RLE) {\r
- RLE b = (RLE) obj;\r
- return (start == b.start) && (nbits == b.nbits);\r
- }\r
- return false;\r
- }\r
- @Override\r
- public int hashCode() {\r
- return new Long(start ^ nbits).hashCode();\r
- }\r
- @Override\r
- public String toString() {\r
- return "["+firstBit()+".."+lastBit()+"]";\r
- }\r
- }\r
- private SortedSet<RLE> bitsets;\r
-\r
- /**\r
- * Creates a new bit set. All bits are initially <code>false</code>.\r
- */\r
- public RLEBitSet() {\r
- bitsets = new TreeSet<RLE>();\r
- }\r
- /**\r
- * Creates a new bit set, with bits set according to the value of <code>s</code>.\r
- * @param s the initialization String\r
- */\r
- public RLEBitSet(String s) {\r
- bitsets = new TreeSet<RLE>();\r
- set(s);\r
- }\r
- /**\r
- * Returns the "logical size" of this {@code RLEBitSet}: the index of the highest set bit\r
- * in the {@code RLEBitSet} plus one. Returns zero if the {@code RLEBitSet} contains no set bits.\r
- * @return the logical size of this {@code RLEBitSet}\r
- */\r
- public long length() {\r
- if (isEmpty())\r
- return 0;\r
- return bitsets.last().lastBit()+1;\r
- }\r
- /**\r
- * Returns the value of the bit with the specified index. The value is {@code true} if the bit\r
- * with the index bit is currently set in this BitSet; otherwise, the result is {@code false}.\r
- * @param bit the bit index\r
- * @return the value of the bit with the specified index\r
- */\r
- public boolean get(long bit) {\r
- synchronized (bitsets) {\r
- for (RLE bs : bitsets) {\r
- if (bit >= bs.firstBit() && bit <= bs.lastBit())\r
- return true;\r
- }\r
- }\r
- return false;\r
- }\r
- /**\r
- * Set one or more bits to true, based on the value of <code>s</code>.\r
- * @param s the initialization String, which consists of a comma or space separated list of\r
- * non-negative numbers and ranges. An individual number represents the bit index to set.\r
- * A range (two numbers separated by a dash) causes all bit indexes between the two numbers\r
- * (inclusive) to be set.\r
- * @exception NumberFormatException - if a number is incorrectly formatted\r
- * @exception IndexOutOfBoundsException - if an index is negative\r
- */\r
- public void set(String s) throws NumberFormatException {\r
- s = s.trim();\r
- if (!s.isEmpty()) {\r
- for (String s2 : s.split("[, \n]+")) {\r
- if (s2.indexOf('-') >= 0) {\r
- String[] pp = s2.split("-");\r
- long f = Long.parseLong(pp[0]);\r
- long t = Long.parseLong(pp[1]);\r
- set(f, t+1);\r
- } else\r
- set(Long.parseLong(s2));\r
- }\r
- }\r
- }\r
- /**\r
- * Sets the bit at the specified index to {@code true}.\r
- * @param bit a bit index\r
- */\r
- public void set(long bit) {\r
- set(bit, bit+1);\r
- }\r
- /**\r
- * Sets the bits from the specified {@code from} (inclusive) to the\r
- * specified {@code to} (exclusive) to {@code true}.\r
- * @param from index of the first bit to be set\r
- * @param to index after the last bit to be set\r
- * @throws IndexOutOfBoundsException if {@code from} is negative,\r
- * or {@code to} is negative,\r
- * or {@code from} is larger than {@code to}\r
- */\r
- public void set(long from, long to) {\r
- checkRange(from, to);\r
- RLE newbits = new RLE(from, to-from);\r
- synchronized (bitsets) {\r
- for (RLE bs : bitsets) {\r
- if (bs.intersects(newbits)) {\r
- if (!newbits.isSubset(bs)) {\r
- bitsets.remove(bs);\r
- bitsets.add(newbits.union(bs));\r
- coalesce();\r
- }\r
- return;\r
- }\r
- }\r
- bitsets.add(newbits);\r
- }\r
- coalesce();\r
- }\r
- /**\r
- * Sets all of the bits in this BitSet to {@code false}.\r
- */\r
- public void clear() {\r
- synchronized (bitsets) {\r
- bitsets.clear();\r
- }\r
- }\r
- /**\r
- * Sets the bit specified by the index to {@code false}.\r
- * @param bit the index of the bit to be cleared\r
- */\r
- public void clear(long bit) {\r
- clear(bit, bit+1);\r
- }\r
- /**\r
- * Sets the bits from the specified {@code from} (inclusive) to the\r
- * specified {@code to} (exclusive) to {@code false}.\r
- * @param from index of the first bit to be cleared\r
- * @param to index after the last bit to be cleared\r
- * @throws IndexOutOfBoundsException if {@code from} is negative,\r
- * or {@code to} is negative,\r
- * or {@code from} is larger than {@code to}\r
- */\r
- public void clear(long from, long to) {\r
- checkRange(from, to);\r
- RLE newbits = new RLE(from, to-from);\r
- List<RLE> newranges = new ArrayList<RLE>();\r
- synchronized (bitsets) {\r
- for (RLE bs : bitsets) {\r
- if (bs.intersects(newbits)) {\r
- // preserve the bits that are not being cleared\r
- long len = newbits.firstBit() - bs.firstBit();\r
- if (len > 0)\r
- newranges.add(new RLE(bs.firstBit(), len));\r
- len = bs.lastBit() - newbits.lastBit();\r
- if (len > 0)\r
- newranges.add(new RLE(newbits.lastBit()+1, len));\r
- bs.nbits = 0;\r
- }\r
- }\r
- if (!newranges.isEmpty()) {\r
- for (RLE bs : newranges) {\r
- bitsets.add(bs);\r
- }\r
- }\r
- }\r
- coalesce();\r
- }\r
- /** Combine abutting RLEBitSets, and remove 0 length RLEBitSets. */\r
- private void coalesce() {\r
- RLE last = null;\r
- synchronized (bitsets) {\r
- Iterator<RLE> iter = bitsets.iterator();\r
- while (iter.hasNext()) {\r
- RLE bs = iter.next();\r
- if (last != null && (last.lastBit()+1 == bs.firstBit())) {\r
- last.nbits += bs.nbits;\r
- iter.remove();\r
- } else if (bs.nbits == 0) {\r
- iter.remove();\r
- } else {\r
- last = bs;\r
- }\r
- }\r
- }\r
- }\r
- /**\r
- * Checks that fromIndex ... toIndex is a valid range of bit indices.\r
- */\r
- private static void checkRange(long from, long to) {\r
- if (from < 0)\r
- throw new IndexOutOfBoundsException("fromIndex < 0: " + from);\r
- if (to < 0)\r
- throw new IndexOutOfBoundsException("toIndex < 0: " + to);\r
- if (from > to)\r
- throw new IndexOutOfBoundsException("fromIndex: " + from + " > toIndex: " + to);\r
- }\r
- /**\r
- * Performs a logical <b>AND</b> of this target bit set with the argument bit set.\r
- * This bit set is modified so that each bit in it has the value {@code true} if and only if\r
- * it both initially had the value {@code true} and the corresponding bit in the bit set\r
- * argument also had the value {@code true}.\r
- * @param set a {@code RLEBitSet}\r
- */\r
- public void and(RLEBitSet set) {\r
- long last = 0;\r
- synchronized (set.bitsets) {\r
- for (RLE bs : set.bitsets) {\r
- clear(last, bs.start);\r
- last = bs.start + bs.nbits;\r
- }\r
- }\r
- clear(last, Long.MAX_VALUE);\r
- }\r
- /**\r
- * Clears all of the bits in this {@code RLEBitSet} whose corresponding bit is set in\r
- * the specified {@code RLEBitSet}.\r
- * @param set the {@code RLEBitSet} with which to mask this {@code RLEBitSet}\r
- */\r
- public void andNot(RLEBitSet set) {\r
- synchronized (set.bitsets) {\r
- for (RLE bs : set.bitsets) {\r
- clear(bs.start, bs.start + bs.nbits);\r
- }\r
- }\r
- }\r
- /**\r
- * Returns true if this {@code RLEBitSet} contains no bits that are set\r
- * to {@code true}.\r
- *\r
- * @return boolean indicating whether this {@code BitSet} is empty\r
- */\r
- public boolean isEmpty() {\r
- return bitsets.isEmpty();\r
- }\r
- /**\r
- * Returns the number of bits set to {@code true} in this {@code RLEBitSet}.\r
- * @return the number of bits set to {@code true} in this {@code RLEBitSet}.\r
- */\r
- public int cardinality() {\r
- int n = 0;\r
- synchronized (bitsets) {\r
- for (RLE bs : bitsets) {\r
- n += bs.cardinality();\r
- }\r
- }\r
- return n;\r
- }\r
- /**\r
- * Cloning this RLEBitSet produces a new RLEBitSet that is equal to it. The clone of the\r
- * bit set is another bit set that has exactly the same bits set to true as this bit set.\r
- * @return a clone of this bit set\r
- */\r
- public Object clone() {\r
- RLEBitSet rv = new RLEBitSet();\r
- synchronized (bitsets) {\r
- for (RLE bs : bitsets) {\r
- rv.bitsets.add(new RLE(bs.start, bs.nbits));\r
- }\r
- }\r
- return rv;\r
- }\r
- /**\r
- * Returns a string representation of this bit set, using the same notation as is required for\r
- * the String constructor. For every index for which this {@code RLEBitSet} contains a bit in\r
- * the set state, the decimal representation of that index is included in the result. Such\r
- * indices are listed in order from lowest to highest, separated by ",". Ranges of set bits are\r
- * indicated by <i>lobit</i>-<i>hibit</i>.\r
- * @return the String\r
- */\r
- @Override\r
- public String toString() {\r
- StringBuilder sb = new StringBuilder();\r
- String prefix = "";\r
- synchronized (bitsets) {\r
- for (RLE bs : bitsets) {\r
- sb.append(prefix);\r
- prefix = ",";\r
- long s = bs.firstBit();\r
- long e = bs.lastBit();\r
- sb.append(s);\r
- if (s != e)\r
- sb.append('-').append(e);\r
- }\r
- }\r
- return sb.toString();\r
- }\r
- /**\r
- * Return an Iterator which provides pairs of {@code Long}s representing the beginning and\r
- * ending index of a range of set bits in this {@code RLEBitSet}.\r
- * @return the Iterator\r
- */\r
- public Iterator<Long[]> getRangeIterator() {\r
- return new Iterator<Long[]>() {\r
- private Iterator<RLE> i = bitsets.iterator();\r
-\r
- @Override\r
- public boolean hasNext() {\r
- return i.hasNext();\r
- }\r
-\r
- @Override\r
- public Long[] next() {\r
- RLE bs = i.next();\r
- return new Long[] { bs.firstBit(), bs.lastBit() };\r
- }\r
-\r
- @Override\r
- public void remove() {\r
- throw new UnsupportedOperationException();\r
- }\r
- };\r
- }\r
+ /**\r
+ * Used to represent a continues set of <i>nbits</i> 1 bits starting at <i>start</i>.\r
+ */\r
+ private class RLE implements Comparable<RLE> {\r
+ private final long start;\r
+ private long nbits;\r
+\r
+ public RLE(long from, long nbits) {\r
+ this.start = from;\r
+ this.nbits = (nbits > 0) ? nbits : 0;\r
+ }\r
+\r
+ /**\r
+ * Returns the index of the first set bit in this RLE.\r
+ *\r
+ * @return the index\r
+ */\r
+ public long firstBit() {\r
+ return start;\r
+ }\r
+\r
+ /**\r
+ * Returns the index of the last set bit in this RLE.\r
+ *\r
+ * @return the index\r
+ */\r
+ public long lastBit() {\r
+ return start + nbits - 1;\r
+ }\r
+\r
+ public boolean intersects(RLE b2) {\r
+ if (b2.lastBit() < this.firstBit())\r
+ return false;\r
+ if (b2.firstBit() > this.lastBit())\r
+ return false;\r
+ return true;\r
+ }\r
+\r
+ public boolean isSubset(RLE b2) {\r
+ if (firstBit() < b2.firstBit())\r
+ return false;\r
+ if (firstBit() > b2.lastBit())\r
+ return false;\r
+ if (lastBit() < b2.firstBit())\r
+ return false;\r
+ if (lastBit() > b2.lastBit())\r
+ return false;\r
+ return true;\r
+ }\r
+\r
+ public RLE union(RLE b2) {\r
+ RLE b1 = this;\r
+ if (b1.firstBit() > b2.firstBit()) {\r
+ b1 = b2;\r
+ b2 = this;\r
+ }\r
+ long end = b1.lastBit();\r
+ if (b2.lastBit() > b1.lastBit())\r
+ end = b2.lastBit();\r
+ return new RLE(b1.firstBit(), end - b1.firstBit() + 1);\r
+ }\r
+\r
+ /**\r
+ * Returns the number of bits set to {@code true} in this {@code RLE}.\r
+ *\r
+ * @return the number of bits set to {@code true} in this {@code RLE}.\r
+ */\r
+ public int cardinality() {\r
+ return (int) nbits;\r
+ }\r
+\r
+ @Override\r
+ public int compareTo(RLE o) {\r
+ if (this.equals(o))\r
+ return 0;\r
+ return (start < o.start) ? -1 : 1;\r
+ }\r
+\r
+ @Override\r
+ public boolean equals(Object obj) {\r
+ if (obj instanceof RLE) {\r
+ RLE b = (RLE) obj;\r
+ return (start == b.start) && (nbits == b.nbits);\r
+ }\r
+ return false;\r
+ }\r
+\r
+ @Override\r
+ public int hashCode() {\r
+ return new Long(start ^ nbits).hashCode();\r
+ }\r
+\r
+ @Override\r
+ public String toString() {\r
+ return "[" + firstBit() + ".." + lastBit() + "]";\r
+ }\r
+ }\r
+\r
+ private SortedSet<RLE> bitsets;\r
+\r
+ /**\r
+ * Creates a new bit set. All bits are initially <code>false</code>.\r
+ */\r
+ public RLEBitSet() {\r
+ bitsets = new TreeSet<RLE>();\r
+ }\r
+\r
+ /**\r
+ * Creates a new bit set, with bits set according to the value of <code>s</code>.\r
+ *\r
+ * @param s the initialization String\r
+ */\r
+ public RLEBitSet(String s) {\r
+ bitsets = new TreeSet<RLE>();\r
+ set(s);\r
+ }\r
+\r
+ /**\r
+ * Returns the "logical size" of this {@code RLEBitSet}: the index of the highest set bit\r
+ * in the {@code RLEBitSet} plus one. Returns zero if the {@code RLEBitSet} contains no set bits.\r
+ *\r
+ * @return the logical size of this {@code RLEBitSet}\r
+ */\r
+ public long length() {\r
+ if (isEmpty())\r
+ return 0;\r
+ return bitsets.last().lastBit() + 1;\r
+ }\r
+\r
+ /**\r
+ * Returns the value of the bit with the specified index. The value is {@code true} if the bit\r
+ * with the index bit is currently set in this BitSet; otherwise, the result is {@code false}.\r
+ *\r
+ * @param bit the bit index\r
+ * @return the value of the bit with the specified index\r
+ */\r
+ public boolean get(long bit) {\r
+ synchronized (bitsets) {\r
+ for (RLE bs : bitsets) {\r
+ if (bit >= bs.firstBit() && bit <= bs.lastBit())\r
+ return true;\r
+ }\r
+ }\r
+ return false;\r
+ }\r
+\r
+ /**\r
+ * Set one or more bits to true, based on the value of <code>s</code>.\r
+ *\r
+ * @param s the initialization String, which consists of a comma or space separated list of\r
+ * non-negative numbers and ranges. An individual number represents the bit index to set.\r
+ * A range (two numbers separated by a dash) causes all bit indexes between the two numbers\r
+ * (inclusive) to be set.\r
+ * @throws NumberFormatException - if a number is incorrectly formatted\r
+ * @throws IndexOutOfBoundsException - if an index is negative\r
+ */\r
+ public void set(String s) throws NumberFormatException {\r
+ s = s.trim();\r
+ if (!s.isEmpty()) {\r
+ for (String s2 : s.split("[, \n]+")) {\r
+ if (s2.indexOf('-') >= 0) {\r
+ String[] pp = s2.split("-");\r
+ long f = Long.parseLong(pp[0]);\r
+ long t = Long.parseLong(pp[1]);\r
+ set(f, t + 1);\r
+ } else\r
+ set(Long.parseLong(s2));\r
+ }\r
+ }\r
+ }\r
+\r
+ /**\r
+ * Sets the bit at the specified index to {@code true}.\r
+ *\r
+ * @param bit a bit index\r
+ */\r
+ public void set(long bit) {\r
+ set(bit, bit + 1);\r
+ }\r
+\r
+ /**\r
+ * Sets the bits from the specified {@code from} (inclusive) to the\r
+ * specified {@code to} (exclusive) to {@code true}.\r
+ *\r
+ * @param from index of the first bit to be set\r
+ * @param to index after the last bit to be set\r
+ * @throws IndexOutOfBoundsException if {@code from} is negative,\r
+ * or {@code to} is negative,\r
+ * or {@code from} is larger than {@code to}\r
+ */\r
+ public void set(long from, long to) {\r
+ checkRange(from, to);\r
+ RLE newbits = new RLE(from, to - from);\r
+ synchronized (bitsets) {\r
+ for (RLE bs : bitsets) {\r
+ if (bs.intersects(newbits)) {\r
+ if (!newbits.isSubset(bs)) {\r
+ bitsets.remove(bs);\r
+ bitsets.add(newbits.union(bs));\r
+ coalesce();\r
+ }\r
+ return;\r
+ }\r
+ }\r
+ bitsets.add(newbits);\r
+ }\r
+ coalesce();\r
+ }\r
+\r
+ /**\r
+ * Sets all of the bits in this BitSet to {@code false}.\r
+ */\r
+ public void clear() {\r
+ synchronized (bitsets) {\r
+ bitsets.clear();\r
+ }\r
+ }\r
+\r
+ /**\r
+ * Sets the bit specified by the index to {@code false}.\r
+ *\r
+ * @param bit the index of the bit to be cleared\r
+ */\r
+ public void clear(long bit) {\r
+ clear(bit, bit + 1);\r
+ }\r
+\r
+ /**\r
+ * Sets the bits from the specified {@code from} (inclusive) to the\r
+ * specified {@code to} (exclusive) to {@code false}.\r
+ *\r
+ * @param from index of the first bit to be cleared\r
+ * @param to index after the last bit to be cleared\r
+ * @throws IndexOutOfBoundsException if {@code from} is negative,\r
+ * or {@code to} is negative,\r
+ * or {@code from} is larger than {@code to}\r
+ */\r
+ public void clear(long from, long to) {\r
+ checkRange(from, to);\r
+ RLE newbits = new RLE(from, to - from);\r
+ List<RLE> newranges = new ArrayList<RLE>();\r
+ synchronized (bitsets) {\r
+ for (RLE bs : bitsets) {\r
+ if (bs.intersects(newbits)) {\r
+ // preserve the bits that are not being cleared\r
+ long len = newbits.firstBit() - bs.firstBit();\r
+ if (len > 0)\r
+ newranges.add(new RLE(bs.firstBit(), len));\r
+ len = bs.lastBit() - newbits.lastBit();\r
+ if (len > 0)\r
+ newranges.add(new RLE(newbits.lastBit() + 1, len));\r
+ bs.nbits = 0;\r
+ }\r
+ }\r
+ if (!newranges.isEmpty()) {\r
+ for (RLE bs : newranges) {\r
+ bitsets.add(bs);\r
+ }\r
+ }\r
+ }\r
+ coalesce();\r
+ }\r
+\r
+ /**\r
+ * Combine abutting RLEBitSets, and remove 0 length RLEBitSets.\r
+ */\r
+ private void coalesce() {\r
+ RLE last = null;\r
+ synchronized (bitsets) {\r
+ Iterator<RLE> iter = bitsets.iterator();\r
+ while (iter.hasNext()) {\r
+ RLE bs = iter.next();\r
+ if (last != null && (last.lastBit() + 1 == bs.firstBit())) {\r
+ last.nbits += bs.nbits;\r
+ iter.remove();\r
+ } else if (bs.nbits == 0) {\r
+ iter.remove();\r
+ } else {\r
+ last = bs;\r
+ }\r
+ }\r
+ }\r
+ }\r
+\r
+ /**\r
+ * Checks that fromIndex ... toIndex is a valid range of bit indices.\r
+ */\r
+ private static void checkRange(long from, long to) {\r
+ if (from < 0)\r
+ throw new IndexOutOfBoundsException("fromIndex < 0: " + from);\r
+ if (to < 0)\r
+ throw new IndexOutOfBoundsException("toIndex < 0: " + to);\r
+ if (from > to)\r
+ throw new IndexOutOfBoundsException("fromIndex: " + from + " > toIndex: " + to);\r
+ }\r
+\r
+ /**\r
+ * Performs a logical <b>AND</b> of this target bit set with the argument bit set.\r
+ * This bit set is modified so that each bit in it has the value {@code true} if and only if\r
+ * it both initially had the value {@code true} and the corresponding bit in the bit set\r
+ * argument also had the value {@code true}.\r
+ *\r
+ * @param set a {@code RLEBitSet}\r
+ */\r
+ public void and(RLEBitSet set) {\r
+ long last = 0;\r
+ synchronized (set.bitsets) {\r
+ for (RLE bs : set.bitsets) {\r
+ clear(last, bs.start);\r
+ last = bs.start + bs.nbits;\r
+ }\r
+ }\r
+ clear(last, Long.MAX_VALUE);\r
+ }\r
+\r
+ /**\r
+ * Clears all of the bits in this {@code RLEBitSet} whose corresponding bit is set in\r
+ * the specified {@code RLEBitSet}.\r
+ *\r
+ * @param set the {@code RLEBitSet} with which to mask this {@code RLEBitSet}\r
+ */\r
+ public void andNot(RLEBitSet set) {\r
+ synchronized (set.bitsets) {\r
+ for (RLE bs : set.bitsets) {\r
+ clear(bs.start, bs.start + bs.nbits);\r
+ }\r
+ }\r
+ }\r
+\r
+ /**\r
+ * Returns true if this {@code RLEBitSet} contains no bits that are set\r
+ * to {@code true}.\r
+ *\r
+ * @return boolean indicating whether this {@code BitSet} is empty\r
+ */\r
+ public boolean isEmpty() {\r
+ return bitsets.isEmpty();\r
+ }\r
+\r
+ /**\r
+ * Returns the number of bits set to {@code true} in this {@code RLEBitSet}.\r
+ *\r
+ * @return the number of bits set to {@code true} in this {@code RLEBitSet}.\r
+ */\r
+ public int cardinality() {\r
+ int n = 0;\r
+ synchronized (bitsets) {\r
+ for (RLE bs : bitsets) {\r
+ n += bs.cardinality();\r
+ }\r
+ }\r
+ return n;\r
+ }\r
+\r
+ /**\r
+ * Cloning this RLEBitSet produces a new RLEBitSet that is equal to it. The clone of the\r
+ * bit set is another bit set that has exactly the same bits set to true as this bit set.\r
+ *\r
+ * @return a clone of this bit set\r
+ */\r
+ public Object clone() {\r
+ RLEBitSet rv = new RLEBitSet();\r
+ synchronized (bitsets) {\r
+ for (RLE bs : bitsets) {\r
+ rv.bitsets.add(new RLE(bs.start, bs.nbits));\r
+ }\r
+ }\r
+ return rv;\r
+ }\r
+\r
+ /**\r
+ * Returns a string representation of this bit set, using the same notation as is required for\r
+ * the String constructor. For every index for which this {@code RLEBitSet} contains a bit in\r
+ * the set state, the decimal representation of that index is included in the result. Such\r
+ * indices are listed in order from lowest to highest, separated by ",". Ranges of set bits are\r
+ * indicated by <i>lobit</i>-<i>hibit</i>.\r
+ *\r
+ * @return the String\r
+ */\r
+ @Override\r
+ public String toString() {\r
+ StringBuilder sb = new StringBuilder();\r
+ String prefix = "";\r
+ synchronized (bitsets) {\r
+ for (RLE bs : bitsets) {\r
+ sb.append(prefix);\r
+ prefix = ",";\r
+ long s = bs.firstBit();\r
+ long e = bs.lastBit();\r
+ sb.append(s);\r
+ if (s != e)\r
+ sb.append('-').append(e);\r
+ }\r
+ }\r
+ return sb.toString();\r
+ }\r
+\r
+ /**\r
+ * Return an Iterator which provides pairs of {@code Long}s representing the beginning and\r
+ * ending index of a range of set bits in this {@code RLEBitSet}.\r
+ *\r
+ * @return the Iterator\r
+ */\r
+ public Iterator<Long[]> getRangeIterator() {\r
+ return new Iterator<Long[]>() {\r
+ private Iterator<RLE> i = bitsets.iterator();\r
+\r
+ @Override\r
+ public boolean hasNext() {\r
+ return i.hasNext();\r
+ }\r
+\r
+ @Override\r
+ public Long[] next() {\r
+ RLE bs = i.next();\r
+ return new Long[]{bs.firstBit(), bs.lastBit()};\r
+ }\r
+\r
+ @Override\r
+ public void remove() {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+ };\r
+ }\r
}\r