Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
_m_heap.c
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 3k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

_m_heap.c：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _m_heap.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #include <LEDA/impl/m_heap.h>
  15. m_heap::m_heap(int m)
  16. { if (m<=0) error_handler(1,string("m_heap constructor: illegal size = %d",m));
  17.   count = 0;
  18.   start = 0;
  19.   offset = 0;
  20.   M = m+1;
  21.   T = new list_item[M+1];
  22.   for(int i=0; i<=M; i++) T[i] = L.append(Convert(MAXINT));
  23. }
  25. void m_heap::clear()
  26. { L.clear();
  27.   for(int i=0; i<=M; i++) T[i] = L.append(Convert(MAXINT));
  28.   count = 0;
  29.   start = 0;
  30.   offset = 0;
  31. } 
  33. m_heap_item m_heap::first_item() const
  34. { list_item it = L.first();
  35.   while (it && L.inf(it) == Convert(MAXINT)) it = L.succ(it);
  36.   return it;
  37.  }
  38.   
  39. m_heap_item m_heap::next_item(m_heap_item it) const
  40. { it = L.succ(it);
  41.   while (it && L.inf(it) == Convert(MAXINT)) it = L.succ(it);
  42.   return it;
  43.  }
  45. m_heap_item m_heap::insert(GenPtr kk, GenPtr info)   // int key
  46. { int key = LEDA_ACCESS(int,kk);
  47.   int k;
  48.   if (count)
  49.    { find_min();
  50.      k = key-offset; 
  51.     }
  52.   else 
  53.    { start = key%M;
  54.      k = 0;
  55.      offset = key;
  56.     }
  58.   if (k<0 || k>=M) 
  59.    error_handler(1,string("m_heap insert: illegal key %d n",key));
  61.   copy_inf(info);
  63.   count++;
  64.   return L.insert(info,T[(start+k)%M]); 
  65. }
  67. m_heap_item m_heap::find_min() const
  68. { if (count)
  69.   { while (L.succ(T[start])==T[start+1])
  70.     { (*(int*)&offset)++;
  71.       (*(int*)&start)++;
  72.       if (start == M) (*(int*)&start) = 0;
  73.      }
  74.     return L.succ(T[start]);
  75.    }
  76.  else return 0;
  77. }
  79. GenPtr m_heap::del_min()
  80. { if (count)
  81.    { find_min();
  82.      count--;
  83.      m_heap_item p = L.succ(T[start]);
  84.      GenPtr inf = L.contents(p);
  85.      L.del(p);
  86.      return inf;
  87.     }
  88.   else error_handler(1,"m_heap del_min: heap is empty");
  89.   return 0;
  90. }
  92. void m_heap::del_item(m_heap_item it) 
  93. { GenPtr x = L.contents(it);
  94.   clear_inf(x);
  95.   L.del(it); 
  96.   count--;
  97. }
  99. void m_heap::change_key(m_heap_item it, GenPtr kk)  // int key
  100. { int key = LEDA_ACCESS(int,kk);
  101.   find_min();
  102.   GenPtr inf = L.contents(it);
  103.   L.del(it); 
  104.   int k = key - offset;
  105.   if (k<0 || k>=M) 
  106.    error_handler(1,string("m_heap change key: illegal key %dn",key));
  107.   L.insert(inf,T[(start+k)%M]);
  108. }
  111. void m_heap::print() const
  112. { m_heap_item p;
  113.   cout << string("count = %d   start = %d   offset = %dn",count,start,offset);
  114.   for (int i=0;i<M;i++) 
  115.   if (L.contents(L.succ(T[i])) != Convert(MAXINT))
  116.   { cout << string("%3d: ",i);
  117.     p = L.succ(T[i]);
  118.     while (L.contents(p) != Convert(MAXINT))
  119.      { cout << string("(%d) ",L.contents(p));
  120.        p = L.succ(p);
  121.       }
  122.    cout << "n";
  123.    }
  124.    cout << "n";
  125. }