/*
 * Copyright (c) 2017, Keitaro Makii and Hiromu Ohtsuka
*/

package tw.heuristic;

import java.util.ArrayList;
import java.util.BitSet;

public class CutDecomposer{
  public static final int LN = 2000;
  public static final int HN = 100000;
  public static final int HM = 1000000;
  public static final int ONET = 400000;
  public static final int STEP = 1000;
  public static final long DEFAULTMAXSTEP = 500000;
  public static int now;
  public static int cu;
  public static int compSize;
  public static long count;
  public static boolean abort;
  private Bag whole;

  private static final boolean DEBUG = false;

  private class CutDivide{
    Separator sep;
    VertexSet c1,c2;
    CutDivide(Separator s,VertexSet a,VertexSet b){
      sep = s;
      c1 = a;
      c2 = b;
    }
  }
    private class NextBag{
      Bag bag;
      int start;
      NextBag(Bag b,int s){
        bag = b;
        start = s;
      }
    }

  public CutDecomposer(Bag whole){
    this.whole = whole;
  }

  public void decompose(){
    decompose(DEFAULTMAXSTEP);
  }

  public boolean decompose(long timeMS){
    abort = false;
    count = 0;
    if(whole.graph.n > ONET){
      return true;
    }

    decomposeWithOneCuts();
    if(getTimeMS() > timeMS){
      whole.flatten();
      whole.setWidth();
      abort = true;
      return false;
    }
    whole.flatten();

    if(whole.graph.n <=  LN){
      decomposeWithTwoCuts();
      if(getTimeMS() > timeMS){
        whole.flatten();
        whole.setWidth();
        abort = true;
        return false;
      }
    }
    else if(whole.graph.n <= HN  && whole.graph.numberOfEdges() <= HM){
      if(!decomposeWithSmallCuts(2,timeMS)){
        whole.flatten();
        whole.setWidth();
        abort = true;
        return false;
      }
    }

    if(whole.graph.n <= 30000){
      whole.flatten();
      if(!decomposeWithSmallCuts(3,timeMS)){
        whole.flatten();
        whole.setWidth();
        abort = true;
        return false;
      }
    }
    if(whole.graph.n <= 20000){
      whole.flatten();
      if(!decomposeWithSmallCuts(4,timeMS)){
        whole.flatten();
        whole.setWidth();
        abort = true;
        return false;
      }
    }


    whole.flatten();
    whole.setWidth();

    return true;
  }

  private static void comment(String comment){
    System.out.println("c " + comment);
  }

  private void decomposeWithOneCuts(){
    VertexSet articulationSet = new VertexSet();
    ArrayList< VertexSet > bcc =
      whole.graph.getBiconnectedComponents(articulationSet);

    count += (whole.graph.n + whole.graph.numberOfEdges());

    if(articulationSet.isEmpty()){
      return;
    }

    if(DEBUG){
      comment("detected 1-cuts");
    }

    whole.initializeForDecomposition();

    for(int a = articulationSet.nextSetBit(0);
      a >= 0; a = articulationSet.nextSetBit(a + 1)){
      count++;
      Separator s = whole.addSeparator(new VertexSet(new int[]{a}));
      s.safe = true;
    }

    for(VertexSet bc : bcc){
      count++;
      whole.addNestedBag(bc);
    }

    for(Separator s : whole.separators){
      for(Bag b : whole.nestedBags){
        count++;
        if(s.vertexSet.isSubset(b.vertexSet)){
          b.addIncidentSeparator(s);
          s.addIncidentBag(b);
        }
      }
    }

    if(DEBUG){
      comment("decomposes with 1-cuts");
      comment("1-cutsSize:" + articulationSet.cardinality());
    }

    return;
  }

  private boolean decomposeWithSmallCuts(int c,long timeMS){
    if(whole.nestedBags != null && !whole.nestedBags.isEmpty()){
      for(Bag nb : whole.nestedBags){
        if(!decomposeWithSmallCuts(nb,c,timeMS)){
          return false;
        }
      }
    }
    else{
      if(!decomposeWithSmallCuts(whole,c,timeMS)){
        return false;
      }
    }
    if(DEBUG){
      comment("decompose with small-cuts");
    }
    return true;
  }

  private boolean decomposeWithSmallCuts(Bag bag,int c,long timeMS){
    if(bag != whole){
      bag.makeLocalGraph();
      count += bag.graph.n * (Math.log(bag.graph.n)+1) + bag.graph.numberOfEdges() * 1.2;
    }
    Graph lg = bag.graph;

    cu = c;
    compSize = 6+cu;

    NextBag nb = new NextBag(bag,0);

    while(true){
      nb = decomposeWithSmallCuts(nb.bag,nb.start,lg.n);
      if(getTimeMS() > timeMS){
        return false;
      }
      if (nb == null){
        return true;
      }
      nb.bag.makeLocalGraph();
      lg = nb.bag.graph;
      count += nb.bag.graph.n * (Math.log(nb.bag.graph.n)+1) + nb.bag.graph.numberOfEdges() * 1.2;

      compSize = 6+cu;
    }
  }

  private NextBag decomposeWithSmallCuts(Bag bag,int start,int end){
    for(int i=start;i<end;i++){
      count++;
      now = i;
      VertexSet v = new VertexSet(new int[]{i});
      VertexSet left = bag.graph.neighborSet(v);
      count += Math.log(bag.graph.n);
      CutDivide cd = decomposeWithSmallCuts(bag,v,new VertexSet(),left);
      if(cd != null){
        Bag nest1 = bag.addNestedBag(cd.c1);
        nest1.addIncidentSeparator(cd.sep);
        cd.sep.addIncidentBag(nest1);

        Bag nest2 = bag.addNestedBag(cd.c2);
        nest2.addIncidentSeparator(cd.sep);
        cd.sep.addIncidentBag(nest2);

        return new NextBag(nest2,start);
      }
      else{
        start++;
      }
    }
    return null;
  }

  private CutDivide decomposeWithSmallCuts(Bag bag,VertexSet comp,VertexSet cand,VertexSet left){
    int addSize = comp.cardinality() + left.cardinality();
    int candSize = cand.cardinality();
    count += addSize + candSize;
    if(addSize > compSize || bag.graph.n <= (addSize + candSize)){
      return null;
    }
    if(left.isEmpty()){
      bag.initializeForDecomposition();
      Separator sep = bag.addSeparator(cand);
      sep.figureOutSafetyBySPT();
      count += sep.getSteps() + bag.graph.n / 15;
      if(sep.safe){
        count += bag.graph.n;
        VertexSet big = bag.graph.all.clone();
        big.andNot(comp);
        comp.or(cand);
        return new CutDivide(sep,comp,big);
      }
      else{
        if(bag == whole){
          bag.nestedBags.clear();
          bag.separators.remove(sep);
        }
        else{
          bag.nestedBags = null;
          bag.separators = null;
        }
      }
      return null;
    }

    int next = left.nextSetBit(0);
    if(next == -1){
      return null;
    }
    if(candSize < cu){
      count++;
      cand.set(next);
      left.clear(next);
      CutDivide cd = decomposeWithSmallCuts(bag,comp,cand,left);
      if(cd != null){
        return cd;
      }
      cand.clear(next);
      left.set(next);
    }
    if(next < now){
      return null;
    }

    count++;
    comp.set(next);
    left = bag.graph.neighborSet(comp);
    left = left.subtract(cand);
    count += (bag.graph.n / (Math.log(bag.graph.n)+1));
    CutDivide cd = decomposeWithSmallCuts(bag,comp,cand,left);
    if(cd != null){
      return cd;
    }
    return null;
  }

  private void decomposeWithTwoCuts(){
    if(whole.nestedBags != null && !whole.nestedBags.isEmpty()){
      for(Bag nb : whole.nestedBags){
        nb.makeLocalGraph();
        count += nb.graph.n;
        decomposeWithTwoCuts(nb);
      }
    }
    else{
      decomposeWithTwoCuts(whole);
    }
    if(DEBUG){
      comment("decomposed with 2-cuts");
    }
  }

  private void decomposeWithTwoCuts(Bag parent){
    ArrayList<VertexSet> art = new ArrayList<VertexSet>();
    Graph lg = parent.graph;
    if(lg.n <= 1){
      return;
    }
//    count += lg.n * Math.log(lg.n) + lg.numberOfEdges();
    count += lg.n * lg.n / Math.log(lg.n) + lg.numberOfEdges();
    for(int i=0;i<lg.n;i++){
      count++;
      VertexSet vs = new VertexSet(lg.n);
      vs.set(i);
      BitSet almostAll = new BitSet(lg.n);
      almostAll.set(0,lg.n);
      almostAll.clear(i);
      VertexSet twoArt = lg.articulations(almostAll);
//      count += lg.n + lg.numberOfEdges();
      for(int j=twoArt.nextSetBit(i+1);j!=-1;j=twoArt.nextSetBit(j+1)){
        count++;
        VertexSet twoVs = vs.clone();
        twoVs.set(j);
        art.add(twoVs);
      }
    }

    if(art.size() == 0){
      parent.validate();
      return;
    }

    if(DEBUG){
      comment("detected 2-cuts");
    }

    parent.initializeForDecomposition();

    VertexSet sep = art.get(0);
    ArrayList<VertexSet> comp = lg.getComponents(sep);
    Separator s = parent.addSeparator(sep);
    s.safe = true;
    count += lg.n;

    art.remove(0);

    for(VertexSet ver:comp){
      ver.or(sep);
      Bag b = parent.addNestedBag(ver);
      b.initializeForDecomposition();
      b.addIncidentSeparator(s);
      s.addIncidentBag(b);
      b.makeLocalGraph();

      ArrayList<VertexSet> nextart = new ArrayList<VertexSet>();
      for(VertexSet oldart:art){
        count++;
        if(oldart.isSubset(ver)){
          count++;
          VertexSet na = new VertexSet();
          for(int i=oldart.nextSetBit(0);i!=-1;i=oldart.nextSetBit(i+1)){
            na.set(b.conv[i]);
          }
          nextart.add(na);
        }
      }
      decomposeWithTwoCuts(b,nextart);
    }
  }

  private void decomposeWithTwoCuts(Bag parent,ArrayList<VertexSet> art){
    if(art.size() == 0){
      count++;
      if(DEBUG){
        parent.validate();
      }
      parent.nestedBags = null;
      parent.separators = null;
      return;
    }

    VertexSet sep = art.get(0);
    ArrayList<VertexSet> comp = parent.graph.getComponents(sep);
    count += parent.graph.n;
    Separator s = parent.addSeparator(sep);
    s.safe = true;

    art.remove(0);

    for(VertexSet ver:comp){
      ver.or(sep);;
      Bag b = parent.addNestedBag(ver);
      b.initializeForDecomposition();
      b.addIncidentSeparator(s);
      s.addIncidentBag(b);
      b.makeLocalGraph();
//      count += Math.log(parent.graph.n);
      ArrayList<VertexSet> nextart = new ArrayList<VertexSet>();
      for(VertexSet oldart:art){
        count++;
        if(oldart.isSubset(ver)){
          count++;
          VertexSet na = new VertexSet();
          for(int i=oldart.nextSetBit(0);i!=-1;i=oldart.nextSetBit(i+1)){
            na.set(b.conv[i]);
          }
          nextart.add(na);
        }
      }
      decomposeWithTwoCuts(b,nextart);
    }
  }

  public long getTimeMS(){
    return count/1000;
  }

  public boolean isAborted(){
    return abort;
  }

  public static void main(String[] args){

  }
}
