//
// $Source: /cvsroot/gambit/gambit/sources/libgambit/map.h,v $
// $Date: 2006/01/07 06:37:06 $
// $Revision: 1.1 $
//
// DESCRIPTION:
// Declaration of map container types
//
// This file is part of Gambit
// Copyright (c) 2002, The Gambit 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//
#ifndef LIBGAMBIT_MAP_H
#define LIBGAMBIT_MAP_H
namespace Gambit {
template <class K, class T> class MapBase {
protected:
int length;
T _default;
K *keys;
T *values;
//
// Insert a new key-value pair at a location in the arrays.
//
T &Insert(const K &key, int where, const T &value);
//
// Remove the key-value pair at a location in the arrays, and return the
// value which was removed.
//
T Delete(int where);
public:
//
// This is the basic map constructor. It initializes the map to be the
// empty map with no relations defined.
//
MapBase(const T &d);
//
// Construct a map to have the same set of relations as another map.
//
MapBase(const MapBase<K, T> &);
//
// This is the map destructor. It deletes all allocated memory, and calls
// the destructors for the keys and values which remain in the map at the
// time of its deallocation.
//
virtual ~MapBase();
//
// These implement the mapping function which maps a key to a value. If
// the map from a key to a value is not defined, a mapping will be defined
// from the key to the default value. The IsDefined() member can be used
// to determine whether a mapping is defined.
//
// <note> If the mapping is not defined for the key in the const map case,
// the mapping returns the default value and no entry is created in
// the map for that key.
//+grp
virtual T &operator()(const K &key) = 0;
virtual T operator()(const K &key) const = 0;
//-grp
virtual T &Lookup(const K &key) = 0;
//
// These are the equality and assignment operators for this and all derived
// classes.
//+grp
int operator==(const MapBase &M) const;
int operator!=(const MapBase &M) const;
MapBase<K, T> &operator=(const MapBase &M);
//-grp
//
// Returns the default value for the map
//+grp
T &Default(void);
const T &Default(void) const;
//-grp
//
// Returns the number of mappings defined in the map
//
int Length(void) const;
//
// Returns nonzero if the key has a mapping defined in the map
//
virtual int IsDefined(const K &key) const = 0;
//
// These member functions implement adding and removing mapping from the map
//+grp
virtual void Define(const K &key, const T &value) = 0;
virtual T Remove(const K &key) = 0;
//-grp
};
//
// <category lib=glib sect=Containers>
//
// The Map is an ordered map. That is, the index class has all the
// usual ordering operators defined upon it (==, !=, <, <=, >, >=). These
// are used to sort the map by keys, thus making search-type operations
// logarithmic instead of linear. This is a particularly large improvement
// when using keys which are costly to compare
//
template <class K, class T> class Map : public MapBase<K, T> {
private:
int Locate(const K &key) const;
public:
//
// Construct an ordered map with no mappings and the given default value.
//
Map(const T &d);
//
// Construct an ordered map with the same key-value mappings as another
// ordered map.
//
Map(const Map<K, T> &m);
virtual ~Map();
//
// These implement the mapping function which maps a key to a value. If
// the map from a key to a value is not defined, a mapping will be defined
// from the key to the default value. The IsDefined() member can be used
// to determine whether a mapping is defined.
//
// <note> If the mapping is not defined for the key in the const map case,
// the mapping returns the default value and no entry is created in
// the map for that key.
//+grp
T &operator()(const K &key);
T operator()(const K &key) const;
//-grp
T &Lookup(const K &key);
//
// Return nonzero exactly when the key has a defined mapping in the map
//
int IsDefined(const K &key) const;
//
// Define a new key-value relation. If the key already exists in the map,
// the new value overwrites the old value; otherwise, a new relation is
// created.
//
void Define(const K &key, const T &value);
//
// Remove the mapping for a key from the relation, and return the value
// to which the key was formerly mapped. If the key does not have a defined
// mapping, has no effect on the contents of the map, and returns the
//
T Remove(const K &key);
};
//-------------------------------------------------------------------------
// MapBase<K, T> member functions
//-------------------------------------------------------------------------
template <class K, class T> MapBase<K, T>::MapBase(const T &d)
: length(0), _default(d), keys(0), values(0)
{ }
template <class K, class T>
MapBase<K, T>::MapBase(const MapBase<K, T> &m)
: length(m.length), _default(m._default)
{
keys = new K[length];
values = new T[length];
for (int i = 0; i < length; i++) {
keys[i] = m.keys[i];
values[i] = m.values[i];
}
}
template <class K, class T> MapBase<K, T>::~MapBase()
{
delete [] keys;
delete [] values;
}
template <class K, class T>
int MapBase<K, T>::operator==(const MapBase<K,T> &M) const
{
if (length != M.length) return 0;
for (int i = 0; i < length; i++)
if (keys[i] != M.keys[i] || values[i] != M.values[i]) return 0;
return (_default == M._default);
}
template <class K, class T>
int MapBase<K, T>::operator!=(const MapBase<K, T> &M) const
{
return !(*this == M);
}
template <class K, class T>
MapBase<K, T> &MapBase<K, T>::operator=(const MapBase<K,T> &M)
{
if (this != &M) {
length = M.length;
if (keys) delete [] keys;
if (values) delete [] values;
if (M.length) {
keys = new K[M.length];
values = new T[M.length];
for (int i = 0; i < length; i++) {
keys[i] = M.keys[i];
values[i] = M.values[i];
}
}
else {
keys = 0;
values = 0;
}
_default = M._default;
}
return *this;
}
template <class K, class T>
T &MapBase<K, T>::Insert(const K &key, int entry, const T &value)
{
K *new_keys = new K[length + 1];
T *new_values = new T[length + 1];
if (length > 0) {
int i;
for (i = 0; i < entry; i++) {
new_keys[i] = keys[i];
new_values[i] = values[i];
}
for (i++; i <= length; i++) {
new_keys[i] = keys[i - 1];
new_values[i] = values[i - 1];
}
}
new_keys[entry] = key;
new_values[entry] = value;
if (length > 0) {
delete [] keys;
delete [] values;
}
keys = new_keys;
values = new_values;
length++;
return values[entry];
}
template <class K, class T> T MapBase<K, T>::Delete(int where)
{
if (length == 1) {
T ret = values[0];
delete [] keys;
delete [] values;
keys = 0;
values = 0;
length = 0;
return ret;
}
T ret = values[where];
K *new_keys = new K[length - 1];
T *new_values = new T[length - 1];
int i;
for (i = 0; i < where; i++) {
new_keys[i] = keys[i];
new_values[i] = values[i];
}
for (i++; i < length; i++) {
new_keys[i - 1] = keys[i];
new_values[i - 1] = values[i];
}
delete [] keys;
delete [] values;
keys = new_keys;
values = new_values;
length--;
return ret;
}
template <class K, class T> T &MapBase<K, T>::Default(void)
{
return _default;
}
template <class K, class T> const T &MapBase<K, T>::Default(void) const
{
return _default;
}
template <class K, class T> int MapBase<K, T>::Length(void) const
{
return length;
}
//-------------------------------------------------------------------------
// Map<K, T> member functions
//-------------------------------------------------------------------------
template <class K, class T> Map<K, T>::Map(const T &d)
: MapBase<K, T>(d)
{ }
template <class K, class T> Map<K, T>::Map(const Map<K, T> &m)
: MapBase<K, T>(m)
{ }
template <class K, class T> Map<K, T>::~Map() { }
template <class K, class T>
int Map<K, T>::Locate(const K &key) const
{
int low = 0, high = this->length - 1, mid = 0;
while (low <= high) {
mid = (low + high) / 2;
if (key < this->keys[mid]) high = mid - 1;
else if (key > this->keys[mid]) low = mid + 1;
else return mid;
}
return mid;
}
template <class K, class T> T &Map<K, T>::operator()(const K &key)
{
int where = Locate(key);
if (this->length > 0 && this->keys[where] == key) return this->values[where];
else return Insert(key, ((key < this->keys[where]) ? where : where + 1),
this->_default);
}
template <class K, class T> T &Map<K, T>::Lookup(const K &key)
{
int where = Locate(key);
if (this->length > 0 && this->keys[where] == key) return this->values[where];
else return Insert(key, ((key < this->keys[where]) ? where : where + 1),
this->_default);
}
template <class K, class T> T Map<K, T>::operator()(const K &key) const
{
int where = Locate(key);
if (this->length > 0 && this->keys[where] == key) return this->values[where];
else return this->_default;
}
template <class K, class T> int Map<K, T>::IsDefined(const K &key) const
{
if (this->length == 0) return 0;
return (this->keys[Locate(key)] == key);
}
template <class K, class T>
void Map<K, T>::Define(const K &key, const T &value)
{
if (this->length == 0) {
Insert(key, 0, value);
return;
}
int where = Locate(key);
if (this->keys[where] == key) this->values[where] = value;
else Insert(key, ((key < this->keys[where]) ? where : where + 1), value);
}
template <class K, class T> T Map<K, T>::Remove(const K &key)
{
int where = Locate(key);
if (where >= 0) return this->Delete(where);
return this->_default;
}
} // end namespace Gambit
#endif // LIBGAMBIT_MAP_H
syntax highlighted by Code2HTML, v. 0.9.1