Merge remote-tracking branch 'remotes/github/ychat-0.5' into ychat-0.5ychat-0.5

1 files changed, 180 insertions, 0 deletions

diff --git a/hmap.cpp b/hmap.cpp
new file mode 100644
index 0000000..662a203
--- /dev/null
+++ b/hmap.cpp
@@ -0,0 +1,180 @@
+#ifndef hmap_cpp
+#define hmap_cpp
+
+
+#include "hmap.h"
+
+using namespace std;
+
+bool  isPrime( int n );
+int nextPrime( int n );
+
+// Construct the hash table.
+template <class obj_type, class key_type>
+hmap<obj_type, key_type>::hmap( double mop )
+              : maxOccupiedPercentage(mop), array( nextPrime( 101 ) )
+{
+ cout << "hmap Constructor" << endl;
+ lookups = 0;
+ make_empty( );
+}
+
+// Insert item x into the hash table. If the item is
+// already present, do nothing
+template <class obj_type, class key_type>
+void hmap<obj_type, key_type>::add_elem( const obj_type &x, const key_type &k  )
+{
+ // Insert x as active
+ int currentPos = findPos( k );
+ if( isActive( currentPos ) )
+  return;
+
+ array[ currentPos ] = hash_entry( x, k, ACTIVE );
+ //	cout << "Inserted=" << x << "= at " << currentPos << endl;
+ if( ++occupied > array.size( ) * maxOccupiedPercentage )
+  rehash( );
+}
+
+// Expand the hash table.
+template <class obj_type, class key_type>
+void hmap<obj_type, key_type>::rehash( )
+{
+ vector<hash_entry> oldArray = array;
+
+ // Create new double-sized, empty table
+ array.resize( nextPrime( 2 * oldArray.size( ) ) );
+ for( int j = 0; j < array.size( ); j++ )
+  array[ j ].info = EMPTY;
+
+ // Copy table over
+ make_empty( );
+ for( int i = 0; i < oldArray.size( ); i++ )
+  if( oldArray[ i ].info == ACTIVE )
+   add_elem( oldArray[ i ].element, oldArray[ i ].key );
+}
+
+// Hash function, can only handle strings.
+// If you want to hash other objects you will have to 
+// create a hash table for them
+template <class obj_type, class key_type>
+unsigned int hmap<obj_type, key_type>::hash( const string & key ) const
+{
+ unsigned int hashVal = 0;
+ //	cout << key << "%";
+
+ for( size_t i = 0; i < key.size(); i++ )
+  hashVal =  ( hashVal << 5 ) ^ key[ i ] ^ hashVal;
+
+ return hashVal;
+}
+
+// Method that performs quadratic probing resolution.
+// Return the position where the search for x terminates.
+template <class obj_type, class key_type>
+int hmap<obj_type, key_type>::findPos( const key_type &k )
+{
+ int collisionNum = 0;
+ int currentPos = hash( k ) % array.size( );
+ lookups++;
+
+ while( array[ currentPos ].info != EMPTY &&
+        array[ currentPos ].key != k )
+ {
+ //		cout <<  array[ currentPos ].element << "!=" << x << endl;
+  lookups++;
+  currentPos += 2 * ++collisionNum - 1;  // Compute ith probe
+
+  if( currentPos >= array.size( ) )
+   currentPos -= array.size( );
+ }
+
+ //	cout << currentPos << " ";
+ return currentPos;
+}
+
+// Remove item x from the hash table.
+template <class obj_type, class key_type>
+void hmap<obj_type, key_type>::del_elem( const key_type & k )
+{
+    int currentPos = findPos( k );
+    if( isActive( currentPos ) )
+        array[ currentPos ].info = DELETED;
+}
+
+// Find item x in the hash table.
+// Return a pointer to the matching item or 0 if not found
+template <class obj_type, class key_type>
+obj_type hmap<obj_type, key_type>::get_elem( const key_type &k )
+{
+ int currentPos = findPos( k );
+ if( isActive( currentPos ) )
+  return array[ currentPos ].element;
+ else
+  return 0;
+}
+
+// Make the hash table logically empty.
+template <class obj_type, class key_type>
+void hmap<obj_type, key_type>::make_empty( )
+{
+ occupied = 0;
+ for( int i = 0; i < array.size( ); i++ )
+  array[ i ].info = EMPTY;
+}
+
+// Return true if currentPos exists and is active.
+template <class obj_type, class key_type>
+bool hmap<obj_type, key_type>::isActive( int currentPos ) const
+{
+ return array[ currentPos ].info == ACTIVE;
+}
+
+
+// Internal method to test if a positive number is prime.
+// Not an efficient algorithm.
+template <class obj_type, class key_type>
+bool hmap<obj_type, key_type>::isPrime( int n ) const 
+{
+ if( n == 2 || n == 3 )
+  return true;
+
+ else if( n == 1 || n % 2 == 0 )
+  return false;
+
+ for( int i = 3; i * i <= n; i += 2 )
+  if( n % i == 0 )
+   return false;
+
+ return true;
+}
+
+// Internal method to return a prime number at least as large as n.
+// Assumes n > 0.
+template <class obj_type, class key_type>
+int hmap<obj_type, key_type>::nextPrime( int n ) const
+{
+ if( n % 2 == 0 )
+  n++;
+
+ for( ; !isPrime( n ); n += 2 );
+
+ return n;
+}
+template<class obj_type, class key_type> void
+hmap<obj_type, key_type>::run_func( void (*func)(obj_type) )
+{
+ for( int i = 0; i < array.size( ); i++ )
+  if ( array[i].info == ACTIVE )
+   ( *func ) ( array[i].element );
+}
+
+template<class obj_type, class key_type> void
+hmap<obj_type, key_type>::run_func( void (*func)(obj_type, void*), void* v_arg )
+{
+ for( int i = 0; i < array.size( ); i++ )
+  if ( array[i].info == ACTIVE )
+   ( *func ) ( array[i].element, v_arg );
+}
+
+#endif
+