hashtablevec.h

3D游戏开发需要用到BSP树来经行场景渲染的管理。本代码包含完整的BSP及文件生成实现

#pragma once

#include "math.h"
#include "vector.h"
#include "vectoraligned.h"

#define VEC_HASH_SIZE	8
#define VEC_HASH_BASE	(VEC_HASH_SIZE-1)

template <class T>
class CVecHash {
public:
						CVecHash();
						~CVecHash();
	void				Clear();
	int					AddElem(T &p);
	int					GetNum();
	T*					GetElem(int i);
	T*					GetElem(T &p);
	CAlignedVec<T>*		GetData();


protected:
	int					GetPos(T &p);
	int					Hash(T &p);

	CAlignedVec<T>		data;
	CVector<int>		next_data;
	int					hash[VEC_HASH_SIZE];
};

template <class T>
inline CVecHash<T>::CVecHash() {
	for(int i=0; i<VEC_HASH_SIZE; i++)
		hash[i] = -1;
}

template <class T>
inline void CVecHash<T>::Clear() {
	for(int i=0; i<VEC_HASH_SIZE; i++)
		hash[i] = -1;
	data.Clear();
	next_data.Clear();
}


template <class T>
inline CVecHash<T>::~CVecHash() {
	data.Clear();
	next_data.Clear();
}

template <class T>
inline int CVecHash<T>::GetNum() {
	return data.GetNum();
}

template <class T>
inline CAlignedVec<T>* CVecHash<T>::GetData() {
	return &data;
}

template <class T>
inline int CVecHash<T>::Hash(T &p) {
	return p.Hash() & VEC_HASH_BASE;
}

template <class T>
inline int CVecHash<T>::GetPos(T &p) {
	int h = Hash(p);
	int i = hash[h];
	while(i >= 0 && !(data[i] == p))
		i = next_data[i];
	return i;
}

template <class T>
inline T* CVecHash<T>::GetElem(T &p) {
	int i = GetPos(p);

	if(i >= 0)
		return data + i;
	else
		return NULL;
}

template <class T>
inline int CVecHash<T>::AddElem(T &p) {
	int h = Hash(p);
	int i = hash[h];
	while(i >= 0 && !(data[i] == p))
		i = next_data[i];

	if(i >= 0)
		return i;

	int cur_pos = data.Append(p);
	next_data.Append(hash[h]);
	hash[h] = cur_pos;
	return cur_pos;
}

template <class T>
inline T* CVecHash<T>::GetElem(int i) {
	return data.GetData() + i;
}