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