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

[lordhoto at users.sourceforge.net]

Revision: 31356
          http://scummvm.svn.sourceforge.net/scummvm/?rev=31356&view=rev
Author:   lordhoto
Date:     2008-04-01 19:01:31 -0700 (Tue, 01 Apr 2008)

Log Message:
-----------
Committed patch #1929274 "HashMap: Iterator rework".

Modified Paths:
--------------
    scummvm/trunk/common/hashmap.h

Modified: scummvm/trunk/common/hashmap.h
===================================================================
--- scummvm/trunk/common/hashmap.h	2008-04-01 18:35:14 UTC (rev 31355)
+++ scummvm/trunk/common/hashmap.h	2008-04-02 02:01:31 UTC (rev 31356)
@@ -150,29 +150,25 @@
 	int lookupAndCreateIfMissing(const Key &key);
 	void expand_array(uint newsize);
 
-	class Iterator;
-	class ConstIterator;
-	friend class Iterator;
-	friend class ConstIterator;
+	template<class T> friend class IteratorImpl;
 
 	/**
 	 * Simple HashMap iterator implementation.
 	 */
-	class Iterator {
+	template<class NodeType>
+	class IteratorImpl {
+		friend class HashMap;
+		template<class T> friend class IteratorImpl;
 	protected:
 		typedef const HashMap hashmap_t;
-		friend class HashMap;
 
-		// Allow ConstIterator to read member vars, so that Iterators can be converted to ConstIterator
-		friend class HashMap::ConstIterator;
-
 		uint _idx;
 		hashmap_t *_hashmap;
 
 	protected:
-		Iterator(uint idx, hashmap_t *hashmap) : _idx(idx), _hashmap(hashmap) {}
+		IteratorImpl(uint idx, hashmap_t *hashmap) : _idx(idx), _hashmap(hashmap) {}
 
-		Node *deref() const {
+		NodeType *deref() const {
 			assert(_hashmap != 0);
 			assert(_idx < _hashmap->_arrsize);
 			Node *node = _hashmap->_arr[_idx];
@@ -181,15 +177,17 @@
 		}
 
 	public:
-		Iterator() : _idx(0), _hashmap(0) {}
+		IteratorImpl() : _idx(0), _hashmap(0) {}
+		template<class T>
+		IteratorImpl(const IteratorImpl<T> &c) : _idx(c._idx), _hashmap(c._hashmap) {}
 
-		Node &operator *() const { return *deref(); }
-		Node *operator->() const { return deref(); }
+		NodeType &operator *() const { return *deref(); }
+		NodeType *operator->() const { return deref(); }
 
-		bool operator ==(const Iterator &iter) const { return _idx == iter._idx && _hashmap == iter._hashmap; }
-		bool operator !=(const Iterator &iter) const { return !(*this == iter); }
+		bool operator ==(const IteratorImpl &iter) const { return _idx == iter._idx && _hashmap == iter._hashmap; }
+		bool operator !=(const IteratorImpl &iter) const { return !(*this == iter); }
 
-		Iterator &operator ++() {
+		IteratorImpl &operator ++() {
 			assert(_hashmap);
 			do {
 				_idx++;
@@ -200,76 +198,16 @@
 			return *this;
 		}
 
-		Iterator operator ++(int) {
-			Iterator old = *this;
+		IteratorImpl operator ++(int) {
+			IteratorImpl old = *this;
 			operator ++();
 			return old;
 		}
 	};
 
-	/**
-	 * Simple HashMap const iterator implementation.
-	 * This is almost completely identical to the normal iterator class, only
-	 * with some const keywords added here and there, plus a conversion
-	 * operator which makes it possible to transparently convert iterators to
-	 * const iterators.
-	 * It is sadly not really possible to reduce this code duplication using
-	 * template, unless one is willing to accept various warnings on certain
-	 * compilers. Note that many (most? all?) implementations of the standard
-	 * C++ library use a similar approach for their implementations.
-	 */
-	class ConstIterator {
-	protected:
-		typedef const HashMap hashmap_t;
-		friend class HashMap;
-
-		uint _idx;
-		hashmap_t *_hashmap;
-
-	protected:
-		ConstIterator(uint idx, hashmap_t *hashmap) : _idx(idx), _hashmap(hashmap) {}
-
-		const Node *deref() const {
-			assert(_hashmap != 0);
-			assert(_idx < _hashmap->_arrsize);
-			const Node *node = _hashmap->_arr[_idx];
-			assert(node != 0);
-			return node;
-		}
-
-	public:
-		ConstIterator() : _idx(0), _hashmap(0) {}
-
-		// Converting a non-const iterator to a const one is allowed
-		ConstIterator(const Iterator &iter) : _idx(iter._idx), _hashmap(iter._hashmap) {}
-
-		const Node &operator *() const { return *deref(); }
-		const Node *operator->() const { return deref(); }
-
-		bool operator ==(const ConstIterator &iter) const { return _idx == iter._idx && _hashmap == iter._hashmap; }
-		bool operator !=(const ConstIterator &iter) const { return !(*this == iter); }
-
-		ConstIterator &operator ++() {
-			assert(_hashmap);
-			do {
-				_idx++;
-			} while (_idx < _hashmap->_arrsize && _hashmap->_arr[_idx] == 0);
-			if (_idx >= _hashmap->_arrsize)
-				_idx = (uint)-1;
-
-			return *this;
-		}
-
-		ConstIterator operator ++(int) {
-			ConstIterator old = *this;
-			operator ++();
-			return old;
-		}
-	};
-
 public:
-	typedef Iterator iterator;
-	typedef ConstIterator const_iterator;
+	typedef IteratorImpl<Node> iterator;
+	typedef IteratorImpl<const Node> const_iterator;
 
 	HashMap();
 	HashMap(const HM_t& map);


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