开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
r_heap.h
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：3k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

r_heap.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  r_heap.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. /* This file has been automatically generated from "r_heap.w"
  15.    by CTANGLE (Version 3.1 [km2c]) */
  20. #include <LEDA/basic.h>
  24. class r_heap_node {
  25.   friend class r_heap;
  27.   GenPtr key; /* key */
  28.   GenPtr inf; /* information */
  29.   int bucket; /* number of bucket containing the node */
  30.   r_heap_node *succ, *pred; /* pointers for list maintenance */
  32.  public:
  34.   r_heap_node(GenPtr k, GenPtr i):
  35.    key(k), inf(i), bucket(0), succ(nil),
  36.    pred(nil) {
  37.   }
  39.    LEDA_MEMORY(r_heap_node)
  40. };
  42. typedef r_heap_node *r_heap_item;
  47. class r_heap {
  48. /* data kept in an |r_heap| */
  49.   int C; /* maximal difference between two keys in the
  50.  * heap */
  51.   r_heap_item *buckets; /* buckets of the |r_heap| */
  52.   int *u; /* upper bounds on the key intervals
  53.  * corresponding to the buckets */
  54.   int B; /* number of buckets */
  55.   int si; /* current number of elements stored in the
  56.  * heap */
  57.   int *bsize; /* table used to (re-)initialize the array
  58.  * |u| or part of it */
  60. /* private functions that facilitate the descriptions of the |r_heap| operations */
  62.   inline void set_bucket_bounds(int min, int upto);
  63.   inline int findbucket(r_heap_item, int);
  64.   void copy_heap(const r_heap &);
  65.   inline void add_item(r_heap_item, int);
  66.   inline void rm_item(r_heap_item);
  68. /* non-public functions concerned with the use of |r_heap| within LEDA */
  70.   virtual void print_key(GenPtr) const {
  71.   }
  72.   virtual void print_inf(GenPtr) const {
  73.   }
  74.   virtual void clear_key(GenPtr &) const {
  75.   }
  76.   virtual void clear_inf(GenPtr &) const {
  77.   }
  78.   virtual void copy_key(GenPtr &) const {
  79.   }
  80.   virtual void copy_inf(GenPtr &) const {
  81.   }
  82.   virtual int int_type() const {
  83.     return 0;
  84.   }
  86.  protected:
  87.    r_heap_node * item(void *p) const {
  88.     return (r_heap_node *) p;
  89.   }
  91.  public:
  92.    r_heap(int C);
  93. /* the maximal difference between two keys in the heap needs to be provided upon initialization */
  95.   r_heap() {
  96.     error_handler(1, "r_heap: must initialize with int C>=0");
  97.   }
  98.   r_heap(const r_heap &);
  99.   r_heap & operator = (const r_heap &);
  100.   virtual ~ r_heap() {
  101.     clear();
  102.   }
  104.   r_heap_item find_min() const;
  106.   r_heap_item insert(GenPtr k, GenPtr i); /* precondition: |k >=
  107.  * key(find_min())| */
  109.   void del_item(r_heap_node * x);
  111.   void del_min();
  113.   void decrease_key(r_heap_node * x, GenPtr k); /* precond.:
  114.  * |key(find_min())<=k<key(x)|
  115.  *  */
  117.   void change_inf(r_heap_node * x, GenPtr i);
  119.   GenPtr key(r_heap_node * x) const {
  120.     return x->key;
  121.   }
  122.   GenPtr inf(r_heap_node * x) const {
  123.     return x->inf;
  124.   }
  126.   void clear();
  127.   int size() const;
  128.   int empty() const;
  130. /* functions that are used by the LEDA iteration macros */
  132.   r_heap_item first_item() const;
  133.   r_heap_item next_item(r_heap_item p) const;
  135.   void print_contents(ostream & chk = cout) const;
  136. };
  138. /* dummy I/O and cmp functions */
  140. inline void Print(const r_heap &, ostream &)
  141. {
  142. }
  143. inline void Read(r_heap &, istream &)
  144. {
  145. }
  146. inline int compare(const r_heap &, const r_heap &)
  147. {
  148.   return 0;
  149. }