/* * @(#)SmallSet.java 25 July 2007 * * Copyright 2007 * College of Computer and Information Science * Northeastern University * Boston, MA 02115 * * The Java Power Tools software may be used for educational * purposes as long as this copyright notice is retained intact * at the top of all source files. * * To discuss possible commercial use of this software, * contact Richard Rasala at Northeastern University, * College of Computer and Information Science, * 617-373-2462 or rasala@ccs.neu.edu. * * The Java Power Tools software has been designed and built * in collaboration with Viera Proulx and Jeff Raab. * * Should this software be modified, the words "Modified from * Original" must be included as a comment below this notice. * * All publication rights are retained. This software or its * documentation may not be published in any media either * in whole or in part without explicit permission. * * This software was created with support from Northeastern * University and from NSF grant DUE-9950829. */ package edu.neu.ccs; import edu.neu.ccs.*; /** *

Class SmallSet is a class that represents a * set of int values between 0 and 31 as the bits * in a single int state. This implements as a * class the traditional bit representation of a small set.

* *

The internal int state representation of the * set as bits is returned by the getState method * and also by the hashCode method.

* *

Using the appropriate constructor, one can restrict the * set to contain elements between given minimum and maximum * elements rather than cover the full range from 0 to 31.

* *

The method makeNextSubset provides an * efficient mechanism for iterating through the subsets * of a set.

* * @author Richard Rasala * @version 2.6.0 * @since 2.6.0 */ public class SmallSet implements Comparable, Stringable { /** The minimum set value in any set. */ public static final int MIN = 0; /** The maximum set value in any set. */ public static final int MAX = 31; /** The maximum number of elements in a set. */ public static final int MAXSIZE = 32; /** The bit MASK with all 1's bits. */ public static final int MASK = -1; /** *

The integer BITS[i] has a 1-bit * in position i and a 0-bit elsewhere.

*/ private static int[] BITS = new int[MAXSIZE]; /** *

The integer BITS[i] has a 0-bit * in position i and a 1-bit elsewhere.

*/ private static int[] COBITS = new int[MAXSIZE]; /** *

The integer LOBITS[i] has a 1-bit * in the positions from 0 to * i and a 0-bit elsewhere.

*/ private static int[] LOBITS = new int[MAXSIZE]; /** *

The integer HIBITS[i] has a 1-bit * in the positions from i to * 31 and a 0-bit elsewhere.

*/ private static int[] HIBITS = new int[MAXSIZE]; /* Initialization of the bit values. */ static { BITS[0] = 1; for (int i = 1; i <= MAX; i++) BITS[i] = BITS[i-1] << 1; for (int i = 0; i <= MAX; i++) COBITS[i] = MASK - BITS[i]; LOBITS[0] = BITS[0]; for (int i = 1; i <= MAX; i++) LOBITS[i] = LOBITS[i-1] | BITS[i]; HIBITS[MAX] = BITS[MAX]; for (int i = (MAX - 1); i >= 0; i--) HIBITS[i] = HIBITS[i+1] | BITS[i]; } /** * The representation of the set as an integer * which equals its hash code. */ private int hash = 0; /** * The number of elements in this set, that is, * the count of 1-bits in the representation. */ private int size = 0; /** *

The boolean that records whether or not the bit * arrays associated with this set have been constructed * and are valid.

*/ private boolean bitsValid = false; /** *

If bitsValid is true, then this array * will contain the bit masks BITS[i] that * correspond to the elements i in this set.

* *

The bit masks will be in increasing order and will * be in the first size slots.

* *

All methods that change the state of this set will * make the boolean bitsValid false.


     * 
     * This array will be constructed only if needed for
     * use in the method makeNextSubset.
     * If constructed, it will be reused.
     */
    private int[] bits = null;
    
    
    /**
     * If bitsValid is true, then this array
     * will contain in position i the sum of
     * the bit masks bits[j] for j
     * from 0 to i.
     * 
     * The bit masks will be in the first size
     * slots.
     * 
     * All methods that change the state of this set will
     * make the boolean bitsValid false.

     * 
     * This array will be constructed only if needed for
     * use in the method makeNextSubset.
     * If constructed, it will be reused.
     */
    private int[] lobits = null;
    
    
    /**
     * If bitsValid is true, then this array
     * will contain in position i the sum of
     * the bit masks bits[j] for j
     * from i to (size-1).
     * 
     * The bit masks will be in the first size
     * slots.
     * 
     * All methods that change the state of this set will
     * make the boolean bitsValid false.

     * 
     * This array will be constructed only if needed for
     * use in the method makeNextSubset.
     * If constructed, it will be reused.
     */
    private int[] hibits = null;
    
    
    /**The minimum element permitted in this set. */
    private int minimum = MIN;
    
    
    /**The maximum element permitted in this set. */
    private int maximum = MAX;
    
    
    /**
     * The bit mask representing all possible elements
     * permitted in this set.
     */
    private int mask = MASK;
    
    
    /**
     * The number of 1 bits in mask.
     */
    private int masksize = MAX + 1;
    
    
    /**
     * The default constructor that creates an empty set
     * with minimum element 0 and maximum element 31.
     */
    public SmallSet() {}
    
    
    /**
     * The constructor that makes a set with minimum 0
     * and maximum 31 whose elements are initialized
     * by the data in the given String.
     * 
     * See fromStringData for a discussion
     * of how the String data is read.
     * 
     * @param data the data to initialize the set
     */
    public SmallSet(String data) {
        fromStringData(data);
    }
    
    
    /**
     * The default constructor that creates an empty set
     * with the given minimum and maximum elements.
     * 
     * Suitable error checking will be done to force
     * minimum and maximum to fall between 0 and 31
     * and to be in order.
     * 
     * @param minimum the minimum element
     * @param maximum the maximum element
     */
    public SmallSet(int minimum, int maximum) {
        minimum = (minimum <= MIN) ? MIN :
            (minimum >= MAX) ? MAX : minimum;
        
        maximum = (maximum <= MIN) ? MIN :
            (maximum >= MAX) ? MAX : maximum;
        
        if (maximum < minimum) {
            int t = minimum;
            minimum = maximum;
            maximum = t;
        }
        
        this.minimum = minimum;
        this.maximum = maximum;
        this.mask = HIBITS[minimum] & LOBITS[maximum];
        this.masksize = maximum - minimum + 1;
    }
    
    
    /**
     * The constructor that makes a set with the given
     * minimum and maximum whose elements are initialized
     * by the data in the given String.
     * 
     * Suitable error checking will be done to force
     * minimum and maximum to fall between 0 and 31
     * and to be in order.
     * 
     * See fromStringData for a discussion
     * of how the String data is read.
     * 
     * @param minimum the minimum element
     * @param maximum the maximum element
     * @param data the data to initialize the set
     */
    public SmallSet(int minimum, int maximum, String data) {
        this(minimum, maximum);
        fromStringData(data);
    }
    
    
    /**
     * The constructor that makes a clone of the given set.
     * 
     * @param set to clone
     */
    public SmallSet(SmallSet set) {
        if (set == null)
            return;
        
        this.size = set.size;
        this.hash = set.hash;
        this.minimum = set.minimum;
        this.maximum = set.maximum;
        this.mask = set.mask;
        this.masksize = set.masksize;
    }
    
    
    /**
     * Returns the size of this set.
     */
    public final int size() {
        return size;
    }
    
    
    /**
     * Returns the minimum permitted element in this set.
     */
    public final int getMinimum() {
        return minimum;
    }
    
    
    /**
     * Returns the maximum permitted element in this set.
     */
    public final int getMaximum() {
        return maximum;
    }
    
    
    /**
     * Returns true if this set is empty.
     */
    public final boolean isEmpty() {
        return hash == 0;
    }
    
    
    /**
     * Returns true if this set is full,
     * that is, if it contains all values
     * between minimum and maximum.
     */
    public final boolean isFull() {
        return hash == mask;
    }
    
    
    /**
     * Make this set empty.
     */
    public final void makeEmpty() {
        setState(0);
    }
    
    
    /**
     * Make this set full.
     */
    public final void makeFull() {
        setState(mask);
    }
    
    
    /**
     * Sets the integer state of this set.
     * 
     * The state set restricts the elements to be
     * between the minimum and the maximum.
     * 
     * Returns true if the internal state has changed.
     * 
     * @param state the state for the set
     */
    public final boolean setState(int state) {
        int oldhash = hash;
        
        hash = state & mask;
        
        if (hash == oldhash)
            return false;
        
        resetCount();
        bitsValid = false;
        
        return true;
    }
    
    
    /**
     * Returns the integer state of this set.
     * 
     * Identical to hashCode.
     */
    public final int getState() {
        return hash;
    }
    
    
    /**
     * Returns true if this set has the given element
     * as one of its elements.
     * 
     * @param element the element to check
     */
    public final boolean hasElement(int element) {
        if ((element < minimum) || (element > maximum))
            return false;
        
        return (hash & BITS[element]) != 0;
    }
    
    
    /**
     * Adds the given element to this set provided
     * that the element is in the range from
     * minimum to maximum.
     * 
     * Returns true if the internal state has changed.
     * 
     * @param element the element to add
     */
    public final boolean addElement(int element) {
        if ((element < minimum) || (element > maximum))
            return false;
        
        boolean hasElement = (hash & BITS[element]) != 0;
        
        if (hasElement)
            return false;
        
        hash = hash | BITS[element];
        size++;
        bitsValid = false;
        
        return true;
    }
    
    
    /**
     * Prunes the given element from this set provided
     * that the element is in the range from
     * minimum to maximum.
     * 
     * Returns true if the internal state has changed.
     * 
     * @param element the element to prune
     */
    public final boolean pruneElement(int element) {
        if ((element < minimum) || (element > maximum))
            return false;
        
        boolean hasElement = (hash & BITS[element]) != 0;
        
        if (! hasElement)
            return false;
        
        hash = hash & COBITS[element];
        size--;
        bitsValid = false;
        
        return true;
    }
    
    
    /**
     * If the given element is in the set then prune it,
     * otherwise add it.
     * 
     * Normally, returns true.  However, returns false
     * if element is not in the range from
     * minimum to maximum.
     * 
     * @param element the element to toggle
     */
    public final boolean toggleElement(int element) {
        if ((element < minimum) || (element > maximum))
            return false;
        
        boolean hasElement = (hash & BITS[element]) != 0;
        
        if (hasElement) {
            hash = hash & COBITS[element];
            size--;
        }
        else {
            hash = hash | BITS[element];
            size++;
        }
        
        bitsValid = false;
        return true;
    }
    
    
    /**
     * Sets this set to have the given element as its only
     * element provided that the element is in the range from
     * minimum to maximum.
     * 
     * Returns true if the internal state has changed.
     * 
     * @param element the element to set
     */
    public final boolean setToElement(int element) {
        if ((element < minimum) || (element > maximum))
            return false;
        
        int oldhash = hash;
        
        hash = BITS[element];
        
        if (hash == oldhash)
            return false;
        
        size = 1;
        bitsValid = false;
        
        return true;
    }
    
    
    /**
     * Adds the elements from the given array of elements
     * to this set.  Omits any elements that fall outside
     * the set bounds minimum and maximum.
     * 
     * Returns true if the internal state has changed.
     * 
     * @param elements the elements to place in this set
     */
    public final boolean addElements(int[] elements) {
        if (elements == null)
            return false;
        
        int oldhash = hash;
        
        int length = elements.length;
        
        for (int i = 0; i < length; i++) {
            int element = elements[i];
            
            if ((element < minimum) || (element > maximum))
                continue;
            
            hash |= BITS[element];
        }
        
        if (hash == oldhash)
            return false;
        
        resetCount();
        bitsValid = false;
        
        return true;
    }
    
    
    /**
     * Prunes the elements from the given array of elements
     * from this set.
     * 
     * Returns true if the internal state has changed.
     * 
     * @param elements the elements to place in this set
     */
    public final boolean pruneElements(int[] elements) {
        if (elements == null)
            return false;
        
        int oldhash = hash;
        
        int length = elements.length;
        
        for (int i = 0; i < length; i++) {
            int element = elements[i];
            
            if ((element < minimum) || (element > maximum))
                continue;
            
            hash &= COBITS[element];
        }
        
        if (hash == oldhash)
            return false;
        
        resetCount();
        bitsValid = false;
        
        return true;
    }
    
    
    /**
     * Sets the elements of this set to the elements from
     * the given array of elements.  Omits any elements that
     * fall outside the set bounds minimum and maximum.
     * 
     * Returns true if the internal state has changed.
     * 
     * @param elements the elements to place in this set
     */
    public final boolean setToElements(int[] elements) {
        if (elements == null)
            return false;
        
        int oldhash = hash;
        
        hash = 0;
        
        int length = elements.length;
        
        for (int i = 0; i < length; i++) {
            int element = elements[i];
            
            if ((element < minimum) || (element > maximum))
                continue;
            
            hash |= BITS[element];
        }
        
        if (hash == oldhash)
            return false;
        
        resetCount();
        bitsValid = false;
        
        return true;
    }
    
    
    /**
     * Adds the elements from min to max inclusive to
     * this set but omits any elements that fall outside
     * the set bounds minimum and maximum.
     * 
     * Returns true if the internal state has changed.
     * 
     * @param min the minimum element
     * @param max the maximum element
     */
    public final boolean addRange(int min, int max) {
        int oldhash = hash;
        
        min = (min <= minimum) ? minimum :
            (min >= maximum) ? maximum : min;
        
        max = (max <= minimum) ? minimum :
            (max >= maximum) ? maximum : max;
        
        if (max < min) {
            int t = min;
            min = max;
            max = t;
        }
        
        hash |= (HIBITS[min] & LOBITS[max]);
        
        if (hash == oldhash)
            return false;
       
        resetCount();
        bitsValid = false;
        
        return true;
    }
    
    
    /**
     * Prunes the elements from min to max inclusive from
     * this set.
     * 
     * Returns true if the internal state has changed.
     * 
     * @param min the minimum element
     * @param max the maximum element
     */
    public final boolean pruneRange(int min, int max) {
        int oldhash = hash;
        
        min = (min <= minimum) ? minimum :
            (min >= maximum) ? maximum : min;
        
        max = (max <= minimum) ? minimum :
            (max >= maximum) ? maximum : max;
        
        if (max < min) {
            int tem = min;
            min = max;
            max = tem;
        }
        
        hash &= (mask - (HIBITS[min] & LOBITS[max]));
        
        if (hash == oldhash)
            return false;
       
        resetCount();
        bitsValid = false;
        
        return true;
    }
    
    
    /**
     * Sets the elements of this set to the elements from
     * min to max inclusive.  Omits any elements that fall
     * outside the set bounds minimum and maximum.
     * 
     * Returns true if the internal state has changed.
     * 
     * @param min the minimum element
     * @param max the maximum element
     */
    public final boolean setToRange(int min, int max) {
        int oldhash = hash;
        
        min = (min <= minimum) ? minimum :
            (min >= maximum) ? maximum : min;
        
        max = (max <= minimum) ? minimum :
            (max >= maximum) ? maximum : max;
        
        if (max < min) {
            int tem = min;
            min = max;
            max = tem;
        }
        
        hash = HIBITS[min] & LOBITS[max];
        
        if (hash == oldhash)
            return false;
        
        size = max - min + 1;
        bitsValid = false;
        
        return true;
    }
    
    
    /**
     * Adds the given set to this set but omits any
     * elements in the given set that fall outside the
     * bounds of this set.
     * 
     * Returns true if the internal state has changed.
     * 
     * @param set the set to add to this set
     */
    public final boolean unionSet(SmallSet set) {
        if (set == null)
            return false;
        
        int state = hash | set.hash;
        
        return setState(state);
    }
    
    
    /**
     * Replaces this set with the intersection of this
     * set and the given set.
     * 
     * Returns true if the internal state has changed.
     * 
     * @param set the set to intersect with this set
     */
    public final boolean intersectSet(SmallSet set) {
        if (set == null)
            return false;
        
        int state = hash & set.hash;
        
        return setState(state);
    }
    
    
    /**
     * Prunes this set by removing the elements in common
     * with the given set, that is, replaces this set by its
     * set difference with the given set.
     * 
     * Returns true if the internal state has changed.
     * 
     * @param set the set to prune from this set
     */
    public final boolean pruneSet(SmallSet set) {
        if (set == null)
            return false;
        
        int state = hash - (hash & set.hash);
        
        return setState(state);
    }
    
    
    /**
     * Replaces the set by its complement relative
     * to the range from minimum to maximum.
     *
     * The set is always changed by this operation.
     */
    public final void complement() {
        hash = mask - hash;
        size = masksize - size;
        bitsValid = false;
    }
    
    
    /**
     * Returns true if this set contains
     * the given set as a subset.
     * 
     * Does not test whether or not the two
     * sets have the same bounds.
     * 
     * @param set the set to test
     */
    public final boolean contains(SmallSet set) {
        if (set == null)
            return false;
        
        return set.hash == (hash & set.hash);
    }
    
    
    /**
     * Returns true if this set is a subset
     * of the given set.
     * 
     * Does not test whether or not the two
     * sets have the same bounds.
     * 
     * @param set the set to test
     */
    public final boolean isSubset(SmallSet set) {
        if (set == null)
            return false;
        
        return hash == (hash & set.hash);
    }
    
    
    /**
     * Returns the integer state of this set.
     * 
     * Identical to getState.
     */
    public final int hashCode() {
        return hash;
    }
    
    
    /**
     * Returns true if the given Object is an
     * instance of SmallSet and if
     * both sets have the same elements.
     * 
     * Does not test whether or not the two
     * sets have the same bounds.
     */
    public final boolean equals(Object object) {
        if (object instanceof SmallSet) {
            SmallSet set = (SmallSet)object;
            
            return hash == set.hash;
        }
        
        return false;
    }
    
    
    /**
     * If the given object is a SmallSet,
     * then returns -1, 0, +1 depending on whether this set
     * precedes the given set, is equal to the given set,
     * or follows the given set.
     * 
     * Throws ClassCastException if the
     * given object is not a SmallSet.
     * 
     * The details of the computation are as follows.  Let
     * set represent the given object cast to
     * SmallSet.
     * 
     * If this set equals set, return 0.
     * 
     * Next, order sets by size:
     *  
     * If this set has more elements than set,
     * return +1.
     * 
     * If this set has less elements than set,
     * return -1.
     * 
     * Otherwise, order sets of the same size as follows.
     * Consider the largest bit index i such
     * that this set and set disagree at that
     * index.  Then if i is an element of this
     * set return +1 and if i is an element of
     * set return -1.
     * 
     * 
     * An equivalent way to think about set ordering is
     * that sets of the same size are ordered according to
     * their ordering as unsigned integers.  In Java this
     * is a bit more complicated to compute than need be
     * because unsigned integer is not a supported type in
     * Java.
     * 
     * Does not test whether or not the two
     * sets have the same bounds.
     */
    public final int compareTo(Object object) {
        String message = "";
        
        if (object instanceof SmallSet) {
            SmallSet set = (SmallSet) object;
            
            int delta_hash = hash - set.hash;
            
            // case; set equality
            if (delta_hash == 0)
                return 0;
            
            int delta_size = size - set.size;
            
            // case: set size not equal
            if (delta_size < 0)
                return -1;
            
            if (delta_size > 0)
                return +1;
            
            // case: bit 31 values not equal
            if ((hash >= 0) && (set.hash < 0))
                return -1;
            
            if ((hash < 0) && (set.hash >= 0))
                return +1;
            
            // case: bit 31 values are equal
            if (delta_hash < 0)
                return -1;
            
            return +1;
        }
        else
        if (object == null) {
            message = "Null argument to compareTo in class SmallSet";
        }
        else {
            message = "Illegal argument to compareTo in class SmallSet: "
                + object.getClass().getName();
        }
        
        throw new ClassCastException(message);
    }
    
    
    /**
     * Takes the given subset of this set and changes its state
     * so that it is the next subset of this set relative to the
     * compareTo comparison operation.
     * 
     * Returns true if and only if the state of the subset has
     * indeed changed.
     * 
     * Returns false and does nothing if:
     * 
     * 
     *   The given subset is null.
     *   The given subset equals this set.
     *   The given subset is not actually a subset of this set.
     *   The given subset does not have the same bounds as this set.
     * 
     * 
     * The following code illustrates how to iterate over the
     * non-empty subsets of a set named s.
     * 
     *      int min = s.getMinimum();
     *     int max = s.getMaximum();
     * 
     *     SmallSet subset = new SmallSet(min, max);    // start empty
     * 
     *     while (s.makeNextSubset(subset)) {
     *         // do some task with the next subset
     *     }
     * 
     * @param subset the subset to change to the next subset
     */
    public final boolean makeNextSubset(SmallSet subset) {
        // subset is null
        if (subset == null)
            return false;
        
        // subset equals this set
        if (subset.hash == hash)
            return false;
        
        // subset is not actaully a subset of this set
        if (subset.hash != (hash & subset.hash))
            return false;
        
        // subset has different bounds
        if (subset.minimum != minimum)
            return false;
        
        if (subset.maximum != maximum)
            return false;
        
        // make sure cached data for this set is up to date
        fillBits();
        
        // invalidate the cached data for the subset if any
        subset.bitsValid = false;
        
        // handle the empty subset
        if (subset.hash == 0) {
            subset.hash = bits[0];
            subset.size = 1;
            return true;
        }
        
        // handle non-empty subset
        int z = subset.size;
        
        // find a = the first slot in the subset 
        int a = 0;
        
        while ((subset.hash & bits[a]) == 0)
            a++;
        
        // handle case when the subset size must increase
        if ((a + z) >= size) {
            subset.hash = lobits[z];
            subset.size = z + 1;
            
            return true;
        }
        
        // find b = the first slot after a that is not in the subset
        int b = a;
        
        while((subset.hash & bits[b]) != 0)
            b++;
        
        subset.hash &= hibits[b];
        
        subset.hash |= bits[b];
        
        int c = b - a - 2;
        
        if (c >= 0)
            subset.hash |= lobits[c];
        
        return true;
    }
    
    
    /**
     * Resets the internal size variable to equal the
     * number of 1-bits in the integer set representation.
     */
    protected final void resetCount() {
        size = 0;
        
        for (int i = minimum; i <= maximum; i++)
            if ((hash & BITS[i]) != 0)
                size++;
    }
    
    
    /**
     * Fills the first size slots in the arrays
     * bits, lobits, and hibits,
     * as described in the comments for these member data variables.
     * 
     * Does nothing if bitsValid is already true.
     */
    protected final void fillBits() {
        if (bitsValid)
            return;
        
        bitsValid = true;
        
        if (bits == null)
            bits = new int[masksize];
        
        if (lobits == null)
            lobits = new int[masksize];
        
        if (hibits == null)
            hibits = new int[masksize];
        
        if(size == 0)
            return;
        
        int k = 0;
        
        for (int i = minimum; i <= maximum; i++) {
            if ((hash & BITS[i]) != 0) {
                bits[k] = BITS[i];
                k++;
            }
        }
        
        lobits[0] = bits[0];
        
        for (int i = 1; i < size; i++)
            lobits[i] = lobits[i-1] | bits[i];
        
        k = size - 1;
        
        hibits[k] = bits[k];
        
        for (int i = (k-1); i >= 0; i--)
            hibits[i] = hibits[i+1] | bits[i];
    }
    
    
    /**
     * Returns an array with the integers in this set
     * sorted in increasing order.  The array length is
     * equal to the size of this set.
     */
    public final int[] toArray() {
        int[] result = new int[size];
        
        if (size == 0)
            return result;
        
        int k = 0;
        
        for (int i = minimum; i <= maximum; i++) {
            if ((hash & BITS[i]) != 0) {
                result[k] = i;
                k++;
            }
        }
        
        return result;
    }
    
    
    /**
     * Returns a space-separated list of the elements
     * in the set.  The list is enclosed in braces: {}.
     */
    public final String toString() {
        if (size == 0)
            return "{ }";
        
        StringBuffer buffer = new StringBuffer(128);
        
        buffer.append("{ ");
        
        for (int element = minimum; element <= maximum; element++) {
            if ((hash & BITS[element]) != 0) {
                buffer.append(element);
                buffer.append(" ");
            }
        }
        
        buffer.append("}");
        
        return buffer.toString();
    }
    
    
    /**
     * Identical to toString.
     */
    public final String toStringData() {
        return toString();
    }
    
    
    /**
     * Initializes this set from the data in the given
     * String.
     * 
     * Expects a list consisting of individual numbers
     * a between minimum and maximum or
     * number pairs a-b representing a range
     * between minimum and maximum.
     * 
     * The list should be separated by spaces and/or
     * commas.
     * 
     * The list may optionally be enclosed in braces:
     * {}.
     * 
     * For robustness, this method will ignore numbers
     * outside the range minimum and maximum
     * as well as any parse exceptions.
     * 
     * @param data the string data to define the set
     */
    public final void fromStringData(String data) {
        int oldhash = hash;
        
        hash = 0;
        
        data = data.trim();
        
        String[] list = Strings.tokenize(data, ", ", true);
        
        int length = list.length;
        
        for (int i = 0; i < length; i++) {
            String s = list[i];
            
            int hyphen = s.indexOf('-');
            
            if (hyphen >= 0) {
                try {
                    String t = s.substring(0, hyphen);
                    String u = s.substring(hyphen + 1, s.length());
                    
                    XInt x = new XInt(t);
                    int a = x.getValue();
                    
                    XInt y = new XInt(u);
                    int b = y.getValue();
                    
                    addRange(a, b);
                }
                catch (Throwable t) { }
            }
            else {
                try {
                    XInt x = new XInt(s);
                    int a = x.getValue();
                    
                    addElement(a);
                }
                catch (Throwable t) { }
                }
        }
        
        if (oldhash != hash) {
            resetCount();
            bitsValid = false;
        }
    }
    
    
    /**
     * Returns the integer with exactly one 1-bit in
     * position i.
     * 
     * Returns 0 if i is not between 0 and 31.
     * 
     * @param i the bit position
     */
    public static int getBitMask(int i) {
        if ((i < MIN) || (i > MAX))
            return 0;
        
        return BITS[i];
    }
    
    
    /**
     * Returns the integer with exactly one 0-bit in
     * position i.
     * 
     * Returns 0 if i is not between 0 and 31.
     * 
     * @param i the bit position
     */
    public static int getCoBitMask(int i) {
        if ((i < MIN) || (i > MAX))
            return 0;
        
        return COBITS[i];
    }
    
    
    /**
     * Returns the integer with 1-bits in precisely
     * the positions from 0 to i.
     * 
     * Returns 0 if i is not between 0 and 31.
     * 
     * @param i the bit position
     */
    public static int getLoBitMask(int i) {
        if ((i < MIN) || (i > MAX))
            return 0;
        
        return LOBITS[i];
    }
    
    
    /**
     * Returns the integer with 1-bits in precisely
     * the positions from i to 31.
     * 
     * Returns 0 if i is not between 0 and 31.
     * 
     * @param i the bit position
     */
    public static int getHiBitMask(int i) {
        if ((i < MIN) || (i > MAX))
            return 0;
        
        return HIBITS[i];
    }
    
}