1 #include <oasys/util/UnitTest.h>

     2 #include <oasys/util/Random.h>

     3 #include <oasys/debug/Log.h>

     4 

     5 #include "prophet/Node.h"

     6 #include "prophet/Util.h"

     7 

     8 #define TEST_SIZE 10

     9 

    10 using namespace oasys;

    11 using namespace prophet;

    12 

    13 template<typename UnitType, typename Sequence, typename Comp>

    14 bool is_heap(const Sequence& list, Comp& comp)

    15 {

    16     typedef typename Sequence::size_type size_type;

    17     size_type len = list.size();

    18     size_type parent = 0;

    19     for (size_type child = 1; child < len; child++)

    20     {

    21         if ((comp)(list[parent],list[child]))

    22         {

    23             log_notice_p("/test","heap sequence failed, size=%u, parent[%u], "

    24                                  "child[%u]",list.size(),parent,child);

    25             return false;

    26         }

    27         if ((child & 1) == 0)

    28             parent++;

    29     }

    30     return true;

    31 }

    32 

    33 template<typename UnitType, typename Sequence, typename Comp>

    34 bool find(const Sequence& list, UnitType a, Comp& comp)

    35 {

    36     typedef typename Sequence::size_type size_type;

    37     size_type len = list.size();

    38     for (size_type pos = 0; pos < len; pos++) {

    39         if (!(comp)(a,list[pos]) && !(comp)(list[pos],a))

    40             return true;

    41     }

    42     return false;

    43 }

    44 

    45 struct less_node {

    46     less_node(int type=0) : mytype(type) {}

    47 

    48     bool operator() (Node* a, Node* b) {

    49         ASSERT(a != NULL && b != NULL);

    50         switch (mytype) {

    51         case 1:

    52             return ((*a).p_value() > (*b).p_value());

    53         case 0:

    54         default:

    55             return ((*a).p_value() < (*b).p_value());

    56         };

    57     }

    58     int mytype;

    59 };

    60 

    61 struct greater_node : public less_node {

    62     greater_node() : less_node(1) {}

    63 };

    64 

    65 struct heap_swap {

    66     inline void operator()(Node* a, size_t pos)

    67     {

    68         a->set_heap_pos(pos);

    69     }

    70 };

    71 

    72 DECLARE_TEST(IntHeap) {

    73     typedef std::vector<int> Seq;

    74     typedef std::less<int> Comp;

    75     typedef Heap<int,Seq,Comp> Heap;

    76     Comp mycomp;

    77     Heap myheap;

    78 

    79     for (int i = 0; i < TEST_SIZE; i++) {

    80         //int val = TEST_SIZE - (i + 1);

    81         int val = oasys::Random::rand(10000);

    82         myheap.add(val);

    83         Seq list = myheap.sequence();

    84         CHECK( (find<int,Seq,Comp>(myheap.sequence(),val,mycomp)) );

    85         CHECK( (Heap::is_heap(myheap.sequence(),mycomp)) );

    86     }

    87 

    88     CHECK(myheap.size() == TEST_SIZE);

    89 

    90     while (myheap.size() > 0) {

    91         log_notice_p("/test","List size = %u",myheap.size());

    92         int r = myheap.top();

    93         myheap.remove(0);

    94         if (!myheap.empty()) {

    95             log_notice_p("/test","r=%d,top=%d",r,myheap.top());

    96             CHECK(r >= myheap.top());

    97             CHECK( Heap::is_heap(myheap.sequence(),mycomp) );

    98         }

    99     }

   100 

   101     return UNIT_TEST_PASSED;

   102 }

   103 

   104 DECLARE_TEST(NodeHeap) {

   105     typedef std::vector<Node*> Seq;

   106     typedef struct less_node Comp;

   107     typedef Heap<Node*,Seq,Comp,struct heap_swap> Heap;

   108 

   109     struct less_node mycomp;

   110     Heap myheap;

   111 

   112     std::string id("a");

   113 

   114     for (int i = 0; i < TEST_SIZE; i++) {

   115         Node* n = new Node(id);

   116         // vary the compared metric

   117         for (int j=i; j < TEST_SIZE - 1; j++)

   118             n->update_pvalue();

   119         myheap.add(n);

   120         CHECK( (find<Node*,Seq,Comp>(myheap.sequence(),n,mycomp)) );

   121         CHECK( (Heap::is_heap(myheap.sequence(),mycomp)) );

   122         // rough equality test using current compare object

   123         size_t pos = n->heap_pos();

   124         CHECK( (!(mycomp)(myheap.sequence()[pos],n)) );

   125         CHECK( (!(mycomp)(n,myheap.sequence()[pos])) );

   126         id += ('a' + i + 1);

   127     }

   128     CHECK(myheap.size() == TEST_SIZE);

   129     do { 

   130         Seq::const_iterator si = myheap.sequence().begin();

   131         size_t pos = 0;

   132         while (si != myheap.sequence().end()) {

   133             CHECK_EQUAL(pos,(*si)->heap_pos());

   134             si++; pos++;

   135         }

   136     } while (0);

   137 

   138     // grab somebody from the middle and up the metric

   139     Node* n = myheap.sequence()[TEST_SIZE/2];

   140     for (int z=0;z<TEST_SIZE/2;z++) {

   141         n->update_pvalue();

   142     }

   143     // inform the heap of new metric at this pos

   144     size_t pos = n->heap_pos();

   145     myheap.remove(TEST_SIZE/2);

   146     myheap.add(n);

   147     log_notice_p("/test","Old pos=%u new pos=%u",TEST_SIZE/2,pos);

   148     CHECK( (Heap::is_heap(myheap.sequence(),mycomp)) );

   149     do { 

   150         Seq::const_iterator si = myheap.sequence().begin();

   151         size_t pos = 0;

   152         while (si != myheap.sequence().end()) {

   153             CHECK_EQUAL(pos,(*si)->heap_pos());

   154             si++; pos++;

   155         }

   156     } while (0);

   157 

   158     // verify that new compare object creates new heap order

   159     struct greater_node gcomp;

   160     DO(myheap.set_compare(new struct greater_node()));

   161     CHECK(myheap.size() == TEST_SIZE);

   162     CHECK( (Heap::is_heap(myheap.sequence(),gcomp)) );

   163     do { 

   164         Seq::const_iterator si = myheap.sequence().begin();

   165         size_t pos = 0;

   166         while (si != myheap.sequence().end()) {

   167             CHECK_EQUAL(pos,(*si)->heap_pos());

   168             si++; pos++;

   169         }

   170     } while (0);

   171 

   172     // go back to original compare object, verify heap order

   173     DO(myheap.set_compare(new struct less_node()));

   174     CHECK(myheap.size() == TEST_SIZE);

   175     CHECK( (Heap::is_heap(myheap.sequence(),mycomp)) );

   176     do { 

   177         Seq::const_iterator si = myheap.sequence().begin();

   178         size_t pos = 0;

   179         while (si != myheap.sequence().end()) {

   180             CHECK_EQUAL(pos,(*si)->heap_pos());

   181             si++; pos++;

   182         }

   183     } while (0);

   184 

   185     while (myheap.size() > 0) {

   186         Node* r = myheap.top();

   187         myheap.remove(0);

   188         if (!myheap.empty()) {

   189             log_notice_p("/test","r=%0.8f,top=%0.8f",

   190                          r->p_value(),myheap.top()->p_value());

   191             CHECK((!(mycomp)(r,myheap.top())));

   192             CHECK( (Heap::is_heap(myheap.sequence(),mycomp)) );

   193             do {

   194                 Seq::const_iterator si = myheap.sequence().begin();

   195                 size_t pos = 0;

   196                 while (si != myheap.sequence().end()) {

   197                     CHECK_EQUAL(pos,(*si)->heap_pos());

   198                     si++; pos++;

   199                 }

   200             } while (0);

   201         }

   202         delete r;

   203     }

   204 

   205     return UNIT_TEST_PASSED;

   206 }

   207 

   208 DECLARE_TESTER(ProphetHeap) {

   209     ADD_TEST(IntHeap);

   210     ADD_TEST(NodeHeap);

   211 }

   212 

   213 DECLARE_TEST_FILE(ProphetHeap, "prophet heap test");