fibheap.H

Go to the documentation of this file.

#ifndef TI_FIBHEAP_
#define TI_FIBHEAP_

#include <cstddef>
#include <fstream>

//#define PEDANDIC_FIBHEAP
//#define FIBNODE_POOL

typedef size_t size_type;


#if defined(ASM_CMOV) && (__GNUC__ >= 3) && (__GNUC_MINOR__ >= 3)
 #warning "using asm_ifaeqbsetac(a,b,c)"
 #define asm_ifaeqbsetac(a,b,c) \
   asm ( \
    "cmpl %[B],%[A]\n\t" \
    "cmovel %[C],%[A]\n\t" \
    : [A] "+r" (a) : [B] "g" (b), [C] "g" (c) : "cc");
#endif


template <class Data> class FibNode
{
  //  friend class FibHeap<Data>;
public:
  FibNode<Data> *father, *son, *left, *right;
  size_type rank;
  Data data;
  bool mark;
};


#ifdef FIBNODE_POOL
// fibnodes have their own pool
template <class T> class CPool
{
private:
  T** pool;
  unsigned int poolsize;
  unsigned int poolpos;

public:
  inline explicit CPool(int _poolsize = 1024) : poolsize(_poolsize) 
   {
     pool = new T*[poolsize];
     for (unsigned int i=0; i<poolsize; ++i) pool[i] = new T;
     poolpos=poolsize;
   }

  inline ~CPool()
   {
     cout << "CPool destructor called " << poolpos << "/" << poolsize << endl;
     for (unsigned int i=0; i<poolpos; ++i) delete pool[i];
     delete [] pool;
   }

  inline T* const new_node(void)
   {
     if (poolpos) return pool[--poolpos];
     else
      {
        const unsigned int oldsize = poolsize;
        poolsize = (oldsize<<1) - (oldsize>>1);
        cout << "Pool empty, increasing Poolsize to "<< poolsize << endl;
        delete [] pool;
        pool = new T*[poolsize];
        poolpos=poolsize-oldsize;
        for (unsigned int i=0; i<poolpos; ++i) pool[i] = new T;
        return pool[--poolpos];
      }
   }

  inline void release_node(T* node)
   {
     if (poolpos<poolsize) pool[poolpos++]=node;
     else
      {
        cout << "Pool full, this should not happen!" << endl;
        delete node;
      }
   }
};

#else
// fibnodes handled by normal memory management
template <class T> class CPool
{
public:
  inline T* new_node(void) const
   {
     return new T;
   }

  inline void release_node(T* node) const
   {
     delete node;
   }
};
#endif


template <class Data> class FibHeap : protected CPool<FibNode<Data> >
{
private:
  FibNode<Data> *min;
  size_type heapsize;

  const FibNode<Data> * next(const FibNode<Data> *act, const bool down = true) const;
  const FibNode<Data> * search(const Data &d) const;
  void remove_son(FibNode<Data> * const n);
  void remove_left(FibNode<Data> * const n);
  void remove_all(void);
  void move_up(FibNode<Data> * const n);

public:
  inline FibHeap(void) : min(NULL), heapsize(0) { }
  ~FibHeap(void);
  void clear(void);
  void init(void);
  void insert(const Data &d);
  inline void push(const Data &d) { insert(d); }
  inline const Data& get_min(void) const { return min->data; }
  inline const Data& top(void) const { return min->data; }
  void delete_min(void);
  inline void pop(void) { delete_min(); }
  inline size_type size(void) const { return heapsize; }
  inline bool empty(void) const { return heapsize==0; }
  void change(const Data &old_data, const Data &new_data);
  void remove(const Data &d);
  void dump(std::ofstream &f);
  void dump_tree(std::ofstream &f);
};


template <class Data>
void FibHeap<Data>::init(void)
{
  remove_all();
}

template <class Data>
FibHeap<Data>::~FibHeap(void)
{
  init();
}

template <class Data>
void FibHeap<Data>::clear(void)
{
  init();
}

template <class Data>
void FibHeap<Data>::insert(const Data &d)
{
  FibNode<Data> * const tmp = this->new_node();
  ++heapsize;
  tmp->data = d;
  tmp->rank = 0;
  tmp->mark = false;
  tmp->father = tmp->son = NULL;
  if (min == NULL) {
    tmp->left = tmp->right = tmp;
    min = tmp;
  } else {
    tmp->left = min->left;
    min->left = tmp;
    tmp->left->right = tmp;
    tmp->right = min;
    if (tmp->data < min->data) min = tmp;
  }
}


template <class Data>
void FibHeap<Data>::delete_min(void)
{
  if (heapsize == 0) return;
  heapsize--;
  if (heapsize == 0) {
    release_node(min);
    min = NULL;
    return;
  }

  FibNode<Data> *tmp;

  if (min->son == NULL) {
    min->left->right = min->right;
    min->right->left = min->left;
    tmp = min->left;
    release_node(min);
  } else {
    tmp = min->son;
    if (min->left == min) {
      release_node(min);
    } else {
      tmp->left->right = min->right;
      min->right->left = tmp->left;
      min->left->right = tmp;
      tmp->left = min->left;
      release_node(min);
    }
  }
  min = tmp;

#ifdef PEDANDIC_FIBHEAP
  size_type s, logsize;
  logsize=1;
  s=heapsize;
  while(s>0) { ++logsize; s>>=1; }
  // logsize is log2(heapsize) and rank <= 1.44 * logsize
  FibNode<Data> **rank_array = new FibNode<Data>*[2*logsize];
  for (s=0; s<2*logsize; s+=1) rank_array[s] = NULL;
#else
  FibNode<Data>* rank_array[48] = { NULL };
  // should be sufficiently large for any "standard" 32-bit-computer!
#endif

  FibNode<Data> *next = tmp;
  FibNode<Data> *tmp2;

  do
  {
    tmp = next;
    next = next->left;
    tmp->father = NULL;
    if (tmp->data < min->data) min = tmp;
    while (((tmp2=rank_array[tmp->rank])!=NULL) && (tmp2!=tmp))
     {
       // join tmp2 and tmp to rank+1 tree
       rank_array[tmp->rank]=NULL;
       if (tmp2->data < tmp->data)
        {
          register FibNode<Data>* const tmp3 = tmp2;
          tmp2 = tmp;
          tmp  = tmp3;
        }

      tmp2->left->right = tmp2->right;
      tmp2->right->left = tmp2->left;
#if defined(asm_ifaeqbsetac)
      asm_ifaeqbsetac(next,tmp2,tmp2->left);
      asm_ifaeqbsetac(min,tmp2,tmp);
#else
      if (next == tmp2) next = tmp2->left;
      if (min  == tmp2) min = tmp;
#endif
      tmp2->father = tmp;
      tmp->rank+=1;
      tmp->mark = false;

      // insert tmp2 in tmp->son list
      if (tmp->son == NULL)
       {
         tmp->son = tmp2;
         tmp2->left = tmp2->right = tmp2;
       }
      else
       {
         tmp->son->left->right = tmp2;
         tmp2->right = tmp->son;
         tmp2->left = tmp->son->left;
         tmp->son->left = tmp2;
       }
     }
    rank_array[tmp->rank]=tmp;
  } while (tmp2!=tmp);

#ifdef PEDANTIC_FIBHEAP
  delete [] rank_array;
#endif
}


template <class Data>
void FibHeap<Data>::change(const Data &old_data, const Data &new_data)
{
  FibNode<Data> * const tmp = search(old_data);
  if (tmp == NULL) return;

  if (old_data<new_data) {
    remove(old_data);
    insert(new_data);
    return;
  }

  tmp->data = new_data;
  if (old_data == new_data) return;
  if (tmp->father) {
    move_up(tmp);
  }
  if (new_data < min->data) min = tmp;

}

template <class Data>
void FibHeap<Data>::remove(const Data &d)
{
  FibNode<Data> * const tmp = search(d);
  if (tmp==NULL) return;
  if (tmp->father) {
    move_up(tmp);
  }
  min = tmp;
  delete_min();
}

template <class Data>
const FibNode<Data>* FibHeap<Data>::search(const Data &d) const
{
  const FibNode<Data>* tmp = min;
  if (tmp == NULL) return NULL;
  do {
    if (tmp->data == d) return tmp;
    tmp = next(tmp, !(d < tmp->data));
  } while (tmp != NULL);
  return NULL;
}

template <class Data>
void FibHeap<Data>::move_up(FibNode<Data> * const n)
{
  if (n == NULL) return;
  FibNode<Data> * const f = n->father;
  if (f == NULL) return;

  n->father = NULL;
  f->rank-=1;
  if (n->left == n) {
    f->son = NULL;
  } else {
    if (f->son == n) f->son = n->left;
    n->left->right = n->right;
    n->right->left = n->left;
  }
  n->left = min;
  n->right = min->right;
  n->right->left = n;
  min->right = n;
  if (f->mark) {
    move_up(f);
  } else {
    f->mark = true;
  }
}

template <class Data>
const FibNode<Data> * FibHeap<Data>::next(const FibNode<Data> *act, const bool down /* =true */) const
{
  if (down && (act->son != NULL)) return act->son;
  if ((act->father != NULL) 
      && (act->father->son != act->left))
    return act->left;
  if (act->father == NULL) {
    if (act->left == min) return NULL;
    else return act->left;
  }
  while ((act->father != NULL) && (act->father->son == act->left)) {
    act = act->father;
  }
  if ((act->father == NULL) && (act->left == min)) return NULL;
  return act->left;
}

template <class Data>
void FibHeap<Data>::dump(std::ofstream &f)
{
  using std::endl;
  FibNode<Data> *tmp;
  size_type nr;

  f << "graph [" << endl << "directed 1" <<endl;
  
  tmp = min;
  nr = 0;
  while (tmp != NULL) {
    f << "node [" << endl;
    f << "id " << static_cast<unsigned long>(tmp) << endl;
    f << "label \"" << tmp->data << "\""<< endl;
    f << "]" << endl;
    if (tmp->son != NULL) {
      f << "edge [" << endl;
      f << "label \"s\"" << endl;
      f << "source " << static_cast<unsigned long>(tmp) << endl;
      f << "target " << static_cast<unsigned long>(tmp->son) << endl;
      f << "]" << endl;
    }
    if (tmp->father != NULL) {
      f << "edge [" << endl;
      f << "label \"f\"" << endl;
      f << "source " << static_cast<unsigned long>(tmp) << endl;
      f << "target " << static_cast<unsigned long>(tmp->father) << endl;
      f << "]" << endl;
    }
    if (tmp->left != NULL) {
      f << "edge [" << endl;
      f << "label \"l\"" << endl;
      f << "source " << static_cast<unsigned long>(tmp) << endl;
      f << "target " << static_cast<unsigned long>(tmp->left) << endl;
      f << "]" << endl;
    }
    if (tmp->right != NULL) {
      f << "edge [" << endl;
      f << "label \"r\"" << endl;
      f << "source " << static_cast<unsigned long>(tmp) << endl;
      f << "target " << static_cast<unsigned long>(tmp->right) << endl;
      f << "]" << endl;
    }
    
    nr +=1;
    tmp = next(tmp);
  }
  f << "]" << endl;
}

template <class Data>
void FibHeap<Data>::dump_tree(std::ofstream &f)
{
  using std::endl;
  FibNode<Data> *tmp;
  size_type nr;

  f << "graph [" << endl << "directed 1" << endl;
  f << "node [" << endl;
  f << "id 0" << endl;
  f << "label \"Wood\"" << endl;
  f << "]" << endl;
  
  tmp = min;
  nr = 0;
  while (tmp != NULL) {
    f << "node [" << endl;
    f << "id " << static_cast<unsigned long>(tmp) << endl;
    f << "label \"" << tmp->data << "\""<< endl;
    f << "]" << endl;
    f << "edge [" << endl;
    f << "source " << static_cast<unsigned long>(tmp->father) << endl;
    f << "target " << static_cast<unsigned long>(tmp) << endl;
    f << "]" << endl;
    nr +=1;
    tmp = next(tmp);
  }
  f << "]" << endl;
}

template <class Data>
void FibHeap<Data>::remove_son(FibNode<Data> * const n)
{
  // remove sons of *n
  FibNode<Data> * const s = n->son;

  if (s == NULL) return;
  if (s->son != NULL) remove_son(s);
  if (s->left != s) remove_left(s);
  // s is only son of n
  release_node(s);
  n->son=NULL;
  heapsize--;
}

template <class Data>
void FibHeap<Data>::remove_left(FibNode<Data> * const n)
{
  // remove siblings of *n
  FibNode<Data> * const l=n->left;
  const FibNode<Data> *f=n->father;

  if (f == NULL) f=min;
  else f=f->son;
  // f is the first of the siblings

  if (l->son != NULL) remove_son(l);
  if (l->left != f) remove_left(l);
  // l is last sibling of n and without sons
  n->left=l->left;
  l->left->right=n;
  release_node(l);
  heapsize--;
}

template <class Data>
void FibHeap<Data>::remove_all(void)
{
  if (heapsize == 0) return;
  remove_son(min);
  remove_left(min);
  release_node(min);
  min = NULL;
  heapsize--;
}

#endif

---