/*
 * Copyright (c) 2017, Hisao Tamaki
 */

package tw.exact;

import java.io.File;

import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class GreedyDecomposer {

//  static final boolean VERBOSE = true;
  private static final boolean VERBOSE = false;
  // private static boolean DEBUG = true;
  static boolean DEBUG = false;

  Graph g;

  Bag whole;
  
  Mode mode;
  
  ArrayList<Separator> frontier;
  XBitSet remaining;
  
  Set<XBitSet> unsafes;
  Set<XBitSet> safes;
  SafeSeparator ss;
  
  Random random;

  public enum Mode {
    fill, defect, degree, safeFirst
//    fill, defect, degree
  }
  
  public GreedyDecomposer(Bag whole) {
    this(whole, Mode.fill);
  }

  public GreedyDecomposer(Bag whole, Mode mode) {
    this.whole = whole;
    this.mode = mode;

    // need a copy as we fill edges
    this.g = whole.graph.copy();
    if (mode == Mode.safeFirst) {
      safes = new HashSet<>();
      unsafes = new HashSet<>();
      ss = new SafeSeparator(whole.graph);
    }
  }

  public void decompose() {
    whole.initializeForDecomposition();
    frontier = new ArrayList<>();
    remaining = (XBitSet) g.all.clone();
    
    while (!remaining.isEmpty()) {
      int vmin = remaining.nextSetBit(0);
      int minCost = costOf(vmin);
      
//      ArrayList<Integer> minFillVertices = new ArrayList<>();
//      minFillVertices.add(vmin);
      
      for (int v = remaining.nextSetBit(vmin + 1);
          v >= 0; v = remaining.nextSetBit(v + 1)) {
        int cost = costOf(v);
        if (cost < minCost) {
          minCost = cost;
          vmin = v;
        }
      }

      ArrayList<Separator> joined = new ArrayList<>();
      
      XBitSet toBeAClique = new XBitSet(g.n);
      toBeAClique.set(vmin);
      
      for (Separator s: frontier) {
        XBitSet vs = s.vertexSet;
        if (vs.get(vmin)) {
          joined.add(s);
          toBeAClique.or(vs);
        }
      }
      
//      System.out.println(joined.size() + " joined");
      
      if (joined.isEmpty()) {
        toBeAClique.set(vmin);
      }
      else if (joined.size() == 1) {
        Separator uniqueSeparator = joined.get(0);
        if (g.neighborSet[vmin].intersectWith(remaining)
          .isSubset(uniqueSeparator.vertexSet)) {
            uniqueSeparator.removeVertex(vmin);
            if (uniqueSeparator.vertexSet.isEmpty()) {
              whole.separators.remove(uniqueSeparator);
              for (Bag b: uniqueSeparator.incidentBags) {
                b.incidentSeparators.remove(uniqueSeparator);
              }
              frontier.remove(uniqueSeparator);
            }
            remaining.clear(vmin);
            if (VERBOSE) {
              System.out.println("cleared " + vmin + " from" +
                  uniqueSeparator);
            }
            continue;
          }
      }

      toBeAClique.or(g.neighborSet[vmin].intersectWith(remaining));

      Bag bag = whole.addNestedBag(toBeAClique);

      if (VERBOSE) {
        System.out.println("added bag with " + vmin + ", " + bag);
      }

      g.fill(toBeAClique);
      
      XBitSet sep = toBeAClique.subtract(
          new XBitSet(new int[]{vmin}));
      
      if (!sep.isEmpty()) {
        Separator separator = 
            whole.addSeparator(sep);
        
        if (VERBOSE) {
          System.out.println("added separator " + separator +
              " with " + vmin + " absorbed");
        }

        separator.addIncidentBag(bag);
        bag.addIncidentSeparator(separator);
        
        frontier.add(separator);
      }
      
      if (VERBOSE) {
        System.out.println("adding incidences to bag: " + bag);
      }

      for (Separator s: joined) {
        assert !s.vertexSet.isEmpty();
        s.addIncidentBag(bag);
        bag.addIncidentSeparator(s);
        if (VERBOSE) {
          System.out.println("   " + s);
        }
        frontier.remove(s);
      }
      
      remaining.clear(vmin);
    }
    
    whole.setWidth();
  }

  int costOf(int v) {
    switch (mode) {
    case fill: return countFill(v);
    case defect: return defectCount(v);
    case degree: return degreeOf(v);
    case safeFirst: {
      XBitSet ns = g.neighborSet[v];
      ns.set(v);
      if (safes.contains(ns)) {
        return countFill(v);
      }
      else if (unsafes.contains(ns)) {
        return g.n * g.n + countFill(v);
      }
      else if (ss.isSafeSeparator(ns)) {
        safes.add(ns);
        return countFill(v);
      }
      else {
        unsafes.add(ns);
        return g.n * g.n + countFill(v);
      }
    }
    default: return 0;
    }
  }
  
  int defectCount(int v) {
    int count = 0;
    
    XBitSet ns = g.neighborSet[v].intersectWith(remaining);
    for (int w = ns.nextSetBit(0); w >= 0; 
        w = ns.nextSetBit(w + 1)) {
      if (ns.subtract(g.neighborSet[w]).cardinality() > 1) {
        count++;
      }
    }
    return count;
  }

  int countFill(int v) {
    int count = 0;
    XBitSet ns = g.neighborSet[v].intersectWith(remaining);
    for (int w = ns.nextSetBit(0); w >= 0; 
        w = ns.nextSetBit(w + 1)) {
      count += ns.subtract(g.neighborSet[w]).cardinality() - 1;
    }
    return count / 2;
  }

  int degreeOf(int v) {
    XBitSet ns = g.neighborSet[v].intersectWith(remaining);
    return ns.cardinality();
  }
}
