discuss@lists.openscad.org

OpenSCAD general discussion Mailing-list

View all threads

Tables/Dictionary proposal

A
arnholm@arnholm.org
Sun, Mar 21, 2021 9:21 AM

On 2021-03-21 00:24, Revar Desmera wrote:

Here’s my first pass thoughts on an immutable table/dictionary data
type for OpenSCAD:

// Dictionary declaration.
a = "fee"; b = "fie";
dict1 = {
"foo": 23,    // KEY : VALUE
"bar": 77,    // String keys.
false: a,    // Boolean keys.
99  : 34,    // Numeric keys.
56  : "AZ",  // Value can be any type.
"baz": 19,    // Should lists, ranges, or functions be allowed
for keys?
"bar": 65,    // Overwrite previous key entry.
undef: 77,    // Should undef keys be allowed?
"bla": undef, // Should undef values be allowed?
str("c","a","t") : b  // Expressions usable for keys or values.
};

For what it is worth, most languages have these kind of look-up tables.
AngelCAD has both 'map' and 'dictionary':

A 'map' is a look-up table where the key and value types can be
anything, but all the entries have the same key and value types:

// type-safe map of integers
map<string,int> dict1;
dict1.insert("foo",23);
dict1.insert("bar",77);

Since geometric objects also have types, you can include them in a map.
If the abstract shape@ type is used in the declaration, you can have a
mixture of 2d or 3d objects in the same map (the @ denotes a handle):

// type-safe map of abstract 2d or 3d shapes
map<string,shape@> dict2;
dict2.insert("sphere",sphere(33));
dict2.insert("circle",circle(50));

A slightly different look-up table is the 'dictionary' type, which uses
only strings as keys, but the value type can be anything and can vary
between entries in the dictionary:

// dictionary of mixed types
dictionary dict3 = {
    {"foo", 23}
   ,{"bar", 77}
   ,{"sphere", @sphere(33)}
   ,{"circle", @circle(50)}
 };

Personally, I find the map more useful than dictionary.

Carsten Arnholm

On 2021-03-21 00:24, Revar Desmera wrote: > Here’s my first pass thoughts on an immutable table/dictionary data > type for OpenSCAD: > >> // Dictionary declaration. >> a = "fee"; b = "fie"; >> dict1 = { >> "foo": 23, // KEY : VALUE >> "bar": 77, // String keys. >> false: a, // Boolean keys. >> 99 : 34, // Numeric keys. >> 56 : "AZ", // Value can be any type. >> "baz": 19, // Should lists, ranges, or functions be allowed >> for keys? >> "bar": 65, // Overwrite previous key entry. >> undef: 77, // Should undef keys be allowed? >> "bla": undef, // Should undef values be allowed? >> str("c","a","t") : b // Expressions usable for keys or values. >> }; For what it is worth, most languages have these kind of look-up tables. AngelCAD has both 'map' and 'dictionary': A 'map' is a look-up table where the key and value types can be anything, but all the entries have the same key and value types: // type-safe map of integers map<string,int> dict1; dict1.insert("foo",23); dict1.insert("bar",77); Since geometric objects also have types, you can include them in a map. If the abstract shape@ type is used in the declaration, you can have a mixture of 2d or 3d objects in the same map (the @ denotes a handle): // type-safe map of abstract 2d or 3d shapes map<string,shape@> dict2; dict2.insert("sphere",sphere(33)); dict2.insert("circle",circle(50)); A slightly different look-up table is the 'dictionary' type, which uses only strings as keys, but the value type can be anything and can vary between entries in the dictionary: // dictionary of mixed types dictionary dict3 = { {"foo", 23} ,{"bar", 77} ,{"sphere", @sphere(33)} ,{"circle", @circle(50)} }; Personally, I find the map more useful than dictionary. Carsten Arnholm
N
NateTG
Sun, Mar 21, 2021 5:43 PM

RevarBat wrote

As I understand this code, it still has an O(n) key search time, and it’s
not even making use of search().  So, pretty slow for a table.  That’s
not even getting into the construction time. ...

I did write that the dumb search could be fixed easily.  To prove it, a
version that uses quicksort (average O(n log n) )  during construction and a
binary search O(log n) during lookup is below.  Again, this is quick and
dirty stuff. I'm sure there are ways to do that with better performance
characteristics.

It's true that a "table feature" would make for faster implementation, but
implementing the data structure in OpenScad means that the end user can (at
least in principle) modify the behavior of the list themselves.  So if
someone decides that a dictionary miss should be an assert(false) instead of
an undef, then they can do that without involving the OpenScad devs or
waiting for a new version to come out.

--
Sent from: http://forum.openscad.org/

RevarBat wrote > As I understand this code, it still has an O(n) key search time, and it’s > not even making use of `search()`. So, pretty slow for a table. That’s > not even getting into the construction time. ... I did write that the dumb search could be fixed easily. To prove it, a version that uses quicksort (average O(n log n) ) during construction and a binary search O(log n) during lookup is below. Again, this is quick and dirty stuff. I'm sure there are ways to do that with better performance characteristics. It's true that a "table feature" would make for faster implementation, but implementing the data structure in OpenScad means that the end user can (at least in principle) modify the behavior of the list themselves. So if someone decides that a dictionary miss should be an assert(false) instead of an undef, then they can do that without involving the OpenScad devs or waiting for a new version to come out. -- Sent from: http://forum.openscad.org/
T
Troberg
Mon, Mar 22, 2021 8:25 AM

doug.moen wrote

Records are restricted to having strings as keys.

Strings as keys is plenty enough for me. You can easily encode any other
datatype as a string anyway.

--
Sent from: http://forum.openscad.org/

doug.moen wrote > Records are restricted to having strings as keys. Strings as keys is plenty enough for me. You can easily encode any other datatype as a string anyway. -- Sent from: http://forum.openscad.org/