diff -r 000000000000 -r 2b3e5ec03512 test/unit_tests/prophet-heap-test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/unit_tests/prophet-heap-test.cc	Thu Apr 21 14:57:45 2011 +0100
@@ -0,0 +1,213 @@
+#include <oasys/util/UnitTest.h>
+#include <oasys/util/Random.h>
+#include <oasys/debug/Log.h>
+
+#include "prophet/Node.h"
+#include "prophet/Util.h"
+
+#define TEST_SIZE 10
+
+using namespace oasys;
+using namespace prophet;
+
+template<typename UnitType, typename Sequence, typename Comp>
+bool is_heap(const Sequence& list, Comp& comp)
+{
+    typedef typename Sequence::size_type size_type;
+    size_type len = list.size();
+    size_type parent = 0;
+    for (size_type child = 1; child < len; child++)
+    {
+        if ((comp)(list[parent],list[child]))
+        {
+            log_notice_p("/test","heap sequence failed, size=%u, parent[%u], "
+                                 "child[%u]",list.size(),parent,child);
+            return false;
+        }
+        if ((child & 1) == 0)
+            parent++;
+    }
+    return true;
+}
+
+template<typename UnitType, typename Sequence, typename Comp>
+bool find(const Sequence& list, UnitType a, Comp& comp)
+{
+    typedef typename Sequence::size_type size_type;
+    size_type len = list.size();
+    for (size_type pos = 0; pos < len; pos++) {
+        if (!(comp)(a,list[pos]) && !(comp)(list[pos],a))
+            return true;
+    }
+    return false;
+}
+
+struct less_node {
+    less_node(int type=0) : mytype(type) {}
+
+    bool operator() (Node* a, Node* b) {
+        ASSERT(a != NULL && b != NULL);
+        switch (mytype) {
+        case 1:
+            return ((*a).p_value() > (*b).p_value());
+        case 0:
+        default:
+            return ((*a).p_value() < (*b).p_value());
+        };
+    }
+    int mytype;
+};
+
+struct greater_node : public less_node {
+    greater_node() : less_node(1) {}
+};
+
+struct heap_swap {
+    inline void operator()(Node* a, size_t pos)
+    {
+        a->set_heap_pos(pos);
+    }
+};
+
+DECLARE_TEST(IntHeap) {
+    typedef std::vector<int> Seq;
+    typedef std::less<int> Comp;
+    typedef Heap<int,Seq,Comp> Heap;
+    Comp mycomp;
+    Heap myheap;
+
+    for (int i = 0; i < TEST_SIZE; i++) {
+        //int val = TEST_SIZE - (i + 1);
+        int val = oasys::Random::rand(10000);
+        myheap.add(val);
+        Seq list = myheap.sequence();
+        CHECK( (find<int,Seq,Comp>(myheap.sequence(),val,mycomp)) );
+        CHECK( (Heap::is_heap(myheap.sequence(),mycomp)) );
+    }
+
+    CHECK(myheap.size() == TEST_SIZE);
+
+    while (myheap.size() > 0) {
+        log_notice_p("/test","List size = %u",myheap.size());
+        int r = myheap.top();
+        myheap.remove(0);
+        if (!myheap.empty()) {
+            log_notice_p("/test","r=%d,top=%d",r,myheap.top());
+            CHECK(r >= myheap.top());
+            CHECK( Heap::is_heap(myheap.sequence(),mycomp) );
+        }
+    }
+
+    return UNIT_TEST_PASSED;
+}
+
+DECLARE_TEST(NodeHeap) {
+    typedef std::vector<Node*> Seq;
+    typedef struct less_node Comp;
+    typedef Heap<Node*,Seq,Comp,struct heap_swap> Heap;
+
+    struct less_node mycomp;
+    Heap myheap;
+
+    std::string id("a");
+
+    for (int i = 0; i < TEST_SIZE; i++) {
+        Node* n = new Node(id);
+        // vary the compared metric
+        for (int j=i; j < TEST_SIZE - 1; j++)
+            n->update_pvalue();
+        myheap.add(n);
+        CHECK( (find<Node*,Seq,Comp>(myheap.sequence(),n,mycomp)) );
+        CHECK( (Heap::is_heap(myheap.sequence(),mycomp)) );
+        // rough equality test using current compare object
+        size_t pos = n->heap_pos();
+        CHECK( (!(mycomp)(myheap.sequence()[pos],n)) );
+        CHECK( (!(mycomp)(n,myheap.sequence()[pos])) );
+        id += ('a' + i + 1);
+    }
+    CHECK(myheap.size() == TEST_SIZE);
+    do { 
+        Seq::const_iterator si = myheap.sequence().begin();
+        size_t pos = 0;
+        while (si != myheap.sequence().end()) {
+            CHECK_EQUAL(pos,(*si)->heap_pos());
+            si++; pos++;
+        }
+    } while (0);
+
+    // grab somebody from the middle and up the metric
+    Node* n = myheap.sequence()[TEST_SIZE/2];
+    for (int z=0;z<TEST_SIZE/2;z++) {
+        n->update_pvalue();
+    }
+    // inform the heap of new metric at this pos
+    size_t pos = n->heap_pos();
+    myheap.remove(TEST_SIZE/2);
+    myheap.add(n);
+    log_notice_p("/test","Old pos=%u new pos=%u",TEST_SIZE/2,pos);
+    CHECK( (Heap::is_heap(myheap.sequence(),mycomp)) );
+    do { 
+        Seq::const_iterator si = myheap.sequence().begin();
+        size_t pos = 0;
+        while (si != myheap.sequence().end()) {
+            CHECK_EQUAL(pos,(*si)->heap_pos());
+            si++; pos++;
+        }
+    } while (0);
+
+    // verify that new compare object creates new heap order
+    struct greater_node gcomp;
+    DO(myheap.set_compare(new struct greater_node()));
+    CHECK(myheap.size() == TEST_SIZE);
+    CHECK( (Heap::is_heap(myheap.sequence(),gcomp)) );
+    do { 
+        Seq::const_iterator si = myheap.sequence().begin();
+        size_t pos = 0;
+        while (si != myheap.sequence().end()) {
+            CHECK_EQUAL(pos,(*si)->heap_pos());
+            si++; pos++;
+        }
+    } while (0);
+
+    // go back to original compare object, verify heap order
+    DO(myheap.set_compare(new struct less_node()));
+    CHECK(myheap.size() == TEST_SIZE);
+    CHECK( (Heap::is_heap(myheap.sequence(),mycomp)) );
+    do { 
+        Seq::const_iterator si = myheap.sequence().begin();
+        size_t pos = 0;
+        while (si != myheap.sequence().end()) {
+            CHECK_EQUAL(pos,(*si)->heap_pos());
+            si++; pos++;
+        }
+    } while (0);
+
+    while (myheap.size() > 0) {
+        Node* r = myheap.top();
+        myheap.remove(0);
+        if (!myheap.empty()) {
+            log_notice_p("/test","r=%0.8f,top=%0.8f",
+                         r->p_value(),myheap.top()->p_value());
+            CHECK((!(mycomp)(r,myheap.top())));
+            CHECK( (Heap::is_heap(myheap.sequence(),mycomp)) );
+            do {
+                Seq::const_iterator si = myheap.sequence().begin();
+                size_t pos = 0;
+                while (si != myheap.sequence().end()) {
+                    CHECK_EQUAL(pos,(*si)->heap_pos());
+                    si++; pos++;
+                }
+            } while (0);
+        }
+        delete r;
+    }
+
+    return UNIT_TEST_PASSED;
+}
+
+DECLARE_TESTER(ProphetHeap) {
+    ADD_TEST(IntHeap);
+    ADD_TEST(NodeHeap);
+}
+
+DECLARE_TEST_FILE(ProphetHeap, "prophet heap test");