lemon-1.2: comparison lemon/binom

equal deleted inserted replaced

-:4a920e9e25a5
+:847a7cba7470
 PRE_HEAP = -1,  ///< = -1.
 POST_HEAP = -2  ///< = -2.
 };
 private:
-class store;
+class Store;
-std::vector<store> _data;
+std::vector<Store> _data;
 int _min, _head;
 ItemIntMap &_iim;
 Compare _comp;
 int _num_items;
 void push (const Item& item, const Prio& value) {
 int i=_iim[item];
 if ( i<0 ) {
 int s=_data.size();
 _iim.set( item,s );
-store st;
+Store st;
 st.name=item;
+st.prio=value;
 _data.push_back(st);
 i=s;
 }
 else {
 _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
 _data[i].degree=0;
 _data[i].in=true;
-}
+_data[i].prio=value;
-_data[i].prio=value;
+}
-if( 0==_num_items ) { _head=i; _min=i; }
+if( 0==_num_items ) {
-else { merge(i); }
+_head=i;
+_min=i;
-_min = findMin();
+} else {
+merge(i);
+if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
+}
 ++_num_items;
 }
 /// \brief Return the item having minimum priority.
 ///
 int head_child=-1;
 if ( _data[_min].child!=-1 ) {
 int child=_data[_min].child;
 int neighb;
-int prev=-1;
 while( child!=-1 ) {
 neighb=_data[child].right_neighbor;
 _data[child].parent=-1;
-_data[child].right_neighbor=prev;
+_data[child].right_neighbor=head_child;
 head_child=child;
-prev=child;
 child=neighb;
 }
 }
-// The first case is that there are only one root.
+if ( _data[_head].right_neighbor==-1 ) {
-if ( -1==_data[_head].right_neighbor ) {
+// there was only one root
 _head=head_child;
 }
-// The case where there are more roots.
 else {
+// there were more roots
 if( _head!=_min )  { unlace(_min); }
 else { _head=_data[_head].right_neighbor; }
 merge(head_child);
 }
 _min=findMin();
 --_num_items;
 }
 /// \param item The item.
 /// \param value The priority.
 /// \pre \e item must be stored in the heap with priority at least \e value.
 void decrease (Item item, const Prio& value) {
 int i=_iim[item];
+int p=_data[i].parent;
-if( _comp( value,_data[i].prio ) ) {
+_data[i].prio=value;
-_data[i].prio=value;
+while( p!=-1 && _comp(value, _data[p].prio) ) {
-int p_loc=_data[i].parent, loc=i;
+_data[i].name=_data[p].name;
-int parent, child, neighb;
+_data[i].prio=_data[p].prio;
+_data[p].name=item;
-while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) {
+_data[p].prio=value;
+_iim[_data[i].name]=i;
-// parent set for other loc_child
+i=p;
-child=_data[loc].child;
+p=_data[p].parent;
-while( -1!=child ) {
+}
-_data[child].parent=p_loc;
+_iim[item]=i;
-child=_data[child].right_neighbor;
+if ( _comp(value, _data[_min].prio) ) _min=i;
-}
-// parent set for other p_loc_child
-child=_data[p_loc].child;
-while( -1!=child ) {
-_data[child].parent=loc;
-child=_data[child].right_neighbor;
-}
-child=_data[p_loc].child;
-_data[p_loc].child=_data[loc].child;
-if( child==loc )
-child=p_loc;
-_data[loc].child=child;
-// left_neighb set for p_loc
-if( _data[loc].child!=p_loc ) {
-while( _data[child].right_neighbor!=loc )
-child=_data[child].right_neighbor;
-_data[child].right_neighbor=p_loc;
-}
-// left_neighb set for loc
-parent=_data[p_loc].parent;
-if( -1!=parent ) child=_data[parent].child;
-else child=_head;
-if( child!=p_loc ) {
-while( _data[child].right_neighbor!=p_loc )
-child=_data[child].right_neighbor;
-_data[child].right_neighbor=loc;
-}
-neighb=_data[p_loc].right_neighbor;
-_data[p_loc].right_neighbor=_data[loc].right_neighbor;
-_data[loc].right_neighbor=neighb;
-_data[p_loc].parent=loc;
-_data[loc].parent=parent;
-if( -1!=parent && _data[parent].child==p_loc )
-_data[parent].child=loc;
-/*if new parent will be the first root*/
-if( _head==p_loc )
-_head=loc;
-p_loc=_data[loc].parent;
-}
-}
-if( _comp(value,_data[_min].prio) ) {
-_min=i;
-}
 }
 /// \brief Increase the priority of an item to the given value.
 ///
 /// This function increases the priority of an item to the given value.
 break;
 }
 }
 private:
+// Find the minimum of the roots
 int findMin() {
-int min_loc=-1, min_val;
+if( _head!=-1 ) {
-int x=_head;
+int min_loc=_head, min_val=_data[_head].prio;
-if( x!=-1 ) {
+for( int x=_data[_head].right_neighbor; x!=-1;
-min_val=_data[x].prio;
+x=_data[x].right_neighbor ) {
-min_loc=x;
-x=_data[x].right_neighbor;
-while( x!=-1 ) {
 if( _comp( _data[x].prio,min_val ) ) {
 min_val=_data[x].prio;
 min_loc=x;
 }
-x=_data[x].right_neighbor;
+}
-}
+return min_loc;
 }
-return min_loc;
+else return -1;
 }
+// Merge the heap with another heap starting at the given position
 void merge(int a) {
-interleave(a);
+if( _head==-1 || a==-1 ) return;
+if( _data[a].right_neighbor==-1 &&
+_data[a].degree<=_data[_head].degree ) {
+_data[a].right_neighbor=_head;
+_head=a;
+} else {
+interleave(a);
+}
+if( _data[_head].right_neighbor==-1 ) return;
 int x=_head;
-if( -1!=x ) {
+int x_prev=-1, x_next=_data[x].right_neighbor;
-int x_prev=-1, x_next=_data[x].right_neighbor;
+while( x_next!=-1 ) {
-while( -1!=x_next ) {
+if( _data[x].degree!=_data[x_next].degree ||
-if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
+( _data[x_next].right_neighbor!=-1 &&
-x_prev=x;
+_data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
+x_prev=x;
+x=x_next;
+}
+else {
+if( _comp(_data[x_next].prio,_data[x].prio) ) {
+if( x_prev==-1 ) {
+_head=x_next;
+} else {
+_data[x_prev].right_neighbor=x_next;
+}
+fuse(x,x_next);
 x=x_next;
 }
 else {
-if( _comp(_data[x].prio,_data[x_next].prio) ) {
+_data[x].right_neighbor=_data[x_next].right_neighbor;
-_data[x].right_neighbor=_data[x_next].right_neighbor;
+fuse(x_next,x);
-fuse(x_next,x);
-}
-else {
-if( -1==x_prev ) { _head=x_next; }
-else {
-_data[x_prev].right_neighbor=x_next;
-}
-fuse(x,x_next);
-x=x_next;
-}
 }
-x_next=_data[x].right_neighbor;
+}
-}
+x_next=_data[x].right_neighbor;
 }
 }
+// Interleave the elements of the given list into the list of the roots
 void interleave(int a) {
-int other=-1, head_other=-1;
+int p=_head, q=a;
+int curr=_data.size();
-while( -1!=a || -1!=_head ) {
+_data.push_back(Store());
-if( -1==a ) {
-if( -1==head_other ) {
+while( p!=-1 || q!=-1 ) {
-head_other=_head;
+if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
-}
+_data[curr].right_neighbor=p;
-else {
+curr=p;
-_data[other].right_neighbor=_head;
+p=_data[p].right_neighbor;
-}
-_head=-1;
-}
-else if( -1==_head ) {
-if( -1==head_other ) {
-head_other=a;
-}
-else {
-_data[other].right_neighbor=a;
-}
-a=-1;
 }
 else {
-if( _data[a].degree<_data[_head].degree ) {
+_data[curr].right_neighbor=q;
-if( -1==head_other ) {
+curr=q;
-head_other=a;
+q=_data[q].right_neighbor;
 }
-else {
+}
-_data[other].right_neighbor=a;
-}
+_head=_data.back().right_neighbor;
-other=a;
+_data.pop_back();
-a=_data[a].right_neighbor;
+}
-}
-else {
+// Lace node a under node b
-if( -1==head_other ) {
-head_other=_head;
-}
-else {
-_data[other].right_neighbor=_head;
-}
-other=_head;
-_head=_data[_head].right_neighbor;
-}
-}
-}
-_head=head_other;
-}
-// Lacing a under b
 void fuse(int a, int b) {
 _data[a].parent=b;
 _data[a].right_neighbor=_data[b].child;
 _data[b].child=a;
 ++_data[b].degree;
 }
-// It is invoked only if a has siblings.
+// Unlace node a (if it has siblings)
 void unlace(int a) {
 int neighb=_data[a].right_neighbor;
 int other=_head;
 while( _data[other].right_neighbor!=a )
 _data[other].right_neighbor=neighb;
 }
 private:
-class store {
+class Store {
 friend class BinomHeap;
 Item name;
 int parent;
 int right_neighbor;
 int child;
 int degree;
 bool in;
 Prio prio;
-store() : parent(-1), right_neighbor(-1), child(-1), degree(0), in(true) {}
+Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
+in(true) {}
 };
 };
 } //namespace lemon

changeset 733	abf31e4af617
parent 703	bb3392fe91f2