HashSet.cpp

Go to the documentation of this file.
00001 /*
00002  * This program is free software; you can redistribute it and/or modify
00003  * it under the terms of the GNU General Public License as published by
00004  * the Free Software Foundation; either version 3 of the License, or
00005  * (at your option) any later version.
00006  *
00007  * Written (W) 2011 Evgeniy Andreev (gsomix)
00008  *
00009  * Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society
00010  */
00011 
00012 #include <shogun/lib/HashSet.h>
00013 
00014 using namespace shogun;
00015 
00016 CHashSet::CHashSet()
00017 {
00018     array_size = 0;
00019     hash_array = NULL;
00020 }
00021 
00022 CHashSet::CHashSet(int32_t size)
00023 {
00024     array_size = size;
00025     hash_array = SG_MALLOC(HashSetNode*, array_size);
00026     for(int32_t i = 0; i < array_size; i++)
00027     {
00028         hash_array[i] = NULL;
00029     }
00030 }
00031 
00032 CHashSet::~CHashSet()
00033 {
00034     if(hash_array != NULL)
00035     {
00036         for(int32_t i = 0; i < array_size; i++)
00037         {
00038             delete hash_array[i];
00039         }
00040         SG_FREE(hash_array);
00041     }
00042 }
00043 
00044 bool CHashSet::insert_key(int32_t key, float64_t data)
00045 {
00046     int32_t index = hash(key);
00047     if(chain_search(index, key) != NULL)
00048     {
00049         // this key is already in set
00050         return false;
00051     }
00052 
00053     // init new node
00054     HashSetNode* new_node = new HashSetNode;
00055     new_node->key = key;
00056     new_node->data = data;
00057     new_node->left = NULL;
00058     new_node->right = NULL;
00059 
00060     // add new node in start of list
00061     if(hash_array[index] == NULL)
00062     {
00063         hash_array[index] = new_node;
00064     }
00065     else
00066     {
00067         hash_array[index]->left = new_node;
00068         new_node->right = hash_array[index];
00069 
00070         hash_array[index] = new_node;
00071     }
00072 
00073     return true;
00074 }
00075 
00076 bool CHashSet::search_key(int32_t key, float64_t &ret_data)
00077 {
00078     int index = hash(key);
00079 
00080     HashSetNode* result = chain_search(index, key);
00081     if(result == NULL)
00082     {
00083         return false;
00084     }
00085     else
00086     {
00087         ret_data = result->data;
00088         return true;
00089     }
00090 }
00091 
00092 HashSetNode* CHashSet::chain_search(int32_t index, int32_t key)
00093 {
00094     if(hash_array[index] == NULL)
00095     {
00096         return NULL;
00097     }
00098     else
00099     {
00100         HashSetNode* current = hash_array[index];
00101 
00102 
00103         do // iterating all items in the list
00104         {
00105             if(current->key == key)
00106             {
00107                 return current; // it's a search key
00108             }
00109 
00110             current = current->right;
00111 
00112         } while(current != NULL);
00113 
00114         return NULL;
00115     }
00116 }
00117 
00118 void CHashSet::delete_key(int32_t key)
00119 {
00120     int index = hash(key);
00121     HashSetNode* result = chain_search(index, key);
00122 
00123     if(result == NULL)
00124     {
00125         return;
00126     }
00127 
00128     if(result->right != NULL)
00129     {
00130         result->right->left = result->left;
00131     }
00132 
00133     if(result->left != NULL)
00134     {
00135         result->left->right = result->right;
00136     }
00137     else
00138     {
00139         hash_array[index] = result->right;
00140     }
00141 
00142     result->left = NULL;
00143     result->right = NULL;
00144 
00145     delete result;
00146 }
00147 
00148 void CHashSet::debug()
00149 {
00150     for(int32_t i = 0; i < array_size; i++)
00151     {
00152         HashSetNode* current = hash_array[i];
00153 
00154         if(current == NULL)
00155         {
00156             SG_SPRINT("NULL\n");
00157             continue;
00158         }
00159 
00160         do
00161         {
00162             SG_SPRINT("%d ", current->key);
00163             current = current->right;
00164         }
00165         while(current != NULL);
00166         printf("\n");
00167     }
00168 }
00169 
00170 int32_t CHashSet::hash(int32_t key)
00171 {
00172     return CHash::MurmurHash2((uint8_t*)(&key), 4, 1) % array_size;
00173 }
00174 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation