Merge pull request #8 from dhuth/master

w/ python test suite

8 files changed, 274 insertions, 0 deletions

diff --git a/test-chill/unit-tests/cprog/Makefile b/test-chill/unit-tests/cprog/Makefile
new file mode 100644
index 0000000..f5f2608
--- /dev/null
+++ b/test-chill/unit-tests/cprog/Makefile
@@ -0,0 +1,17 @@
+OBJS = $(patsubst %.cc, %.o, $(wildcard *.cc))
+
+.PHONY: all
+all: sorter
+
+$(OBJS): %.o: %.cc
+	g++ -g -fprofile-arcs -ftest-coverage -c $< -o $@
+
+.PHONY: sorter
+sorter: $(OBJS)
+	g++ -g -fprofile-arcs -ftest-coverage -o bin/sorter $(OBJS)
+
+.PHONY: clean
+clean:
+	rm -f *.o
+	rm -f *.gcno *.gcda *.gcov
+	rm -f bin/sorter
diff --git a/test-chill/unit-tests/cprog/MergeSorter.cc b/test-chill/unit-tests/cprog/MergeSorter.cc
new file mode 100644
index 0000000..6e747a3
--- /dev/null
+++ b/test-chill/unit-tests/cprog/MergeSorter.cc
@@ -0,0 +1,77 @@
+#include "MergeSorter.h"
+
+/* Python
+def msort(lst, start, end, pindent = 0):
+    if start == end:
+        return
+    center = start + ((end - start) // 2)
+    print(' '*pindent + "SPLIT {}|{}".format(lst[start:center+1], lst[center+1:end+1]))
+    msort(lst, start, center, pindent+1)
+    msort(lst, center+1, end, pindent+1)
+    left = list(lst[start:center+1])
+    right = list(lst[center+1:end+1])
+    print(' '*pindent + "MERGE {}|{}".format(lst[start:center+1], lst[center+1:end+1]))
+    i,j = 0, 0
+    for k in range(start, end+1):
+        if i >= len(left):
+            lst[k] = right[j]
+            j += 1
+            print(' '*(pindent+1) + 'pull j: {} {} {}'.format(lst[start:k+1], left[i:], right[j:]))
+        elif j >= len(right):
+            lst[k] = left[i]
+            i += 1
+            print(' '*(pindent+1) + 'pull i: {} {} {}'.format(lst[start:k+1], left[i:], right[j:]))
+        elif left[i] > right[j]:
+            lst[k] = right[j]
+            j += 1
+            print(' '*(pindent+1) + 'pull j: {} {} {}'.format(lst[start:k+1], left[i:], right[j:]))
+        else:
+            lst[k] = left[i]
+            i += 1
+            print(' '*(pindent+1) + 'pull i: {} {} {}'.format(lst[start:k+1], left[i:], right[j:]))
+    print(' '*pindent + "-- {}".format(lst[start:end+1]))
+        
+
+if __name__ == '__main__':
+    import random as r
+    x = [int(r.random()*12) for i in range(7)]
+    print(x)
+    msort(x, 0, len(x)-1)
+    print(x)
+*/
+
+static void mergesort(std::vector<int>& lst, int start, int end) {
+    if(start == end) return;
+    int center = start + (end-start)/2;
+    mergesort(lst, start, center);
+    mergesort(lst, center+1, end);
+    std::vector<int> left = std::vector<int>(lst.begin()+start, lst.begin()+(center+1));
+    std::vector<int> right = std::vector<int>(lst.begin()+(center+1),lst.begin()+(end+1));
+    int i = 0;
+    int j = 0;
+    for(int k = start; k < (end+1); k++) {
+        if (i >= left.size()) {
+            lst[k] = right[j++];
+        }
+        else if(j >= right.size()) {
+            lst[k] = left[i++];
+        }
+        else if(left[i] > right[j]) {
+            lst[k] = right[j++];
+        }
+        else {
+            lst[k] = left[i++];
+        }
+    }
+}
+
+MergeSorter::MergeSorter() {
+    this->name = std::string("mergesort");
+}
+
+MergeSorter::~MergeSorter() {
+}
+
+void MergeSorter::sort(std::vector<int>& list) const {
+    mergesort(list, 0, list.size()-1);
+}
diff --git a/test-chill/unit-tests/cprog/MergeSorter.h b/test-chill/unit-tests/cprog/MergeSorter.h
new file mode 100644
index 0000000..e2ed391
--- /dev/null
+++ b/test-chill/unit-tests/cprog/MergeSorter.h
@@ -0,0 +1,14 @@
+#ifndef MERGE_SORTER_H
+#define MERGE_SORTER_H
+
+#include <vector>
+#include "Sorter.h"
+
+class MergeSorter : public Sorter {
+public:
+    MergeSorter();
+    virtual ~MergeSorter();
+    virtual void sort(std::vector<int>& list) const;
+};
+
+#endif
diff --git a/test-chill/unit-tests/cprog/QuickSorter.cc b/test-chill/unit-tests/cprog/QuickSorter.cc
new file mode 100644
index 0000000..3ade346
--- /dev/null
+++ b/test-chill/unit-tests/cprog/QuickSorter.cc
@@ -0,0 +1,83 @@
+#include "QuickSorter.h"
+
+/* Python
+
+def swap(l, i, k):
+    v = l[i]
+    l[i] = l[k]
+    l[k] = v
+    print(str(l))
+
+def partition(l, start, end):
+    print("PARTITION {} [{}:{}]".format(l, start, end))
+    p_value = l[end]
+    p_index = end-1
+    
+    for i in range(start, end):
+        while(i < p_index and l[i] >= p_value):
+            swap(l, i, p_index)
+            p_index -= 1
+        while(i >= p_index and l[i] < p_value):
+            swap(l, i, p_index)
+            p_index += 1
+    swap(l, p_index, end)
+    print("DONE {}|[{}]|{}:{}".format(l[start:p_index], l[p_index], l[p_index+1:end+1], p_value))
+    return p_index
+
+def qsort(l, i, k):
+    if i < k:
+        p = partition(l, i, k)
+        qsort(l,i,p-1)
+        qsort(l,p+1,k)
+
+if __name__ == "__main__":
+    import random as r
+    x = [int(r.random()*12) for i in range(12)]
+    print(x)
+    qsort(x, 0, len(x)-1)
+    print(x)
+    
+*/
+
+static void swap(std::vector<int>& list, int i, int k) {
+    int v = list[i];
+    list[i] = list[k];
+    list[k] = v;
+}
+
+static int partition(std::vector<int>& list, int i, int k) {
+    int pivot_value = list[k];
+    int pivot_index = k - 1;
+    
+    for(int index = i; index < k; index++) {
+        while((index < pivot_index) && (list[index] >= pivot_value)) {
+            swap(list, index, pivot_index);
+            pivot_index--;
+        }
+        while((index >= pivot_index) && (list[index] < pivot_value)) {
+            swap(list, index, pivot_index);
+            pivot_index++;
+        }
+    }
+    swap(list, pivot_index, k);
+    return pivot_index;
+}
+
+static void quicksort(std::vector<int>& list, int i, int k) {
+    if(i < k) {
+        int p = partition(list, i, k);
+        quicksort(list, i, p-1);
+        quicksort(list, p+1, k);
+    }
+}
+
+QuickSorter::QuickSorter() {
+    this->name = std::string("quicksort");
+}
+
+QuickSorter::~QuickSorter() {
+}
+
+void QuickSorter::sort(std::vector<int>& list) const {
+    quicksort(list, 0, list.size()-1);
+}
diff --git a/test-chill/unit-tests/cprog/QuickSorter.h b/test-chill/unit-tests/cprog/QuickSorter.h
new file mode 100644
index 0000000..81919dd
--- /dev/null
+++ b/test-chill/unit-tests/cprog/QuickSorter.h
@@ -0,0 +1,14 @@
+#ifndef QUICK_SORTER_H
+#define QUICK_SORTER_H
+
+#include <vector>
+#include "Sorter.h"
+
+class QuickSorter : public Sorter {
+public:
+    QuickSorter();
+    virtual ~QuickSorter();
+    virtual void sort(std::vector<int>& list) const;
+};
+
+#endif
diff --git a/test-chill/unit-tests/cprog/Sorter.cc b/test-chill/unit-tests/cprog/Sorter.cc
new file mode 100644
index 0000000..a1ae5ec
--- /dev/null
+++ b/test-chill/unit-tests/cprog/Sorter.cc
@@ -0,0 +1,8 @@
+#include "Sorter.h"
+
+Sorter::Sorter() {
+}
+
+Sorter::~Sorter() {
+}
+
diff --git a/test-chill/unit-tests/cprog/Sorter.h b/test-chill/unit-tests/cprog/Sorter.h
new file mode 100644
index 0000000..abf8f82
--- /dev/null
+++ b/test-chill/unit-tests/cprog/Sorter.h
@@ -0,0 +1,16 @@
+#ifndef SORTER_H
+#define SORTER_H
+
+#include <string>
+#include <vector>
+
+class Sorter {
+public:
+    Sorter();
+    virtual ~Sorter();
+    
+    std::string name;
+    virtual void sort(std::vector<int>& list) const = 0;
+};
+
+#endif
diff --git a/test-chill/unit-tests/cprog/main.cc b/test-chill/unit-tests/cprog/main.cc
new file mode 100644
index 0000000..3fe960b
--- /dev/null
+++ b/test-chill/unit-tests/cprog/main.cc
@@ -0,0 +1,45 @@
+#include <cstdio>
+#include <cstdlib>
+#include <map>
+#include <string>
+#include <vector>
+
+#include "Sorter.h"
+#include "QuickSorter.h"
+#include "MergeSorter.h"
+//#include "InsertionSorter.h"
+//#include "ShellSorter.h"
+
+void read_vector(std::vector<int>& vec, int start, int stop, char** argv) {
+    for(int i = start; i < stop; i++) {
+        vec.push_back((int)strtol(argv[i],NULL,0));
+    }
+}
+
+void print_vector(std::vector<int>& vec) {
+    printf("[");
+    for(std::vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
+        printf(" %d ", *iter);
+    }
+    printf("]\n");
+}
+
+void addsorter(std::map<std::string, Sorter*>& m, Sorter* s) {
+    m[s->name] = s;
+}
+
+int main(int argc, char** argv) {
+    std::map<std::string, Sorter*> sorter_map;
+    std::vector<int> vec;
+    
+    read_vector(vec, 2, argc, argv);
+    print_vector(vec);
+    
+    addsorter(sorter_map, new QuickSorter());
+    addsorter(sorter_map, new MergeSorter());
+    //addsorter(sorter_map, new InsertionSorter());
+    //addsorter(sorter_map, new ShellSorter());
+    sorter_map[std::string(argv[1])]->sort(vec);
+    print_vector(vec);
+}
+