home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / basic / _f_heap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  7.9 KB  |  347 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _f_heap.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef HEAPH
  17. #include <LEDA/f_heap.h>
  18. #endif
  19.  
  20. #ifndef MATHH
  21. #include <math.h>
  22. #endif
  23.  
  24. //-----------------------------------------------------------------------------
  25. // class f_heap_node
  26. //-----------------------------------------------------------------------------
  27.  
  28.  
  29. void f_heap_node::link(f_heap_node *sohn)
  30.     // Vereinigung der beiden Heap geordneten Baeume h1 und h2
  31.     // sohn wird neues Kind des Knotens
  32.     // Vorbedingung: rank == sohn->rank && key <= sohn->key
  33. { 
  34.    //sohn aus seiner Liste loeschen
  35.    sohn->left->right = sohn->right;
  36.    sohn->right->left = sohn->left;
  37.  
  38.    // sohn in zirkulaere Liste der Kinder von vater aufnehmen
  39.    if ( children == 0 )
  40.      { children = sohn;
  41.        // zirkulaere Liste aufbauen
  42.        sohn->left = sohn;
  43.        sohn->right = sohn;
  44.      }
  45.    else
  46.      // in bestehende Liste aufnehmen
  47.      { sohn->left = children;
  48.        sohn->right = children->right;
  49.        children->right->left = sohn;
  50.        children->right = sohn;
  51.      }
  52.  
  53.    sohn->parent = this;
  54.    rank++;
  55.    sohn->mark = 0;
  56.  
  57. }  // end of link()
  58.  
  59.    void f_heap_node::cut(f_heap_node* m_ptr)
  60.     // loescht die Beziehung des Knotens zu seinem Elterknoten
  61.     // und fuegt ihn in Wurzel-Liste (nach m_ptr) ein
  62.     // Precondition: parent != 0 
  63.     { 
  64.        if ( parent->rank == 1 )
  65.             parent->children = 0;
  66.         else  // mehrere Kinder
  67.            { if ( parent->children == this ) parent->children = right;
  68.              // x aus zirkulaerer Liste loeschen
  69.              left->right = right;
  70.              right->left = left;
  71.             } 
  72.         parent->rank--;
  73.         parent=0;
  74.  
  75.        // in zirkulaere Liste der Wurzeln aufnehmen
  76.  
  77.        left = m_ptr;
  78.        right = m_ptr->right;
  79.        m_ptr->right->left = this;
  80.        m_ptr->right = this;
  81.  
  82.     }  // end of cut() 
  83.  
  84.  
  85. //-----------------------------------------------------------------------------
  86. // class f_heap
  87. //-----------------------------------------------------------------------------
  88.  
  89. f_heap::f_heap() 
  90. { node_count = 0;
  91.   minptr = 0;
  92.   node_list = 0;
  93.   rank_field = new f_heap_node*[63];
  94.  }  
  95.  
  96. f_heap_node* f_heap::first_item() const
  97. { while (node_list && node_list->deleted) 
  98.   { f_heap_node* p = node_list;
  99.     f_heap_node *const *const q = &node_list;  
  100.     (*(f_heap_node**)q) = node_list->next;
  101.     delete p;
  102.    }
  103.   return node_list;
  104. }
  105.  
  106. f_heap_node* f_heap::next_item(f_heap_node* p) const
  107. { while (p->next && p->next->deleted)
  108.   { f_heap_node* q = p->next->next;
  109.     delete p->next;
  110.     p->next = q;
  111.    }
  112.   return p->next;
  113. }
  114.  
  115. f_heap::f_heap(const f_heap& H)
  116. { node_count = 0;
  117.   minptr = 0;
  118.   node_list = 0;
  119.   rank_field = new f_heap_node*[63];
  120.  
  121.   f_heap_node* min_p=0;
  122.  
  123.   for(f_heap_node* p = H.first_item(); p; p = H.next_item(p))
  124.    { f_heap_node* q = insert(p->key,p->inf);  
  125.      // base class insert: calls default virtuals => we must call virtuals of H
  126.      // and compute the minimum
  127.      H.copy_key(q->key);    
  128.      H.copy_inf(q->inf);
  129.      if (min_p ==0) min_p = q;
  130.      else if ( H.cmp(q->key,min_p->key) < 0 ) min_p = q;
  131.     }
  132.    minptr = min_p;
  133. }
  134.  
  135. f_heap& f_heap::operator=(const f_heap& H)
  136. { if (this == &H) return *this;
  137.   clear();
  138.   for (f_heap_node* p = H.first_item(); p; p = H.next_item(p)) 
  139.    insert(p->key,p->inf);  // calls correct virtual functions 
  140.  
  141.  }
  142.  
  143.   
  144.  
  145. int f_heap::max_rank() const
  146. { // max_rank <= 1.4404 * log_2(node_count)
  147.   register int x = 0;
  148.   register int n = node_count;
  149.   while (n) { x++;
  150.               n >>= 1;
  151.              }
  152.   return int(1.5*x);
  153. }
  154.  
  155. void f_heap::change_inf(f_heap_node* p, ent i)
  156. { clear_inf(p->inf);
  157.   copy_inf(i);
  158.   p->inf = i;
  159. }
  160.   
  161.  
  162. f_heap_node *f_heap::insert(ent k, ent info)
  163. {   // Kreieren eines neuen heap ordered trees und Einfuegen 
  164.  
  165.     copy_key(k);
  166.     copy_inf(info);
  167.  
  168.     f_heap_node *neu = new_f_heap_node(k,info);
  169.  
  170.     if ( minptr == 0 )
  171.       { minptr = neu;
  172.         // zirkulaere Liste aufbauen
  173.         neu->right = neu;
  174.         neu->left = neu;
  175.       }
  176.     else  
  177.       // in zirkulaere Liste aufnehmen und minptr ueberpruefen
  178.       { neu->left = minptr;
  179.         neu->right = minptr->right;
  180.         minptr->right->left = neu;
  181.         minptr->right = neu;
  182.         if ( cmp(k,minptr->key) < 0 ) minptr = neu;
  183.        }
  184.  
  185.     node_count++;
  186.  
  187.     return ( neu );
  188.  
  189.  } 
  190.  
  191.  
  192. void f_heap::decrease_key(f_heap_node *start, ent newkey)
  193.   // neuer Distanzlabel fuer angegebenen Knoten
  194.   { register f_heap_node* vater = start->parent;
  195.     register f_heap_node* x = start;
  196.  
  197.     if (start->left == 0 || start->right == 0)
  198.        error_handler(1,"f_heap decrease_key: item not in f_heap"); 
  199.  
  200.  
  201.     int d = cmp(newkey,x->key);
  202.  
  203.     if ( d==0  && cmp(newkey,minptr->key) ) return; 
  204.  
  205.     if ( d > 0 )
  206.      { cout << "newkey = ";
  207.        print_key(newkey);
  208.        cout << "   oldkey = "; 
  209.        print_key(x->key);
  210.        cout << "   minkey = ";
  211.        print_key(minptr->key);
  212.        cout <<  "\n";
  213.        error_handler(1,"f_heap: key too large in decrease_key.");
  214.  
  215.      }
  216.  
  217.     copy_key(newkey);
  218.     clear_key(x->key);
  219.     x->key = newkey; 
  220.  
  221.     if ( vater && cmp(newkey,vater->key) <= 0 )
  222.      { // streiche Kante ( x, Vater(x) )
  223.        x->cut(minptr);
  224.  
  225.       // errege(Vater(x))
  226.         x = vater;
  227.         while ( x->mark && x->parent )
  228.           { vater = x->parent;
  229.             x->cut(minptr);
  230.             x = vater;
  231.           }
  232.         x->mark = 1;
  233.       }
  234.  
  235.     // minptr testen
  236.     if ( cmp(newkey,minptr->key) <= 0 ) minptr = start;   // "<=" by s.n.
  237.  
  238.  
  239.   }  // end of decrease_key()
  240.  
  241. void f_heap::del_min()
  242.   // Knoten mit minimalem Distanzlabel wird geloescht
  243.   { f_heap_node *ring1, *ring2, *lauf, *help; 
  244.  
  245.     f_heap_node* erg = minptr;
  246.  
  247.     // leerer F-Heap ?
  248.     if ( minptr == 0 ) return;
  249.  
  250.     if ( node_count > 0 ) node_count--;
  251.  
  252.     // letzter Knoten im F-Heap ?
  253.     if ( node_count==0 )
  254.      { minptr = 0;
  255.        clear_key(erg->key);
  256.        clear_inf(erg->inf);
  257.        erg->deleted = 1;
  258.        return;
  259.       }
  260.  
  261.     // ring1 und ring2 zum Verschmelzen der Listen
  262.     ring1 = minptr->right;
  263.     ring2 = minptr->children;
  264.  
  265.     if ( ring2 )
  266.      {  // Elternbeziehung von ring2 loeschen
  267.        while ( ring2->parent )
  268.         { ring2->parent = 0;
  269.           ring2 = ring2->right;
  270.          }    
  271.  
  272.        // Verschmelzen (altes Minimum bleibt zunaechst drin!)
  273.        ring2->left->right = ring1;
  274.        ring1->left->right = ring2;
  275.        help = ring1->left;
  276.        ring1->left = ring2->left;
  277.        ring2->left = help;
  278.       }
  279.  
  280.  
  281.     // Vereinigung der Heap geordneten Baeume
  282.  
  283.     int max = max_rank();
  284.  
  285.     for ( int i = 0 ; i <= max ; i++ ) rank_field[i] = 0;
  286.  
  287.     lauf  = minptr->right;
  288.     help  = lauf;
  289.  
  290.     while (lauf != minptr)   // altes Minimum dient als Stopper
  291.     { register f_heap_node* r = lauf;
  292.       register f_heap_node* r1;
  293.       register int rank = r->rank;
  294.  
  295.       lauf = lauf->right;
  296.  
  297.       while (r1=rank_field[rank])
  298.       { rank_field[rank] = 0;
  299.         if (cmp(r->key,r1->key) <= 0) r->link(r1);
  300.         else { r1->link(r);
  301.                r = r1; 
  302.               }
  303.         rank++;
  304.        }
  305.       rank_field[rank] = r;
  306.  
  307.       if ( cmp(r->key,help->key) <= 0 ) help = r;  // neues Minimum
  308.         
  309.      }
  310.  
  311.     // altesMinimum loeschen
  312.     minptr->left->right = minptr->right;
  313.     minptr->right->left = minptr->left;
  314.  
  315.     // minptr neu setzen
  316.     minptr = help;
  317.  
  318.     clear_key(erg->key);
  319.     clear_inf(erg->inf);
  320.  
  321.     erg->deleted = 1;
  322.  
  323. }  // end of del_min()
  324.  
  325.  
  326. void f_heap::clear()
  327.   { f_heap_node* tail = node_list;
  328.  
  329.     if (tail==0) return;
  330.  
  331.     for(;;)
  332.     { if (tail->deleted == 0)
  333.       { clear_key(tail->key);
  334.         clear_inf(tail->inf);
  335.        }
  336.       if (tail->next) tail = tail->next;
  337.       else break;
  338.      }
  339.  
  340.      deallocate_list(node_list,tail,10);
  341.  
  342.      node_count = 0;
  343.      minptr     = 0;
  344.      node_list  = 0;
  345.   }
  346.  
  347.