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 #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
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
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
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
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
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
00706 deep_clear_list(h->queue());
00707 delete h;
00708 }
00709 else
00710 {
00711 h->set_queue(sift(h->queue()));
00712
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
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
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
00857 h = prevhead->next();
00858
00859
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
00909
00910 v->set_il(0);
00911 v->set_il_tail(0);
00912
00913 if (v->next() == 0 && v->child() == 0)
00914 {
00915
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
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
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
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
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
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 }
01133
01134 }
01135
01136
01137 #endif // ! MLN_UTIL_SOFT_HEAP_HH