alpar@222: // -*- C++ -*- alpar@222: /* alpar@222: *template > alpar@222: * alpar@222: *constructors: alpar@222: * alpar@222: *FibHeap(ItemIntMap), FibHeap(ItemIntMap, Compare) alpar@222: * alpar@222: *Member functions: alpar@222: * alpar@222: *int size() : returns the number of elements in the heap alpar@222: * alpar@222: *bool empty() : true iff size()=0 alpar@222: * alpar@222: *void set(Item, Prio) : calls push(Item, Prio) if Item is not alpar@222: * in the heap, and calls decrease/increase(Item, Prio) otherwise alpar@222: * alpar@222: *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item alpar@222: * mustn't be in the heap. alpar@222: * alpar@222: *Item top() : returns the Item with least Prio. alpar@222: * Must be called only if heap is nonempty. alpar@222: * alpar@222: *Prio prio() : returns the least Prio alpar@222: * Must be called only if heap is nonempty. alpar@222: * alpar@222: *Prio get(Item) : returns Prio of Item alpar@222: * Must be called only if Item is in heap. alpar@222: * alpar@222: *void pop() : deletes the Item with least Prio alpar@222: * alpar@222: *void erase(Item) : deletes Item from the heap if it was already there alpar@222: * alpar@222: *void decrease(Item, P) : decreases prio of Item to P. alpar@222: * Item must be in the heap with prio at least P. alpar@222: * alpar@222: *void increase(Item, P) : sets prio of Item to P. alpar@222: * alpar@222: *state_enum state(Item) : returns PRE_HEAP if Item has not been in the alpar@222: * heap until now, IN_HEAP if it is in the heap at the moment, and alpar@222: * POST_HEAP otherwise. In the latter case it is possible that Item alpar@222: * will get back to the heap again. alpar@222: * alpar@222: *In Fibonacci heaps, increase and erase are not efficient, in case of alpar@222: *many calls to these operations, it is better to use bin_heap. alpar@222: */ alpar@222: alpar@222: #ifndef FIB_HEAP_H alpar@222: #define FIB_HEAP_H alpar@222: alpar@222: #include alpar@222: #include alpar@222: #include alpar@222: alpar@222: namespace hugo { alpar@222: alpar@222: template > alpar@222: alpar@222: class FibHeap { alpar@222: alpar@222: typedef Prio PrioType; alpar@222: alpar@222: class store; alpar@222: alpar@222: std::vector container; alpar@222: int minimum; alpar@222: ItemIntMap &iimap; alpar@222: Compare comp; alpar@222: int num_items; alpar@222: alpar@222: ///\todo It is use nowhere alpar@222: ///\todo It doesn't conforms to the naming conventions. alpar@222: public: alpar@222: enum state_enum { alpar@222: IN_HEAP = 0, alpar@222: PRE_HEAP = -1, alpar@222: POST_HEAP = -2 alpar@222: }; alpar@222: alpar@222: public : alpar@222: alpar@222: FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {} alpar@222: FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(), alpar@222: iimap(_iimap), comp(_comp), num_items() {} alpar@222: alpar@222: alpar@222: int size() const { alpar@222: return num_items; alpar@222: } alpar@222: alpar@222: alpar@222: bool empty() const { return num_items==0; } alpar@222: alpar@222: alpar@222: void set (Item const it, PrioType const value) { alpar@222: int i=iimap[it]; alpar@222: if ( i >= 0 && container[i].in ) { alpar@222: if ( comp(value, container[i].prio) ) decrease(it, value); alpar@222: if ( comp(container[i].prio, value) ) increase(it, value); alpar@222: } else push(it, value); alpar@222: } alpar@222: alpar@222: alpar@222: void push (Item const it, PrioType const value) { alpar@222: int i=iimap[it]; alpar@222: if ( i < 0 ) { alpar@222: int s=container.size(); alpar@222: iimap.set( it, s ); alpar@222: store st; alpar@222: st.name=it; alpar@222: container.push_back(st); alpar@222: i=s; alpar@222: } else { alpar@222: container[i].parent=container[i].child=-1; alpar@222: container[i].degree=0; alpar@222: container[i].in=true; alpar@222: container[i].marked=false; alpar@222: } alpar@222: alpar@222: if ( num_items ) { alpar@222: container[container[minimum].right_neighbor].left_neighbor=i; alpar@222: container[i].right_neighbor=container[minimum].right_neighbor; alpar@222: container[minimum].right_neighbor=i; alpar@222: container[i].left_neighbor=minimum; alpar@222: if ( comp( value, container[minimum].prio) ) minimum=i; alpar@222: } else { alpar@222: container[i].right_neighbor=container[i].left_neighbor=i; alpar@222: minimum=i; alpar@222: } alpar@222: container[i].prio=value; alpar@222: ++num_items; alpar@222: } alpar@222: alpar@222: alpar@222: Item top() const { alpar@222: return container[minimum].name; alpar@222: } alpar@222: alpar@222: alpar@222: PrioType prio() const { alpar@222: return container[minimum].prio; alpar@222: } alpar@222: alpar@222: alpar@222: alpar@222: alpar@222: PrioType& operator[](const Item& it) { alpar@222: return container[iimap[it]].prio; alpar@222: } alpar@222: alpar@222: const PrioType& operator[](const Item& it) const { alpar@222: return container[iimap[it]].prio; alpar@222: } alpar@222: alpar@222: // const PrioType get(const Item& it) const { alpar@222: // return container[iimap[it]].prio; alpar@222: // } alpar@222: alpar@222: void pop() { alpar@222: /*The first case is that there are only one root.*/ alpar@222: if ( container[minimum].left_neighbor==minimum ) { alpar@222: container[minimum].in=false; alpar@222: if ( container[minimum].degree!=0 ) { alpar@222: makeroot(container[minimum].child); alpar@222: minimum=container[minimum].child; alpar@222: balance(); alpar@222: } alpar@222: } else { alpar@222: int right=container[minimum].right_neighbor; alpar@222: unlace(minimum); alpar@222: container[minimum].in=false; alpar@222: if ( container[minimum].degree > 0 ) { alpar@222: int left=container[minimum].left_neighbor; alpar@222: int child=container[minimum].child; alpar@222: int last_child=container[child].left_neighbor; alpar@222: alpar@222: makeroot(child); alpar@222: alpar@222: container[left].right_neighbor=child; alpar@222: container[child].left_neighbor=left; alpar@222: container[right].left_neighbor=last_child; alpar@222: container[last_child].right_neighbor=right; alpar@222: } alpar@222: minimum=right; alpar@222: balance(); alpar@222: } // the case where there are more roots alpar@222: --num_items; alpar@222: } alpar@222: alpar@222: alpar@222: void erase (const Item& it) { alpar@222: int i=iimap[it]; alpar@222: alpar@222: if ( i >= 0 && container[i].in ) { alpar@222: if ( container[i].parent!=-1 ) { alpar@222: int p=container[i].parent; alpar@222: cut(i,p); alpar@222: cascade(p); alpar@222: } alpar@222: minimum=i; //As if its prio would be -infinity alpar@222: pop(); alpar@222: } alpar@222: } alpar@222: alpar@222: alpar@222: void decrease (Item it, PrioType const value) { alpar@222: int i=iimap[it]; alpar@222: container[i].prio=value; alpar@222: int p=container[i].parent; alpar@222: alpar@222: if ( p!=-1 && comp(value, container[p].prio) ) { alpar@222: cut(i,p); alpar@222: cascade(p); alpar@222: } alpar@222: if ( comp(value, container[minimum].prio) ) minimum=i; alpar@222: } alpar@222: alpar@222: alpar@222: void increase (Item it, PrioType const value) { alpar@222: erase(it); alpar@222: push(it, value); alpar@222: } alpar@222: alpar@222: alpar@222: state_enum state(const Item &it) const { alpar@222: int i=iimap[it]; alpar@222: if( i>=0 ) { alpar@222: if ( container[i].in ) i=0; alpar@222: else i=-2; alpar@222: } alpar@222: return state_enum(i); alpar@222: } alpar@222: alpar@222: alpar@222: private: alpar@222: alpar@222: void balance() { alpar@222: alpar@222: int maxdeg=int( floor( 2.08*log(double(container.size()))))+1; alpar@222: alpar@222: std::vector A(maxdeg,-1); alpar@222: alpar@222: /* alpar@222: *Recall that now minimum does not point to the minimum prio element. alpar@222: *We set minimum to this during balance(). alpar@222: */ alpar@222: int anchor=container[minimum].left_neighbor; alpar@222: int next=minimum; alpar@222: bool end=false; alpar@222: alpar@222: do { alpar@222: int active=next; alpar@222: if ( anchor==active ) end=true; alpar@222: int d=container[active].degree; alpar@222: next=container[active].right_neighbor; alpar@222: alpar@222: while (A[d]!=-1) { alpar@222: if( comp(container[active].prio, container[A[d]].prio) ) { alpar@222: fuse(active,A[d]); alpar@222: } else { alpar@222: fuse(A[d],active); alpar@222: active=A[d]; alpar@222: } alpar@222: A[d]=-1; alpar@222: ++d; alpar@222: } alpar@222: A[d]=active; alpar@222: } while ( !end ); alpar@222: alpar@222: alpar@222: while ( container[minimum].parent >=0 ) minimum=container[minimum].parent; alpar@222: int s=minimum; alpar@222: int m=minimum; alpar@222: do { alpar@222: if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; alpar@222: s=container[s].right_neighbor; alpar@222: } while ( s != m ); alpar@222: } alpar@222: alpar@222: alpar@222: void makeroot (int c) { alpar@222: int s=c; alpar@222: do { alpar@222: container[s].parent=-1; alpar@222: s=container[s].right_neighbor; alpar@222: } while ( s != c ); alpar@222: } alpar@222: alpar@222: alpar@222: void cut (int a, int b) { alpar@222: /* alpar@222: *Replacing a from the children of b. alpar@222: */ alpar@222: --container[b].degree; alpar@222: alpar@222: if ( container[b].degree !=0 ) { alpar@222: int child=container[b].child; alpar@222: if ( child==a ) alpar@222: container[b].child=container[child].right_neighbor; alpar@222: unlace(a); alpar@222: } alpar@222: alpar@222: alpar@222: /*Lacing a to the roots.*/ alpar@222: int right=container[minimum].right_neighbor; alpar@222: container[minimum].right_neighbor=a; alpar@222: container[a].left_neighbor=minimum; alpar@222: container[a].right_neighbor=right; alpar@222: container[right].left_neighbor=a; alpar@222: alpar@222: container[a].parent=-1; alpar@222: container[a].marked=false; alpar@222: } alpar@222: alpar@222: alpar@222: void cascade (int a) alpar@222: { alpar@222: if ( container[a].parent!=-1 ) { alpar@222: int p=container[a].parent; alpar@222: alpar@222: if ( container[a].marked==false ) container[a].marked=true; alpar@222: else { alpar@222: cut(a,p); alpar@222: cascade(p); alpar@222: } alpar@222: } alpar@222: } alpar@222: alpar@222: alpar@222: void fuse (int a, int b) { alpar@222: unlace(b); alpar@222: alpar@222: /*Lacing b under a.*/ alpar@222: container[b].parent=a; alpar@222: alpar@222: if (container[a].degree==0) { alpar@222: container[b].left_neighbor=b; alpar@222: container[b].right_neighbor=b; alpar@222: container[a].child=b; alpar@222: } else { alpar@222: int child=container[a].child; alpar@222: int last_child=container[child].left_neighbor; alpar@222: container[child].left_neighbor=b; alpar@222: container[b].right_neighbor=child; alpar@222: container[last_child].right_neighbor=b; alpar@222: container[b].left_neighbor=last_child; alpar@222: } alpar@222: alpar@222: ++container[a].degree; alpar@222: alpar@222: container[b].marked=false; alpar@222: } alpar@222: alpar@222: alpar@222: /* alpar@222: *It is invoked only if a has siblings. alpar@222: */ alpar@222: void unlace (int a) { alpar@222: int leftn=container[a].left_neighbor; alpar@222: int rightn=container[a].right_neighbor; alpar@222: container[leftn].right_neighbor=rightn; alpar@222: container[rightn].left_neighbor=leftn; alpar@222: } alpar@222: alpar@222: alpar@222: class store { alpar@222: friend class FibHeap; alpar@222: alpar@222: Item name; alpar@222: int parent; alpar@222: int left_neighbor; alpar@222: int right_neighbor; alpar@222: int child; alpar@222: int degree; alpar@222: bool marked; alpar@222: bool in; alpar@222: PrioType prio; alpar@222: alpar@222: store() : parent(-1), child(-1), degree(), marked(false), in(true) {} alpar@222: }; alpar@222: alpar@222: }; alpar@222: alpar@222: } //namespace hugo alpar@222: #endif