PR-Tree

[algatt]

Hello, I am trying to code a PR-Tree which is basically a multi-
dimensional index, but I have some problems with the QuickSort,
because it's crashing. Here's my code any help is appreciated.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DIMS 4 //number of dimensions
#define RECTS 4 //number of rectangles stored in each leaf

FILE *inputFile; //the file from where data is loaded

//structure used to store the head and the tail of the loaded
//data along with the total number of nodes
typedef struct matrix {
struct nodes *head;
struct nodes *tail;
int numNodes;
} matrix;

//structure to store each shape
typedef struct nodes {
int v[DIMS]; //the value of each point i.e. if DIMS=4 x1, y1, x2,
y2
struct nodes *next; //pointer to next node
struct nodes *prev; //pointer to previous node
int rid; //unique ID assigned to each shape
int used; //0=not inserted in PR-Tree | 1=inserted in PR-Tree
struct nodes *x[DIMS]; //this will store the pointers to sort on each
dimension
} nodes;

//structure to store each point of a shape
typedef struct rect {
int points[DIMS];
} rect;

//structure for pseudo-PR-Tree
typedef struct pseudoPR {
rect point[DIMS][RECTS];//stores the points for each rectangle
struct pseudoPR *left; //pointer to next one
struct pseudoPR *right; //pointer to previous one
rect mbb; //stores minimum bounding box of combined leaves
int level; //determine the level of the pseudo-PR-Tree
int numnodes; //number of nodes
} pseudoPR;

typedef struct lrPointers{
struct lrPointers *next;
struct lrPointers *prev;
pseudoPR *addr;
int level;
} lrPointers;

typedef struct lrHead{
struct lrPointers *head;
struct lrPointers *tail;
} lrHead;


matrix *list;

nodes *dimHeads[DIMS][2];

pseudoPR *ppr;

lrHead *lrp;

clock_t cStart;


//start is passed, then subtracted from the current time to obtain
duration in seconds
void showTime (clock_t start)
{
printf(" || in %fs.\n",((double)clock()-start / (CLOCKS_PER_SEC
*1000)) /1000);
}

//checks the file location from where to load information
int loadFile(char *location)
{
inputFile = fopen(location,"r");

if (!inputFile)
{
printf("\nERROR: Invalid source file path.");
return 0;
}
else
{
printf("\nOK: Input file found.");
return 1;
}

}

//used to fill up matrix with information read from file
void loadMatrix(){

char buffer [1000];
int j;

cStart=clock();

while (fgets(buffer,sizeof(buffer),inputFile))
{
nodes *tNode = malloc(sizeof *tNode);

//a new node is created for each dimension
for (j=0; j<DIMS; j++)
tNode->x[j]=malloc(sizeof *tNode->x[j]);

//values are loaded from file into the node
sscanf(buffer,"%d%d%d%d",&tNode->v[0],&tNode->v[1],&tNode-

v[2],&tNode->v[3]);

//rid is assigned as next in line number
tNode->rid=list->numNodes;
tNode->used=0;

if (list->head==NULL){ //if list is still empty

//set sorting nodes to NULL
for (j=0; j<DIMS; j++){
tNode->x[j]->prev=0;
tNode->x[j]->next=0;
}

//fill in first node being the same as the head and tail
list->head=list->tail=tNode;
list->head->next=list->tail->prev=NULL;
list->numNodes++;

} else { // if list is not empty
for (j=0; j<DIMS; j++) {
tNode->x[j]->prev=list->tail;
tNode->x[j]->prev->x[j]->next=tNode;
}
tNode->prev=list->tail;
list->tail->next=tNode;
list->tail=tNode;
list->numNodes++;
}

} //end reading file

//set the head and tail of each dimension to the current head and
tail
for (j=0; j<DIMS; j++){
dimHeads[j][0]=list->head;
dimHeads[j][1]=list->tail;
}

printf("\nOK: %d records inserted in list", list->numNodes);

showTime(cStart);

}


//simply prints the original list
void printList(){

cStart=clock();

nodes *tNode = malloc(sizeof *tNode);

tNode=list->head;

int i;

printf("\nOutput Original List");
printf("\nID\t RID\t Used\t Prev\t Next\t Point Values");

while (tNode!=NULL ){
printf("\n%d\t %d\t %d\t %d\t %d\t",(int)tNode,tNode->rid,tNode-

used,(int)tNode->prev,(int)tNode->next);

for (i=0; i<DIMS; i++){
printf("%d ",tNode->v);
};

tNode=tNode->next;

}

printf("\nOK: Original list printed");
showTime(cStart);

}

//prints a sorted list; variable which must be assigned a node
(usually the head dimension to be printed)
//and variable point specifies which dimension to be printed 0=x1,
1=y1, 2=x2, 3=y2, etc...
void printSortList(nodes *which, int point){

cStart = clock();

nodes *tNode = malloc(sizeof *tNode);

if (tNode==NULL) {
printf("\nERROR: Empty List.");
return;
}

tNode=which;

int i=0;

while (tNode!=NULL)
{
printf("\n%d\t %d\t %d\t %d\t",(int)tNode,tNode->rid,(int)tNode-

x[0]->prev,(int)tNode->x[0]->next);

for (i=0; i<DIMS; i++)
printf("\t%d",tNode->v);

tNode=tNode->x[point]->next;

}

printf("\nOK: Printed Ordered Lists");
showTime(cStart);

}

void nodeSwap(nodes *nt1, nodes *nt2, int point)
//n1 is left, n2 is right
{
nodes *nt1_prev, *nt1_next;
nodes *nt2_prev, *nt2_next;
int j=point;

nt1_prev = nt1->x[j]->prev;
nt1_next = nt1->x[j]->next;
nt2_prev = nt2->x[j]->prev;
nt2_next = nt2->x[j]->next;

//nodes to swap are head and tail
if ( (nt1->x[j]->prev==NULL) && (nt2->x[j]->next==NULL) ){
nt1->x[j]->prev=nt2_prev;
nt1->x[j]->next=NULL;
nt2->x[j]->next=nt1_next;
nt2->x[j]->prev=NULL;
nt2_prev->x[j]->next=nt1;
dimHeads[j][0]=nt2;
dimHeads[0][1]=nt1;

//nodes to swap are head and not tail
} else if ( (nt1->x[j]->prev==NULL) && (nt2->x[j]->next!=NULL))
{
//if the next node is immediately after head
if (nt1->x[j]->next==nt2){

nt1->x[j]->next=nt2_next;
nt1->x[j]->prev=nt2;
nt2->x[j]->prev=NULL;
nt2->x[j]->next=nt1;
nt2_next->x[j]->prev=nt1;

//if the next node is far away from head
} else {
nt1_next->x[j]->prev=nt2;
nt2_prev->x[j]->next=nt1;
nt1->x[j]->prev=nt2->x[j]->prev;
nt1->x[j]->next=nt2->x[j]->next;
nt2->x[j]->prev=NULL;
nt2->x[j]->next=nt1_next;
}

dimHeads[j][0]=nt2;
}
//first node is not head and the second node is tail
else if ( (nt1->x[j]->prev!=NULL) && (nt2->x[j]->next==NULL))
{

//if the first node is immediately before tail
if (nt1->x[j]->next==nt2){

nt1->x[j]->next=NULL;
nt1->x[j]->prev=nt2;
nt1_prev->x[j]->next=nt2;
nt2->x[j]->prev=nt1_prev;
nt2->x[j]->next=nt1;

}
//if first node and tail are far away
else {

nt1_next->x[j]->prev=nt2;
nt1_prev->x[j]->next=nt2;
nt2_prev->x[j]->next=nt1;
nt1->x[j]->prev=nt2->x[j]->prev;
nt1->x[j]->next=NULL;
nt2->x[j]->prev=nt1_prev;
nt2->x[j]->next=nt1_next;
}


dimHeads[j][1]=nt1;



}
//both nodes are not head nor tail and next to each other
else if (nt1->x[j]->next == nt2) {
nt2->x[j]->prev=nt1_prev;
nt2->x[j]->next=nt1;
nt1->x[j]->next=nt2_next;

nt1->x[j]->prev=nt2;

nt1_prev->x[j]->next=nt2;
nt2_next->x[j]->prev=nt1;



}
//both nodes are not head nor tail and are far away
else {
nt1_prev->x[j]->next=nt2;
nt1_next->x[j]->prev=nt2;
nt2_prev->x[j]->next=nt1;
nt2_next->x[j]->prev=nt1;

nt1->x[j]->next=nt2_next;
nt1->x[j]->prev=nt2_prev;

nt2->x[j]->next=nt1_next;
nt2->x[j]->prev=nt2_prev;

}

}


//simple BubbleSort
void sort(int point)
{

int changed = 0;
int j = point;


nodes *tNode = dimHeads[j][0];

cStart=clock();

while (tNode->x[j]->next){

if ( ((tNode->v[j] > tNode->x[j]->next->v[j]) && (point<(DIMS+1)/2))
|| ((tNode->v[j] < tNode->x[j]->next->v[j]) && (point>=(DIMS+1)/2)))
{
nodes *c2 = tNode->x[j]->next;

nodeSwap(tNode,tNode->x[j]->next,j);

tNode=c2;

changed=1;

} else
tNode = tNode->x[j]->next;
}

if (changed==1)
sort(j);


}

//calls sort [BubbleSort] for all dimensions
void sortAll(){

cStart=clock();

int j;

for (j=0; j<DIMS; j++)
sort(j);


printf("\nOK: List sorted");
showTime(cStart);

}

//prints the list sorted in all dimensions
void printAll(){

if (list->head==NULL){
printf("\nERROR: Empty List.");
return;
}

cStart=clock();

int j;

for (j=0; j<DIMS; j++){
printf("\nSorted Point [%d]",j+1);
if (j<(DIMS+1)/2)
printf(" in ASC order");
else
printf(" in DES order");
printSortList(dimHeads[j][0],j);
printf("\n");
}

printf("\nOK: %d lists printed",DIMS);
showTime(cStart);
}

//delete a node from a list
void delNode(nodes *dNode){

int i=0;

if (list->numNodes==1){
for (i=0; i<DIMS; i++){

dimHeads[0]=NULL;
dimHeads[1]=NULL;
}
list->head=list->tail=NULL;
list->numNodes=0;
return;

}

list->numNodes--;

for (i=0; i<DIMS; i++){
if (dNode==dimHeads[0])
{
dimHeads[0]=dNode->x->next;
dNode->x->next->x->prev=NULL;
}

else if (dNode==dimHeads[1]){
dNode->x->prev->x->next=NULL;
dimHeads[1]=dNode->x->prev;
}
else {
dNode->x->prev->x->next=dNode->x->next;
dNode->x->next->x->prev=dNode->x->prev;
}
}


if (dNode==list->head)
{
list->head=dNode->next;
dNode->next->prev=NULL;
} else if (dNode==list->tail)
{
list->tail=dNode->prev;
dNode->prev->next=NULL;
} else {
dNode->prev->next=dNode->next;
dNode->next->prev=dNode->prev;
}

}



//create the first Pseudo-PR-Tree

void pcr(pseudoPR *pr){

lrPointers *rh = malloc(sizeof *rh);
nodes *tmp = malloc(sizeof *tmp);

rh=lrp->head;

int i=0;
int j=0;
int k;
int maxlevel = lrp->head->level;


pr=rh->addr;

tmp=dimHeads[0];

pr->mbb.points[0]=tmp->v[0];
pr->mbb.points[1]=tmp->v[1];
pr->mbb.points[2]=tmp->v[2];
pr->mbb.points[3]=tmp->v[3];


while ( (pr->numnodes>0) && (i<DIMS) )
{
tmp=dimHeads[0];

j=0;


while ( (j<RECTS) && (list->head!=NULL) )
{


for (k=0; k<DIMS; k++){
pr->point[j].points[k]=tmp->v[k];

if (k < (int)DIMS/2)
{
if (tmp->v[k] < pr->mbb.points[k])
pr->mbb.points[k]=tmp->v[k];
}
else {
if (tmp->v[k] > pr->mbb.points[k])
pr->mbb.points[k]=tmp->v[k];
}


}




j++;

if (tmp->x->next!=NULL){
tmp=tmp->x->next;
delNode(tmp->x->prev);
pr->numnodes--;
} else {
delNode(tmp);
pr->numnodes--;
}

}

i++;

}


if (pr->numnodes>0){

if (pr->numnodes <= RECTS*4)
{
pseudoPR *tempPPR = malloc(sizeof *tempPPR);
lrPointers *tempLR = malloc(sizeof *tempLR);

tempPPR->left=NULL;
tempPPR->right=NULL;
tempPPR->level=maxlevel+1;
tempPPR->numnodes=pr->numnodes;
pr->left=tempPPR;

tempLR->addr=tempPPR;
tempLR->level=tempPPR->level;
tempLR->next=NULL;
tempLR->prev=lrp->tail;

lrp->tail->next=tempLR;
} else {

int n1 = (int)(pr->numnodes/2);
int n2 = (pr->numnodes)-n1;

pseudoPR *tempPPR = malloc(sizeof *tempPPR);
pseudoPR *tempPPR2 = malloc(sizeof *tempPPR2);
lrPointers *tempLR = malloc(sizeof *tempLR);
lrPointers *tempLR2 = malloc(sizeof *tempLR2);

tempPPR->left=NULL;
tempPPR2->left=NULL;

tempPPR->right=NULL;
tempPPR2->right=NULL;

tempPPR->level=maxlevel+1;
tempPPR2->level=maxlevel+1;

tempPPR->numnodes=n1;
tempPPR2->numnodes=n2;

pr->left=tempPPR;
pr->right=tempPPR2;

tempLR->addr=tempPPR;
tempLR2->addr=tempPPR2;

tempLR->level=tempPPR->level;
tempLR2->level=tempPPR->level;

tempLR->next=tempLR2;
tempLR2->prev=tempLR;
lrp->tail->next=tempLR;
tempLR2->next=NULL;


}
}

if(lrp->head->next==NULL)
{
lrp->head=lrp->tail=NULL;
} else {
lrp->head->next->prev=NULL;
lrp->head=lrp->head->next;

}

}

//must be fixed
void printPseudo(pseudoPR *pr){

printf("\nID [%d] \t Level [%d] \t Left [%d] \tRight [%d]",(int)pr,pr-

level,(int)pr->left,(int)pr->right);

int i,j,k;
for (k=0; k<DIMS; k++){
printf("\n");
for (j=0; j<RECTS; j++){

printf("\n [");
for (i=0; i<DIMS; i++){
printf("%d ",pr->point[k][j].points);
}
printf("]");
}
}

printf(" MBB = [%d %d %d %d]",pr->mbb.points[0],pr->mbb.points[1],pr-

mbb.points[2],pr->mbb.points[3]);

if ( (pr->left!=NULL)) printPseudo(pr->left);
if ( (pr->right!=NULL)) printPseudo(pr->right);

}

//does not work
void quickSort(struct nodes *left, struct nodes *right, int which){

if (left==right)
return;

nodes *start = left;
nodes *current = start->x[0]->next;

int pass = 0;

while (1)
{

if (start->v[0] > current->v[0])
nodeSwap(start,current,0);


if (current==right)
break;

current=current->x[0]->next;
if (current==left) pass=1;
};


if (!pass)
nodeSwap(left,current,0);
else
nodeSwap(current,left,0);


nodes *oCurrent = current;

current=current->x[0]->prev;

if (current!=NULL)
if ((left->x[0]->prev!=current) && (current->x[0]->next!=left))
quickSort(left,current,0);

current=oCurrent;
current=current->x[0]->next;

if (current!=NULL)
if ((current->x[0]->prev!=right) && (right->x[0]->next!=current))
quickSort(current,right,0);

};




int main(){

loadFile("c:/r.txt");

list = malloc(sizeof *list);
list->head=list->tail=NULL;
list->numNodes=0;

loadMatrix();
printList();
sortAll();

ppr = malloc(sizeof *ppr);
ppr->left=NULL;
ppr->right=NULL;
ppr->numnodes=list->numNodes;
ppr->level=0;

lrp = malloc(sizeof *lrp);

lrPointers *tLR = malloc(sizeof *tLR);
tLR->addr=ppr;
tLR->next=NULL;
tLR->prev=NULL;
tLR->level=ppr->level;
lrp->head=tLR;
lrp->tail=tLR;

printAll();

cStart = clock();
while (lrp->head!=NULL)
{
pcr(lrp->head->addr);
}
printf ("\nOK: Pseudo PR-Tree created ");
showTime(cStart);

printPseudo(ppr);


free(list);
free(ppr);

return 0;
}

Thank You.

 

[Richard Heathfield]

algatt said:

Hello, I am trying to code a PR-Tree which is basically a multi-
dimensional index, but I have some problems with the QuickSort,
because it's crashing. Here's my code any help is appreciated.

In all the cases I happened to see where you allocate memory, you appear to
assume that the allocation succeeded. It may well be that this assumption
is false, and that could certainly explain your crashes.

 

[GeorgeRXZ]

Hello, I am trying to code a PR-Tree which is basically a multi-
dimensional index, but I have some problems with the QuickSort,
because it's crashing. Here's my code any help is appreciated.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DIMS 4 //number of dimensions
#define RECTS 4 //number of rectangles stored in each leaf

FILE *inputFile; //the file from where data is loaded

//structure used to store the head and the tail of the loaded
//data along with the total number of nodes
typedef struct matrix {
struct nodes *head;
struct nodes *tail;
int numNodes;

} matrix;

//structure to store each shape
typedef struct nodes {
int v[DIMS]; //the value of each point i.e. if DIMS=4 x1, y1, x2,
y2
struct nodes *next; //pointer to next node
struct nodes *prev; //pointer to previous node
int rid; //unique ID assigned to each shape
int used; //0=not inserted in PR-Tree | 1=inserted in PR-Tree
struct nodes *x[DIMS]; //this will store the pointers to sort on each
dimension

} nodes;

//structure to store each point of a shape
typedef struct rect {
int points[DIMS];

} rect;

//structure for pseudo-PR-Tree
typedef struct pseudoPR {
rect point[DIMS][RECTS];//stores the points for each rectangle
struct pseudoPR *left; //pointer to next one
struct pseudoPR *right; //pointer to previous one
rect mbb; //stores minimum bounding box of combined leaves
int level; //determine the level of the pseudo-PR-Tree
int numnodes; //number of nodes

} pseudoPR;

typedef struct lrPointers{
struct lrPointers *next;
struct lrPointers *prev;
pseudoPR *addr;
int level;

} lrPointers;

typedef struct lrHead{
struct lrPointers *head;
struct lrPointers *tail;

} lrHead;

matrix *list;

nodes *dimHeads[DIMS][2];

pseudoPR *ppr;

lrHead *lrp;

clock_t cStart;

//start is passed, then subtracted from the current time to obtain
duration in seconds
void showTime (clock_t start)
{
printf(" || in %fs.\n",((double)clock()-start / (CLOCKS_PER_SEC
*1000)) /1000);

}

//checks the file location from where to load information
int loadFile(char *location)
{
inputFile = fopen(location,"r");

if (!inputFile)
{
printf("\nERROR: Invalid source file path.");
return 0;
}
else
{
printf("\nOK: Input file found.");
return 1;
}

}

//used to fill up matrix with information read from file
void loadMatrix(){

char buffer [1000];
int j;

cStart=clock();

while (fgets(buffer,sizeof(buffer),inputFile))
{
nodes *tNode = malloc(sizeof *tNode);

//a new node is created for each dimension
for (j=0; j<DIMS; j++)
tNode->x[j]=malloc(sizeof *tNode->x[j]);

//values are loaded from file into the node
sscanf(buffer,"%d%d%d%d",&tNode->v[0],&tNode->v[1],&tNode-

v[2],&tNode->v[3]);

//rid is assigned as next in line number
tNode->rid=list->numNodes;
tNode->used=0;

if (list->head==NULL){ //if list is still empty

//set sorting nodes to NULL
for (j=0; j<DIMS; j++){
tNode->x[j]->prev=0;
tNode->x[j]->next=0;
}

//fill in first node being the same as the head and tail
list->head=list->tail=tNode;
list->head->next=list->tail->prev=NULL;
list->numNodes++;

} else { // if list is not empty
for (j=0; j<DIMS; j++) {
tNode->x[j]->prev=list->tail;
tNode->x[j]->prev->x[j]->next=tNode;
}
tNode->prev=list->tail;
list->tail->next=tNode;
list->tail=tNode;
list->numNodes++;
}

} //end reading file

//set the head and tail of each dimension to the current head and
tail
for (j=0; j<DIMS; j++){
dimHeads[j][0]=list->head;
dimHeads[j][1]=list->tail;
}

printf("\nOK: %d records inserted in list", list->numNodes);

showTime(cStart);

}

//simply prints the original list
void printList(){

cStart=clock();

nodes *tNode = malloc(sizeof *tNode);

tNode=list->head;

int i;

printf("\nOutput Original List");
printf("\nID\t RID\t Used\t Prev\t Next\t Point Values");

while (tNode!=NULL ){
printf("\n%d\t %d\t %d\t %d\t %d\t",(int)tNode,tNode->rid,tNode-

used,(int)tNode->prev,(int)tNode->next);

for (i=0; i<DIMS; i++){
printf("%d ",tNode->v);
};

tNode=tNode->next;

}

printf("\nOK: Original list printed");
showTime(cStart);

}

//prints a sorted list; variable which must be assigned a node
(usually the head dimension to be printed)
//and variable point specifies which dimension to be printed 0=x1,
1=y1, 2=x2, 3=y2, etc...
void printSortList(nodes *which, int point){

cStart = clock();

nodes *tNode = malloc(sizeof *tNode);

if (tNode==NULL) {
printf("\nERROR: Empty List.");
return;
}

tNode=which;

int i=0;

while (tNode!=NULL)
{
printf("\n%d\t %d\t %d\t %d\t",(int)tNode,tNode->rid,(int)tNode-

x[0]->prev,(int)tNode->x[0]->next);

for (i=0; i<DIMS; i++)
printf("\t%d",tNode->v);

tNode=tNode->x[point]->next;

}

printf("\nOK: Printed Ordered Lists");
showTime(cStart);

}

void nodeSwap(nodes *nt1, nodes *nt2, int point)
//n1 is left, n2 is right
{
nodes *nt1_prev, *nt1_next;
nodes *nt2_prev, *nt2_next;
int j=point;

nt1_prev = nt1->x[j]->prev;
nt1_next = nt1->x[j]->next;
nt2_prev = nt2->x[j]->prev;
nt2_next = nt2->x[j]->next;

//nodes to swap are head and tail
if ( (nt1->x[j]->prev==NULL) && (nt2->x[j]->next==NULL) ){
nt1->x[j]->prev=nt2_prev;
nt1->x[j]->next=NULL;
nt2->x[j]->next=nt1_next;
nt2->x[j]->prev=NULL;
nt2_prev->x[j]->next=nt1;
dimHeads[j][0]=nt2;
dimHeads[0][1]=nt1;

//nodes to swap are head and not tail
} else if ( (nt1->x[j]->prev==NULL) && (nt2->x[j]->next!=NULL))
{
//if the next node is immediately after head
if (nt1->x[j]->next==nt2){

nt1->x[j]->next=nt2_next;
nt1->x[j]->prev=nt2;
nt2->x[j]->prev=NULL;
nt2->x[j]->next=nt1;
nt2_next->x[j]->prev=nt1;

//if the next node is far away from head
} else {
nt1_next->x[j]->prev=nt2;
nt2_prev->x[j]->next=nt1;
nt1->x[j]->prev=nt2->x[j]->prev;
nt1->x[j]->next=nt2->x[j]->next;
nt2->x[j]->prev=NULL;
nt2->x[j]->next=nt1_next;
}

dimHeads[j][0]=nt2;
}
//first node is not head and the second node is tail
else if ( (nt1->x[j]->prev!=NULL) && (nt2->x[j]->next==NULL))
{

//if the first node is immediately before tail
if (nt1->x[j]->next==nt2){

nt1->x[j]->next=NULL;
nt1->x[j]->prev=nt2;
nt1_prev->x[j]->next=nt2;
nt2->x[j]->prev=nt1_prev;
nt2->x[j]->next=nt1;

}
//if first node and tail are far away
else {

nt1_next->x[j]->prev=nt2;
nt1_prev->x[j]->next=nt2;
nt2_prev->x[j]->next=nt1;
nt1->x[j]->prev=nt2->x[j]->prev;
nt1->x[j]->next=NULL;
nt2->x[j]->prev=nt1_prev;
nt2->x[j]->next=nt1_next;
}

dimHeads[j][1]=nt1;

}
//both nodes are not head nor tail and next to each other
else if (nt1->x[j]->next == nt2) {
nt2->x[j]->prev=nt1_prev;
nt2->x[j]->next=nt1;
nt1->x[j]->next=nt2_next;

nt1->x[j]->prev=nt2;

nt1_prev->x[j]->next=nt2;
nt2_next->x[j]->prev=nt1;

}
//both nodes are not head nor tail and are far away
else {
nt1_prev->x[j]->next=nt2;
nt1_next->x[j]->prev=nt2;
nt2_prev->x[j]->next=nt1;
nt2_next->x[j]->prev=nt1;

nt1->x[j]->next=nt2_next;
nt1->x[j]->prev=nt2_prev;

nt2->x[j]->next=nt1_next;
nt2->x[j]->prev=nt2_prev;

}

}

//simple BubbleSort
void sort(int point)
{

int changed = 0;
int j = point;

nodes *tNode = dimHeads[j][0];

cStart=clock();

while (tNode->x[j]->next){

if ( ((tNode->v[j] > tNode->x[j]->next->v[j]) && (point<(DIMS+1)/2))
|| ((tNode->v[j] < tNode->x[j]->next->v[j]) && (point>=(DIMS+1)/2)))
{
nodes *c2 = tNode->x[j]->next;

nodeSwap(tNode,tNode->x[j]->next,j);

tNode=c2;

changed=1;

} else
tNode = tNode->x[j]->next;
}

if (changed==1)
sort(j);

}

//calls sort [BubbleSort] for all dimensions
void sortAll(){

cStart=clock();

int j;

for (j=0; j<DIMS; j++)
sort(j);

printf("\nOK: List sorted");
showTime(cStart);

}

//prints the list sorted in all dimensions
void printAll(){

if (list->head==NULL){
printf("\nERROR: Empty List.");
return;
}

cStart=clock();

int j;

for (j=0; j<DIMS; j++){
printf("\nSorted Point [%d]",j+1);
if (j<(DIMS+1)/2)
printf(" in ASC order");
else
printf(" in DES order");
printSortList(dimHeads[j][0],j);
printf("\n");
}

printf("\nOK: %d lists printed",DIMS);
showTime(cStart);

}

//delete a node from a list
void delNode(nodes *dNode){

int i=0;

if (list->numNodes==1){
for (i=0; i<DIMS; i++){

dimHeads[0]=NULL;
dimHeads[1]=NULL;
}
list->head=list->tail=NULL;
list->numNodes=0;
return;

}

list->numNodes--;

for (i=0; i<DIMS; i++){
if (dNode==dimHeads[0])
{
dimHeads[0]=dNode->x->next;
dNode->x->next->x->prev=NULL;
}

else if (dNode==dimHeads[1]){
dNode->x->prev->x->next=NULL;
dimHeads[1]=dNode->x->prev;
}
else {
dNode->x->prev->x->next=dNode->x->next;
dNode->x->next->x->prev=dNode->x->prev;
}
}

if (dNode==list->head)
{
list->head=dNode->next;
dNode->next->prev=NULL;
} else if (dNode==list->tail)
{
list->tail=dNode->prev;
dNode->prev->next=NULL;
} else {
dNode->prev->next=dNode->next;
dNode->next->prev=dNode->prev;
}

}

//create the first Pseudo-PR-Tree

void pcr(pseudoPR *pr){

lrPointers *rh = malloc(sizeof *rh);
nodes *tmp = malloc(sizeof *tmp);

rh=lrp->head;

int i=0;
int j=0;
int k;
int maxlevel = lrp->head->level;

pr=rh->addr;

tmp=dimHeads[0];

pr->mbb.points[0]=tmp->v[0];
pr->mbb.points[1]=tmp->v[1];
pr->mbb.points[2]=tmp->v[2];
pr->mbb.points[3]=tmp->v[3];

while ( (pr->numnodes>0) && (i<DIMS) )
{
tmp=dimHeads[0];

j=0;

while ( (j<RECTS) && (list->head!=NULL) )
{

for (k=0; k<DIMS; k++){
pr->point[j].points[k]=tmp->v[k];

if (k < (int)DIMS/2)
{
if (tmp->v[k] < pr->mbb.points[k])
pr->mbb.points[k]=tmp->v[k];
}
else {
if (tmp->v[k] > pr->mbb.points[k])
pr->mbb.points[k]=tmp->v[k];
}

}

j++;

if (tmp->x->next!=NULL){
tmp=tmp->x->next;
delNode(tmp->x->prev);
pr->numnodes--;
} else {
delNode(tmp);
pr->numnodes--;
}

}

i++;

}

if (pr->numnodes>0){

if (pr->numnodes <= RECTS*4)
{
pseudoPR *tempPPR = malloc(sizeof *tempPPR);
lrPointers *tempLR = malloc(sizeof *tempLR);

tempPPR->left=NULL;
tempPPR->right=NULL;
tempPPR->level=maxlevel+1;
tempPPR->numnodes=pr->numnodes;
pr->left=tempPPR;

tempLR->addr=tempPPR;
tempLR->level=tempPPR->level;
tempLR->next=NULL;
tempLR->prev=lrp->tail;

lrp->tail->next=tempLR;
} else {

int n1 = (int)(pr->numnodes/2);
int n2 = (pr->numnodes)-n1;

pseudoPR *tempPPR = malloc(sizeof *tempPPR);
pseudoPR *tempPPR2 = malloc(sizeof *tempPPR2);
lrPointers *tempLR = malloc(sizeof *tempLR);
lrPointers *tempLR2 = malloc(sizeof *tempLR2);

tempPPR->left=NULL;
tempPPR2->left=NULL;

tempPPR->right=NULL;
tempPPR2->right=NULL;

tempPPR->level=maxlevel+1;
tempPPR2->level=maxlevel+1;

tempPPR->numnodes=n1;
tempPPR2->numnodes=n2;

pr->left=tempPPR;
pr->right=tempPPR2;

tempLR->addr=tempPPR;
tempLR2->addr=tempPPR2;

tempLR->level=tempPPR->level;
tempLR2->level=tempPPR->level;

tempLR->next=tempLR2;
tempLR2->prev=tempLR;
lrp->tail->next=tempLR;
tempLR2->next=NULL;

}
}

if(lrp->head->next==NULL)
{
lrp->head=lrp->tail=NULL;
} else {
lrp->head->next->prev=NULL;
lrp->head=lrp->head->next;

}

}

//must be fixed
void printPseudo(pseudoPR *pr){

printf("\nID [%d] \t Level [%d] \t Left [%d] \tRight [%d]",(int)pr,pr->level,(int)pr->left,(int)pr->right);

int i,j,k;
for (k=0; k<DIMS; k++){
printf("\n");
for (j=0; j<RECTS; j++){

printf("\n [");
for (i=0; i<DIMS; i++){
printf("%d ",pr->point[k][j].points);
}
printf("]");
}
}

printf(" MBB = [%d %d %d %d]",pr->mbb.points[0],pr->mbb.points[1],pr-

mbb.points[2],pr->mbb.points[3]);

if ( (pr->left!=NULL)) printPseudo(pr->left);
if ( (pr->right!=NULL)) printPseudo(pr->right);

}

//does not work
void quickSort(struct nodes *left, struct nodes *right, int which){

if (left==right)
return;

nodes *start = left;
nodes *current = start->x[0]->next;

int pass = 0;

while (1)
{

if (start->v[0] > current->v[0])
nodeSwap(start,current,0);

if (current==right)
break;

current=current->x[0]->next;
if (current==left) pass=1;
};

if (!pass)
nodeSwap(left,current,0);
else
nodeSwap(current,left,0);

nodes *oCurrent = current;

current=current->x[0]->prev;

if (current!=NULL)
if ((left->x[0]->prev!=current) && (current->x[0]->next!=left))
quickSort(left,current,0);

current=oCurrent;
current=current->x[0]->next;

if (current!=NULL)
if ((current->x[0]->prev!=right) && (right->x[0]->next!=current))
quickSort(current,right,0);

};

int main(){

loadFile("c:/r.txt");

list = malloc(sizeof *list);
list->head=list->tail=NULL;
list->numNodes=0;

loadMatrix();
printList();
sortAll();

ppr = malloc(sizeof *ppr);
ppr->left=NULL;
ppr->right=NULL;
ppr->numnodes=list->numNodes;
ppr->level=0;

lrp = malloc(sizeof *lrp);

lrPointers *tLR = malloc(sizeof *tLR);
tLR->addr=ppr;
tLR->next=NULL;
tLR->prev=NULL;
tLR->level=ppr->level;
lrp->head=tLR;
lrp->tail=tLR;

printAll();

cStart = clock();
while (lrp->head!=NULL)
{
pcr(lrp->head->addr);
}
printf ("\nOK: Pseudo PR-Tree created ");
showTime(cStart);

printPseudo(ppr);

free(list);
free(ppr);

return 0;

}

Thank You.

you can find all tree related programs on following website.


http://zsoftwares.googlepages.com/BI_TRE.htm

http://zsoftwares.googlepages.com/BIN_SER.htm

Creation of Binary search tree and Preorder, Postorder, Inorder
http://zsoftwares.googlepages.com/prepost.htm

Binary search tree, Leaf nodes, Breadth first search algorithm.
http://zsoftwares.googlepages.com/BT_BFS.htm

For more C Source codes visit
http://zsoftwares.googlepages.com/CPrograms.html
For Data structure and file in C source codes
http://zsoftwares.googlepages.com/DSFPrograms.htm

Note: To run all the source programs given on above website you need
( OS : DOS/ or any version of Windows OS
and Turboc compiler or any windows compatible c language compiler)


GEOrgE

 

[Richard Heathfield]

GeorgeRXZ said:

you can find all tree related programs on following website.

(1) Please don't quote a 700-line message to write a dozen lines at the
bottom;
(2) please don't recommend broken code to people who are seeking help.

 

[Ben Bacarisse]

Hello, I am trying to code a PR-Tree which is basically a multi-
dimensional index, but I have some problems with the QuickSort,
because it's crashing.

Unless the problem is very simple, we will soon be stuck because:
(1) some of your lines have got wrapped so the code is not compilable;
(2) your program does not call quickSort; and
(3) your program needs input that is not provided.

If you can, post as short, compilable, version that exhibits the
problem. If it needs data, so do we! If possible, re-write it to
include the data.

 

[algatt]

Unless the problem is very simple, we will soon be stuck because:
(1) some of your lines have got wrapped so the code is not compilable;
(2) your program does not call quickSort; and
(3) your program needs input that is not provided.

If you can, post as short, compilable, version that exhibits the
problem. If it needs data, so do we! If possible, re-write it to
include the data.

Ok, here is the source code with the file it needs:

http://www.mediafire.com/?berlny9jvdx

In order to use quicksort this has to be typed in main

quickSort(dimheads[0][0],dimheads[0][1]);

Thanks

 

[Ben Bacarisse]

Please don't quote sigs (the part after, and including, the "-- ").

Ok, here is the source code with the file it needs:
http://www.mediafire.com/?berlny9jvdx
In order to use quicksort this has to be typed in main

quickSort(dimheads[0][0],dimheads[0][1]);

Presumably you mean:

quickSort(dimHeads[0][0],dimHeads[0][1], 0);

and do I just guess where to add this?

In working out the dimheads typo, I saw that dimHeads has file scope
(it is "global") but is modified by some of the most low-level
functions in the program. This makes it very hard to unpick the
working of the code.

BTW, I did guess where to add the call to quickSort and I get exactly
the same output as from the version without it. I can only repeat
that you really need to find a minimal complete program the exhibits
the problem. Just trying to cut down the program to leave the bare
minimum that still goes wrong is likely to show you where the problem
is.

 

[user923005]

Unless the problem is very simple, we will soon be stuck because:
(1) some of your lines have got wrapped so the code is not compilable;
(2) your program does not call quickSort; and
(3) your program needs input that is not provided.

If you can, post as short, compilable, version that exhibits the
problem. If it needs data, so do we! If possible, re-write it to
include the data.

Ok, here is the source code with the file it needs:

http://www.mediafire.com/?berlny9jvdx

In order to use quicksort this has to be typed in main

quickSort(dimheads[0][0],dimheads[0][1]);

That link requires some sort of account formation. No thanks.

Here is a PR-Tree that is already coded and debugged:
http://www.cse.ust.hk/~yike/prtree/prtree.tgz
It comes from this site:
http://www.cse.ust.hk/~yike/prtree/

 

[Kelsey Bjarnason]

[megasnip - was quoting 700 lines necessary?]

For more C Source codes visit
http://zsoftwares.googlepages.com/CPrograms.html

Awright, I did. Opened one at random:
http://zsoftwares.googlepages.com/Assign1.htm

Let's see...

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

Three lines in, already an error - there's no such header as conio.h in C.

//--------------------------------------------------------------------------
void main()

Two more lines, two more errors. // comments aren't defined by the most
commonly-used C standard - but it does define main, more precisely, it
defines main to return an int. Not void, not string, not array of doubles.

{
int a[10],n,choice;
int read_array(int []);

Blech. Prototyping is good - but put 'em _outside_ the function, where
they belong.

textcolor(10);

No such animal in C.

while(1)
{
clrscr();
No such animal in C.

printf("\n\n\t ********* MENU ******** ");
....
printf("\n\n\t ENTER YOYR CHOICE :: ");

Hmmm - no terminal newline, no buffer flush - so the prompt may not even
show until _after_ they input their choice. Not good.

...
scanf("%d",&choice);

No attempt to see whether scanf returned a result - nor to clear the
buffer, though I suspect the getch() - also not part of C - might do that.

....

}
}

main is missing the expected return value.


int read_array(int a[])
{
int n,i;

printf("\n\n\t ENTER THE ARRAY LENGTH :: ");

scanf("%d",&n);

No attempt to handle errors.

for(i=0;i<n;i++)
{
printf("\n\n\t ENTER THE ELEMENT [%d] :: ",i);
scanf("%d",&a);

No attempt to handle errors.
}

return(n);
}

According to this function, I can enter 100 as the array length - but the
actual array length is only 10. Net result: buffer overrun.

Note: To run all the source programs given on above website you need (
OS : DOS/ or any version of Windows OS
and Turboc compiler or any windows compatible c language compiler)

Why do you need DOS, Windows, Turbo C or a "windows compatible" compiler,
when the same job could be done as effectively in standard C, which will
work - as well as the code can ever work - on any system or compiler?

All in all, not a recommended site.

 

[Richard]

[megasnip - was quoting 700 lines necessary?]

For more C Source codes visit
http://zsoftwares.googlepages.com/CPrograms.html

Awright, I did. Opened one at random:
http://zsoftwares.googlepages.com/Assign1.htm

Let's see...

You only seem happy when being obstructive, rude and thoroughly
arrogant. How do you get through your day?

Do you really think you are winning points by pointing out flavour of
the day "conio.h"?

With regard to your rather amateurish and puerile review of the site:

1) His main didn't need a return statement. His "incorrect" Main
declaration was a void. That mistake made his other one acceptable ot,
at least, ignorable.
2) Language tutorials are not programming tutorials. There is nothing in
the C Standard about having to handle error conditions which you raised
about 5 times. The functions he used ARE in the C standard. Make up your
mind.

By trying to do the usual comp.lang.c "who has the longest pecker"
routine you have fallen for the easy route. Using your rational then ALL
functions and results should be minutely checked for potential error
conditions and type over runs.

Your post might have been helpful and informative if you weren't so keen
on basically being destructive and over bearing in your replies.

 

[Kelsey Bjarnason]

[snips]

You only seem happy when being obstructive, rude and thoroughly
arrogant.

Really?

Consider a newbie, looking at that page.. They don't know from squat,
they learn how to do things the wrong way. Now consider either the OP or
the newbie seeing my comments. The OP could fix the code, or the newbie
could look for a better resource.

In my view, the result of that would be a net benefit to the newbie - and
to any who have to work with him or his code.

This, to you, is obstructive, is it?

How do you get through your day?

Very easily.

Do you really think you are winning points by pointing out flavour of
the day "conio.h"?

Points? Was there a game going on? If so, I'm unaware of it.

1) His main didn't need a return statement.

In C99, IIRC, you can get away with this. However, C99 is not terribly
widely used.

His "incorrect" Main declaration was a void.

He has no Main declaration. His declaration of main is incorrect; I
assume this is what you were referring to, but if so, there's no need for
quotes: it is wrong.

That mistake made his other one acceptable ot,
at least, ignorable.

I see; in your view, compounding one error with another makes the first
error acceptable. I take it you've never worked in a field where this is
not the case - programming, for example.

2) Language tutorials are not programming tutorials.

This one sure isn't.

There is nothing in
the C Standard about having to handle error conditions which you raised
about 5 times.

He's giving tutorials on how to use language constructs. Teaching people
to use them sloppily, or worse, incorrectly, benefits nobody.

The functions he used ARE in the C standard.

getch() is in the C standard? clrscr is in the C standard? I'm sure
you'll quote chapter and verse.

By trying to do the usual comp.lang.c "who has the longest pecker"

Is that a common game for you? Personally, I've never understood the
point of it. Dick size might matter to someone of little actual worth
other than that, but the rest of us have things to contribute - such as
pointing out the flaws in a tutorial.

And no, I don't want to know the size of your dick; you're not my type.