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

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

数值算法/人工智能

开发平台：

MultiPlatform

dp_hash.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  dp_hash.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #ifndef LEDA_DP_HASH_H
  14. #define LEDA_DP_HASH_H
  16. //------------------------------------------------------------------------------
  17. // Dynamic Perfect Hashing
  18. //
  19. // Michael Wenzel          ( 1990/91 )
  20. //------------------------------------------------------------------------------
  23. #include <LEDA/basic.h>
  26. // ---------------------------------------------------------------
  27. // declarations
  28. // ---------------------------------------------------------------
  31. class headertable;
  32. class subtable;
  33. class dp_hash;
  35. typedef headertable* htp;
  36. typedef subtable* stp;
  38. #define EMPTY (GenPtr(2147483648))
  39. #define maxuni 2147483647
  40.                                 // #define maxprim 2147483659
  41. // aber kleiner wegen random-Funktion
  42. #define maxprim 2147483647
  43. #define wursechs 2.44948974278
  48. // --------------------------------------------------------------
  49. // class headertable
  50. //
  51. // Items werden auf Headertables gehasht,
  52. // die sie dann injektiv auf Subtables verteilen
  54. class headertable {
  56.   unsigned kj;                     // Multiplikator
  57.   int wj;                          // Anzahl Elemente in Tafel
  58.   int mj;                          // max. Anzahl Elemente
  59.   stp tj;                          // Startpunkt der Subtables
  61.   friend class b_dict;
  62.   friend class dp_hash;
  63.   friend class subtable;
  65.   stp lookup(GenPtr );
  67.   bool insert(GenPtr ,GenPtr ,stp& ,int& ,bool& ,stp ,stp );
  68.   int dinsert(GenPtr ,GenPtr ,stp ,stp& ,stp& );
  70.   bool del(GenPtr ,stp ,stp ); 
  71.   int give_elements(stp& ,stp ,stp );  
  74.   headertable()
  75.     { 
  76.       kj = wj = mj=0; 
  77.       tj=0;   
  78.      }
  80. };
  82. // --------------------------------------------------------------
  83. // class subtable
  84. //
  85. // Jedes Subtableelement ist leer,
  86. // oder von der Headertable wird genau ein Element    
  87. // auf eine Position gehasht
  89. class subtable {
  91.   GenPtr ke;
  92.   GenPtr inf;
  94.   friend class b_dict;
  95.   friend class dp_hash;
  96.   friend class headertable;
  98.   void set_s(GenPtr a,GenPtr b)
  99.     {
  100.        ke=a; inf=b; }
  102.   void clear()
  103.     { 
  104.        ke=EMPTY; inf=0; }
  106.   subtable()
  107.     {  
  108.        ke=EMPTY; inf=0; }
  110.   subtable(GenPtr a ,GenPtr b )
  111.     {  
  112.        ke=a; inf=b; }
  114.   subtable(subtable& s)
  115.     {  
  116.        ke=s.ke;
  117.        inf=s.inf; }
  119.    subtable& operator=(subtable& s)
  120.     {
  121.        ke=s.ke;
  122.        inf=s.inf;
  123.        return *this; }
  126.   public:
  128.   GenPtr key() { return ke; }
  130.   GenPtr info() { return inf; }
  132. };
  134. // ------------------------------------------------------------------
  135. // class dp_hash
  136. //
  137. // alle Informationen fuer das Dictionary
  138. // Elemente werden auf Headertables gehasht, 
  139. // die dann die Elemente weitergeben
  140. // Der Platzverbrauch der Headertables wird kontrolliert
  143. class dp_hash {
  145.   htp* htablep;      // Feld von Zeigern auf Headertables
  146.      // leere Headertables werden nicht angelegt
  148.   unsigned k;        // Verteilungsfunktion (k*x)%p%sM
  150.   int n;             // Anzahl Elemente im Dictionary
  152.   int M;             // Anzahl Elemente, die momentan bzgl.
  153.      // Platzverbrauch mit Wahrscheinlichkeit >= 0.5
  154.      // abgespeichert werden koennen ( ohne Rehash )
  156.   int sM;            // Anzahl Headertables
  158.   int bed;           // Kontrolle des Platzverbrauchs
  160.   stp anf,wo,ende;   // zur Speicherverwaltung beim Rehash
  164.   stp  rehash_all(GenPtr=EMPTY ,GenPtr=0);
  167.   virtual void clear_key(GenPtr&)const {}
  168.   virtual void clear_inf(GenPtr&)const {}
  170.   virtual void copy_key(GenPtr&) const {}
  171.   virtual void copy_inf(GenPtr&) const {}
  173. protected:
  175.   stp item(void* p) const { return stp(p); }
  177. public:
  179.   stp first_item() const
  180.   { error_handler(1,"sorry, dp_hash::first_item not implemented");
  181.     return nil;
  182.    }
  184.   stp next_item(stp) const
  185.   { error_handler(1,"sorry, dp_hash::next_item not implemented");
  186.     return nil;
  187.    }
  189.   dp_hash& operator=(const dp_hash&) 
  190.   { error_handler(1,"sorry, dp_hash::operator= not implemented");
  191.     return *this;
  192.    }
  194.   GenPtr  key(stp it)  const { return it->ke; }
  195.   GenPtr  inf(stp it)  const { return it->inf; }
  196.   GenPtr& info(stp it) const { return it->inf; }
  198.   stp  insert(GenPtr,GenPtr );
  199.   void del(GenPtr);
  201.   void del_item(stp it) { del(it->ke); }
  203.   stp  lookup(GenPtr ) const;
  205.   stp  change_inf(GenPtr ,GenPtr );
  207.   int  size() const { return n; }
  209.   void clear();
  212.   dp_hash();
  213.   dp_hash(int ,GenPtr* ,GenPtr* );
  214.   virtual ~dp_hash();
  217.   friend class b_dict;
  219. };
  221. #endif