[Avida-SVN] r3362 - in development/source: targets/unit-tests tools

[blwalker at myxo.css.msu.edu]

Author: blwalker
Date: 2009-08-10 12:58:07 -0400 (Mon, 10 Aug 2009)
New Revision: 3362

Modified:
   development/source/targets/unit-tests/main.cc
   development/source/tools/tArray.h
Log:

Adds an iterative mergesort to tArray, along with a simple unit test.

Reasoning: it seems reasonable to wish to sort a tArray.  The only current way is to use tArray::QSort, which wraps qsort.  However, since qsort may have different implementations, it may not always sort elements of the same value in the same order, therefore possibly breaking consistency in the case of, oh, sorting phenotypes by # of cpus -- two different phenotypes with the same number of cpus might appear in different orders.  Therefore it is necessary to have our own sort.
The sort I am most comfortable with is mergesort, and I'm definitely not up to writing a well-optimized quicksort.  Therefore I wrote a mergesort, which I did not optimize but should serve well enough.

QSort ought to be perfectly fine to use when sorting tArrays not composed of elements which have this particular problem (same value for sorting, but actually different).


Modified: development/source/targets/unit-tests/main.cc
===================================================================
--- development/source/targets/unit-tests/main.cc	2009-08-07 00:40:58 UTC (rev 3361)
+++ development/source/targets/unit-tests/main.cc	2009-08-10 16:58:07 UTC (rev 3362)
@@ -24,6 +24,7 @@
 
 #include <iostream>
 #include <iomanip>
+#include "functions.h"
 
 using namespace std;
 
@@ -94,6 +95,22 @@
     for (tArray<int>::iterator it = test1.begin(); it != test1.end(); it++) (*it) = -2;
     for (int i = 0; i < test1.GetSize(); i++) if (test1[i] != -2) result = false;
     ReportTestResult("STL-style iterator", result);
+    
+    result = true;
+    tArray<int> test3(10);
+    test3[0] = 3;
+    test3[1] = 9;
+    test3[2] = 0;
+    test3[3] = -1;
+    test3[4] = 2;
+    test3[5] = 3;
+    test3[6] = 7;
+    test3[7] = -3;
+    test3[8] = 0;
+    test3[9] = 4;
+    test3.MergeSort(IntCompareFunction);
+    for(int i = 0; i < test3.GetSize() - 1; i++) if (test3[i] > test3[i+1]) result = false;
+    ReportTestResult("MergeSort", result);
   }
 };
 

Modified: development/source/tools/tArray.h
===================================================================
--- development/source/tools/tArray.h	2009-08-07 00:40:58 UTC (rev 3361)
+++ development/source/tools/tArray.h	2009-08-10 16:58:07 UTC (rev 3362)
@@ -46,7 +46,7 @@
 private:
   T* m_data;  // Data Elements
   int m_size; // Number of Elements
-
+  
 public:
   typedef T* iterator; //!< STL-compatible iterator.
   typedef const T* const_iterator; //!< STL-compatible const_iterator.
@@ -223,6 +223,57 @@
   {
     qsort(m_data, m_size, sizeof(m_data[0]), comparator);
   }
+  
+  
+  // @blw iterative mergesort, pretty much unoptimized
+  // exists so as not to depend on qsort (which may differ / break consistency)
+  // and because it is pretty easy to write for blw
+  void MergeSort(int ( * comparator ) ( const void *, const void * ))
+  {
+    /* Blocks of size blocksize are sorted: merge each pair into a sorted block */
+    for (int blocksize = 1; blocksize < m_size; blocksize *= 2) {
+      for (int block = 0; block < m_size / blocksize; block += 2) {
+        
+        // merge sorted blocks into sorted result block
+        int leftstart = block * blocksize;
+        const int leftend = (block + 1) * blocksize;
+        int rightstart = (block + 1) * blocksize;
+        const int rightend = m_size < (block + 2) * blocksize ? m_size : (block + 2) * blocksize;
+        int resultindex = 0;
+        tArray result(rightend - leftstart);
+        
+        while (leftstart < leftend && rightstart < rightend) {
+          if (comparator(&(m_data[leftstart]), &(m_data[rightstart])) <= 0) {
+            result[resultindex] = m_data[leftstart];
+            leftstart++;
+          }
+          else {
+            result[resultindex] = m_data[rightstart];
+            rightstart++;
+          }
+          resultindex++;
+        }
+        
+        while (leftstart < leftend) {
+          result[resultindex] = m_data[leftstart];
+          leftstart++;
+          resultindex++;
+        }  
+        
+        while (rightstart < rightend) {
+          result[resultindex] = m_data[rightstart];
+          rightstart++;
+          resultindex++;
+        }
+        
+        // replace blocks with result block
+        leftstart = block * blocksize;
+        for (int i = leftstart; i < rightend; i++) {
+          m_data[i] = result[i - leftstart];
+        }
+      }
+    }
+  }
 
 };