Home | History | Annotate | Download | only in runtime 
      1 /*
      2  [The "BSD license"]
      3  Copyright (c) 2005-2009 Terence Parr
      4  All rights reserved.
      5 
      6  Redistribution and use in source and binary forms, with or without
      7  modification, are permitted provided that the following conditions
      8  are met:
      9  1. Redistributions of source code must retain the above copyright
     10      notice, this list of conditions and the following disclaimer.
     11  2. Redistributions in binary form must reproduce the above copyright
     12      notice, this list of conditions and the following disclaimer in the
     13      documentation and/or other materials provided with the distribution.
     14  3. The name of the author may not be used to endorse or promote products
     15      derived from this software without specific prior written permission.
     16 
     17  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     18  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     19  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     20  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     21  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     22  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     26  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27  */
     28 package org.antlr.runtime;
     29 
     30 import java.util.List;
     31 
     32 /**A stripped-down version of org.antlr.misc.BitSet that is just
     33  * good enough to handle runtime requirements such as FOLLOW sets
     34  * for automatic error recovery.
     35  */
     36 public class BitSet implements Cloneable {
     37     protected final static int BITS = 64;    // number of bits / long
     38     protected final static int LOG_BITS = 6; // 2^6 == 64
     39 
     40     /* We will often need to do a mod operator (i mod nbits).  Its
     41      * turns out that, for powers of two, this mod operation is
     42      * same as (i & (nbits-1)).  Since mod is slow, we use a
     43      * precomputed mod mask to do the mod instead.
     44      */
     45     protected final static int MOD_MASK = BITS - 1;
     46 
     47     /** The actual data bits */
     48     protected long bits[];
     49 
     50     /** Construct a bitset of size one word (64 bits) */
     51     public BitSet() {
     52         this(BITS);
     53     }
     54 
     55     /** Construction from a static array of longs */
     56     public BitSet(long[] bits_) {
     57         bits = bits_;
     58     }
     59 
     60 	/** Construction from a list of integers */
     61 	public BitSet(List items) {
     62 		this();
     63 		for (int i = 0; i < items.size(); i++) {
     64 			Integer v = (Integer) items.get(i);
     65 			add(v.intValue());
     66 		}
     67 	}
     68 
     69     /** Construct a bitset given the size
     70      * @param nbits The size of the bitset in bits
     71      */
     72     public BitSet(int nbits) {
     73         bits = new long[((nbits - 1) >> LOG_BITS) + 1];
     74     }
     75 
     76 	public static BitSet of(int el) {
     77 		BitSet s = new BitSet(el + 1);
     78 		s.add(el);
     79 		return s;
     80 	}
     81 
     82 	public static BitSet of(int a, int b) {
     83 		BitSet s = new BitSet(Math.max(a,b)+1);
     84 		s.add(a);
     85 		s.add(b);
     86 		return s;
     87 	}
     88 
     89 	public static BitSet of(int a, int b, int c) {
     90 		BitSet s = new BitSet();
     91 		s.add(a);
     92 		s.add(b);
     93 		s.add(c);
     94 		return s;
     95 	}
     96 
     97 	public static BitSet of(int a, int b, int c, int d) {
     98 		BitSet s = new BitSet();
     99 		s.add(a);
    100 		s.add(b);
    101 		s.add(c);
    102 		s.add(d);
    103 		return s;
    104 	}
    105 
    106 	/** return this | a in a new set */
    107 	public BitSet or(BitSet a) {
    108 		if ( a==null ) {
    109 			return this;
    110 		}
    111 		BitSet s = (BitSet)this.clone();
    112 		s.orInPlace(a);
    113 		return s;
    114 	}
    115 
    116 	/** or this element into this set (grow as necessary to accommodate) */
    117 	public void add(int el) {
    118 		int n = wordNumber(el);
    119 		if (n >= bits.length) {
    120 			growToInclude(el);
    121 		}
    122 		bits[n] |= bitMask(el);
    123 	}
    124 
    125 	/**
    126 	 * Grows the set to a larger number of bits.
    127 	 * @param bit element that must fit in set
    128 	 */
    129 	public void growToInclude(int bit) {
    130 		int newSize = Math.max(bits.length << 1, numWordsToHold(bit));
    131 		long newbits[] = new long[newSize];
    132 		System.arraycopy(bits, 0, newbits, 0, bits.length);
    133 		bits = newbits;
    134 	}
    135 
    136 	public void orInPlace(BitSet a) {
    137 		if ( a==null ) {
    138 			return;
    139 		}
    140 		// If this is smaller than a, grow this first
    141 		if (a.bits.length > bits.length) {
    142 			setSize(a.bits.length);
    143 		}
    144 		int min = Math.min(bits.length, a.bits.length);
    145 		for (int i = min - 1; i >= 0; i--) {
    146 			bits[i] |= a.bits[i];
    147 		}
    148 	}
    149 
    150 	/**
    151 	 * Sets the size of a set.
    152 	 * @param nwords how many words the new set should be
    153 	 */
    154 	private void setSize(int nwords) {
    155 		long newbits[] = new long[nwords];
    156 		int n = Math.min(nwords, bits.length);
    157 		System.arraycopy(bits, 0, newbits, 0, n);
    158 		bits = newbits;
    159 	}
    160 
    161     private final static long bitMask(int bitNumber) {
    162         int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS
    163         return 1L << bitPosition;
    164     }
    165 
    166     public Object clone() {
    167         BitSet s;
    168         try {
    169             s = (BitSet)super.clone();
    170             s.bits = new long[bits.length];
    171             System.arraycopy(bits, 0, s.bits, 0, bits.length);
    172         }
    173         catch (CloneNotSupportedException e) {
    174             throw new InternalError();
    175         }
    176         return s;
    177     }
    178 
    179     public int size() {
    180         int deg = 0;
    181         for (int i = bits.length - 1; i >= 0; i--) {
    182             long word = bits[i];
    183             if (word != 0L) {
    184                 for (int bit = BITS - 1; bit >= 0; bit--) {
    185                     if ((word & (1L << bit)) != 0) {
    186                         deg++;
    187                     }
    188                 }
    189             }
    190         }
    191         return deg;
    192     }
    193 
    194     public boolean equals(Object other) {
    195         if ( other == null || !(other instanceof BitSet) ) {
    196             return false;
    197         }
    198 
    199         BitSet otherSet = (BitSet)other;
    200 
    201         int n = Math.min(this.bits.length, otherSet.bits.length);
    202 
    203         // for any bits in common, compare
    204         for (int i=0; i<n; i++) {
    205             if (this.bits[i] != otherSet.bits[i]) {
    206                 return false;
    207             }
    208         }
    209 
    210         // make sure any extra bits are off
    211 
    212         if (this.bits.length > n) {
    213             for (int i = n+1; i<this.bits.length; i++) {
    214                 if (this.bits[i] != 0) {
    215                     return false;
    216                 }
    217             }
    218         }
    219         else if (otherSet.bits.length > n) {
    220             for (int i = n+1; i<otherSet.bits.length; i++) {
    221                 if (otherSet.bits[i] != 0) {
    222                     return false;
    223                 }
    224             }
    225         }
    226 
    227         return true;
    228     }
    229 
    230     public boolean member(int el) {
    231 		if ( el<0 ) {
    232 			return false;
    233 		}
    234         int n = wordNumber(el);
    235         if (n >= bits.length) return false;
    236         return (bits[n] & bitMask(el)) != 0;
    237     }
    238 
    239 	// remove this element from this set
    240 	public void remove(int el) {
    241 		int n = wordNumber(el);
    242 		if (n < bits.length) {
    243 			bits[n] &= ~bitMask(el);
    244 		}
    245 	}
    246 
    247     public boolean isNil() {
    248         for (int i = bits.length - 1; i >= 0; i--) {
    249             if (bits[i] != 0) return false;
    250         }
    251         return true;
    252     }
    253 
    254     private final int numWordsToHold(int el) {
    255         return (el >> LOG_BITS) + 1;
    256     }
    257 
    258     public int numBits() {
    259         return bits.length << LOG_BITS; // num words * bits per word
    260     }
    261 
    262     /** return how much space is being used by the bits array not
    263      *  how many actually have member bits on.
    264      */
    265     public int lengthInLongWords() {
    266         return bits.length;
    267     }
    268 
    269     /**Is this contained within a? */
    270     /*
    271 	public boolean subset(BitSet a) {
    272         if (a == null || !(a instanceof BitSet)) return false;
    273         return this.and(a).equals(this);
    274     }
    275 	*/
    276 
    277     public int[] toArray() {
    278         int[] elems = new int[size()];
    279         int en = 0;
    280         for (int i = 0; i < (bits.length << LOG_BITS); i++) {
    281             if (member(i)) {
    282                 elems[en++] = i;
    283             }
    284         }
    285         return elems;
    286     }
    287 
    288     public long[] toPackedArray() {
    289         return bits;
    290     }
    291 
    292 	private final static int wordNumber(int bit) {
    293 		return bit >> LOG_BITS; // bit / BITS
    294 	}
    295 
    296 	public String toString() {
    297 		return toString(null);
    298 	}
    299 
    300 	public String toString(String[] tokenNames) {
    301 		StringBuffer buf = new StringBuffer();
    302 		String separator = ",";
    303 		boolean havePrintedAnElement = false;
    304 		buf.append('{');
    305 
    306 		for (int i = 0; i < (bits.length << LOG_BITS); i++) {
    307 			if (member(i)) {
    308 				if (i > 0 && havePrintedAnElement ) {
    309 					buf.append(separator);
    310 				}
    311 				if ( tokenNames!=null ) {
    312 					buf.append(tokenNames[i]);
    313 				}
    314 				else {
    315 					buf.append(i);
    316 				}
    317 				havePrintedAnElement = true;
    318 			}
    319 		}
    320 		buf.append('}');
    321 		return buf.toString();
    322 	}
    323 
    324 
    325 }
    326