code: /*
   * Copyright (c) 2016, Hisao Tamaki
   */
  package tw.heuristic;
  
  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);
  			}
  	}
  }
  