Свободен |
30-05-2010 - 17:39 CODE | #include <stdio.h>
/////////////////////////////////////////////////////////////// // Dirty binary tree // template <typename T> class CNode { public: CNode () { m_IsAccepted = false; m_pRight = 0; m_pLeft = 0; };
CNode ( CNode* pRoot, T Value ) { m_IsAccepted = false; m_pRight = 0; m_pLeft = 0; m_Value = Value; if ( pRoot ) { m_IsAccepted = Insert ( pRoot, this ); }; };
~CNode() { if ( m_IsAccepted ) { if ( m_pRight ) { delete m_pRight; };
if ( m_pLeft ) { delete m_pLeft; }; }; };
T* GetValue () { return &m_Value; };
bool IsAccepted() const { return m_IsAccepted; };
bool operator == (const CNode& rValue) { return this->m_Value == rValue.m_Value; };
bool operator > (const CNode& rValue) { return this->m_Value > rValue.m_Value; };
bool operator < (const CNode& rValue) { return this->m_Value > rValue.m_Value; };
CNode& operator = ( CNode& rValue ) { if ( this != &rValue ) { m_pLeft = rValue.m_pLeft; m_pRight = rValue.m_pRight; m_Value = rValue.m_Value; m_IsAccepted = rValue.m_IsAccepted; }; return *this; };
static bool Insert ( CNode* pRoot, CNode* pChild ) { if ( pRoot && pChild ) { if ( pChild->m_IsAccepted ) { return false; }; if ( !pRoot->m_IsAccepted ) { pChild->m_IsAccepted = true; *pRoot = *pChild; delete pChild; return true; }; if ( *pRoot == *pChild ) { *pChild = *pRoot; return false; } else if ( *pChild > *pRoot ) { if ( pRoot->m_pRight ) { return Insert ( pRoot->m_pRight, pChild ); } else { pRoot->m_pRight = pChild; return true; }; } else { if ( pRoot->m_pLeft ) { return Insert ( pRoot->m_pLeft, pChild ); } else { pRoot->m_pLeft = pChild; return true; }; }; } else { return false; }; };
private: CNode* m_pRight, *m_pLeft; T m_Value; bool m_IsAccepted; };
/////////////////////////////////////////////////////////////// // Matrix item template // template <typename T> class CMatrixItem { public: CMatrixItem () { };
CMatrixItem ( int x, int y, T Value ) { m_x = x; m_y = y; m_Value = Value; };
CMatrixItem ( CMatrixItem& rValue ) { memset ( this, &rValue, sizeof(this) ); };
CMatrixItem& operator = ( CMatrixItem& rValue ) { if ( this != &rValue ) { m_x = rValue.m_x; m_y = rValue.m_y; m_Value = rValue.m_Value; }; return *this; };
bool operator == (const CMatrixItem& rValue) { return m_Value == rValue.m_Value; };
bool operator > (const CMatrixItem& rValue) { return m_Value > rValue.m_Value; };
bool operator < (const CMatrixItem& rValue) { return m_Value < rValue.m_Value; };
public: operator T() { return m_Value; };
int GetX() const { return m_x; };
int GetY() const { return m_y; };
private: int m_x; int m_y; T m_Value; };
////////////////////////////////////////////////////////////// // template <> CMatrixItem<char*>::CMatrixItem ( int x, int y, char* Value ) { m_x = x; m_y = y;
// Store hash instead of full string if ( Value ) { unsigned int b = 0x0005C6B7; unsigned int a = 0x0000F8C9; unsigned int hash = 0;
while ( *Value ) { hash = hash * a + *Value; a *= b; Value++; };
m_Value = (char*)(hash & 0x7FFFFFFF); } else { m_Value = 0; }; };
/////////////////////////////////////////////////////////////// // Build dirty binary tree and filter equal values // pMatrix - flattened two-dimensional array // width - matrix width // height - matrix height template<typename T> CNode<CMatrixItem<T>>* GetTree ( T* pMatrix, int width, int height ) { if ( CNode<CMatrixItem<T>>* pTree = new CNode<CMatrixItem<T>>() ) { for ( int x = 0; x < width; x++ ) { for ( int y = 0; y < height; y++ ) { CNode<CMatrixItem<T>>* pNode = new CNode<CMatrixItem<T>> ( pTree, CMatrixItem<T>(x,y, pMatrix[x+y*width] ) ); if ( pNode && !pNode->IsAccepted() ) { printf ( "%d:%d seems to be equal to %d:%d\n", x, y, pNode->GetValue()->GetX(), pNode->GetValue()->GetY() ); delete pNode; }; }; }; return pTree; };
return 0; }
/////////////////////////////////////////////////////////////// // int main(int argc, char* argv[]) { int arr[5][5] = { { 22, 12, 13, 14, 15 }, { 22, 22, 23, 00, 25 }, { 31, 31, 33, 00, 35 }, { 41, 42, 43, 00, 11 }, { 51, 52, 53, 54, 11 } };
printf ( "Дублирование в целочисленной матрице:\n" ); if ( CNode<CMatrixItem<int>>* pTree = GetTree ( &arr[0][0], 5, 5 ) ) { // Here we're with our binary tree
// ... DoSomething();
// Clean-up delete pTree; };
printf ( "\n\nДублирование в матрице, содержащей строки:\n" ); char* chararr[3][3] = { { "Один", "Ноль", "Три" }, { "Четыре", "Пять", "Ноль" }, { "Семь", "Восемь", "Девять" } };
if ( CNode<CMatrixItem<char*>>* pTree = GetTree ( &chararr[0][0], 3, 3 ) ) { // Here we're with our binary tree
// ... DoSomething();
// Clean-up delete pTree; };
return 0; }
|
Это сообщение отредактировал JeyLo - 30-05-2010 - 17:52 |