| 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
|