Ordered sets/tables

[vpax]

We keep running into situations where it would be handy to have two different notions of ordering associated with sets and tables.

One type of ordering is "insertion order", meaning that the container remembers the order in which items were added. This would then be the order in which elements are provided for for loops or when printing/logging (other than per the next item).

The other type of ordering is "canonical ordering", meaning that if you print/log the container, the elements always come out in a given order. One could imagine doing this by allowing the script writer to specify an associated comparison function (for sorting); or an associated canonicalizer (which might sort but might do something else); and/or having standard canonical formats for all the easy cases (strings are lexical, numerics are by the usual numerical ordering, IP addresses by conversion-to-integer-equivalent).

For canonical ordering, it's not clear to me whether that needs to be the for loop ordering - I think it's probably okay that it isn't, and that would also allow the use of both "insertion ordering" (which would affect loop ordering) and "canonical ordering" (which would override it when printing/logging).

[timwoj]

We currently have ORDERED and UNORDERED modes for Dictionary objects. ORDERED mode is the "insertion order" version that you're describing above. We don't modify the table elements for it, but we keep the keys in a separate vector in the order they were inserted. When we do retrievals based on indexes (and for looping) we actually do the lookup into the ordered list and go off that ordering instead.

It wouldn't be too much effort to add a canonical ordering mode that does something similar, but keeps the ordered vector sorted based on a predicate method provided to the Dictionary object when it's created. There'd obviously be a performance loss for the sorting during insertion, but code complexity would remain basically the same since it would be using the same mechanisms used for the ORDERED version for everything else.

[timwoj]

Another question here that I just thought of (as I'm looking at another Dictionary issue) is how this would be controlled via script-land. Most likely the easiest way is to add an attribute that you can pass when creating a table or set. That attribute would get passed down to the TableVal constructor to set the ordering on the internal Dictionary.

[timwoj]

The &ordered attribute was added in the PR above. &sorted shouldn't be too much harder, once I sort out how to cleanly call script functions from C++.