From 5e73dce0e71791b87e5b096a890578eefcc26639 Mon Sep 17 00:00:00 2001 From: KUDr Date: Sat, 27 May 2006 16:12:16 +0000 Subject: (svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing. --- yapf/unittest/test_autocopyptr.h | 43 +++++ yapf/unittest/test_binaryheap.h | 103 +++++++++++ yapf/unittest/test_blob.h | 61 +++++++ yapf/unittest/test_fixedsizearray.h | 114 ++++++++++++ yapf/unittest/test_hashtable.h | 74 ++++++++ yapf/unittest/test_yapf.h | 350 ++++++++++++++++++++++++++++++++++++ yapf/unittest/unittest.cpp | 166 +++++++++++++++++ yapf/unittest/unittest.dsp | 172 ++++++++++++++++++ yapf/unittest/unittest.h | 34 ++++ yapf/unittest/unittest.vcproj | 187 +++++++++++++++++++ yapf/unittest/unittest_vs80.vcproj | 272 ++++++++++++++++++++++++++++ 11 files changed, 1576 insertions(+) create mode 100644 yapf/unittest/test_autocopyptr.h create mode 100644 yapf/unittest/test_binaryheap.h create mode 100644 yapf/unittest/test_blob.h create mode 100644 yapf/unittest/test_fixedsizearray.h create mode 100644 yapf/unittest/test_hashtable.h create mode 100644 yapf/unittest/test_yapf.h create mode 100644 yapf/unittest/unittest.cpp create mode 100644 yapf/unittest/unittest.dsp create mode 100644 yapf/unittest/unittest.h create mode 100644 yapf/unittest/unittest.vcproj create mode 100644 yapf/unittest/unittest_vs80.vcproj (limited to 'yapf/unittest') 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 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 bh(max_items); + CFixedSizeArrayT 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 bh(max_items); + CFixedSizeArrayT 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 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 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 CSubArray; +typedef CFixedSizeArrayT 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 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 HashTable1_t; + typedef CArrayT Array_t; + typedef CHashTableT 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 +struct CTestYapfNodeT { + typedef Tkey_ Key; + typedef CTestYapfNodeT 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 CYapfNode1; +typedef CTestYapfNodeT CYapfNode2; + +template +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(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 Row; + typedef CFixedSizeArrayT 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 +struct CYapf_TypesT +{ + typedef CYapf_TypesT Types; + + typedef Tpf_ Tpf; + typedef Tnode_list NodeList; + typedef Tmap Map; + typedef CYapfBaseT PfBase; + typedef CYapfTestBaseT PfFollow; + typedef CDummy1 PfOrigin; + typedef CDummy2 PfDestination; + typedef CYapfSegmentCostCacheNoneT PfCache; + typedef CDummy3 PfCost; +}; + +typedef CNodeList_HashTableT CNodeList1; +typedef CNodeList_HashTableT CNodeList2; + +struct CTestYapf1 + : public CYapfT > +{ +}; + +struct CTestYapf2 + : public CYapfT > +{ +}; + + 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 +#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 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 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 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + -- cgit v1.2.3-70-g09d2