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