how to sort 'arrays of handle' by two variables

[patric]

Hello,

I have a very specific programming question:

I would like to number selected Symbols just like the 'number instruments' tool which is implemented in spotlight.

Therefore I have created an Array of Handles - 1 Handle for each selected symbol. Now I want to create an order to number these symbols. As variables I want to use x- and y-coordinates.

So for the moment I have an Array of Handles or symbols (h) and (arrays of) x- and y-coordinates (x,y). Now I need an algorithm to sort the symbols by both of the coordinates, so I can number the symbols from top to bottom and/or left to right.

It seems basic programming knowledge, but I cannot find an algorithm which sorts by two variables. For the moment I feel quite desperate, so please help me!!!

Patric

[Miguel Barrera]

First, I would add the handle array number to x,y so you know which set corresponds to the handle such as :

x,y,handle array number

523.45, 678.90, 1

234.56, 987.65, 2

523.45, 123.45, 3

Use the function

PROCEDURE SortArray(VAR arraytosort :ARRAY; numtosort :INTEGER; fieldnumber :INTEGER);

Although it says it will sort 1 dimensional arrays, I have used it with a 2-dimensional and it will sort the first element. After this the array would look like this:

x,y,handle array number

234.56, 987.65, 2

523.45, 678.90, 1

523.45, 123.45, 3

To reorder the y element you need to find the smaller value and swap it so it becomes the first element. You go down the list and find the second smallest, swap it, and so forth. The final result then should look like this

x,y,handle array number

234.56, 987.65, 2

523.45, 123.45, 3

523.45, 678.90, 1

If you search google for "array sorting", you will find several code samples. This is one link you may try

http://www.cs.mtu.edu/~shene/COURSES/cs201/NOTES/chap08/sorting.html

[J. Miller]

A quick way to sort either by x or y is to offer the user the choice to sort by x or y. Then you can perform the sort based on a user response. A "Bubble" sort is what you are looking for.

Hope that helps

Jeff Miller

[patric]

Thank you so much!

That should solve the problem.

So if I want the algorithm to sort from the upper left corner down to the lower right, I just have to implement the Bubblesort algorithm twice with a request like:

IF y[i+1]=y (i=index of the handle array) THEN DO 'BUBBLESORT X-Coordinates'

?

Patric

[patric]

The Bubble Sort works fine, but I've got a problem swapping the handles:

When the coordinate is negative the corresponding handle won't stored and I don't know why...

The code is:

FOR l:=1 TO i-1 DO Begin

FOR k:=1 TO i-1 DO Begin

checkX:=FALSE;

havetochange:=FALSE;

Get2DPt(h[k],1,pX[k],pY[k]);

Get2DPt(h[k+1],1,pX[k+1],pY[k+1]);

IF (pY[k]

IF (pY[k]=pY[k+1]) THEN checkX:=TRUE;

IF (havetochange=TRUE) THEN biggerY:=h[k];

IF (havetochange=TRUE) THEN h[k]:=h[k+1];

IF (havetochange=TRUE) THEN h[k+1]:=biggerY;

IF(checkX=TRUE)&(pX[k]>pX[k+1]) THEN biggerY:=h[k];

IF(checkX=TRUE)&(pX[k]>pX[k+1]) THEN h[k]:=h[k+1];

IF(checkX=TRUE)&(pX[k]>pX[k+1]) THEN h[k+1]:=biggerY;

END;

END;

Do you have any idea?

I also tried to add greater numbers to the coordinates but then it does not even work for positive coordinates...

Edited January 22, 2009 by patric

[Pat Stanford]

Have you looked at the built in SortArray function? It only sorts on a single variable, but you can run it twice, first on the X (secondary sort) and then again on the Y primary sort.

In looking at your code, I doesn't look right to me. What you pasted into the message does not use the variable l anywhere in the For statement.

I would also combine the If statements that have the same criteria into single lines by using a Begin/End around the actions. If is an expensive function and if you have a lot of symbols, call IF 6 times (or even 3) for each change will greatly slow down the code.

Another optimization (but less important), would be to make k+1 a named variable and only do the calculation once at the top of the For statement. By my count, you are doing the same math calculation 10 times in the loop.

I don't see anything right off that is causing the code to not work for negative numbers.

Can you post a little more of you code so we can see the definitions for H and pX and pY? Which are arrays? are you using data structures?

Pat

[patric]

Hi Pat, thanks for your help,

it might be that the code is a little bit naive as I'm a VectorScript newbie and my c and java skills are a little bit rusty.

Have you looked at the built in SortArray function? (secondary sort) and then again on the Y primary sort.

- I checked it, but I thought, it would only change the y-coordinate. In fact I have an Array Of Handles which I want to sort by Arrays Of Real. So I tried the simplest way of using a bubble sort. I just want to sort about 300 symbols in one step, so slimming down the code is not the most important thing for this moment

In looking at your code, I doesn't look right to me. What you pasted into the message does not use the variable l anywhere in the For statement.

- 'l' is just a counter to make sure that every position in the array is checked every time. It's not the elegant but the easy way...

There might be a mistake, but I don't get it.

I would also combine the If statements that have the same criteria into single lines by using a Begin/End around the actions. If is an expensive function and if you have a lot of symbols, call IF 6 times (or even 3) for each change will greatly slow down the code.

- could you give me an example? I tried something like that but the compiler gave back an exception.

I don't see anything right off that is causing the code to not work for negative numbers.

- Neither do I. When I move the symbols to positive coordinates, the whole things works fine.

Can you post a little more of you code so we can see the definitions for H and pX and pY? Which are arrays? are you using data structures?

- I'm not sure what you mean ('using data structures')...

I don't have the code in a nice and structured way to present. Sorry! Here are just parts of it.

VAR

h : ARRAY [1..1000] OF Handle;

pX,pY : ARRAY [1..1000] OF Real;

biggerY: HANDLE;{used in bubble sort to store data}

i,j,k,l,m: Integer;

CountSymI : Integer;

CountSymStr : String;

havetochange,checkX: Boolean;{used in Bubblesort}

in the main program:

{to store the selected objects in Handles}

i:=1;

h:=FSActLayer;

While h<>NIL DO BEGIN

h[i+1]:=NextSObj(h);

i:=i+1;

END;

{to store the corresponding coordinates of the stored objects}

j:=1;

WHILE h[j] <> NIL DO BEGIN

Get2DPt(h[j],1,pX[j],pY[j]);

j:=j+1;

END;

{bubble sort}

FOR l:=1 TO i-1 DO Begin

FOR k:=1 TO i-1 DO Begin

checkX:=FALSE;

havetochange:=FALSE;

Get2DPt(h[k],1,pX[k],pY[k]);

Get2DPt(h[k+1],1,pX[k+1],pY[k+1]);

IF (pY[k]

IF (pY[k]=pY[k+1]) THEN checkX:=TRUE;

IF (havetochange=TRUE) THEN biggerY:=h[k]; {ein simpler swap algorithmus}

IF (havetochange=TRUE) THEN h[k]:=h[k+1];

IF (havetochange=TRUE) THEN h[k+1]:=biggerY;

IF(checkX=TRUE)&(pX[k]>pX[k+1]) THEN biggerY:=h[k];

IF(checkX=TRUE)&(pX[k]>pX[k+1]) THEN h[k]:=h[k+1];

IF(checkX=TRUE)&(pX[k]>pX[k+1]) THEN h[k+1]:=biggerY;

END;

END;

{writing the new handle number into the data base}

CountsymI:=1;

While h[CountsymI]<>NIL DO BEGIN

CountSymStr:=NUM2Str(0,CountSymI);SetRField(h[CountsymI],'RechteckigeDB','Pultnr',CountSymStr); {changes the field 'pultnr' in the database 'RechteckigeDB'}

CountSymI:=CountSymI+1;

END;

then of course END and RUN...

I hope that you will understand the way I want it to work;-)

[MullinRJ]

Patric, I think if you simplify your data structure, it will be a lot easier to manipulate the elements.

Start by defining a "Structure" that you'll store in an array. It should contain a handle and a point.

TYPE

???SymbolPositions = Structure

??????H :Handle;

??????P :Point;??????{ also a structure (predefined) }

???end;??????{ SymbolPositions }

Now create an array to hold these elements.

VAR

???SymPosArray :Dynarray [] of SymbolPositions;

???

It is not yet dimentioned, because you don't know how many elements you will put into it. This you will figure out at runtime.

You may also need to create a variable of the same type as your structure that you can hold one array element in.

???SymPos : SymbolPositions;

Next, in your main program, you need to count how many objects you want to collect data on. There are many ways to do it. I'll leave it to you to find the best way as I don't know how your drawing is structured. Often, you will select all items of interest then run you program against the selected objects, but that's only one way.

When you have the count, CNT, you ALLOCATE your array size. The array is linear, as each element is a Structured variable, but each element has two parts, actually three because the second element of your structure, P, is also a structure of TYPE Point, where P has two parts, P.x and P.y.

To access an element in your array, you can say:

???SymPos := SymPosArray[7];??????{ data stored in array position 7 - H and P}

???

To access the pieces of your structure, say:

???SymHnd := SymPos.H;???????????????{ from a single variable }

???SymHnd := SymPosArray[7].H; ??{ from an array of structures }

Since the point data in your structure is also a structure, acess it like this:

???SymX := SymPosArray[7].P.x;

???SymY := SymPosArray[7].P.y;

???

This may be a lot for starters, but it is much easier to modify your code if your variables are built in a way that makes the code easier to manipulate. KISS is my guiding light. Now, back to the big picture...

Your main program will have a format somewhat like this:

BEGIN

???{ Count your symbols }

???CNT := { some function to count them }

???Allocate SymPosArray [1..CNT];

???{ Read your handles and XY values into the array }

???SymHnd := { Get your first handle }

???for I := 1 to CNT do begin

??????SymPosArray.H := SymHnd;

??????GetSymLoc(SymHnd, SymPosArray.P.x, SymPosArray.P.y);

??????SymHnd := { Get your next handle, usually with NextSObj(SymHnd); }

???end;

???{ Now you can sort }

???{ I would try the VS command SortArray() here, but you may have to do it manually. }

???{ To sort on both X & Y variables, you need to sort your primary variable last. }

???{ The rest of your program... }

END;

Have fun,

Raymond

[patric]

Thanks Raymond!

It seems there is a lot to do. I will try what you suggest.

But do you think the problem with the negative coordinates will be solved? As you have proposed a similar script before did you have any problems like this?

[MullinRJ]

Hi Patric,

???I think you should see your negative coordinate problem go away. One of the problems you were having was that you were swapping elements in the handle array, but not in the pX & pY arrays. You also needed to swap the same components in the pX and pY arrays when you swapped a handle in the H array if you wanted the handles and associated coordinates kept together.

???With an array of structures, you will be swapping whole structures from one position to another, guaranteeing that the X and Y travel with the H. This is why I proposed building the structure this way. Less things to go wrong when you finally get around to sorting the data the way you want.

Raymond

[panta rhei]

Ray,

Brilliant! I've wondered what these structures could do for me, but now I see it. I have quite a few plug-ins that use bubble sorts ?by reference? (ie. I sort by a value, but actually use another array reorderd by the sorted one.)

Thanks!

Petri

[patric]

You search the code again and again and you won't find the mistake by yourself. And in the end it's so easy;)

Thanks for the help!

[patric]

It's not so easy as it first seemed, but it's a great manual you wrote, Raymond.

With this tool it's fun programming!

[MullinRJ]

Thanks, Patric,

It's never as easy as it first seems. You obviously like puzzles, so, over time it will get easier. One of the joys of programming in VW is that you are manipulating images, so you can see the results of your efforts as you work, and sometimes the mistakes are more beautiful than the desired results - sometimes. I'm glad you're enjoying it.

Petri,

At times, I've used the indirect method for sorting arrays. I've not tested this, but for large arrays with a lot of data in each cell (as with a large structure), I wonder if the indirect method might be faster. If I ever figure it out, I'll let you know.

Raymond