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 #ifndef MLN_UTIL_SOFT_HEAP_HH 00027 # define MLN_UTIL_SOFT_HEAP_HH 00028 00032 00059 # include <mln/core/concept/object.hh> 00060 # include <mln/trait/value_.hh> 00061 # include <mln/util/tracked_ptr.hh> 00062 # include <climits> 00063 # include <stack> 00064 00065 00066 00067 namespace mln 00068 { 00069 00070 namespace util 00071 { 00072 00073 00075 template <typename T> 00076 struct ilcell 00077 { 00078 typedef util::tracked_ptr< ilcell<T> > ilcell_t; 00079 00080 ilcell(); 00081 ilcell(const T& key, ilcell_t next = 0); 00082 00083 ilcell_t next() const; 00084 const T& key() const; 00085 00086 void set_next(ilcell_t next); 00087 void set_key(const T& key); 00088 00089 private: 00090 T key_; 00091 ilcell_t next_; 00092 }; 00093 00094 00096 template <typename T, typename R> 00097 class node 00098 { 00099 00100 typedef util::tracked_ptr< ilcell<T> > ilcell_t; 00101 00102 public: 00103 node(); 00104 node(const T& ckey, const R& rank, 00105 node<T,R> *next = 0, node<T,R> *child = 0, 00106 ilcell_t il = 0, ilcell_t il_tail = 0); 00107 ~node(); 00108 00109 const T& ckey() const; 00110 const R& rank() const; 00111 node<T,R> * next() const; 00112 node<T,R> * child() const; 00113 ilcell_t il() const; 00114 ilcell_t il_tail() const; 00115 00116 void set_il(ilcell_t il); 00117 void set_il_tail(ilcell_t il_tail); 00118 void set_ckey(const T& ckey); 00119 void set_rank(const R& rank); 00120 void set_next(node<T,R> * next); 00121 void set_child(node<T,R> *child); 00122 00123 private: 00124 T ckey_; 00125 R rank_; 00126 node<T,R> *next_; 00127 node<T,R> *child_; 00128 ilcell_t il_; 00129 ilcell_t il_tail_; 00130 00131 }; 00132 00133 00134 00135 00137 template <typename T, typename R> 00138 class head 00139 { 00140 public: 00141 00142 head(); 00143 head(const R& rank, node<T,R> *queue = 0, head<T,R> *next = 0, 00144 head<T,R> *prev = 0, head<T,R> *suffix_min = 0); 00145 ~head(); 00146 00147 node<T,R> *queue() const; 00148 head<T,R> *next() const; 00149 head<T,R> *prev() const; 00150 head<T,R> *suffix_min() const; 00151 const R& rank() const; 00152 00153 void set_queue(node<T,R> *queue); 00154 void set_next(head<T,R> *next); 00155 void set_prev(head<T,R> *prev); 00156 void set_suffix_min(head<T,R> *suffix_min); 00157 void set_rank(const R& rank); 00158 00159 private: 00160 node<T,R> *queue_; 00161 head<T,R> *next_; 00162 head<T,R> *prev_; 00163 head<T,R> *suffix_min_; 00164 R rank_; 00165 00166 }; 00167 00168 00169 00170 00176 // 00177 template <typename T, typename R> 00178 class soft_heap : public Object< soft_heap<T,R> > 00179 { 00180 typedef util::tracked_ptr< ilcell<T> > ilcell_t; 00181 00182 public: 00183 00185 typedef T element; 00186 00187 00194 // FIXME: is it a correct value for r? 00195 soft_heap(unsigned r = 20); 00197 ~soft_heap(); 00198 00199 00201 void push(const T& element); 00202 00206 void push(soft_heap<T,R>& sh); 00207 00210 T pop_front(); 00211 00213 bool is_valid() const; 00214 00216 bool is_empty() const; 00217 00219 int nelements() const; 00220 00222 void clear(); 00223 00226 head<T,R> *head_hook_() const; 00227 00231 void soft_clear_(); 00232 00233 00234 00235 private: 00238 void meld(node<T,R> *q); 00239 00242 void fix_minlist(head<T,R> *h); 00243 00246 node<T,R> * sift(node<T,R> *v); 00247 00256 template <typename L> 00257 void clear_list(L *begin, L *end = 0); 00258 00269 template <typename L> 00270 void deep_clear_list(L *n); 00271 00273 void debug_head_list() const; 00274 00276 void println_() const; 00277 00278 head<T,R> *header_; 00279 head<T,R> *tail_; 00280 00282 unsigned r_; 00283 00284 int nelements_; 00285 }; 00286 00287 00288 00289 # ifndef MLN_INCLUDE_ONLY 00290 00291 00292 /*-------` 00293 | ilcell | 00294 \-------*/ 00295 00296 00297 template <typename T> 00298 inline 00299 ilcell<T>::ilcell() 00300 { 00301 } 00302 00303 00304 template <typename T> 00305 inline 00306 ilcell<T>::ilcell(const T& key, ilcell_t next) 00307 : key_(key), next_(next) 00308 { 00309 } 00310 00311 00312 template <typename T> 00313 inline 00314 typename ilcell<T>::ilcell_t 00315 ilcell<T>::next() const 00316 { 00317 return next_; 00318 } 00319 00320 00321 template <typename T> 00322 inline 00323 const T& 00324 ilcell<T>::key() const 00325 { 00326 return key_; 00327 } 00328 00329 00330 template <typename T> 00331 inline 00332 void 00333 ilcell<T>::set_next(ilcell_t next) 00334 { 00335 next_ = next; 00336 } 00337 00338 00339 template <typename T> 00340 inline 00341 void 00342 ilcell<T>::set_key(const T& key) 00343 { 00344 key_ = key; 00345 } 00346 00347 00348 00349 00350 /*-----` 00351 | node | 00352 \-----*/ 00353 00354 00355 template <typename T, typename R> 00356 inline 00357 node<T,R>::node() 00358 : il_(0), il_tail_(0) 00359 { 00360 } 00361 00362 00363 template <typename T, typename R> 00364 inline 00365 node<T,R>::node(const T& ckey, const R& rank, 00366 node<T,R> *next, node<T,R> *child, 00367 ilcell_t il, ilcell_t il_tail) 00368 : ckey_(ckey), rank_(rank), next_(next), child_(child), 00369 il_(il), il_tail_(il_tail) 00370 { 00371 } 00372 00373 00374 template <typename T, typename R> 00375 inline 00376 node<T,R>::~node() 00377 { 00378 } 00379 00380 00381 template <typename T, typename R> 00382 inline 00383 const T& 00384 node<T,R>::ckey() const 00385 { 00386 return ckey_; 00387 } 00388 00389 00390 template <typename T, typename R> 00391 inline 00392 const R& 00393 node<T,R>::rank() const 00394 { 00395 return rank_; 00396 } 00397 00398 00399 template <typename T, typename R> 00400 inline 00401 node<T,R> * 00402 node<T,R>::next() const 00403 { 00404 return next_; 00405 } 00406 00407 00408 template <typename T, typename R> 00409 inline 00410 node<T,R> * 00411 node<T,R>::child() const 00412 { 00413 return child_; 00414 } 00415 00416 00417 template <typename T, typename R> 00418 inline 00419 typename node<T,R>::ilcell_t 00420 node<T,R>::il() const 00421 { 00422 return il_; 00423 } 00424 00425 00426 template <typename T, typename R> 00427 inline 00428 typename node<T,R>::ilcell_t 00429 node<T,R>::il_tail() const 00430 { 00431 return il_tail_; 00432 } 00433 00434 00435 template <typename T, typename R> 00436 inline 00437 void 00438 node<T,R>::set_il(ilcell_t il) 00439 { 00440 il_ = il; 00441 } 00442 00443 00444 template <typename T, typename R> 00445 inline 00446 void 00447 node<T,R>::set_il_tail(ilcell_t il_tail) 00448 { 00449 il_tail_ = il_tail; 00450 } 00451 00452 00453 template <typename T, typename R> 00454 inline 00455 void 00456 node<T,R>::set_ckey(const T& ckey) 00457 { 00458 ckey_ = ckey; 00459 } 00460 00461 00462 template <typename T, typename R> 00463 inline 00464 void 00465 node<T,R>::set_rank(const R& rank) 00466 { 00467 rank_ = rank; 00468 } 00469 00470 00471 template <typename T, typename R> 00472 inline 00473 void 00474 node<T,R>::set_next(node<T,R> * next) 00475 { 00476 next_ = next; 00477 } 00478 00479 00480 template <typename T, typename R> 00481 inline 00482 void 00483 node<T,R>::set_child(node<T,R> *child) 00484 { 00485 child_ = child; 00486 } 00487 00488 00489 00490 00491 /*-----` 00492 | head | 00493 \-----*/ 00494 00495 00496 template <typename T, typename R> 00497 inline 00498 head<T,R>::head() 00499 { 00500 } 00501 00502 00503 template <typename T, typename R> 00504 inline 00505 head<T,R>::head(const R& rank, node<T,R> *queue, head<T,R> *next, 00506 head<T,R> *prev, head<T,R> *suffix_min) 00507 : queue_(queue), next_(next), prev_(prev), 00508 suffix_min_(suffix_min), rank_(rank) 00509 { 00510 } 00511 00512 00513 template <typename T, typename R> 00514 inline 00515 head<T,R>::~head() 00516 { 00517 } 00518 00519 00520 template <typename T, typename R> 00521 inline 00522 node<T,R> * 00523 head<T,R>::queue() const 00524 { 00525 return queue_; 00526 } 00527 00528 00529 template <typename T, typename R> 00530 inline 00531 head<T,R> * 00532 head<T,R>::next() const 00533 { 00534 return next_; 00535 } 00536 00537 00538 template <typename T, typename R> 00539 inline 00540 head<T,R> * 00541 head<T,R>::prev() const 00542 { 00543 return prev_; 00544 } 00545 00546 00547 template <typename T, typename R> 00548 inline 00549 head<T,R> * 00550 head<T,R>::suffix_min() const 00551 { 00552 return suffix_min_; 00553 } 00554 00555 00556 template <typename T, typename R> 00557 inline 00558 const R& 00559 head<T,R>::rank() const 00560 { 00561 return rank_; 00562 } 00563 00564 00565 template <typename T, typename R> 00566 inline 00567 void 00568 head<T,R>::set_queue(node<T,R> *queue) 00569 { 00570 queue_ = queue; 00571 } 00572 00573 00574 template <typename T, typename R> 00575 inline 00576 void 00577 head<T,R>::set_next(head<T,R> *next) 00578 { 00579 next_ = next; 00580 } 00581 00582 00583 template <typename T, typename R> 00584 inline 00585 void 00586 head<T,R>::set_prev(head<T,R> *prev) 00587 { 00588 prev_ = prev; 00589 } 00590 00591 00592 template <typename T, typename R> 00593 inline 00594 void 00595 head<T,R>::set_suffix_min(head<T,R> *suffix_min) 00596 { 00597 suffix_min_ = suffix_min; 00598 } 00599 00600 00601 template <typename T, typename R> 00602 inline 00603 void 00604 head<T,R>::set_rank(const R& rank) 00605 { 00606 rank_ = rank; 00607 } 00608 00609 00610 00611 00612 /*------------` 00613 | soft_heap | 00614 \------------*/ 00615 00616 00617 template <typename T, typename R> 00618 inline 00619 soft_heap<T,R>::soft_heap(unsigned r) 00620 { 00621 nelements_ = 0; 00622 r_ = r; 00623 header_ = new head<T,R>(mln_max(R)); 00624 tail_ = new head<T,R>(mln_max(R), 0, 0, header_); 00625 header_->set_next(tail_); 00626 } 00627 00628 00629 template <typename T, typename R> 00630 inline 00631 soft_heap<T,R>::~soft_heap() 00632 { 00633 head<T,R> *tmp = header_; 00634 while (tmp != 0) 00635 { 00636 deep_clear_list(tmp->queue()); 00637 tmp = tmp->next(); 00638 } 00639 clear_list(header_, tail_->next()); 00640 } 00641 00642 00643 template <typename T, typename R> 00644 inline 00645 void 00646 soft_heap<T,R>::push(const T& element) 00647 { 00648 ilcell_t l(new ilcell<T>(element)); 00649 node<T,R> *q = new node<T,R>(element, 0, 0, 0, l, l); 00650 meld(q); 00651 ++nelements_; 00652 } 00653 00654 00655 template <typename T, typename R> 00656 inline 00657 void 00658 soft_heap<T,R>::push(soft_heap<T,R>& psh) 00659 { 00660 head<T,R> *head = psh.head_hook_(); 00661 while (head != 0) 00662 { 00663 if (head->queue() != 0) 00664 meld(head->queue()); 00665 head = head->next(); 00666 } 00667 nelements_ += psh.nelements(); 00668 psh.soft_clear_(); 00669 } 00670 00671 00672 template <typename T, typename R> 00673 inline 00674 T 00675 soft_heap<T,R>::pop_front() 00676 { 00677 mln_precondition(is_valid()); 00678 00679 node<T,R> *tmp; 00680 00681 T min; 00682 int childcount; 00683 head<T,R> *h = header_->next()->suffix_min(); 00684 while (h->queue()->il() == 0) 00685 { 00686 tmp = h->queue(); 00687 childcount = 0; 00688 while (tmp->next() != 0) 00689 { 00690 tmp = tmp->next(); 00691 ++childcount; 00692 } 00693 00694 if (childcount < h->rank() / 2) 00695 { 00696 h->prev()->set_next(h->next()); 00697 h->next()->set_prev(h->prev()); 00698 fix_minlist(h->prev()); 00699 tmp = h->queue(); 00700 while (tmp->next() != 0) 00701 { 00702 meld(tmp->child()); 00703 tmp = tmp->next(); 00704 } 00705 //FIXME: is it right? 00706 deep_clear_list(h->queue()); 00707 delete h; 00708 } 00709 else 00710 { 00711 h->set_queue(sift(h->queue())); 00712 // FIXME: not generic enough. 00713 if (h->queue()->ckey() == T::plus_infty()) 00714 { 00715 h->prev()->set_next(h->next()); 00716 h->next()->set_prev(h->prev()); 00717 00718 // Remove h and switch to h->prev. 00719 head<T,R> *h_bak = h; 00720 h = h->prev(); 00721 deep_clear_list(h_bak->queue()); 00722 delete h_bak; 00723 } 00724 fix_minlist(h); 00725 } 00726 h = header_->next()->suffix_min(); 00727 } 00728 00729 min = h->queue()->il()->key(); 00730 00731 //Don't need to delete h->queue()->il(). May be used in another node. 00732 h->queue()->set_il(h->queue()->il()->next()); 00733 if (h->queue()->il() == 0) 00734 h->queue()->set_il_tail(0); 00735 00736 --nelements_; 00737 return min; 00738 } 00739 00740 00741 template <typename T, typename R> 00742 inline 00743 bool 00744 soft_heap<T,R>::is_valid() const 00745 { 00746 return header_ != 0 && tail_ != 0; 00747 } 00748 00749 00750 template <typename T, typename R> 00751 inline 00752 bool 00753 soft_heap<T,R>::is_empty() const 00754 { 00755 return nelements_ == 0 ; 00756 } 00757 00758 00759 template <typename T, typename R> 00760 inline 00761 int 00762 soft_heap<T,R>::nelements() const 00763 { 00764 return nelements_; 00765 } 00766 00767 00768 template <typename T, typename R> 00769 inline 00770 void 00771 soft_heap<T,R>::clear() 00772 { 00773 if (header_->next() == tail_) 00774 return; 00775 00776 head<T,R> *tohead = header_->next(); 00777 head<T,R> *prevtail = tail_->prev(); 00778 prevtail->set_next(0); 00779 tohead->set_prev(0); 00780 header_->set_next(tail_); 00781 tail_->set_prev(header_); 00782 00783 head<T,R> *tmp = tohead; 00784 while (tmp != 0) 00785 { 00786 deep_clear_list(tmp->queue()); 00787 tmp = tmp->next(); 00788 } 00789 clear_list(tohead); 00790 00791 nelements_ = 0; 00792 } 00793 00794 00795 template <typename T, typename R> 00796 inline 00797 void 00798 soft_heap<T,R>::soft_clear_() 00799 { 00800 clear_list(header_->next(), tail_); 00801 header_->set_next(tail_); 00802 header_->set_prev(0); 00803 tail_->set_next(0); 00804 tail_->set_prev(header_); 00805 nelements_ = 0; 00806 } 00807 00808 00809 template <typename T, typename R> 00810 inline 00811 head<T,R> * 00812 soft_heap<T,R>::head_hook_() const 00813 { 00814 return header_; 00815 } 00816 00817 00818 template <typename T, typename R> 00819 inline 00820 void 00821 soft_heap<T,R>::meld(node<T,R>* q) 00822 { 00823 head<T,R> *tohead = header_->next(); 00824 while (q->rank() > tohead->rank()) 00825 tohead = tohead->next(); 00826 head<T,R> *prevhead = tohead->prev(); 00827 00828 node<T,R> *top, *bottom; 00829 00830 while (q->rank() == tohead->rank()) 00831 { 00832 if (util::ord_strict(q->ckey(), tohead->queue()->ckey())) 00833 { 00834 top = q; 00835 bottom = tohead->queue(); 00836 } 00837 else 00838 { 00839 top = tohead->queue(); 00840 bottom = q; 00841 } 00842 00843 q = new node<T,R>(top->ckey(), top->rank() + 1, top, bottom, 00844 top->il(), top->il_tail()); 00845 00846 tohead = tohead->next(); 00847 } 00848 00849 head<T,R> *h; 00850 if (prevhead == tohead->prev()) 00851 { 00852 h = new head<T,R>(q->rank(), q, tohead, prevhead); 00853 } 00854 else 00855 { 00856 // Do not create a new head. 00857 h = prevhead->next(); 00858 00859 //Discard/delete everything between h and tohead. 00860 head<T,R> *head_del = h->next(), *tmp_del; 00861 while (head_del != tohead) 00862 { 00863 tmp_del = head_del->next(); 00864 delete head_del; 00865 head_del = tmp_del; 00866 } 00867 00868 } 00869 h->set_queue(q); 00870 h->set_rank(q->rank()); 00871 h->set_prev(prevhead); 00872 h->set_next(tohead); 00873 00874 prevhead->set_next(h); 00875 tohead->set_prev(h); 00876 00877 fix_minlist(h); 00878 } 00879 00880 00881 template <typename T, typename R> 00882 inline 00883 void 00884 soft_heap<T,R>::fix_minlist(head<T,R> *h) 00885 { 00886 head<T,R> *tmpmin; 00887 if (h->next() == tail_) 00888 tmpmin = h; 00889 else 00890 tmpmin = h->next()->suffix_min(); 00891 00892 while (h != header_) 00893 { 00894 if (util::ord_strict(h->queue()->ckey(), tmpmin->queue()->ckey())) 00895 tmpmin = h; 00896 h->set_suffix_min(tmpmin); 00897 h = h->prev(); 00898 } 00899 } 00900 00901 00902 template <typename T, typename R> 00903 inline 00904 node<T,R> * 00905 soft_heap<T,R>::sift(node<T,R> *v) 00906 { 00907 node<T,R> *tmp; 00908 // We do not need to free the list since these object are also pointed by 00909 // other structs. 00910 v->set_il(0); 00911 v->set_il_tail(0); 00912 00913 if (v->next() == 0 && v->child() == 0) 00914 { 00915 //FIXME: not generic enough... 00916 v->set_ckey(T::plus_infty()); 00917 return v; 00918 } 00919 node<T,R> *v_next_bak = v->next(); 00920 v->set_next(sift(v->next())); 00921 00922 // Cleanup possibly removed nodes. 00923 while (v_next_bak != v->next()) 00924 { 00925 deep_clear_list(v_next_bak->next()); 00926 deep_clear_list(v_next_bak->child()); 00927 tmp = v_next_bak->next(); 00928 delete v_next_bak; 00929 v_next_bak = tmp; 00930 } 00931 00932 if (util::ord_strict(v->child()->ckey(), v->next()->ckey())) 00933 { 00934 // Swap child and next. 00935 tmp = v->child(); 00936 v->set_child(v->next()); 00937 v->set_next(tmp); 00938 } 00939 00940 v->set_il(v->next()->il()); 00941 v->set_il_tail(v->next()->il_tail()); 00942 v->set_ckey(v->next()->ckey()); 00943 00944 if (v->rank() > r_ && (v->rank() % 2 == 1 00945 || v->child()->rank() < static_cast<unsigned>((v->rank() - 1)))) 00946 { 00947 node<T,R> *v_next_bak = v->next(); 00948 v->set_next(sift(v->next())); 00949 00950 // Cleanup possibly removed nodes. 00951 while (v_next_bak != v->next()) 00952 { 00953 deep_clear_list(v_next_bak->next()); 00954 deep_clear_list(v_next_bak->child()); 00955 tmp = v_next_bak->next(); 00956 delete v_next_bak; 00957 v_next_bak = tmp; 00958 } 00959 00960 if (util::ord_strict(v->child()->ckey(), v->next()->ckey())) 00961 { 00962 tmp = v->child(); 00963 v->set_child(v->next()); 00964 v->set_next(tmp); 00965 } 00966 00967 if (v->next()->ckey() != T::plus_infty() && v->next()->il() != 0) 00968 { 00969 v->next()->il_tail()->set_next(v->il()); 00970 v->set_il(v->next()->il()); 00971 if (v->il_tail() == 0) 00972 v->set_il_tail(v->next()->il_tail()); 00973 v->set_ckey(v->next()->ckey()); 00974 } 00975 } 00976 00977 if (v->child()->ckey() == T::plus_infty()) 00978 { 00979 if (v->next()->ckey() == T::plus_infty()) 00980 { 00981 // Clear child and next lists. 00982 deep_clear_list(v->child()); 00983 deep_clear_list(v->next()); 00984 00985 v->set_child(0); 00986 v->set_next(0); 00987 } 00988 else 00989 { 00990 node<T,R> *next_bak = v->next(); 00991 00992 // There may be several children, we must clear all of them. 00993 deep_clear_list(v->child()); 00994 00995 v->set_child(v->next()->child()); 00996 v->set_next(v->next()->next()); 00997 delete next_bak; 00998 } 00999 } 01000 01001 return v; 01002 } 01003 01004 01005 template <typename T, typename R> 01006 template <typename L> 01007 inline 01008 void 01009 soft_heap<T,R>::clear_list(L *begin, L *end) 01010 { 01011 L *tmp; 01012 while (begin != end) 01013 { 01014 tmp = begin->next(); 01015 delete begin; 01016 begin = tmp; 01017 } 01018 } 01019 01020 01021 template <typename T, typename R> 01022 template <typename L> 01023 inline 01024 void 01025 soft_heap<T,R>::deep_clear_list(L *n) 01026 { 01027 L *current_node, *tmp; 01028 std::stack<L *> st; 01029 01030 st.push(n); 01031 while (!st.empty()) 01032 { 01033 current_node = st.top(); 01034 st.pop(); 01035 while (current_node != 0) 01036 { 01037 if (current_node->child() != 0) 01038 st.push(current_node->child()); 01039 01040 tmp = current_node->next(); 01041 delete current_node; 01042 01043 current_node = tmp; 01044 } 01045 } 01046 } 01047 01048 01049 template <typename T, typename R> 01050 inline 01051 void 01052 soft_heap<T,R>::debug_head_list() const 01053 { 01054 head<T,R> *n = header_; 01055 std::cout << "Head list = " << std::endl; 01056 while (n != 0) 01057 { 01058 std::cout << n->id << "("; 01059 01060 node<T,R> *current_node; 01061 std::stack< node<T,R> *> st; 01062 st.push(n->queue()); 01063 while (!st.empty()) 01064 { 01065 current_node = st.top(); 01066 st.pop(); 01067 while (current_node != 0) 01068 { 01069 if (current_node->child() != 0) 01070 st.push(current_node->child()); 01071 std::cout << current_node->id << ","; 01072 current_node = current_node->next(); 01073 } 01074 } 01075 01076 std::cout << ") - "; 01077 n = n->next(); 01078 } 01079 std::cout << std::endl; 01080 } 01081 01082 01083 template <typename T, typename R> 01084 inline 01085 void 01086 soft_heap<T,R>::println_() const 01087 { 01088 01089 std::cout << "===============" << std::endl; 01090 head<T,R> *head = header_; 01091 while (head != 0) 01092 { 01093 std::cout << "<Head>" << std::endl; 01094 node<T,R> *node = head->queue(), *child; 01095 while (node != 0) 01096 { 01097 std::cout << " <node>" << std::endl; 01098 01099 ilcell_t il(node->il()); 01100 while (il != 0) 01101 { 01102 std::cout << il->item() << std::endl; 01103 il = il->next(); 01104 } 01105 01106 child = node->child(); 01107 while (child != 0) 01108 { 01109 std::cout << " <child>" << std::endl; 01110 ilcell_t il(child->il()); 01111 while (il != 0) 01112 { 01113 std::cout << il->item() << std::endl; 01114 il = il->next(); 01115 } 01116 child = child->child(); 01117 std::cout << " </child>" << std::endl; 01118 } 01119 node = node->next(); 01120 01121 std::cout << " </node>" << std::endl; 01122 } 01123 std::cout << "</Head>" << std::endl; 01124 head = head->next(); 01125 } 01126 } 01127 01128 01129 # endif // ! MLN_INCLUDE_ONLY 01130 01131 01132 } // end of namespace mln::util 01133 01134 } // end of namespace mln 01135 01136 01137 #endif // ! MLN_UTIL_SOFT_HEAP_HH