I've worked out a graph positioning algorithm. We start with an approximation like the current output, then modify the x positions so that the x for every node corresponds to the position of that terminal in the left-to-right reading of the original expression. Then we set the Y positions of all terminals to be on the bottom row. Finally we adjust the Y positions of intermediate operator nodes so that they lie on a direct line from the parent to any eventual left children. I think this produces a sufficiently attractive layout and should be possible with the current data structure.

(By the way, why did you duplicate the various arrays and then indirect them so they're no longer indexed by the plain node number? There's clearly a reason you did that but I can't work out why…)

G

gtoal wrote:

(By the way, why did you duplicate the various arrays and then indirect them so they're no longer indexed by the plain node number? There's clearly a reason you did that but I can't work out why…)

Which arrays are you referring to? Are you talking about the ones that replaced the clone attributes?

Individuality wrote:

gtoal wrote:

(By the way, why did you duplicate the various arrays and then indirect them so they're no longer indexed by the plain node number? There's clearly a reason you did that but I can't work out why…)

Which arrays are you referring to? Are you talking about the ones that replaced the clone attributes?

yes, node xs == nx and node ys == ny, also nodeparents == p (parents), nodetext, nodetypes == o (operator), v (value)

- I think there's duplication but they're not quite identical - where your arrays are indexed by ‘nodei’, to find the same item in my arrays you have to index by ‘item nodei of nodenumbers’ …

what was the reason for renumbering and copying the arrays? If it was just because it wasn't obvious what my data structures were due to the overly short names (thank my friend Rainer for that ;-) ) then we can simplify the drawing code by reverting to the original arrays, but if there was an algorithmic reason for it…?

gtoal wrote:

yes, node xs == nx and node ys == ny, also nodeparents == p (parents), nodetext, nodetypes == o (operator), v (value)

- I think there's duplication but they're not quite identical - where your arrays are indexed by ‘nodei’, to find the same item in my arrays you have to index by ‘item nodei of nodenumbers’ …

what was the reason for renumbering and copying the arrays? If it was just because it wasn't obvious what my data structures were due to the overly short names (thank my friend Rainer for that ;-) ) then we can simplify the drawing code by reverting to the original arrays, but if there was an algorithmic reason for it…?

Yes, it was just ignorance. At the moment, I simply copied each local variable used for clones, to translate them to a list representation. Also, from the code, node X seems to be different from nx, and influences it.

Why did you create the local variables for the clones if they could retrieved from the list with the node's number?

EDIT: Now, I'm studying your code to understand every piece of data.

Individuality wrote:

Yes, it was just ignorance. At the moment, I simply copied each local variable used for clones, to translate them to a list representation. Also, from the code, node X seems to be different from nx, and influences it.

right - nx was the index for the x position, to get a pixel position it has to be scaled. I would have done the same with y except I had no plans for tweaaking the y coordinate at the time so I (inconsistently) put the pixel y in there instead of the y level.

Individuality wrote:

Why did you create the local variables for the clones if they could retrieved from the list with the node's number?

If I remember right (and honestly at my age remembering what I wrote yesterday is sometimes a trial ;-) ) it was that the clone loaded all its parameters once then sat in a display loop using only the local copies for speed. (Then the display loop disappeared when it turned into a broadcast acted on by all clones). It could probably be simplified too, now we have something that works.

Individuality wrote:

EDIT: Now, I'm studying your code to understand every piece of data.

o == operator string (eg “+”) or a type tag, ie ‘num’, or ‘str’. Since I merged two pieces of code, its unfortunate that numbers are flagged differently in the expression parser where they are codes as ‘0’ and in my original display code where they were tagged as ‘num’. I was in the process of changing over from one convention to the other but the code is currently a mixture of both.

v = value. its the integer for an integer terminal. In the copy in my area I also got the ‘calculate’ procedure to write back the value of an operator node into that field, for display if wanted (not yet used)

l - left (or only) child

r - right child, or 0 for unary operations (in this case, factorial)

p - was filled in during my display tree walk, pointing back to the parent of an operand. for display purposes only, not used in the calculation or parsing

node - should be the index of the root node after parsing. Note that the root node is likely to be the last node created, not the first node.

node, and arrays o, v, l & r should be all that's needed by the display code. The rest of the variables are either from my first attempt at display or from the parser. Hopefully I didn't make too many of those shared globals when they didn't have to be.

Left and right parents? Did you mean children?

How do I get a leaf/terminal node's corresponding token/lexeme?

Individuality wrote:

Left and right parents? Did you mean children?

How do I get a leaf/terminal node's corresponding token/lexeme?

Oops :-)

If it is an operator, it's in ‘o’. If o contains ‘num’ (or 0) then it is an integer and the value is in ‘v’.

Take my current copy which I've changed since I copied your code back. It displays the node values correctly. (And fixes a minor drawing bug with pen width)

gtoal wrote:

Individuality wrote:

Left and right parents? Did you mean children?

How do I get a leaf/terminal node's corresponding token/lexeme?

Oops :-)

If it is an operator, it's in ‘o’. If o contains ‘num’ (or 0) then it is an integer and the value is in ‘v’.

Take my current copy which I've changed since I copied your code back. It displays the node values correctly. (And fixes a minor drawing bug with pen width)

Thanks. I saw that, but the tokens don't appear to be in order. I'm trying to space the x positions to resemble the equation. How do I get the node's index to the corresponding “text” item?

Individuality wrote:

Thanks. I saw that, but the tokens don't appear to be in order. I'm trying to space the x positions to resemble the equation. How do I get the node's index to the corresponding “text” item?

I'm not quite sure what you're asking for, but if you want to assign a left to right ordering for the tokens, perhaps you could do it on the fly as you do the pre-order traverse of the tree. Assign sequential indexes recursively to the left branch, assign an index to the operator being examined, then assign recursively to the right branch.

gtoal wrote:

Individuality wrote:

Thanks. I saw that, but the tokens don't appear to be in order. I'm trying to space the x positions to resemble the equation. How do I get the node's index to the corresponding “text” item?

I'm not quite sure what you're asking for, but if you want to assign a left to right ordering for the tokens, perhaps you could do it on the fly as you do the pre-order traverse of the tree. Assign sequential indexes recursively to the left branch, assign an index to the operator being examined, then assign recursively to the right branch.

Thanks! I'll think about how to implement that. I also thought about having a pointer to the original token in “text” when adding values to ‘o’ or ‘v;’ is this approach wise? I'm still looking over the “newnode” block, so I may have misunderstood something.

Individuality wrote:

Thanks! I'll think about how to implement that. I also thought about having a pointer to the original token in “text” when adding values to ‘o’ or ‘v;’ is this approach wise? I'm still looking over the “newnode” block, so I may have misunderstood something.

Sure, I've done that in proper compilers. Often useful for reporting syntax errors.

Note the last three node creation blocks haven't been used yet. It's all done in ‘newnode’.

As I mentioned I copied the parser from a friend's C code, so it does some things I wouldn't normally do - I would normally have a flat array for all children rather than separate arrays for left and right children - this would make it easier to support other constructs such as if/then/else with 3 children, or (as we have here) factorial with only 1 child.

I uploaded the latest version of your project and updated the node positioning to match the original equation. Now, I need to do the y-positions.

EDIT: Noooo, somehow my changes weren't saved!
EDIT 2: I uploaded the new version. It's good now.

Individuality wrote:

I uploaded the latest version of your project and updated the node positioning to match the original equation. Now, I need to do the y-positions.

Woo! That's nice!

Let's stop there for now and look at it again when I get back from vacation. Comments and suggestions from the peanut gallery welcome while we're gone…

G

Okay. So, we both won't be active for a few weeks. I'll think of more design ideas.

Chibi-Matoran wrote:

Okay. So, we both won't be active for a few weeks. I'll think of more design ideas.

Don't let me stop you if you're rarin' to go! However I won't be around to help - no internet at sea! (I leave in a week but I'll be fairly busy preparing until then)

Just a heads-up on where I expect to take my side of the code: I'll want to generalise expressions more (a child array rather than left/right child special cases), add assignments to variables, and procedure calls, then at some point the ability to define your own functions (a little akin to your 1-line challenge) and eventually I want to add a proper parser for language constructs and create a programming language :-)

I'm also thinking of a scrolling text window which contains generated code for a pseudo-machine.

G

Noooo!!! Now, I have a programming language rival!!!1!!

gtoal wrote:

(a little akin to your 1-line challenge)

??? I didn't make the one-line challenge, and what does it have to do with implementing functions? What do you mean by that?

Chibi-Matoran wrote:

Noooo!!! Now, I have a programming language rival!!!1!!

Or collaborator :-)

Chibi-Matoran wrote:

gtoal wrote:

(a little akin to your 1-line challenge)

??? I didn't make the one-line challenge, and what does it have to do with implementing functions? What do you mean by that?

I told you old-guy memory is depressingly bad at times. I think I confused Minion with Matoran. Anyway, what I meant was something like

define myfun(x,y)=sin(x)+cos(y).

I.e. a 1-line function definition, as the first step towards something more complex.

I fixed the known bug - factorials now display OK. Maybe not pretty but it doesn't cause an infinite loop like it did before (recursing on displaying node 0)

Bump! I've realized that the tokens that I am using to space the nodes are in fact the expression's characters, stripped of whitespace. Therefore, the spacing breaks for numbers with more than one digit. Luckily, I thought up another way to determine the spacing:

Pseudocode: