Changeset 1064 for cpp/frams/model/similarity/EMD

Timestamp:

01/26/21 18:50:37 (4 years ago)

Author:

Maciej Komosinski

Message:

Properly allocated and de-allocated dynamic arrays of size calculated in runtime, not relying on g++ "extension"

Location:

cpp/frams/model/similarity/EMD

Files:

• emd.c (modified) (12 diffs)
• emd.h (modified) (2 diffs)

cpp/frams/model/similarity/EMD/emd.c

@@ -2 +2 @@
     emd.c
 
-    Last update: 3/14/98
+    Last update: 3/14/98 (but see emd.h for a list newer changes)
 
     An implementation of the Earth Movers Distance.
@@ -13 +13 @@
     E-Mail: rubner@cs.stanford.edu   URL: http://robotics.stanford.edu/~rubner/emd/default.htm
 */
+
+// For a list of changes since 2020, see emd.h
 
 #include <stdio.h>
@@ -98 +100 @@
 {
   int itr;
-  int max_n = (_n1 > _n2) ? _n1 : _n2;
+  int max_n = max(_n1, _n2); //max_n was introduced in r1062 instead of the #defined constant MAX_SIG_SIZE1=1000 in the original implementation. max_n is better than the constant, but it would be even better to use either _n1 or _n2, if we only knew what size each individual array should precisely have.
   double totalCost;
   float w;
   node2_t *XP;
   flow_t *FlowP;
-  node1_t U[max_n], V[max_n];
+  node1_t *U=new node1_t[max_n], *V=new node1_t[max_n];
   /* THE COST MATRIX */
   float** _CM = new float*[_n1];
@@ -189 +191 @@
   delete[] _RowsX;
   delete[] _ColsX;  
+
+  delete[] U;
+  delete[] V;
   
   /* RETURN THE NORMALIZED COST == EMD */    
@@ -206 +211 @@
 {
   int i, j;
-  int max_n = (_n1 > _n2) ? _n1 : _n2;
+  int max_n = max(_n1, _n2); //max_n was introduced in r1062 instead of the #defined constant MAX_SIG_SIZE1=1000 in the original implementation. max_n is better than the constant, but it would be even better to use either _n1 or _n2, if we only knew what size each individual array should precisely have.
   double sSum, dSum, diff;
   feature_t *P1, *P2;
-  double S[max_n], D[max_n];
+  double *S=new double[max_n], *D=new double[max_n];
 
   
@@ -272 +277 @@
 
   _EnterX = _EndX++;  /* AN EMPTY SLOT (ONLY _n1+_n2-1 BASIC VARIABLES) */
+
+  delete[] S;
+  delete[] D;
 
   return sSum > dSum ? dSum : sSum;
@@ -465 +473 @@
 static void newSol(int _n1, int _n2, node2_t * _XV, char **_IsX, node2_t **_RowsX, node2_t **_ColsX)
 {
-    int i, j, k, max_n = (_n1 > _n2) ? _n1 : _n2;
+    int i, j, k;
+    int max_n = max(_n1, _n2); //max_n was introduced in r1062 instead of the #defined constant MAX_SIG_SIZE1=1000 in the original implementation. max_n is better than the constant, but it would be even better to use either _n1 or _n2, if we only knew what size each individual array should precisely have.
     double xMin;
     int steps;
-    node2_t *Loop[2*max_n], *CurX, *LeaveX;
+    node2_t **Loop=new node2_t*[2*max_n], *CurX, *LeaveX;
  
 #if DEBUG_LEVEL > 3
@@ -534 +543 @@
     /* SET _EnterX TO BE THE NEW EMPTY SLOT */
     _EnterX = LeaveX;
+
+        delete[] Loop;
 }
 
@@ -543 +554 @@
 static int findLoop(node2_t **Loop, int _n1, int _n2, node2_t *_XV, node2_t **_RowsX, node2_t **_ColsX)
 {
-  int i, steps, max_n = (_n1 > _n2) ? _n1 : _n2;
+  int i, steps;
+  int max_n = max(_n1, _n2); //max_n was introduced in r1062 instead of the #defined constant MAX_SIG_SIZE1=1000 in the original implementation. max_n is better than the constant, but it would be even better to use either _n1 or _n2, if we only knew what size each individual array should precisely have.
   node2_t **CurX, *NewX;
-  char IsUsed[2*max_n]; 
+  char *IsUsed=new char[2*max_n]; 
  
   for (i=0; i < _n1+_n2; i++)
@@ -627 +639 @@
 #endif
 
+  delete[] IsUsed;
+
   return steps;
 }
@@ -637 +651 @@
 static void russel(double *S, double *D, int _n1, int _n2, float **_CM, char **_IsX, node2_t **_RowsX, node2_t **_ColsX)
 {
-  int i, j, found, minI, minJ, max_n = (_n1 > _n2) ? _n1 : _n2;
+  int i, j, found, minI, minJ;
+  int max_n = max(_n1, _n2); //max_n was introduced in r1062 instead of the #defined constant MAX_SIG_SIZE1=1000 in the original implementation. max_n is better than the constant, but it would be even better to use either _n1 or _n2, if we only knew what size each individual array should precisely have.
   double deltaMin, oldVal, diff;
   double** Delta = new double*[_n1];
   for(int k = 0; k < _n1; ++k)
     Delta[k] = new double[_n2];
-  node1_t Ur[max_n], Vr[max_n];
+  node1_t *Ur=new node1_t[max_n], *Vr=new node1_t[max_n];
   node1_t uHead, *CurU, *PrevU;
   node1_t vHead, *CurV, *PrevV;
@@ -790 +805 @@
         }
     } while (uHead.Next != NULL || vHead.Next != NULL);
+
+        delete[] Ur;
+        delete[] Vr;
     for(int k = 0; k < _n1; ++k)
       delete[] Delta[k];

cpp/frams/model/similarity/EMD/emd.h

@@ -4 +4 @@
     emd.h
 
-    Last update: 3/24/98
+    Last update: 3/24/98 (but see below for newer changes)
 
     An implementation of the Earth Movers Distance.
@@ -15 +15 @@
     E-Mail: rubner@cs.stanford.edu   URL: http://robotics.stanford.edu/~rubner/emd/default.htm
 */
+
+// List of changes since 2020, compared to the original implementation:
+// r1050: Renamed variables that caused problems with g++ 7.3.0
+// r1062: Global static arrays moved to a function and now allocated dynamically; removed #defined limit of MAX_SIG_SIZE=1000
+
 
 /* DEFINITIONS */