I have a function that takes an x an y coordinate as parameters

void storecoords(float x, floaty)

{

float Array[][2];

}

I need to store a number of x,y coordinates in an array such that:

Array [x1 ][x2][x3][x4][x5] ...

[y1 ][y2][y3][y4][y5] ...

i.e.

As the x y coordinates are recieved by the function I need to

1) check if the coordinates are in the array.

2) if if the coordinates are do nothing.

3) if the coordinates are not in the array: add the coordinates to the array.

n.b the array must be able to grow dynamically as more and more coordinates are added?

Any suggestions appreciated?

Thanks,

void storecoords(float x, floaty)

{

float Array[][2];

}

I need to store a number of x,y coordinates in an array such that:

Array [x1 ][x2][x3][x4][x5] ...

[y1 ][y2][y3][y4][y5] ...

i.e.

As the x y coordinates are recieved by the function I need to

1) check if the coordinates are in the array.

2) if if the coordinates are do nothing.

3) if the coordinates are not in the array: add the coordinates to the array.

n.b the array must be able to grow dynamically as more and more coordinates are added?

Any suggestions appreciated?

Thanks,

If the array must be able to grow, you cannot define it as static data, or heap data with 'float Array[][2]'. You'll have to use malloc(), calloc(), and/or realloc() to grow the array.

It really is a piece of cake to put into effect. In fact, if you can live with a singly dimensioned array this is almost trivial, and it will certainly be "standard C". A singly dimensioned array would put the X,Y pairs into consecutive locations. For any pair (N) that is in the array, X is at location (X * 2) and Y is at (X * 2 + 1).

Kent

Is the data sorted? If so, you can do a binary search on it just as you would any other array. An array of 1,000,000 entries is then searched with only 20 tests.

If not, you'd have to sequentially search the array just as you would any other array.

Here's an example of using a single array to contain all of the data would add an entry.

float *MyData = NULL;

int MyDataLength = 0;

AddDataPair (float X, float Y)

{

MyData = (float *)realloc (MyData, 2*(MyDataLength+1));

MyData[MyDataLength*2] = X;

MyData[MyDataLength*2+1] = Y;

MyDataLength++;

}

Here's the same technique using separate X and Y arrays:

float *MyDataX = NULL;

float *MyDataY = NULL;

int MyDataLength = 0;

AddDataPair (float X, float Y)

{

MyDataX = (float *)realloc (MyDataX, (MyDataLength+1));

MyDataY = (float *)realloc (MyDataY, (MyDataLength+1));

MyDataX[MyDataLength] = X;

MyDataX[MyDataLength] = Y;

MyDataLength++;

}

Search functions would use any/all of these arrays in similar fashion.

Kent

For e.g. if the array values are stored sorted(keep storing in sorted order),checking for presence can be done using Binary search which is much faster than Linear Search.

U have to take a decision as to whether the frequency of u checking for presence of co-ordinates is high enough

for u to keep the array sorted or sorting the list regularly.

As soon as I read your symptom I knew what I'd left off. My apologies....

Good Catch, Mercantilum.

Kent

The next question is how often will you be adding or deleting coordinates.

It may be beneficial to insert new coordinates into their sorted locations.

Kent

Sort the array in ascending order. Because the data rarely changes when the program is running, the sorting/inserting algorithm doesn't need to be particularly efficient.

The bsearch() function can be used to examine the array. Because the array is so small, it might be worthwhile to write your own binary search routine that doesn't rely on the system provided algorithm. The bsearch() function has to call your comparison routine every time through the loop. If bsearch() proves too slow, writing your own (I can help with this, too) should drastically cut search times -- perhaps by as much as 50%.

Kent

Writing your own is faster on such a small dataset.

bsearch (int Target)

{

int LowIdx;

int HighIdx;

int MidIdx;

int CompareValue;

LowIdx = 0;

HighIdx = idx-1;

MidIdx = (LowIdx + HighIdx) / 2;

while (LowIdx != HighIdx)

{

CompareValue = Target - X[idx];

if (CompareValue < 0)

HighIdx = MidIdx;

else if (CompareValue > 0)

LowIdx = MidIdx+1;

else

break;

MidIdx = (LowIdx + HighIdx) / 2;

}

return MidIdx;

}

The system released bsearch is "general purpose" so you have to provide it some help, like the comparison function.

Kent

Sorry -- took the code from another application and didn't change that one variable. :) This was actually borrowed from an app that compared strings. A "true" binary search doesn't have three conditions, as this one does.

idx is th number of items in the array. If idx==1, then HighIdx becomes 0, meaning that the only item in the array is the correct one.

If you're searching a small dataset, a sequential search is just fine. You might start there, and convert to a binary search only when you think that performance is a problem.

Kent

Please provide your email to receive a free trial preview!

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.