How do I change the binary search function to intake the compare?

Question

I am having trouble with the logic of combining these two stipulations in my assignment. How do I change the below binary search function to intake the compareTo the coordinate structures. I wrote it wrong the first time because I used the original string locations. I also dont understand how the compareTo function is suppose to keep track of the length away from the target. Which is confusing to me because the way it reads below for the compareTo function says the opposite to me and asking me to compare individual x and y coordinates. how am I suppose to do that if i am just using the pointers? Am i just passing coordinates *ptrPt1 into the binary search? Number 3 is the most confusing mess of words.

Context for the function relationship:

3. You must write a function compareTo which takes in two pointers, ptrPt1 and ptrPt2, to coordinate structs and returns a negative integer if the point pointed to by ptrPt1 is closer to you than the point pointed to by ptrPt2, 0 if the two locations pointed to by both are identical locations, and a positive integer if the point pointed to by ptrPt1 is farther from you than the point pointed to by ptrPt2. Exceptions to this will be when the two pointers are pointing to points that are the same distance from you, but are distinct points. In these cases, if ptrPt1's x coordinate is lower than ptrPt2's x coordinate, a negative integer must be returned. Alternatively, if ptrPt1's x coordinate is greater than ptrPt2's x coordinate a positive integer must be returned. Finally, if the x coordinate of both points is the same, if ptrPt1's y coordinate is lower than ptrPt2's y coordinate, a negative integer must be returned. If ptrPt1's y coordinate is greater than ptrPt2's y coordinate, a positive integer must be returned.
4. Since your location must be used for sorting, please make the variable that stores your x and y coordinates global. Your program should have no other global variables.
5. A Binary Search function must be used when answering queries.

int binarysearch(int searchval, int* array, int length) {

    int low = 0, high = length-1;

    // Search while there is a valid search space.
    while (low <= high) {

        int mid = (low+high)/2;

        // Value is too small.
        if (searchval < array[mid])
            high = mid-1;

        // too big.
        else if (searchval > array[mid])
            low = mid+1;

        // found it!
        else
            return 1;
    }

    // Never found it.
    return 0;

}


int
compareTo(coordinates *ptrPt1, coordinates *ptrPt2) {
    
    if (ptrPt1 > ptrPt2)
        return -1;
    if(ptrPt1 == ptrPt2)
        return 0;
    if(ptrPt1 < ptrPt2)
        return 1; 
    
}

Answer 1

Your compareTo needs to be refactored.

Comparing the addresses of the structs [vs. the X/Y coordinates within them] is incorrect.

For compareTo, it must first compute the distance from an arbitrary reference point (e.g.) self for each of the two points passed as arguments. Per the problem definition, self can [and should] be a [the only] global.

It gets the distance to self for each of the two [argument] points. It chooses the closer of these two points [if they are different].

If the two points are the same distance from the self point, it first chooses the one with the lower X coordinate value. If the X coordinates are the same for the two points, it chooses the one that has the lower of the two Y values.

Thus, it's a three step process.

---

Your binarysearch needs to be refactored. Upon mismatch/failure, it returns 0. But, zero is a valid index/value for a match. So, it needs to return -1 on failure.

---

There are some issues with the problem definition.

---

Issue (1):

It's not clear [to me] what "rank" is supposed to be. The only thing that makes sense is that "rank" is the index into the list that is sorted by compareTo.

---

Issue (2):

It's not clear what "distance" means. It could be (e.g.):

sqrt((p1->x - p2->x)**2 + (p1->y - p2->y)**2)

But, that uses floating point, and it may be overkill for this problem.

Another "distance" is the manhattan distance which is just the sum of the absolute differences of the X and Y values of the two coordinates:

abs(p1->x - p2->x) + abs(p1->y - p2->y)

---

Issue (3):

I think that two sorted lists are required.

One sorted by compareTo. Another sorted just by X/Y coordinates.

This is because it is required to use a binary search when matching a search coordinate. Because the search coordinate does not know the rank, it can't use the compareTo list and must use the X/Y list.

There are two possible approaches.

This can be achieved by using two lists that are either pointers or indices into the person list. The binarysearch should be modified to accept an array of indices/pointers.

Or, it can be achieved by sorting the person list by compareTo, recording the rank in the coordinate struct and then resorting the list by X/Y coordinates. The binarysearch should be modified to accept an array of coordinates.

---

I've chosen to use the latter approach.

And, I've added some test code to generate a randomized input file, if desired.

I've just implemented a simple insertion sort [algorithm is a cut-n-paste from the wikipedia entry for insertion sort]. So, you'll still have to code up the combined merge/insertion sort logic.

Spoiler Alert: Below is the complete/refactored code:

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

typedef struct {
    int x;
    int y;
    int rank;
} coord_t;

// maximum coordinate
#ifndef COORDMAX
#define COORDMAX        10000
#endif

// max # of [infected] people
#ifndef PERSONMAX
#define PERSONMAX       106
#endif

#define SEARCHMAX       (2 * (PERSONMAX - 1))   // max # of search coordinates
#define THRESHMAX       30          // maximum threshold

coord_t self;                       // coordinates of tracer

typedef int (*cmpfnc_p)(const coord_t *,const coord_t *);

int opt_d;                          // 1=debug
int opt_f;                          // distance mode (0=manhattan, 1=sqrt)
unsigned int opt_R;                 // random fill

void gentest(FILE *fi);

// disti -- get distance from given coordinate to self (manhattan distance)
int
disti(const coord_t *pt)
{
    int dif;
    int tot = 0;

    dif = pt->x - self.x;
    if (dif < 0)
        dif = -dif;
    tot += dif;

    dif = pt->y - self.y;
    if (dif < 0)
        dif = -dif;
    tot += dif;

    return tot;
}

// distf -- get distance from given coordinate to self (floating pt distance)
int
distf(const coord_t *pt)
{
    double dif;
    double tot = 0;
    int rtn;

    dif = pt->x - self.x;
    dif *= dif;
    tot += dif;

    dif = pt->y - self.y;
    dif *= dif;
    tot += dif;

    tot = sqrt(tot);

    // scale result
    // FIXME -- this is untested and may not be necessary
    tot *= INT_MAX;
    tot /= COORDMAX;

    rtn = round(tot);

    return rtn;
}

// dist -- get distance from given coordinate to self
int
dist(const coord_t *pt)
{
    int tot;

    if (opt_f)
        tot = distf(pt);
    else
        tot = disti(pt);

    return tot;
}

// compareAbs -- compare two coordinates for lowest X/Y values
int
compareAbs(const coord_t *p1,const coord_t *p2)
{
    int cmp;

    do {
        // use lower X coordinate
        cmp = p1->x - p2->x;
        if (cmp)
            break;

        // use lower Y coordinate
        cmp = p1->y - p2->y;
        if (cmp)
            break;
    } while (0);

    return cmp;
}

// compareTo -- compare two coordinates for distance from self and then position
int
compareTo(const coord_t *p1,const coord_t *p2)
{
    int cmp;

    do {
        // compare distance to self
        cmp = dist(p1) - dist(p2);
        if (cmp)
            break;

        // compare against absolute coordinates
        cmp = compareAbs(p1,p2);
    } while (0);

    return cmp;
}

// sortswap -- swap array elements
void
sortswap(coord_t *p1,coord_t *p2)
{
    coord_t tmp;

    tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

// sortinsert -- insertion sort
void
sortinsert(coord_t *list,int count,cmpfnc_p cmp)
{

    for (int i = 1;  i < count;  ++i) {
        for (int j = i;  j > 0;  --j) {
            if (cmp(&list[j - 1],&list[j]) <= 0)
                break;
            sortswap(&list[j - 1],&list[j]);
        }
    }
}

// sortany -- outer sort routine
void
sortany(coord_t *list,int count,int threshold,cmpfnc_p cmp)
{

    // TODO: do mergesort
    if (count < threshold) {
    }

    // finish with insertion sort
    sortinsert(list,count,cmp);
}

// binarysearch -- perform binary search on coordinate list
int
binarysearch(const coord_t *search,const coord_t *array,int length,
    cmpfnc_p cmpfnc)
{
    int low = 0;
    int high = length - 1;
    int match = -1;

    // Search while there is a valid search space.
    while (low <= high) {
        int mid = (low + high) / 2;

        int cmp = cmpfnc(search,&array[mid]);

        // found it
        if (cmp == 0) {
            match = mid;
            break;
        }

        // Value is too small.
        if (cmp < 0)
            high = mid - 1;

        // too big.
        else
            low = mid + 1;
    }

    return match;
}

// main -- main program
int
main(int argc,char **argv)
{
    const char *file = NULL;
    char *cp;
    FILE *fi;
    int person_count;
    int search_count;
    int threshold;
    coord_t *pt;
    coord_t *person_list;
    coord_t *search_list;

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        cp = *argv;
        if (*cp != '-')
            break;

        switch (cp[1]) {
        case 'd':
            opt_d = ! opt_d;
            break;

        case 'f':
            opt_f = ! opt_f;
            break;

        case 'R':
            cp += 2;
            opt_R = (*cp != 0) ? atoi(cp) : time(NULL);
            printf("R=%u\n",opt_R);
            srand(opt_R);
            break;
        }
    }

    // get/open input file
    do {
        fi = stdin;

        if (argc <= 0) {
            if (opt_R)
                fi = stdout;
            else
                fi = stdin;
            break;
        }

        file = *argv;

        fi = fopen(file,opt_R ? "w" : "r");
        if (fi == NULL) {
            perror(file);
            exit(1);
        }
    } while (0);

    // generate test data
    if (opt_R) {
        gentest(fi);
        fclose(fi);
        exit(0);
    }

    fscanf(fi,"%d %d %d %d %d",
        &self.x,&self.y,&person_count,&search_count,&threshold);

    person_list = calloc(person_count,sizeof(*person_list));
    if (person_list == NULL) {
        perror("person_list");
        exit(1);
    }

    search_list = calloc(search_count,sizeof(*search_list));
    if (search_list == NULL) {
        perror("search_list");
        exit(1);
    }

    // read in coordinates of all people
    for (int idx = 0;  idx < person_count;  ++idx) {
        pt = &person_list[idx];
        fscanf(fi,"%d %d",&pt->x,&pt->y);
    }

    // read in all search coordinates
    for (int idx = 0;  idx < search_count;  ++idx) {
        pt = &search_list[idx];
        fscanf(fi,"%d %d",&pt->x,&pt->y);
    }

    // get the ranking
    sortany(person_list,person_count,threshold,compareTo);

    // remember the ranking and print the ranked list
    for (int idx = 0;  idx < person_count;  ++idx) {
        pt = &person_list[idx];
        pt->rank = idx;
        if (opt_d)
            printf("%d %d dist=%d rank=%d\n",pt->x,pt->y,dist(pt),idx);
        else
            printf("%d %d\n",pt->x,pt->y);
    }

    // reorder list for search points
    sortany(person_list,person_count,threshold,compareAbs);

    // perform all queries
    for (int idx = 0;  idx < search_count;  ++idx) {
        pt = &search_list[idx];

        int match = binarysearch(pt,person_list,person_count,compareAbs);

        if (match < 0) {
            printf("%d %d not found\n",pt->x,pt->y);
            continue;
        }

        pt = &person_list[match];
        printf("%d %d found at rank %d\n",pt->x,pt->y,pt->rank);
    }

    if (file != NULL)
        fclose(fi);

    free(person_list);
    free(search_list);

    return 0;
}

// gencoord -- generate a random coordinate
void
gencoord(coord_t *pt)
{
    int val;
    int neg;

    for (int mode = 0;  mode <= 1;  ++mode) {
        val = rand();
        neg = (val & 1);
        val >>= 1;

        val %= (COORDMAX + 1);
        if (neg)
            val = -val;

        if (mode == 0)
            pt->x = val;
        else
            pt->y = val;
    }
}

// genrand -- genrate a random number in the inclusive range
int
genrand(int lo,int hi)
{
    int val;

    val = rand();
    val %= (hi + 1);
    if (val < lo)
        val = lo;

    return val;
}

// gensame -- decide if coordinate already in use
int
gensame(coord_t *pt,coord_t *list,int length)
{
    int match;

    do {
        // coordinate may _not_ be the starting/self point
        match = (compareAbs(pt,&self) == 0);
        if (match)
            break;

        // coordinate may not match any previous point in the list
        for (int idx = 0;  idx < length;  ++idx) {
            match = (compareAbs(pt,&list[idx]) == 0);
            if (match)
                break;
        }
    } while (0);

    return match;
}

// gentest -- generate a random test file
void
gentest(FILE *fi)
{
    int val;
    int threshold;
    int person_count;
    int search_count;
    int same;
    coord_t *person_list;
    coord_t *pt;
    coord_t tmp;

    gencoord(&self);

    person_count = genrand(2,PERSONMAX);
    search_count = genrand(1,SEARCHMAX);
    threshold = genrand(1,THRESHMAX);

    fprintf(fi,"%d %d %d %d %d\n",
        self.x,self.y,person_count,search_count,threshold);

    person_list = calloc(person_count,sizeof(*person_list));
    if (person_list == NULL) {
        perror("person_list");
        exit(1);
    }

    // generate coordinates of all people
    fprintf(fi,"\n");
    for (int idx = 0;  idx < person_count;  ++idx) {
        pt = &person_list[idx];
        pt->rank = 0;

        // ensure [proposed] coordinate is unique
        same = 1;
        while (same) {
            gencoord(pt);
            same = gensame(pt,person_list,idx);
        }

        fprintf(fi,"%d %d\n",pt->x,pt->y);
    }

    // generate search coordinates
    fprintf(fi,"\n");
    for (int idx = 0;  idx < search_count;  ++idx) {
        pt = &tmp;

        val = rand();
        val %= 100;

        // generate a random point that is _not_ a person or self (10% of the
        // time)
        if (val < 10) {
            same = 1;
            while (same) {
                gencoord(pt);
                same = gensame(pt,person_list,person_count);
            }
        }

        // randomly select an infected person
        else {
            val = genrand(0,person_count - 1);
            pt = &person_list[val];
        }

        fprintf(fi,"%d %d\n",pt->x,pt->y);
    }

    free(person_list);
}