Moved SCL parser generator to platform repository.

[simantics/platform.git] / bundles / org.simantics.scl.compiler / src / org / simantics / scl / compiler / parser / generator / compression / CompressTable.java

diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/generator/compression/CompressTable.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/generator/compression/CompressTable.java
new file mode 100644 (file)
index 0000000..d2b7971
--- /dev/null
+++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/generator/compression/CompressTable.java
@@ -0,0 +1,101 @@
+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);
+    }
+    
+}