Merge pull request #515 from gsomix/CSet

CSet and CMap
shogun-toolbox · May 9, 2012 · 98c94f9 · 98c94f9
2 parents f91c456 + 7d48e17
commit 98c94f9
Show file tree

Hide file tree

Showing 6 changed files with 512 additions and 36 deletions.
diff --git a/examples/undocumented/libshogun/Makefile b/examples/undocumented/libshogun/Makefile
@@ -59,6 +59,8 @@ TARGETS = basic_minimal \
 		  splitting_standard_crossvalidation \
 		  mathematics_arpack \
 		  library_fibonacci_heap \
+		  library_set \
+		  library_map \
 		  mathematics_lapack \
 		  converter_locallylinearembedding \
 		  converter_localtangentspacealignment \

diff --git a/examples/undocumented/libshogun/library_map.cpp b/examples/undocumented/libshogun/library_map.cpp
@@ -0,0 +1,38 @@
+#include <shogun/lib/Map.h>
+#include <shogun/io/SGIO.h>
+#include <shogun/base/init.h>
+#include <shogun/lib/common.h>
+
+using namespace shogun;
+
+#define SIZE 6
+
+void print_message(FILE* target, const char* str)
+{
+	fprintf(target, "%s", str);
+}
+
+int main(int argc, char** argv)
+{
+	init_shogun(&print_message, &print_message, &print_message);
+	const char* v[SIZE] = {"Russia", "England", "Germany", "USA", "France", "Spain"};
+
+	CMap<int32_t, const char*>* map = new CMap<int32_t, const char*>(SIZE/2, SIZE/2);
+
+	for (int i=0; i<SIZE; i++)
+		map->add(i, v[i]);
+
+	map->remove(0);
+
+	//SG_SPRINT("Num of elements: %d\n", map->get_num_elements());
+	for (int i=0; i<SIZE; i++)
+	{
+		if (map->contains(i));
+			//SG_SPRINT("key %d contains in map with index %d and data=%s\n", 
+			//	i, map->index_of(i), map->get_element(i));
+	}
+
+	SG_UNREF(map);
+	exit_shogun();
+	return 0;
+}
diff --git a/examples/undocumented/libshogun/library_set.cpp b/examples/undocumented/libshogun/library_set.cpp
@@ -0,0 +1,37 @@
+#include <shogun/lib/Set.h>
+#include <shogun/io/SGIO.h>
+#include <shogun/base/init.h>
+#include <shogun/lib/common.h>
+
+using namespace shogun;
+
+#define SIZE 8
+
+void print_message(FILE* target, const char* str)
+{
+	fprintf(target, "%s", str);
+}
+
+int main(int argc, char** argv)
+{
+	init_shogun(&print_message, &print_message, &print_message);
+	double v[SIZE] = {0.0,0.1,0.2,0.2,0.3,0.4,0.5,0.5};
+
+	CSet<double>* set = new CSet<double>(SIZE/2, SIZE/2);
+
+	for (int i=0; i<SIZE; i++)
+		set->add(v[i]);
+
+	set->remove(0.2);
+
+	//SG_SPRINT("Num of elements: %d\n", set->get_num_elements());
+	for (int i=0; i<SIZE; i++)
+	{
+		if (set->contains(v[i]));
+			//SG_SPRINT("%lg contains in set with index %d\n", v[i], set->index_of(v[i]));
+	}
+
+	SG_UNREF(set);
+	exit_shogun();
+	return 0;
+}
diff --git a/src/shogun/lib/Map.h b/src/shogun/lib/Map.h
@@ -50,7 +50,7 @@ IGNORE_IN_CLASSLIST template<class K, class T> struct CMapNode
 };
 #endif
 
-/** @brief the class CSet, a set based on the hash-table.
+/** @brief the class CMap, a map based on the hash-table.
  * w: http://en.wikipedia.org/wiki/Hash_table
  */
 IGNORE_IN_CLASSLIST template<class K, class T> class CMap: public CSGObject
@@ -118,23 +118,30 @@ IGNORE_IN_CLASSLIST template<class K, class T> class CMap: public CSGObject
 	/** @return object name */
 	virtual const char* get_name() const { return "Map"; }
 
-	/** Add an element to the set
+	/** Add an element to the map
 	 *
-	 * @param e elemet to be added
+	 * @param key key to be added
+	 * @param data data to be added
+	 * @return index of added element
 	 */
-	void add(const K& key, const T& data)
+	int32_t add(const K& key, const T& data)
 	{
 		int32_t index=hash(key);
 		if (chain_search(index, key)==NULL)
 		{
-			insert_key(index, key, data);
+			int32_t added_index=insert_key(index, key, data);
 			num_elements++;
+
+			return added_index;
 		}
+
+		return -1;
 	}
 
-	/** Remove an element from the set
+	/** Check an element in the map
 	 *
-	 * @param e element to be looked for
+	 * @param key key to be looked for
+	 * @return true if element contains in the map
 	 */
 	bool contains(const K& key)
 	{
@@ -147,7 +154,7 @@ IGNORE_IN_CLASSLIST template<class K, class T> class CMap: public CSGObject
 
 	/** Remove an element from the set
 	 *
-	 * @param e element to be removed
+	 * @param key key to be removed
 	 */
 	void remove(const K& key)
 	{
@@ -163,7 +170,7 @@ IGNORE_IN_CLASSLIST template<class K, class T> class CMap: public CSGObject
 
 	/** Index of element in the set
 	 *
-	 * @param e element to be removed
+	 * @param key key to be looked for
 	 * @return index of the element or -1 if not found
 	 */
 	int32_t index_of(const K& key)
@@ -177,37 +184,65 @@ IGNORE_IN_CLASSLIST template<class K, class T> class CMap: public CSGObject
 		return -1;
 	}
 
-	/** Get number of elements
+	/** Get element by key
 	 *
-	 * @return number of elements
+	 * @param key key to be looked for
+	 * @return exist element or new element 
+	 * (if key doesn't consist in map)
 	 */
-	int32_t get_num_elements() const
+	T get_element(const K& key)
 	{
-		return num_elements;
+		int32_t index=hash(key);
+		CMapNode<K, T>* result=chain_search(index, key);
+
+		if (result!=NULL)		
+			return result->data;
+		else
+		{
+			int32_t added_index=add(key, T());
+			result=get_node_ptr(added_index);
+
+			return result->data;
+		}
+	}
+
+	/** Set element by key
+	 *
+	 * @param key key of element 
+	 * @param data new data for element
+	 */
+	void set_element(const K& key, const T& data)
+	{
+		int32_t index=hash(key);
+		CMapNode<K, T>* result=chain_search(index, key);
+
+		if (result!=NULL)		
+			result->data=data;
+		else
+		{
+			add(key, data);
+		}
 	}
 
 	/** Get number of elements
 	 *
 	 * @return number of elements
 	 */
-	int32_t get_maxnum_elements() const
+	int32_t get_num_elements() const
 	{
-		return array->get_num_elements();
+		return num_elements;
 	}
 
-	/** Get set element at index
-	 *
-	 * (does NOT do bounds checking)
+	/** Get size of auxilary array
 	 *
-	 * @param index index
-	 * @return array element at index
+	 * @return array size
 	 */
-	T get_element(int32_t index) const
+	int32_t get_array_size() const
 	{
-		return array->get_element(index)->data;
+		return array->get_num_elements();
 	}
 
-	/** get set element at index as reference
+	/** get element at index as reference
 	 *
 	 * (does NOT do bounds checking)
 	 *
@@ -216,26 +251,26 @@ IGNORE_IN_CLASSLIST template<class K, class T> class CMap: public CSGObject
 	 */
 	T* get_element_ptr(int32_t index)
 	{
-		if (is_free(array->get_element(index)))
-			return NULL;
-		return &(array->get_element(index)->data);
+		CMapNode<K, T>* result=array->get_element(index);
+		if (result!=NULL && !is_free(result))
+			return &(array->get_element(index)->data);
+		return NULL;
 	}
 
-	/** operator overload for set read only access
-	 * use add() for write access
+	/** get node at index as reference
 	 *
-	 * DOES NOT DO ANY BOUNDS CHECKING
+	 * (does NOT do bounds checking)
 	 *
 	 * @param index index
-	 * @return element at index
+	 * @return node at index
 	 */
-	T operator[](int32_t index) const
+	CMapNode<K, T>* get_node_ptr(int32_t index)
 	{
-		return array->get_element(index)->data;
+		return array->get_element(index);
 	}
 
 	/** @return underlying array of nodes in memory */
-	T* get_array()
+	CMapNode<K, T>** get_array()
 	{
 		return array->get_array();
 	}
@@ -283,7 +318,7 @@ IGNORE_IN_CLASSLIST template<class K, class T> class CMap: public CSGObject
 	}
 
 	/** Inserts nodes with certain key and data in set */
-	void insert_key(int32_t index, const K& key, const T& data)
+	int32_t insert_key(int32_t index, const K& key, const T& data)
 	{
 		int32_t new_index;
 		CMapNode<K, T>* new_node;
@@ -329,6 +364,8 @@ IGNORE_IN_CLASSLIST template<class K, class T> class CMap: public CSGObject
 
 			hash_array[index]=new_node;
 		}
+
+		return new_index;
 	}
 
 	/** Deletes key from set */