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

package tw.exact;

import java.util.ArrayList;

public class Separator {
  Bag parent;
  Graph graph;
  XBitSet vertexSet;
  int size;
  ArrayList<Bag> incidentBags;
  boolean safe;
  boolean unsafe;
  boolean wall;
  
  int[] parentVertex;

  public Separator(Bag parent) {
    this.parent = parent;
    graph = parent.graph;
    incidentBags = new ArrayList<>();
  }

  public Separator(Bag parent, XBitSet vertexSet) {
    this(parent);
    this.vertexSet = vertexSet;
    size = vertexSet.cardinality();
  }
  
  public void addIncidentBag(Bag bag) {
    incidentBags.add(bag);
  }
  
  public void removeVertex(int v) {
    if (vertexSet.get(v)) {
       size--;
    }
    vertexSet.clear(v);
  }
  
  public void invert() {
    vertexSet = convert(vertexSet, parent.inv);
    parent = parent.parent;
  }

  public void convert() {
    vertexSet = convert(vertexSet, parent.conv);
  }
  
  private XBitSet convert(XBitSet s, int[] conv) {
    XBitSet result = new XBitSet();
    for (int v = s.nextSetBit(0); v >= 0;
        v = s.nextSetBit(v + 1)) {
      result.set(conv[v]);
    }
    return result;
  }

  public void collectBagsToPack(ArrayList<Bag> list, Bag from) {
    for (Bag bag: incidentBags) {
      if (bag !=from) {
        bag.collectBagsToPack(list,  this);
      }
    }
  }

  public void figureOutSafety(SafeSeparator ss) {
    if (!safe && !unsafe) {
      safe = ss.isSafeSeparator(vertexSet);
      unsafe = !safe;
    }
  }
  
  public void figureOutSafetyBySPT() {
    if (!safe && !unsafe) {
      safe = isSafe();
      unsafe = !safe;
    }
  }
  
  public boolean isSafe() {
    return isSafeBySPT();
  }
  
  public boolean isSafeBySPT() {
    parentVertex = new int[graph.n];
    ArrayList<XBitSet> components = 
        graph.getComponents(vertexSet);
    for (XBitSet compo: components) {
      if (!isSafeComponentBySPT(compo)) {
        return false;
      }
    }
    return true;
  }
  
  private boolean isSafeComponentBySPT(XBitSet component) {
    XBitSet neighborSet = graph.neighborSet(component);
    XBitSet rest = graph.all.subtract(neighborSet).subtract(component);

    for (int v = neighborSet.nextSetBit(0); v >= 0;
        v = neighborSet.nextSetBit(v + 1)) {
      XBitSet missing = neighborSet.subtract(graph.neighborSet[v]);
      
      for (int w = missing.nextSetBit(0); w >= 0 && w <= v;
          w = missing.nextSetBit(w + 1)) {
        missing.clear(w);
      }

      if (!missing.isEmpty()) {
        XBitSet spt = shortestPathTree(v, missing, rest);
        if (spt == null) {
          return false;
        }
        rest.andNot(spt);
      }
    }
    return true;
  }

  private XBitSet shortestPathTree(int v, XBitSet targets,
      XBitSet available) {
    XBitSet union = available.unionWith(targets);
    
    XBitSet reached = new XBitSet(graph.n);
    reached.set(v);
    XBitSet leaves = (XBitSet) reached.clone();
    while (!targets.isSubset(reached) && !leaves.isEmpty()) {
      XBitSet newLeaves = new XBitSet(graph.n);
      for (int u = leaves.nextSetBit(0); u >= 0;
          u = leaves.nextSetBit(u + 1)) {
        XBitSet children = 
            graph.neighborSet[u].intersectWith(union).subtract(reached);
        for (int w = children.nextSetBit(0); w >= 0;
            w = children.nextSetBit(w + 1)) {
          reached.set(w);
          parentVertex[w] = u;
          if (available.get(w)) {
            newLeaves.set(w);
          }
        }
      }
      leaves = newLeaves;
    }
    
    if (!targets.isSubset(reached)) {
      return null;
    }

    XBitSet spt = new XBitSet(graph.n);
    for (int u = targets.nextSetBit(0); u >= 0;
        u = targets.nextSetBit(u + 1)) {
        int w = parentVertex[u];
        while (w != v) {
          spt.set(w);
          w = parentVertex[w];
        }
    }
    return spt;
  }


  public void dump(String indent) {
    System.out.println(indent + "sep:" + toString());
  }
  
  public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append(vertexSet);
    sb.append("(");
    for (Bag bag: incidentBags){
      if (bag == null) {
        sb.append("null bag ");
      }
      else {
        sb.append(parent.nestedBags.indexOf(bag) + ":" + bag.vertexSet);
        sb.append(" ");
      }
    }
    sb.append(")");
    
    return sb.toString();
  }
  
}
