|
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"); |