conflict resolve

3 files changed, 53 insertions, 39 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..45282db
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,7 @@
+/hungarian
+
+*~
+\#*\#
+.\#*
+*.bak
+*.swp
diff --git a/Makefile b/Makefile
index 4c02575..79c80f6 100644
--- a/Makefile
+++ b/Makefile
@@ -1,11 +1,14 @@
 all:
 	gcc -o "hungarian"{,.c}
 
+nodebug:
+	gcc -o "hungarian"{,.c}
+
 test:
 	./"hungarian"
 
 valgrind:
-	valgrind --leak-check=full ./"hungarian"
+	valgrind --tool=memcheck --leak-check=full ./"hungarian"
 
 clean:
 	if [ -f "hungarian" ]; then  unlink "hungarian";  fi
diff --git a/hungarian.c b/hungarian.c
index 90f9f64..f0bb446 100644
--- a/hungarian.c
+++ b/hungarian.c
@@ -93,22 +93,22 @@ typedef struct
      * The set of all limbs, a limb consist of 64 bits
      */
     cell* limbs;
-
+    
     /**
      * Singleton array with the index of the first non-zero limb
      */
     long* first;
-
+    
     /**
-     * Array the the index of the previous non-zero limb for echo limb
+     * Array the the index of the previous non-zero limb for each limb
      */
     long* prev;
-
+    
     /**
-     * Array the the index of the next non-zero limb for echo limb
+     * Array the the index of the next non-zero limb for each limb
      */
     long* next;
-
+    
 } BitSet;
 
 
@@ -139,8 +139,8 @@ int main(int argc, char** argv)
     asm("cpuid");
     asm volatile("rdtsc" : "=a" (a), "=d" (d));
     srand(((llong)a) | (((llong)d) << 32LL));
-
-  
+    
+    
     long n = 10, m = 15;
     
     long i;
@@ -174,8 +174,6 @@ int main(int argc, char** argv)
 	}
     }
     
-    //kuhn_match(table, n, m);
-    
     printf("\nInput:\n\n");
     print(t, n, m, null);
     
@@ -187,14 +185,14 @@ int main(int argc, char** argv)
     for (i = 0; i < n; i++)
         sum += *(*(t + *(*(assignment + i) + 0)) + *(*(assignment + i) + 1));
     printf("\n\nSum: %li\n\n", sum);
-
+    
     return 0;
 }
 
 void print(cell** t, long n, long m, long** assignment)
 {
     long i, j;
-
+    
     long** assigned = new_arrays(n);
     for (i = 0; i < n; i++)
     {
@@ -205,7 +203,7 @@ void print(cell** t, long n, long m, long** assignment)
     if (assignment != null)
         for (i = 0; i < n; i++)
 	    (*(*(assigned + **(assignment + i)) + *(*(assignment + i) + 1)))++;
-        
+    
     for (i = 0; i < n; i++)
     {
 	printf("    ");
@@ -224,11 +222,11 @@ void print(cell** t, long n, long m, long** assignment)
 /**
  * Calculates an optimal bipartite minimum weight matching using an
  * O(n³)-time implementation of The Hungarian Algorithm, also known
- * as Kuhn's Algorithm. This implemention is restricted to square
- * tables.
+ * as Kuhn's Algorithm.
  * 
  * @param   table  The table in which to perform the matching
- * @param   n      The dimension of the table
+ * @param   n      The height of the table
+ * @param   h      The width of the table
  * @return         The optimal assignment, an array of row–coloumn pairs
  */
 long** kuhn_match(cell** table, long n, long m)
@@ -239,7 +237,7 @@ long** kuhn_match(cell** table, long n, long m)
     
     kuhn_reduceRows(table, n, m);
     byte** marks = kuhn_mark(table, n, m);
-
+    
     boolean* rowCovered = new_booleans(n);
     boolean* colCovered = new_booleans(m);
     for (i = 0; i < n; i++)
@@ -249,13 +247,13 @@ long** kuhn_match(cell** table, long n, long m)
     }
     for (i = n; i < m; i++)
         *(colCovered + i) = false;
-
+    
     long* altRow = new_longs(n * m);
     long* altCol = new_longs(n * m);
     
     long* rowPrimes = new_longs(n);
     long* colMarks  = new_longs(m);
-
+    
     long* prime;
     
     for (;;)
@@ -307,7 +305,7 @@ void kuhn_reduceRows(cell** t, long n, long m)
 	for (j = 1; j < m; j++)
 	    if (min > *(ti + j))
 	        min = *(ti + j);
-
+	
 	for (j = 0; j < m; j++)
 	    *(ti + j) -= min;
     }
@@ -335,7 +333,7 @@ byte** kuhn_mark(cell** t, long n, long m)
         for (j = 0; j < m; j++)
  	    *(marksi + j) = UNMARKED;
     }
-
+    
     boolean* rowCovered = new_booleans(n);
     boolean* colCovered = new_booleans(m);
     for (i = 0; i < n; i++)
@@ -384,7 +382,7 @@ boolean kuhn_isDone(byte** marks, boolean* colCovered, long n, long m)
     for (j = 0; j < m; j++)
         if (*(colCovered + j))
 	    count++;
-        
+    
     return count == n;
 }
 
@@ -403,7 +401,7 @@ boolean kuhn_isDone(byte** marks, boolean* colCovered, long n, long m)
 long* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCovered, long n, long m)
 {
     long i, j;
-    BitSet zeroes = new_BitSet(n * n);
+    BitSet zeroes = new_BitSet(n * m);
     
     for (i = 0; i < n; i++)
         if (!*(rowCovered + i))
@@ -418,8 +416,14 @@ long* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCo
     {
         p = BitSet_any(zeroes);
 	if (p < 0)
+        {
+	    free(zeroes.limbs);
+	    free(zeroes.first);
+	    free(zeroes.next);
+	    free(zeroes.prev);
 	    return null;
-
+	}
+	
 	row = p / m;
 	col = p % m;
 	
@@ -432,12 +436,12 @@ long* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCo
 		markInRow = true;
 		col = j;
 	    }
-            
+	
 	if (markInRow)
 	{
 	    *(rowCovered + row) = true;
 	    *(colCovered + col) = false;
-                
+	    
 	    for (i = 0; i < n; i++)
 	        if ((*(*(t + i) + col) == 0) && (row != i))
 		{
@@ -446,7 +450,7 @@ long* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCo
 		    else
 		        BitSet_unset(zeroes, i * m + col);
 		}
-                
+	    
 	    for (j = 0; j < m; j++)
 	        if ((*(*(t + row) + j) == 0) && (col != j))
 		{
@@ -455,7 +459,7 @@ long* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCo
 		    else
 		        BitSet_unset(zeroes, row * m + j);
 		}
-                
+	    
 	    if ((!*(rowCovered + row)) && (!*(colCovered + col)))
 	        BitSet_set(zeroes, row * m + col);
 	    else
@@ -497,7 +501,7 @@ void kuhn_altMarks(byte** marks, long* altRow, long* altCol, long* colMarks, lon
     }
     for (i = n; i < m; i++)
         *(colMarks + i) = -1;
-        
+    
     for (i = 0; i < n; i++)
         for (j = 0; j < m; j++)
 	    if (*(*(marks + i) + j) == MARKED)
@@ -522,7 +526,7 @@ void kuhn_altMarks(byte** marks, long* altRow, long* altCol, long* colMarks, lon
 	*(altRow + index) = *(altRow + index - 1);
 	*(altCol + index) = col;
     }
-        
+    
     byte* markx;
     for (i = 0; i <= index; i++)
     {
@@ -587,7 +591,7 @@ void kuhn_addAndSubtract(cell** t, boolean* rowCovered, boolean* colCovered, lon
 long** kuhn_assign(byte** marks, long n, long m)
 {
     long** assignment = new_arrays(n);
-
+    
     long i, j;
     for (i = 0; i < n; i++)
     {
@@ -599,7 +603,7 @@ long** kuhn_assign(byte** marks, long n, long m)
 		*(*(assignment + i) + 1) = j;
 	    }
     }
-
+    
     return assignment;
 }
 
@@ -644,9 +648,9 @@ void BitSet_set(BitSet this, long i)
 {
     long j = i >> 6L;
     llong old = *(this.limbs + j);
-
+    
     *(this.limbs + j) |= 1LL << (llong)(i & 63L);
-
+    
     if ((!*(this.limbs + j)) ^ (!old))
     {
         j++;
@@ -669,7 +673,7 @@ void BitSet_unset(BitSet this, long i)
     llong old = *(this.limbs + j);
     
     *(this.limbs + j) &= ~(1LL << (llong)(i & 63L));
-  
+    
     if ((!*(this.limbs + j)) ^ (!old))
     {
 	j++;
@@ -678,7 +682,7 @@ void BitSet_unset(BitSet this, long i)
 	*(this.prev + n) = p;
 	*(this.next + p) = n;
 	if (*(this.first) == j)
-	    *(this.first) = *(this.next + j);
+	    *(this.first) = n;
     }
 }
 
@@ -692,7 +696,7 @@ long BitSet_any(BitSet this)
 {
     if (*(this.first) == 0L)
         return -1;
-            
+    
     long i = *(this.first) - 1L;
     return lb(*(this.limbs + i) & -*(this.limbs + i)) + (i << 6L);
 }
@@ -708,7 +712,7 @@ long lb(llong value)
 {
     long rc = 0L;
     llong v = value;
-            
+    
     if (v & 0xFFFFFFFF00000000LL)  {  rc |= 32L;  v >>= 32LL;  }
     if (v & 0x00000000FFFF0000LL)  {  rc |= 16L;  v >>= 16LL;  }
     if (v & 0x000000000000FF00LL)  {  rc |=  8L;  v >>=  8LL;  }