gmap.imp

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/base/gmap.imp,v $
// $Date: 2002/08/26 05:49:57 $
// $Revision: 1.3 $
//
// DESCRIPTION:
// Implementation 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.
//

#include <assert.h>
#include <string.h>

#include "base/gmap.h"

//-------------------------------------------------------------------------
//                    gBaseMap<K, T> member functions
//-------------------------------------------------------------------------

template <class K, class T> gBaseMap<K, T>::gBaseMap(const T &d)
  : length(0), _default(d), keys(0), values(0)
{ }

template <class K, class T>
gBaseMap<K, T>::gBaseMap(const gBaseMap<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> gBaseMap<K, T>::~gBaseMap()
{
  delete [] keys;
  delete [] values;
}

template <class K, class T>
int gBaseMap<K, T>::operator==(const gBaseMap<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 gBaseMap<K, T>::operator!=(const gBaseMap<K, T> &M) const
{
  return !(*this == M);
}

template <class K, class T>
gBaseMap<K, T> &gBaseMap<K, T>::operator=(const gBaseMap<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 &gBaseMap<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 gBaseMap<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 &gBaseMap<K, T>::Default(void)
{
  return _default;
}

template <class K, class T> const T &gBaseMap<K, T>::Default(void) const
{
  return _default;
}

template <class K, class T> int gBaseMap<K, T>::Length(void) const
{
  return length;
}

template <class K, class T> void gBaseMap<K, T>::Dump(gOutput &f) const
{
  for (int i = 0; i < length; i++)
    f << keys[i] << " --> " << values[i] << '\n';
}

//-------------------------------------------------------------------------
//                      gOrdMap<K, T> member functions
//-------------------------------------------------------------------------

template <class K, class T> gOrdMap<K, T>::gOrdMap(const T &d)
  : gBaseMap<K, T>(d)
{ }

template <class K, class T> gOrdMap<K, T>::gOrdMap(const gOrdMap<K, T> &m)
  : gBaseMap<K, T>(m)
{ }

template <class K, class T> gOrdMap<K, T>::~gOrdMap()   { }

template <class K, class T>
int gOrdMap<K, T>::Locate(const K &key) const
{
  int low = 0, high = length - 1, mid = 0;
  
  while (low <= high)   {
    mid = (low + high) / 2;
    if (key < keys[mid])     high = mid - 1;
    else if (key > keys[mid])    low = mid + 1;
    else    return mid;
  }

  return mid;
}


template <class K, class T> T &gOrdMap<K, T>::operator()(const K &key)
{
  int where = Locate(key);

  if (length > 0 && keys[where] == key)    return values[where];
  else return Insert(key, ((key < keys[where]) ? where : where + 1),
		    _default);
}

template <class K, class T> T &gOrdMap<K, T>::Lookup(const K &key)
{
  int where = Locate(key);

  if (length > 0 && keys[where] == key)    return values[where];
  else return Insert(key, ((key < keys[where]) ? where : where + 1),
		     _default);
}

template <class K, class T> T gOrdMap<K, T>::operator()(const K &key) const
{
  int where = Locate(key);

  if (length > 0 && keys[where] == key)    return values[where];
  else   return _default;
}

template <class K, class T> int gOrdMap<K, T>::IsDefined(const K &key) const
{
  if (length == 0)   return 0;
  return (keys[Locate(key)] == key);
}

template <class K, class T>
void gOrdMap<K, T>::Define(const K &key, const T &value)
{
  if (length == 0)  {
    Insert(key, 0, value);
    return;
  }

  int where = Locate(key);

  if (keys[where] == key)   values[where] = value;
  else Insert(key, ((key < keys[where]) ? where : where + 1), value);
}

template <class K, class T> T gOrdMap<K, T>::Remove(const K &key)
{
  int where = Locate(key);

  if (where >= 0)    return Delete(where);
  return _default;
}