xbuild.c

xtree程序实现

  /* Choose subtree */
  /******************/

  if (current_node->ptr[0]->ptr[0]->attribute != LEAF) {

	child_chosen = least_area_enlarge(current_node, data_node);

  }
  else {

	child_chosen = least_overlap_enlarge(current_node, data_node);

  }

  /*******/
  /* CL4 */
  /*******/
    
  /***********************/
  /* Descend recursively */
  /***********************/

  current_node = current_node->ptr[child_chosen];
  level_found = choose_leaf(node_found, current_node, current_level+1, data_node);


  return(level_found);

} /* choose_leaf */


/*
  function : void adjust_MBR(node_type *node_inserted)
  purpose  : to adjust the MBR from the node inserted up to the root
  parameter: node_type *node_inserted - the node just inserted
  return   : none
*/
void adjust_MBR(node_type *node_inserted)
{
  node_type *node = node_inserted;
  int i, flag;

  while(node->attribute != ROOT) {
	      
  	flag = FALSE;
  	for(i=0; i < dim; i++) { 
		if(node->parent->a[i] > node->a[i]) {
			node->parent->a[i] = node->a[i];
			flag = TRUE;
		}
		if(node->parent->b[i] < node->b[i]) {
			node->parent->b[i] = node->b[i];
			flag = TRUE;
		}
  	}

	if (flag == FALSE) break;

	node = node->parent;

  }

  return;

} /* adjust_MBR */


/*
  function : void adjust_MBR_delete(node_type *node_inserted)
  purpose  : to adjust the MBR from the node just some entries are removed up to the root
  parameter: node_type *node_inserted - the nodes that some nodes have beem removed
  return   : none
*/
void adjust_MBR_delete(node_type *node_inserted)
{
  node_type *node = node_inserted, *parent;
  int j, stop;


  while(node->attribute != ROOT) {
  
	parent = node->parent;
//if (node == NULL)
//{
//	printf("---node is nULL!\n");
//}
//if (parent == NULL)
//{
//	printf("---parent is NULL!\n");
//	printf("---restore\n");
//	parent = node_inserted->parent;
//}
	// **** Ray changed
	//stop = M - parent->vacancy;
	stop = parent->snodeSize*M - parent->vacancy;

	for (j=0; j<dim; j++) {
		parent->a[j] = parent->ptr[0]->a[j];
		parent->b[j] = parent->ptr[0]->b[j];
	}
//printf("stop %d\n", stop);
	for (j=1; j<stop; j++) {
		cal_MBR_node_node(parent->a, parent->b, parent, parent->ptr[j]);
	}
  
//printf("3\n");
     //   if (flag == FALSE) break;
 
        node = parent;
        
  }
         
  return;

} /* adjust_MBR_delete */     


/*
  function : void swap(int *sorted_index, double *value, int i, int j)
  purpose  : to swap the two elements in both sorted index and value
             specified by the index i and index j 
  parameter: int *sorted_index - the array with two elements to be swapped
             double *value     - the array with two elements to be swapped
	     int i             - the index of swapping
	     int j             - the index of swapping
  return   : none
*/
void swap(int *sorted_index, double *value, int i, int j)
{ 
  int temp_index;
  double temp_value; 

  temp_value = value[i];  
  value[i] = value[j];
  value[j] = temp_value;
  
  temp_index = sorted_index[i];
  sorted_index[i] = sorted_index[j];
  sorted_index[j] = temp_index;
                
  return;
   
}


/*
  function : int partition(int *sorted_index, double *value, int start_index, int end_index)
  purpose  : to partition the sorted index and the value into two parts, which is used
             in quicksort
  parameter: int *sorted_index - the array of sorted index
             double *value     - the array of value
	     int start_index   - the index of the beginning of the array to be partitioned
	     int end_index     - the index of the end of the array to be partitioned
  return   : int - the index pointing to the partition index
*/
int partition(int *sorted_index, double *value, int start_index, int end_index)
{
  double pivot_value;  
  int i, j;
        
  pivot_value = value[start_index];
        
  i = start_index - 1;
  j = end_index + 1;
                
  while (1) {
   
        do {    
                j = j - 1;
  
        } while (value[j] > pivot_value);
 
        do {
                i = i + 1;

        } while (value[i] < pivot_value);

        if (i < j)
                swap(sorted_index, value, i, j);
        else
                return(j);
        
  }     


  // **** Ray have added the return value -1.
  return -1;

}



/* I think it is sorted in increasing order */
/*
  function : void quicksort(int *sorted_index, double *value, int start_index, int end_index)
  purpose  : to sort the array value starting from start_index to end_index with the output
             in the sorted_index
  parameter: int *sorted_index - the sorted index of the array value
             double *value     - the array value to be sorted
	     int start_index   - the start index of the array to be sorted
	     int end_index     - the end index of the array to be sorted
  return   : none
*/
void quicksort(int *sorted_index, double *value, int start_index, int end_index)
{
  int pivot;

  if (start_index < end_index) {

        pivot = partition(sorted_index, value, start_index, end_index);

        quicksort(sorted_index, value, start_index, pivot);

        quicksort(sorted_index, value, pivot+1, end_index);

  }
 
  return;

}

/*
  function : void sort_entries(int *sorted_index, node_type **overnode, int axis_sort, int noOfOver) 
  purpose  : to sort the entries in the over node according to the axis chosen axis_sort
  parameter: int *sorted_index    - the array of sorted index
             node_type **overnode - the array of the over node
	     int axis_sort        - the axis chosen
	     int noOfOver         - the no. of over nodes
  return   : none
*/
// *** Ray changed
//void sort_entries(int *sorted_index, node_type **overnode, int axis_sort)
void sort_entries(int *sorted_index, node_type **overnode, int axis_sort, int noOfOver)
{
  int i, start, end;
  double *value;

  // *** Ray changed
  //value = (double *)malloc(sizeof(double) * (M+1));
  value = (double *)malloc(sizeof(double) * noOfOver);

  // *** Ray changed
  //for (i=0; i<M+1; i++) {
  for (i=0; i<noOfOver; i++) {
	sorted_index[i] = i;
	value[i] = (double)overnode[i]->a[axis_sort];
  }

  // *** Ray changed
  //quicksort(sorted_index, value, 0, M);
  quicksort(sorted_index, value, 0, noOfOver-1);

  i = 0;
  // *** Ray changed
  //while (i<M) {
  while (i<noOfOver-1) {

	if (value[i] == value[i+1]) {

		start = i;

		// *** Ray changed
		//while (i < M && value[i] == value[i+1]) {
		while (i < noOfOver-1 && value[i] == value[i+1]) {

			value[i] = (double)overnode[sorted_index[i]]->b[axis_sort];
			i ++;

		}

		value[i] = (double)overnode[sorted_index[i]]->b[axis_sort];
		end = i;	



		if ((end - start) > 1) {
			quicksort(sorted_index, value, start, end);
		}
		else {
			if (value[end] < value[start]) {
				swap(sorted_index, value, start, end);
			}
		}
	}


	i++;

  }

  free(value);


  return;

}

/*
  function : int ChooseSplitAxis(node_type **overnode) 
  purpose  : to choose the best split axis among the array of the nodes overnode
  parameter: node_type **overnode - the array of the over nodes to be chosen with the
                                    best split axis
  return   : int - the best split axis
*/
int ChooseSplitAxis(node_type **overnode)
{
  int axis_chosen, *sorted_index;
  node_type *group1, *group2;
  double new_margin_value, min_margin_value;


  int i, j, k, l, stop, cut;
  // *** Ray added
  node_type *parentNode;
  int noOfOver;

  // *** Ray added
if (overnode[0] == NULL) printf("  ~~~~~sad\n");
  parentNode = overnode[0]->parent;
  noOfOver = parentNode->snodeSize*M+1;


  // *** Ray changed
  //sorted_index = (int *)malloc(sizeof(int) * (M+1));
  sorted_index = (int *)malloc(sizeof(int) * noOfOver);
  tree_node_allocate(&group1);
  tree_node_allocate(&group2);


  for (i=0; i<dim; i++) {

	sort_entries(sorted_index, overnode, i, noOfOver);   // sort the entries by axis i


	new_margin_value = 0.0;
	// *** Ray changed
	//stop = M - 2*m + 1;
	stop = M*parentNode->snodeSize - 2*m + 1;
	for (k=0; k<stop; k++) {

        	for (l=0; l<dim; l++) {
                	group1->a[l] = overnode[sorted_index[0]]->a[l];
	                group1->b[l] = overnode[sorted_index[0]]->b[l];
					// *** Ray changed
        	        //group2->a[l] = overnode[sorted_index[M]]->a[l];
                	//group2->b[l] = overnode[sorted_index[M]]->b[l];
					group2->a[l] = overnode[sorted_index[M*parentNode->snodeSize]]->a[l];
                	group2->b[l] = overnode[sorted_index[M*parentNode->snodeSize]]->b[l];
        	}        


		j = 0;
		cut = m + k;
		// *** Ray changed
		//while (j < M+1) {
		while (j < M*parentNode->snodeSize+1) {

			if (j < cut) {

				cal_MBR_node_node(group1->a, group1->b, group1, overnode[sorted_index[j]]);

			}
			else {

				cal_MBR_node_node(group2->a, group2->b, group2, overnode[sorted_index[j]]);

			}

			j++;

		}

		for (l=0; l<dim; l++) {

			new_margin_value = new_margin_value + group1->b[l] - group1->a[l];
			new_margin_value = new_margin_value + group2->b[l] - group2->a[l];

		}
	}

	if (i == 0) {

                axis_chosen = i;
                min_margin_value = new_margin_value;
	}
	else {

		if (new_margin_value < min_margin_value) {

			axis_chosen = i;
			min_margin_value = new_margin_value;
		}

	}	
  }

  tree_node_deallocate(group1);
  tree_node_deallocate(group2);
  free(sorted_index);

  return(axis_chosen);

} /* ChooseSplitAxis */


/*
  function : void ChooseSplitIndex(node_type **overnode, int axis_chosen, node_type 
             *group1_chosen, node_type *group2_chosen)
  purpose  : to choose the best split index among the over nodes given the chosen axis
  parameter: node_type **overnode     - the array of the over nodes
             int axis_chosen          - the axis to be split
	     node_type *group1_chosen - the 1st group to be partitioned
	     node_type *group2_chosen - the 2nd group to be partitioned
  return   : none
*/
void ChooseSplitIndex(node_type **overnode, int axis_chosen, node_type 
*group1_chosen, node_type *group2_chosen)
{
  int split_index, *sorted_index;
  node_type *group1, *group2;  
  double new_overlap_value, min_overlap_value;
  double vol_at_index, new_vol;

  int i, j, k, stop, cut;
  
//FILE *fp;
  // *** Ray added
  node_type *parentNode;
  int noOfOver;

  // *** Ray added (to be changed)
  parentNode = overnode[0]->parent;
  noOfOver = parentNode->snodeSize*M+1;

  // **** Ray has changed
  //sorted_index = (int *)malloc(sizeof(int) * (M+1));
  sorted_index = (int *)malloc(sizeof(int) * noOfOver);

  // **** Ray changed
  tree_temp_node_allocate(&group1, parentNode->snodeSize);
  tree_temp_node_allocate(&group2, parentNode->snodeSize);

  
  sort_entries(sorted_index, overnode, axis_chosen, noOfOver);   // sort the entries by the axis, axis_chosen


  new_overlap_value = 0.0;  
  // *** Ray has changed
  //stop = M - 2*m + 1;
  stop = M*parentNode->snodeSize - 2*m + 1;
  for (k=0; k<stop; k++) {

	for (i=0; i<dim; i++) {
		group1->a[i] = overnode[sorted_index[0]]->a[i];
		group1->b[i] = overnode[sorted_index[0]]->b[i];
		// *** Ray changed
		//group2->a[i] = overnode[sorted_index[M]]->a[i];
		//group2->b[i] = overnode[sorted_index[M]]->b[i];
		group2->a[i] = overnode[sorted_index[M*parentNode->snodeSize]]->a[i];
		group2->b[i] = overnode[sorted_index[M*parentNode->snodeSize]]->b[i];
	}


	cut = m + k; 
	// *** Ray changed
	//for (j=0; j<M+1; j++) {
	for (j=0; j<M*parentNode->snodeSize+1; j++) {
  
		if (j < cut) {
  
			cal_MBR_node_node(group1->a, group1->b, group1, overnode[sorted_index[j]]);
                        
		}
		else {
                        	
			cal_MBR_node_node(group2->a, group2->b, group2, overnode[sorted_index[j]]);
  
		}

	}

	new_overlap_value = cal_overlap(group1, group2);
 
        
	if (k == 0) {   

		split_index = k;
		min_overlap_value = new_overlap_value;
		vol_at_index = cal_vol(group1->a, group1->b) + cal_vol(group2->a, group2->b);

  	}
	else {   
                
		if (new_overlap_value < min_overlap_value) {

			split_index = k;
			min_overlap_value = new_overlap_value;
			vol_at_index = cal_vol(group1->a, group1->b) + cal_vol(group2->a, group2->b);

		}
		else {

			new_vol = cal_vol(group1->a, group1->b) + cal_vol(group2->a, group2->b);
			if (new_vol < vol_at_index) {
				split_index = k;
			}

		}
  	}

  }

	
  for (i=0; i<dim; i++) {
	group1_chosen->a[i] = overnode[sorted_index[0]]->a[i];
	group1_chosen->b[i] = overnode[sorted_index[0]]->b[i];
	// *** Ray changed
	//group2_chosen->a[i] = overnode[sorted_index[M]]->a[i];
	//group2_chosen->b[i] = overnode[sorted_index[M]]->b[i];
	group2_chosen->a[i] = overnode[sorted_index[M*parentNode->snodeSize]]->a[i];
	group2_chosen->b[i] = overnode[sorted_index[M*parentNode->snodeSize]]->b[i];
  }


  cut = m + split_index;

  // *** Ray changed
  //for (j=0; j<M+1; j++) {
  for (j=0; j<M*parentNode->snodeSize+1; j++) {


	if (j < cut) {
                
		group1_chosen->ptr[j] = overnode[sorted_index[j]];

		overnode[sorted_index[j]]->parent = group1_chosen;
		cal_MBR_node_node(group1_chosen->a, group1_chosen->b, group1_chosen, overnode[sorted_index[j]]);
	}


	else {

		group2_chosen->ptr[j-cut] = overnode[sorted_index[j]];
                overnode[sorted_index[j]]->parent = group2_chosen;
                cal_MBR_node_node(group2_chosen->a, group2_chosen->b, group2_chosen, overnode[sorted_index[j]]);
	}

  }       


  // *** Ray changed
  //group1_chosen->vacancy = M - cut;
  //group2_chosen->vacancy = cut - 1;	// M - (M+1 - cut);
  if (cut%M == 0)
  {
	group1_chosen->vacancy = 0;
	group2_chosen->vacancy = M-1;

	group1_chosen->snodeSize = cut/M;
	group2_chosen->snodeSize = parentNode->snodeSize + 1 - group1_chosen->snodeSize;
  }
  else
  {
	group1_chosen->vacancy = M - cut%M;
	group2_chosen->vacancy = cut%M - 1;	// M - (M+1 - cut);

	group1_chosen->snodeSize = cut/M + 1;
	group2_chosen->snodeSize = parentNode->snodeSize + 1 - group1_chosen->snodeSize;
  }

  tree_node_deallocate(group1);
  tree_node_deallocate(group2);
  free(sorted_index);

                       
  return;
        
} /* ChooseSplitIndex() */


























/*