00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00030
00031 #include <mln/util/fibonacci_heap.hh>
00032 #include <mln/core/alias/point2d.hh>
00033
00034
00035 using mln::point2d;
00036
00037 point2d p[] = { point2d(4,5), point2d(3,4), point2d(3,2),
00038 point2d(1,6), point2d(2,3), point2d(3,5),
00039 point2d(2,4), point2d(7,2), point2d(9,6),
00040 point2d(7,3) };
00041
00042 point2d res_1[] = { point2d(1,6), point2d(2,3), point2d(2,4) };
00043
00044 point2d res_2[] = { point2d(53,4), point2d(5,4), point2d(1,4),
00045 point2d(3,2), point2d(3,4), point2d(3,5),
00046 point2d(4,5), point2d(7,2), point2d(7,3),
00047 point2d(9,6) };
00048
00049
00050 int main()
00051 {
00052 using namespace mln;
00053
00055 util::fibonacci_heap<int,point2d> heap;
00056 for (unsigned i = 0; i < 5; ++i)
00057 heap.push(3, p[i]);
00058
00060 util::fibonacci_heap<int,point2d> heap2;
00061 for (unsigned i = 5; i < 10; ++i)
00062 heap2.push(3, p[i]);
00063
00064
00075
00076 heap.push(heap2);
00077
00079 mln_assertion(heap2.is_empty());
00080 mln_assertion(heap2.nelements() == 0);
00081
00083
00084
00085
00096
00097
00098 heap2.push(heap);
00099
00101 mln_assertion(heap.is_empty());
00102 mln_assertion(heap.nelements() == 0);
00103
00105 mln_assertion(heap2.front() == res_1[0]);
00106
00107
00109 for (unsigned i = 0; i < 3; ++i)
00110 mln_assertion(heap2.pop_front() == res_1[i]);
00111
00112
00114 heap2.push(1, point2d(53,4));
00115 heap2.push(3, point2d(1,4));
00116 heap2.push(2, point2d(5,4));
00117
00119 unsigned i = 0;
00120 while (heap2.is_valid())
00121 {
00122 mln_assertion(heap2.pop_front() == res_2[i++]);
00123 mln_assertion(heap2.nelements() == (10 - i));
00124 }
00125
00127 mln_assertion(heap2.is_empty());
00128 mln_assertion(heap2.nelements() == 0);
00129
00130
00131
00133 heap.push(3, point2d(2,4));
00134 heap2.push(3, point2d(53,4));
00135 util::fibonacci_heap<int,point2d> tmp = heap;
00136 heap = heap2;
00137 heap2 = tmp;
00138
00139 mln_assertion(heap2.nelements() == 1);
00140 mln_assertion(heap.nelements() == 1);
00141 mln_assertion(tmp.nelements() == 0);
00142
00143
00145 util::fibonacci_heap<int,point2d> tmp2(heap);
00146
00147 mln_assertion(tmp2.nelements() == 1);
00148 mln_assertion(heap.nelements() == 0);
00149
00150 }