Binary Tree Traversal in Spin

tmaynard · 2010-04-13 00:23

Okay, here's the deal: my brother has this idea for a Morse Code Keyer (details will be undisclosed

). He's an "idea guy" (a project manager) and I'm an "in the trenches guy" (developer -- both retired), so I'm looking at realizing his idea. The project as I visualize it requires a binary tree traversal ... or, more simply, a binary tree "hopping around."

As each Morse character element (dot or dash) is keyed in the program would move from node to node in the tree. The existence of a node is proof of a valid character (or character-under-construction, or even sequence of characters, for Q-Codes, etc.).

I'm a newcomer to the Propeller (but did time in the SX28 and PIC trenches ... along with plenty of assembler on bigger hardware). I don't see anything in the Spin manual about linked lists or binary trees. How would this be done in Spin? Or will I need to drop into PASM to traverse the tree?

Oh, and the ancillary question is: how would I build the (static) data tree in memory? It's not huge, but it will contain the letters, numbers, and an assortment of other, specialized characters -- 50 nodes? 60?

Here's a Wikipedia page that illustrates the static data tree:
en.wikipedia.org/wiki/File:Morse_code_tree3.png

That's basically the structure I need in memory (extended somewhat) ... along with the means to move around within it. Any hints/tips for a newbie?

TIA,
Tom.

Phil Pilgrim (PhiPi) · 2010-04-13 00:45

You've really got three choices at each node: dot, dash, and space. Of course, you could make every node a leaf containing the character read so far, but with branches to follow in case it continues from there.

-Phil

Mike Green · 2010-04-13 01:03

It would be best to use several parallel arrays for your tree with the subscript as the pointer. One byte array would point to the child node for dot. One byte array would point to the child node for dash. A 3rd byte array would contain the character if that's the end of the code (space) or a zero if there's no valid character at that point. The root of the tree would be at subscript zero.

You'd need about 70 bytes for each array for a total of around 210 bytes for the whole tree.

tmaynard · 2010-04-13 01:45

Phil Pilgrim (PhiPi) said...
You've really got three choices at each node: dot, dash, and space.

I don't expect anyone to know the intricacies of Morse ... but spaces are purely a timing thing. The base of Morse is the dot-timing, the inter-element spacing is equal to one dot-time, a dash is equal to three dot-times, and the inter-character timing is also three dot-times.

This is rather abstruse (but defined quite well on Wikipedia), so during character construction the inter-element timing is simply single dot-lengths. So at each node I only have dots or dashes and dot-length timers running.

I will "open the kimono" enough to reveal that my brother's idea is to implement a keyer that will only send "PERFECT" (capitalization his) code ... that is, no mal-formed characters will be sent.

Mike Green said...
It would be best to use several parallel arrays for your tree with the subscript as the pointer.

I'm going to have to sit and scratch my head a bit to get this ready to go ... but I think I see the general direction. I'll have to map this approach onto the actual binary tree to see how to make it work.

Thanks to one and all for your input. I may be pushing the Spin envelope a bit here ... and that's a fine thing.

Tom.

CannibalRobotics · 2010-04-13 01:53

For reception, a 'space' is just punctuation for 'new data' so you really have only dots and dashes - or zeros and ones. If a space is a terminator then it's also the bit count. Arrange data array in bit count then binary order of the code. Your decision tree jumps to the 'remaining' charactors after each new data your tree.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Signature space for rent!
Send $1 to CannibalRobotics.com.

Phil Pilgrim (PhiPi) · 2010-04-13 02:25

By "space" I meant inter-character, not inter-element. For example, there are three things that can follow the first dot:

space: E
dot: I (or S, H, U, 2, 3, 4, 5, etc.)
dash: A (or R, L, 1, etc.)

The inter-character space is an element of the code, not "merely" punctuation, since the symbol length is variable. This means that Morse is a trinary code, not a binary code.

-Phil

cimplex · 2010-04-13 03:11

I'm a bit confused here...is this device for sending ascii characters as morse code, OR receiving morse code and outputting the equivalent ascii character??

For the sending an ascii char as morse option, I made a morse generator as one of my learning projects on the prop. The easiest way I found was to make a byte (or long word) table, with 0 representing a dot, and 1 for dash for each character of the alphabet. Since all the text will be single case, plus any punctuation characters you want, the table will be relatively short. Arrange the table so that an ascii character will index into the correct morse character sequence. Then you bit shift through the morse char and use timing loops for dot, dash and space. I used the same technique to create a RTTY transmitter, with the 1 or 0 specifying the audio shift frequency.

Going from morse to a character, you might consider receiving the whole character into a byte (long), using intersymbol timing to frame it as mentioned in the post above, then doing a pattern match against the list of characters. Same idea as transmit, just in reverse.

-Joe

Post Edited (cimplex) : 4/13/2010 3:39:25 AM GMT

tmaynard · 2010-04-13 04:47

cimplex said...
I'm a bit confused here...is this device for sending ascii characters as morse code, OR receiving morse code and outputting the equivalent ascii character??

My apologies -- I never meant to bring alien amateur radio terms to bear -- but I guess it's the nature of the beast.

A "keyer" is an automated device for sending Morse Code characters, usually using a set of "paddles" (dual, single-contact, normally-open switches). One side sends dots, the other side sends dashes. The behavior when both sides are closed is governed by yet another algorithm, although "Iambic-B" is probably the most common (alternating elements).

Phil Pilgrim (PhiPi) said...
By "space" I meant inter-character, not inter-element. For example, there are three things that can follow the first dot

Of course, you're absolutely correct ... but I confess it's the first time I've heard the "white space" of Morse referred to as an element of the code -- either inter-element or inter-character.

But, how to represent these data in memory, and how to do it in Spin? I don't have problems with C and Struct(s), and with the general linked list-style implementation ... but Spin? I'm left in the lurch. Is PASM my only option?

t++

potatohead · 2010-04-13 05:12

I'm assuming the keyer would only output a valid character. What happens when somebody starts down the road to the wrong character? Will they just get the closest one? Is feedback given to the user, or will no character be keyed at the xmitter, until a valid one? No need to respond, if that let's the secret sauce out [noparse]:)[/noparse] Just curious.

Seems to me, for sending code at least, SPIN would be plenty fast enough. You just need to author your core methods and arrays, instead of defining structures. Once that's done, the higher level program logic wouldn't be a whole lot different than you are used to.

The reason for my query above is the predictive potential here. If a tree is being used to constrain the output to "perfect" code, it seems to me extending that to simple words and phrases would be on the table, meaning quite a bit more traversing...

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness!
8x8 color 80 Column NTSC Text Object
Safety Tip: Life is as good as YOU think it is!

Mike Green · 2010-04-13 05:12

There are lots of ways to represent list structures including the one I outlined earlier. All of them are doable in Spin and in PASM and in various ways. What kind of list structure do you want? Do you want a classic LISP pointer pair? Do you want a doubly linked list? What I proposed was application specific. After all, why use more than one byte for a pointer when you've got fewer than 256 list items? In Spin, there's no great advantage to using 16 bit addresses over subscripts since the subscripting operations are interpreter primitives as are the pointer dereferencing operations.

tmaynard · 2010-04-13 14:16

potatohead said...
I'm assuming the keyer would only output a valid character. What happens when somebody starts down the road to the wrong character? Will they just get the closest one? Is feedback given to the user, or will no character be keyed at the xmitter, until a valid one? No need to respond, if that let's the secret sauce out [noparse]:)[/noparse] Just curious.

No, the secret's out: the keyer will only allow correctly-formed characters (and perhaps more -- but not all the way to words).

The user sends (say) a dit. The program leaves the root node and travels down the dit-path landing on "E" -- that's valid, so the keyer transmits the dit, and sets the inter-element timer. The user sends a dah, the program moves down the dah-path landing on "A" -- also valid. The keyer sends the dah, and resets the inter-element timer. And so on, until at some point the user sends either a dit or a dah, the program moves down the corresponding path and lands on a <NIL> -- invalid. Nothing goes out on the air, the user is bonged that his sending has been "corrected," the inter-element ... and inter-character ... timers are reset and the program returns to the root node.

That's the whole secret (rather over simplified). In my brother's words, it's the PERFECT Keyer (his capitalization).

Mike Green said...
There are lots of ways to represent list structures including the one I outlined earlier. All of them are doable in Spin and in PASM and in various ways. What kind of list structure do you want? Do you want a classic LISP pointer pair? Do you want a doubly linked list? What I proposed was application specific. After all, why use more than one byte for a pointer when you've got fewer than 256 list items?

Way back in my original post I gave a pointer to the Morse Code binary tree diagram on Wikipedia. That's exactly the kind of structure that I want to implement (or emulate) -- with a few extensions so that the tree includes amateur radio prosigns.

In C a node would look something like this:

struct tree_el {
    int val; 
    struct tree_el * right, * left;
};

Where "val" is the Morse Code character of the moment, and the "right" and "left" pointers are dit and dah path marks. Of course, as you say, it doesn't have to be this way ... but that's what came to me and it's kind of lodged itself in my brain.

If you do look at the Wikipedia tree, you'll note that there are some problematic characters that appear in the table
below an empty node. That's unfortunate, but work-around-able.

potatohead · 2010-04-13 14:35

Heh... Include a wrist strap, sufficient to deliver a mild "tingle", and I think it would be absolutely golden. I'm completely serious about that, BTW. It's quick, effective, and resonates by reinforcing natural inhibitions and reactions to reinforce correct form.

...or include a mechanical rest, that vibrates, or delivers a "thump" on bad character form input. [noparse]:)[/noparse]

Anyway, if it's just about reading what the user does, and sending code, SPIN is gonna be quick enough.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness!
8x8 color 80 Column NTSC Text Object
Safety Tip: Life is as good as YOU think it is!

tmaynard · 2010-04-13 14:49

potatohead said...
Anyway, if it's just about reading what the user does, and sending code, SPIN is gonna be quick enough.

Right, I have no doubts about speed ... my question is about how to navigate that tree structure in a language (in my studies so far) that has no pointers or indexed addressing. And then there's the second question about how to get that static tree structure in memory in the first place?

Kye · 2010-04-13 14:54

So in spin there are no data types so the compilier does not feature support for structures.

But, you can always just manually handle the pointer math and dereferencing.

' Just to show how we logically will order our elements.
'
' long value <- The pointer must point to this element.
' long left
' long right
 
PUB getValue(ptr)
 
  return long[noparse][[/noparse]ptr][noparse][[/noparse]0]
 
PUB getleft(ptr)
 
  return long[noparse][[/noparse]ptr][noparse][[/noparse]1]
 
PUB getRight(ptr)
 
  return long[noparse][[/noparse]ptr][noparse][[/noparse]2]
 
PUB setValue(ptr, value)
 
  long[noparse][[/noparse]ptr][noparse][[/noparse]0] := value
 
PUB setleft(ptr, newptr)
 
  long[noparse][[/noparse]ptr][noparse][[/noparse]1] := newptr
 
PUB setRight(ptr, newptr)
 
  long[noparse][[/noparse]ptr][noparse][[/noparse]2] := newptr

Then just make sure to call the functions on a valid node and your good.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Nyamekye,

jazzed · 2010-04-13 15:05

Will your Binary Tree change or just represent a static graph for lookups ?
A simple list allocator can be used for new references if data is not deleted.
Dave Hien (and others) have created memory managers if you need dynamic data.

There is no C like data structure or object pointers in Spin, so you have to do it by hand.
You can use an array of words (or other type) in VAR sections for emulating a C struct
except that you can not mix data types there. DAT sections allow mixing data types.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
May the road rise to meet you; may the sun shine on your back.
May you create something useful, even if it's just a hack.

jazzed · 2010-04-13 16:01

Lots of help today [noparse]:)[/noparse]

Kye's wrappers will be helpful once you have a allocated references.
Since your tree is static, a simple list allocator will work.

' this untested code is the simple allocator idea.

' words would be better for size, but this would be compatible with Kye's mutator code
' bytes would fit the data better, but I'll leave that for Mike to demonstrate.
con

  HEAPSIZE = $100
  ELEMSIZE = 4 ' long elements
  
var

  long end
  long heap[noparse][[/noparse]HEAPSIZE]

pub init

  heap[noparse][[/noparse]0] := 0
  end := @heap
  
pub allocate(length) | newptr ' length in ELEMSIZE units

  newptr := end+length+ELEMSIZE
  newptr &= -ELEMSIZE ' make word or long aligned address
  result := end ' result is default return value
  end := newptr

Example traversing the tree iteratively in a BST ordered list.

pub find(data) ' return non-zero tree node pointer if found

  result := heap[noparse][[/noparse]0]
  repeat while result <> 0
    if data == getValue(result)
      return result
    if data > getValue(result)
      result := getRight(result)
    else
      result := getLeft(result)
  result := 0

If there are errors here, someone will surely point them out [noparse]:)[/noparse]

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
May the road rise to meet you; may the sun shine on your back.
May you create something useful, even if it's just a hack.

tmaynard · 2010-04-13 16:47

Kye said...
So in spin there are no data types so the compilier does not feature support for structures.

But, you can always just manually handle the pointer math and dereferencing.

That's definitely along the lines I'm considering. Thanks! I don't need any functions to modify the tree in any way -- except perhaps just to build it in the first place, but I can simply hard-code the structure and linkage since it's simple enough.

jazzed said...
Will your Binary Tree change or just represent a static graph for lookups ?
A simple list allocator can be used for new references if data is not deleted.
Dave Hien (and others) have created memory managers if you need dynamic data.

The tree is completely static -- no insertions or deletions -- it's being used to validate a data stream.

I knew I was overstating the requirements when I used "binary tree traversal" in the subject. I have no need to visit every node (as in the traditional tree traversal), I only need to test user input against a static tree, where a null node indicates bad input.

jazzed said...
Lots of help today [noparse]:)[/noparse]

Indeed! Maybe too much! I've got a half a dozen ideas to ponder now, starting with Mike Green's parallel array solution. When time permits I'll be "desk checking" that method ... and then moving on to the other, excellent suggestions. Once again, thanks to all for your help.

t++

Binary Tree Traversal in Spin

Comments