code: /*
   * Copyright (c) 2017, Hiromu Ohtsuka
  */
  
  package tw.heuristic;
  
  public class VertexSet
  implements Comparable< VertexSet >, Cloneable{
    private int TH1 = 256;
    public static enum Type{
      ARRAYSET, XBITSET
    };
    private XBitSet xbitset;
    private ArraySet arrayset;
    private Type type = Type.ARRAYSET;
  
    public VertexSet(){
      arrayset = new ArraySet();
    }
  
    public VertexSet(int n){
      this();
      TH1 = n / 100;
    }
  
    public VertexSet(int n, int[] a){
      TH1 = n / 100;
      if(a.length <= TH1){
        arrayset = new ArraySet(a);
      }
      else{
        type = Type.XBITSET;
        xbitset = new XBitSet(a);
      }
    }
  
    public VertexSet(int[] a){
      if(a.length <= TH1){
        arrayset = new ArraySet(a);
      }
      else{
        type = Type.XBITSET;
        xbitset = new XBitSet(a);
      }
    }
  
    private VertexSet(ArraySet as){
      arrayset = as;
      ensureType();
    }
  
    private VertexSet(XBitSet xbs){
      xbitset = xbs;
      type = Type.XBITSET;
      ensureType();
    }
  
    private void toArraySet(){
      if(type == Type.ARRAYSET){
        return;
      }
      arrayset = arraySetOf(xbitset);
      type = Type.ARRAYSET;
      xbitset = null;
    }
  
    private void toXBitSet(){
      if(type == Type.XBITSET){
        return;
      }
      xbitset = xBitSetOf(arrayset);
      type = Type.XBITSET;
      arrayset = null;
    }
  
    private static XBitSet xBitSetOf(ArraySet as){
      return new XBitSet(as.toArray());
    }
  
    private static ArraySet arraySetOf(XBitSet xbs){
      return new ArraySet(xbs.toArray());
    }
  
    private void ensureType(){
      int size = (type == Type.ARRAYSET) ?
        arrayset.cardinality() : xbitset.cardinality();
      if(size <= TH1){
        toArraySet();
      }
      else{
        toXBitSet();
      }
    }
  
    public void and(VertexSet set){
      if(type == Type.ARRAYSET && set.type == Type.ARRAYSET){
        arrayset.and(set.arrayset);
        ensureType();
        return;
      }
      if(type == Type.XBITSET && set.type == Type.XBITSET){
        xbitset.and(set.xbitset);
        ensureType();
        return;
      }
      if(type == Type.ARRAYSET){
        toXBitSet();
      }
      else{
        set.toXBitSet();
      }
      xbitset.and(set.xbitset);
      set.ensureType();
      ensureType();
    }
  
    public void andNot(VertexSet set){
      if(type == Type.ARRAYSET && set.type == Type.ARRAYSET){
        arrayset.andNot(set.arrayset);
        ensureType();
        return;
      }
      if(type == Type.XBITSET && set.type == Type.XBITSET){
        xbitset.andNot(set.xbitset);
        ensureType();
        return;
      }
      if(type == Type.ARRAYSET){
        toXBitSet();
      }
      else{
        set.toXBitSet();
      }
      xbitset.andNot(set.xbitset);
      set.ensureType();
      ensureType();
    }
  
    public int cardinality(){
      if(type == Type.ARRAYSET){
        return arrayset.cardinality();
      }
      else{
        return xbitset.cardinality();
      }
    }
  
    public void clear(){
      if(type == Type.ARRAYSET){
        arrayset.clear();
      }
      else{
        type = Type.ARRAYSET;
        xbitset = null;
        arrayset = new ArraySet();
      }
    }
  
    public void clear(int i){
      if(type == Type.ARRAYSET){
        arrayset.clear(i);
      }
      else{
        xbitset.clear(i);
      }
      ensureType();
    }
  
    public void clear(int fromIndex, int toIndex){
      if(type == Type.ARRAYSET){
        arrayset.clear(fromIndex, toIndex);
      }
      else{
        xbitset.clear(fromIndex, toIndex);
      }
      ensureType();
    }
  
    @Override
      public VertexSet clone(){
        try{
          VertexSet result = (VertexSet)super.clone();
          if(type == Type.ARRAYSET){
            result.arrayset = (ArraySet)arrayset.clone();
          }
          else{
            result.xbitset = (XBitSet)xbitset.clone();
          }
          return result;
        }
        catch(CloneNotSupportedException e){
          throw new AssertionError();
        }
      }
  
    @Override
      public boolean equals(Object obj){
        if(!(obj instanceof VertexSet)){
          return false;
        }
        VertexSet vs = (VertexSet)obj;
        if(type == Type.ARRAYSET && vs.type == Type.ARRAYSET){
          return arrayset.equals(vs.arrayset);
        }
        if(type == Type.XBITSET && vs.type == Type.XBITSET){
          return xbitset.equals(vs.xbitset);
        }
        if(type == Type.ARRAYSET){
          return xBitSetOf(arrayset).equals(vs.xbitset);
        }
        else{
          return xbitset.equals(xBitSetOf(vs.arrayset));
        }
      }
  
    public void flip(int i){
      if(type == Type.ARRAYSET){
        arrayset.flip(i);
      }
      else{
        xbitset.flip(i);
      }
      ensureType();
    }
  
    public void flip(int fromIndex, int toIndex){
      if(type == Type.ARRAYSET){
        arrayset.flip(fromIndex, toIndex);
      }
      else{
        xbitset.flip(fromIndex, toIndex);
      }
      ensureType();
    }
  
    public boolean get(int i){
      if(type == Type.ARRAYSET){
        return arrayset.get(i);
      }
      else{
        return xbitset.get(i);
      }
    }
  
    public VertexSet get(int fromIndex, int toIndex){
      throw new UnsupportedOperationException();
    }
  
    @Override
      public int hashCode(){
        int hash = 1;
        if(type == Type.ARRAYSET){
          for(int i = 0; i < arrayset.size; i++){
            hash = 31 * hash + arrayset.a[i];
          }
        }
        else{
          for(int i = xbitset.nextSetBit(0);
            i >= 0; i = xbitset.nextSetBit(i + 1)){
            hash = 31 * hash + i;
          }
        }
        return hash;
      }
  
    public boolean hasSmaller(VertexSet set){
      if(type == Type.ARRAYSET && set.type == Type.ARRAYSET){
        return arrayset.hasSmaller(set.arrayset);
      }
      if(type == Type.XBITSET && set.type == Type.XBITSET){
        return xbitset.hasSmaller(set.xbitset);
      }
      if(type == Type.ARRAYSET){
        return xBitSetOf(arrayset).hasSmaller(set.xbitset);
      }
      else{
        return xbitset.hasSmaller(xBitSetOf(set.arrayset));
      }
    }
  
    public boolean hasSmallerVertexThan(VertexSet set){
      if(type == Type.ARRAYSET && set.type == Type.ARRAYSET){
        return arrayset.hasSmallerVertexThan(set.arrayset);
      }
      if(type == Type.XBITSET && set.type == Type.XBITSET){
        return xbitset.hasSmallerVertexThan(set.xbitset);
      }
      if(type == Type.ARRAYSET){
        return xBitSetOf(arrayset).hasSmallerVertexThan(set.xbitset);
      }
      else{
        return xbitset.hasSmallerVertexThan(xBitSetOf(set.arrayset));
      }
    }
  
    public boolean intersects(VertexSet set){
      if(type == Type.ARRAYSET && set.type == Type.ARRAYSET){
        return arrayset.intersects(set.arrayset);
      }
      if(type == Type.XBITSET && set.type == Type.XBITSET){
        return xbitset.intersects(set.xbitset);
      }
      if(type == Type.ARRAYSET){
        return xBitSetOf(arrayset).intersects(set.xbitset);
      }
      else{
        return xbitset.intersects(xBitSetOf(set.arrayset));
      }
    }
  
    public VertexSet intersectWith(VertexSet set){
      if(type == Type.ARRAYSET && set.type == Type.ARRAYSET){
        return new VertexSet(arrayset.intersectWith(set.arrayset));
      }
      if(type == Type.XBITSET && set.type == Type.XBITSET){
        return new VertexSet(xbitset.intersectWith(set.xbitset));
      }
      if(type == Type.ARRAYSET){
        return new VertexSet(xBitSetOf(arrayset).intersectWith(set.xbitset));
      }
      else{
        return new VertexSet(xbitset.intersectWith(xBitSetOf(set.arrayset)));
      }
    }
  
    public boolean isSubset(VertexSet set){
      if(type == Type.ARRAYSET && set.type == Type.ARRAYSET){
        return arrayset.isSubset(set.arrayset);
      }
      if(type == Type.XBITSET && set.type == Type.XBITSET){
        return xbitset.isSubset(set.xbitset);
      }
      if(type == Type.ARRAYSET){
        return xBitSetOf(arrayset).isSubset(set.xbitset);
      }
      else{
        return xbitset.isSubset(xBitSetOf(set.arrayset));
      }
    }
  
    public boolean isDisjoint(VertexSet set){
      if(type == Type.ARRAYSET && set.type == Type.ARRAYSET){
        return arrayset.isDisjoint(set.arrayset);
      }
      if(type == Type.XBITSET && set.type == Type.XBITSET){
        return xbitset.isDisjoint(set.xbitset);
      }
      if(type == Type.ARRAYSET){
        return xBitSetOf(arrayset).isDisjoint(set.xbitset);
      }
      else{
        return xbitset.isDisjoint(xBitSetOf(set.arrayset));
      }
    }
  
    public boolean isEmpty(){
      if(type == Type.ARRAYSET){
        return arrayset.isEmpty();
      }
      else{
        return xbitset.isEmpty();
      }
    }
  
    public boolean isSuperset(VertexSet set){
      if(type == Type.ARRAYSET && set.type == Type.ARRAYSET){
        return arrayset.isSuperset(set.arrayset);
      }
      if(type == Type.XBITSET && set.type == Type.XBITSET){
        return xbitset.isSuperset(set.xbitset);
      }
      if(type == Type.ARRAYSET){
        return xBitSetOf(arrayset).isSuperset(set.xbitset);
      }
      else{
        return xbitset.isSuperset(xBitSetOf(set.arrayset));
      }
    }
  
    public int length(){
      if(type == Type.ARRAYSET){
        return arrayset.length();
      }
      else{
        return xbitset.length();
      }
    }
  
    public int nextClearBit(int fromIndex){
      if(type == Type.ARRAYSET){
        return arrayset.nextClearBit(fromIndex);
      }
      else{
        return xbitset.nextClearBit(fromIndex);
      }
    }
  
    public int nextSetBit(int fromIndex){
      if(type == Type.ARRAYSET){
        return arrayset.nextSetBit(fromIndex);
      }
      else{
        return xbitset.nextSetBit(fromIndex);
      }
    }
  
    public void or(VertexSet set){
      if(type == Type.ARRAYSET && set.type == Type.ARRAYSET){
        arrayset.or(set.arrayset);
        ensureType();
        return;
      }
      if(type == Type.XBITSET && set.type == Type.XBITSET){
        xbitset.or(set.xbitset);
        ensureType();
        return;
      }
      if(type == Type.ARRAYSET){
        toXBitSet();
      }
      else{
        set.toXBitSet();
      }
      xbitset.or(set.xbitset);
      set.ensureType();
      ensureType();
    }
  
    public int previousClearBit(int fromIndex){
      throw new UnsupportedOperationException();
    }
  
    public int previousSetBit(int fromIndex){
      throw new UnsupportedOperationException();
    }
  
    public void set(int i){
      if(type == Type.ARRAYSET){
        arrayset.set(i);
      }
      else{
        xbitset.set(i);
      }
      ensureType();
    }
  
    public void set(int i, boolean value){
      if(type == Type.ARRAYSET){
        arrayset.set(i, value);
      }
      else{
        xbitset.set(i, value);
      }
      ensureType();
    }
  
    public void set(int fromIndex, int toIndex){
      if(type == Type.ARRAYSET){
        arrayset.set(fromIndex, toIndex);
      }
      else{
        xbitset.set(fromIndex, toIndex);
      }
      ensureType();
    }
  
    public void set(int fromIndex, int toIndex, boolean value){
      if(type == Type.ARRAYSET){
        arrayset.set(fromIndex, toIndex, value);
      }
      else{
        xbitset.set(fromIndex, toIndex, value);
      }
      ensureType();
    }
  
    public int size(){
      throw new UnsupportedOperationException();
    }
  
    public VertexSet subtract(VertexSet set){
      if(type == Type.ARRAYSET && set.type == Type.ARRAYSET){
        return new VertexSet(arrayset.subtract(set.arrayset));
      }
      if(type == Type.XBITSET && set.type == Type.XBITSET){
        return new VertexSet(xbitset.subtract(set.xbitset));
      }
      if(type == Type.ARRAYSET){
        return new VertexSet(xBitSetOf(arrayset).subtract(set.xbitset));
      }
      else{
        return new VertexSet(xbitset.subtract(xBitSetOf(set.arrayset)));
      }
    }
  
    public int[] toArray(){
      if(type == Type.ARRAYSET){
        return arrayset.toArray();
      }
      else{
        return xbitset.toArray();
      }
    }
  
    public byte[] toByteArray(){
      if(type == Type.ARRAYSET){
        return arrayset.toByteArray();
      }
      else{
        return xbitset.toByteArray();
      }
    }
  
    public long[] toLongArray(){
      if(type == Type.ARRAYSET){
        return arrayset.toLongArray();
      }
      else{
        return xbitset.toLongArray();
      }
    }
  
    @Override
      public String toString(){
        if(type == Type.ARRAYSET){
          return arrayset.toString();
        }
        else{
          return xbitset.toString();
        }
      }
  
    public VertexSet unionWith(VertexSet set){
      if(type == Type.ARRAYSET && set.type == Type.ARRAYSET){
        return new VertexSet(arrayset.unionWith(set.arrayset));
      }
      if(type == Type.XBITSET && set.type == Type.XBITSET){
        return new VertexSet(xbitset.unionWith(set.xbitset));
      }
      if(type == Type.ARRAYSET){
        return new VertexSet(xBitSetOf(arrayset).unionWith(set.xbitset));
      }
      else{
        return new VertexSet(xbitset.unionWith(xBitSetOf(set.arrayset)));
      }
    }
  
    public static VertexSet valueOf(byte[] bytes){
      throw new UnsupportedOperationException();
    }
  
    public static VertexSet valueOf(long[] longs){
      throw new UnsupportedOperationException();
    }
  
    public void xor(VertexSet set){
      if(type == Type.ARRAYSET && set.type == Type.ARRAYSET){
        arrayset.xor(set.arrayset);
        ensureType();
        return;
      }
      if(type == Type.XBITSET && set.type == Type.XBITSET){
        xbitset.xor(set.xbitset);
        ensureType();
        return;
      }
      if(type == Type.ARRAYSET){
        toXBitSet();
      }
      else{
        set.toXBitSet();
      }
      xbitset.xor(set.xbitset);
      set.ensureType();
      ensureType();
    }
  
    @Override
      public int compareTo(VertexSet vs){
        if(type == Type.ARRAYSET && vs.type == Type.ARRAYSET){
          return arrayset.compareTo(vs.arrayset);
        }
        if(type == Type.XBITSET && vs.type == Type.XBITSET){
          return xbitset.compareTo(vs.xbitset);
        }
        if(type == Type.ARRAYSET){
          return xBitSetOf(arrayset).compareTo(vs.xbitset);
        }
        else{
          return xbitset.compareTo(xBitSetOf(vs.arrayset));
        }
      }
  
    public void checkTypeValidity(){
      if(type == Type.ARRAYSET){
        assert(arrayset != null);
        assert(xbitset == null);
        assert(arrayset.cardinality() <= TH1);
      }
      else{
        assert(xbitset != null);
        assert(arrayset == null);
        assert(xbitset.cardinality() > TH1);
      }
    }
  }
  