// Q4_HW3_HZ.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "BinaryTree.h"
#include <iostream>
#include <Windows.h>
#include <algorithm>
#include <ctime>
// calculate time
LARGE_INTEGER m_nFreq;
LARGE_INTEGER m_nBeginTime;
LARGE_INTEGER nEndTime;
#define arrsize 65000
#define times 10
//#define TEST
#define RSHIFT(num, ary) \
{\
for (int i = tsize - 1; i >= num; i--) \
ary[i + 1] = ary[i]; \
}
int tsize = 0;
double get_time_consuming();
int BinarySearch(int ary [], int key, int l, int h);
void BinaryInsert(int arr [], int key);
int _tmain(int argc, _TCHAR* argv [])
{
// get clock frequency
QueryPerformanceFrequency(&m_nFreq);
///////////
int ary[arrsize];
BinaryTree<int> Bitree;
for (int i = 0; i < arrsize; i++)
ary[i] = i;
std::random_shuffle(ary, ary + arrsize); //shuffle the array
clock_t ct1 = clock();
QueryPerformanceCounter(&m_nBeginTime);
for (int k = 0; k < times; k++)
{
for (int j = 0; j < arrsize; j++)
{
Bitree.insert(ary[j]);
}
}
clock_t ct2 = clock();
QueryPerformanceCounter(&nEndTime);
QueryPerformanceFrequency(&m_nFreq);
double t1 = get_time_consuming();
std::cout << "BinaryTree build time t1: " << t1 << '\t' << (double) (ct2 - ct1) << std::endl;
///////////
int arr[arrsize];
clock_t ct3 = clock();
QueryPerformanceCounter(&m_nBeginTime);
for (int c = 0; c < times; c++)
{
tsize = 0;
for (int b = 0; b < arrsize; b++)
{
BinaryInsert(arr, ary[b]);
}
}
clock_t ct4 = clock();
QueryPerformanceCounter(&nEndTime);
QueryPerformanceFrequency(&m_nFreq);
double t2 = get_time_consuming();
std::cout << "BinaryInsert time t2: " << t2 << '\t' << (double) (ct4 - ct3) << std::endl;
cout << "Ratio t2/t1: " << t2 / t1 << '\t' << ((double) (ct4 - ct3)) / ((double) (ct2 - ct1)) << endl;
////////////
#ifdef TEST
print(Bitree.GetRoot());
std::cout << "\n\narr : \n";
for (int i = 0; i < arrsize; i++)
std::cout << arr[i] << '\t';
std::cout << std::endl;
std::cout << "\n\ntemp : \n";
for (int i = 0; i < arrsize; i++)
std::cout << ary[i] << '\t';
std::cout << std::endl;
#endif // TEST
//system("pause");
return 0;
return 0;
}
double get_time_consuming()
{
double time = (nEndTime.QuadPart - m_nBeginTime.QuadPart) * 1000.0 / m_nFreq.QuadPart;
return time;
}
int BinarySearch(int ary [], int key, int l, int h)
{
int m = (l + h) / 2 + 0;
while (l <= h)
{
m = (l + h) / 2 + 0;
if (key < ary[m])
{
h = m - 1;
continue;
}
else if (key > ary[m])
{
l = m + 1;
continue;
}
else return m;
}
return m;
}
void BinaryInsert(int arr [], int key)
{
int lo = 0;
int hi = tsize - 1;
//std::cout << tsize << '\t';
if (tsize == 0)
{
arr[0] = key;
tsize++;
}
else
{
int val = BinarySearch(arr, key, lo, hi);
if (arr[val] < key)
{
RSHIFT(val + 1, arr);
arr[val + 1] = key;
tsize++;
}
else
{
RSHIFT(val, arr);
arr[val] = key;
tsize++;
}
}
}
