tools/lexer/jflex-1.4/src/JFlex/StateSet.java

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * JFlex 1.4.3                                                             *
 * Copyright (C) 1998-2009  Gerwin Klein <lsf@jflex.de>                    *
 * All rights reserved.                                                    *
 *                                                                         *
 * This program is free software; you can redistribute it and/or modify    *
 * it under the terms of the GNU General Public License. See the file      *
 * COPYRIGHT for more information.                                         *
 *                                                                         *
 * This program is distributed in the hope that it will be useful,         *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of          *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the           *
 * GNU General Public License for more details.                            *
 *                                                                         *
 * You should have received a copy of the GNU General Public License along *
 * with this program; if not, write to the Free Software Foundation, Inc., *
 * 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA                 *
 *                                                                         *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
package JFlex;

/**
 * A set of NFA states (= integers). 
 *
 * Very similar to java.util.BitSet, but is faster and doesn't crash
 *
 * @author Gerwin Klein
 * @version $Revision: 1.4.3 $, $Date: 2009/12/21 15:58:48 $ 
 */
final public class StateSet {

  private final boolean DEBUG = false;

  public final static StateSet EMPTY = new StateSet();


  final static int BITS = 6;
  final static int MASK = (1<<BITS)-1;
  
  long bits[];
  
  
  public StateSet() {
    this(256);
  }  

  public StateSet(int size) {    
    bits = new long[size2nbits(size)];
  }

  public StateSet(int size, int state) {
    this(size);
    addState(state);
  }

  public StateSet(StateSet set) {
    bits = new long[set.bits.length];
    System.arraycopy(set.bits, 0, bits, 0, set.bits.length);
  }


  public void addState(int state) {
    if (DEBUG) {
      Out.dump("StateSet.addState("+state+") start"); //$NON-NLS-1$ //$NON-NLS-2$
      Out.dump("Set is : "+this); //$NON-NLS-1$
    }
   
    int index = state >> BITS;
    if (index >= bits.length) resize(state);
    bits[index] |= (1L << (state & MASK));
    
    if (DEBUG) {
      Out.dump("StateSet.addState("+state+") end"); //$NON-NLS-1$ //$NON-NLS-2$
      Out.dump("Set is : "+this); //$NON-NLS-1$
    }
  }


  private int size2nbits (int size) {
    return ((size >> BITS) + 1);
  }


  private void resize(int size) {
    int needed = size2nbits(size);

    // if (needed < bits.length) return;
         
    long newbits[] = new long[Math.max(bits.length*4,needed)];
    System.arraycopy(bits, 0, newbits, 0, bits.length);
    
    bits = newbits;
  }


  public void clear() {    
    int l = bits.length;
    for (int i = 0; i < l; i++) bits[i] = 0;
  }

  public boolean isElement(int state) {
    int index = state >> BITS;
    if (index >= bits.length)  return false;
    return (bits[index] & (1L << (state & MASK))) != 0;
  }

  /**
   * Returns one element of the set and removes it. 
   *
   * Precondition: the set is not empty.
   */
  public int getAndRemoveElement() {
    int i = 0;
    int o = 0;
    long m = 1;
    
    while (bits[i] == 0) i++;
    
    while ( (bits[i] & m) == 0 ) {
      m<<= 1;
      o++;
    }
    
    bits[i]&= ~m;
    
    return (i << BITS) + o;
  }

  public void remove(int state) {
    int index = state >> BITS;
    if (index >= bits.length) return;
    bits[index] &= ~(1L << (state & MASK));
  }

  /**
   * Returns the set of elements that contained are in the specified set
   * but are not contained in this set.
   */
  public StateSet complement(StateSet set) {
    
    if (set == null) return null;
    
    StateSet result = new StateSet();
    
    result.bits = new long[set.bits.length];
    
    int i;
    int m = Math.min(bits.length, set.bits.length);
    
    for (i = 0; i < m; i++) {
      result.bits[i] = ~bits[i] & set.bits[i];
    }
    
    if (bits.length < set.bits.length) 
      System.arraycopy(set.bits, m, result.bits, m, result.bits.length-m);
    
    if (DEBUG) 
      Out.dump("Complement of "+this+Out.NL+"and "+set+Out.NL+" is :"+result); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
    
    return result;
  }

  public void add(StateSet set) {
    
    if (DEBUG) Out.dump("StateSet.add("+set+") start"); //$NON-NLS-1$ //$NON-NLS-2$

    if (set == null) return;

    long tbits[];
    long sbits[] = set.bits;
    int sbitsl = sbits.length;

    if (bits.length < sbitsl) {
      tbits = new long[sbitsl];
      System.arraycopy(bits, 0, tbits, 0, bits.length);
    }
    else {
      tbits = this.bits;
    }
    
    for (int i = 0; i < sbitsl; i++) {
      tbits[i] |= sbits[i];      
    }

    this.bits = tbits;
    
    if (DEBUG) {
      Out.dump("StateSet.add("+set+") end"); //$NON-NLS-1$ //$NON-NLS-2$
      Out.dump("Set is : "+this); //$NON-NLS-1$
    }
  }
  


  public boolean containsSet(StateSet set) {

    if (DEBUG)
      Out.dump("StateSet.containsSet("+set+"), this="+this); //$NON-NLS-1$ //$NON-NLS-2$

    int i;
    int min = Math.min(bits.length, set.bits.length);
    
    for (i = 0; i < min; i++) 
      if ( (bits[i] & set.bits[i]) != set.bits[i] ) return false;
    
    for (i = min; i < set.bits.length; i++)
      if ( set.bits[i] != 0 ) return false;
    
    return true;
  }



  /**
   * @throws ClassCastException if b is not a StateSet
   * @throws NullPointerException if b is null
   */
  public boolean equals(Object b) {

    int i = 0;
    int l1,l2;
    StateSet set = (StateSet) b;

    if (DEBUG) Out.dump("StateSet.equals("+set+"), this="+this); //$NON-NLS-1$ //$NON-NLS-2$

    l1 = bits.length;
    l2 = set.bits.length;

    if (l1 <= l2) {      
      while (i < l1) {
        if (bits[i] != set.bits[i]) return false;
        i++;
      }
      
      while (i < l2) 
        if (set.bits[i++] != 0) return false;
    }
    else {
      while (i < l2) {
        if (bits[i] != set.bits[i]) return false;
        i++;
      }
      
      while (i < l1) 
        if (bits[i++] != 0) return false;
    }

    return true;
  }

  public int hashCode() {
    long h = 1234;
    long [] _bits = bits;
    int  i = bits.length-1;

    // ignore zero high bits
    while (i >= 0 && _bits[i] == 0) i--;

    while (i >= 0)
      h ^= _bits[i--] * i;

    return (int)((h >> 32) ^ h);
  } 


  public StateSetEnumerator states() {
    return new StateSetEnumerator(this);
  }


  public boolean containsElements() {
    for (int i = 0; i < bits.length; i++)
      if (bits[i] != 0) return true;
      
    return false;
  }

  
  public StateSet copy() {
    StateSet set = new StateSet();
    set.bits = new long[bits.length];
    System.arraycopy(bits, 0, set.bits, 0, bits.length);
    return set;
  }


  /**
   * Copy specified StateSet into this.
   * 
   * @param set  the state set to copy.
   */ 
  public void copy(StateSet set) {
    
    if (DEBUG) 
      Out.dump("StateSet.copy("+set+") start"); //$NON-NLS-1$ //$NON-NLS-2$

    if (set == null) {
      for (int i = 0; i < bits.length; i++) bits[i] = 0;
      return;
    }

    if (bits.length < set.bits.length) {
      bits = new long[set.bits.length];
    }
    else {
      for (int i = set.bits.length; i < bits.length; i++) bits[i] = 0;
    }

    System.arraycopy(set.bits, 0, bits, 0, bits.length);        

    if (DEBUG) {
      Out.dump("StateSet.copy("+set+") end"); //$NON-NLS-1$ //$NON-NLS-2$
      Out.dump("Set is : "+this); //$NON-NLS-1$
    }
  }

  
  public String toString() {
    StateSetEnumerator set = states();

    StringBuffer result = new StringBuffer("{"); //$NON-NLS-1$

    if ( set.hasMoreElements() ) result.append(""+set.nextElement()); //$NON-NLS-1$

    while ( set.hasMoreElements() ) {
      int i = set.nextElement();
      result.append( ", "+i); //$NON-NLS-1$
    }

    result.append("}"); //$NON-NLS-1$

    return result.toString();
  }  
}