오랜만에 자료구조 코딩을 해봤습니다.
회사 와서 코딩하다보니 학생 때에 잘안쓰던, template, object function, reference 등을 쓰게 되네요
어느 정도 '일'로써 코딩을 하다보니까 방어코딩 하는 습관도 생기고 ㅎㅎ
간만에 하니까 binray tree 도 힘드네요 ㅎㅎ
hash map 에서 한 node를 전부 map으로 구성했습니다.
이렇게 하면 hashkey collision이 일어나더라도 O(logn)의 성능이 나오려나
node class
#pragma once
namespace TANG
{
//=====================================================================================
template <class KeyType, class DataType>
class Node
{
public:
KeyType key_;
DataType data_;
Node* left_;
Node* right_;
Node ( KeyType& key
, DataType& data)
: key_(key)
, data_(data)
, left_(NULL)
, right_(NULL){};
~Node (){};
KeyType& Key () { return key_; }
DataType& Data () { return data_; }
};
//=====================================================================================
}
map class
#pragma once
namespace TANG
{
//=====================================================================================
template <class KeyType, class DataType, class CompareFunction>
class Map
{
private:
typedef Node<KeyType, DataType>* NODE_PTR;
NODE_PTR root_;
CompareFunction compare_;
int count_;
inline void ChangeNode ( int pre_compare_ret
, NODE_PTR pre_node
, NODE_PTR change_node)
{
if( pre_compare_ret < 0)
{
pre_node->left_ = change_node;
}
else if( pre_compare_ret > 0)
{
pre_node->right_ = change_node;
}
else
{
root_ = change_node;
}
}
public:
Map () : root_(NULL)
,count_(0){}
~Map () {};
//---------------------------------------------------------------------------------
void print (int& a)
{
std::cout << a << " ";
}
void print (std::string& a)
{
std::cout << a.c_str() << " ";
}
bool IsEmpty ()
{
return NULL == root_;
}
inline int Count ()
{
return count_;
}
//---------------------------------------------------------------------------------
void Show ()
{
std::cout << " count = " << Count() << std::endl << "[ ";
InOrder(root_);
std::cout << "]" << std::endl;
};
//---------------------------------------------------------------------------------
void InOrder (NODE_PTR node)
{
if( NULL == node )
return ;
InOrder(node->left_);
//std::cout << node->Key() << " ";
print(node->Key());
InOrder(node->right_);
};
//---------------------------------------------------------------------------------
int InsertConst ( KeyType key
, DataType data)
{
return Insert(key, data);
}
//---------------------------------------------------------------------------------
int Insert ( KeyType& key
, DataType& data)
{
NODE_PTR new_node = new Node<KeyType, DataType>( key, data );
if ( NULL == root_ )
{
count_++;
root_ = new_node;
return 0;
}
NODE_PTR tmp = root_;
for(;;)
{
int compare_ret = compare_( key, tmp->Key() );
if( compare_ret < 0 )
{
if( NULL == tmp->left_ )
{
tmp->left_ = new_node;
break;
}
else
{
tmp = tmp->left_;
continue;
}
}
else if( compare_ret > 0 )
{
if( NULL == tmp->right_ )
{
tmp->right_ = new_node;
break;
}
else
{
tmp = tmp->right_;
continue;
}
}
else
{
delete new_node;
return -1;
}
}//for(;;)
count_++;
return 0;
}
//---------------------------------------------------------------------------------
int GetConst ( KeyType key
, DataType& data)
{
return Get(key, data);
}
//---------------------------------------------------------------------------------
int Get ( KeyType& key
, DataType& data)
{
NODE_PTR tmp = root_;
for(;;)
{
if( NULL == tmp )
{
return -1;
}
int compare_ret = compare_( key, tmp->Key() );
if( compare_ret < 0 )
{
tmp = tmp->left_;
continue;
}
else if( compare_ret > 0 )
{
tmp = tmp->right_;
continue;
}
else
{
data = tmp->Data();
break;
}
}//for(;;)
return 0;
}
//---------------------------------------------------------------------------------
int DeleteConst ( KeyType key)
{
return Delete(key);
}
//---------------------------------------------------------------------------------
int Delete ( KeyType& key)
{
NODE_PTR pre_tmp = NULL;
int pre_compare_ret = 0;
NODE_PTR tmp = root_;
for(;;)
{
if( NULL == tmp )
{
return -1;
}
int compare_ret = compare_( key, tmp->Key() );
if( compare_ret < 0 )
{
pre_compare_ret = compare_ret;
pre_tmp = tmp;
tmp = tmp->left_;
continue;
}
else if( compare_ret > 0 )
{
pre_compare_ret = compare_ret;
pre_tmp = tmp;
tmp = tmp->right_;
continue;
}
else
{
NODE_PTR change_node = NULL;
NODE_PTR change_node_parent = NULL;
if( NULL == tmp->right_ )
{
change_node = tmp->left_;
ChangeNode( pre_compare_ret, pre_tmp, change_node);
delete tmp;
}
else if( NULL == tmp->right_->left_ )
{
change_node = tmp->right_;
change_node->left_ = tmp->left_;
ChangeNode( pre_compare_ret, pre_tmp, change_node);
delete tmp;
}
else
{
change_node = tmp->right_->left_;
change_node_parent = tmp->right_;
while( NULL != change_node->left_ )
{
change_node_parent = change_node;
change_node = change_node->left_;
}
change_node_parent->left_ = change_node->right_;
change_node->left_ = tmp->left_;
change_node->right_ = tmp->right_;
ChangeNode( pre_compare_ret, pre_tmp, change_node);
delete tmp;
}
count_--;
break;
}
}
return 0;
}
//---------------------------------------------------------------------------------
};
//=====================================================================================
}
hashmap class
#pragma once
namespace TANG
{
//=====================================================================================
template <class KeyType, class DataType, class CompareFunction, class HashFunction>
class HashMap
{
private:
class HashMapNode
{
public:
HashMapNode (int hash ) : hashkey(hash)
, left_(NULL)
, right_(NULL) {}
~HashMapNode () {}
Map<KeyType, DataType, CompareFunction> map;
int hashkey;
HashMapNode* left_;
HashMapNode* right_;
};
HashMapNode* root_;
HashFunction hash_;
inline void ChangeNode ( int pre_compare_ret
, HashMapNode* pre_node
, HashMapNode* change_node)
{
if( pre_compare_ret < 0)
{
pre_node->left_ = change_node;
}
else if( pre_compare_ret > 0)
{
pre_node->right_ = change_node;
}
else
{
root_ = change_node;
}
}
int count_;
public:
HashMap () : root_(NULL) {}
~HashMap () {}
//---------------------------------------------------------------------------------
bool IsEmpty ()
{
return NULL == root_;
}
//---------------------------------------------------------------------------------
int Count ()
{
count_ = 0;
InOrderCount(root_);
return count_;
};
//---------------------------------------------------------------------------------
void InOrderCount (HashMapNode* node)
{
if( NULL == node )
return ;
InOrderCount(node->left_);
count_ += node->map.Count();
InOrderCount(node->right_);
};
//---------------------------------------------------------------------------------
void Show ()
{
InOrder(root_);
};
//---------------------------------------------------------------------------------
void InOrder (HashMapNode* node)
{
if( NULL == node )
return ;
InOrder(node->left_);
std::cout << "hashkey = " << node->hashkey;
node->map.Show();
InOrder(node->right_);
};
//---------------------------------------------------------------------------------
int InsertConst ( KeyType key
, DataType data)
{
return Insert(key, data);
}
//---------------------------------------------------------------------------------
int Insert ( KeyType& key
, DataType& data)
{
int hashkey = hash_(key);
if ( NULL == root_ )
{
root_ = new HashMapNode(hashkey);
return root_->map.Insert(key, data);
}
HashMapNode* tmp = root_;
for(;;)
{
int compare_ret = hashkey - tmp->hashkey;
if( compare_ret < 0 )
{
if( NULL == tmp->left_ )
{
tmp->left_ = new HashMapNode(hashkey);
return tmp->left_->map.Insert(key, data);
}
else
{
tmp = tmp->left_;
continue;
}
}
else if( compare_ret > 0 )
{
if( NULL == tmp->right_ )
{
tmp->right_ = new HashMapNode(hashkey);
return tmp->right_->map.Insert(key, data);
}
else
{
tmp = tmp->right_;
continue;
}
}
else // collision
{
return tmp->map.Insert(key, data);
}
}//for(;;)
return 0;
}
//---------------------------------------------------------------------------------
int GetConst ( KeyType key
, DataType& data)
{
return Get(key, data);
}
//---------------------------------------------------------------------------------
int Get ( KeyType& key
, DataType& data)
{
int hashkey = hash_(key);
HashMapNode* tmp = root_;
for(;;)
{
if( NULL == tmp )
{
return -1;
}
int compare_ret = hashkey - tmp->hashkey;
if( compare_ret < 0 )
{
tmp = tmp->left_;
continue;
}
else if( compare_ret > 0 )
{
tmp = tmp->right_;
continue;
}
else
{
return tmp->map.Get(key, data);
}
}//for(;;)
return 0;
}
//---------------------------------------------------------------------------------
int DeleteConst ( KeyType key)
{
return Delete(key);
}
//---------------------------------------------------------------------------------
int Delete ( KeyType& key)
{
int hashkey = hash_(key);
HashMapNode* pre_tmp = NULL;
int pre_compare_ret = 0;
HashMapNode* tmp = root_;
for(;;)
{
if( NULL == tmp )
{
return -1;
}
int compare_ret = hashkey - tmp->hashkey;
if( compare_ret < 0 )
{
pre_compare_ret = compare_ret;
pre_tmp = tmp;
tmp = tmp->left_;
continue;
}
else if( compare_ret > 0 )
{
pre_compare_ret = compare_ret;
pre_tmp = tmp;
tmp = tmp->right_;
continue;
}
else
{
if( 0 != tmp->map.Delete(key) )
return -1;
if( false == tmp->map.IsEmpty() )
break;
HashMapNode* change_node = NULL;
HashMapNode* change_node_parent = NULL;
if( NULL == tmp->right_ )
{
change_node = tmp->left_;
ChangeNode( pre_compare_ret, pre_tmp, change_node);
delete tmp;
}
else if( NULL == tmp->right_->left_ )
{
change_node = tmp->right_;
change_node->left_ = tmp->left_;
ChangeNode( pre_compare_ret, pre_tmp, change_node);
delete tmp;
}
else
{
change_node = tmp->right_->left_;
change_node_parent = tmp->right_;
while( NULL != change_node->left_ )
{
change_node_parent = change_node;
change_node = change_node->left_;
}
change_node_parent->left_ = change_node->right_;
change_node->left_ = tmp->left_;
change_node->right_ = tmp->right_;
ChangeNode( pre_compare_ret, pre_tmp, change_node);
delete tmp;
}
break;
}
}
return 0;
}
//---------------------------------------------------------------------------------
};
//=====================================================================================
}
compare function, hash function
#pragma once;
namespace TANG
{
class CompareInt
{
public:
int operator()(int left, int right)
{
return left - right;
}
};
class HashShort
{
public:
short operator()(int key)
{
return (short)key % 10;
}
};
class HashString
{
public:
short operator()(std::string& key)
{
int size = key.size();
unsigned int sum = 0;
unsigned int ten = 1;
for(int i = 0; i < size && i < 3; i++)
{
sum += (unsigned int)key.at(i) * ten;
ten *= 10;
}
return sum % 1023;
}
};
class CompareString
{
public:
int operator()(std::string& left, std::string& right)
{
int leftsize = left.size();
int rightsize = right.size();
int minsize = leftsize;
if( minsize > rightsize )
minsize = rightsize;
for(int i = 0; i < minsize; i++)
{
int ret = right.at(i) - left.at(i);
if( ret > 0 )
return -1;
else if( ret < 0 )
return 1;
}
if( leftsize == rightsize )
return 0;
else if( minsize == leftsize )
return -1;
return 1;
}
};
}
테스트
#include "pch.h"
#pragma hdrstop
int main()
{
using namespace TANG;
srand((unsigned int)time(NULL));
int ret = 0;
#if 0
Map<int, int, CompareInt> yaho;
for(int i = 0; i < 10000; i++)
{
ret = yaho.InsertConst((int)rand(), i);
}
//yaho.Show();
int data;
for(int i = 0; i < 100; i++)
{
int key = (int)rand();
ret = yaho.GetConst(key, data);
if( 0 == ret )
std::cout << "key : " << key
<< "\tdata : " << data
<< std::endl;
}
//ret = yaho.GetConst(3, data);
int failcount = 0;
for(int i = 0; i < 100; i++)
{
int key = (int)rand();
ret = yaho.DeleteConst(key);
if( 0 != ret )
{
failcount++;
std::cout << "fail key : " << key
<< std::endl;
}
}
std::cout << "fail count : " << failcount << std::endl;
std::cout << "count : " << yaho.Count() << std::endl;
//ret = yaho.DeleteConst(3);
int test;
std::cin >> test;
yaho.Delete(test);
#endif
#if 0
int count = 0;
std::ifstream fin("input2.txt");
fin >> count;
Map<int, int, CompareInt> yaho;
int duplicate_count = 0;
for(int i = 0; i < count; i++)
{
int inputvalue;
fin >> inputvalue;
int data = 1;
if( 0 != yaho.Insert(inputvalue, data))
{
duplicate_count++;
}
}
fin.close();
std::cout << "count : " << yaho.Count() << std::endl;
std::cout << "duplicate : " << duplicate_count << std::endl;
std::ifstream fin2("input2.txt");
int delete_fail_count = 0;
fin2 >> count;
for(int j = 0;j < count-2; j++)
{
int inputvalue;
fin2 >> inputvalue;
if( 0 != yaho.Delete(inputvalue) )
{
delete_fail_count++;
}
}
fin2.close();
std::cout << "count : " << yaho.Count() << std::endl;
std::cout << "deletefail: " << delete_fail_count << std::endl;
//yaho.Show();
#endif
#if 0
HashMap<int, int, CompareInt, HashShort> yaho;
ret = yaho.InsertConst(1, 1);
ret = yaho.InsertConst(2, 2);
ret = yaho.InsertConst(3, 3);
ret = yaho.InsertConst(13, 3);
ret = yaho.InsertConst(13, 3);
ret = yaho.DeleteConst(13);
for(int i = 0; i < 20; i++)
{
ret = yaho.InsertConst((int)rand(), i);
ret = yaho.DeleteConst(i);
}
ret = yaho.InsertConst(13, 3);
yaho.Show();
#endif
#if 0
HashMap<std::string, int, CompareString, HashString> yaho;
ret = yaho.InsertConst("yaho", 1);
ret = yaho.InsertConst("aaaaa", 2);
ret = yaho.InsertConst("a", 3);
ret = yaho.InsertConst("dsgawegwaeg", 3);
ret = yaho.InsertConst("wer23", 3);
int data = 0;
ret = yaho.GetConst("aaaaa", data);
std::cout << "select : " << data << std::endl;
ret = yaho.DeleteConst("a");
ret = yaho.DeleteConst("www");
ret = yaho.DeleteConst("wer23");
yaho.Show();
#endif
#if 0
std::ofstream fout("input.txt");
int count = 10000;
fout << count << std::endl;
for(int j = 0; j < count; j++)
{
char randomtext[100] = {0};
for(int i = 0; i < 99; i ++)
{
int r = rand();
randomtext[i] = 'a' + r % 26;
}
fout << randomtext << std::endl;
}
#endif
#if 0
std::ofstream fout("input2.txt");
int count = 10000;
fout << count << std::endl;
for(int j = 0; j < count; j++)
{
int r = rand();
fout << r << std::endl;
}
#endif
#if 1
HashMap<std::string, int, CompareString, HashString> yaho;
int count = 0;
std::ifstream fin("input.txt");
fin >> count;
int duplicate_count = 0;
for(int i = 0; i < count; i++)
{
char inputtext[100] = {0};
fin >> inputtext;
std::string input_key(inputtext);
int input_data = 1;
if( 0 != yaho.Insert(input_key, input_data) )
{
duplicate_count++;
}
}
fin.close();
std::cout << "count : " << yaho.Count() << std::endl;
std::cout << "duplicate : " << duplicate_count << std::endl;
std::ifstream fin2("input.txt");
fin2 >> count;
int delete_fail_count = 0;
for(int j = 0; j < count; j++)
{
char inputtext[100] = {0};
fin2 >> inputtext;
std::string input_key(inputtext);
int input_data = 1;
if( 0 != yaho.Delete(input_key) )
{
delete_fail_count++;
}
}
std::cout << "count : " << yaho.Count() << std::endl;
std::cout << "delete fail_count : " << delete_fail_count << std::endl;
fin2.close();
//yaho.Show();
#endif
return 0;
}
오랫만에 자료구조 코딩하니까 잼나네요 ㅎㅎ