Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) 00002 // 00003 // This file is part of Olena. 00004 // 00005 // Olena is free software: you can redistribute it and/or modify it under 00006 // the terms of the GNU General Public License as published by the Free 00007 // Software Foundation, version 2 of the License. 00008 // 00009 // Olena is distributed in the hope that it will be useful, 00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 // General Public License for more details. 00013 // 00014 // You should have received a copy of the GNU General Public License 00015 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00016 // 00017 // As a special exception, you may use this file as part of a free 00018 // software project without restriction. Specifically, if other files 00019 // instantiate templates or use macros or inline functions from this 00020 // file, or you compile this file and link it with other files to produce 00021 // an executable, this file does not by itself cause the resulting 00022 // executable to be covered by the GNU General Public License. This 00023 // exception does not however invalidate any other reasons why the 00024 // executable file might be covered by the GNU General Public License. 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 // mln_assertion(heap.front() == res_1[0]); 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 }