bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/generator/compression/GCCompress.java

   1 package org.simantics.scl.compiler.parser.generator.compression;
   2
   3 import java.util.Arrays;
   4
   5 import org.simantics.scl.compiler.parser.generator.table.ParseTableBuilder;
   6
   7 public class GCCompress {
   8
   9     public static final int DONT_CARE = ParseTableBuilder.ERROR_ACTION;
  10
  11     private static int[][] compressRows(int[] colors, final int[][] table) {
  12         final int columns = table[0].length;
  13         int colorCount = GraphColoring.color(colors, new GraphColoring.ColGraph() {
  14             @Override
  15             public int size() {
  16                 return table.length;
  17             }
  18
  19             @Override
  20             public boolean areConnected(int a, int b) {
  21                 int[] aRow = table[a];
  22                 int[] bRow = table[b];
  23                 for(int i=0;i<columns;++i) {
  24                     int aV = aRow[i];
  25                     int bV = bRow[i];
  26                     if(aV != DONT_CARE && bV != DONT_CARE && aV != bV)
  27                         return true;
  28                 }
  29                 return false;
  30             }
  31         });
  32
  33         final int[][] compr = new int[colorCount][columns];
  34         for(int i=0;i<compr.length;++i)
  35             Arrays.fill(compr[i], DONT_CARE);
  36
  37         for(int i=0;i<table.length;++i) {
  38             int color = colors[i];
  39             int[] inRow = table[i];
  40             int[] outRow = compr[color];
  41             for(int j=0;j<columns;++j) {
  42                 int v = inRow[j];
  43                 if(v != DONT_CARE)
  44                     outRow[j] = v;
  45             }
  46         }
  47
  48         return compr;
  49     }
  50
  51     private static int[][] compressColumns(int[] colors, final int[][] table) {
  52         final int columns = table[0].length;
  53         int colorCount = GraphColoring.color(colors, new GraphColoring.ColGraph() {
  54             @Override
  55             public int size() {
  56                 return columns;
  57             }
  58
  59             @Override
  60             public boolean areConnected(int a, int b) {
  61                 for(int i=0;i<table.length;++i) {
  62                     int[] row = table[i];
  63                     int aV = row[a];
  64                     int bV = row[b];
  65                     if(aV != DONT_CARE && bV != DONT_CARE && aV != bV)
  66                         return true;
  67                 }
  68                 return false;
  69             }
  70         });
  71
  72         final int[][] compr = new int[table.length][colorCount];
  73         for(int i=0;i<compr.length;++i) {
  74             Arrays.fill(compr[i], DONT_CARE);
  75         }
  76         for(int i=0;i<table.length;++i) {
  77             for(int j=0;j<columns;++j) {
  78                 int v = table[i][j];
  79                 if(v != DONT_CARE) {
  80                     int color = colors[j];
  81                     compr[i][color] = v;
  82                 }
  83             }
  84         }
  85
  86         return compr;
  87     }
  88
  89     public static CompressedTable compress(int[][] table) {
  90         System.out.println("Compress:");
  91         System.out.println("    Rows: " + table.length);
  92         System.out.println("    Columns: " + table[0].length);
  93
  94         int[] rowIndex = new int[table.length];
  95         int[] columnIndex = new int[table[0].length];
  96
  97         table = compressRows(rowIndex, table);
  98         table = compressColumns(columnIndex, table);
  99
 100         System.out.println("    Compressed rows: " + table.length);
 101         System.out.println("    Compressed columns: " + table[0].length);
 102
 103         int columns = table[0].length;
 104
 105         int[] compressedTable = new int[table.length * columns];
 106         for(int i=0;i<table.length;++i)
 107             System.arraycopy(table[i], 0, compressedTable, i*columns, columns);
 108         for(int i=0;i<rowIndex.length;++i)
 109             rowIndex[i] *= columns;
 110         return new CompressedTable(rowIndex, columnIndex, compressedTable);
 111
 112         //for(int[] row : table)
 113         //    System.out.println(Arrays.toString(row));
 114     }
 115
 116 }