On Sep 20, 2014, at 12:22 PM, Thiago L. <fakedme@gmail.com> wrote:
On 20/09/14 04:09 PM, Tim Hill wrote:
On Sep 20, 2014, at 5:05 AM, Thiago L. <fakedme@gmail.com> wrote:
Also posted on http://stackoverflow.com/q/25922437/3691554
So I've been writing deep-copy algorithms, and I wanna test them to see if they work the way I want them to. While I do have access to the original->copy map, I want a general-purpose deep-compare algorithm that must be able to compare table keys (tables as keys?). The #Lua channel on Freenode thinks it's impossible, I just think it's really hard.
My deep-copy algorithm(s) are avaliable here: https://gist.github.com/SoniEx2/fc5d3614614e4e3fe131 (it's not very organized, but there are 3 of them, one uses recursive calls, the other uses a todo table, and the other simulates a call stack (in a very ugly but 5.1-compatible way))
I assume you mean “equivalent” rather than “equal”, in the sense that two tables are equal if they have the same content, not are the same table? Otherwise you would be talking shallow compare.
—Tim
I don't think I ever claimed equality...
Well, roughly..
(1) Get keys of both tables into lua arrays, and sort them using some scheme that works across all Lua types.
(2) Compare the keys; if the two arrays are different, tables are different
(3) Where two keys in the arrays match, compare the types of the values; if the types are different the tables are different
(4) If the types of the values are the same and NOT tables, compare the values directly, if the values are different the tables are different
(5) For table values, recursively compare them using the same algorithm
This algorithm does not, however, address the issue of equivalent vs equal, as I noted. In fact, as written it assumes tables must be EQUAL for keys but EQUIVALENT for values, which is cleanly nonsense. To correct this, you need to build a correspondence table that maps tables in one copy to tables in the other copy, and then use this table when comparing tables for equality (this also optimizes performance when the same table occurs multiples times, and can be used to break inner table “loops” when you traverse the table graph).
—Tim
