From 63aa39bbdac0e990102d3b51138de7d9e5eb7163 Mon Sep 17 00:00:00 2001
From: adam <adam@megacz.com>
Date: Thu, 8 Apr 2004 03:28:48 +0000
Subject: [PATCH] make runtime independent of foo_alloc

darcs-hash:20040408032848-5007d-87037bbfd11863eef9d3baea5f8b2c3df1fb479a.gz
---
 src/org/ibex/Box.java          |   34 ++++++++++++++--------------------
 src/org/ibex/util/Simplex.java |   30 +++++++++++++++++-------------
 src/org/ibex/util/Vec.java     |   38 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 69 insertions(+), 33 deletions(-)

diff --git a/src/org/ibex/Box.java b/src/org/ibex/Box.java
index e3e30ec..fb4e985 100644
--- a/src/org/ibex/Box.java
+++ b/src/org/ibex/Box.java
@@ -277,10 +277,9 @@ public final class Box extends JSScope implements Scheduler.Task {
     }
 
     private static float[] coeff = null;
-    private static Simplex lp_h = new Simplex(100, 100, 300);
-    private static Simplex lp = new Simplex(100, 100, 300);
+    private static Simplex lp_h = new Simplex(65535, 65535, 65535);
+    private static Simplex lp = new Simplex(65535, 65535, 65535);
 
-    // FIXME: numboxes^2, and damn ugly to boot
     private static int[] regions = new int[65535];
     private static int[] regions_v = new int[65535];
     private static int numregions = 0;
@@ -291,18 +290,18 @@ public final class Box extends JSScope implements Scheduler.Task {
     private void computeRegions() {
         numregions = 0;
         for(Box c = firstPackedChild(); c != null; c = c.nextPackedSibling()) {
-            int target = c.col;
-            for(boolean stop = false;;) {
-                for(int i=0; i<=numregions; i++) {
-                    if (i == numregions) { regions[numregions++] = target; break; }
-                    if (target == regions[i]) break;
-                    if (target < regions[i]) { int tmp = target; target = regions[i]; regions[i] = tmp; }
-                }
-                if (stop) break;
-                stop = true;
-                target = min(cols, c.col+c.colspan);
-            }
+            regions[numregions++] = c.col;
+            regions[numregions++] = min(cols, c.col+c.colspan);
+        }
+        Vec.sortInts(regions, 0, numregions);
+        int j = 0;
+        int newnumregions = numregions;
+        for(int i=1; i<numregions; i++) {
+            if (regions[j] != regions[i]) j++;
+            else newnumregions--;
+            regions[j] = regions[i];
         }
+        numregions = newnumregions;
         if (regions[numregions-1] == cols) numregions--;
         else regions[numregions] = cols;
     }
@@ -321,7 +320,7 @@ public final class Box extends JSScope implements Scheduler.Task {
 
             for(int i=0; i<coeff.length; i++) coeff[i] = (float)0.0;
             if (!findMinimum) {
-                coeff[numregions*2+numkids] = (float)10000.0;               // priority 1: sum of columns no greater than parent
+                coeff[numregions*2+numkids] = (float)10000.0;           // priority 1: sum of columns no greater than parent
                 for(int i=numregions*2; i<numregions*2+numkids; i++) coeff[i] = (float)100.0;  // priority 2: honor maxwidths
                 for(int i=numregions; i<numregions*2; i++) coeff[i] = (float)(0.1);            // priority 3: equalize columns
             } else {
@@ -329,11 +328,6 @@ public final class Box extends JSScope implements Scheduler.Task {
             }
             lp_h.setObjective(coeff, false);
 
-            for(int i=0; i<numregions; i++) {
-                for(int j=0; j<coeff.length; j++) coeff[j] = j==i ? (float)1.0 : (float)0.0;
-                lp_h.add_constraint(coeff, Simplex.GE, (float)0.0);
-            }
-
             // priority 1: sum of columns as close to parent's width as possible
             for(int i=0; i<coeff.length; i++) coeff[i] = (i<numregions) ? (float)(regions[i+1] - regions[i]) : (float)0.0;
             coeff[numregions*2+numkids] = (float)-1.0;
diff --git a/src/org/ibex/util/Simplex.java b/src/org/ibex/util/Simplex.java
index e8871ca..2ae314a 100644
--- a/src/org/ibex/util/Simplex.java
+++ b/src/org/ibex/util/Simplex.java
@@ -256,9 +256,7 @@ public class Simplex {
             epsel=DEF_EPSEL;
             non_zeros=0;
 
-            for(int i = 0; i < mat_alloc; i++) { set_row_nr(mat,i, 0); set_value(mat, i, 0); }
-            for(int i = 0; i < mat_alloc; i++)   col_no[i] = 0;
-            for(int i = 0; i < columns + 1; i++) col_end[i] = 0;
+            for(int i = 0; i < col_end.length; i++) col_end[i] = 0;
             for(int i = 0; i < rows + 1; i++)    row_end[i] = 0;
             for(int i = 0; i < rows + 1; i++)   orig_rh[i] = 0;
             for(int i = 0; i < rows + 1; i++)   rh[i] = 0;
@@ -272,9 +270,6 @@ public class Simplex {
             for(int i = 0; i <= rows; i++)     { bas[i]=i; basis[i]=TRUE; }
             for(int i = rows + 1; i <= sum; i++) basis[i]=FALSE;
             for(int i = 0 ; i <= sum; i++)       lower[i]=TRUE;
-            for(int i = 0; i < eta_alloc; i++) eta_value[i] = 0;
-            for(int i = 0; i < eta_alloc; i++) eta_row_nr[i] = 0;
-            for(int i = 0; i < rows_alloc + max_num_inv; i++) eta_col_end[i] = 0;
             for(int i = 0; i <= sum; i++) solution[i] = 0;
             for(int i = 0; i <= sum; i++) best_solution[i] = 0;
             for(int i = 0; i <= rows; i++) duals[i] = 0;
@@ -1295,7 +1290,7 @@ public class Simplex {
         }
 
         public int solve() {
-            int result;
+            int result = FAILURE;
             if (active == FALSE) set_globals();
             total_iter  = 0;
             max_level   = 1;
@@ -1320,16 +1315,25 @@ public class Simplex {
                 eta_size  = Eta_size;
                 eta_alloc = Eta_alloc;
                 num_inv   = Num_inv;
-                return(result);
             }
-            return(FAILURE);
+            for(int i = 0; i < maxmat; i++) { set_row_nr(mat,i, 0); set_value(mat, i, 0); }
+            for(int i = 0; i < maxmat; i++)   col_no[i] = 0;
+
+            // FIXME: not sure about this
+            for(int i = 0; i < Eta_size; i++) eta_value[i] = 0;
+            for(int i = 0; i < Eta_size; i++) eta_row_nr[i] = 0;
+            for(int i = 0; i < Eta_size; i++) eta_col_end[i] = 0;
+
+            maxmat = 0;
+            return(result);
         }
 
+    private int maxmat = 0;
     private final static float round( float val, float eps) { return (Math.abs(val) < eps) ? 0 : val; }
-    static int get_row_nr(MatrixArray m, int i) { return m.row_nr[i]; }
-    static void set_row_nr(MatrixArray m, int i, int val) { m.row_nr[i] = val; }
-    static float get_value(MatrixArray m, int i) { return m.value[i]; }
-    static void set_value(MatrixArray m, int i, float val) { m.value[i] = val; }
+    int get_row_nr(MatrixArray m, int i) { return m.row_nr[i]; }
+    void set_row_nr(MatrixArray m, int i, int val) { m.row_nr[i] = val; maxmat = Math.max(i, maxmat); }
+    float get_value(MatrixArray m, int i) { return m.value[i]; }
+    void set_value(MatrixArray m, int i, float val) { m.value[i] = val; maxmat = Math.max(i, maxmat); }
     public static class MatrixArray {
         public int[] row_nr;
         public float[] value;
diff --git a/src/org/ibex/util/Vec.java b/src/org/ibex/util/Vec.java
index e120be5..71a0437 100644
--- a/src/org/ibex/util/Vec.java
+++ b/src/org/ibex/util/Vec.java
@@ -180,4 +180,42 @@ public final class Vec implements Serializable {
             vec.store[b] = tmp;
         }
     }
+
+    public static final void sortInts(int[] a, int start, int end) {
+        int tmpa;
+        if(start >= end) return;
+        if(end-start <= 6) {
+            for(int i=start+1;i<=end;i++) {
+                tmpa = a[i];
+                int j;
+                for(j=i-1;j>=start;j--) {
+                    if(a[j] <= tmpa) break;
+                    a[j+1] = a[j];
+                }
+                a[j+1] = tmpa;
+            }
+            return;
+        }
+
+        int pivot = a[end];
+        int lo = start - 1;
+        int hi = end;
+
+        do {
+            while(a[++lo] < pivot) { }
+            while((hi > lo) && a[--hi] > pivot) { }
+            swapInts(a, lo, hi);
+        } while(lo < hi);
+        swapInts(a, lo, end);
+        sortInts(a, start, lo-1);
+        sortInts(a, lo+1, end);
+    }
+
+    private static final void swapInts(int[] vec, int a, int b) {
+        if(a != b) {
+            int tmp = vec[a];
+            vec[a] = vec[b];
+            vec[b] = tmp;
+        }
+    }
 }
-- 
1.7.10.4