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

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

数值算法/人工智能

开发平台：

MultiPlatform

ch_map.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  ch_map.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  15. #ifndef LEDA_CH_MAP_H
  16. #define LEDA_CH_MAP_H
  18. //------------------------------------------------------------------------------
  19. // Hashing Map with Chaining & Table Doubling
  20. //
  21. // S. Naeher  (1994)
  22. //
  23. //------------------------------------------------------------------------------
  25. #include <LEDA/basic.h>
  26.  
  28. //------------------------------------------------------------------------------
  29. // class ch_map_elem  
  30. //------------------------------------------------------------------------------
  32. class ch_map_elem 
  33. {
  34.   friend class ch_map;
  36.   unsigned long    k;
  37.   GenPtr           i;
  38.   ch_map_elem*  succ;
  39. };
  41. typedef ch_map_elem*  ch_map_item;
  44. //--------------------------------------------------------------------
  45. // class ch_map
  46. //--------------------------------------------------------------------
  50. class ch_map 
  51. {
  53.    static ch_map_elem STOP;
  55.    ch_map_elem* table;
  56.    ch_map_elem* table_end;
  57.    ch_map_elem* free;
  58.    ch_map_elem* iterator;
  60.    int table_size;           
  61.    int table_size_1;           
  62.    int shift;
  64.    virtual void clear_inf(GenPtr&)  const { }
  65.    virtual void copy_inf(GenPtr&)   const { }
  66.    virtual void init_inf(GenPtr&)   const { }
  69. /*
  70.    ch_map_elem*  HASH(unsigned long x)  const
  71.    { return table + ((x>>shift) & table_size_1);  }
  72. */
  73.    ch_map_elem*  HASH(unsigned long x)  const
  74.    { return table + (x & table_size_1);  }
  76.    void init_table(int);
  77.    void rehash();
  78.    GenPtr& access1(ch_map_item, unsigned long);
  80.    public:
  82.    void clear_entries();
  84.    GenPtr& access(unsigned long);
  85.    GenPtr  access(unsigned long) const;
  86.    GenPtr  lookup(unsigned long) const;
  88.    void print();
  90.    void start_iteration();
  91.    bool next_index(unsigned long&);
  93.    ch_map_item first_item() const { return 0; }
  94.    ch_map_item next_item(ch_map_item) const { return 0; }
  96.    ch_map& operator=(const ch_map&);
  97.    ch_map(const ch_map&);
  98.    ch_map(int s = 0, int n=1024); 
  100.    virtual ~ch_map() { delete[] table; }
  102. };
  106. inline GenPtr& ch_map::access(unsigned long x)
  107. { 
  108.   ch_map_item p = HASH(x);
  109.   if (p->k == x) 
  110.     return p->i; 
  111.   else
  112.     if (p->k == 0xFFFFFFFF) // NIL
  113.        { p->k = x;
  114.          init_inf(p->i);
  115.          return p->i;
  116.         }
  117.      else
  118.        return access1(p,x);
  119.  }
  121. #endif