Programming in Functional OpenSCAD

classic Classic list List threaded Threaded
42 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Re: Programming in Functional OpenSCAD

NateTG
If you're feeling silly, you can do a sort by multiple indices built on the
quicksort template. This probably ends up being a bunch slower, and it
should probably be modified to handle non-list arguments gracefully.


function listgt (a,b,list,i=0) =
   (i<len(list)-1 &amp;&amp; list[i]&lt;len(a)-1 &amp;&amp;
list[i]&lt;len(b)-1 &amp;&amp; a[list[i]]==b[list[i]])?
      listgt(a,b,list,i+1)
   :(i&lt;len(list)-1 &amp;&amp; list[i]&lt;len(a)-1 &amp;&amp;
list[i]&lt;len(b)-1 &amp;&amp; a[list[i]]>b[list[i]])?
      true
   :(i<len(list)-1 &amp;&amp; list[i]&lt;len(a)-1 &amp;&amp;
list[i]&lt;len(b)-1 &amp;&amp; a[list[i]]&lt;b[list[i]])?
      false
   :
      false
;

function listeq (a,b,list,i=0) =
   (i&lt;len(list)-1 &amp;&amp; list[i]&lt;len(a)-1 &amp;&amp;
list[i]&lt;len(b)-1 &amp;&amp; a[list[i]]==b[list[i]])?
      listeq(a,b,list,i+1)
   :(i&lt;len(list)-1 &amp;&amp; list[i]&lt;len(a)-1 &amp;&amp;
list[i]&lt;len(b)-1 &amp;&amp; a[list[i]]>b[list[i]])?
      false
   :(i<len(list)-1 &amp;&amp; list[i]&lt;len(a)-1 &amp;&amp;
list[i]&lt;len(b)-1 &amp;&amp; a[list[i]]&lt;b[list[i]])?
      false
   :(i==len(list)-1)?
      true
   :
      false
;

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



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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Programming in Functional OpenSCAD

Ronaldo
If you're feeling silly, you can do a sort by multiple indices built on the
quicksort template. This probably ends up being a bunch slower, and it
should probably be modified to handle non-list arguments gracefully.
 
​I agree that sophistication ​may be included in quicksort to cope efficiently with more general settings like lexicographic sorting. First class function would be helpful but external templates is another way to go.

Quicksort is a simple algorithm were it is easy to make the necessary changes to other circumstances. But how to do it with the 2-3 tree insertion and removal? If you had coded them using access functions to node records may be it was a question of changing a few functions and calling points.

As an exercise, I have recoded the 2-3 tree insertion mediated by node access functions instead of direct node field access. There is 7 value comparison points to review  for a more general setting. However, the tree insertion running time has doubled, a price to pay for flexibility.


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
123