I have already pointed out that it is hard to write non-trivial data
structures in OpenSCAD. I see two main reasons for that: the only intrinsic
data structure in OpenSCAD is list (officially called vector) with very
basic operators and any change in a data structure implies in rewriting all
the structure because of the lack of variables and assignments in OpenSCAD.
Yes, I know that OpenSCAD is not a programming language.

A 2-3 tree is not a trivial data structure and I suspect its implementation
code would be ugly in any programming language. But I think you could
improve your code readability by providing a proper set of atomic functions
to operate over the subjacent node representation. So, your higher level
functions (for insertion for instance) would not be cluttered by operations
on the list components of tree nodes. As an example, the expression:

[node[1],[tree,node[1],[node[2],node[3],node[4]]]]

appearing somewhere in addtreetotreenode function definition seems to be
more readable  (although not always concise) as something like:

let( lval = left_val(node), l2node = left_val(node) )
...

new_2_leaf( lval, new_2_node( tree, lval, l2node ) )

2018-01-26 1:10 GMT-02:00 NateTG nate-openscadforum@pedantic.org:

Thanks for looking at it.  Reading other people's code isn't always the
easiest thing in the world.  I'm still finding my feet in this purely
functional approach, so it's not surprising that it's ugly.  (TBH, I'm a
little surprised at how easily I got it working.)

A specific question is whether my sense that adding or removing any data
from a structure is always going to involve reconstructing the insert or
remove path, and it seems like the answer to that is yes.

Do you know if OpenSCAD has garbage collection or some other memory
management scheme?

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

There is no information hiding resource in OpenSCAD. However, the coder can
avoid to mix lower and higher level operations by using proper atomic
functions for creation, inspecting and information retrieval of data nodes
virtually isolating its data representation from data structure operations.
I would not call those atomic functions as helper functions.

Nate's treefindvalue() function for instance might have the following much
more readable form:

function is_in_tree(tree, value) =
let( Lvalue = Lvalue(tree),
Rvalue = Rvalue(tree),
left = Lbranch(tree),
right = Rbranch(tree) )
is_2node(tree)?
( value==Lvalue )
|| ( (value<Lvalue) && is_in_tree(left, value) )
|| is_in_tree(right, value)
:is_3node(tree)?
(value==Lvalue)
|| ( value==Rvalue )
|| ( (value<Lvalue) && is_in_tree(left, value) )
|| ( (value>Rvalue) && is_in_tree(right, value) )
|| is_in_tree(Cbranch(tree), value)
:is_2leaf(tree)?
( value==Lvalue )
|| ( value==Rvalue )
:is_leaf(tree) && (value==Lvalue)
;

where a bunch of data representation access functions are called. To write
and read this code we don't need know where the left branch Lbranch() is
stored or how the test is_2node(tree) is performed. The code of is_in_tree
may be a bit less efficient than Nate's one but readability,
maintainability are prime qualities.

The algorithms for value insertion and removal from a 2-3 tree require the
manipulation of temporary abnormal nodes storing 3 values. So, the node
data representation should be able to store that kind of nodes. A set of
functions for creation, testing and value retrieval of temporary nodes may
be:

// temporary nodes
function tnode(v1,v2,v3, t1,t2,t3) = [t1, v1, t2, v2, t3, v3]; // creation
function is_temp(t) = (len(t)==6); // testing
function Tvalue(tree,ind) = t[2ind+1]; // retrieval
function Tbranch(tree,ind) = t[2ind];

By calling those functions, the value insertion coding will be easier and
the code clearer.

2-3 tree is a data abstraction for the user code. The node might be
regarded as a data abstraction for the 2-3 tree data structure.

2018-01-26 17:05 GMT-02:00 doug moen doug@moens.org:

2018-01-26 13:35 GMT-02:00 NateTG nate-openscadforum@pedantic.org:

​My greatest concerns on defining data structures in OpenSCAD language are
not the lacking of a garbage collection but the order of complexity. For
instance, the element insertion and re​moving from  2-3 trees have order
O(log n). However, an analysis of your implementation in OpenSCAD will show
that its order of complexity is O(n2) or worst due to the repeated structure
copies required by  any change in it. And this is true for any data
structure.

So, I think there is no point in using complex data structures in OpenSCAD.
A simple ordered list is as good as any search tree.

order O(log n). However, an analysis of your implementation in OpenSCAD will
show that its order of complexity is O(n2) or worst due to the repeated
structure copies required by  any change in it.  ...

Does OpenSCAD never use references (so that if there's some variable a, then
b=[a] is going to create a copy of it)?

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

OpenSCAD uses references to reference-counted, immutable values. Multiple
variables can point to the same immutable list object. There is no need for
OpenSCAD to make copies of lists, since there are no operations for
mutating a list. AFAIK; I haven't read all the code in the interpreter.

I don't think there's much point in worrying about this, though. Like
Ronaldo says, just use the simplest possible data structure. If this leads
to a performance problem, and you want to use a more complicated data
structure, you should measure the performance to ensure that the more
complicated code is actually faster. OpenSCAD doesn't have the same
performance characteristics as conventional languages, so your complicated
code might be slower.

On 30 January 2018 at 18:05, NateTG nate-openscadforum@pedantic.org wrote:

The question is how to build things like Delaunay triangulation when
needed. You can't do it without the support of a complex data structure.

2018-01-30 21:16 GMT-02:00 doug moen doug@moens.org: