WARNING: Some learning in here but no production code yet. Processing oddly-designed data structures can be tricky. Last night I wrote an “iterator” just for fun. Let’s think about collections and how we can process their elements.
When we create our PolylinePath instances, we get some number of points, like 25, and we want to store the distances between them, as part of figuring out which segment contains a given desired distance along the polyline. The current code for doing that looks like this:
function PolylinePath:_create_lengths(points)
local lengths = {}
local total_length = 0
local previous = points[1]
for _, pt in points do
local len = previous:dist(pt)
total_length += len
table.insert(lengths, len)
previous = pt
end
return lengths, total_length
end
For each point on the polyline, we are storing the distance from the beginning of the line to the point in question. Then we find the second of the pair of points that covers a given distance with this code:
function PolylinePath:_find_distance(d)
local remaining_distance = d
for i, len in self._lengths do
if remaining_distance < len then
return i, remaining_distance/len
end
remaining_distance -= len
end
return nil
end
And then we actually use that index to fetch and interpolate between that second point and the preceding point, with this:
function PolylinePath:point_at_distance(d, debug)
local idx, frac = self:_find_distance(d)
local p0 = self._points[idx-1]
local p1 = self._points[idx]
return p0*(1 - frac) + p1*frac
end
So that’s not too awful, although I think that if I were faced with that code in a pop quiz, it would take me a while to figure out what was going on.
Last night, in a moment of idleness, I wrote a little test of an iterator. I’m not sure what brought the idea to mind, but I wrote this test to try the idea:
function Tests:test_pairs()
-- secret part behind this line
local list = {1, 2, 3, 4, 5}
for a,b in do_by_pairs(list) do
print(a, b)
end
end
I’ll show the secret part in a moment. The test prints, on consecutive lines:
1 2
2 3
3 4
4 5
That seems almost useful. If it were producing point pairs from the polyline, for example, the distances we want to store would be just the distances between those pairs. Now of course we know how to write out the code to produce those values longhand, but before I show how it’s done, let me plug this code into the PolylinePath and show how nice it is.
Here is the new version of _create_lengths:
function PolylinePath:_create_lengths(points)
local lengths = {0}
local total_length = 0
for p0, p1 in self:do_by_pairs() do
local len = p0:dist(p1)
table.insert(lengths, len)
total_length += len
end
return lengths, total_length
end
Compare that with the previous:
function PolylinePath:_create_lengths(points)
local lengths = {}
local total_length = 0
local previous = points[1]
for _, pt in points do
local len = previous:dist(pt)
total_length += len
table.insert(lengths, len)
previous = pt
end
return lengths, total_length
end
I think that is noticeably easier to figure out. Once one is sure what do_by_pairs does, it’s even easier.
Here is the code in PolylinePath that implements do_by_pairs for that object:
function PolylinePath:do_by_pairs()
local i = 0
local pts = self._points
local n = table.getn(pts)
return function()
i += 1
if i < n then
return pts[i], pts[i+1]
end
end
end
Whoa! Maybe using it is easier but writing it. wow. (I am not sure we couldn’t do better: this is the very first cut at it that I did.) Let’s explore what this is and how it works.
The job of a function like do_by_pairs is to return a function that can be called repeatedly, each time returning one of whatever the iterator is supposed to return. In a regular iterator that would be key and value or index and value. In this one, we return two values from the array.
The inner function does that: it checks to see if it is not yet done, i < n. If it isn’t done yet, it returns the points at i and i+1. If it is done, it just returns, which will return nil, which will silently stop the iteration.
In the official Lua article Iterators and Closures, it concludes:
This is a common situation with iterators: They may be difficult to write, but are easy to use. This is not a big problem; more often than not, end users programming in Lua do not define iterators, but only use those provided by the application.
I don’t think it’s worth it to make the PolylinePath’s private function _create_lengths easier by adding a more complicated iterator definition to the class. Yes, _create_lengths is perhaps easier to understand, but because it’s in the class, we are pretty much required to understand the do_by_pairs as well. In my view, it makes things worse, if done this way.
However.
There is an idea lurking here. There is a possible class lurking here. The points of a PolylinePath are, of course, a representation of a polyline, a series of points that one moves or draws between. It’s not really just an array of points, it is an array of points that are interrelated in a particular useful way.
So we could have a Polyline class, a thin cover over a simple table, if we wanted one, if we thought it would pay off. We create a new class to make things easier to understand, and to encapsulate behavior that would otherwise be written out longhand all around the code.
Same reason we write functions: we write once, use often, and sometimes we just write one to express part of a large idea, even if we only use it once.
But is the root of this idea really the Polyline, a sequence of points? I’m not sure that it is. Maybe the root idea is a “fence post” collection, a collection of any thing such that the things are the ends and there is another idea in between the ends. Maybe it’s a specialized collection of pairs.
Think of it this way: from the point of view of a user of a polyline, what is interesting is each consecutive pair of points, as if it were stored like this:
polyline = { {p0,p1}, {p1,p2}. {p2, p3}, ...}
We just store the thing as a sequence p0 to pn because it is more efficient in storage and not much less efficient in processing. You could make the case that that detail should be well hidden inside some kind of polyline object and that producing the pairs, as my iterator above does, is what should really happen.
Just for fun, let’s implement a Polyline class that iterates by producing its pairs. How can we know if we like a thing unless we can see it?
Here’s what I have for one test:
function Tests:test_polyline()
local poly = Polyline({10, 20, 30, 40, 50})
local expected = { {10,20}, {20,30}, {30,40}, {40,50} }
local i = 1
for i, first, second in poly:pairwise() do
self:assert_equals(first, expected[i][1])
self:assert_equals(second, expected[i][2])
end
end
My “iterator” is named pairwise, and the class goes like this:
Polyline = class()
function Polyline:init(array)
self._array = array
local mt = getmetatable(self)
mt.__pairs = self.pairwise
end
function Polyline:pairwise()
local f = function(t, i)
i += 1
if i < table.getn(t._array) then
return i, t._array[i], t._array[i+1]
end
end
return f, self, 0
end
And after much search-fu, I think I have determined that, while one can override the default looping behavior in Lua, one cannot do the same thing in Luau, thus not in SLua. There may be a way to override it, but so far all I’ve found is that “it is difficult”, and that __pairs, which is the thing in Lua, is not used in Luau/SLua.
So the above is as good as it could get, based on what I now understand. Well, almost. We can do this:
Polyline = class()
function Polyline:init(array)
self._contents = array
end
function Polyline:pairwise()
local f = function(contents, i)
i += 1
if i < table.getn(contents) then
return i, contents[i], contents[i+1]
end
end
return f, self._contents, 0
end
That simplifies the pairwise function a bit by explicitly grabbing the contents array once and using it inside the function.
How about this:
function Polyline:pairwise()
local f = function(contents, i)
if i < table.getn(contents) - 1 then
return i+1, contents[i+1], contents[i+2]
end
end
return f, self._contents, 0
end
No, I don’t think that’s notably better. More plus and minus going on. Revert that.
Well, not much. If we needed a polyline class and to iterate it a lot, well, it might be worth doing. As things stand for our vehicle moving purposes, I don’t think we need it.
As for the convenience in PolylinePath, I honestly don’t think it buys much, but I’ll leave it in as at least the _create_lengths method is a bit more clear that way.
I see some improvements we could make to PolylinePath. Maybe I’ll write those up. Maybe I’ll just do them.
For now … safe paths!