Hi there!

The problem is rather simple:

I want to have an algorithm which
can handle different lengths of arrays for
the following problem:

Given a float (eg 50), I want a loop
to generate a new value, which has a certain
distance from the given x amount of former
units (thats the "different length array", saving
the floats generated for x former values).

A #while-statement shall check, if the feshly
generated number is identical or within a
given range of the former values. If it is, it
generates a new value, until it generates
a valid one.

The actual code, as of yet, looks like this:

/**/
#declare Max_Angle = 40; //Given float
#declare Angle_Dif=10; //Distance range from former values
#declare Mem_Angle=3; //Former values to be saved

#declare Former=array[Mem_Angle]
//Initialize empty array
#declare F=0; #while (F<Mem_Angle) #declare Former[F]=0; #declare F=F+1;
#end

 #declare Num_1=rand(Rand)*Max_Angle;
//Should check if within range
 #while (
  #declare F=0; #while (F<Mem_Angle)
    (Num_1>=Former[F]-Angle_Dif & Num_1<=Former[F]+Angle_Dif) &
   #declare F=F+1; #end
    true //(Num_1>=Former[F]-Angle_Dif & Num_1<=Former[F]+Angle_Dif)
    //Num_1=Former[Mem_Angle-1]
    )
//Create new value
  #declare Num_1=rand(Gerb_Rand)*Max_Angle;
 #end

//Put new value inside the array and erase oldest
 #declare F=Mem_Angle-1; #while (F>0) #declare Former[F]=Former[F-1];
#declare F=F-1; #end
 #declare Former[0]=Num_1;

The actual code of value-generation, the checking, and the
saving, is done inside a loop (which is the obvious
use for this)

Any comments?

--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html

Post a reply to this message

Found the problem. The check had the error
with all those "&"s, there have should been
a "|" after each pair of boolean-statements.

So that's cleaned up, and actually also put into
two small macros to easily create such a
memorizing array. If anyone want it, post a
reply, I'll post the small include file at
p.b.s-f.


> //Should check if within range
>  #while (
>   #declare F=0; #while (F<Mem_Angle)
>     (Num_1>=Former[F]-Angle_Dif & Num_1<=Former[F]+Angle_Dif) & <===
> Error, replace "&" with "|"
>    #declare F=F+1; #end
>     true //(Num_1>=Former[F]-Angle_Dif & Num_1<=Former[F]+Angle_Dif)
>     //Num_1=Former[Mem_Angle-1]
>     )

--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html

Post a reply to this message

Of course this algorithm is very slow with a large amount of coordinates,
but there's little one can do to help this in the current SDL (speeding this
up would need a more advanced data structure, such as a binary tree or hash
table).

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

Using the Current SDL, I think it would be possible to
write a binary-tree-data-structure in a 1D-array. You'd
probably have to use some loops or perhaps even
recursive macros, but it can be done. If it must be proven,
I'll do it, when I have some free time, because I think
binary-tree-structures might be useful in many cases.

But for my needs, running through a few floats isn't
worth the amount of calculation and time I'd have to
spend in order to write a binary-tree.


--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html

Post a reply to this message

On Sun, 24 Mar 2002 13:08:12 +0100, Tim Nikias wrote:
> Using the Current SDL, I think it would be possible to
> write a binary-tree-data-structure in a 1D-array. You'd
> probably have to use some loops or perhaps even
> recursive macros, but it can be done. If it must be proven,
> I'll do it, when I have some free time, because I think
> binary-tree-structures might be useful in many cases.

A binary tree can always be put in a 1-d array.  It's simple: Given a
cell with index n, the left child of that cell is at index n*2 and
the right child of that cell is at index n*2+1.  The parent of that
cell is, obviously, at index int(n/2).  A few macros to implement that
scheme and there you go.

However, it would only be useful with numbers and strings and possibly
vectors (but for vectors you'd have to define a sort order.)

-- 
#macro R(L P)sphere{L F}cylinder{L P F}#end#macro P(V)merge{R(z+a z)R(-z a-z)R(a
-z-z-z a+z)torus{1F clipped_by{plane{a 0}}}translate V}#end#macro Z(a F T)merge{
P(z+a)P(z-a)R(-z-z-x a)pigment{rgbf 1}hollow interior{media{emission 3-T}}}#end 
Z(-x-x.2x)camera{location z*-10rotate x*90normal{bumps.02scale.05}}

Post a reply to this message

Ron Parker <ron### [at] povrayorg> wrote:
> A binary tree can always be put in a 1-d array.  It's simple: Given a
> cell with index n, the left child of that cell is at index n*2 and
> the right child of that cell is at index n*2+1.  The parent of that
> cell is, obviously, at index int(n/2).  A few macros to implement that
> scheme and there you go.

  Yes, but would it be as fast as a regular binary tree (ie one where
items are allocated dynamically and which contains pointers to children)?
For example adding a new item or removing an item can be slow.

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

On 24 Mar 2002 15:00:38 -0500, Warp wrote:
> Ron Parker <ron### [at] povrayorg> wrote:
>> A binary tree can always be put in a 1-d array.  It's simple: Given a
>> cell with index n, the left child of that cell is at index n*2 and
>> the right child of that cell is at index n*2+1.  The parent of that
>> cell is, obviously, at index int(n/2).  A few macros to implement that
>> scheme and there you go.
> 
>   Yes, but would it be as fast as a regular binary tree (ie one where
> items are allocated dynamically and which contains pointers to children)?
> For example adding a new item or removing an item can be slow.

It wouldn't be any slower than a regular binary tree, but it would have a
limit on the maximum depth, it would take up more storage than absolutely
necessary, and it couldn't be balanced.  Subject to those contraints, though,
it wouldn't need to move any data around to insert or delete a node.  

Unfortunately, the combination of "can't be balanced" and "maximum depth" 
leads to it being only theoretically useful, since it's very sensitive to 
the order you add elements.

-- 
#local R=rgb 99;#local P=R-R;#local F=pigment{gradient x}box{0,1pigment{gradient
y pigment_map{[.5F pigment_map{[.3R][.3F color_map{[.15red 99][.15P]}rotate z*45
translate x]}]#local H=pigment{gradient y color_map{[.5P][.5R]}scale 1/3}[.5F
pigment_map{[.3R][.3H][.7H][.7R]}]}}}camera{location.5-3*z}//only my opinions

Post a reply to this message

I've had my experiences with implementing Binary-Trees with
JAVA, and there are some things I'd just want to add to this
little conversation:
1. Maximum depth could be overcome by "moving" the structure
into a larger array (though a little parsing intensive, not at all
useless under certain circumstances).
2. Moving across the binary tree, using macros, would require
only a very simple system
3. Inserting and deleting entries using a dropping-algorithm
(forgot the actual name right now), where the smaller values
simply "trickle" through till the bottom of the tree, wouldn't be
that difficult to add, its just a recursive macro-call, or could perhaps
even be put into a while-loop

So, all in all, the question is rather, if the amount of macros and
parsing needed to use them all, is really needed, or if you can
go by with other means.

Just my two cents worth.

--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html

Post a reply to this message

Tim Nikias <tim### [at] gmxde> wrote:
> 3. Inserting and deleting entries using a dropping-algorithm
> (forgot the actual name right now), where the smaller values
> simply "trickle" through till the bottom of the tree, wouldn't be
> that difficult to add, its just a recursive macro-call, or could perhaps
> even be put into a while-loop

  Don't confuse a binary tree with a binary heap.
  A heap is very easy and fast to construct. Rearranging an array into a
heap can be done statically and in O(n*log n) time. Inserting a value
into a heapified array can be done statically and in O(log n) time.
  However, a heap is not a binary tree and doesn't have the advantages of
the tree. You can't find a certain item in a heap in O(log n) time, as you
can do in a tree. If you want to insert a new value in a "treed" array it will
probably require at least O(n) time, perhaps even O(n*log n) (I'm not
sure about this, so I may well be wrong).

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

In article <slr### [at] fwicom> , Ron Parker 
<ron### [at] povrayorg>  wrote:

> It wouldn't be any slower than a regular binary tree, but it would have a
> limit on the maximum depth, it would take up more storage than absolutely
> necessary, and it couldn't be balanced.

Actually, this implies it isn't possible to make an array (of arbitrary size,
of course) an element of another array, or is this possible?  I have to admit
I never tried, but from the code I cannot really see a reason why it shouldn't
be possible other than as being a yet another parser limitation...

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

Actually, the following at least seems to work.  Of course, I have not checked
if it doesn't corrupt any internal data:

    #declare foo = array[40];

    #declare foo[1] = array[10];
    #declare foo[2] = array[5];

    #declare foo[1][5] = 5.0;

As far as I can tell this is, together with the ability to undef arrays
sufficient to build linked structures...


    Thorsten


____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

On Mon, 25 Mar 2002 10:45:41 +0100, "Thorsten Froehlich" <tho### [at] trfde>
wrote:
> Actually, this implies it isn't possible to make an array (of arbitrary size,
> of course) an element of another array, or is this possible?  I have to admit
> I never tried, but from the code I cannot really see a reason why it shouldn't
> be possible other than as being a yet another parser limitation...

something related
http://news.povray.org/6lpkut0vdh0h6gljr7u2v4mip6olddkmel%404ax.com

ABX

Post a reply to this message

In article <3c9ef692@news.povray.org> , "Thorsten Froehlich" <tho### [at] trfde>
wrote:

> Actually, the following at least seems to work.  Of course, I have not checked
> if it doesn't corrupt any internal data:
>
>     #declare foo = array[40];
>
>     #declare foo[1] = array[10];
>     #declare foo[2] = array[5];
>
>     #declare foo[1][5] = 5.0;
>
> As far as I can tell this is, together with the ability to undef arrays
> sufficient to build linked structures...

For example:

#declare treeroot = array[3];

#declare rd = seed(1);

#macro randfilltree(node, i)
 #declare node[2] = array[1];
 #declare node[2][0] = rand(rd) * 1000 + 10;
 #if(i > 0)
  #if(rand(rd) > 0.1)
   #declare node[0] = array[3];
   randfilltree(node[0], i - 1)
  #end
  #if(rand(rd) > 0.1)
   #declare node[1] = array[3];
   randfilltree(node[1], i - 1)
  #end
 #end
#end

#macro dumptree(node)
 #debug " ("
 #debug str(node[2][0], 0, 0)
 #if(defined(node[0]))
  dumptree(node[0])
 #end
 #if(defined(node[1]))
  dumptree(node[1])
 #end
 #debug ")"
#end

#macro findmaxtree(node)
 #if(defined(node[0]) & defined(node[1]))
  max(node[2][0], findmaxtree(node[0]), findmaxtree(node[1]))
 #else
  #if(defined(node[0]))
   max(node[2][0], findmaxtree(node[0]))
  #else
   #if(defined(node[1]))
    max(node[2][0], findmaxtree(node[1]))
   #else
    0
   #end
  #end
 #end
#end

randfilltree(treeroot, 6)

#debug str(findmaxtree(treeroot), 0, 0)

dumptree(treeroot)

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <22vt9u8jvqkto0feosejmc6chmierd8lqm@4ax.com> , W„odzimierz ABX 
Skiba <abx### [at] babilonorg>  wrote:

>> Actually, this implies it isn't possible to make an array (of arbitrary size,
>> of course) an element of another array, or is this possible?  I have to admit
>> I never tried, but from the code I cannot really see a reason why it
>> shouldn't be possible other than as being a yet another parser limitation...
>
> something related
> <http://news.povray.org/6lpkut0vdh0h6gljr7u2v4mip6olddkmel%404ax.com>

Yes, exactly!  I was sure it couldn't be a new idea, but somehow few people
have discovered everything possible with arrays yet.


BTW, when building trees recursively there is always the macro recursion
limit, but trees with a height of 98 are either very big or not well balanced
anyway...

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

On Mon, 25 Mar 2002 11:52:53 +0100, "Thorsten Froehlich" <tho### [at] trfde>
wrote:
> BTW, when building trees recursively there is always the macro recursion
> limit, but trees with a height of 98 are either very big or not well balanced
> anyway...

But even then there is a workaround - iteration instead of recursion with
stack placed in another array. Operations on stack can be realised via
Resize_Array macro. This method works fine in my recent implementation in
IC_Text addition for iso_csg library.

ABX

Post a reply to this message

In article <0k2u9uso8jitmnmjc9v6dusa75e6f9v5hr@4ax.com> , W„odzimierz ABX 
Skiba <abx### [at] babilonorg>  wrote:

> But even then there is a workaround - iteration instead of recursion with
> stack placed in another array. Operations on stack can be realised via
> Resize_Array macro. This method works fine in my recent implementation in
> IC_Text addition for iso_csg library.

Yes, but I am not sure it is possible to access an array with an arbitrary
number of dimensions this way.  Take a look at the example macros I posted.
They all depend on passing of array elements that are arrays...

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

On Mon, 25 Mar 2002 10:45:41 +0100, Thorsten Froehlich wrote:
> In article <slr### [at] fwicom> , Ron Parker 
><ron### [at] povrayorg>  wrote:
> 
>> It wouldn't be any slower than a regular binary tree, but it would have a
>> limit on the maximum depth, it would take up more storage than absolutely
>> necessary, and it couldn't be balanced.
> 
> Actually, this implies it isn't possible to make an array (of arbitrary size,
> of course) an element of another array, or is this possible?  I have to admit

I didn't mean to imply that.  What I was saying was that using an array to
represent the tree directly using the scheme I mentioned limits the depth
to a maximum, unless you want to spend lots of time enlarging the array.

However, I think perhaps we could add a few lines to Parse_Array_Declare to
allow syntax like this to enlarge an array more quickly:

#declare A=array[5] {1, 2, 3, 4, 5}
#declare B=array[10] A

or maybe something a little more attractive...

-- 
plane{-z,-3normal{crackle scale.2#local a=5;#while(a)warp{repeat x flip x}rotate
z*60#local a=a-1;#end translate-9*x}pigment{rgb 1}}light_source{-9red 1rotate 60
*z}light_source{-9rgb y rotate-z*60}light_source{9-z*18rgb z}text{ttf"arial.ttf"
"RP".01,0translate-<.6,.4,.02>pigment{bozo}}light_source{-z*3rgb-.2}//Ron Parker

Post a reply to this message

On 25 Mar 2002 08:28:30 -0500, Ron Parker <ron### [at] povrayorg> wrote:
> However, I think perhaps we could add a few lines to Parse_Array_Declare to
> allow syntax like this to enlarge an array more quickly:

That's not fair for other feature requests ;-)

( there are lines

  //#macro Insert_In_Array(Item, DestArray, Index)
  //#macro Insert_Array_In_Array(ItemArray, DestArray, Index)
  //#macro Append_To_Array(Item, DestArray, Index)
  //#macro Append_Array_To_Array(ItemArray, DestArray, Index)

in arrays.inc I'm working on)

ABX

Post a reply to this message

On Mon, 25 Mar 2002 14:34:31 +0100, W³odzimierz ABX Skiba wrote:
> On 25 Mar 2002 08:28:30 -0500, Ron Parker <ron### [at] povrayorg> wrote:
>> However, I think perhaps we could add a few lines to Parse_Array_Declare to
>> allow syntax like this to enlarge an array more quickly:
> 
> That's not fair for other feature requests ;-)

Don't worry; it's not likely to happen anyway.  I haven't even had time 
lately to work on the bugs I've agreed to take on.

-- 
#macro R(L P)sphere{L F}cylinder{L P F}#end#macro P(V)merge{R(z+a z)R(-z a-z)R(a
-z-z-z a+z)torus{1F clipped_by{plane{a 0}}}translate V}#end#macro Z(a F T)merge{
P(z+a)P(z-a)R(-z-z-x a)pigment{rgbf 1}hollow interior{media{emission 3-T}}}#end 
Z(-x-x.2x)camera{location z*-10rotate x*90normal{bumps.02scale.05}}

Post a reply to this message

W³odzimierz ABX Skiba <abx### [at] babilonorg> wrote:
> Operations on stack can be realised via
> Resize_Array macro.

  The problem with using Resize_Array() is that it defies the whole purpose
of using binary trees. The main reason of using trees is that adding,
removing and searching values are all O(log n) operations, which makes it
awesomely fast.
  However, if you have to recurr to Resize_Array(), you are making it O(n),
which effectively destroys its speed benefits.

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

Ron Parker <ron### [at] povrayorg> wrote:
> #declare A=array[5] {1, 2, 3, 4, 5}
> #declare B=array[10] A

  That would be a really nice feature because resizing an array internally
is probably about 100 to 1000 times faster than doing it with SDL.

  Another possibility is just adding a function: resize_array(A, 10)
(I think it might be better this way.)

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message