// -*- C++ -*-

#ifndef HUGO_FIB_HEAP_H

#define HUGO_FIB_HEAP_H

///\file

///\brief Fibonacci Heap implementation.

#include <vector>

#include <functional>

#include <math.h>

namespace hugo {

  /// An implementation of the Fibonacci Heap.

  /**

     This class implements the \e Fibonacci \e heap data structure. A \e

     heap is a data structure for storing items with specified priorities,

     such that finding the item with minimum priority is efficient. In a

     heap one can change the priority of an item, and to add or erase an

     item.

     The methods \ref increase and \ref erase are not efficient, in

     case of many calls to these operations, it is better to use

     a binary heap.

     /param Item The type of the items to be stored.  

     /param Prio The type of the priority of the items.

     /param ItemIntMap A read and writable Item int map, for the usage of

     the heap.

     /param Compare A class for the comparison of the priorities. The

     default is \c std::less<Prio>.

  */

#ifdef DOXYGEN

  template <typename Item, 

	    typename Prio, 

	    typename ItemIntMap, 

	    typename Compare>

#else

  template <typename Item, 

	    typename Prio, 

	    typename ItemIntMap, 

	    typename Compare = std::less<Prio> >

#endif

  class FibHeap {

  public: 

    typedef Prio PrioType;

  private:

    class store;

    std::vector<store> container;

    int minimum;

    ItemIntMap &iimap;

    Compare comp;

    int num_items;

    ///\todo It is use nowhere

    ///\todo It doesn't conform to the naming conventions.

  public:

    enum state_enum {

      IN_HEAP = 0,

      PRE_HEAP = -1,

      POST_HEAP = -2

    };

  public :

    FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} 

    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 

      iimap(_iimap), comp(_comp), num_items() {}

    ///The number of items stored in the heap.

    /**

    Returns the number of items stored in the heap.

    */

    int size() const { return num_items; }

    ///Checks if the heap stores no items.

    /**

       Returns true iff the heap stores no items.

    */

    bool empty() const { return num_items==0; }

    ///Item \c item gets to the heap with priority \c value independently if \c item was already there.

    /**

       This method calls \ref push(item, value) if \c item is not

       stored in the heap, and it calls \ref decrease(it, \c value) or

       \ref increase(it, \c value) otherwise.

    */

    void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van

    ///Adds \c item to the heap with priority \c value. 

    /**

       Adds \c item to the heap with priority \c value. 

       \pre \c item must not be stored in the heap. 

    */

    void push (Item const it, PrioType const value); /*vigyazat: az implementacioban it van*/

    ///Returns the item having the minimum priority w.r.t.  Compare.

    /**

       This method returns the item having the minimum priority w.r.t.  Compare. 

       \pre The heap must be nonempty.

    */

    Item top() const { return container[minimum].name; }

    ///Returns the minimum priority w.r.t.  Compare.

    /**

       It returns the minimum priority w.r.t.  Compare.

       \pre The heap must be nonempty.

    */

    PrioType prio() const { return container[minimum].prio; }

    ///Returns the priority of \c item.

    /**

       It returns the priority of \c item.

       \pre \c item must be in the heap.

    */

    PrioType& operator[](const Item& it) { return container[iimap[it]].prio; }

    ///Returns the priority of \c item.

    /**

       It returns the priority of \c item.

       \pre \c item must be in the heap.

    */

    const PrioType& operator[](const Item& it) const { 

      return container[iimap[it]].prio; 

    }

    ///Deletes the item with minimum priority w.r.t.  Compare.

    /**

    This method deletes the item with minimum priority w.r.t. 

    Compare from the heap.

    \pre The heap must be non-empty.

    */

    void pop();

    ///Deletes \c item from the heap.

    /**

       This method deletes \c item from the heap, if \c item was already

       stored in the heap. It is quite inefficient in Fibonacci heaps.

    */

    void erase (const Item& item); /*vigyazat: az implementacioban it van*/

    ///Decreases the priority of \c item to \c value.

    /**

       This method decreases the priority of \c item to \c value.

       \pre \c item must be stored in the heap with priority at least \c

       value w.r.t.  Compare.

    */

    void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/

    ///Increases the priority of \c item to \c value.

    /**

       This method sets the priority of \c item to \c value. Though

       there is no precondition on the priority of \c item, this

       method should be used only if one wants to \e increase

       (w.r.t.  Compare) the priority of \c item, because this

       method is inefficient.

    */

    void increase (Item it, PrioType const value) {

      erase(it);

      push(it, value);

    }

    ///Tells if \c item is in, was in, or has not been in the heap.

    /**

       This method returns PRE_HEAP if \c item has never been in the

       heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP

       otherwise. In the latter case it is possible that \c item will

       get back to the heap again.

    */

    state_enum state(const Item &it);  /*vigyazat: az implementacioban it van*/

    // **********************************************************************

    //  IMPLEMENTATIONS

    // **********************************************************************

    void set (Item const it, PrioType const value) {

      int i=iimap[it];

      if ( i >= 0 && container[i].in ) {

	if ( comp(value, container[i].prio) ) decrease(it, value); 

	if ( comp(container[i].prio, value) ) increase(it, value); 

      } else push(it, value);

    }

    void push (Item const it, PrioType const value) {

      int i=iimap[it];      

      if ( i < 0 ) {

	int s=container.size();

	iimap.set( it, s );	

	store st;

	st.name=it;

	container.push_back(st);

	i=s;

      } else {

	container[i].parent=container[i].child=-1;

	container[i].degree=0;

	container[i].in=true;

	container[i].marked=false;

      }

      if ( num_items ) {

	container[container[minimum].right_neighbor].left_neighbor=i;

	container[i].right_neighbor=container[minimum].right_neighbor;

	container[minimum].right_neighbor=i;

	container[i].left_neighbor=minimum;

	if ( comp( value, container[minimum].prio) ) minimum=i; 

      } else {

	container[i].right_neighbor=container[i].left_neighbor=i;

	minimum=i;	

      }

      container[i].prio=value;

      ++num_items;

    }

    void pop() {

      /*The first case is that there are only one root.*/

      if ( container[minimum].left_neighbor==minimum ) {

	container[minimum].in=false;

	if ( container[minimum].degree!=0 ) { 

	  makeroot(container[minimum].child);

	  minimum=container[minimum].child;

	  balance();

	}

      } else {

	int right=container[minimum].right_neighbor;

	unlace(minimum);

	container[minimum].in=false;

	if ( container[minimum].degree > 0 ) {

	  int left=container[minimum].left_neighbor;

	  int child=container[minimum].child;

	  int last_child=container[child].left_neighbor;

	  makeroot(child);

	  container[left].right_neighbor=child;

	  container[child].left_neighbor=left;

	  container[right].left_neighbor=last_child;

	  container[last_child].right_neighbor=right;

	}

	minimum=right;

	balance();

      } // the case where there are more roots

      --num_items;   

    }

    void erase (const Item& it) {

      int i=iimap[it];

      if ( i >= 0 && container[i].in ) { 	

	if ( container[i].parent!=-1 ) {

	  int p=container[i].parent;

	  cut(i,p);	    

	  cascade(p);

	}

	minimum=i;     //As if its prio would be -infinity

	pop();

      }

    }

    void decrease (Item it, PrioType const value) {

      int i=iimap[it];

      container[i].prio=value;

      int p=container[i].parent;

      if ( p!=-1 && comp(value, container[p].prio) ) {

	cut(i,p);	    

	cascade(p);

      }      

      if ( comp(value, container[minimum].prio) ) minimum=i; 

    }

    state_enum state(const Item &it) const {

      int i=iimap[it];

      if( i>=0 ) {

	if ( container[i].in ) i=0;

	else i=-2; 

      }

      return state_enum(i);

    }

  private:

    void balance() {      

    int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;

    std::vector<int> A(maxdeg,-1); 

    /*

     *Recall that now minimum does not point to the minimum prio element.

     *We set minimum to this during balance().

     */

    int anchor=container[minimum].left_neighbor; 

    int next=minimum; 

    bool end=false; 

       do {

	int active=next;

	if ( anchor==active ) end=true;

	int d=container[active].degree;

	next=container[active].right_neighbor;

	while (A[d]!=-1) {	  

	  if( comp(container[active].prio, container[A[d]].prio) ) {

	    fuse(active,A[d]); 

	  } else { 

	    fuse(A[d],active);

	    active=A[d];

	  } 

	  A[d]=-1;

	  ++d;

	}	

	A[d]=active;

       } while ( !end );

       while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;

       int s=minimum;

       int m=minimum;

       do {  

	 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;

	 s=container[s].right_neighbor;

       } while ( s != m );

    }

    void makeroot (int c) {

      int s=c;

      do {  

	container[s].parent=-1;

	s=container[s].right_neighbor;

      } while ( s != c );

    }

    void cut (int a, int b) {    

      /*

       *Replacing a from the children of b.

       */

      --container[b].degree;

      if ( container[b].degree !=0 ) {

	int child=container[b].child;

	if ( child==a ) 

	  container[b].child=container[child].right_neighbor;

	unlace(a);

      }

      /*Lacing a to the roots.*/

      int right=container[minimum].right_neighbor;

      container[minimum].right_neighbor=a;

      container[a].left_neighbor=minimum;

      container[a].right_neighbor=right;

      container[right].left_neighbor=a;

      container[a].parent=-1;

      container[a].marked=false;

    }

    void cascade (int a) 

    {

      if ( container[a].parent!=-1 ) {

	int p=container[a].parent;

	if ( container[a].marked==false ) container[a].marked=true;

	else {

	  cut(a,p);

	  cascade(p);

	}

      }

    }

    void fuse (int a, int b) {

      unlace(b);

      /*Lacing b under a.*/

      container[b].parent=a;

      if (container[a].degree==0) {

	container[b].left_neighbor=b;

	container[b].right_neighbor=b;

	container[a].child=b;	

      } else {

	int child=container[a].child;

	int last_child=container[child].left_neighbor;

	container[child].left_neighbor=b;

	container[b].right_neighbor=child;

	container[last_child].right_neighbor=b;

	container[b].left_neighbor=last_child;

      }

      ++container[a].degree;

      container[b].marked=false;

    }

    /*

     *It is invoked only if a has siblings.

     */

    void unlace (int a) {      

      int leftn=container[a].left_neighbor;

      int rightn=container[a].right_neighbor;

      container[leftn].right_neighbor=rightn;

      container[rightn].left_neighbor=leftn;

    }

    class store {

      friend class FibHeap;

      Item name;

      int parent;

      int left_neighbor;

      int right_neighbor;

      int child;

      int degree;  

      bool marked;

      bool in;

      PrioType prio;

      store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 

    };

  };

} //namespace hugo

#endif