OpenSCAD

Tables/Dictionary proposal

Classic

List

Threaded

13 messages Options

RevarBat

Tables/Dictionary proposal

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.
};

// Dictionary comprehension.
dict2 = { for (i=[0:100]) if(i%2==0) i : i*5 };

// Extending/merging dictionaries. Later duplicate keys overwrite previous ones.
// Should lists merge into dictionaries using numeric positions as keys?
dict3 = concat(dict1, dict2, {"flee": 0});

// Getting dictionary values.
x = dict3["bar"];
y = dict3[a];
z = dict3["fit"]; // Returns undef for nonexistent keys.

// Iterating a dictionary. Iterate keys in original declared order?
for (key = dict3) {
echo(key=key, val=dict3[key]);
}

This implementation would let me, among other things, rewrite my `vnf_validate()` (a validator for `polyhedron()` data.) to be FAR faster.

- Revar

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

doug.moen

Re: Tables/Dictionary proposal

Here are my comments about Revars dictionary proposal, compared to my record proposal.

Records are restricted to having strings as keys. I use a std::ordered_map with a locale-independent key comparison function, which means that when you iterate over a record, you get the keys in alphabetical order: fully deterministic and very predictable.

Dictionaries are more complicated. If you allow arbitrary values as keys, then do you use an ordered map or a hash map? What is the hash function? Are functions permitted as keys? How do you hash a function? How do you determine function equality? If you use the function address to compute the hash, then you get non-deterministic behaviour. The iteration order of a dictionary will be different on different machines, which could cause shapes to render differently on different machines. That can be nasty. Python solves this problem by preserving the insertion order of a dictionary using a more complicated data structure. Then, when you iterate over a dictionary, the iteration order is the insertion order. This gives you deterministic behaviour back. Even then, I think it is tricky to allow functions to be used as keys, because function equality is not well defined.

Also, for iterating over a dictionary or record, I think it is better to give [key,value] pairs rather than just key values.

On Sat, Mar 20, 2021, at 7:24 PM, 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.
};

// Dictionary comprehension.
dict2 = { for (i=[0:100]) if(i%2==0) i : i*5 };

// Extending/merging dictionaries. Later duplicate keys overwrite previous ones.
// Should lists merge into dictionaries using numeric positions as keys?
dict3 = concat(dict1, dict2, {"flee": 0});

// Getting dictionary values.
x = dict3["bar"];
y = dict3[a];
z = dict3["fit"]; // Returns undef for nonexistent keys.

// Iterating a dictionary. Iterate keys in original declared order?
for (key = dict3) {
echo(key=key, val=dict3[key]);
}
This implementation would let me, among other things, rewrite my `vnf_validate()` (a validator for `polyhedron()` data.) to be FAR faster.

- Revar

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

NateTG

Re: Tables/Dictionary proposal

In reply to this post by RevarBat

It is already possible to create dictionary / associative array functionality using function literals. This is a quick and dirty version that uses a dumb search, but that's something that could be corrected with a little bit of work.

function last(list)=
   let(
      listcheck=assert(is_list(list))
   )
   len(list)-1
;
<raw>
function index_list_find(list,index,i=0)=
   (i>last(list))?
      undef
   :(list[i][0]==index)?
      list[i][1]
   :
      index_list_find(list,index,i+1)
;

function index_list_from_pairs(
   filter=function(index) (is_string(index)),
   pairlist=[],
)=
   let(
      test=[for(item=pairlist) assert(is_list(item) && len(item)==2)]
   )
   [for (item=pairlist) if(filter(item[0])) item]
;

function list_to_pairs(list)=
   let(
      test=assert(0==len(list)%2,"odd length list")
   )
   [for(i=[0:2:last(list)-1]) [list[i],list[i+1]]]
;

function simple_struct(
   arg=undef,
   nlist=[],
   slist=[]
)=
   (is_string(arg))?
      index_list_find(list=slist,index=arg)
   :(is_num(arg))?
      index_list_find(list=nlist,index=arg)
   :(is_list(arg))?
      ("add_list"==arg[0])?
         function (list) (
            simple_struct(arg=["add_pairs"],nlist=nlist,slist=slist) (list_to_pairs(list))
         )
      :("add_pairs"==arg[0])?
         function(pairs) (
            function(arg) (
               simple_struct(
                  arg=arg,
                  nlist=concat(
                     nlist,
                     index_list_from_pairs(
                        filter=function(x) (is_num(x)),
                        pairlist=pairs
                     )
                  )
                  ,
                  slist=concat(
                     slist,
                     index_list_from_pairs(
                        filter=function(x) (is_string(x)),
                        pairlist=pairs
                     )
                  )
               )
            )
         )
      :("keys"==arg[0])?
         concat([for(n=nlist) n[0]],[for(s=slist) s[0]])
      :("values"==arg[0])?
         concat([for(n=nlist) n[1]],[for(s=slist) s[1]])
      :
         assert(false,str("unsupported command:",arg[0]))
   :
      assert(false,str("unexpected argument:",arg))
;

test=simple_struct(["add_pairs"])([ ["a",1],[1,"a"],["1",2]]);

echo(test("a"));
echo(test("1"));
echo(test(1));

test2=test(["add_list"])(["one","two","three","four"]);

echo(test2("one"));
echo(test2(["keys"]));
echo(test2(["values"]));

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

RevarBat

Re: Tables/Dictionary proposal

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. However, I think there may be the promise here for the implementation of faster structures. Since function literals can effectively contain their own data, they can act as nodes. This bears investigation, but I think it will still be a fair lot less efficient than built-in tables.

- Revar

On Mar 20, 2021, at 5:15 PM, NateTG <[hidden email]> wrote:

function last(list)=
   let(
      listcheck=assert(is_list(list))
   )
   len(list)-1
;
<raw>
function index_list_find(list,index,i=0)=
   (i>last(list))?
      undef
   :(list[i][0]==index)?
      list[i][1]
   :
      index_list_find(list,index,i+1)
;

function index_list_from_pairs(
   filter=function(index) (is_string(index)),
   pairlist=[],
)=
   let(
      test=[for(item=pairlist) assert(is_list(item) && len(item)==2)]
   )
   [for (item=pairlist) if(filter(item[0])) item]
;

function list_to_pairs(list)=
   let(
      test=assert(0==len(list)%2,"odd length list")
   )
   [for(i=[0:2:last(list)-1]) [list[i],list[i+1]]]
;

function simple_struct(
   arg=undef,
   nlist=[],
   slist=[]
)=
   (is_string(arg))?
      index_list_find(list=slist,index=arg)
   :(is_num(arg))?
      index_list_find(list=nlist,index=arg)
   :(is_list(arg))?
      ("add_list"==arg[0])?
         function (list) (
            simple_struct(arg=["add_pairs"],nlist=nlist,slist=slist) (list_to_pairs(list))
         )
      :("add_pairs"==arg[0])?
         function(pairs) (
            function(arg) (
               simple_struct(
                  arg=arg,
                  nlist=concat(
                     nlist,
                     index_list_from_pairs(
                        filter=function(x) (is_num(x)),
                        pairlist=pairs
                     )
                  )
                  ,
                  slist=concat(
                     slist,
                     index_list_from_pairs(
                        filter=function(x) (is_string(x)),
                        pairlist=pairs
                     )
                  )
               )
            )
         )
      :("keys"==arg[0])?
         concat([for(n=nlist) n[0]],[for(s=slist) s[0]])
      :("values"==arg[0])?
         concat([for(n=nlist) n[1]],[for(s=slist) s[1]])
      :
         assert(false,str("unsupported command:",arg[0]))
   :
      assert(false,str("unexpected argument:",arg))
;

test=simple_struct(["add_pairs"])([ ["a",1],[1,"a"],["1",2]]);

echo(test("a"));
echo(test("1"));
echo(test(1));

test2=test(["add_list"])(["one","two","three","four"]);

echo(test2("one"));
echo(test2(["keys"]));
echo(test2(["values"]));

Sent from the OpenSCAD mailing list archive at Nabble.com.
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

RevarBat

Re: Tables/Dictionary proposal

In reply to this post by doug.moen

Based on comments, here’s my revised proposal. Main changes are:

- All keys are coerced to strings, similar to `str()`.

- Using `each` for dictionary comprehensions.

- Structure type var.foo syntax.

- Iteration using [key,value].

- Discussion of interaction with ternary ?: operators.

- Discussion of setting values in a dictionary, in both mutable and immutable variants.

// Dictionaries proposal, v2.

// Dictionary declaration.
a = "fee"; b = "fie";
dict1 = {
"foo": 23, // KEY : VALUE
"bar": 77, // Keys are Strings.
false: a, // All keys are coerced into a string via str(). This key is "false"
99 : 34, // This key is the string "99"
56 : "AZ", // Value can be any type.
"bar": 65, // Overwrites previous "bar" key entry.
str("c","a","t") : b // Expressions usable for keys or values.
a>b?a:b : a>b?5:8 // If you have a '?' then the next ':' is part of the ternary expression,
// not a separator. This should always be unambiguous. If not, use parens.
};

// Dictionary comprehension.
dict2 = {
for (i=[0:100])
if(i%2==0) // `if` works as expected.
each { // `each` will expand sub-dictionaries, but only in a dictionary comprehension
i:i*5, // Using `each` on a dictionary in a list comprehension expands into [key,val] items.
i+0.5:i*5+1
}
};

// Extending/merging dictionaries. Later duplicated keys overwrite previous ones.
// Lists merge into dictionaries using numeric positions as keys.
dict3 = concat(dict1, dict2, {"flee":0});

// Getting dictionary values.
w = dict3["bar"];
x = dict3.baz; // Same as dict3["baz"]. Lets you make structures.
y = dict3[a];
z = dict3["fit"]; // Returns undef for nonexistent keys.

// Iterating a dictionary. Iterate keys in original declared order?
for (kv = dict3) {
echo(key=kv[0], val=kv[1]);
}

// If we ever have mutable dictionaries, then you can set items like:
dict3.foo = 17;
dict3["bar"] = 12;

// Otherwise with immutable dictionaries, we end up doing
dict4 = concat(dict3, {"foo":17});
dict5 = {each dict4, "bar":12};

-Revar

On Mar 20, 2021, at 5:08 PM, Doug Moen <[hidden email]> wrote:

Here are my comments about Revars dictionary proposal, compared to my record proposal.

Records are restricted to having strings as keys. I use a std::ordered_map with a locale-independent key comparison function, which means that when you iterate over a record, you get the keys in alphabetical order: fully deterministic and very predictable.

Dictionaries are more complicated. If you allow arbitrary values as keys, then do you use an ordered map or a hash map? What is the hash function? Are functions permitted as keys? How do you hash a function? How do you determine function equality? If you use the function address to compute the hash, then you get non-deterministic behaviour. The iteration order of a dictionary will be different on different machines, which could cause shapes to render differently on different machines. That can be nasty. Python solves this problem by preserving the insertion order of a dictionary using a more complicated data structure. Then, when you iterate over a dictionary, the iteration order is the insertion order. This gives you deterministic behaviour back. Even then, I think it is tricky to allow functions to be used as keys, because function equality is not well defined.

Also, for iterating over a dictionary or record, I think it is better to give [key,value] pairs rather than just key values.

On Sat, Mar 20, 2021, at 7:24 PM, 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.
};

// Dictionary comprehension.
dict2 = { for (i=[0:100]) if(i%2==0) i : i*5 };

// Extending/merging dictionaries. Later duplicate keys overwrite previous ones.
// Should lists merge into dictionaries using numeric positions as keys?
dict3 = concat(dict1, dict2, {"flee": 0});

// Getting dictionary values.
x = dict3["bar"];
y = dict3[a];
z = dict3["fit"]; // Returns undef for nonexistent keys.

// Iterating a dictionary. Iterate keys in original declared order?
for (key = dict3) {
echo(key=key, val=dict3[key]);
}
This implementation would let me, among other things, rewrite my `vnf_validate()` (a validator for `polyhedron()` data.) to be FAR faster.

- Revar

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

JordanBrown

Re: Tables/Dictionary proposal

In reply to this post by RevarBat

My first thought is that the simple case of dictionary literals should allow constant unquoted keys, ala JavaScript:

polar = { rho: 10, theta:0, phi:45 };

That seems like by far the dominant use case, at least in JS. Everything else would have to work around it. The big question is then how you use an expression as the key when creating one of these.

The JavaScript answer is a subscripted assignment, e.g. polar['rho'] = 5;. But that can never fly in OpenSCAD because everything is immutable.

What comes to mind is an alternate syntax, where the name:value could be replaced by [ name, value ]. Thus:

th = "theta";
polar = { rho: 10, [th, 10], phi: 45 };

Perhaps the two alternatives are name:value and expr, where expr must evaluate to a two-element vector. This has implications for non-string keys. Is { 5: 10 } the same as {[5, 10]}? Is { true: "hello" } the same as { [ true, "hello" ] }? Is { [ true, "hello" } ]the same as { [ "true", "hello" ] }?

For comparison, note Torsten's prototype at https://github.com/openscad/openscad/pull/3087. It appears to allow only for constant keys, and uses = as the separator between name and value, to align with normal assignment. That makes this syntax be more like the existing { } syntax, but not like JavaScript or Python.

Some specific comments:

"baz": 19, // Should lists, ranges, or functions be allowed for keys?

No. Not worth the hassle. But if keys can be expressions, they could be allowed in the future.

"bar": 65, // Overwrite previous key entry.

Yes. But mostly to support some sort of concat-like expression.

undef: 77, // Should undef keys be allowed?

Yes.

"bla": undef, // Should undef values be allowed?

Yes, absolutely. (Especially important to allow a concat-like expression to delete values supplied earlier.) No strong opinion on whether this deletes the key or leaves it with a value of undef. The difference would be in how it iterates.

// Getting dictionary values.
x = dict3["bar"];
y = dict3[a];
z = dict3["fit"]; // Returns undef for nonexistent keys.

Should also allow dict3.bar.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

RevarBat

Re: Tables/Dictionary proposal

Hmm. What about a declaration syntax that allows key literals preceded by ‘.’:

dict = { .rho: 10, .theta:0, “foo”:”bar” };

That would make it similar in feel to the key literal getter syntax:

x = dict.theta;

-Revar

On Mar 20, 2021, at 6:08 PM, Jordan Brown <[hidden email]> wrote:
<head> <meta http-equiv="Content-Type" content="text/html; charset=">
My first thought is that the simple case of dictionary literals should allow constant unquoted keys, ala JavaScript:
polar = { rho: 10, theta:0, phi:45 };
That seems like by far the dominant use case, at least in JS. Everything else would have to work around it. The big question is then how you use an expression as the key when creating one of these.

The JavaScript answer is a subscripted assignment, e.g. polar['rho'] = 5;. But that can never fly in OpenSCAD because everything is immutable.

What comes to mind is an alternate syntax, where the name:value could be replaced by [ name, value ]. Thus:
th = "theta";
polar = { rho: 10, [th, 10], phi: 45 };
Perhaps the two alternatives are name:value and expr, where expr must evaluate to a two-element vector. This has implications for non-string keys. Is { 5: 10 } the same as {[5, 10]}? Is { true: "hello" } the same as { [ true, "hello" ] }? Is { [ true, "hello" } ]the same as { [ "true", "hello" ] }?

For comparison, note Torsten's prototype at https://github.com/openscad/openscad/pull/3087. It appears to allow only for constant keys, and uses = as the separator between name and value, to align with normal assignment. That makes this syntax be more like the existing { } syntax, but not like JavaScript or Python.

Some specific comments:
"baz": 19, // Should lists, ranges, or functions be allowed for keys?

No. Not worth the hassle. But if keys can be expressions, they could be allowed in the future.

"bar": 65, // Overwrite previous key entry.

Yes. But mostly to support some sort of concat-like expression.

undef: 77, // Should undef keys be allowed?

Yes.

"bla": undef, // Should undef values be allowed?

Yes, absolutely. (Especially important to allow a concat-like expression to delete values supplied earlier.) No strong opinion on whether this deletes the key or leaves it with a value of undef. The difference would be in how it iterates.

// Getting dictionary values.
x = dict3["bar"];
y = dict3[a];
z = dict3["fit"]; // Returns undef for nonexistent keys.

Should also allow dict3.bar.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

RevarBat

Re: Tables/Dictionary proposal

In reply to this post by RevarBat

Actually, thinking on this, I’m having second thoughts about coercing keys to strings. There’s way too many rounding error problems for numbers. Also, it just feels kind of out of place in OpenSCAD.

We only have a few data types to worry about. Making hashes for each type shouldn’t be hard at all. Function literals could be hashed, but why bother? They could simply be disallowed.

-Revar

On Mar 20, 2021, at 6:07 PM, Revar Desmera <[hidden email]> wrote:

Based on comments, here’s my revised proposal. Main changes are:
- All keys are coerced to strings, similar to `str()`.
- Using `each` for dictionary comprehensions.
- Structure type var.foo syntax.
- Iteration using [key,value].
- Discussion of interaction with ternary ?: operators.
- Discussion of setting values in a dictionary, in both mutable and immutable variants.

// Dictionaries proposal, v2.

// Dictionary declaration.
a = "fee"; b = "fie";
dict1 = {
"foo": 23, // KEY : VALUE
"bar": 77, // Keys are Strings.
false: a, // All keys are coerced into a string via str(). This key is "false"
99 : 34, // This key is the string "99"
56 : "AZ", // Value can be any type.
"bar": 65, // Overwrites previous "bar" key entry.
str("c","a","t") : b // Expressions usable for keys or values.
a>b?a:b : a>b?5:8 // If you have a '?' then the next ':' is part of the ternary expression,
// not a separator. This should always be unambiguous. If not, use parens.
};

// Dictionary comprehension.
dict2 = {
for (i=[0:100])
if(i%2==0) // `if` works as expected.
each { // `each` will expand sub-dictionaries, but only in a dictionary comprehension
i:i*5, // Using `each` on a dictionary in a list comprehension expands into [key,val] items.
i+0.5:i*5+1
}
};

// Extending/merging dictionaries. Later duplicated keys overwrite previous ones.
// Lists merge into dictionaries using numeric positions as keys.
dict3 = concat(dict1, dict2, {"flee":0});

// Getting dictionary values.
w = dict3["bar"];
x = dict3.baz; // Same as dict3["baz"]. Lets you make structures.
y = dict3[a];
z = dict3["fit"]; // Returns undef for nonexistent keys.

// Iterating a dictionary. Iterate keys in original declared order?
for (kv = dict3) {
echo(key=kv[0], val=kv[1]);
}

// If we ever have mutable dictionaries, then you can set items like:
dict3.foo = 17;
dict3["bar"] = 12;

// Otherwise with immutable dictionaries, we end up doing
dict4 = concat(dict3, {"foo":17});
dict5 = {each dict4, "bar":12};

-Revar

On Mar 20, 2021, at 5:08 PM, Doug Moen <[hidden email]> wrote:

Here are my comments about Revars dictionary proposal, compared to my record proposal.

Records are restricted to having strings as keys. I use a std::ordered_map with a locale-independent key comparison function, which means that when you iterate over a record, you get the keys in alphabetical order: fully deterministic and very predictable.

Dictionaries are more complicated. If you allow arbitrary values as keys, then do you use an ordered map or a hash map? What is the hash function? Are functions permitted as keys? How do you hash a function? How do you determine function equality? If you use the function address to compute the hash, then you get non-deterministic behaviour. The iteration order of a dictionary will be different on different machines, which could cause shapes to render differently on different machines. That can be nasty. Python solves this problem by preserving the insertion order of a dictionary using a more complicated data structure. Then, when you iterate over a dictionary, the iteration order is the insertion order. This gives you deterministic behaviour back. Even then, I think it is tricky to allow functions to be used as keys, because function equality is not well defined.

Also, for iterating over a dictionary or record, I think it is better to give [key,value] pairs rather than just key values.

On Sat, Mar 20, 2021, at 7:24 PM, 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.
};

// Dictionary comprehension.
dict2 = { for (i=[0:100]) if(i%2==0) i : i*5 };

// Extending/merging dictionaries. Later duplicate keys overwrite previous ones.
// Should lists merge into dictionaries using numeric positions as keys?
dict3 = concat(dict1, dict2, {"flee": 0});

// Getting dictionary values.
x = dict3["bar"];
y = dict3[a];
z = dict3["fit"]; // Returns undef for nonexistent keys.

// Iterating a dictionary. Iterate keys in original declared order?
for (key = dict3) {
echo(key=key, val=dict3[key]);
}
This implementation would let me, among other things, rewrite my `vnf_validate()` (a validator for `polyhedron()` data.) to be FAR faster.

- Revar

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

caterpillar

Re: Tables/Dictionary proposal

In reply to this post by RevarBat

I implement a simple hashmap in[dotSCAD](https://github.com/JustinSDK/dotSCAD).
https://openhome.cc/eGossip/OpenSCAD/lib3x-hashmap.html

I have it in dotSCAD because something requires it, such as OpenSCAD Wave Function Collapse.
https://twitter.com/caterpillar/status/1372372145901244416

https://openhome.cc

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

https://openhome.cc

caterpillar

Re: Tables/Dictionary proposal

In reply to this post by RevarBat

RevarBat 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.
};

// Dictionary comprehension.
dict2 = { for (i=[0:100]) if(i%2==0) i : i*5 };

// Extending/merging dictionaries. Later duplicate keys overwrite previous ones.
// Should lists merge into dictionaries using numeric positions as keys?
dict3 = concat(dict1, dict2, {"flee": 0});

// Getting dictionary values.
x = dict3["bar"];
y = dict3[a];
z = dict3["fit"]; // Returns undef for nonexistent keys.

// Iterating a dictionary. Iterate keys in original declared order?
for (key = dict3) {
echo(key=key, val=dict3[key]);
}

This implementation would let me, among other things, rewrite my `vnf_validate()` (a validator for `polyhedron()` data.) to be FAR faster.

- Revar

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

A workaround...

// require https://github.com/JustinSDK/dotSCAD
use <util/map/hashmap.scad>;
use <util/map/hashmap_entries.scad>;
use <util/map/hashmap_get.scad>;
use <util/map/hashmap_keys.scad>;

a = "fee";
b = "fie";

m1 = hashmap([
["foo", 23],
["bar", 77],
[false, a],
[99 , 34],
[56 , "AZ"],
["baz", 19],
["bar", 65],
[undef, 77],
["bla", undef],
[str("c","a","t"), b]
]);

m2 = hashmap([
for(i =[0:100]) if(i%2 == 0) [i, i * 5]
]);

m3 = hashmap(concat(hashmap_entries(m1), hashmap_entries(m2)));

x = hashmap_get(m3, "bar");
y = hashmap_get(m3, a);
z = hashmap_get(m3, "fit");

for (key = hashmap_keys(m3)) {
echo(key=key, val=hashmap_get(m3, key));
}

https://openhome.cc

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

https://openhome.cc

cacb

Re: Tables/Dictionary proposal

In reply to this post by RevarBat

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
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

NateTG

Re: Tables/Dictionary proposal

In reply to this post by RevarBat

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.

function last(list)=
   let(
      listcheck=assert(is_list(list))
   )
   len(list)-1
;

function index_list_find(list,index,start=0,end=undef)=
   let(
      last=(is_undef(end)?last(list):end),
      pivot=ceil( (start+last)/2 )
   )
   (list[pivot][0]==index)?
      list[pivot][1]
   :(list[pivot][0]<index)?
      (pivot==last)?
         undef
      :
         index_list_find(list,index,start=pivot+1,end=last)
   ://(list[pivot][0]>index)
      (pivot==start)?
         undef
      :
         index_list_find(list,index,start=start,end=pivot-1)  
;

function index_quicksort(arr) = !(len(arr)>0) ? [] : let(
    pivot   = arr[floor(len(arr)/2)],
    lesser  = [ for (y = arr) if (y[0]  < pivot[0]) y ],
    equal   = [ for (y = arr) if (y[0] == pivot[0]) y ],
    greater = [ for (y = arr) if (y[0]  > pivot[0]) y ]
) concat(
    index_quicksort(lesser), equal, index_quicksort(greater)
);

function index_list_from_pairs(
   filter=function(index) (is_string(index)),
   pairlist=[],
)=
   let(
      test=[for(item=pairlist) assert(is_list(item) && len(item)==2)]
   )
   [for (item=pairlist) if(filter(item[0])) item]
;

function list_to_pairs(list)=
   let(
      test=assert(0==len(list)%2,"odd length list")
   )
   [for(i=[0:2:last(list)-1]) [list[i],list[i+1]]]
;

function simple_struct(
   arg=undef,
   nlist=[],
   slist=[]
)=
   (is_string(arg))?
      index_list_find(list=slist,index=arg)
   :(is_num(arg))?
      index_list_find(list=nlist,index=arg)
   :(is_list(arg))?
      ("add_list"==arg[0])?
         function (list) (
            simple_struct(arg=["add_pairs"],nlist=nlist,slist=slist) (list_to_pairs(list))
         )
      :("add_pairs"==arg[0])?
         function(pairs) (
            function(arg) (
               simple_struct(
                  arg=arg,
                  nlist=index_quicksort(
                     concat(
                        nlist,
                        index_list_from_pairs(
                           filter=function(x) (is_num(x)),
                           pairlist=pairs
                        )
                     )
                  )
                  ,
                  slist=index_quicksort(
                     concat(
                        slist,
                        index_list_from_pairs(
                           filter=function(x) (is_string(x)),
                           pairlist=pairs
                        )
                     )
                  )
               )
            )
         )
      :("keys"==arg[0])?
         concat([for(n=nlist) n[0]],[for(s=slist) s[0]])
      :("values"==arg[0])?
         concat([for(n=nlist) n[1]],[for(s=slist) s[1]])
      :
         assert(false,str("unsupported command:",arg[0]))
   :
      assert(false,str("unexpected argument:",arg))
;

test=simple_struct(["add_pairs"])([ ["a",1],[1,"a"],["1",2]]);

echo(test("a"));
echo(test("1"));
echo(test(1));

test2=test(["add_list"])(["one","two","three","four"]);

echo(test2("one"));
function last(list)=
   let(
      listcheck=assert(is_list(list))
   )
   len(list)-1
;

function index_list_find(list,index,start=0,end=undef)=
   let(
      last=(is_undef(end)?last(list):end),
      pivot=ceil( (start+last)/2 )
   )
   (list[pivot][0]==index)?
      list[pivot][1]
   :(list[pivot][0]<index)?
      (pivot==last)?
         undef
      :
         index_list_find(list,index,start=pivot+1,end=last)
   ://(list[pivot][0]>index)
      (pivot==start)?
         undef
      :
         index_list_find(list,index,start=start,end=pivot-1)  
;

function index_quicksort(arr) = !(len(arr)>0) ? [] : let(
    pivot   = arr[floor(len(arr)/2)],
    lesser  = [ for (y = arr) if (y[0]  < pivot[0]) y ],
    equal   = [ for (y = arr) if (y[0] == pivot[0]) y ],
    greater = [ for (y = arr) if (y[0]  > pivot[0]) y ]
) concat(
    index_quicksort(lesser), equal, index_quicksort(greater)
);

function index_list_from_pairs(
   filter=function(index) (is_string(index)),
   pairlist=[],
)=
   let(
      test=[for(item=pairlist) assert(is_list(item) && len(item)==2)]
   )
   [for (item=pairlist) if(filter(item[0])) item]
;

function list_to_pairs(list)=
   let(
      test=assert(0==len(list)%2,"odd length list")
   )
   [for(i=[0:2:last(list)-1]) [list[i],list[i+1]]]
;

function simple_struct(
   arg=undef,
   nlist=[],
   slist=[]
)=
   (is_string(arg))?
      index_list_find(list=slist,index=arg)
   :(is_num(arg))?
      index_list_find(list=nlist,index=arg)
   :(is_list(arg))?
      ("add_list"==arg[0])?
         function (list) (
            simple_struct(arg=["add_pairs"],nlist=nlist,slist=slist) (list_to_pairs(list))
         )
      :("add_pairs"==arg[0])?
         function(pairs) (
            function(arg) (
               simple_struct(
                  arg=arg,
                  nlist=index_quicksort(
                     concat(
                        nlist,
                        index_list_from_pairs(
                           filter=function(x) (is_num(x)),
                           pairlist=pairs
                        )
                     )
                  )
                  ,
                  slist=index_quicksort(
                     concat(
                        slist,
                        index_list_from_pairs(
                           filter=function(x) (is_string(x)),
                           pairlist=pairs
                        )
                     )
                  )
               )
            )
         )
      :("keys"==arg[0])?
         concat([for(n=nlist) n[0]],[for(s=slist) s[0]])
      :("values"==arg[0])?
         concat([for(n=nlist) n[1]],[for(s=slist) s[1]])
      :
         assert(false,str("unsupported command:",arg[0]))
   :
      assert(false,str("unexpected argument:",arg))
;

test=simple_struct(["add_pairs"])([ ["a",1],[1,"a"],["1",2]]);

echo(test("a"));
echo(test("1"));
echo(test(1));

test2=test(["add_list"])(["one","two","three","four"]);

echo(test2("one"));

echo("keys",test2(["keys"]));

echo(test2("foo"));
echo("keys",test2(["keys"]));
echo("values",test2(["values"]));

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]

Troberg

Re: Tables/Dictionary proposal

In reply to this post by doug.moen

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 the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]