/*
 * Copyright (c) 2017, Hisao Tamaki and Hiromu Otsuka
*/

package tw.heuristic;

import java.io.PrintStream;

import java.util.ArrayList;
import java.util.Arrays;

public class BlockSieve{
  private static final String spaces64 =
    "                                                                ";
  public static final int MAX_CHILDREN_SIZE = 512;
  private Node root;
  private int n;
  private int last;
  private int targetWidth;
  private int margin;
  private int size;

  private abstract class Node{
    protected int index;
    protected int width;
    protected int ntz;
    protected Node[] children;
    protected VertexSet[] values;
    protected int[] cardinalities;

    protected Node(int index, int width, int ntz){
      this.index = index;
      this.width = width;
      this.ntz = ntz;
    }

    public abstract int indexOf(long label);
    public abstract int add(long label);
    public abstract int size();
    public abstract long getLabelAt(int i);

    public long getMask(){
      return Unsigned.consecutiveOneBit(ntz, ntz + width);
    }

    public int add(long label, Node child){
      int i = add(label);
      if(children != null){
        children = Arrays.copyOf(children, children.length + 1);
        for(int j = children.length - 1; j - 1 >= i; j--){
          children[j] = children[j - 1];
        }
        children[i] = child;
        return i;
      }
      else{
        children = new Node[1];
        children[0] = child;
        return 0;
      }
    }

    public int add(long label, VertexSet value){
      return add(label, value, value.cardinality());
    }

    public int add(long label, VertexSet value, int cardinality){
      int i = add(label);
      if(values != null && cardinalities != null){
        values = Arrays.copyOf(values, values.length + 1);
        for(int j = values.length - 1; j - 1 >= i; j--){
          values[j] = values[j - 1];
        }
        values[i] = value;
        cardinalities =
          Arrays.copyOf(cardinalities, cardinalities.length + 1);
        for(int j = cardinalities.length - 1; j - 1 >= i; j--){
          cardinalities[j] = cardinalities[j - 1];
        }
        cardinalities[i] = cardinality;
        return i;
      }
      else{
        values = new VertexSet[1];
        values[0] = value;
        cardinalities = new int[1];
        cardinalities[0] = cardinality;
        return 0;
      }
    }

    public boolean isLeaf(){
      return index == last && isLastInInterval();
    }

    public boolean isLastInInterval(){
      return ntz + width == 64;
    }

    public abstract void filterSuperblocks(long[] longs, long[] neighbors, 
        int intersects, ArrayList< VertexSet > list);

    public abstract void filterSubblocks(long[] longs, long[] neighbors,
        int intersects, ArrayList< VertexSet > list);

    public abstract void dump(PrintStream ps, String indent);
  }

  private class ByteNode extends Node{
    private byte[] labels;

    public ByteNode(int index, int width, int ntz){
      super(index, width, ntz);
      assert(width <= 8);
      labels = new byte[0];
    }

    @Override
      public int size(){
        return labels.length;
      }

    @Override
      public long getLabelAt(int i){
        return Unsigned.toUnsignedLong(labels[i]) << ntz;
      }

    @Override
      public int indexOf(long label){
        return Unsigned.binarySearch(labels, 
            Unsigned.byteValue((label & getMask()) >>> ntz));
      }

    @Override
      public int add(long label){
        int i = -(indexOf(label)) - 1;
        labels = Arrays.copyOf(labels, labels.length + 1);
        for(int j = labels.length - 1; j - 1 >= i; j--){
          labels[j] = labels[j - 1];
        }
        labels[i] = Unsigned.byteValue((label & getMask()) >>> ntz);
        return i;
      }

    @Override
      public void dump(PrintStream ps, String indent){
        for(int i = 0; i < labels.length; i++){
          ps.println(indent + Long.toBinaryString(labels[i]));
          if(!isLeaf()){
            children[i].dump(ps, indent + spaces64);
          }
        }
      }

    @Override
      public void filterSuperblocks(long[] longs, long[] neighbors, 
          int intersects, ArrayList< VertexSet > list){
        long mask = getMask();
        int bits = 0;
        if(index < longs.length){
          bits = Unsigned.intValue(((longs[index] & mask) >>> ntz));
        }

        int neighb = 0;
        if(index < neighbors.length){
          neighb = Unsigned.intValue((neighbors[index] & mask) >>> ntz);
        }

        if(isLeaf()){
          for(int i = labels.length - 1; i >= 0; i--){
            int label = Unsigned.toUnsignedInt(labels[i]);
            if(Unsigned.compare(bits, label) > 0){
              break;
            }
            if((bits & ~label) == 0){
              int intersects1 = intersects +
                Integer.bitCount(label & neighb);
              if(intersects1 + cardinalities[i] 
                  <= targetWidth + 1){
                list.add(values[i]);
              }
            }
          }
        }
        else{
          for(int i = labels.length - 1; i >= 0; i--){
            int label = Unsigned.toUnsignedInt(labels[i]);
            if(Unsigned.compare(bits, label) > 0){
              break;
            }
            if((bits & ~label) == 0){
              int intersects1 = intersects +
                Integer.bitCount(label & neighb);
              if(intersects1 <= margin){
                children[i].filterSuperblocks(
                    longs, neighbors, intersects1, list);
              }
            }
          }
        }
      }

    @Override
      public void filterSubblocks(long[] longs, long[] neighbors, 
          int intersects, ArrayList< VertexSet > list) {
        long mask = getMask();
        int bits = 0;
        if(index < longs.length){
          bits = Unsigned.intValue((longs[index] & mask) >>> ntz);
        }

        int neighb = 0;
        if(index < neighbors.length){
          neighb = Unsigned.intValue((neighbors[index] & mask) >>> ntz);
        }

        if(isLeaf()){
          for(int i = 0; i < labels.length; i++){
            int label = Unsigned.toUnsignedInt(labels[i]);
            if(Unsigned.compare(bits, label) < 0){
              break;
            }
            if((~bits & label) == 0){
              int intersects1 = intersects +
                Integer.bitCount(label & neighb);
              if(intersects1 + cardinalities[i] 
                  <= targetWidth + 1){
                list.add(values[i]);
              }
            }
          }
        }
        else{
          for(int i = 0; i < labels.length; i++){
            int label = Unsigned.toUnsignedInt(labels[i]);
            if(Unsigned.compare(bits, label) < 0){
              break;
            }
            if((~bits & label) == 0){
              int intersects1 = intersects +
                Integer.bitCount(label & neighb);
              if(intersects1 <= margin){
                children[i].filterSubblocks(
                    longs, neighbors, intersects1, list);
              }
            }
          }
        }
      }
  }

  private class ShortNode extends Node{
    private short[] labels;

    public ShortNode(int index, int width, int ntz){
      super(index, width, ntz);
      assert(width <= 16);
      labels = new short[0];
    }

    @Override
      public int size(){
        return labels.length;
      }

    @Override
      public long getLabelAt(int i){
        return Unsigned.toUnsignedLong(labels[i]) << ntz;
      }

    @Override
      public int indexOf(long label){
        return Unsigned.binarySearch(labels, 
            Unsigned.shortValue((label & getMask()) >>> ntz));
      }

    @Override
      public int add(long label){
        int i = -(indexOf(label)) - 1;
        labels = Arrays.copyOf(labels, labels.length + 1);
        for(int j = labels.length - 1; j - 1 >= i; j--){
          labels[j] = labels[j - 1];
        }
        labels[i] = Unsigned.shortValue(((label & getMask()) >>> ntz));
        return i;
      }

    @Override
      public void dump(PrintStream ps, String indent){
        for (int i = 0; i < labels.length; i++) {
          ps.println(indent + Long.toBinaryString(labels[i]));
          if (!isLeaf()) {
            children[i].dump(ps, indent + spaces64);
          }
        }
      }

    @Override
      public void filterSuperblocks(long[] longs, long[] neighbors, 
          int intersects, ArrayList< VertexSet > list){
        long mask = getMask();
        int bits = 0;
        if(index < longs.length){
          bits = Unsigned.intValue((longs[index] & mask) >>> ntz);
        }

        int neighb = 0;
        if(index < neighbors.length){
          neighb = Unsigned.intValue((neighbors[index] & mask) >>> ntz);
        }

        if(isLeaf()){
          for(int i = labels.length - 1; i >= 0; i--){
            int label = Unsigned.toUnsignedInt(labels[i]);
            if(Unsigned.compare(bits, label) > 0){
              break;
            }
            if((bits & ~label) == 0){
              int intersects1 = intersects +
                Integer.bitCount(label & neighb);
              if(intersects1 + cardinalities[i] 
                  <= targetWidth + 1){
                list.add(values[i]);
              }
            }
          }
        }
        else{
          for(int i = labels.length - 1; i >= 0; i--){
            int label = Unsigned.toUnsignedInt(labels[i]);
            if(Unsigned.compare(bits, label) > 0){
              break;
            }
            if((bits & ~label) == 0){
              int intersects1 = intersects +
                Integer.bitCount(label & neighb);
              if(intersects1 <= margin){
                children[i].filterSuperblocks(
                    longs, neighbors, intersects1, list);
              }
            }
          }
        }
      }

    @Override
      public void filterSubblocks(long[] longs, long[] neighbors, 
          int intersects, ArrayList< VertexSet > list) {
        long mask = getMask();
        int bits = 0;
        if(index < longs.length){
          bits = Unsigned.intValue((longs[index] & mask) >>> ntz);
        }

        int neighb = 0;
        if(index < neighbors.length){
          neighb = Unsigned.intValue((neighbors[index] & mask) >>> ntz);
        }

        if(isLeaf()){
          for(int i = 0; i < labels.length; i++){
            int label = Unsigned.toUnsignedInt(labels[i]);
            if(Unsigned.compare(bits, label) < 0){
              break;
            }
            if((~bits & label) == 0){
              int intersects1 = intersects +
                Integer.bitCount(label & neighb);
              if(intersects1 + cardinalities[i] 
                  <= targetWidth + 1){
                list.add(values[i]);
              }
            }
          }
        }
        else{
          for(int i = 0; i < labels.length; i++){
            int label = Unsigned.toUnsignedInt(labels[i]);
            if(Unsigned.compare(bits, label) < 0){
              break;
            }
            if((~bits & label) == 0){
              int intersects1 = intersects +
                Integer.bitCount(label & neighb);
              if(intersects1 <= margin){
                children[i].filterSubblocks(
                    longs, neighbors, intersects1, list);
              }
            }
          }
        }
      }
  }

  private class IntegerNode extends Node{
    private int[] labels;

    public IntegerNode(int index, int width, int ntz){
      super(index, width, ntz);
      assert(width <= 32);
      labels = new int[0];
    }

    @Override
      public int size(){
        return labels.length;
      }

    @Override
      public long getLabelAt(int i){
        return Integer.toUnsignedLong(labels[i]) << ntz;
      }

    @Override
      public int indexOf(long label){
        return Unsigned.binarySearch(labels, 
            Unsigned.intValue((label & getMask()) >>> ntz));
      }

    @Override
      public int add(long label){
        int i = -(indexOf(label)) - 1;
        labels = Arrays.copyOf(labels, labels.length + 1);
        for(int j = labels.length - 1; j - 1 >= i; j--){
          labels[j] = labels[j - 1];
        }
        labels[i] = Unsigned.intValue((label & getMask()) >>> ntz);
        return i;
      }

    @Override
      public void dump(PrintStream ps, String indent){
        for (int i = 0; i < labels.length; i++) {
          ps.println(indent + Long.toBinaryString(labels[i]));
          if (!isLeaf()) {
            children[i].dump(ps, indent + spaces64);
          }
        }
      }

    @Override
      public void filterSuperblocks(long[] longs, long[] neighbors, 
          int intersects, ArrayList< VertexSet > list){
        long mask = getMask();
        int bits = 0;
        if(index < longs.length){
          bits = Unsigned.intValue((longs[index] & mask) >>> ntz);
        }

        int neighb = 0;
        if(index < neighbors.length){
          neighb = Unsigned.intValue((neighbors[index] & mask) >>> ntz);
        }

        if(isLeaf()){
          for(int i = labels.length - 1; i >= 0; i--){
            int label = labels[i];
            if(Unsigned.compare(bits, label) > 0){
              break;
            }
            if((bits & ~label) == 0){
              int intersects1 = intersects +
                Integer.bitCount(label & neighb);
              if(intersects1 + cardinalities[i] 
                  <= targetWidth + 1){
                list.add(values[i]);
              }
            }
          }
        }
        else{
          for(int i = labels.length - 1; i >= 0; i--){
            int label = labels[i];
            if(Unsigned.compare(bits, label) > 0){
              break;
            }
            if((bits & ~label) == 0){
              int intersects1 = intersects +
                Integer.bitCount(label & neighb);
              if(intersects1 <= margin){
                children[i].filterSuperblocks(
                    longs, neighbors, intersects1, list);
              }
            }
          }
        }
      }

    @Override
      public void filterSubblocks(long[] longs, long[] neighbors, 
          int intersects, ArrayList< VertexSet > list) {
        long mask = getMask();
        int bits = 0;
        if(index < longs.length){
          bits = Unsigned.intValue((longs[index] & mask) >>> ntz);
        }

        int neighb = 0;
        if(index < neighbors.length){
          neighb = Unsigned.intValue((neighbors[index] & mask) >>> ntz);
        }

        if(isLeaf()){
          for(int i = 0; i < labels.length; i++){
            int label = labels[i];
            if(Unsigned.compare(bits, label) < 0){
              break;
            }
            if((~bits & label) == 0){
              int intersects1 = intersects +
                Integer.bitCount(label & neighb);
              if(intersects1 + cardinalities[i] 
                  <= targetWidth + 1){
                list.add(values[i]);
              }
            }
          }
        }
        else{
          for(int i = 0; i < labels.length; i++){
            int label = labels[i];
            if(Unsigned.compare(bits, label) < 0){
              break;
            }
            if((~bits & label) == 0){
              int intersects1 = intersects +
                Integer.bitCount(label & neighb);
              if(intersects1 <= margin){
                children[i].filterSubblocks(
                    longs, neighbors, intersects1, list);
              }
            }
          }
        }
      }
  }

  private class LongNode extends Node{
    private long[] labels;

    public LongNode(int index){
      this(index, 64, 0);
    }

    private LongNode(int index, int width, int ntz){
      super(index, width, ntz);
      assert(width <= 64);
      labels = new long[0];
    }

    @Override
      public int size(){
        return labels.length;
      }

    @Override
      public long getLabelAt(int i){
        return labels[i] << ntz;
      }

    @Override
      public int indexOf(long label){
        return Unsigned.binarySearch(labels, (label & getMask()) >>> ntz);
      }

    @Override
      public int add(long label){
        int i = -(indexOf(label)) - 1;
        labels = Arrays.copyOf(labels, labels.length + 1);
        for(int j = labels.length - 1; j - 1 >= i; j--){
          labels[j] = labels[j - 1];
        }
        labels[i] = ((label & getMask()) >>> ntz);
        return i;
      }

    @Override
      public void dump(PrintStream ps, String indent){
        for(int i = 0; i < labels.length; i++){
          ps.println(indent + Long.toBinaryString(labels[i]));
          if(!isLeaf()){
            children[i].dump(ps, indent + spaces64);
          }
        }
      }

    @Override
      public void filterSuperblocks(long[] longs, long[] neighbors, 
          int intersects, ArrayList< VertexSet > list){
        long mask = getMask();
        long bits = 0;
        if(index < longs.length){
          bits = (longs[index] & mask) >>> ntz;
        }

        long neighb = 0;
        if(index < neighbors.length){
          neighb = (neighbors[index] & mask) >>> ntz;
        }

        if(isLeaf()){
          for(int i = labels.length - 1; i >= 0; i--){
            long label = labels[i];
            if(Unsigned.compare(bits, label) > 0){
              break;
            }
            if((bits & ~label) == 0){
              int intersects1 = intersects +
                Long.bitCount(label & neighb);
              if(intersects1 + cardinalities[i] 
                  <= targetWidth + 1){
                list.add(values[i]);
              }
            }
          }
        }
        else{
          for(int i = labels.length - 1; i >= 0; i--){
            long label = labels[i];
            if(Unsigned.compare(bits, label) > 0){
              break;
            }
            if((bits & ~label) == 0){
              int intersects1 = intersects +
                Long.bitCount(label & neighb);
              if(intersects1 <= margin){
                children[i].filterSuperblocks(
                    longs, neighbors, intersects1, list);
              }
            }
          }
        }
      }

    @Override
      public void filterSubblocks(long[] longs, long[] neighbors, 
          int intersects, ArrayList< VertexSet > list) {
        long mask = getMask();
        long bits = 0;
        if(index < longs.length){
          bits = (longs[index] & mask) >>> ntz;
        }

        long neighb = 0;
        if(index < neighbors.length){
          neighb = (neighbors[index] & mask) >>> ntz;
        }

        if(isLeaf()){
          for(int i = 0; i < labels.length; i++){
            long label = labels[i];
            if(Unsigned.compare(bits, label) < 0){
              break;
            }
            if((~bits & label) == 0){
              int intersects1 = intersects +
                Long.bitCount(label & neighb);
              if(intersects1 + cardinalities[i] 
                  <= targetWidth + 1){
                list.add(values[i]);
              }
            }
          }
        }
        else{
          for(int i = 0; i < labels.length; i++){
            long label = labels[i];
            if(Unsigned.compare(bits, label) < 0){
              break;
            }
            if((~bits & label) == 0){
              int intersects1 = intersects +
                Long.bitCount(label & neighb);
              if(intersects1 <= margin){
                children[i].filterSubblocks(
                    longs, neighbors, intersects1, list);
              }
            }
          }
        }
      }
  }

  public BlockSieve(int n, int targetWidth, int margin){
    this.n = n;
    this.targetWidth = targetWidth;
    this.margin = margin;
    root = new LongNode(0);
    last = (n - 1) / 64;
  }

  public VertexSet put(VertexSet bs, VertexSet value){
    long longs[] = bs.toLongArray();
    Node node = root, parent = null;

    int i = 0, j1 = 0;
    long bits = 0;
    for(;;){
      bits = 0;
      if(i < longs.length){
        bits = longs[i];
      }
      int j = node.indexOf(bits);
      if(j < 0){
        break;
      }
      if(node.isLeaf()){
        return node.values[j];
      }
      parent = node;
      node = node.children[j];
      i = node.index;
      j1 = j;
    }

    if(node.isLeaf()){
      node.add(bits, value);
    }
    else if(node.isLastInInterval()){
      node.add(bits, newPath(i + 1, longs, value));
    }
    else{
      Node header = newNode(
          i, 64 - (node.ntz + node.width), node.ntz + node.width);
      if(!header.isLeaf()){
        header.add(bits, newPath(i + 1, longs, value));
      }
      else{
        header.add(bits, value);
      }
      node.add(bits, header);
    }

    ++size;
    if(parent != null){
      parent.children[j1] = tryWidthResizing(node);
    }
    else{
      root = tryWidthResizing(node);
    }

    return null;
  }

  private Node tryWidthResizing(Node node){
    if(node.size() > MAX_CHILDREN_SIZE){
      Node node1 = resizeWidth(node);
      for(int i = 0; i < node1.children.length; i++){
        node1.children[i] = tryWidthResizing(node1.children[i]);
      }
      return node1;
    }
    return node;
  }

  private Node resizeWidth(Node node){
    int w = node.width, leng = node.size();
    long m = node.getMask();

    long[] l = new long[leng];
    int ntz = Long.numberOfTrailingZeros(m);
    int t = ntz + node.width;
    while(l.length > MAX_CHILDREN_SIZE){
      t = (ntz + t) / 2;
      m = Unsigned.consecutiveOneBit(ntz, t);
      int p = 0;
      for(int i = 0; i < leng; i++){
        long label = ((node.getLabelAt(i) & m) >>> ntz);
        int j = Unsigned.binarySearch(l, 0, p, label);
        if(j < 0){
          j = -j - 1;
          for(int k = p; k - 1 >= j; k--){
            l[k] = l[k - 1];
          }
          l[j] = label;
          ++p;
        }
      }
      l = Arrays.copyOfRange(l, 0, p);
    }

    Node[] c = new Node[l.length];
    for(int i = 0; i < c.length; i++){
      long msk = node.getMask() & ~m;
      c[i] = newNode(node.index, 
          Long.bitCount(msk), Long.numberOfTrailingZeros(msk));
    }

    for(int i = 0; i < leng; i++){
      long label = node.getLabelAt(i);
      int j = Unsigned.binarySearch(l, ((label & m) >>> ntz));
      if(!node.isLeaf()){
        c[j].add(label, node.children[i]);
      }
      else{
        c[j].add(label,
            node.values[i], node.cardinalities[i]);
      }
    }

    Node n1 = newNode(node.index, 
        Long.bitCount(m), Long.numberOfTrailingZeros(m));

    for(int i = 0; i < l.length; i++){
      n1.add(l[i] << ntz, c[i]);
    }

    return n1;
  }

  private Node newNode(int index, int width, int ntz){
    if(width > 32){
      return new LongNode(index, width, ntz);
    }
    else if(width > 16){
      return new IntegerNode(index, width, ntz);
    }
    else if(width > 8){
      return new ShortNode(index, width, ntz);
    }
    else{
      return new ByteNode(index, width, ntz);
    }
  }

  private Node newPath(int index, long[] longs, VertexSet value){
    Node node = new LongNode(index);

    long bits = 0;
    if(index < longs.length){
      bits = longs[index];
    }

    if(index == last){
      node.add(bits, value);
    }
    else{
      node.add(bits, newPath(index + 1, longs, value));
    }

    return node;
  }

  public void collectSuperblocks(
      VertexSet component, VertexSet neighbors, ArrayList< VertexSet > list){
    root.filterSuperblocks(component.toLongArray(), 
        neighbors.toLongArray(), 0, list);
  }

  public void collectSubblocks(
      VertexSet component, VertexSet neighbors, ArrayList< VertexSet > list){
    root.filterSubblocks(component.toLongArray(), 
        neighbors.toLongArray(), 0, list);
  }

  public int size(){
    return size;
  }

  public void dump(PrintStream ps){
    root.dump(ps, "");
  }

  public static void main(String args[]){
  }
}
