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 */     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;   }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);          }     }/* I think it is sorted in increasing order */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;}/* Sort an array in increasing order according to a set of centroid along the axis */void sort_entries_centroid(int *sorted_index, node_type **overnode, int axis_sort){  double *value;  int i;  value = (double *)malloc(sizeof(double) * M+1);  if (overnode[0]->attribute == LEAF) {  	for (i=0; i<= M; i++) {		sorted_index[i] = i;		value[i] = (double)overnode[i]->a[axis_sort];	}  } else {  	for (i=0; i<= M; i++) {		sorted_index[i] = i;		value[i] = (double)overnode[i]->centroid[axis_sort];	}  }  quicksort(sorted_index, value, 0, M);  free(value);  return;} /* sort_entries_centroid */void sort_entries(int *sorted_index, node_type **overnode, int axis_sort){  int i, start, end;  double *value;  value = (double *)malloc(sizeof(double) * M+1);  for (i=0; i<M+1; i++) {	sorted_index[i] = i;	value[i] = (double)overnode[i]->a[axis_sort];  }  quicksort(sorted_index, value, 0, M);  i = 0;  while (i<M) {	if (value[i] == value[i+1]) {		start = i;		while (i < M && 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;} /* sort_entries *//* Choose the split axis by maximizing the variance */int ChooseSplitAxisByVariance(node_type **overnode){  int axis_chosen;  double max_variance = -1.0;  double mean;  double variance;  int i, j;  if (overnode[0]->attribute == LEAF) {  	for (i=0; i<dim; i++) {		mean = 0.0;		for (j=0; j <= M; j++) 			mean += overnode[j]->a[i];		mean /= M;		variance = 0.0;		for (j=0; j <= M; j++) 			variance += pow(overnode[j]->a[i] - mean, 2.0);		if (max_variance < variance)			axis_chosen = i;  	}  } else {  	for (i=0; i<dim; i++) {		mean = 0.0;		for (j=0; j <= M; j++) 			mean += overnode[j]->centroid[i];		mean /= M;		variance = 0.0;		for (j=0; j <= M; j++) 			variance += pow(overnode[j]->centroid[i] - mean, 2.0);		if (max_variance < variance)			axis_chosen = i;	}  }  return(axis_chosen);} /* ChooseSplitAxisByVariance */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;  sorted_index = (int *)malloc(sizeof(int) * M+1);  tree_node_allocate(&group1);  tree_node_allocate(&group2);  for (i=0; i<dim; i++) {	sort_entries(sorted_index, overnode, i);   // sort the entries by axis i	new_margin_value = 0.0;	stop = M - 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];        	        group2->a[l] = overnode[sorted_index[M]]->a[l];                	group2->b[l] = overnode[sorted_index[M]]->b[l];        	}        		j = 0;		cut = m + k;		while (j < M+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 *//* Find the splitting index by minimizing the sum of variances on each side of the split */void ChooseSplitIndexByVariance(node_type **overnode, int axis_chosen, node_type *group1_chosen, node_type *group2_chosen){  int split_index, *sorted_index;  int i, j, k, stop, cut;  double mean1;  double mean2;  double sum_variance;  double min_variance = FLT_MAX;                          sorted_index = (int *)malloc(sizeof(int) * M+1);  // sort the entries by the centroid along the chosen axis  sort_entries_centroid(sorted_index, overnode, axis_chosen);     stop = M - 2*m + 1;  if (overnode[0]->attribute == LEAF) {  	for (k=0; k <= stop; k++) {		cut = m + k;		mean1 = 0.0;		mean2 = 0.0;		sum_variance = 0.0;		for (j=0; j < cut; j++)			mean1 += overnode[sorted_index[j]]->a[axis_chosen];		for (; j <= M; j++)			mean2 += overnode[sorted_index[j]]->a[axis_chosen];		mean1 /= cut;		mean2 /= M + 1 - cut;		for (j=0; j < cut; j++) 			sum_variance += pow(overnode[sorted_index[j]]->a[axis_chosen] - mean1, 2.0);		for (; j <= M; j++)			sum_variance += pow(overnode[sorted_index[j]]->a[axis_chosen] - mean2, 2.0);		if (min_variance > sum_variance) {			min_variance = sum_variance;			split_index = cut;			}	}  } else {  	for (k=0; k <= stop; k++) {		cut = m + k;		mean1 = 0.0;		mean2 = 0.0;		sum_variance = 0.0;		for (j=0; j < cut; j++)			mean1 += overnode[sorted_index[j]]->centroid[axis_chosen];		for (; j <= M; j++)			mean2 += overnode[sorted_index[j]]->centroid[axis_chosen];			mean1 /= cut;		mean2 /= M + 1 - cut;		for (j=0; j < cut; j++) 			sum_variance += pow(overnode[sorted_index[j]]->centroid[axis_chosen] - mean1, 2.0);		for (; j <= M; j++)			sum_variance += pow(overnode[sorted_index[j]]->centroid[axis_chosen] - mean2, 2.0);		if (min_variance > sum_variance) {			min_variance = sum_variance;			split_index = cut;			}	}  }  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];	group2_chosen->a[i] = overnode[sorted_index[M]]->a[i];	group2_chosen->b[i] = overnode[sorted_index[M]]->b[i];  }  cut = split_index;  for (j=0; j<M+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]]);	}  }         group1_chosen->vacancy = M - cut;  group2_chosen->vacancy = cut - 1;	// M - (M+1 - cut);  update_centroid_node(group1_chosen);  update_radius_node(group1_chosen);  update_centroid_node(group2_chosen);  update_radius_node(group2_chosen);  free(sorted_index);  return;        } /* ChooseSplitIndexByVariance */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;                            sorted_index = (int *)malloc(sizeof(int) * M+1);  tree_node_allocate(&group1);  tree_node_allocate(&group2);    sort_entries(sorted_index, overnode, axis_chosen);   // sort the entries by the axis, axis_chosen  new_overlap_value = 0.0;    stop = M - 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];		group2->a[i] = overnode[sorted_index[M]]->a[i];		group2->b[i] = overnode[sorted_index[M]]->b[i];	}	cut = m + k; 	for (j=0; j<M+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];	group2_chosen->a[i] = overnode[sorted_index[M]]->a[i];	group2_chosen->b[i] = overnode[sorted_index[M]]->b[i];  }  cut = m + split_index;  for (j=0; j<M+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]]);	}  }         group1_chosen->vacancy = M - cut;  group2_chosen->vacancy = cut - 1;	// M - (M+1 - cut);  tree_node_deallocate(group1);  tree_node_deallocate(group2);  free(sorted_index);                         return;        } /* ChooseSplitIndex() */void split(node_type *splitting_node, node_type *extra_node, node_type *node1, node_type *node2) {  node_type **overnode;  int axis_chosen;  int i;  overnode = (node_type **)malloc((M+1) * sizeof(node_type *));  for (i=0; i<M; i++) {        overnode[i] = splitting_node->ptr[i];  }  overnode[M] = extra_node;  for(i=0; i < M; i++) {        node1->ptr[i]=NULL;        node2->ptr[i]=NULL;  }  //axis_chosen = ChooseSplitAxis(overnode);  axis_chosen = ChooseSplitAxisByVariance(overnode);  //ChooseSplitIndex(overnode, axis_chosen, node1, node2);  ChooseSplitIndexByVariance(overnode, axis_chosen, node1, node2);  node1->attribute = NODE;  node1->parent = splitting_node->parent;  node1->id = NO_ID;  node2->attribute = NODE;  node2->parent = splitting_node->parent;  node2->id = NO_ID;  free(overnode);  return;} /* split() */void adjust_tree(node_type *splitting_node, int over_level, int old_level, node_type *node1, node_type *node2, node_type *root) {  int split_child_no = 0;  node_type *split_parent;  int i, j;  if(splitting_node->attribute == ROOT) { 	/* The splitting node is the root */	node1->parent = root;	node2->parent = root;	root->ptr[0] = node1;	root->ptr[1] = node2;	for (j=2; j<M; j++) 		root->ptr[j] = NULL;	root->parent = NULL;	root->vacancy=M-2;	root->attribute=ROOT;	cal_MBR_node_node(root->a, root->b, node1, node2);	update_centroid_node(root);	update_radius_node(root);	extra_level++;	//printf("grow!!!!!!!!!!!!\n");  }  else { 	/* The splitted is an intermediate node */	split_parent = splitting_node->parent;        for(i=0; i < M; i++) {		if(split_parent->ptr[i] == splitting_node) { 			split_child_no = i;	             	break;		}        }	tree_node_deallocate(splitting_node);		/* insert first node */	split_parent->ptr[split_child_no] = node1;	node1->parent = split_parent;	adjust_MBR_delete(node1);	/* insert second node */		if(split_parent->vacancy != 0) { 		/* no need to split again */           	split_parent->ptr[M - split_parent->vacancy] = node2;		node2->parent = split_parent;		split_parent->vacancy--;		//cal_MBR_node_node(split_parent->a, split_parent->b, node1, split_parent);		cal_MBR_node_node(split_parent->a, split_parent->b, node2, split_parent);		adjust_MBR(split_parent);		update_centroid(node2);	}       	else { 		update_centroid(node1);		// Ling		/* need to split again */		overflow(split_parent, over_level-1, old_level, node2, root);	}  }  return;} /* adjust_tree */void choose_leaf_level(node_type **node_found, node_type *current_node, int current_level, node_type *inserted_node, int desired_level) {   int child_chosen;  if (current_level == desired_level) {        *node_found = current_node;        return;  }    //printf("current_level %d desired_level %d\n", current_level, desired_level);  //printf("current_node->ptr[0]->ptr[0] %d\n", current_node->ptr[0]->ptr[0]);  //if (current_node->ptr[0]->ptr[0]->attribute != LEAF) {  if (inserted_node->attribute != LEAF) {    	child_chosen = nearest_centroid(current_node, inserted_node->centroid);        //child_chosen = least_area_enlarge(current_node, inserted_node);  }  else {  	child_chosen = nearest_centroid(current_node, inserted_node->a);        //child_chosen = least_overlap_enlarge(current_node, inserted_node);  }  current_node = current_node->ptr[child_chosen];  //printf("current_level %d desired_level %d\n", current_level, desired_level);  choose_leaf_level(node_found, current_node, current_level+1, inserted_node, desired_level);    return;                        } /* choose_leaf_level */