tagging ychat-0.6ychat-0.6

1 files changed, 125 insertions, 0 deletions

diff --git a/hmap.h b/hmap.h
new file mode 100644
index 0000000..d8aeda6
--- /dev/null
+++ b/hmap.h
@@ -0,0 +1,125 @@
+#pragma warning(disable:4786)
+
+#ifndef hmap_h
+#define hmap_h
+
+#include <vector>
+#include "incl.h"
+
+using namespace std;
+
+// void add_elem( obj_type x, key_type k )       --> Insert x
+// void del_elem( key_type k )       --> Remove x
+// obj_type get_elem( key_type k )  --> Return item that matches x
+// void make_empty( )      --> Remove all items
+
+template <class obj_type, class key_type>
+class hmap
+{
+private:
+    enum entry_type
+    {
+        ACTIVE, EMPTY, DELETED
+    };
+
+    struct hash_entry
+    {
+        obj_type   element;
+        key_type   key;
+        entry_type info;
+
+        hash_entry( const obj_type &e = obj_type( ), const key_type &k = key_type( ), entry_type i = EMPTY ) : element( e ), key( k ), info( i )
+        { }
+    }
+    ;
+
+    int occupied;
+
+    virtual bool is_active( int i_current_pos ) const;
+    virtual void rehash( );
+    virtual bool is_prime  ( int n ) const;
+    virtual int  next_prime( int n ) const;
+    double       i_max_occupied_percentage;
+
+protected:
+    int lookups;
+    unsigned int hash( const string &key ) const;
+    vector<hash_entry> array;
+
+public:
+    hmap( double moc );
+
+    virtual int  find_pos  ( const key_type &k );
+    virtual void make_empty( );
+    virtual void add_elem ( const obj_type &x, const key_type &k );
+    virtual void del_elem ( const key_type &k );
+    virtual obj_type get_elem ( const key_type &k );
+
+    virtual void  run_func( void (*func)(obj_type) );
+    virtual void  run_func( void (*func)(obj_type, void*), void* v_arg );
+
+    virtual vector<key_type>*  get_key_vector( );
+    
+    // inline:
+    void get_size()
+    {
+        int size = 0;
+        for( int j = 0; j < array.size( ); j++ )
+            if (array[ j ].info == ACTIVE)
+                size++;
+        return size;
+    };
+
+    int get_lookups()
+    {
+        return lookups;
+    };
+
+    int get_capacity()
+    {
+        return array.size();
+    };
+
+    double get_lambda()
+    {
+        return static_cast<double>(get_size())/static_cast<double>(get_capacity());
+    }
+
+    obj_type& operator[]( key_type &k )
+    {
+        return get_elem( k );
+    }
+
+};
+
+template <class obj_type, class key_type>
+class linearhmap : public hmap<obj_type, key_type>
+{
+public:
+    linearhmap(double moc) : hmap<obj_type, key_type>(moc)
+    {}
+    ;
+
+    virtual int find_pos( const key_type &k )
+    {
+        int i_collision_num = 0;
+        int i_current_pos = hash( k ) % array.size( );
+        lookups++;
+
+        while( array[ i_current_pos ].info != EMPTY &&
+                array[ i_current_pos ].key  !=  k )
+        {
+            lookups   ++;
+            i_current_pos++;
+
+            if( i_current_pos >= array.size( ) )
+                i_current_pos -= array.size( );
+        }
+
+        return i_current_pos;
+    }
+};
+
+#include "hmap.cpp"
+
+#endif