From dc77d02c7e63ab9185870a8c6028ccab9dbbf716 Mon Sep 17 00:00:00 2001 From: Max Horn Date: Sat, 8 Apr 2006 11:38:41 +0000 Subject: Removed common/map.h with the Common::Map template class (it was a very bad implementation, and our HashMap is simply better). svn-id: r21688 --- common/config-file.h | 2 - common/config-manager.h | 3 - common/map.h | 291 ------------------------------------------------ 3 files changed, 296 deletions(-) delete mode 100644 common/map.h (limited to 'common') diff --git a/common/config-file.h b/common/config-file.h index 59f2b5c2f9..a7588a049d 100644 --- a/common/config-file.h +++ b/common/config-file.h @@ -25,7 +25,6 @@ #include "common/config-manager.h" #include "common/list.h" -#include "common/map.h" #include "common/str.h" #include "common/stream.h" @@ -51,7 +50,6 @@ namespace Common { */ class ConfigFile { public: - //typedef Map StringSet; typedef HashMap StringSet; struct KeyValue { diff --git a/common/config-manager.h b/common/config-manager.h index eb06f7493d..8793a35db8 100644 --- a/common/config-manager.h +++ b/common/config-manager.h @@ -26,7 +26,6 @@ #include "common/array.h" //#include "common/config-file.h" -#include "common/map.h" #include "common/hashmap.h" #include "common/singleton.h" #include "common/str.h" @@ -45,7 +44,6 @@ struct IgnoreCase_Hash { uint operator()(const String& x) const { return hashit_lower(x.c_str()); } }; -//typedef Map StringMap; typedef HashMap StringMap; /** @@ -76,7 +74,6 @@ public: bool hasKVComment(const String &key) const; }; - //typedef Map DomainMap; typedef HashMap DomainMap; #if !(defined(PALMOS_ARM) || defined(PALMOS_DEBUG) || defined(__GP32__)) diff --git a/common/map.h b/common/map.h deleted file mode 100644 index 9279a60464..0000000000 --- a/common/map.h +++ /dev/null @@ -1,291 +0,0 @@ -/* ScummVM - Scumm Interpreter - * Copyright (C) 2002-2006 The ScummVM project - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * $URL$ - * $Id$ - */ - -#ifndef COMMON_MAP_H -#define COMMON_MAP_H - -#include "common/scummsys.h" -#include "common/func.h" - -namespace Common { - - -/** - * Template based map (aka dictionary) class which uniquely maps elements of - * class Key to elements of class Value. - * - * @todo This implementation is fairly limited. In particular, the tree is not - * balanced. Ultimately this template should be reimplemented, e.g. using - * a red-black tree. Or if one day using Std C++ lib becomes acceptable, - * we can use that. - * @todo Having unit tests for this class would be very desirable. There are a - * big number of things which can go wrong in this code. - */ -template > -class Map { -protected: - struct BaseNode { - Key _key; - Value _value; - BaseNode() {} - BaseNode(const Key &key) : _key(key) {} - }; - struct Node : BaseNode { - Node *_parent; - Node *_left, *_right; - Node() : _parent(0), _left(0), _right(0) {} - Node(const Key &key, Node *parent) : BaseNode(key), _parent(parent), _left(0), _right(0) {} - }; - - Node *_root; - Node *_header; - - Comparator _cmp; - - uint _size; - -private: - Map(const Map &map); - Map &operator =(const Map &map); - -public: - class const_iterator { - friend class Map; - protected: - Node *_node; - const_iterator(Node *node) : _node(node) {} - - public: - const_iterator() : _node(0) {} - - const BaseNode &operator *() const { assert(_node != 0); return *_node; } - const BaseNode *operator->() const { assert(_node != 0); return _node; } - bool operator ==(const const_iterator &iter) const { return _node == iter._node; } - bool operator !=(const const_iterator &iter) const { return !(*this == iter); } - const_iterator operator ++() { - if (!_node) - return *this; - if (_node->_right) { - _node = _node->_right; - while (_node->_left) - _node = _node->_left; - } else { - Node *parent = _node->_parent; - while (_node == parent->_right) { - _node = parent; - parent = _node->_parent; - } - - if (_node->_right != parent) - _node = parent; - } - - if (_node->_parent == 0) - _node = 0; - - return *this; - } - }; - -public: - Map() : _root(0), _size(0) { - _header = new Node(); - _header->_right = _header->_left = _header; - } - -#ifndef __SYMBIAN32__ - virtual ~Map() -#else - ~Map() -#endif - { - clearNodes(_root); - delete _header; - _root = _header = 0; - _size = 0; - } - - /* - * Return the object for the given key. If no match is found, a new entry - * with the given key and the default data value is inserted. - */ - Value &operator [](const Key &key) { - Node *node; - if (!_root) { - node = _root = new Node(key, _header); - _size++; - } else { - node = findOrCreateNode(_root, key); - } - return node->_value; - } - - const Value &operator [](const Key &key) const { - Node *node = findNode(_root, key); - assert(node != 0); - return node->_value; - } - - bool contains(const Key &key) const { - return (findNode(_root, key) != 0); - } - - void clear() { - clearNodes(_root); - _root = 0; - _size = 0; - } - - bool empty() const { - return (_root == 0); - } - - uint size() const { return _size; } - - size_t erase(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 - // from one of our maps if you need to be efficient :-) - Node *node = findNode(_root, key); - if (!node) - return 0; // key wasn't present, so no work has to be done - - // Now we have to remove 'node'. There are two simple cases and one hard. - Node *parent = node->_parent; - Node *rep; - if (!node->_left) { - rep = node->_right; - } else if (!node->_right) { - rep = node->_left; - } else { - // We have to do it the hard way since both children are present. - Node *n2; - - n2 = rep = node->_right; - - // Now insert the left child leftmost into our right child - while (n2->_left) - n2 = n2->_left; - n2->_left = node->_left; - n2->_left->_parent = n2; - } - - // Replace this node with node 'rep' - if (rep) - rep->_parent = parent; - if (parent == _header) // Root node? - _root = rep; - else if (parent->_left == node) - parent->_left = rep; - else - parent->_right = rep; - - // Finally free the allocated memory - delete node; - - return 1; - } - - void merge(const Map &map) { - merge(map._root); - } - - const_iterator begin() const { - Node *node = _root; - if (node) { - while (node->_left) - node = node->_left; - } - return const_iterator(node); - } - - const_iterator end() const { - return const_iterator(); - } - - const_iterator find(const Key &key) const { - Node *node = findNode(_root, key); - if (node) - return const_iterator(node); - return end(); - } - - -protected: - /** 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) { - if (_cmp(key, node->_key)) - node = node->_left; - else if (_cmp(node->_key, key)) - node = node->_right; - else - return node; - } - return 0; - } - - Node *findOrCreateNode(Node *node, const Key &key) { - Node *prevNode = 0; - bool left = true; - while (node) { - prevNode = node; - if (_cmp(key, node->_key)) { - left = true; - node = node->_left; - } else if (_cmp(node->_key, key)) { - left = false; - node = node->_right; - } else - return node; - } - node = new Node(key, prevNode); - _size++; - if (left) { - prevNode->_left = node; - } else { - prevNode->_right = node; - } - return node; - } - - void clearNodes(Node *node) { - if (!node) - return; - - clearNodes(node->_left); - clearNodes(node->_right); - delete node; - } -}; - -} // End of namespace Common - -#endif -- cgit v1.2.3