/*******************************************************************************
+
+  LEDA 3.5
+
+  f_heap.h
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/

#ifndef LEDA_FHEAP_H
#define LEDA_FHEAP_H

//------------------------------------------------------------------------------
//
// Fibonacci Heap
//
// Michael Muth  (1988)
//
// Modifications
//
// - virtual compare function  (Stefan Naeher, August 1989)
//
// - virtual clear functions   (Stefan Naeher, April 1990)
//
// - improvement for double keys (key_type_id)  (Stefan Naeher, 1996)
//
//------------------------------------------------------------------------------


#include <LEDA/basic.h>


class f_heap_node  {
// repraesentiert Knoten und Heap geordnete Baeume

friend class f_heap;

   f_heap_node* next;          // used to link all used items 
   f_heap_node* pred;          

   f_heap_node* left;          // left and right siblings (circular List)
   f_heap_node* right;   
   f_heap_node* parent;        // parent node
   f_heap_node* children;      // a child

   int  rank;                   // number of children
   char mark;                   // ( 1=true, 0=false )

   GenPtr key;                  // key
   GenPtr inf;                  // information


// size: 10 words =  40 bytes


   void link(f_heap_node*);
   void cut(f_heap_node*);


public:

   f_heap_node(GenPtr k, GenPtr i, f_heap_node* n) 
   {  key = k;
      inf = i;
      next = n;
      pred = 0;
      rank = 0;
      mark = 0;
      parent = 0;
      children = 0;

      if (n) n->pred = this;

    }  // end of f_heap_node()


  LEDA_MEMORY(f_heap_node)

 };  //f_heap_node


typedef f_heap_node* f_heap_item;


class f_heap
 /* Ein F-Heap enthaelt eine zirkulaere Liste von Heap geordneten
    Baeumen. Der Einstieg erfolgt ueber den minptr, einen Zeiger
    auf den Baum mit kleinstem Schluessel in der Wurzel. Die ei-
    gentlichen Items ( Paare aus NxT ) sind in den Knoten der
    Baeume enthalten.                                               */
 { 
   int node_count;         // number of nodes
   f_heap_node* minptr;    // entry to the List of roots
   f_heap_node* node_list; // List of all nodes

   int max_rank() const;

   f_heap_node* merge_heaps(f_heap_node**);
   f_heap_node* gen_merge_heaps(f_heap_node**);
   f_heap_node* int_merge_heaps(f_heap_node**);

   f_heap_node* new_f_heap_node(GenPtr k, GenPtr i)
   { return  node_list = new f_heap_node(k,i,node_list); }

   virtual int cmp(GenPtr, GenPtr) const { return 0; }

   virtual void print_key(GenPtr)  const {}
   virtual void print_inf(GenPtr)  const {}

   virtual void clear_key(GenPtr&) const {}
   virtual void clear_inf(GenPtr&) const {}

   virtual void copy_key(GenPtr&)  const {}
   virtual void copy_inf(GenPtr&)  const {}

   virtual int  key_type_id() const { return UNKNOWN_TYPE_ID; }

protected:

  f_heap_node* item(void* p) const { return (f_heap_node*)p; }

public:

 f_heap();
 f_heap(const f_heap&);
 f_heap& operator=(const f_heap&);

virtual ~f_heap()  { clear(); }


f_heap_node* insert(GenPtr, GenPtr);
f_heap_node* find_min() const { return(minptr); }

void del_min();  
void decrease_key(f_heap_node*,GenPtr);
void change_inf(f_heap_node*,GenPtr);
void del_item(f_heap_node *x){ decrease_key(x,minptr->key); del_min();}
void clear();

GenPtr  key(f_heap_node *x) const { return x->key ; }
GenPtr  inf(f_heap_node *x) const { return x->inf; }

  
int  size()  const { return node_count; }
int  empty() const { return (find_min()==0) ? true : false; }


// Iteration:


f_heap_node* first_item() const;

f_heap_node* next_item(f_heap_node* p) const;



};  // end of class f_heap


#endif
