HP 48GX - Store Coordinates in a List

[MNH]

Suppose I have coordinates representing the topographic features of a piece of commercial property. There will be coordinates representing the property boundary too. These coordinates will be stored by point number, but not in consecutive order, and not starting with point number one. If I want to store the coordinates in a list of lists, these constraints might be a pain to deal with. Each list in the list will have the following format:
Point #, A 2-D vector (Northing (Y-value), Easting (X-value)), Description of the point

Some examples would be:
{100 [5000 5000] "PROP COR"}
{500 [5200 5100] "BLDG COR"}
Stored in a list would be {{100 [5000 5000] "PROP COR"},{500 [5200 5100] "BLDG COR"}}
Assume user is programming in User-RPL.

There's a gap from 1 to 99 and 101 to 499. That's a lot of wasted memory; there are 500 positions available in the list, but only 2 positions are being used. What's the solution? Without knowing the starting position of the first list or the ending position of the last list, the solution isn't easy. Also, when getting a list from the list, point # 100 is in the first position; there's an offset of N+99, if I'm not mistaken.

Maybe I could do something like this after point # 100 is stored:
{100 100 {100 [5000 5000] "PROP COR"}}, where 100 is the starting index and 100 is the ending index.
After point # 500 is stored:
{100 500 {100 [5000 5000] "PROP COR"},{500 [5200 5100] "BLDG COR"}}

A typical point numbering scenario for a survey crew might be:
1 to 99 - control points
100 to 199 - property corners
200 to 499 - underground utilities
500 and above - topographic features

I was thinking points might be stored in banks of 50 points each to conserve memory.
{1 1 50 {100 [5000 5000] "PROP COR"} ... { }}, where 1 is the number of available banks
{2 500 550 [5200 5100] "BLDG COR"} ... { }}, there are now 2 available banks

Does anyone have any suggestions about how this might be done?

[Giuseppe Donnini]

Lists are completely free-format in RPL, so if you don't use any dummy placeholders, no memory is going to be wasted. In particular, there is no necessary connection between your point number and the implied element index of a list. The point number is just the first (arbitrary) element of a sub-list which is itself an (arbitrary) element of the outer list.

[Han]

Leave your data list as-is. Instead, create a new object (string?) whose characters represent the point-number within the list. Let's say we use a 2-character string of indices (there are 256 characters, so that gives us a space of \( 256^2 = 65536 \) points. The "first" point is point 100, which in base 256 is simply the 100th character. So that would be a character 0 followed by character 100 (or the letter "d"). Then the next two characters would be character 1 followed by character 244 since \( 500 = 1\cdot 256^1 + 244 \cdot 256^0 \).

Thus when you want to know which point the \(n\)-th element in your data list is, you simply get the \( 2n \)-th and \( (2n+1) \)-th characters and convert from base 256 back to base 10. Moreover, if you want to search for the \( k \)-th point, you simply traverse your string two characters at a time and compute the decimal representation of those two characters and check to see if it matches the value \( k \). This would be much faster because actual lists are composite objects. Thus, when "skipping" objects in side a list, the cost is very high (as opposed to simply traversing a string 2 characters at a time and doing a quick computation each time).

[MNH]

(03-28-2021 09:08 PM)Han Wrote:  Leave your data list as-is. Instead, create a new object (string?) whose characters represent the point-number within the list.

"0 100" // My data list can contain 100 indexes based on the Point # of the inner list.
In this example index 0 (outer list) contains { { 100 [5000 5000] "BLDG COR" } }, but I'm looking for Point # 100 (inner list).

Would my code test each index from the outer list (index 0 through index 100), then test index 0 (Point #) from the inner list and test it against the Point # I'm looking for?

[BruceH]

(03-28-2021 04:21 AM)MNH Wrote:  Suppose I have coordinates representing the topographic features of a piece of commercial property. There will be coordinates representing the property boundary too. These coordinates will be stored by point number, but not in consecutive order, and not starting with point number one. If I want to store the coordinates in a list of lists, these constraints might be a pain to deal with. Each list in the list will have the following format:
Point #, A 2-D vector (Northing (Y-value), Easting (X-value)), Description of the point

Some examples would be:
{100 [5000 5000] "PROP COR"}
{500 [5200 5100] "BLDG COR"}
Stored in a list would be {{100 [5000 5000] "PROP COR"},{500 [5200 5100] "BLDG COR"}}
Assume user is programming in User-RPL.

There's a gap from 1 to 99 and 101 to 499. That's a lot of wasted memory; there are 500 positions available in the list, but only 2 positions are being used. What's the solution? Without knowing the starting position of the first list or the ending position of the last list, the solution isn't easy. Also, when getting a list from the list, point # 100 is in the first position; there's an offset of N+99, if I'm not mistaken.

You are mistaken. ;-) There's no offset and no wasted space - your list is storing exactly what you see, namely the number 100, followed by an array [5000,5000] followed by a string and so on. That number 100 is just a number in a list and has no special meaning.

Quote:Maybe I could do something like this after point # 100 is stored:
{100 100 {100 [5000 5000] "PROP COR"}}, where 100 is the starting index and 100 is the ending index.

Lists don't have indexes like that. There's no handy "store this under index 50; retrieve index 50" pair of commands, unfortunately.

Quote:After point # 500 is stored:
{100 500 {100 [5000 5000] "PROP COR"},{500 [5200 5100] "BLDG COR"}}

A typical point numbering scenario for a survey crew might be:
1 to 99 - control points
100 to 199 - property corners
200 to 499 - underground utilities
500 and above - topographic features

I was thinking points might be stored in banks of 50 points each to conserve memory.
{1 1 50 {100 [5000 5000] "PROP COR"} ... { }}, where 1 is the number of available banks
{2 500 550 [5200 5100] "BLDG COR"} ... { }}, there are now 2 available banks

No need, one list is just as good as two in this scenario. If you do want to split up the lists to separate the points logged by different crews then I would suggest using different variable names for each of the lists rather than adding another number to the beginning.

Quote:Does anyone have any suggestions about how this might be done?

[MNH]

(03-28-2021 12:25 PM)Giuseppe Donnini Wrote:  Lists are completely free-format in RPL, so if you don't use any dummy placeholders, no memory is going to be wasted. In particular, there is no necessary connection between your point number and the implied element index of a list. The point number is just the first (arbitrary) element of a sub-list which is itself an (arbitrary) element of the outer list.

I've been reading about handling arrays in the C programming language hoping for some similarity to HP User-RPL. You mention free-format, yes I agree because a list can contain both numerical data and character strings. I don't have to worry about allocating memory. The connection between my point number and the implied element index of a list is something I couldn't vocalize in my original post; I didn't know how to pose the question.
I think as I'm adding points to my list I should sort them in ascending order. When I need to get a point from my list I can execute a binary search. Does that sound logical?

[MNH]

(03-31-2021 09:27 PM)BruceH Wrote:  Maybe I could do something like this after point # 100 is stored:
{100 100 {100 [5000 5000] "PROP COR"}}, where 100 is the starting index and 100 is the ending index.

What I meant by starting and ending indexes, is they are a way to keep track of the lowest point number in the list and how many elements are in the list. Since I don't need any empty lists in the list to act as placeholders, and there doesn't need to be any correspondence between the list elements and their position in the list, all that is irrelevant.

[Joe Horn]

(04-01-2021 09:00 PM)MNH Wrote:  I think as I'm adding points to my list I should sort them in ascending order. When I need to get a point from my list I can execute a binary search. Does that sound logical?

Rather than sorting the list each time a new point is added, I suggest also using a binary search for where the new point should go, then inserting it there. That's much faster than sorting the entire list (if the list is large). A simple User RPL routine which performs insertion into an already-sorted list is here: https://www.hpcalc.org/details/6877

If the above is what you meant, please ignore this reply.

[MNH]

(03-28-2021 09:08 PM)Han Wrote:  Let's say we use a 2-character string of indices (there are 256 characters, so that gives us a space of \( 256^2 = 65536 \) points.

I appreciate the response and the time you took to write it, but I don't completely understand how to use a 2-character string. I could use characters 'A' through 'Z' and 'a' through 'z.'
That would be \(52^2 = 2704\) points. That is more than adequate for my purposes.

[BruceH]

(04-01-2021 09:21 PM)MNH Wrote:  

(03-31-2021 09:27 PM)BruceH Wrote:  Maybe I could do something like this after point # 100 is stored:
{100 100 {100 [5000 5000] "PROP COR"}}, where 100 is the starting index and 100 is the ending index.

What I meant by starting and ending indexes, is they are a way to keep track of the lowest point number in the list and how many elements are in the list. Since I don't need any empty lists in the list to act as placeholders, and there doesn't need to be any correspondence between the list elements and their position in the list, all that is irrelevant.

Ah, I see. Given the amount of code needed to check each new value against the lowest and highest and fiddle around updating the beginning of the list it is probably easier to just calculate the highest and lowest on demand and not try to track them at all. (An added benefit is that then you don't need a special "add point to list" routine.) The following example finds the lowest value:

Code:

2: {{100 [5000 5000] "PROP COR"} {77 [7000 7000] "PROP BCK"}}
1: << -> a b 'IFTE(a(1) < b(1), a, b)' >>
STREAM

Just change the < to > in the IFTE statement to get the highest element from the list.

[Han]

Hopefully this reply isn't too late. Please allow me to explain how I understand your goal to see if our thinking is in alignment. You wish to have a list whose elements are themselves lists (point data). It is possible that you may have several of these types of lists (organized as point types) which might also be incorporated together as a list. So something like:

Code:

{
  { { point 1-1 data }, { point 1-2 data }, ..., { point 1-n data} } // type 1 with n points
  { { point 2-1 data }, { point 2-2 data }, ..., { point 2-m data } } // type 2 with m points
   ...
}

I recommend simply have one list of just points, where the point data itself contains the "type".

Code:

{
  {100 [5000 5000] "PROP COR"}
  {500 [5200 5100] "BLDG COR"}
}

Then keep a string that indexes these points for fast searching. If you wish to only use A-Z and a-z as your characters, that gives you \( 52^2 = 2704 \) points as you previously calculated. Then your string of indices would look like "BwJg" (assuming \( B=1 \) and \( w=48\) to get \(1\cdot 52^1 + 48\cdot 52^0 =100\); similarly \( J = 9 \) and \( g = 32 \) for \( 9\cdot 52^1 + 32\dot 52^0 = 500 \)).

Without the use of index strings, you would have to check each individual point (which is itself a list) and skip the current point (assuming no match) and go check the next point. Due to the way lists are stored internally, this is an extremely slow process (skipping a list means skipping each individual object within the list). So for example, if you wanted to know where point labeled 500 is stored (or if it even exists), you would have to check the first point, see that it is is not labeled as 500, and then "skip" the first point to check the next point. Strings are just a sequence of characters, and skipping characters is extremely fast. The number of "skips" is the position within the list (with perhaps +1 depending on whether your index starts at 1).

A second string would be used to sort your list. This string would also be composed of 2-character indices, but the value would be the index within the point list. In other words, we sort the point labels (100 and 500) and store the position. With only two points, your string would be "ABAC" since ( \( A=0, B=1, C=2 \) so that \( AB = 0\cdot 52^1 + 1\cdot 52^0 = 1\) and \( AC = 0\cdot 52^1 + 2\cdot 52^0 = 2 \)). Let's suppose we add a third point to the end of the existing point list, and that its point number is 300. Then the first string "BwJg" becomes "BwJgFo" (\( F=5 \) and \( o = 40 \) so \( Fo = 5\cdot 52^1 + 40\cdot 52^0 = 300 \)). We simply "tack on" the new point and store its label into the string. The second string would have to be modified to "ABADAC" so that the second 2-character code "AD" (which is 3 in base 10) points to the third position in the original point data list. In order to insert "AD" into an already sorted string of indices, you would need to apply a binary search (pretty fast) as Joe Horn mentioned, and split and concatenate substrings.

Thus if you wanted the label of the \(k\)-th unsorted point, you would use the first string and extract the \(2k\)-th and \(2k+1\)-th characters, convert into decimal. If you want the \( k\)-th sorted point in the data point list, then you would use the second string instead. After converting the 2-character string to decimal form, use this value (call it \( p \)) and extract the \( p\)-th element of the point list. And lastly, if you wanted to find the point whose label is \( k \) itself, just start at the beginning of the first string, and keep extracting 2 characters at a time, convert to decimal form, and see if the resulting value is equal to \( k \). The number of skips (call it \( p \)) is the position of the \( k\)-th label within the point list; just extract the \( p \)-th element from your point list.

Gaps in point labels will not matter. And you will not have to sort your points list -- it will be ordered in chronological order (the last point was the last added). Your second string will keep the positions of the sorted labels.

[MNH]

(04-13-2021 07:44 AM)Han Wrote:  Hopefully this reply isn't too late.

I'm still working on this project as time permits. Thank you for your very thorough response!

[Han]

It occurred to me that there is some redundancy in keeping the labels 100 and 500 in my example. You could save some space by omitting these numbers in the list of points and simply store them in your first string with a one-to-one correspondence between the \( k \)-th pair of characters in the string and the \( k \)-th point in the list of points. If you also structure your points to use a numerical code for the point type, rather than strings such as "PROP COR" and "BLDG COR" (maybe use a two-digit value?), then you could instead use an array of points to save on memory.

[MNH]

(04-14-2021 06:50 AM)Han Wrote:  If you also structure your points to use a numerical code for the point type, rather than strings such as "PROP COR" and "BLDG COR" (maybe use a two-digit value?), then you could instead use an array of points to save on memory.

I've worked for a company that used numerical codes for point types. The available software back then didn't have drop-down lists, so typing a number (1- 99) was easier than typing out a word or words. Your idea is a good one!