map.h

swain-0.5.2.zip的源代码,比较好用,希望大家喜欢.

/*
This file is part of SWAIN (http://sourceforge.net/projects/swain).
Copyright (C) 2006  Daniel Lindstr鰉 and Daniel Nilsson

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.
*/
#pragma once

#include <stdlib.h>

#define INITIAL_SIZE	16

#define SLOT_EMPTY	0
#define SLOT_USED	1
#define SLOT_DELETED	2

template <class T>
class Map {
private:
	char *slots;
	int *keys;
	T *vals;
	int size;
	int count;
	T nullItem;

	void allocateTable(int sz);
	void growTable(void);
	int findBucket(int key, bool deletedOk);
public:
	Map(T null);
	~Map(void);

	T put(int key, T val);
	T get(int key);
	bool hasKey(int key);
	T remove(int key);
	bool findKey(int *key, T val);
};

template <class T>
Map<T>::Map(T null) {
	nullItem = null;
	count = 0;
	allocateTable(INITIAL_SIZE);
}

template <class T>
Map<T>::~Map(void) {
	delete slots;
	delete keys;
	delete vals;
}

template <class T>
void Map<T>::allocateTable(int sz) {
	size = sz;
	slots = new char[size];
	keys = new int[size];
	vals = new T[size];
	for (int i = 0; i < size; i++) {
		slots[i] = SLOT_EMPTY;
		keys[i] = -1;
		vals[i] = nullItem;
	}
}

template <class T>
void Map<T>::growTable(void) {
	char *oldSlots = slots;
	int *oldKeys = keys;
	T *oldVals = vals;
	int oldSize = size;
	int i;

	allocateTable(size * 2);
	// Rehash...
	for (i = 0; i < oldSize; i++) {
		if (oldSlots[i] == SLOT_USED) {
			put(oldKeys[i], oldVals[i]);
		}
	}
	delete oldSlots;
	delete oldKeys;
	delete oldVals;
}

template <class T>
int Map<T>::findBucket(int key, bool deletedOk) {
	int hash = key % size;
	while ((slots[hash] == SLOT_USED && keys[hash] != key) ||
		   (slots[hash] == SLOT_DELETED && !deletedOk)) {
		hash = (hash + 1) % size;
	}
	return hash;
}

template <class T>
T Map<T>::put(int key, T val) {
	T old = nullItem;
	int i = findBucket(key, true);
	if (slots[i] == SLOT_USED) {	// Replace an existing item
		old = vals[i];
		vals[i] = val;
	} else if (slots[i] == SLOT_DELETED) { // Replace a deleted item
		slots[i] = SLOT_USED;
		keys[i] = key;
		vals[i] = val;
	} else if (count < size/2) {	// Insert a new item without resizing
		old = nullItem;
		slots[i] = SLOT_USED;
		keys[i] = key;
		vals[i] = val;
		count++;
	} else {						// Insert a new item but resize first
		growTable();
		i = findBucket(key, true);		// May be another bucket in the larger table
		old = nullItem;
		slots[i] = SLOT_USED;
		keys[i] = key;
		vals[i] = val;
		count++;
	}
	return old;
}

template <class T>
T Map<T>::get(int key) {
	int i = findBucket(key, false);
	if (slots[i] == SLOT_USED) {
		return vals[i];
	} else {
		return nullItem;
	}
}

template <class T>
bool Map<T>::hasKey(int key) {
	int i = findBucket(key, false);
	return slots[i] == SLOT_USED;
}

template <class T>
T Map<T>::remove(int key) {
	int i = findBucket(key, false);
	T val;
	if (slots[i] == SLOT_USED) {
		val = vals[i];
		slots[i] = SLOT_DELETED;
		keys[i] = -1;
		vals[i] = nullItem;
		return val;
	} else {
		return nullItem;
	}
}

template <class T>
bool Map<T>::findKey(int *key, T val) {
	int i;
	for (i = 0; i < size; i++) {
		if (slots[i] == SLOT_USED && vals[i] == val) {
			*key = keys[i];
			return true;
		}
	}
	return false;
}