(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.

11 files changed, 1576 insertions, 0 deletions

diff --git a/yapf/unittest/test_autocopyptr.h b/yapf/unittest/test_autocopyptr.h
new file mode 100644
index 000000000..a08d84a59
--- /dev/null
+++ b/yapf/unittest/test_autocopyptr.h
@@ -0,0 +1,43 @@
+/* $Id$ */
+
+struct CData
+{
+	int val;
+
+	FORCEINLINE CData() : val(0)                       {NumInstances()++; /*DBG("DCata::ctor()\n");*/}
+	FORCEINLINE CData(const CData& src) : val(src.val) {NumInstances()++; /*DBG("DCata::ctor(%d)\n", val);*/}
+	FORCEINLINE ~CData()                               {NumInstances()--; /*DBG("DCata::dtor(%d)\n", val);*/}
+
+	FORCEINLINE bool operator < (const CData& other) const {return (val < other.val);}
+
+	FORCEINLINE static int& NumInstances() { static int num_instances = 0; return num_instances; };
+
+};
+
+typedef CAutoCopyPtrT<CData> PData;
+
+static int TestAutoCopyPtr(bool silent)
+{
+	int res = 0;
+	{
+		PData p1, p3;
+		p1->val = 4;
+		PData p2; p2 = p1;
+		p2->val = 6;
+		DBG("\n%d, %d", p1->val, p2->val);
+		CHECK_INT(0, p1->val, 4);
+		CHECK_INT(1, p2->val, 6);
+
+		p2 = p1;
+		p3 = p1;
+		p2->val = 7;
+		DBG("\n%d, %d", p1->val, p2->val);
+		CHECK_INT(2, p3->val, 4);
+		CHECK_INT(3, p2->val, 7);
+
+		CHECK_INT(4, CData::NumInstances(), 3);
+	}
+	CHECK_INT(5, CData::NumInstances(), 0);
+	return res;
+}
+
diff --git a/yapf/unittest/test_binaryheap.h b/yapf/unittest/test_binaryheap.h
new file mode 100644
index 000000000..f0ba44749
--- /dev/null
+++ b/yapf/unittest/test_binaryheap.h
@@ -0,0 +1,103 @@
+/* $Id$ */
+
+// this test uses CData structure defined in test_autocopyptr.h
+
+static int TestBinaryHeap1(bool silent)
+{
+	CData::NumInstances() = 0;
+	int res = 0;
+	{
+		const int max_items = 10000;
+		const int total_adds = 1000000;
+		CBinaryHeapT<CData> bh(max_items);
+		CFixedSizeArrayT<CData, max_items> data;
+
+
+		DBG("\nFilling BinaryHeap with %d items...", max_items);
+		CHECK_INT(0, bh.Size(), 0);
+		CHECK_INT(1, CData::NumInstances(), 0);
+		int i = 0;
+		for (; i < max_items; i++) {
+			CData& d = data.Add();
+			d.val = rand() & 0xFFFF;
+			bh.Push(d);
+		}
+		CHECK_INT(2, bh.Size(), max_items);
+		CHECK_INT(3, CData::NumInstances(), max_items);
+
+
+		DBG("\nShaking items %d times...", total_adds);
+		int num_last = bh.GetHead().val;
+		for (i = 0; i < total_adds; i++) {
+			CData& d = bh.PopHead();
+			//printf("\nd->val = %d, num_last = %d", d->val, num_last);
+			CHECK_INT(4, d.val < num_last, 0);
+			if(d.val < num_last) {
+				printf("Sort error @ item %d", i);
+			}
+			num_last = d.val;
+			d.val += rand() & 0xFFFF;
+			bh.Push(d);
+		}
+
+
+		DBG("\nDone!");
+		CHECK_INT(5, bh.Size(), max_items);
+		CHECK_INT(6, CData::NumInstances(), max_items);
+	}
+	CHECK_INT(7, CData::NumInstances(), 0);
+	return res;
+}
+
+
+
+// this test uses CData and PData structures defined in test_autocopyptr.h
+
+static int TestBinaryHeap2(bool silent)
+{
+	CData::NumInstances() = 0;
+	int res = 0;
+	{
+		const int max_items = 10000;
+		const int total_adds = 1000000;
+		CBinaryHeapT<CData> bh(max_items);
+		CFixedSizeArrayT<CData, max_items> data;
+
+
+		DBG("\nFilling BinaryHeap with %d items...", max_items);
+		CHECK_INT(0, bh.Size(), 0);
+		CHECK_INT(1, CData::NumInstances(), 0);
+		int i = 0;
+		for (; i < max_items; i++) {
+			CData& d = data.Add();
+			d.val = rand() & 0xFFFF;
+			bh.Push(d);
+		}
+		CHECK_INT(2, bh.Size(), max_items);
+		CHECK_INT(3, CData::NumInstances(), max_items);
+
+
+		DBG("\nShaking items %d times...", total_adds);
+		int num_last = bh.GetHead().val;
+		for (i = 0; i < total_adds; i++) {
+			CData& d = bh.GetHead();
+			bh.RemoveHead();
+			//printf("\nd->val = %d, num_last = %d", d->val, num_last);
+			CHECK_INT(4, d.val < num_last, 0);
+			if(d.val < num_last) {
+				printf("Sort error @ item %d", i);
+			}
+			num_last = d.val;
+			d.val += rand() & 0xFFFF;
+			bh.Push(d);
+		}
+
+
+		DBG("\nDone!");
+		CHECK_INT(5, bh.Size(), max_items);
+		CHECK_INT(6, CData::NumInstances(), max_items);
+	}
+	CHECK_INT(7, CData::NumInstances(), 0);
+	return res;
+}
+
diff --git a/yapf/unittest/test_blob.h b/yapf/unittest/test_blob.h
new file mode 100644
index 000000000..5f266b0f7
--- /dev/null
+++ b/yapf/unittest/test_blob.h
@@ -0,0 +1,61 @@
+/* $Id$ */
+
+static int TestBlob1(bool silent)
+{
+	typedef CBlobT<int64> Blob;
+	int res = 0;
+	{
+		Blob a;
+		Blob b;
+		CHECK_INT(0, a.IsEmpty(), true);
+		CHECK_INT(1, a.Size(), 0);
+
+		const int nItems = 10;
+
+    {
+		  for (int i = 1; i <= nItems; i++) {
+			  a.Append(i);
+			  CHECK_INT(2, a.IsEmpty(), false);
+			  CHECK_INT(3, a.Size(), i);
+		  }
+    }
+
+    {
+		  for (int i = 1; i <= nItems; i++) {
+			  CHECK_INT(4, *a.Data(i - 1), i);
+		  }
+    }
+	}
+	return res;
+}
+
+static int TestBlob2(bool silent)
+{
+	typedef CBlobT<CFsaItem> Blob;
+	int res = 0;
+	{
+		Blob a;
+		Blob b;
+		CHECK_INT(0, a.IsEmpty(), true);
+		CHECK_INT(1, a.Size(), 0);
+
+		const int nItems = 10;
+
+    {
+		  for (int i = 1; i <= nItems; i++) {
+			  a.Append(CFsaItem(i));
+			  CHECK_INT(2, a.IsEmpty(), false);
+			  CHECK_INT(3, a.Size(), i);
+		  }
+    }
+    {
+		  for (int i = 1; i <= nItems; i++) {
+			  CHECK_INT(4, a.Data(i - 1)->i, i);
+		  }
+    }
+		CHECK_INT(15, CFsaItem::NumInstances(), nItems);
+	}
+	CHECK_INT(16, CFsaItem::NumInstances(), 0);
+
+	return res;
+}
diff --git a/yapf/unittest/test_fixedsizearray.h b/yapf/unittest/test_fixedsizearray.h
new file mode 100644
index 000000000..0065a821e
--- /dev/null
+++ b/yapf/unittest/test_fixedsizearray.h
@@ -0,0 +1,114 @@
+/* $Id$ */
+
+struct CFsaItem
+{
+	int i;
+
+	FORCEINLINE static int& NumInstances() { static int num_instances = 0; return num_instances; };
+
+	FORCEINLINE CFsaItem(int i = 0)
+	{
+		this->i = i;
+		NumInstances()++;
+		DBG("(*)");
+	}
+
+	FORCEINLINE CFsaItem(const CFsaItem& src)
+	{
+		this->i = src.i;
+		NumInstances()++;
+		DBG("(c)");
+	}
+
+	FORCEINLINE ~CFsaItem()
+	{
+		NumInstances()--;
+		DBG("(-)");
+	}
+};
+
+typedef CFixedSizeArrayT<CFsaItem, 4> CSubArray;
+typedef CFixedSizeArrayT<CSubArray, 4> CSuperArray;
+
+static int TestFixedSizeArray(bool silent)
+{
+	int res = 0;
+	{
+		CSuperArray a;
+
+		CHECK_INT(0, a.IsFull(), false);
+		CHECK_INT(1, a.IsEmpty(), true);
+
+		CSubArray& b1 = a.Add();
+		b1.Add().i = 1;
+		new(&b1.AddNC())CFsaItem(2);
+
+		CSubArray& b2 = a.Add();
+		new(&b2.AddNC())CFsaItem(3);
+		b2.Add().i = 4;
+
+		CSubArray& b3 = a.AddNC();
+		new(&b3)CSubArray(b1);
+
+		CSubArray& b4 = a.AddNC();
+		new(&b4)CSubArray(b2);
+
+		CHECK_INT(2, a[0][0].i, 1);
+		CHECK_INT(3, b1[1].i, 2);
+		CHECK_INT(4, b1.Size(), 2);
+		CHECK_INT(5, a[3][0].i, 3);
+		CHECK_INT(6, a[3][1].i, 4);
+		CHECK_INT(7, CFsaItem::NumInstances(), 4);
+		CHECK_INT(8, a.IsFull(), true);
+		CHECK_INT(9, a.IsEmpty(), false);
+		CHECK_INT(10, a[3].IsFull(), false);
+		CHECK_INT(11, a[3].IsEmpty(), false);
+	}
+	CHECK_INT(12, CFsaItem::NumInstances(), 0);
+
+	return res;
+}
+
+typedef CArrayT<CFsaItem, 2> CArray;
+
+static int TestArray(bool silent)
+{
+	int res = 0;
+	{
+		CArray a;
+
+		CHECK_INT(0, a.IsFull(), false);
+		CHECK_INT(1, a.IsEmpty(), true);
+
+		CHECK_INT(2, a.Size(), 0);
+
+		a.Add().i = 1;
+		CHECK_INT(3, a.Size(), 1);
+
+		new(&a.AddNC())CFsaItem(2);
+		CHECK_INT(4, a.Size(), 2);
+
+		CHECK_INT(5, a.IsFull(), false);
+		CHECK_INT(6, a.IsEmpty(), false);
+
+		a.Add().i = 3;
+		CHECK_INT(7, a.Size(), 3);
+
+		new(&a.AddNC())CFsaItem(4);
+		CHECK_INT(8, a.Size(), 4);
+
+		CHECK_INT(9, a[0].i, 1);
+		CHECK_INT(10, a[1].i, 2);
+		CHECK_INT(11, a[2].i, 3);
+		CHECK_INT(12, a[3].i, 4);
+
+		CHECK_INT(13, a.IsFull(), true);
+		CHECK_INT(14, a.IsEmpty(), false);
+
+		CHECK_INT(15, CFsaItem::NumInstances(), 4);
+	}
+	CHECK_INT(16, CFsaItem::NumInstances(), 0);
+
+	return res;
+}
+
diff --git a/yapf/unittest/test_hashtable.h b/yapf/unittest/test_hashtable.h
new file mode 100644
index 000000000..230550f2b
--- /dev/null
+++ b/yapf/unittest/test_hashtable.h
@@ -0,0 +1,74 @@
+/* $Id$ */
+
+struct CHashItem1 {
+	struct CKey {
+		int k;
+		FORCEINLINE int CalcHash() const {return k;};
+		FORCEINLINE bool operator == (const CKey& other) const {return (k == other.k);}
+	};
+	typedef CKey Key;
+	CKey  key;
+	int   val;
+	CHashItem1* m_next;
+
+	CHashItem1() : m_next(NULL) {}
+	FORCEINLINE const Key& GetKey() const {return key;}
+	CHashItem1* GetHashNext() {return m_next;}
+	void SetHashNext(CHashItem1* next) {m_next = next;}
+};
+
+static int TestHashTable1(bool silent)
+{
+	typedef CHashItem1 Item;
+	typedef CHashTableT<Item, 12> HashTable1_t;
+	typedef CArrayT<Item, 1024, 16384> Array_t;
+	typedef CHashTableT<Item, 16> HashTable2_t;
+
+	int res = 0;
+	{
+		HashTable1_t ht1;
+		HashTable2_t ht2;
+		Array_t      ar1;
+		Array_t      ar2;
+
+#ifdef _DEBUG
+		static const int nItems = 10000;
+#else
+		static const int nItems = 1000000;
+#endif
+		{
+			srand(0);
+			for (int i = 0; i < nItems; i++) {
+				int r1 = i;
+				int r2 = rand() & 0x0000FFFF | (rand() << 16);
+				Item& I1 = ar1.Add();
+				Item& I2 = ar2.Add();
+				I1.key.k = r1;
+				I2.key.k = r1;
+				I1.val = r2;
+				I2.val = r2;
+				ht1.Push(I1);
+				ht2.Push(I2);
+			}
+		}
+		{
+			srand(0);
+			for (int i = 0; i < nItems; i++) {
+				int r1 = i;
+				int r2 = rand() & 0x0000FFFF | (rand() << 16);
+				HashTable1_t::Tkey k; k.k = r1;
+				Item& i1 = ht1.Find(k);
+				Item& i2 = ht2.Find(k);
+
+				CHECK_INT(0, &i1 != NULL, 1);
+				CHECK_INT(1, &i2 != NULL, 1);
+
+				if (&i1 != NULL) CHECK_INT(2, i1.val, r2);
+				if (&i2 != NULL) CHECK_INT(3, i2.val, r2);
+			}
+		}
+	}
+	return res;
+}
+
+
diff --git a/yapf/unittest/test_yapf.h b/yapf/unittest/test_yapf.h
new file mode 100644
index 000000000..ca4b21de0
--- /dev/null
+++ b/yapf/unittest/test_yapf.h
@@ -0,0 +1,350 @@
+/* $Id$ */
+
+#include "../yapf_base.hpp"
+
+struct CYapfMap1
+{
+	enum {xMax = 32, yMax = 68};
+	static int MapZ(int x, int y)
+	{
+		static const char *z1[yMax] = {
+			"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
+			"A000000000000000000000000000000000000000000000000000000000000000000A",
+			"A000000000000000000000000000000000000000000000000000000000000000000A",
+			"A000000000001000000000000000000000000000000000000000000000000000000A",
+			"A000000000001000000000000000000000000000000000000000000000000000000A",
+			"A000033333333333000000000000000000000000000000000000000000000000000A",
+			"A000030000000000000000000000000000000000000000000000000000000000000A",
+			"A000030000000000000000000000000000000000000000000000000000000000000A",
+			"A000030000000000000000000000000000000000000000000000000000000000000A",
+			"A000030000000000000000000000000000000000000000000000000000000000000A",
+			"A000030000000000000000000000000000000000000000000000000000000000000A",
+			"A210030000000000000000000000000000000000000000000000000000000000000A",
+			"A000000000000000000000000000000000000000000000000000000000000000000A",
+			"A000000000000000000000000000000000000000000000000000000000000000000A",
+			"A000000000000000000000000000000000000000000000000000000000000000000A",
+			"A000000000000000000000000000000000000000000000000000000000000000000A",
+			"A011333323333333233333333333333333333333333333333333333333333000000A",
+			"A000030000000000000000000000000000000000000000000000000000003000000A",
+			"A000030000000000000000000000000000000000000000000000000000003000000A",
+			"A000030000000000000000000000000000000000000000000000000000003000000A",
+			"A210030000000000000000000000000000000000000000000000000000003000000A",
+			"A000030000000000000000000000000000000000000000000000000000003000000A",
+			"A000030000000000000000000000000000000000000000000000000000003000000A",
+			"A000230000000000000000000000000000000000000000000000000000003000000A",
+			"A000030000000000000000000000000000000000000000000000000000003000000A",
+			"A000030000000000000000000000000000000000000000000000000000003000000A",
+			"A000030000000000000000000000000000000000000000000000000000003000000A",
+			"A000000000000000000000000000003333333333333333333333333333333000000A",
+			"A000000000000000000000000000000000000000000000000000000000000000000A",
+			"A000000000000000000000000000000000000000000000000000000000000000000A",
+			"A000000000000000000000000000000000000000000000000000000000000000000A",
+			"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
+		};
+
+		static const char *z2[yMax] = {
+			"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
+			"A000000000000000000000000000000000000000000000000000000000000000000A",
+			"A003333333333333333333333333333333333333333333333333300000000000000A",
+			"A003000000001000000000000000000000000000000000000000300000000000000A",
+			"A003000000001000000000000000000000000000000000000000300000000000000A",
+			"A003333333333333333333333333333333333333300000000000300000000000000A",
+			"A000030000000000000000000000000000000000300000000000300000000000000A",
+			"A000030000000000000000000000000000000000333333333333300000000000000A",
+			"A000030000000000000000000000000000000000300000000000000000000000000A",
+			"A000030000000000000000000000000000000000300000000000000000000000000A",
+			"A000030000000000000000000000000000000000300000000000000000000000000A",
+			"A210030000000000000000000000000000000000300000000000000000000000000A",
+			"A000000000000000000000000000000000000000333300000000000000000000000A",
+			"A000000000000000000000000000000000000000000300000000000000000000000A",
+			"A000000000000000000000000000000000000000000300000000000000000000000A",
+			"A000000000000000000000000000000000000000000300000000000000000000000A",
+			"A012333323333333233333333333333333333333333333333333333333333000000A",
+			"A000030000000000000000000000000000000000000000000000000000003000000A",
+			"A000030000000000000000000000000000000000000000000000000300003000000A",
+			"A000030000000000000000000000000000000000000000000000000300003000000A",
+			"A210030000000000000000000000000000000000000000000000000330003000000A",
+			"A000030000000000000000000000000000000000000000000000000300003000000A",
+			"A000030000000000000000000000000000000000000000000000000300003000000A",
+			"A000230000000000000000000000000000000000000000000000000300003000000A",
+			"A000030000000000000000000000000000000000000000000000000300003000000A",
+			"A000030000000000000000000000000000000000000000000000000300003000000A",
+			"A000030000000000000000000000000000000000000000000000000300003000000A",
+			"A000000000000000000000000000003333333333333333333333333333333000000A",
+			"A000000000000000000000000000000000000000000000000000000000000000000A",
+			"A000000000000000000000000000000000000000000000000000000000000000000A",
+			"A000000000000000000000000000000000000000000000000000000000000000000A",
+			"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
+		};
+
+		static const char **z = z1;
+
+		if (x >= 0 && x < xMax && y >= 0 && y < yMax) {
+			int ret = z[x][y];
+			return ret;
+		}
+		return z[0][0];
+	}
+};
+
+struct CNodeKey1 {
+	int            m_x;
+	int            m_y;
+	Trackdir       m_td;
+	DiagDirection  m_exitdir;
+
+	CNodeKey1() : m_x(0), m_y(0), m_td(INVALID_TRACKDIR) {}
+
+	int CalcHash() const {return m_x | (m_y << 5) | (m_td << 10);}
+	bool operator == (const CNodeKey1& other) const {return (m_x == other.m_x) && (m_y == other.m_y) && (m_td == other.m_td);}
+};
+
+struct CNodeKey2 : public CNodeKey1
+{
+	int CalcHash() const {return m_x | (m_y << 5) | (m_exitdir << 10);}
+	bool operator == (const CNodeKey1& other) const {return (m_x == other.m_x) && (m_y == other.m_y) && (m_exitdir == other.m_exitdir);}
+};
+
+template <class Tkey_>
+struct CTestYapfNodeT {
+	typedef Tkey_ Key;
+	typedef CTestYapfNodeT<Tkey_> Node;
+
+	Tkey_           m_key;
+	CTestYapfNodeT *m_parent;
+	int             m_cost;
+	int             m_estimate;
+	CTestYapfNodeT *m_next;
+
+	CTestYapfNodeT(CTestYapfNodeT* parent = NULL) : m_parent(parent), m_cost(0), m_estimate(0), m_next(NULL) {}
+
+	const Tkey_& GetKey() const {return m_key;}
+	int GetCost() {return m_cost;}
+	int GetCostEstimate() {return m_estimate;}
+	bool operator < (const CTestYapfNodeT& other) const {return m_estimate < other.m_estimate;}
+	CTestYapfNodeT* GetHashNext() {return m_next;}
+	void SetHashNext(CTestYapfNodeT* next) {m_next = next;}
+};
+
+typedef CTestYapfNodeT<CNodeKey1> CYapfNode1;
+typedef CTestYapfNodeT<CNodeKey2> CYapfNode2;
+
+template <class Types>
+struct CYapfTestBaseT
+{
+	typedef typename Types::Tpf Tpf;
+	typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+	typedef typename Node::Key Key;    ///< key to hash tables
+	typedef typename Types::Map Map;
+
+	int m_x1, m_y1;
+	int m_x2, m_y2;
+	Trackdir m_td1;
+
+	CYapfTestBaseT()
+		: m_x1(0), m_y1(0), m_x2(0), m_y2(0), m_td1(INVALID_TRACKDIR)
+	{
+	}
+
+	void Set(int x1, int y1, int x2, int y2, Trackdir td1)
+	{
+		m_x1 = x1;
+		m_y1 = y1;
+		m_x2 = x2;
+		m_y2 = y2;
+		m_td1 = td1;
+	}
+
+	Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+	FORCEINLINE char TransportTypeChar() const {return 'T';}
+
+	FORCEINLINE void PfFollowNode(Node& org)
+	{
+		int x_org = org.m_key.m_x;
+		int y_org = org.m_key.m_y;
+		int z_org = Map::MapZ(x_org, y_org);
+		DiagDirection exitdir = TrackdirToExitdir(org.m_key.m_td);
+
+		TileIndexDiffC diff = TileIndexDiffCByDir(exitdir);
+		int x_new = x_org + diff.x;
+		int y_new = y_org + diff.y;
+		int z_new = Map::MapZ(x_new, y_new);
+
+		int z_diff = z_new - z_org;
+		if (abs(z_diff) > 1) return;
+
+		TrackdirBits trackdirs = DiagdirReachesTrackdirs(exitdir);
+		TrackdirBits trackdirs90 = TrackdirCrossesTrackdirs(org.m_key.m_td);
+		trackdirs &= (TrackdirBits)~(int)trackdirs90;
+
+		while (trackdirs != TRACKDIR_BIT_NONE) {
+			Trackdir td_new = (Trackdir)FindFirstBit2x64(trackdirs);
+			trackdirs = (TrackdirBits)KillFirstBit2x64(trackdirs);
+
+			Node& n = Yapf().CreateNewNode();
+			n.m_key.m_x  =  x_new;
+			n.m_key.m_y  =  y_new;
+			n.m_key.m_td = td_new;
+			n.m_key.m_exitdir = TrackdirToExitdir(n.m_key.m_td);
+			n.m_parent   = &org;
+			Yapf().AddNewNode(n);
+		}
+	}
+
+	FORCEINLINE void PfSetStartupNodes()
+	{
+		Node& n1 = Yapf().CreateNewNode();
+		n1.m_key.m_x = m_x1;
+		n1.m_key.m_y = m_y1;
+		n1.m_key.m_td = m_td1;
+		n1.m_key.m_exitdir = TrackdirToExitdir(n1.m_key.m_td);
+		Yapf().AddStartupNode(n1);
+	}
+
+	FORCEINLINE bool PfCalcCost(Node& n)
+	{
+		// base tile cost depending on distance
+		int c = IsDiagonalTrackdir(n.m_key.m_td) ? 10 : 7;
+		// additional penalty for curve
+		if (n.m_parent != NULL && n.m_key.m_td != n.m_parent->m_key.m_td) c += 3;
+		// z-difference cost
+		int z_new = Map::MapZ(n.m_key.m_x, n.m_key.m_y);
+		int z_old = Map::MapZ(n.m_parent->m_key.m_x, n.m_parent->m_key.m_y);
+		if (z_new > z_old) n.m_cost += (z_new - z_old) * 10;
+		// apply it
+		n.m_cost = n.m_parent->m_cost + c;
+		return true;
+	}
+
+	FORCEINLINE bool PfCalcEstimate(Node& n)
+	{
+		int dx = abs(n.m_key.m_x - m_x2);
+		int dy = abs(n.m_key.m_y - m_y2);
+		int dd = min(dx, dy);
+		int dxy = abs(dx - dy);
+		int d = 14 * dd + 10 * dxy;
+		n.m_estimate = n.m_cost + d /*+ d / 4*/;
+		return true;
+	}
+
+	FORCEINLINE bool PfDetectDestination(Node& n)
+	{
+		bool bDest = (n.m_key.m_x == m_x2) && (n.m_key.m_y == m_y2);
+		return bDest;
+	}
+
+	static int stTestAstar(bool silent)
+	{
+		Tpf pf;
+		pf.Set(3, 3, 20, 56, TRACKDIR_X_NE);
+		int ret = pf.TestAstar(silent);
+		return ret;
+	}
+
+	int TestAstar(bool silent)
+	{
+		CPerformanceTimer pc;
+
+		pc.Start();
+		bool bRet = Yapf().FindPath(NULL);
+		pc.Stop();
+
+		if (!bRet) return 1;
+
+		typedef CFixedSizeArrayT<int, 1024> Row;
+		typedef CFixedSizeArrayT<Row, 1024> Box;
+
+		Box box;
+		{
+			for (int x = 0; x < Map::xMax; x++) {
+				Row& row = box.Add();
+				for (int y = 0; y < Map::yMax; y++) {
+					row.Add() = Map::MapZ(x, y);
+				}
+			}
+		}
+		int nPathTiles = 0;
+		{
+			for (Node* pNode = &Yapf().GetBestNode(); pNode != NULL; pNode = pNode->m_parent) {
+				box[pNode->m_key.m_x][pNode->m_key.m_y] = '.';
+				nPathTiles++;
+			}
+		}
+		{
+			printf("\n\n");
+			for (int x = 0; x < Map::xMax; x++) {
+				for (int y = 0; y < Map::yMax; y++) {
+					printf("%c", box[x][y]);
+				}
+				printf("\n");
+			}
+		}
+
+		{
+			printf("\n");
+			printf("Path Tiles:    %6d\n", nPathTiles);
+//			printf("Closed nodes:  %6d\n", pf.m_nodes.ClosedCount());
+//			printf("Open nodes:    %6d\n", pf.m_nodes.OpenCount());
+//			printf("A-star rounds: %6d\n", pf.m_num_steps);
+		}
+		int total_time = pc.Get(1000000);
+		if (total_time != 0)
+			printf("Total time:    %6d us\n", pc.Get(1000000));
+
+		printf("\n");
+
+		{
+			int nCnt = Yapf().m_nodes.TotalCount();
+			for (int i = 0; i < nCnt; i++) {
+				Node& n = Yapf().m_nodes.ItemAt(i);
+				int& z = box[n.m_key.m_x][n.m_key.m_y];
+				z = (z < 'a') ? 'a' : (z + 1);
+			}
+		}
+		{
+			for (int x = 0; x < Map::xMax; x++) {
+				for (int y = 0; y < Map::yMax; y++) {
+					printf("%c", box[x][y]);
+				}
+				printf("\n");
+			}
+		}
+
+		return 0;
+	}
+};
+
+struct CDummy1 {};
+struct CDummy2 {};
+struct CDummy3 {};
+
+template <class Tpf_, class Tnode_list, class Tmap>
+struct CYapf_TypesT
+{
+	typedef CYapf_TypesT<Tpf_, Tnode_list, Tmap> Types;
+
+	typedef Tpf_                              Tpf;
+	typedef Tnode_list                        NodeList;
+	typedef Tmap                              Map;
+	typedef CYapfBaseT<Types>                 PfBase;
+	typedef CYapfTestBaseT<Types>             PfFollow;
+	typedef CDummy1                           PfOrigin;
+	typedef CDummy2                           PfDestination;
+	typedef CYapfSegmentCostCacheNoneT<Types> PfCache;
+	typedef CDummy3                           PfCost;
+};
+
+typedef CNodeList_HashTableT<CYapfNode1, 12, 16> CNodeList1;
+typedef CNodeList_HashTableT<CYapfNode2, 12, 16> CNodeList2;
+
+struct CTestYapf1
+	: public CYapfT<CYapf_TypesT<CTestYapf1, CNodeList1, CYapfMap1> >
+{
+};
+
+struct CTestYapf2
+	: public CYapfT<CYapf_TypesT<CTestYapf2, CNodeList2, CYapfMap1> >
+{
+};
+
+
diff --git a/yapf/unittest/unittest.cpp b/yapf/unittest/unittest.cpp
new file mode 100644
index 000000000..acd8d0820
--- /dev/null
+++ b/yapf/unittest/unittest.cpp
@@ -0,0 +1,166 @@
+/* $Id$ */
+
+#define UNITTEST
+
+#include "../../stdafx.h"
+
+EXTERN_C_BEGIN
+#include "../../macros.h"
+#include "../../tile.h"
+#include "../../openttd.h"
+#include "../../map.h"
+#include "../../rail.h"
+EXTERN_C_END
+
+//#include "../track_dir.hpp"
+
+#include "../yapf.hpp"
+
+#include "../autocopyptr.hpp"
+
+#include "unittest.h"
+
+#include "test_autocopyptr.h"
+#include "test_binaryheap.h"
+#include "test_fixedsizearray.h"
+#include "test_blob.h"
+#include "test_hashtable.h"
+#include "test_yapf.h"
+
+int _total_pf_time_us = 0;
+
+int num_tests_failed = 0;
+int num_tests_total = 0;
+bool _dbg = false;
+
+int do_test(const char* name, TESTPROC test_proc, bool silent)
+{
+	printf("%s ", name);
+	if (!silent) {printf("[enter]:"); getc(stdin);}
+	_dbg = !silent;
+	fflush(stdout);
+	int res = test_proc(silent);
+	if (res == 0)
+	{
+		printf("%s OK\n", silent ? "..." : "\n");
+	}
+	else {
+		printf("\n ERROR! (0x%X)\n", res);
+		printf("\nFailed cases:");
+		int num_failed = 0;
+		for(int i = 0; i < 32; i++) {
+			if (((1 << i) & res) != 0) {
+				printf(" %d", i);
+				num_failed++;
+			}
+		}
+		printf("\n\nTotal: %d cases failed\n\n", num_failed);
+	}
+
+	num_tests_total++;
+	if (res != 0) num_tests_failed++;
+
+	return (res == 0) ? 0 : 1;
+}
+
+struct TEST_RECORD {
+	const char* name;
+	TESTPROC    testproc;
+};
+
+TEST_RECORD tests[] = {
+	{"AutoCopyPtr test"   , &TestAutoCopyPtr         },
+	{"BinaryHeap test 1"  , &TestBinaryHeap1         },
+	{"BinaryHeap test 2"  , &TestBinaryHeap2         },
+	{"FixedSizeArray test", &TestFixedSizeArray      },
+	{"Array test"         , &TestArray               },
+	{"Blob test 1"        , &TestBlob1               },
+	{"Blob test 2"        , &TestBlob2               },
+	{"HashTable test 1"   , &TestHashTable1          },
+	{"Yapf test 1"        , &CTestYapf1::stTestAstar },
+	{"Yapf test 2"        , &CTestYapf2::stTestAstar },
+
+	{NULL                 , NULL                     },
+};
+
+int main(int argc, char** argv)
+{
+	bool silent = (argc == 1);
+
+	for (TEST_RECORD* tr = tests; tr->name != NULL; tr++)
+		do_test(tr->name, tr->testproc, silent);
+
+	if (num_tests_failed == 0)
+		printf("\nALL %d TESTS PASSED OK!\n\n", num_tests_total);
+	else
+		printf("\n****** %d (from %d of total) TEST(S) FAILED! ******\n", num_tests_failed, num_tests_total);
+	return 0;
+}
+
+
+
+extern "C"
+const TileIndexDiffC _tileoffs_by_dir[] = {
+	{-1,  0},
+	{ 0,  1},
+	{ 1,  0},
+	{ 0, -1}
+};
+
+extern "C"
+const byte _ffb_64[128] = {
+	0,0,1,0,2,0,1,0,
+	3,0,1,0,2,0,1,0,
+	4,0,1,0,2,0,1,0,
+	3,0,1,0,2,0,1,0,
+	5,0,1,0,2,0,1,0,
+	3,0,1,0,2,0,1,0,
+	4,0,1,0,2,0,1,0,
+	3,0,1,0,2,0,1,0,
+
+	0,0,0,2,0,4,4,6,
+	0,8,8,10,8,12,12,14,
+	0,16,16,18,16,20,20,22,
+	16,24,24,26,24,28,28,30,
+	0,32,32,34,32,36,36,38,
+	32,40,40,42,40,44,44,46,
+	32,48,48,50,48,52,52,54,
+	48,56,56,58,56,60,60,62,
+};
+
+/* Maps a trackdir to the (4-way) direction the tile is exited when following
+* that trackdir */
+extern "C"
+const DiagDirection _trackdir_to_exitdir[] = {
+	DIAGDIR_NE,DIAGDIR_SE,DIAGDIR_NE,DIAGDIR_SE,DIAGDIR_SW,DIAGDIR_SE, DIAGDIR_NE,DIAGDIR_NE,
+	DIAGDIR_SW,DIAGDIR_NW,DIAGDIR_NW,DIAGDIR_SW,DIAGDIR_NW,DIAGDIR_NE,
+};
+
+/* Maps a diagonal direction to the all trackdirs that are connected to any
+* track entering in this direction (including those making 90 degree turns)
+*/
+extern "C"
+const TrackdirBits _exitdir_reaches_trackdirs[] = {
+	TRACKDIR_BIT_X_NE | TRACKDIR_BIT_LOWER_E | TRACKDIR_BIT_LEFT_N,  /* DIAGDIR_NE */
+	TRACKDIR_BIT_Y_SE | TRACKDIR_BIT_LEFT_S  | TRACKDIR_BIT_UPPER_E, /* DIAGDIR_SE */
+	TRACKDIR_BIT_X_SW | TRACKDIR_BIT_UPPER_W | TRACKDIR_BIT_RIGHT_S, /* DIAGDIR_SW */
+	TRACKDIR_BIT_Y_NW | TRACKDIR_BIT_RIGHT_N | TRACKDIR_BIT_LOWER_W  /* DIAGDIR_NW */
+};
+
+/* Maps a trackdir to all trackdirs that make 90 deg turns with it. */
+extern "C"
+const TrackdirBits _track_crosses_trackdirs[] = {
+	TRACKDIR_BIT_Y_SE     | TRACKDIR_BIT_Y_NW,                                                   /* TRACK_X     */
+	TRACKDIR_BIT_X_NE     | TRACKDIR_BIT_X_SW,                                                   /* TRACK_Y     */
+	TRACKDIR_BIT_RIGHT_N  | TRACKDIR_BIT_RIGHT_S  | TRACKDIR_BIT_LEFT_N  | TRACKDIR_BIT_LEFT_S,  /* TRACK_UPPER */
+	TRACKDIR_BIT_RIGHT_N  | TRACKDIR_BIT_RIGHT_S  | TRACKDIR_BIT_LEFT_N  | TRACKDIR_BIT_LEFT_S,  /* TRACK_LOWER */
+	TRACKDIR_BIT_UPPER_W  | TRACKDIR_BIT_UPPER_E  | TRACKDIR_BIT_LOWER_W | TRACKDIR_BIT_LOWER_E, /* TRACK_LEFT  */
+	TRACKDIR_BIT_UPPER_W  | TRACKDIR_BIT_UPPER_E  | TRACKDIR_BIT_LOWER_W | TRACKDIR_BIT_LOWER_E  /* TRACK_RIGHT */
+};
+
+
+
+
+
+
+
diff --git a/yapf/unittest/unittest.dsp b/yapf/unittest/unittest.dsp
new file mode 100644
index 000000000..627138ab2
--- /dev/null
+++ b/yapf/unittest/unittest.dsp
@@ -0,0 +1,172 @@
+# Microsoft Developer Studio Project File - Name="unittest" - Package Owner=<4>

+# Microsoft Developer Studio Generated Build File, Format Version 6.00

+# ** DO NOT EDIT **

+

+# TARGTYPE "Win32 (x86) Console Application" 0x0103

+

+CFG=unittest - Win32 Debug

+!MESSAGE This is not a valid makefile. To build this project using NMAKE,

+!MESSAGE use the Export Makefile command and run

+!MESSAGE

+!MESSAGE NMAKE /f "unittest.mak".

+!MESSAGE

+!MESSAGE You can specify a configuration when running NMAKE

+!MESSAGE by defining the macro CFG on the command line. For example:

+!MESSAGE

+!MESSAGE NMAKE /f "unittest.mak" CFG="unittest - Win32 Debug"

+!MESSAGE

+!MESSAGE Possible choices for configuration are:

+!MESSAGE

+!MESSAGE "unittest - Win32 Release" (based on "Win32 (x86) Console Application")

+!MESSAGE "unittest - Win32 Debug" (based on "Win32 (x86) Console Application")

+!MESSAGE

+

+# Begin Project

+# PROP AllowPerConfigDependencies 0

+# PROP Scc_ProjName ""

+# PROP Scc_LocalPath ""

+CPP=cl.exe

+RSC=rc.exe

+

+!IF  "$(CFG)" == "unittest - Win32 Release"

+

+# PROP BASE Use_MFC 0

+# PROP BASE Use_Debug_Libraries 0

+# PROP BASE Output_Dir "unittest___Win32_Release"

+# PROP BASE Intermediate_Dir "unittest___Win32_Release"

+# PROP BASE Target_Dir ""

+# PROP Use_MFC 0

+# PROP Use_Debug_Libraries 0

+# PROP Output_Dir "unittest___Win32_Release"

+# PROP Intermediate_Dir "unittest___Win32_Release"

+# PROP Target_Dir ""

+# ADD BASE CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /c

+# ADD CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /c

+# ADD BASE RSC /l 0x409 /d "NDEBUG"

+# ADD RSC /l 0x409 /d "NDEBUG"

+BSC32=bscmake.exe

+# ADD BASE BSC32 /nologo

+# ADD BSC32 /nologo

+LINK32=link.exe

+# ADD BASE LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /machine:I386

+# ADD LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /machine:I386

+

+!ELSEIF  "$(CFG)" == "unittest - Win32 Debug"

+

+# PROP BASE Use_MFC 0

+# PROP BASE Use_Debug_Libraries 1

+# PROP BASE Output_Dir "unittest___Win32_Debug"

+# PROP BASE Intermediate_Dir "unittest___Win32_Debug"

+# PROP BASE Target_Dir ""

+# PROP Use_MFC 0

+# PROP Use_Debug_Libraries 1

+# PROP Output_Dir "unittest___Win32_Debug"

+# PROP Intermediate_Dir "unittest___Win32_Debug"

+# PROP Target_Dir ""

+# ADD BASE CPP /nologo /W3 /Gm /GX /ZI /Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /GZ /c

+# ADD CPP /nologo /W3 /Gm /GX /ZI /Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /GZ /c

+# ADD BASE RSC /l 0x409 /d "_DEBUG"

+# ADD RSC /l 0x409 /d "_DEBUG"

+BSC32=bscmake.exe

+# ADD BASE BSC32 /nologo

+# ADD BSC32 /nologo

+LINK32=link.exe

+# ADD BASE LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /debug /machine:I386 /pdbtype:sept

+# ADD LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /debug /machine:I386 /pdbtype:sept

+

+!ENDIF

+

+# Begin Target

+

+# Name "unittest - Win32 Release"

+# Name "unittest - Win32 Debug"

+# Begin Group "Source Files"

+

+# PROP Default_Filter "cpp;c;cxx;rc;def;r;odl;idl;hpj;bat"

+# Begin Source File

+

+SOURCE=.\unittest.cpp

+# End Source File

+# End Group

+# Begin Group "Header Files"

+

+# PROP Default_Filter "h;hpp;hxx;hm;inl"

+# Begin Source File

+

+SOURCE=.\test_autocopyptr.h

+# End Source File

+# Begin Source File

+

+SOURCE=.\test_binaryheap.h

+# End Source File

+# Begin Source File

+

+SOURCE=.\test_blob.h

+# End Source File

+# Begin Source File

+

+SOURCE=.\test_fixedsizearray.h

+# End Source File

+# Begin Source File

+

+SOURCE=.\test_hashtable.h

+# End Source File

+# Begin Source File

+

+SOURCE=.\test_yapf.h

+# End Source File

+# Begin Source File

+

+SOURCE=.\unittest.h

+# End Source File

+# End Group

+# Begin Group "Resource Files"

+

+# PROP Default_Filter "ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe"

+# End Group

+# Begin Group "yapf"

+

+# PROP Default_Filter ""

+# Begin Source File

+

+SOURCE=..\array.hpp

+# End Source File

+# Begin Source File

+

+SOURCE=..\autocopyptr.hpp

+# End Source File

+# Begin Source File

+

+SOURCE=..\binaryheap.hpp

+# End Source File

+# Begin Source File

+

+SOURCE=..\blob.hpp

+# End Source File

+# Begin Source File

+

+SOURCE=..\countedptr.hpp

+# End Source File

+# Begin Source File

+

+SOURCE=..\fixedsizearray.hpp

+# End Source File

+# Begin Source File

+

+SOURCE=..\hashtable.hpp

+# End Source File

+# Begin Source File

+

+SOURCE=..\nodelist.hpp

+# End Source File

+# Begin Source File

+

+SOURCE=..\track_dir.hpp

+# End Source File

+# Begin Source File

+

+SOURCE=..\yapfbase.hpp

+# End Source File

+# End Group

+# End Target

+# End Project

diff --git a/yapf/unittest/unittest.h b/yapf/unittest/unittest.h
new file mode 100644
index 000000000..27ba4ebdd
--- /dev/null
+++ b/yapf/unittest/unittest.h
@@ -0,0 +1,34 @@
+/* $Id$ */
+
+#define UNITTEST
+
+extern int num_tests_failed;
+extern int num_tests_total;
+
+extern bool _dbg;
+#define DBG if(_dbg) printf
+
+
+#define CHECK_INT(case_num, val, should_be) \
+{ \
+	if((val) != (should_be)) { \
+	res |= (1 << case_num); \
+	printf("\n****** ERROR in case %d: " #val " = %d (should be %d)!", case_num, (val), (should_be)); \
+	} \
+}
+
+typedef int(*TESTPROC)(bool silent);
+
+//#undef FORCEINLINE
+//#define FORCEINLINE
+
+
+#if defined(_WIN32) || defined(_WIN64)
+#  include <windows.h>
+#else
+#endif
+
+
+
+
+
diff --git a/yapf/unittest/unittest.vcproj b/yapf/unittest/unittest.vcproj
new file mode 100644
index 000000000..59d375bc5
--- /dev/null
+++ b/yapf/unittest/unittest.vcproj
@@ -0,0 +1,187 @@
+<?xml version="1.0" encoding="Windows-1252"?>

+<VisualStudioProject

+	ProjectType="Visual C++"

+	Version="7.10"

+	Name="unittest"

+	ProjectGUID="{4AECBDC3-D57E-4AFB-90BD-DDF10707588C}"

+	Keyword="Win32Proj">

+	<Platforms>

+		<Platform

+			Name="Win32"/>

+	</Platforms>

+	<Configurations>

+		<Configuration

+			Name="Debug|Win32"

+			OutputDirectory="Debug"

+			IntermediateDirectory="Debug"

+			ConfigurationType="1"

+			CharacterSet="2">

+			<Tool

+				Name="VCCLCompilerTool"

+				Optimization="0"

+				PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"

+				MinimalRebuild="TRUE"

+				BasicRuntimeChecks="3"

+				RuntimeLibrary="5"

+				UsePrecompiledHeader="0"

+				WarningLevel="3"

+				Detect64BitPortabilityProblems="TRUE"

+				DebugInformationFormat="4"/>

+			<Tool

+				Name="VCCustomBuildTool"/>

+			<Tool

+				Name="VCLinkerTool"

+				OutputFile="$(OutDir)/unittest.exe"

+				LinkIncremental="2"

+				GenerateDebugInformation="TRUE"

+				ProgramDatabaseFile="$(OutDir)/unittest.pdb"

+				SubSystem="1"

+				TargetMachine="1"/>

+			<Tool

+				Name="VCMIDLTool"/>

+			<Tool

+				Name="VCPostBuildEventTool"/>

+			<Tool

+				Name="VCPreBuildEventTool"/>

+			<Tool

+				Name="VCPreLinkEventTool"/>

+			<Tool

+				Name="VCResourceCompilerTool"/>

+			<Tool

+				Name="VCWebServiceProxyGeneratorTool"/>

+			<Tool

+				Name="VCXMLDataGeneratorTool"/>

+			<Tool

+				Name="VCWebDeploymentTool"/>

+			<Tool

+				Name="VCManagedWrapperGeneratorTool"/>

+			<Tool

+				Name="VCAuxiliaryManagedWrapperGeneratorTool"/>

+		</Configuration>

+		<Configuration

+			Name="Release|Win32"

+			OutputDirectory="Release"

+			IntermediateDirectory="Release"

+			ConfigurationType="1"

+			CharacterSet="2">

+			<Tool

+				Name="VCCLCompilerTool"

+				PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"

+				RuntimeLibrary="4"

+				UsePrecompiledHeader="0"

+				WarningLevel="3"

+				Detect64BitPortabilityProblems="TRUE"

+				DebugInformationFormat="3"/>

+			<Tool

+				Name="VCCustomBuildTool"/>

+			<Tool

+				Name="VCLinkerTool"

+				OutputFile="$(OutDir)/unittest.exe"

+				LinkIncremental="1"

+				GenerateDebugInformation="TRUE"

+				SubSystem="1"

+				OptimizeReferences="2"

+				EnableCOMDATFolding="2"

+				TargetMachine="1"/>

+			<Tool

+				Name="VCMIDLTool"/>

+			<Tool

+				Name="VCPostBuildEventTool"/>

+			<Tool

+				Name="VCPreBuildEventTool"/>

+			<Tool

+				Name="VCPreLinkEventTool"/>

+			<Tool

+				Name="VCResourceCompilerTool"/>

+			<Tool

+				Name="VCWebServiceProxyGeneratorTool"/>

+			<Tool

+				Name="VCXMLDataGeneratorTool"/>

+			<Tool

+				Name="VCWebDeploymentTool"/>

+			<Tool

+				Name="VCManagedWrapperGeneratorTool"/>

+			<Tool

+				Name="VCAuxiliaryManagedWrapperGeneratorTool"/>

+		</Configuration>

+	</Configurations>

+	<References>

+	</References>

+	<Files>

+		<Filter

+			Name="Source Files"

+			Filter="cpp;c;cxx;def;odl;idl;hpj;bat;asm;asmx"

+			UniqueIdentifier="{4FC737F1-C7A5-4376-A066-2A32D752A2FF}">

+			<File

+				RelativePath=".\unittest.cpp">

+			</File>

+		</Filter>

+		<Filter

+			Name="Header Files"

+			Filter="h;hpp;hxx;hm;inl;inc;xsd"

+			UniqueIdentifier="{93995380-89BD-4b04-88EB-625FBE52EBFB}">

+			<File

+				RelativePath=".\test_autocopyptr.h">

+			</File>

+			<File

+				RelativePath=".\test_binaryheap.h">

+			</File>

+			<File

+				RelativePath=".\test_blob.h">

+			</File>

+			<File

+				RelativePath=".\test_fixedsizearray.h">

+			</File>

+			<File

+				RelativePath=".\test_hashtable.h">

+			</File>

+			<File

+				RelativePath=".\test_yapf.h">

+			</File>

+			<File

+				RelativePath=".\unittest.h">

+			</File>

+		</Filter>

+		<Filter

+			Name="Resource Files"

+			Filter="rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx"

+			UniqueIdentifier="{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}">

+		</Filter>

+		<Filter

+			Name="yapf"

+			Filter="">

+			<File

+				RelativePath="..\array.hpp">

+			</File>

+			<File

+				RelativePath="..\autocopyptr.hpp">

+			</File>

+			<File

+				RelativePath="..\binaryheap.hpp">

+			</File>

+			<File

+				RelativePath="..\blob.hpp">

+			</File>

+			<File

+				RelativePath="..\countedptr.hpp">

+			</File>

+			<File

+				RelativePath="..\fixedsizearray.hpp">

+			</File>

+			<File

+				RelativePath="..\hashtable.hpp">

+			</File>

+			<File

+				RelativePath="..\nodelist.hpp">

+			</File>

+			<File

+				RelativePath="..\track_dir.hpp">

+			</File>

+			<File

+				RelativePath="..\yapfbase.hpp">

+			</File>

+		</Filter>

+	</Files>

+	<Globals>

+	</Globals>

+</VisualStudioProject>

diff --git a/yapf/unittest/unittest_vs80.vcproj b/yapf/unittest/unittest_vs80.vcproj
new file mode 100644
index 000000000..34680386f
--- /dev/null
+++ b/yapf/unittest/unittest_vs80.vcproj
@@ -0,0 +1,272 @@
+<?xml version="1.0" encoding="Windows-1252"?>

+<VisualStudioProject

+	ProjectType="Visual C++"

+	Version="8.00"

+	Name="unittest"

+	ProjectGUID="{01F91A15-3DA0-4FD1-981D-38F935BDD8FE}"

+	RootNamespace="test_bh"

+	Keyword="Win32Proj"

+	>

+	<Platforms>

+		<Platform

+			Name="Win32"

+		/>

+	</Platforms>

+	<ToolFiles>

+	</ToolFiles>

+	<Configurations>

+		<Configuration

+			Name="Debug|Win32"

+			OutputDirectory="$(SolutionDir)../$(ConfigurationName)"

+			IntermediateDirectory="$(SolutionDir)../$(ConfigurationName)"

+			ConfigurationType="1"

+			CharacterSet="1"

+			>

+			<Tool

+				Name="VCPreBuildEventTool"

+			/>

+			<Tool

+				Name="VCCustomBuildTool"

+			/>

+			<Tool

+				Name="VCXMLDataGeneratorTool"

+			/>

+			<Tool

+				Name="VCWebServiceProxyGeneratorTool"

+			/>

+			<Tool

+				Name="VCMIDLTool"

+			/>

+			<Tool

+				Name="VCCLCompilerTool"

+				Optimization="0"

+				InlineFunctionExpansion="0"

+				PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"

+				MinimalRebuild="true"

+				BasicRuntimeChecks="0"

+				RuntimeLibrary="3"

+				UsePrecompiledHeader="0"

+				WarningLevel="3"

+				Detect64BitPortabilityProblems="true"

+				DebugInformationFormat="3"

+			/>

+			<Tool

+				Name="VCManagedResourceCompilerTool"

+			/>

+			<Tool

+				Name="VCResourceCompilerTool"

+			/>

+			<Tool

+				Name="VCPreLinkEventTool"

+			/>

+			<Tool

+				Name="VCLinkerTool"

+				OutputFile="$(SolutionDir)../bin/$(ProjectName).exe"

+				LinkIncremental="2"

+				GenerateDebugInformation="true"

+				SubSystem="1"

+				TargetMachine="1"

+			/>

+			<Tool

+				Name="VCALinkTool"

+			/>

+			<Tool

+				Name="VCManifestTool"

+			/>

+			<Tool

+				Name="VCXDCMakeTool"

+			/>

+			<Tool

+				Name="VCBscMakeTool"

+			/>

+			<Tool

+				Name="VCFxCopTool"

+			/>

+			<Tool

+				Name="VCAppVerifierTool"

+			/>

+			<Tool

+				Name="VCWebDeploymentTool"

+			/>

+			<Tool

+				Name="VCPostBuildEventTool"

+			/>

+		</Configuration>

+		<Configuration

+			Name="Release|Win32"

+			OutputDirectory="$(SolutionDir)../$(ConfigurationName)"

+			IntermediateDirectory="$(SolutionDir)../$(ConfigurationName)"

+			ConfigurationType="1"

+			CharacterSet="1"

+			WholeProgramOptimization="1"

+			>

+			<Tool

+				Name="VCPreBuildEventTool"

+			/>

+			<Tool

+				Name="VCCustomBuildTool"

+			/>

+			<Tool

+				Name="VCXMLDataGeneratorTool"

+			/>

+			<Tool

+				Name="VCWebServiceProxyGeneratorTool"

+			/>

+			<Tool

+				Name="VCMIDLTool"

+			/>

+			<Tool

+				Name="VCCLCompilerTool"

+				InlineFunctionExpansion="2"

+				EnableIntrinsicFunctions="true"

+				FavorSizeOrSpeed="1"

+				OmitFramePointers="true"

+				PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"

+				RuntimeLibrary="2"

+				UsePrecompiledHeader="0"

+				WarningLevel="3"

+				Detect64BitPortabilityProblems="true"

+				DebugInformationFormat="3"

+			/>

+			<Tool

+				Name="VCManagedResourceCompilerTool"

+			/>

+			<Tool

+				Name="VCResourceCompilerTool"

+			/>

+			<Tool

+				Name="VCPreLinkEventTool"

+			/>

+			<Tool

+				Name="VCLinkerTool"

+				OutputFile="$(SolutionDir)../bin/$(ProjectName).exe"

+				LinkIncremental="1"

+				GenerateDebugInformation="true"

+				SubSystem="1"

+				OptimizeReferences="2"

+				EnableCOMDATFolding="2"

+				TargetMachine="1"

+			/>

+			<Tool

+				Name="VCALinkTool"

+			/>

+			<Tool

+				Name="VCManifestTool"

+			/>

+			<Tool

+				Name="VCXDCMakeTool"

+			/>

+			<Tool

+				Name="VCBscMakeTool"

+			/>

+			<Tool

+				Name="VCFxCopTool"

+			/>

+			<Tool

+				Name="VCAppVerifierTool"

+			/>

+			<Tool

+				Name="VCWebDeploymentTool"

+			/>

+			<Tool

+				Name="VCPostBuildEventTool"

+			/>

+		</Configuration>

+	</Configurations>

+	<References>

+	</References>

+	<Files>

+		<Filter

+			Name="Source Files"

+			Filter="cpp;c;cc;cxx;def;odl;idl;hpj;bat;asm;asmx"

+			UniqueIdentifier="{4FC737F1-C7A5-4376-A066-2A32D752A2FF}"

+			>

+			<File

+				RelativePath=".\unittest.cpp"

+				>

+			</File>

+		</Filter>

+		<Filter

+			Name="Header Files"

+			Filter="h;hpp;hxx;hm;inl;inc;xsd"

+			UniqueIdentifier="{93995380-89BD-4b04-88EB-625FBE52EBFB}"

+			>

+			<File

+				RelativePath=".\test_autocopyptr.h"

+				>

+			</File>

+			<File

+				RelativePath=".\test_binaryheap.h"

+				>

+			</File>

+			<File

+				RelativePath=".\test_blob.h"

+				>

+			</File>

+			<File

+				RelativePath=".\test_fixedsizearray.h"

+				>

+			</File>

+			<File

+				RelativePath=".\test_hashtable.h"

+				>

+			</File>

+			<File

+				RelativePath=".\test_yapf.h"

+				>

+			</File>

+			<File

+				RelativePath=".\unittest.h"

+				>

+			</File>

+		</Filter>

+		<Filter

+			Name="Resource Files"

+			Filter="rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav"

+			UniqueIdentifier="{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}"

+			>

+		</Filter>

+		<Filter

+			Name="yapf"

+			>

+			<File

+				RelativePath="..\array.hpp"

+				>

+			</File>

+			<File

+				RelativePath="..\autocopyptr.hpp"

+				>

+			</File>

+			<File

+				RelativePath="..\binaryheap.hpp"

+				>

+			</File>

+			<File

+				RelativePath="..\blob.hpp"

+				>

+			</File>

+			<File

+				RelativePath="..\countedptr.hpp"

+				>

+			</File>

+			<File

+				RelativePath="..\fixedsizearray.hpp"

+				>

+			</File>

+			<File

+				RelativePath="..\hashtable.hpp"

+				>

+			</File>

+			<File

+				RelativePath="..\nodelist.hpp"

+				>

+			</File>

+			<File

+				RelativePath="..\track_dir.hpp"

+				>

+			</File>

+		</Filter>

+	</Files>

+	<Globals>

+	</Globals>

+</VisualStudioProject>