code: /*
   * Copyright (c) 2016, Hisao Tamaki
   */
  package tw.exact;
  
  import java.util.BitSet;
  import java.util.Comparator;
  
  /**
   * This class extends {@code java.util.BitSet} which implements 
   * a variable length bit vector. 
   * The main purpose is to provide methods that create
   * a new vector as a result of a set operation such as 
   * union and intersection, rather than modifying the 
   * existing one.  See API documentation for {@code java.util.BitSet}.
   *
   * @author  Hisao Tamaki
   */
  
  public class XBitSet extends BitSet 
    implements Comparable<XBitSet>{
    
    /**
     * Creates an empty {@code XBitSet}.
     */
    public XBitSet() {
      super();
    }
  
    /**
     * Creates an empty {@code XBitSet} whose initial size is large enough to explicitly
     * contain members smaller than {@code n}.
     *
     * @param  n the initial size of the {@code XBitSet} 
     * @throws NegativeArraySizeException if the specified initial size
     *         is negative
     */
    public XBitSet(int n) {
      super(n);
    }
    
    /**
     * Creates an {@code XBitSet} with members provided by an array
     *
     * @param  a an array of members to be in the {@code XBitSet}
     */
    public XBitSet(int a[]) {
      super();
      for (int i = 0; i < a.length; i++) {
        set(a[i]);
      }
    }  
    
    /**
     * Creates an {@code XBitSet} with members provided by an array.
     * The initial size is large enough to explicitly
     * contain members smaller than {@code n}.  
     *
     * @param  n the initial size of the {@code XBitSet}
     * @param  a an array of indices where the bits should be set
     * @throws NegativeArraySizeException if the specified initial size
     *         is negative
     */
    public XBitSet(int n, int a[]) {
      super(n);
      for (int i = 0; i < a.length; i++) {
        set(a[i]);
      }
    }  
    
    /**
     * Returns {@code true} if this target {@code XBitSet} is a subset
     * of the argument {@code XBitSet}
     *
     * @param  set an {@code XBitSet}
     * @return boolean indicating whether this {@code XBitSet} is a subset
     *         of the argument {@code XBitSet}
    */
    public boolean isSubset(XBitSet set) {
      BitSet tmp = (BitSet) this.clone();
      tmp.andNot(set);
      return tmp.isEmpty();
    }
  
    /**
     * Returns {@code true} if this target {@code XBitSet} is disjoint
     * from the argument {@code XBitSet}
     *
     * @param  set an {@code XBitSet}
     * @return boolean indicating whether this {@code XBitSet} is 
     *  disjoint from the argument {@code XBitSet}
    */
    public boolean isDisjoint(XBitSet set) {
      BitSet tmp = (BitSet) this.clone();
      tmp.and(set);
      return tmp.isEmpty();
    }
  
    /**
     * Returns {@code true} if this target {@code XBitSet} has a 
     * non-empty intersection with the argument {@code XBitSet}
     *
     * @param  set an {@code XBitSet}
     * @return boolean indicating whether this {@code XBitSet} 
     *  intersects with the argument {@code XBitSet}
    */
  
    public boolean intersects(XBitSet set) {
      return super.intersects(set);
    }
  
    /**
     * Returns {@code true} if this target {@code XBitSet} is a superset
     * of the argument bit set
     *
     * @param  set an {@code XBitSet}
     * @return boolean indicating whether this {@code XBitSet} is a superset
     *  of the argument {@code XBitSet}
    */
    public boolean isSuperset(XBitSet set) {
      BitSet tmp = (BitSet) set.clone();
      tmp.andNot(this);
      return tmp.isEmpty();
    }
    
    /**
     * Returns a {@code XBitSet} that is the union of this
     * target {@code XBitSet} and the argument {@code XBitSet}
     *
     * @param  set an {@code XBitSet}
     * @return the union {@code XBitSet}
    */
    public XBitSet unionWith(XBitSet set) {
      XBitSet result = (XBitSet) this.clone();
      result.or(set);
      return result;
    }
  
    /**
     * Returns an {@code XBitSet} that is the intersection of this
     * target {@code XBitSet} and the argument {@code XBitSet}
     *
     * @param  set an {@code XBitSet}
     * @return the intersection {@code XBitSet}
    */
    public XBitSet intersectWith(XBitSet set) {
      XBitSet result = (XBitSet) this.clone();
      result.and(set);
      return result;
    }
  
    /**
     * Returns an {@code XBitSet} that is the result of
     * of removing the members of the argument {@code XBitSet}
     * from the target {@code XBitSet}.
     * @param  set an {@code XBitSet}
     * @return the difference {@code XBitSet}
    */
    public XBitSet subtract(XBitSet set) {
      XBitSet result = (XBitSet) this.clone();
      result.andNot(set);
      return result;
    }
    
    /**
     * Returns {@code true} if the target {@code XBitSet} has a member 
     * that is smaller than the smallest member of the argument {@code XBitSet}.
     * Both the target and the argument {@code XBitSet} must be non-empty
     * to ensure a meaningful result.
     * @param  set an {@code XBitSet}
     * @return {@code true} if the target {@code XBitSet} has a member
     * smaller than the smallest member of the argument {@code XBitSet};
     * {@code false} otherwise 
    */
    public boolean hasSmaller(XBitSet set) {
      assert !isEmpty() && !set.isEmpty();
      return this.nextSetBit(0) < set.nextSetBit(0);
    }
  
    @Override
    /**
     * Compare the target {@code XBitSet} with the argument
     * {@code XBitSet}, where the bit vectors are viewed as
     * binary representation of an integer, the bit {@code i} 
     * set meaning that the number contains {@code 2^i}.
     * @return negative value if the target is smaller, positive if it is
     * larger, and zero if it equals the argument  
     */
    public int compareTo(XBitSet set) {
      int l1 = this.length();
      int l2 = set.length();
      if (l1 != l2) {
        return l1 - l2;
      }
      for (int i = l1 - 1; i >= 0; i--) {
        if (this.get(i) && !set.get(i)) return 1;
        else if (!this.get(i) && set.get(i)) return -1;
      }
      return 0;
    }
  
    /**
     * Converts the target {@code XBitSet} into an array
     * that contains all the members in the set
     * @return the array representation of the set
     */
    public int[] toArray() {
      int[] result = new int[cardinality()];
      int k = 0;
      for (int i = nextSetBit(0); i >=0; i= nextSetBit(i + 1)) {
        result[k++] = i;
      }
      return result;
    }
    
    /**
     * Checks if this target bit set has an element
     * that is smaller than every element in 
     * the argument bit set
     * @param vs bit set 
     * @return {@code true} if this bit set has an element
     * smaller than every element in {@code vs}
     */
    public boolean hasSmallerVertexThan(XBitSet vs) {
      if (this.isEmpty()) return false;
      else if (vs.isEmpty()) return true;
      else return nextSetBit(0) < vs.nextSetBit(0);
    }
  
    /**
     * holds the reference to an instance of the {@code DescendingComparator}
     * for {@code BitSet}
     */
    public static final Comparator<BitSet> descendingComparator =
        new DescendingComparator();
  
    /**
     * holds the reference to an instance of the {@code AscendingComparator}
     * for {@code BitSet}
     */
    public static final Comparator<BitSet> ascendingComparator =
        new AscendingComparator();
    
    /**
     * holds the reference to an instance of the {@code CardinalityComparator}
     * for {@code BitSet}
     */
    public static final Comparator<BitSet> cardinalityComparator =
        new CardinalityComparator();
    
    /**
     * A comparator for {@code BitSet}. The {@code compare}
     * method compares the two vectors in the lexicographic order 
     * where the highest bit is the most significant. 
     */
    public static class DescendingComparator implements Comparator<BitSet> {
      @Override
      public int compare(BitSet s1, BitSet s2) {
        int l1 = s1.length();
        int l2 = s2.length();
        if (l1 != l2) {
          return l1 - l2;
        }
        for (int i = l1 - 1; i >= 0; i--) {
          if (s1.get(i) && !s2.get(i)) return 1;
          else if (!s1.get(i) && s2.get(i)) return -1;
        }
        return 0;
      }
    }
  
    /**
     * A comparator for {@code BitSet}. The {@code compare} method compares
     * the two vectors in the lexicographic order where the
     * lowest bit is the most significant. 
     */
    public static class AscendingComparator implements Comparator<BitSet> {
      @Override
      public int compare(BitSet s1, BitSet s2) {
        int l1 = s1.length();
        int l2 = s2.length();
  
        for (int i = 0; i < Math.min(l1,  l2); i++) {
          if (s1.get(i) && !s2.get(i)) return 1;
          else if (!s1.get(i) && s2.get(i)) return -1;
        }
        return l1 - l2;
      }
    }
    
    /**
     * A comparator for {@code BitSet}. The {@code compare} method compares
     * the two sets in terms of the cardinality. In case of
     * a tie, the two sets are compared by the {@code AscendingComparator} 
     */
    public static class CardinalityComparator implements Comparator<BitSet> {
      @Override
      public int compare(BitSet s1, BitSet s2) {
        int c1 = s1.cardinality();
        int c2 = s2.cardinality();
        if (c1 != c2) {
          return c1 - c2;
        }
        else 
          return ascendingComparator.compare(s1, s2);
      }
    }
  }
  