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

   1 package org.simantics.scl.compiler.parser.generator.compression;
   2
   3 import java.util.Arrays;
   4
   5 public class CompressTable {
   6
   7     private static class Row implements Comparable<Row> {
   8         int id;
   9         int density;
  10         int minPos;
  11         int maxPos;
  12         int[] data;
  13         int displacement;
  14
  15         @Override
  16         public int compareTo(Row o) {
  17             return o.density < density ? 1 : o.density > density ? -1 : 0;
  18         }
  19     }
  20
  21     public static CompressedTable compress(int[][] table_) {
  22         // Sort table by size
  23         Row[] table = new Row[table_.length];
  24         for(int i=0;i<table.length;++i) {
  25             Row row = new Row();
  26             row.id = i;
  27             row.data = table_[i];
  28             int density = 0;
  29             int minPos = -1;
  30             int maxPos = -1;
  31             for(int j=0;j<row.data.length;++j) {
  32                 int el = row.data[j];
  33                 if(el != 0) {
  34                     ++density;
  35                     if(minPos == -1)
  36                         minPos = j;
  37                     maxPos = j;
  38                 }
  39             }
  40             row.density = density;
  41             row.minPos = minPos;
  42             row.maxPos = maxPos;
  43             table[i] = row;
  44         }
  45         Arrays.sort(table);
  46
  47         // Start to fill
  48         int width = table_.length == 0 ? 0 : table_[0].length;
  49         int capacity = 2*table_.length*width;
  50         int[] rowIds = new int[capacity];
  51         Arrays.fill(rowIds, -1);
  52         int[] values = new int[capacity];
  53         for(Row row : table) {
  54             if(row.density == 0) {
  55                 row.displacement = capacity/2;
  56                 continue;
  57             }
  58             tryAgain: for(int dId=0;dId<capacity;++dId) {
  59                 int d = capacity/2 + ((dId&1)==0 ? dId/2 : -1-dId/2);
  60                 for(int p = row.minPos;p<=row.maxPos;++p) {
  61                     int newValue = row.data[p];
  62
  63                     if(newValue != 0) {
  64                         int id = d+p;
  65                         if(rowIds[id] >= 0)
  66                             continue tryAgain;
  67                     }
  68                 }
  69                 row.displacement = d;
  70                 for(int p = row.minPos;p<=row.maxPos;++p) {
  71                     int val = row.data[p];
  72                     if(val != 0) {
  73                         int id = d+p;
  74                         rowIds[id] = row.id;
  75                         values[id] = val;
  76                     }
  77                 }
  78                 break;
  79             }
  80         }
  81
  82         // Produce final tables
  83         int minDis=capacity;
  84         int maxDis=0;
  85         for(Row row : table) {
  86             int d = row.displacement;
  87             if(d < minDis)
  88                 minDis = d;
  89             if(d > maxDis)
  90                 maxDis = d;
  91         }
  92         int[] displacement = new int[table.length];
  93         for(int i=0;i<table.length;++i)
  94             displacement[table[i].id] = table[i].displacement-minDis;
  95         rowIds = Arrays.copyOfRange(rowIds, minDis, maxDis+width);
  96         values = Arrays.copyOfRange(values, minDis, maxDis+width);
  97
  98         return new CompressedTable(rowIds, values, displacement);
  99     }
 100
 101 }