gdx/src/com/badlogic/gdx/utils/Bits.java

   1 \r
   2 package com.badlogic.gdx.utils;\r
   3 \r
   4 /** A bitset, without size limitation, allows comparison via bitwise operators to other bitfields.\r
   5  * \r
   6  * @author mzechner\r
   7  * @author jshapcott */\r
   8 public class Bits {\r
   9   \r
  10         long[] bits = {0};\r
  11 \r
  12         public Bits () {\r
  13         }\r
  14 \r
  15         \r
  16         /** Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range 0 through nbits-1.\r
  17          * @param nbits the initial size of the bit set\r
  18          */\r
  19         public Bits (int nbits) {\r
  20                 checkCapacity(nbits >>> 6);\r
  21         }\r
  22 \r
  23         /** @param index the index of the bit\r
  24          * @return whether the bit is set\r
  25          * @throws ArrayIndexOutOfBoundsException if index < 0 */\r
  26         public boolean get (int index) {\r
  27                 final int word = index >>> 6;\r
  28                 if (word >= bits.length) return false;\r
  29                 return (bits[word] & (1L << (index & 0x3F))) != 0L;\r
  30         }\r
  31 \r
  32         /** @param index the index of the bit to set\r
  33          * @throws ArrayIndexOutOfBoundsException if index < 0 */\r
  34         public void set (int index) {\r
  35                 final int word = index >>> 6;\r
  36                 checkCapacity(word);\r
  37                 bits[word] |= 1L << (index & 0x3F);\r
  38         }\r
  39 \r
  40         /** @param index the index of the bit to flip */\r
  41         public void flip (int index) {\r
  42                 final int word = index >>> 6;\r
  43                 checkCapacity(word);\r
  44                 bits[word] ^= 1L << (index & 0x3F);\r
  45         }\r
  46 \r
  47         private void checkCapacity (int len) {\r
  48                 if (len >= bits.length) {\r
  49                         long[] newBits = new long[len + 1];\r
  50                         System.arraycopy(bits, 0, newBits, 0, bits.length);\r
  51                         bits = newBits;\r
  52                 }\r
  53         }\r
  54 \r
  55         /** @param index the index of the bit to clear\r
  56          * @throws ArrayIndexOutOfBoundsException if index < 0 */\r
  57         public void clear (int index) {\r
  58                 final int word = index >>> 6;\r
  59                 if (word >= bits.length) return;\r
  60                 bits[word] &= ~(1L << (index & 0x3F));\r
  61         }\r
  62 \r
  63         /** Clears the entire bitset */\r
  64         public void clear () {\r
  65                 int length = bits.length;\r
  66                 for (int i = 0; i < length; i++) {\r
  67                         bits[i] = 0L;\r
  68                 }\r
  69         }\r
  70 \r
  71         /** @return the number of bits currently stored, <b>not</b> the highset set bit! */\r
  72         public int numBits () {\r
  73                 return bits.length << 6;\r
  74         }\r
  75 \r
  76         /** Returns the "logical size" of this bitset: the index of the highest set bit in the bitset plus one. Returns zero if the\r
  77          * bitset contains no set bits.\r
  78          * \r
  79          * @return the logical size of this bitset */\r
  80         public int length () {\r
  81                 for (int word = bits.length - 1; word >= 0; --word) {\r
  82                         if (bits[word] != 0) {\r
  83                                 for (int bit = 63; bit >= 0; --bit) {\r
  84                                         if ((bits[word] & (1L << (bit & 0x3F))) != 0L) {\r
  85                                                 return (word << 6) + bit;\r
  86                                         }\r
  87                                 }\r
  88                         }\r
  89                 }\r
  90                 return 0;\r
  91         }\r
  92 \r
  93         /** @return true if this bitset contains no bits that are set to true */\r
  94         public boolean isEmpty () {\r
  95                 int length = bits.length;\r
  96                 for (int i = 0; i < length; i++) {\r
  97                         if (bits[i] != 0L) {\r
  98                                 return false;\r
  99                         }\r
 100                 }\r
 101                 return true;\r
 102         }\r
 103 \r
 104         /** Returns the index of the first bit that is set to true that occurs on or after the specified starting index. If no such bit\r
 105          * exists then -1 is returned. */\r
 106         public int nextSetBit (int fromIndex) {\r
 107                 int word = fromIndex >>> 6;\r
 108                 if (word >= bits.length) return -1;\r
 109                 for (int i = fromIndex & 0x3f; i < 64; i++) {\r
 110                         if ((bits[word] & (1L << (i & 0x3F))) != 0L) {\r
 111                                 return (word << 6) + i;\r
 112                         }\r
 113                 }\r
 114                 for (word++; word < bits.length; word++) {\r
 115                         if (word != 0) {\r
 116                                 for (int i = 0; i < 64; i++) {\r
 117                                         if ((bits[word] & (1L << (i & 0x3F))) != 0L) {\r
 118                                                 return (word << 6) + i;\r
 119                                         }\r
 120                                 }\r
 121                         }\r
 122                 }\r
 123                 return -1;\r
 124         }\r
 125 \r
 126         /** Returns the index of the first bit that is set to false that occurs on or after the specified starting index. If no such bit\r
 127          * exists then -1 is returned. */\r
 128         public int nextClearBit (int fromIndex) {\r
 129                 int word = fromIndex >>> 6;\r
 130                 if (word >= bits.length) return -1;\r
 131                 for (int i = fromIndex & 0x3f; i < 64; i++) {\r
 132                         if ((bits[word] & (1L << (i & 0x3F))) == 0L) {\r
 133                                 return (word << 6) + i;\r
 134                         }\r
 135                 }\r
 136                 for (word++; word < bits.length; word++) {\r
 137                         if (word == 0) {\r
 138                                 return word << 6;\r
 139                         }\r
 140                         for (int i = 0; i < 64; i++) {\r
 141                                 if ((bits[word] & (1L << (i & 0x3F))) == 0L) {\r
 142                                         return (word << 6) + i;\r
 143                                 }\r
 144                         }\r
 145                 }\r
 146                 return -1;\r
 147         }\r
 148 \r
 149         /** Performs a logical <b>AND</b> of this target bit set with the argument bit set. This bit set is modified so that each bit in it has\r
 150          * the value true if and only if it both initially had the value true and the corresponding bit in the bit set argument also\r
 151          * had the value true.\r
 152          * @param other a bit set */\r
 153         public void and (Bits other) {\r
 154                 for (int i = 0, j = bits.length, k = other.bits.length; i < j && i < k; i++) {\r
 155                         bits[i] &= other.bits[i];\r
 156                 }\r
 157         }\r
 158 \r
 159         /** Clears all of the bits in this bit set whose corresponding bit is set in the specified bit set.\r
 160          * \r
 161          * @param other a bit set */    \r
 162         public void andNot (Bits other) {\r
 163                 for (int i = 0, j = bits.length, k = other.bits.length; i < j && i < k; i++) {\r
 164                         bits[i] &= ~other.bits[i];\r
 165                 }\r
 166         }\r
 167 \r
 168         /** Performs a logical <b>OR</b> of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value\r
 169          * true if and only if it either already had the value true or the corresponding bit in the bit set argument has the value\r
 170          * true.\r
 171          * @param other a bit set */\r
 172         public void or (Bits other) {\r
 173                 for (int i = 0, j = bits.length, k = other.bits.length; i < j && i < k; i++) {\r
 174                         bits[i] |= other.bits[i];\r
 175                 }\r
 176         }\r
 177         \r
 178         /** Performs a logical <b>XOR</b> of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value true if and only if one of the following statements holds: \r
 179          * <ul>\r
 180          * <li>The bit initially has the value true, and the corresponding bit in the argument has the value false.</li> \r
 181          * <li>The bit initially has the value false, and the corresponding bit in the argument has the value true. </li>\r
 182          * </ul>\r
 183          * @param other\r
 184          */\r
 185         public void xor (Bits other) {\r
 186                 for (int i = 0, j = bits.length, k = other.bits.length; i < j && i < k; i++) {\r
 187                         bits[i] ^= other.bits[i];\r
 188                 }\r
 189         }\r
 190 \r
 191         /** Returns true if the specified BitSet has any bits set to true that are also set to true in this BitSet.\r
 192          * \r
 193          * @param other a bit set\r
 194          * @return boolean indicating whether this bit set intersects the specified bit set\r
 195          */\r
 196         public boolean intersects (Bits other) {\r
 197                 for (int i = 0, j = bits.length, k = other.bits.length; i < j && i < k; i++) {\r
 198                         if ((bits[i] & other.bits[i]) != 0) {\r
 199                                 return true;\r
 200                         }\r
 201                 }\r
 202                 return false;\r
 203         }\r
 204 \r
 205 }