tasty cakes renaming and cleaning

fixed stupid placeholder file by using it as an anchor for the sorts methods instead.
added an efficient randomize list method in sorts.
using new randomize list method in sorts tester, removing yet more code.  mmmm.

diff --git a/nucleus/library/algorithms/placeholder.cpp b/nucleus/library/algorithms/placeholder.cpp
deleted file mode 100644 (file)
index 953ca62..0000000
--- a/nucleus/library/algorithms/placeholder.cpp
+++ /dev/null
@@ -1,8 +0,0 @@
-\r
-\r
-// sole purpose of this is to make the lib be generated,\r
-// even though we currently do not have any code that lives inside it.\r
-\r
-int __private_private_bogus_placeholder_xj27_qx19() { return 32; }\r
-\r
-\r

diff --git a/nucleus/library/algorithms/sorts.cpp b/nucleus/library/algorithms/sorts.cpp
new file mode 100644 (file)
index 0000000..dc964a5
--- /dev/null
+++ b/nucleus/library/algorithms/sorts.cpp
@@ -0,0 +1,2 @@
+
+#include "sorts.h"

diff --git a/nucleus/library/algorithms/sorts.h b/nucleus/library/algorithms/sorts.h
index 052ecb24419bf262326115193d08acc0e4c78609..592f9903add6815118a4837c4669db0a685ebb29 100644 (file)
--- a/nucleus/library/algorithms/sorts.h
+++ b/nucleus/library/algorithms/sorts.h
@@ -16,6 +16,8 @@
 // Please send updates for this code to: fred@gruntose.com -- Thanks, fred.
 //////////////
 
+#include <mathematics/chaos.h>
+
 namespace algorithms {
 
        /*
@@ -345,12 +347,27 @@ namespace algorithms {
         * operates in O(n log(n)) time on average, worst case O(n^2).
         * sorts the original array.
         */
-       template<class type>
+       template <class type>
        void quick_sort(type v[], int n, bool reverse = false)
        {
                inner_quick_sort(v, 0, n - 1, reverse);
        }
 
+       //////////////
+
+       //! handy method for randomizing the order of a list.  not strictly a sorting function...
+       template <class type>
+       void randomize_list(type v[], int n)
+       {
+               mathematics::chaos randomizer;
+               for (int i = 0; i < n; i++) {
+                       // we will swap with any element that is not prior to the current index; thus we allow
+                       // swapping the element with itself and later, but not with anything earlier.
+                       int swap_index = randomizer.inclusive(i, n - 1);
+                       swap_values(v, i, swap_index);
+               }
+       }
+
 }  // namespace.
 
 #endif // outer guard.

diff --git a/nucleus/library/tests_algorithms/test_sorts.cpp b/nucleus/library/tests_algorithms/test_sorts.cpp
index e936a721f63e64758388ecefaf55ae856e2762fd..6bc49557e619172ce2c9c1a7281e98383fee22b1 100644 (file)
--- a/nucleus/library/tests_algorithms/test_sorts.cpp
+++ b/nucleus/library/tests_algorithms/test_sorts.cpp
@@ -47,7 +47,7 @@ public:
 
        int *populate_random_c_array(int size);
        basis::array<int> populate_random_array(int size);
-       void rerandomize(int list[], int size);
+//     void rerandomize(int list[], int size);
        bool verify_ascending(const int *list, int size);
        bool verify_descending(const int *list, int size);
 
@@ -75,11 +75,11 @@ basis::array<int> test_sorts::populate_random_array(int size)
        return to_return;
 }
 
-void test_sorts::rerandomize(int list[], int size)
-{
-       for (int i = 0; i < size; i++)
-               list[i] = randomizer().inclusive(0, MAX_VALUE);
-}
+//void test_sorts::rerandomize(int list[], int size)
+//{
+//     for (int i = 0; i < size; i++)
+//             list[i] = randomizer().inclusive(0, MAX_VALUE);
+//}
 
 bool test_sorts::verify_ascending(const int *list, int size)
 {
@@ -114,7 +114,7 @@ void test_sorts::test_shell_sort(int size)
        ASSERT_TRUE(verify_ascending(list, size),
            "ordering check - list should be ordered at first check");
 
-       rerandomize(list, size);
+       randomize_list(list, size);
 
        // check a reversed sort.
        shell_sort(list, size, true);
@@ -136,7 +136,7 @@ void test_sorts::test_heap_sort(int size)
        ASSERT_TRUE(verify_ascending(list, size),
            "ordering check - list should be ordered at first check");
 
-       rerandomize(list, size);
+       randomize_list(list, size);
 
        // check a reversed sort.
        heap_sort(list, size, true);
@@ -161,7 +161,7 @@ void test_sorts::test_merge_sort(int size)
        ASSERT_TRUE(verify_ascending(ret.access(), size),
            "ordering check - list should be ordered at first check");
 
-       rerandomize(list.access(), size);
+       randomize_list(list.access(), size);
 
        // check a reversed sort.
        ret = merge_sort(list, true);
@@ -182,7 +182,7 @@ void test_sorts::test_quick_sort(int size)
 
 //     LOG(a_sprintf("after quick sort: %s", dump_list(list, size).s()));
 
-       rerandomize(list, size);
+       randomize_list(list, size);
 
        // check a reversed sort.
        quick_sort(list, size, true);

diff --git a/nucleus/library/tests_nodes/test_singly_linked_list.cpp b/nucleus/library/tests_nodes/test_singly_linked_list.cpp
index e5e88c5884a5ccd0406d379a31ee85805ecd4a43..391cac9dc20b1a8024aea339d3caedfa9abbe022 100644 (file)
--- a/nucleus/library/tests_nodes/test_singly_linked_list.cpp
+++ b/nucleus/library/tests_nodes/test_singly_linked_list.cpp
@@ -90,7 +90,7 @@ int test_singly_linked_list::execute()
        b->set_next(c);
        c->set_next(d);
        d->set_next(e);
-//     e->set_next(NULL_POINTER);  // not actually necessary, right?
+       // it's not necessary to set e's next to null; this is the default.
 
        ASSERT_FALSE(singly_linked_list::has_cycle(a), "list should be found to have zero cycles")
   }