Index: trunk/ab5.0/jenga/include/common/Hashmap.h
===================================================================
--- trunk/ab5.0/jenga/include/common/Hashmap.h	(revision 639)
+++ trunk/ab5.0/jenga/include/common/Hashmap.h	(revision 828)
@@ -1,2 +1,11 @@
+#include <stdexcept>
+#include <unordered_set>
+#include <boost/range/algorithm.hpp>
+#include <boost/checked_delete.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/cast.hpp>
+#include <boost/serialization/serialization.hpp>
+#include <boost/serialization/split_member.hpp>
+
 #pragma once
 
@@ -5,24 +14,38 @@
 namespace Common{
 
+template<class T>
+class ObjectInHashmap;
+template<class T>
+struct ObjectInHashmapHash;
+template<class T>
+struct ObjectInHashmapEqualTo;
 
 #define MAX_HASHMAP 65535
-template<class T> class Hashmap
-{
-	T* hashArray[MAX_HASHMAP];
+template<class T> class Hashmap : boost::noncopyable
+{
+	typedef std::unordered_set<ObjectInHashmap<T>*, ObjectInHashmapHash<T>, ObjectInHashmapEqualTo<T>> MapType;
+	MapType map;
+
+	struct downcast
+	{
+		typedef T* result_type;
+		T* operator ()(ObjectInHashmap<T>* p) const
+		{
+			return boost::polymorphic_cast<T*>(p);
+		}
+	};
+	struct const_downcast
+	{
+		typedef T const* result_type;
+		T const* operator ()(ObjectInHashmap<T> const* p) const
+		{
+			return boost::polymorphic_cast<T const*>(p);
+		}
+	};
 
 public:
-	virtual int GetHash( const char *keyName ) const
-	{
-		int key;
-		for(key=0;*keyName!='\0';keyName++){
-			key=((key<<8)+ *keyName )%MAX_HASHMAP;
-		}
-		return key;
-	}
 
 	Hashmap()
-		: isIteratorReady( false )
-	{
-		memset( hashArray, 0, MAX_HASHMAP*sizeof(T*) );
+	{
 	}
 	~Hashmap()
@@ -32,13 +55,6 @@
 	void Clear()
 	{
-		for( int i=0; i<MAX_HASHMAP; i++ )
-		{
-			T* temp = hashArray[i];
-			if( temp )
-			{
-				delete temp;
-			}
-		}
-		memset( hashArray, 0, MAX_HASHMAP*sizeof(T*) );
+		boost::for_each(*this, boost::checked_deleter<T const>());
+		map.clear();
 	}
 
@@ -46,114 +62,52 @@
 	void PullOutAll()
 	{
-		memset( hashArray, 0, MAX_HASHMAP*sizeof(T*) );
-	}
-
-	bool Put( T* value )
-	{
-		int key = GetHash( value->GetKeyName().c_str() );
-
-		if(hashArray[key]){
-			T *temp = hashArray[key];
-			while( true ){
-				if( temp->IsDuplication( value ) )
-				{
-					// 重複している
-					return false;
-				}
-
-				if( temp->GetChainNext() == NULL )
-				{
-					break;
-				}
-				temp = temp->GetChainNext();
-			}
-			temp->SetChainNext( value );
-		}
-		else{
-			hashArray[key] = value;
-		}
-
-		return true;
-	}
-
-	T* GetHashArrayElement( const char *keyName )
-	{
-		return hashArray[GetHash(keyName)];
-	}
-	const T* GetHashArrayElement( const char *keyName ) const
-	{
-		return hashArray[GetHash(keyName)];
-	}
-
-	bool IsExistDuplicationKeyName( const std::string &keyName ) const
-	{
-		int key = GetHash( keyName.c_str() );
-
-		if(hashArray[key]){
-			const T *temp = hashArray[key];
-			while( true ){
-				if( temp->IsDuplication( keyName ) )
-				{
-					// 重複している
-					return true;
-				}
-
-				if( temp->GetChainNext() == NULL )
-				{
-					break;
-				}
-				temp = temp->GetChainNext();
-			}
-		}
-
-		return false;
+		map.clear();
+	}
+
+	bool Put(T* value)
+	{
+		if (value == nullptr)
+		{
+			throw std::invalid_argument("Hashmap::Put");
+		}
+		return map.insert(value).second;
+	}
+
+	typedef boost::transform_iterator<downcast, typename MapType::local_iterator> local_iterator;
+	typedef boost::transform_iterator<const_downcast, typename MapType::const_local_iterator> const_local_iterator;
+
+	boost::iterator_range<local_iterator> GetHashArrayElement(std::string const& keyName)
+	{
+		ObjectInHashmapDummy<T> t(keyName);
+		return boost::iterator_range<local_iterator>(
+			local_iterator(map.begin(map.bucket(&t)), downcast()),
+			local_iterator(map.end(map.bucket(&t)), downcast()));
+	}
+
+	boost::iterator_range<const_local_iterator> GetHashArrayElement(std::string const& keyName) const
+	{
+		ObjectInHashmapDummy<T> t(keyName);
+		return boost::iterator_range<const_local_iterator>(
+			const_local_iterator(map.begin(map.bucket(&t)), const_downcast()),
+			const_local_iterator(map.end(map.bucket(&t)), const_downcast()));
+	}
+
+	bool IsExistDuplicationKeyName(const std::string &keyName) const
+	{
+		ObjectInHashmapDummy<T> t(keyName);
+		return map.find(&t) != map.end();
 	}
 
 	bool IsExist( const T* value ) const
 	{
-		int key = GetHash( value->GetKeyName().c_str() );
-
-		if(hashArray[key]){
-			const T *temp = hashArray[key];
-			while( true ){
-				if( temp->IsDuplication( value ) )
-				{
-					// 重複している
-					return true;
-				}
-
-				if( temp->GetChainNext() == NULL )
-				{
-					break;
-				}
-				temp = temp->GetChainNext();
-			}
-		}
-
-		return false;
-	}
-
-	const T *FindLike( const T* value ) const
-	{
-		int key = GetHash( value->GetKeyName().c_str() );
-
-		if(hashArray[key]){
-			const T *temp = hashArray[key];
-			while( true ){
-				if( temp->IsDuplication( value ) )
-				{
-					// 重複している
-					return temp;
-				}
-
-				if( temp->GetChainNext() == NULL )
-				{
-					break;
-				}
-				temp = temp->GetChainNext();
-			}
-		}
-
-		return NULL;
+		return map.find(const_cast<T*>(value)) != map.end();
+	}
+
+	const T *FindLike( const ObjectInHashmap<T>* value ) const
+	{
+		auto it = map.find(const_cast<ObjectInHashmap<T>*>(value));
+		return it != map.end()
+			? boost::polymorphic_downcast<T const*>(*it)
+			: nullptr;
 	}
 
@@ -162,49 +116,25 @@
 	// イテレータ
 	/////////////////////////////////////////////////////////////////
-private:
-	mutable std::vector<T*> iterator_Objects;
-	mutable int iterator_CurrentNext;
-	mutable bool isIteratorReady;
-public:
-	void Iterator_Init() const
-	{
-		iterator_Objects.clear();
-		iterator_CurrentNext = 0;
-
-		for( int i=0; i<MAX_HASHMAP; i++ ){
-			if( hashArray[i] ){
-				T* temp = hashArray[i];
-				while( temp )
-				{
-					iterator_Objects.push_back( temp );
-
-					temp = (T*)temp->GetChainNext();
-				}
-			}
-		}
-
-		isIteratorReady = true;
-	}
-	void Iterator_Reset() const
-	{
-		if( !isIteratorReady )
-		{
-			Jenga::Throw( "イテレータの準備ができていない" );
-		}
-		iterator_CurrentNext = 0;
-	}
-	bool Iterator_HasNext() const
-	{
-		return ( iterator_CurrentNext < (int)iterator_Objects.size() );
-	}
-	T *Iterator_GetNext() const
-	{
-		return iterator_Objects[iterator_CurrentNext++];
-	}
-	int Iterator_GetMaxCount() const
-	{
-		return (int)iterator_Objects.size();
-	}
-
+	//typedef boost::transform_iterator<downcast, typename MapType::iterator> iterator;
+	typedef boost::transform_iterator<downcast, typename MapType::const_iterator> const_iterator;
+	typedef const_iterator iterator;
+	typedef typename MapType::size_type size_type;
+	typedef typename MapType::difference_type difference_type;
+	//iterator begin()
+	//{
+	//	return iterator(map.begin(), downcast());
+	//}
+	//iterator end()
+	//{
+	//	return iterator(map.end(), downcast());
+	//}
+	const_iterator begin() const
+	{
+		return const_iterator(map.begin(), downcast());
+	}
+	const_iterator end() const
+	{
+		return const_iterator(map.end(), downcast());
+	}
 
 	// XMLシリアライズ用
@@ -215,46 +145,27 @@
 	{
 		std::vector<T *> objects;
-		ar & BOOST_SERIALIZATION_NVP( objects );
-
-		// 読み込み後の処理
+		ar & BOOST_SERIALIZATION_NVP(objects);
 		Clear();
-		BOOST_FOREACH( T *object, objects )
-		{
-			Put( object );
-		}
-		Iterator_Init();
+		map = boost::copy_range<MapType>(objects);
 	}
 	template<class Archive> void save(Archive& ar, const unsigned int version) const
 	{
-		// 保存準備
-		std::vector<T *> objects;
-		objects.clear();
-		Iterator_Reset();
-		while( Iterator_HasNext() )
-		{
-			objects.push_back( Iterator_GetNext() );
-		}
-
-		ar & BOOST_SERIALIZATION_NVP( objects );
-	}
-};
-
-template<class T> class ObjectInHashmap
-{
-	T *pNextObject;
+		std::vector<T *> objects(begin(), end());
+		ar & BOOST_SERIALIZATION_NVP(objects);
+	}
+};
+
+template<class T>
+class ObjectInHashmap
+{
+protected:
+	ObjectInHashmap()
+	{
+	}
+	~ObjectInHashmap()
+	{
+	}
+
 public:
-
-	ObjectInHashmap()
-		: pNextObject( NULL )
-	{
-	}
-	~ObjectInHashmap()
-	{
-		if( pNextObject )
-		{
-			delete pNextObject;
-		}
-	}
-
 	virtual const std::string &GetKeyName() const = 0;
 	virtual bool IsDuplication( const T *value ) const
@@ -266,16 +177,54 @@
 		return ( GetKeyName() == keyName );
 	}
-
-	T *GetChainNext()
-	{
-		return pNextObject;
-	}
-	const T *GetChainNext() const
-	{
-		return pNextObject;
-	}
-	void SetChainNext( T *pNextObject )
-	{
-		this->pNextObject = pNextObject;
+};
+
+template<class T>
+struct ObjectInHashmapHash
+{
+	typedef std::size_t result_type;
+	std::size_t operator ()(ObjectInHashmap<T> const* x) const
+	{
+		return std::hash<std::string>()(x->GetKeyName());
+	}
+};
+
+// GetHashArrayElementなどで文字列から検索するために用いる。
+template<class T>
+class ObjectInHashmapDummy : public ObjectInHashmap<T>, boost::noncopyable
+{
+public:
+	explicit ObjectInHashmapDummy(std::string const& s) : str(s) {}
+
+	virtual std::string const& GetKeyName() const override
+	{
+		return str;
+	}
+
+	virtual bool IsDuplication(T const* value) const override
+	{
+		return value != nullptr
+			&& value->ObjectInHashmap<T>::IsDuplication(str);
+	}
+
+private:
+	std::string const& str;
+};
+
+template<class T>
+struct ObjectInHashmapEqualTo
+{
+	typedef bool result_type;
+	bool operator ()(_In_ ObjectInHashmap<T> const* lhs, _In_ ObjectInHashmap<T> const* rhs) const
+	{
+		assert(lhs != nullptr);
+		assert(rhs != nullptr);
+		if (auto pl = dynamic_cast<T const*>(rhs))
+		{
+			return lhs->IsDuplication(pl);
+		}
+		else
+		{
+			return rhs->IsDuplication(dynamic_cast<T const*>(lhs));
+		}
 	}
 };
