[Scummvm-cvs-logs] CVS: scummvm/common map.h,1.16,1.17
Max Horn
fingolfin at users.sourceforge.net
Wed Oct 8 11:06:13 CEST 2003
- Previous message: [Scummvm-cvs-logs] CVS: scummvm/bs2 anims.cpp,1.27,1.28 function.cpp,1.24,1.25 sound.cpp,1.24,1.25 sword2.h,1.17,1.18
- Next message: [Scummvm-cvs-logs] CVS: scummvm/common str.cpp,1.23,1.24 str.h,1.15,1.16
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
Update of /cvsroot/scummvm/scummvm/common
In directory sc8-pr-cvs1:/tmp/cvs-serv10677
Modified Files:
map.h
Log Message:
renamed createNode() to findOrCreateNode(); added addKey() method; reimplemented merge()
Index: map.h
===================================================================
RCS file: /cvsroot/scummvm/scummvm/common/map.h,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -d -r1.16 -r1.17
--- map.h 5 Oct 2003 14:15:31 -0000 1.16
+++ map.h 8 Oct 2003 18:05:20 -0000 1.17
@@ -113,7 +113,7 @@
if (!_root)
node = _root = new Node(key, _header);
else
- node = createNode(_root, key);
+ node = findOrCreateNode(_root, key);
return node->_value;
}
@@ -136,6 +136,15 @@
return (_root == 0);
}
+ Value &addKey(const Key &key) {
+ Node *node;
+ if (!_root)
+ node = _root = new Node(key, _header);
+ else
+ node = findOrCreateNode(_root, key);
+ return node->_value;
+ }
+
void remove(const Key &key) {
// TODO - implement efficiently. Indeed, maybe switch to using red-black trees?
// For now, just a lame, bad remove algorithm. Rule: don't remove elements
@@ -179,17 +188,7 @@
}
void merge(const Map<Key, Value> &map) {
- // FIXME - this is a very bad algorithm.
- // Right now we insert the items from 'map' using the default iterator,
- // which gives us the objects ordered, leading to an unbalanced tree.
- // This could be fixed by switching to a red black tree, or by using a
- // different walk order (infix comes to mind).
- if (map.isEmpty())
- return;
- ConstIterator x(map.begin()), e(map.end());
- for (; x != e; ++x) {
- (*this)[x->_key] = x->_value;
- }
+ merge(map._root);
}
ConstIterator begin() const {
@@ -206,7 +205,16 @@
}
protected:
- // Find the node matching the given key, if any
+ /** Merge the content of the given tree into this tree. */
+ void merge(const Node *node) {
+ if (!node)
+ return;
+ (*this)[node->_key] = node->_value;
+ merge(node->_left);
+ merge(node->_right);
+ }
+
+ /** Find and return the node matching the given key, if any. */
Node *findNode(Node *node, const Key &key) const {
while (node && (key != node->_key)) {
if (key < node->_key) {
@@ -218,7 +226,7 @@
return node;
}
- Node *createNode(Node *node, const Key &key) {
+ Node *findOrCreateNode(Node *node, const Key &key) {
Node *prevNode = 0;
bool left = true;
while (node) {
- Previous message: [Scummvm-cvs-logs] CVS: scummvm/bs2 anims.cpp,1.27,1.28 function.cpp,1.24,1.25 sound.cpp,1.24,1.25 sword2.h,1.17,1.18
- Next message: [Scummvm-cvs-logs] CVS: scummvm/common str.cpp,1.23,1.24 str.h,1.15,1.16
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
More information about the Scummvm-git-logs
mailing list