1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [The "BSD license"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2010 Terence Parr 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Redistribution and use in source and binary forms, with or without 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * modification, are permitted provided that the following conditions 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * are met: 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1. Redistributions of source code must retain the above copyright 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer. 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 2. Redistributions in binary form must reproduce the above copyright 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer in the 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * documentation and/or other materials provided with the distribution. 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 3. The name of the author may not be used to endorse or promote products 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * derived from this software without specific prior written permission. 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpackage org.antlr.misc; 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.analysis.Label; 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.tool.Grammar; 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.Collection; 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.Iterator; 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.List; 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.Map; 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/**A BitSet to replace java.util.BitSet. 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Primary differences are that most set operators return new sets 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * as opposed to oring and anding "in place". Further, a number of 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * operations were added. I cannot contain a BitSet because there 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is no way to access the internal bits (which I need for speed) 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * and, because it is final, I cannot subclass to add functionality. 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Consider defining set degree. Without access to the bits, I must 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * call a method n times to test the ith bit...ack! 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Also seems like or() from util is wrong when size of incoming set is bigger 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * than this.bits.length. 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * @author Terence Parr 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpublic class BitSet implements IntSet, Cloneable { 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected final static int BITS = 64; // number of bits / long 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected final static int LOG_BITS = 6; // 2^6 == 64 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* We will often need to do a mod operator (i mod nbits). Its 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * turns out that, for powers of two, this mod operation is 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * same as (i & (nbits-1)). Since mod is slow, we use a 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * precomputed mod mask to do the mod instead. 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected final static int MOD_MASK = BITS - 1; 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** The actual data bits */ 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected long bits[]; 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Construct a bitset of size one word (64 bits) */ 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public BitSet() { 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this(BITS); 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Construction from a static array of longs */ 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public BitSet(long[] bits_) { 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits = bits_; 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Construct a bitset given the size 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * @param nbits The size of the bitset in bits 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public BitSet(int nbits) { 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits = new long[((nbits - 1) >> LOG_BITS) + 1]; 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** or this element into this set (grow as necessary to accommodate) */ 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void add(int el) { 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("add("+el+")"); 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = wordNumber(el); 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("word number is "+n); 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("bits.length "+bits.length); 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (n >= bits.length) { 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver growToInclude(el); 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits[n] |= bitMask(el); 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void addAll(IntSet set) { 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( set instanceof BitSet ) { 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.orInPlace((BitSet)set); 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( set instanceof IntervalSet ) { 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet other = (IntervalSet)set; 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // walk set and add each interval 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator iter = other.intervals.iterator(); iter.hasNext();) { 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval I = (Interval) iter.next(); 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.orInPlace(BitSet.range(I.a,I.b)); 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new IllegalArgumentException("can't add "+ 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver set.getClass().getName()+ 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " to BitSet"); 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void addAll(int[] elements) { 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( elements==null ) { 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < elements.length; i++) { 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int e = elements[i]; 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver add(e); 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void addAll(Iterable elements) { 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( elements==null ) { 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Iterator it = elements.iterator(); 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while (it.hasNext()) { 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Object o = (Object) it.next(); 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !(o instanceof Integer) ) { 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new IllegalArgumentException(); 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer eI = (Integer)o; 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver add(eI.intValue()); 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = elements.size(); 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Object o = elements.get(i); 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !(o instanceof Integer) ) { 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new IllegalArgumentException(); 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer eI = (Integer)o; 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver add(eI.intValue()); 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntSet and(IntSet a) { 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver BitSet s = (BitSet)this.clone(); 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.andInPlace((BitSet)a); 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s; 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void andInPlace(BitSet a) { 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int min = Math.min(bits.length, a.bits.length); 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = min - 1; i >= 0; i--) { 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits[i] &= a.bits[i]; 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // clear all bits in this not present in a (if this bigger than a). 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = min; i < bits.length; i++) { 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits[i] = 0; 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver private final static long bitMask(int bitNumber) { 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 1L << bitPosition; 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void clear() { 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = bits.length - 1; i >= 0; i--) { 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits[i] = 0; 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void clear(int el) { 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = wordNumber(el); 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (n >= bits.length) { // grow as necessary to accommodate 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver growToInclude(el); 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits[n] &= ~bitMask(el); 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Object clone() { 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver BitSet s; 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver try { 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s = (BitSet)super.clone(); 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.bits = new long[bits.length]; 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.arraycopy(bits, 0, s.bits, 0, bits.length); 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver catch (CloneNotSupportedException e) { 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new InternalError(); 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s; 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int size() { 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int deg = 0; 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = bits.length - 1; i >= 0; i--) { 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver long word = bits[i]; 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (word != 0L) { 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int bit = BITS - 1; bit >= 0; bit--) { 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ((word & (1L << bit)) != 0) { 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver deg++; 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return deg; 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean equals(Object other) { 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( other == null || !(other instanceof BitSet) ) { 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver BitSet otherSet = (BitSet)other; 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = Math.min(this.bits.length, otherSet.bits.length); 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // for any bits in common, compare 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i=0; i<n; i++) { 226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (this.bits[i] != otherSet.bits[i]) { 227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // make sure any extra bits are off 232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (this.bits.length > n) { 234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = n+1; i<this.bits.length; i++) { 235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (this.bits[i] != 0) { 236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if (otherSet.bits.length > n) { 241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = n+1; i<otherSet.bits.length; i++) { 242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (otherSet.bits[i] != 0) { 243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Grows the set to a larger number of bits. 253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * @param bit element that must fit in set 254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void growToInclude(int bit) { 256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int newSize = Math.max(bits.length << 1, numWordsToHold(bit)); 257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver long newbits[] = new long[newSize]; 258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.arraycopy(bits, 0, newbits, 0, bits.length); 259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits = newbits; 260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean member(int el) { 263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = wordNumber(el); 264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (n >= bits.length) return false; 265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return (bits[n] & bitMask(el)) != 0; 266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Get the first element you find and return it. Return Label.INVALID 269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * otherwise. 270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int getSingleElement() { 272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < (bits.length << LOG_BITS); i++) { 273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (member(i)) { 274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return i; 275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return Label.INVALID; 278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean isNil() { 281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = bits.length - 1; i >= 0; i--) { 282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bits[i] != 0) return false; 283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntSet complement() { 288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver BitSet s = (BitSet)this.clone(); 289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.notInPlace(); 290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s; 291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntSet complement(IntSet set) { 294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( set==null ) { 295324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return this.complement(); 296324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 297324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return set.subtract(this); 298324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 299324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 300324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void notInPlace() { 301324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = bits.length - 1; i >= 0; i--) { 302324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits[i] = ~bits[i]; 303324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 304324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 305324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 306324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** complement bits in the range 0..maxBit. */ 307324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void notInPlace(int maxBit) { 308324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver notInPlace(0, maxBit); 309324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 310324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 311324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** complement bits in the range minBit..maxBit.*/ 312324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void notInPlace(int minBit, int maxBit) { 313324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // make sure that we have room for maxBit 314324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver growToInclude(maxBit); 315324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = minBit; i <= maxBit; i++) { 316324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = wordNumber(i); 317324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits[n] ^= bitMask(i); 318324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 319324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 320324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 321324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver private final int numWordsToHold(int el) { 322324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return (el >> LOG_BITS) + 1; 323324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 324324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 325324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static BitSet of(int el) { 326324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver BitSet s = new BitSet(el + 1); 327324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.add(el); 328324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s; 329324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 330324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 331324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static BitSet of(Collection elements) { 332324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver BitSet s = new BitSet(); 333324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Iterator iter = elements.iterator(); 334324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while (iter.hasNext()) { 335324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer el = (Integer) iter.next(); 336324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.add(el.intValue()); 337324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 338324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s; 339324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 340324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 341324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static BitSet of(IntSet set) { 342324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( set==null ) { 343324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 344324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 345324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 346324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( set instanceof BitSet ) { 347324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return (BitSet)set; 348324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 349324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( set instanceof IntervalSet ) { 350324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver BitSet s = new BitSet(); 351324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.addAll(set); 352324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s; 353324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 354324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new IllegalArgumentException("can't create BitSet from "+set.getClass().getName()); 355324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 356324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 357324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static BitSet of(Map elements) { 358324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return BitSet.of(elements.keySet()); 359324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 360324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 361324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static BitSet range(int a, int b) { 362324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver BitSet s = new BitSet(b + 1); 363324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = a; i <= b; i++) { 364324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = wordNumber(i); 365324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.bits[n] |= bitMask(i); 366324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 367324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s; 368324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 369324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 370324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** return this | a in a new set */ 371324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntSet or(IntSet a) { 372324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( a==null ) { 373324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return this; 374324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 375324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver BitSet s = (BitSet)this.clone(); 376324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.orInPlace((BitSet)a); 377324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s; 378324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 379324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 380324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void orInPlace(BitSet a) { 381324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( a==null ) { 382324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 383324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 384324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // If this is smaller than a, grow this first 385324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (a.bits.length > bits.length) { 386324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver setSize(a.bits.length); 387324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 388324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int min = Math.min(bits.length, a.bits.length); 389324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = min - 1; i >= 0; i--) { 390324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits[i] |= a.bits[i]; 391324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 392324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 393324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 394324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // remove this element from this set 395324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void remove(int el) { 396324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = wordNumber(el); 397324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (n >= bits.length) { 398324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver growToInclude(el); 399324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 400324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits[n] &= ~bitMask(el); 401324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 402324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 403324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 404324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Sets the size of a set. 405324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * @param nwords how many words the new set should be 406324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 407324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver private void setSize(int nwords) { 408324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver long newbits[] = new long[nwords]; 409324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = Math.min(nwords, bits.length); 410324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.arraycopy(bits, 0, newbits, 0, n); 411324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits = newbits; 412324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 413324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 414324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int numBits() { 415324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return bits.length << LOG_BITS; // num words * bits per word 416324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 417324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 418324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** return how much space is being used by the bits array not 419324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * how many actually have member bits on. 420324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 421324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int lengthInLongWords() { 422324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return bits.length; 423324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 424324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 425324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /**Is this contained within a? */ 426324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean subset(BitSet a) { 427324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (a == null) return false; 428324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return this.and(a).equals(this); 429324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 430324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 431324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /**Subtract the elements of 'a' from 'this' in-place. 432324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Basically, just turn off all bits of 'this' that are in 'a'. 433324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 434324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void subtractInPlace(BitSet a) { 435324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (a == null) return; 436324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // for all words of 'a', turn off corresponding bits of 'this' 437324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < bits.length && i < a.bits.length; i++) { 438324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bits[i] &= ~a.bits[i]; 439324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 440324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 441324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 442324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntSet subtract(IntSet a) { 443324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (a == null || !(a instanceof BitSet)) return null; 444324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 445324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver BitSet s = (BitSet)this.clone(); 446324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.subtractInPlace((BitSet)a); 447324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s; 448324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 449324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 450324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public List toList() { 451324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new NoSuchMethodError("BitSet.toList() unimplemented"); 452324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 453324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 454324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int[] toArray() { 455324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int[] elems = new int[size()]; 456324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int en = 0; 457324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < (bits.length << LOG_BITS); i++) { 458324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (member(i)) { 459324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver elems[en++] = i; 460324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 461324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 462324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return elems; 463324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 464324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 465324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public long[] toPackedArray() { 466324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return bits; 467324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 468324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 469324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String toString() { 470324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return toString(null); 471324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 472324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 473324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Transform a bit set into a string by formatting each element as an integer 474324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * separator The string to put in between elements 475324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * @return A commma-separated list of values 476324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 477324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String toString(Grammar g) { 478324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver StringBuffer buf = new StringBuffer(); 479324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver String separator = ","; 480324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean havePrintedAnElement = false; 481324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append('{'); 482324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 483324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < (bits.length << LOG_BITS); i++) { 484324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (member(i)) { 485324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (i > 0 && havePrintedAnElement ) { 486324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(separator); 487324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 488324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( g!=null ) { 489324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(g.getTokenDisplayName(i)); 490324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 491324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 492324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(i); 493324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 494324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver havePrintedAnElement = true; 495324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 496324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 497324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append('}'); 498324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return buf.toString(); 499324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 500324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 501324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /**Create a string representation where instead of integer elements, the 502324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ith element of vocabulary is displayed instead. Vocabulary is a Vector 503324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of Strings. 504324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * separator The string to put in between elements 505324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * @return A commma-separated list of character constants. 506324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 507324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String toString(String separator, List vocabulary) { 508324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (vocabulary == null) { 509324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return toString(null); 510324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 511324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver String str = ""; 512324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < (bits.length << LOG_BITS); i++) { 513324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (member(i)) { 514324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (str.length() > 0) { 515324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver str += separator; 516324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 517324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (i >= vocabulary.size()) { 518324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver str += "'" + (char)i + "'"; 519324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 520324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if (vocabulary.get(i) == null) { 521324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver str += "'" + (char)i + "'"; 522324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 523324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 524324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver str += (String)vocabulary.get(i); 525324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 526324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 527324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 528324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return str; 529324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 530324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 531324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 532324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Dump a comma-separated list of the words making up the bit set. 533324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Split each 64 bit number into two more manageable 32 bit numbers. 534324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This generates a comma-separated list of C++-like unsigned long constants. 535324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 536324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String toStringOfHalfWords() { 537324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver StringBuffer s = new StringBuffer(); 538324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < bits.length; i++) { 539324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (i != 0) s.append(", "); 540324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver long tmp = bits[i]; 541324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tmp &= 0xFFFFFFFFL; 542324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.append(tmp); 543324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.append("UL"); 544324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.append(", "); 545324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tmp = bits[i] >>> 32; 546324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tmp &= 0xFFFFFFFFL; 547324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.append(tmp); 548324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.append("UL"); 549324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 550324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s.toString(); 551324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 552324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 553324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 554324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Dump a comma-separated list of the words making up the bit set. 555324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This generates a comma-separated list of Java-like long int constants. 556324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 557324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String toStringOfWords() { 558324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver StringBuffer s = new StringBuffer(); 559324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < bits.length; i++) { 560324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (i != 0) s.append(", "); 561324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.append(bits[i]); 562324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.append("L"); 563324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 564324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s.toString(); 565324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 566324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 567324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String toStringWithRanges() { 568324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return toString(); 569324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 570324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 571324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver private final static int wordNumber(int bit) { 572324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return bit >> LOG_BITS; // bit / BITS 573324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 574324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 575