Re: PR-Tree

On Oct 11, 2:23 am, algatt <alang...@xxxxxxxxx> wrote:
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[i]);
};

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[i]);

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[i][0]=NULL;
dimHeads[i][1]=NULL;
}
list->head=list->tail=NULL;
list->numNodes=0;
return;

}

list->numNodes--;

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

else if (dNode==dimHeads[i][1]){
dNode->x[i]->prev->x[i]->next=NULL;
dimHeads[i][1]=dNode->x[i]->prev;
}
else {
dNode->x[i]->prev->x[i]->next=dNode->x[i]->next;
dNode->x[i]->next->x[i]->prev=dNode->x[i]->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[i][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[i][0];

j=0;

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

for (k=0; k<DIMS; k++){
pr->point[i][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[i]->next!=NULL){
tmp=tmp->x[i]->next;
delNode(tmp->x[i]->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[i]);
}
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





.

Relevant Pages

  • Re: Using a link list over an array.
    ... compile (p->data is a void *) so you have not shown us some key ... int cmp ... head = list_sort; ... list_type *tail; ...
    (comp.lang.c)
  • [PATCH 20/21] mm: kill check_user_page_readable
    ... used only by oprofile's i386 and arm backtrace code, at interrupt time, ... static struct frame_tail* user_backtrace ... -/* check that the pagecontaining the frame tail are present */ ... void arm_backtrace(struct pt_regs * const regs, unsigned int depth) ...
    (Linux-Kernel)
  • PR-Tree
    ... //structure used to store the head and the tail of the loaded ... typedef struct matrix { ... int points; ...
    (comp.lang.c)
  • Re: Alternative method of object representation
    ... in turn is a container for a head and the four appendages. ... For portability among their 9 platforms, they used a virtual machine called the Z-machine, and the code was compiled to Z-code from a language called ZIL. ... int prop_num; ... struct prop_table { ...
    (rec.games.roguelike.development)
  • Re: K&R exercise 1-18
    ... int advance ... int head, tail; ... if (nonspace) { ...
    (comp.lang.c)