Skip to content

Commit

Permalink
deleted CSet, added CMap
Browse files Browse the repository at this point in the history
  • Loading branch information
@gsomix
gsomix committed May 7, 2012
1 parent 8105d5f commit 15cb774
Show file tree
Hide file tree
Showing 3 changed files with 70 additions and 84 deletions.
1 change: 0 additions & 1 deletion examples/undocumented/libshogun/Makefile
View file
Expand Up @@ -59,7 +59,6 @@ TARGETS = basic_minimal \
splitting_standard_crossvalidation \
mathematics_arpack \
library_fibonacci_heap \
library_hashset \
mathematics_lapack \
converter_locallylinearembedding \
converter_localtangentspacealignment \
Expand Down
24 changes: 0 additions & 24 deletions examples/undocumented/libshogun/library_hashset.cpp
View file

This file was deleted.

129 changes: 70 additions & 59 deletions src/shogun/lib/Set.h → src/shogun/lib/Map.h
View file
Expand Up @@ -9,46 +9,55 @@
* Copyright (C) 2012 Evgeniy Andreev (gsomix)
*/

#ifndef _SET_H_
#define _SET_H_
#ifndef _MAP_H_
#define _MAP_H_

#include <shogun/base/SGObject.h>
#include <shogun/lib/common.h>
#include <shogun/lib/Hash.h>
#include <shogun/base/DynArray.h>

#include <cstdio>

namespace shogun
{

#define IGNORE_IN_CLASSLIST

#define MapNode CMapNode<K, T>

#ifndef DOXYGEN_SHOULD_SKIP_THIS
/** hashset node */
template<class T> struct HashSetNode
IGNORE_IN_CLASSLIST template<class K, class T> struct CMapNode
{
/** index in set array
* It also using for reference to next free
* element in array.
*/
/** index in hashtable */
int32_t index;

/** key and data of node */
T element;
/** is free? */
bool free;

/** key of node */
K key;

/** data of node */
T data;

/** pointer to left sibling */
HashSetNode *left;
CMapNode *left;

/** pointer to right sibling */
HashSetNode *right;
CMapNode *right;
};
#endif

/** @brief the class CSet, a set based on the hash-table.
* w: http://en.wikipedia.org/wiki/Hash_table
*/
template<class T> class CSet: public CSGObject
IGNORE_IN_CLASSLIST template<class K, class T> class CMap: public CSGObject
{
public:
/** Default constructor */
CSet()
CMap()
{
hash_size=0;
free_index=0;
Expand All @@ -59,7 +68,7 @@ template<class T> class CSet: public CSGObject
}

/** Custom constructor */
CSet(int32_t size, int32_t reserved=1024, bool tracable=true)
CMap(int32_t size, int32_t reserved=1024, bool tracable=true)
{
hash_size=size;
free_index=0;
Expand All @@ -68,23 +77,23 @@ template<class T> class CSet: public CSGObject

if(use_sg_mallocs)
{
hash_array=SG_CALLOC(HashSetNode<T>*, size);
hash_array=SG_CALLOC(MapNode*, size);
}
else
{
hash_array=(HashSetNode<T>**) calloc(size, sizeof(HashSetNode<T>*));
hash_array=(CMapNode<K, T>**) calloc(size, sizeof(CMapNode<K, T>*));
}

for (int32_t i=0; i<size; i++)
{
hash_array[i]=NULL;
}

array=new DynArray<HashSetNode<T>*>(reserved, tracable);
array=new DynArray<CMapNode<K, T>*>(reserved, tracable);
}

/** Default destructor */
virtual ~CSet()
virtual ~CMap()
{
if (array!=NULL)
{
Expand Down Expand Up @@ -119,18 +128,18 @@ template<class T> class CSet: public CSGObject
}

/** @return object name */
virtual const char* get_name() const { return "Set"; }
virtual const char* get_name() const { return "Map"; }

/** Add an element to the set
*
* @param e elemet to be added
*/
void add(const T& e)
void add(const K& key, const T& data)
{
int32_t index=hash(e);
if (chain_search(index, e)==NULL)
int32_t index=hash(key);
if (chain_search(index, key)==NULL)
{
insert_key(index, e);
insert_key(index, key, data);
num_elements++;
}
}
Expand All @@ -139,10 +148,10 @@ template<class T> class CSet: public CSGObject
*
* @param e element to be looked for
*/
bool contains(const T& e)
bool contains(const K& key)
{
int32_t index=hash(e);
if (chain_search(index, e)!=NULL)
int32_t index=hash(key);
if (chain_search(index, key)!=NULL)
{
return true;
}
Expand All @@ -154,10 +163,10 @@ template<class T> class CSet: public CSGObject
*
* @param e element to be removed
*/
void remove(const T& e)
void remove(const K& key)
{
int32_t index=hash(e);
HashSetNode<T>* result=chain_search(index, e);
int32_t index=hash(key);
CMapNode<K, T>* result=chain_search(index, key);

if (result!=NULL)
{
Expand All @@ -171,10 +180,10 @@ template<class T> class CSet: public CSGObject
* @param e element to be removed
* @return index of the element or -1 if not found
*/
int32_t index_of(const T& e)
int32_t index_of(const K& key)
{
int32_t index=hash(e);
HashSetNode<T>* result=chain_search(index, e);
int32_t index=hash(key);
CMapNode<K ,T>* result=chain_search(index, key);

if (result!=NULL)
{
Expand Down Expand Up @@ -202,7 +211,7 @@ template<class T> class CSet: public CSGObject
*/
T get_element(int32_t index) const
{
return array->get_element(index)->element;
return array->get_element(index)->data;
}

/** get set element at index as reference
Expand All @@ -214,7 +223,9 @@ template<class T> class CSet: public CSGObject
*/
T* get_element_ptr(int32_t index)
{
return &(array->get_element(index)->element);
if (is_free(array->get_element(index)))
return NULL;
return &(array->get_element(index)->data);
}

/** operator overload for set read only access
Expand All @@ -227,7 +238,7 @@ template<class T> class CSet: public CSGObject
*/
T operator[](int32_t index) const
{
return array->get_element(index)->element;
return array->get_element(index)->data;
}

/** @return underlying array of nodes in memory */
Expand All @@ -240,14 +251,15 @@ template<class T> class CSet: public CSGObject
/** Returns hash of key
* MurmurHash used
*/
int32_t hash(const T& key)
int32_t hash(const K& key)
{
return CHash::MurmurHash2((uint8_t*)(&key), sizeof(int32_t), 0xDEADBEEF) % hash_size;
return CHash::MurmurHash2((uint8_t*)(&key), sizeof(key), 0xDEADBEEF) % hash_size;
}

bool is_free(HashSetNode<T>* node)
/** is free? */
bool is_free(CMapNode<K, T>* node)
{
if ((node->left==NULL) && (node->right==NULL))
if (node->free==true)
{
return true;
}
Expand All @@ -256,19 +268,19 @@ template<class T> class CSet: public CSGObject
}

/** Searchs key in list(chain) */
HashSetNode<T>* chain_search(int32_t index, const T& key)
CMapNode<K, T>* chain_search(int32_t index, const K& key)
{
if (hash_array[index]==NULL)
{
return NULL;
}
else
{
HashSetNode<T>* current=hash_array[index];
CMapNode<K, T>* current=hash_array[index];

do // iterating all items in the list
{
if (current->element==key)
if (current->key==key)
{
return current; // it's a search key
}
Expand All @@ -282,26 +294,21 @@ template<class T> class CSet: public CSGObject
}

/** Inserts nodes with certain key and data in set */
void insert_key(int32_t index, const T& e)
void insert_key(int32_t index, const K& key, const T& data)
{
int32_t new_index;
HashSetNode<T>* new_node;

if(array==NULL)
{
return;
}
CMapNode<K, T>* new_node;

if ((free_index>=array->get_num_elements()) || (array->get_element(free_index)==NULL))
{
// init new node
if(use_sg_mallocs)
{
new_node=SG_MALLOC(HashSetNode<T>, 1);
new_node=SG_CALLOC(MapNode, 1);
}
else
{
new_node=(HashSetNode<T>*) calloc(1, sizeof(HashSetNode<T>));
new_node=(CMapNode<K, T>*) calloc(1, sizeof(CMapNode<K, T>));
}

array->append_element(new_node);
Expand All @@ -319,8 +326,10 @@ template<class T> class CSet: public CSGObject
}

new_node->index=new_index;
new_node->element=e;
new_node->left=new_node; // self referencing
new_node->free=false;
new_node->key=key;
new_node->data=data;
new_node->left=NULL;
new_node->right=NULL;

// add new node in start of list
Expand All @@ -338,7 +347,7 @@ template<class T> class CSet: public CSGObject
}

/** Deletes key from set */
void delete_key(int32_t index, HashSetNode<T>* node)
void delete_key(int32_t index, CMapNode<K, T>* node)
{
int32_t temp=0;

Expand All @@ -354,7 +363,7 @@ template<class T> class CSet: public CSGObject

if (node->left!=NULL)
{
node->left->right = node->right;
node->left->right = node->right;
}
else
{
Expand All @@ -364,6 +373,7 @@ template<class T> class CSet: public CSGObject
temp=node->index;

node->index=free_index;
node->free=true;
node->left=NULL;
node->right=NULL;

Expand All @@ -372,8 +382,9 @@ template<class T> class CSet: public CSGObject


protected:
/** */
/** whether SG_MALLOC or just malloc etc shall be used */
bool use_sg_mallocs;

/** hashtable size */
int32_t hash_size;

Expand All @@ -384,12 +395,12 @@ template<class T> class CSet: public CSGObject
int32_t num_elements;

/** array of lists (chains) */
HashSetNode<T>** hash_array;
CMapNode<K, T>** hash_array;

/** array for index permission */
DynArray<HashSetNode<T>*>* array;
DynArray<CMapNode<K, T>*>* array;
};

}

#endif /* _SET_H_ */
#endif /* _MAP_H_ */

0 comments on commit 15cb774

Please sign in to comment.