Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
r_heap.h
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

r_heap.h：Code Content
  2. /* This file has been automatically generated from "r_heap.w"
  3.    by CTANGLE (Version 3.1 [km2c]) */
  8. #include <LEDA/basic.h>
  12. class r_heap_node {
  13.   friend class r_heap;
  15.   GenPtr key; /* key */
  16.   GenPtr inf; /* information */
  17.   int bucket; /* number of bucket containing the node */
  18.   r_heap_node *succ, *pred; /* pointers for list maintenance */
  20.  public:
  22.   r_heap_node(GenPtr k, GenPtr i):
  23.    key(k), inf(i), bucket(0), succ(nil),
  24.    pred(nil) {
  25.   }
  27.    LEDA_MEMORY(r_heap_node)
  28. };
  30. typedef r_heap_node *r_heap_item;
  35. class r_heap {
  36. /* data kept in an |r_heap| */
  37.   int C; /* maximal difference between two keys in the
  38.  * heap */
  39.   r_heap_item *buckets; /* buckets of the |r_heap| */
  40.   int *u; /* upper bounds on the key intervals
  41.  * corresponding to the buckets */
  42.   int B; /* number of buckets */
  43.   int si; /* current number of elements stored in the
  44.  * heap */
  45.   int *bsize; /* table used to (re-)initialize the array
  46.  * |u| or part of it */
  48. /* private functions that facilitate the descriptions of the |r_heap| operations */
  50.   inline void set_bucket_bounds(int min, int upto);
  51.   inline int findbucket(r_heap_item, int);
  52.   void copy_heap(const r_heap &);
  53.   inline void add_item(r_heap_item, int);
  54.   inline void rm_item(r_heap_item);
  56. /* non-public functions concerned with the use of |r_heap| within LEDA */
  58.   virtual void print_key(GenPtr) const {
  59.   }
  60.   virtual void print_inf(GenPtr) const {
  61.   }
  62.   virtual void clear_key(GenPtr &) const {
  63.   }
  64.   virtual void clear_inf(GenPtr &) const {
  65.   }
  66.   virtual void copy_key(GenPtr &) const {
  67.   }
  68.   virtual void copy_inf(GenPtr &) const {
  69.   }
  70.   virtual int int_type() const {
  71.     return 0;
  72.   }
  74.  protected:
  75.    r_heap_node * item(void *p) const {
  76.     return (r_heap_node *) p;
  77.   }
  79.  public:
  80.    r_heap(int C);
  81. /* the maximal difference between two keys in the heap needs to be provided upon initialization */
  83.   r_heap() {
  84.     error_handler(1, "r_heap: must initialize with int C>=0");
  85.   }
  86.   r_heap(const r_heap &);
  87.   r_heap & operator = (const r_heap &);
  88.   virtual ~ r_heap() {
  89.     clear();
  90.   }
  92.   r_heap_item find_min() const;
  94.   r_heap_item insert(GenPtr k, GenPtr i); /* precondition: |k >=
  95.  * key(find_min())| */
  97.   void del_item(r_heap_node * x);
  99.   void del_min();
  101.   void decrease_key(r_heap_node * x, GenPtr k); /* precond.:
  102.  * |key(find_min())<=k<key(x)|
  103.  *  */
  105.   void change_inf(r_heap_node * x, GenPtr i);
  107.   GenPtr key(r_heap_node * x) const {
  108.     return x->key;
  109.   }
  110.   GenPtr inf(r_heap_node * x) const {
  111.     return x->inf;
  112.   }
  114.   void clear();
  115.   int size() const;
  116.   int empty() const;
  118. /* functions that are used by the LEDA iteration macros */
  120.   r_heap_item first_item() const;
  121.   r_heap_item next_item(r_heap_item p) const;
  123.   void print_contents(ostream & chk = cout) const;
  124. };
  126. /* dummy I/O and cmp functions */
  128. inline void Print(const r_heap &, ostream &)
  129. {
  130. }
  131. inline void Read(r_heap &, istream &)
  132. {
  133. }
  134. inline int compare(const r_heap &, const r_heap &)
  135. {
  136.   return 0;
  137. }