📄 qtree.cpp
字号:
#include "qtree.h"
extern int qtree_level;
extern Cache cache_memory;
extern filename[];
extern BlockFile myblockfile;
qtree_node::qtree_node (int lv){
for (int i=0; i<DIMENSION; i++)
coor_lower[i]=coor_upper[i]=0;
level=lv;
is_leaf=true;
enable_split=true;
num_pts=0;
node_id="";
}
qtree_node::~qtree_node(){
//dummy
}
bool qtree_node::insert_one_data (Entry* data){
char temp[DIMENSION];
int t;
if (is_leaf==false) // non-leaf
{ for (int i=0;i< DIMENSION; i++)
{ if (data->data[i] <= (coor_upper[i]- 1.0/(my_int_power(level+1)))) temp[i]='0';
else temp[i]='1';
}
child[binary_to_deci(temp)]->insert_one_data(data); //recursive
}
else //leaf
{
t=cache_memory.in_cache(node_id);
if (t<0) // not in cache, but in file
{ int ri1;
ri1=myblockfile.retrieve_index(node_id);
myblockfile.fwrite_one_data(data, ri1);
} ////////to be improved
else if ((cache_memory.cacheblock[t]).write_one_data(data)== true) //successful insertion
num_pts++;
else // cache block full
{
if(enable_split==true) {
split();
this->insert_one_data(data);
}
else{ //no more split, just store the coming data to file
int ri;
ri=myblockfile.retrieve_index(node_id);
if (ri==-1){ //no such block in file, so create one
myblockfile.fappend_block();
myblockfile.file_cont[myblockfile.number-1]=node_id;
myblockfile.fwrite_one_data(data, myblockfile.number-1);
}
else { // the block exists
myblockfile.fwrite_one_data(data, ri);
}
}
}
}
return true;
}
void qtree_node::split(){
/* child_0=new qtree_node(left, right-right/(2*level), top-top/(2*level), bottom ,level+1);
child_0->node_id+="00";
for(int i)
child_1=new qtree_node(left, right-right/(2*level),top, bottom+bottom/(2*level), level+1);
child_1->node_id+="01";
child_2=new qtree_node(left+left(2*level), right,top-top/(2*level), bottom, level+1);
child_2->node_id+="10";
child_3=new qtree_node(left+left(2*level), right,top, bottom+bottom/(2*level), level+1);
child_3->node_id+="11"; */
char appen[DIMENSION];
bool invert_the_last=false;
// char* appen2=new char[DIMENSION];
this->is_leaf=false;
for (int i=my_int_power(DIMENSION)-1;i>=0;i--) { //for each child
child[i]=new qtree_node(level+1);
if ((level+1) > qtree_level) qtree_level++; //update global variable
/* itoa(i, appen,2); //appen=00, 01, 10.....
char zero='0';
if (strlen(appen)<DIMENSION)
{//strcpy(appen2, appen);
for (int x=1; x<=DIMENSION-strlen(appen);x++)
(char*)appen=strcat(&zero, appen);
// strcpy(appen, appen2);
// delete[] appen2;
} */
deci_to_binary(i, appen);
string temp_node_id=node_id;
for (int k=0; k<DIMENSION; k++)
temp_node_id+=appen[k];
child[i]->node_id = temp_node_id;
for(int j=0;j<DIMENSION;j++){ //for each dimension bound, split mother's bounds
if (appen[j]=='0')
{ child[i]->coor_upper[j]=coor_upper[j]-1.0/(my_int_power(child[i]->level));
child[i]->coor_lower[j]=coor_lower[j];
}
else
{ child[i]->coor_upper[j]=coor_upper[j];
child[i]->coor_lower[j]=coor_lower[j]+1.0/(my_int_power(child[i]->level));
}
}
// start moving
int t=cache_memory.find_available_space();
if (i!=0)
{
if (t<0) { string temp_node_id=node_id;
for (int j=0 ; j<DIMENSION; j++)
temp_node_id+=appen[j];
myblockfile.fappend_block();
myblockfile.file_cont[myblockfile.number-1]=temp_node_id;
child[i]->ptr_to_cache=NULL; //means this child is not in cache, but in file
child[i]->num_pts = myblockfile.file_cont_no[myblockfile.number-1]=move_data_m2f(i);
child[i]->enable_split=false;
invert_the_last=true;
//child[0]->enable_split=false;
}
else
{ string temp_node_id=node_id;
for (int j=0 ; j<DIMENSION; j++)
temp_node_id+=appen[j];
cache_memory.cache_cont[t] = temp_node_id;
cache_memory.cacheblock[t].block_id = temp_node_id;
child[i]->ptr_to_cache = &cache_memory.cacheblock[t];
move_data(&cache_memory.cacheblock[t],i);
child[i]->num_pts = cache_memory.cacheblock[t].num_pts;
}
}
else // the last child overwrites mother
{ int k=cache_memory.in_cache(node_id); //find mother itself
string temp_node_id=node_id;
for (int j=0; j<DIMENSION; j++)
temp_node_id+=appen[j];
cache_memory.cache_cont[k] = temp_node_id; //overwrite mother's id with the last child's
cache_memory.cacheblock[k].block_id = temp_node_id;
child[i]->ptr_to_cache = ptr_to_cache;
move_data (ptr_to_cache,i);
ptr_to_cache = NULL; //set mother's point as null
if (invert_the_last==true)
child[i]->enable_split=false;
}
}
}
int qtree_node::move_data_m2f(int child_i){
char* temp_ptr;
int counter=0;
float load;
for (temp_ptr= ptr_to_cache->cache+ sizeof(int); temp_ptr < ptr_to_cache->write_ptr; temp_ptr+=DIMENSION * sizeof(float))
{ bool sign=true; //true means within bounds
for (int i=0; i< DIMENSION; i++)
{
memcpy(&load, temp_ptr+i*sizeof(float), sizeof(float));
if (load < child[child_i]->coor_upper[i] && load > child[child_i]->coor_lower[i]) //testing whether in bounds //to deal with data sharp ON the bound later
continue;
else {sign=false; break;}
}
if (sign==true){ // within bounds
counter++;
myblockfile.fmove_one_data(temp_ptr, myblockfile.number-1);
}
}
return counter;
}
void qtree_node::move_data(CacheBlock* dest, int child_i){
char* temp_ptr; //pointer for reading the mother block's data
int counter=0;
float load;
if (dest != ptr_to_cache) //not the last child
{ dest->write_ptr = dest->cache+sizeof(int);
for (temp_ptr= ptr_to_cache->cache+ sizeof(int); temp_ptr < ptr_to_cache->write_ptr; temp_ptr+=DIMENSION * sizeof(float))
{ bool sign=true; //true means within bounds
for (int i=0; i< DIMENSION; i++)
{
memcpy(&load, temp_ptr+i*sizeof(float), sizeof(float));
if (load < child[child_i]->coor_upper[i] && load > child[child_i]->coor_lower[i]) //testing whether in bounds //to deal with data sharp ON the bound later
continue;
else {sign=false; break;}
}
if (sign==true){ // within bounds
counter++;
memcpy(dest->write_ptr, temp_ptr, DIMENSION * sizeof(float));
dest->write_ptr += DIMENSION * sizeof(float);
}
}
memcpy(dest->cache, &counter, sizeof(int));
dest->num_pts = counter;
}
else { // the last child
char* original_write_ptr = ptr_to_cache->write_ptr; //write_ptr will be modified while overwriting
ptr_to_cache->write_ptr = ptr_to_cache->cache+sizeof(int);
for (temp_ptr= ptr_to_cache->cache+ sizeof(int); temp_ptr < original_write_ptr; temp_ptr+=DIMENSION * sizeof(float))
{ bool sign=true; //true means within bounds
for (int i=0; i< DIMENSION; i++)
{
memcpy(&load, temp_ptr+i*sizeof(float), sizeof(float));
if (load < child[child_i]->coor_upper[i] && load > child[child_i]->coor_lower[i]) //testing whether in bounds //to deal with data sharp ON the bound later
continue;
else {sign=false; break;}
}
if (sign==true){ // within bounds
counter++;
memcpy(dest->write_ptr, temp_ptr, DIMENSION * sizeof(float));
dest->write_ptr += DIMENSION * sizeof(float);
}
}
memcpy(dest->cache, &counter, sizeof(int));
dest->num_pts = counter;
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -