[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