package org.simantics.scl.compiler.parser.generator.compression;

import java.util.Arrays;

public class CompressTable {

    private static class Row implements Comparable<Row> {
        int id;
        int density;
        int minPos;
        int maxPos;
        int[] data;
        int displacement;
        
        @Override
        public int compareTo(Row o) {
            return o.density < density ? 1 : o.density > density ? -1 : 0;
        }
    }
    
    public static CompressedTable compress(int[][] table_) {
        // Sort table by size
        Row[] table = new Row[table_.length];
        for(int i=0;i<table.length;++i) {
            Row row = new Row();
            row.id = i;
            row.data = table_[i];
            int density = 0;
            int minPos = -1;
            int maxPos = -1;
            for(int j=0;j<row.data.length;++j) {
                int el = row.data[j];
                if(el != 0) {
                    ++density;
                    if(minPos == -1)
                        minPos = j;
                    maxPos = j;
                }
            }
            row.density = density;
            row.minPos = minPos;
            row.maxPos = maxPos;
            table[i] = row;
        }
        Arrays.sort(table);
        
        // Start to fill
        int width = table_.length == 0 ? 0 : table_[0].length;
        int capacity = 2*table_.length*width;
        int[] rowIds = new int[capacity];
        Arrays.fill(rowIds, -1);
        int[] values = new int[capacity];
        for(Row row : table) {
            if(row.density == 0) {
                row.displacement = capacity/2;
                continue;
            }
            tryAgain: for(int dId=0;dId<capacity;++dId) {
                int d = capacity/2 + ((dId&1)==0 ? dId/2 : -1-dId/2);
                for(int p = row.minPos;p<=row.maxPos;++p) {
                    int newValue = row.data[p];
                    
                    if(newValue != 0) {
                        int id = d+p;
                        if(rowIds[id] >= 0)
                            continue tryAgain;
                    }
                }
                row.displacement = d;
                for(int p = row.minPos;p<=row.maxPos;++p) {
                    int val = row.data[p];
                    if(val != 0) {
                        int id = d+p;
                        rowIds[id] = row.id;
                        values[id] = val;
                    }
                }
                break;
            }
        }
        
        // Produce final tables
        int minDis=capacity;
        int maxDis=0;
        for(Row row : table) {
            int d = row.displacement;
            if(d < minDis)
                minDis = d;
            if(d > maxDis)
                maxDis = d;
        }
        int[] displacement = new int[table.length];
        for(int i=0;i<table.length;++i)
            displacement[table[i].id] = table[i].displacement-minDis;
        rowIds = Arrays.copyOfRange(rowIds, minDis, maxDis+width);
        values = Arrays.copyOfRange(values, minDis, maxDis+width);
        
        return new CompressedTable(rowIds, values, displacement);
    }
    
}