[Scummvm-cvs-logs] SF.net SVN: scummvm: [21476] scummvm/trunk/common/hashmap.h

fingolfin at users.sourceforge.net fingolfin at users.sourceforge.net
Tue Mar 28 04:35:10 CEST 2006


Revision: 21476
Author:   fingolfin
Date:     2006-03-28 04:34:34 -0800 (Tue, 28 Mar 2006)
ViewCVS:  http://svn.sourceforge.net/scummvm/?rev=21476&view=rev

Log Message:
-----------
Added iterator support to hashmap, as well as erase & find methods (all currently needs more testing and may be buggy)

Modified Paths:
--------------
    scummvm/trunk/common/hashmap.h
Modified: scummvm/trunk/common/hashmap.h
===================================================================
--- scummvm/trunk/common/hashmap.h	2006-03-28 11:21:13 UTC (rev 21475)
+++ scummvm/trunk/common/hashmap.h	2006-03-28 12:34:34 UTC (rev 21476)
@@ -114,7 +114,37 @@
 	void expand_array(uint newsize);
 
 public:
+	class const_iterator {
+		typedef const HashMap<Key, Val> * hashmap_t;
+		friend class HashMap<Key, Val>;
+	protected:
+		hashmap_t _hashmap;
+		uint _idx;
+		const_iterator(uint idx, hashmap_t hashmap) : _idx(idx), _hashmap(hashmap) {}
 
+		const BaseNode *deref() const {
+			assert(_hashmap != 0);
+			BaseNode *node(_hashmap->_arr[_idx]);
+			assert(node != 0);
+			return node;
+		}
+
+	public:
+		const_iterator() : _idx(0), _hashmap(0) {}
+
+		const BaseNode &operator *() const { return *deref(); }
+		const BaseNode *operator->() const { return deref(); }
+		bool operator !=(const const_iterator &iter) const { return _idx != iter._idx || _hashmap != iter._hashmap; }
+		void operator ++() {
+			assert(_hashmap);
+			do {
+				_idx++;
+			} while (_idx < _hashmap->_arrsize && _hashmap->_arr[_idx] == 0);
+			if (_idx >= _hashmap->_arrsize)
+				_idx = (uint)-1;
+		}
+	};
+
 	HashMap();
 	~HashMap();
 
@@ -126,19 +156,26 @@
 
 	void clear(bool shrinkArray = 0);
 
-	// The following two methods are used to return a list of
-	// all the keys / all the values (or rather, duplicates of them).
-	// Currently they aren't used, and I think a better appraoch
-	// is to add iterators, which allow the same in a more C++-style
-	// fashion, do not require making duplicates, and finally
-	// even allow in-place modifications of
-	//const_iterator	begin() const
-	//const_iterator	end() const
+	size_t erase(const Key &key);
+
+	const_iterator	begin() const {
+		// TODO/FIXME: Fix this, entry 0 is not necessarily != NULL
+		return const_iterator(0, this);
+	}
+	const_iterator	end() const {
+		return const_iterator((uint)-1, this);
+	}
 	
-	// TODO: There is no "remove" method yet.
-	//void remove(const Key &key);
+	const_iterator	find(const String &key) const {
+		uint ctr = lookup(key);
+		if (_arr[ctr])
+			return const_iterator(ctr, this);
+		return end();
+	}
+	
+	
+	// TODO: insert() method?
 
-
 	bool empty() const {
 		return (_nele == 0);
 	}
@@ -296,6 +333,28 @@
 	return _arr[ctr]->_value;
 }
 
+template <class Key, class Val>
+size_t HashMap<Key, Val>::erase(const Key &key) {
+	// This is based on code in the Wikipedia article on Hash tables.
+	uint i = lookup(key);
+	if (_arr[i] == NULL)
+		return 0; // key wasn't present, so no work has to be done
+	uint j = i;
+	while (true) {
+		j = (j + 1) % _arrsize;
+		if (_arr[j] == NULL)
+			break;
+		uint k = hashit(_arr[j]->_key, _arrsize);
+		if ((j > i && (k <= i || k > j)) ||
+		    (j < i && (k <= i && k > j)) ) {
+			_arr[i] = _arr[j];
+			i = j;
+		}
+	}
+	_arr[i] = NULL;
+	return 1;
+}
+
 }	// End of namespace Common
 
 #endif


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.





More information about the Scummvm-git-logs mailing list