Tree Representation

[Roger Hui]

NB. Model of tree representation (5!:4).

ar =. 5!:1
type =. 3!:0
boxed =. 32&=@type
mt =. 0&e.@$
oarg =. >@(1&{)
shr =. |.!.''
shl =. 1&(|.!.'')
boxc =. 9!:6 ''
dash =. 10{boxc

sh =. (*/@}: , {:)@(1&,)@$ $ ,
rows =. */\.@}:@$
bl =. }.@(,&0)@(+/)@(0&=)@(|/ i.@{.@(,&1))
mask =. 1&,. #&, ,.&0@>:@i.@#
mat =. mask@bl@rows { ' '&,@sh

extent =. (+./\ *. +./\.) @ (' '&~:) @: ({."1)
limb1 =. 1&|.@$ 1&~: }. (10 6 0{boxc)&,@($&(9{boxc))
limb =. -@(i.&1)@[ |. #@[ {. limb1@]
pfx =. (limb +/)@extent ,. ]
pad =. [ {. ] ,. dash&=@({:"1)@] { ' '&,:@($&dash)@(-&{: $)
take =. pad`({.&(,.' ')@[) @. (mt@])
rc =. #@>@{."1 ; >./@:({:@$@>)
kernt =. (0{boxc)&=@shl@[ *. ' '&~:@]
kernb =. (6{boxc)&=@] *. ' '&~:@shl@[
kern =. (<0 0)&{&>"2 (kernt +./"1@:+. kernb) (<_1 0)&{&>"2
gap =. ,&.>"_1 {&((0 1$' ');1 1$' ')@kern
graft =. (pfx&.>@{. 0} ]) @ (,&.>/) @ gap @ ({@rc take&.> ])

lab =. ,: @ (2&|.) @ ((' ',dash,dash,' ')&,)
label =. lab`((,.dash)&[) @. (e.&'0123456789'@{.)
center =. ((i.&1) -@+ <.@-:@(+/))@] |. #@] {. [
root =. label@[ center extent@>@{.@]

leaf =. ,@<@(((,:dash,' ')&[ center $&1@#) ,. ])@mat@":

trx =. >@{. (root ; ]) graft@:(tr@>)@oarg
trgl =. >@{. (root ; ]) graft@:(trx@>@{. , tr @>@}.)@oarg
trgr =. >@{. (root ; ]) graft@:(tr @>@{. , trx@>@}.)@oarg
trg =. trgr`trgl`trx @. (i.&(<,'`')@oarg)
trtil =. trx`(leaf@(,&' ')@oarg@>@{.@oarg) @. ((<,'0')&=@{.@>@{.@oarg)
trcase =. (leaf@oarg)`trgl`trgl`trg`trtil`trx @. ((;:'0@.`:4~')&i.@{.)
tr =. leaf`trcase @. boxed

rep =. ([.(`({"0 1)))`(].(,&)("0))\
west =. (e.&(9{boxc) *. shr"1@(e.&dash)) rep (5{boxc)
cross =. (e.&(5{boxc) *. shl"1@(e.&dash)) rep (4{boxc)
east =. (e.&(9{boxc) *. shl"1@(e.&dash)) rep (3{boxc)
north =. (e.&(6{boxc) *. shr"1@(e.&dash)) rep (7{boxc)
connect =. north @ east @ cross @ west

tree =. connect @ > @ (,.&.>/) @ (> (root ; ]) tr@>@ar)

________________________________________________________________


tree <'tree'
+- connect
+- @ -+- >
+- @ -+ +- <
| +- / --- @ ------+ +- ,.
| +- & -+- >
- tree -- @ -+ +- >
| | +- root
| +-----+- ;
+-----+ +- ]
| +- tr
| +- @ ------+- >
+- @ -+- ar

5!:4 is another in the "representation" series of verbs.
5!:1 atomic (gerundial)
5!:2 display
5!:3 string
5!:4 tree

5!:4 will be available in the next version (3.5) of J. The argument
to 5!:4 is a boxed named; the result is a literal table of the tree
representation of the named object.

The model is divided into groups of defns. Unless otherwise noted,
the defns are verbs.

The first group are utilities:
ar - atomic representation
type - internal "type"
boxed - 1 iff boxed
mt - 1 iff empty
oarg - open the second element of the list argument
shr - shift right
shl - shift left
boxc - (noun) box drawing characters
dash - (noun) the "dash" in the set of box drawing characters

"mat" is the main verb of the next group of definition. The argument
is a literal array; the result "looks like" the argument, but is a table.

The other defns manipulate arrays of a type that I call a "generational
tree": a list of boxed literal tables having the same number of rows,
such that nodes at the same depth are in the same box. For example,
the GT for "tree" is:

+--------+-----+------+------+-----------+------+-----+
| | | | |+- connect | | |
| | | |+- @ -|+- > | | |
| | |+- @ -|| | |+- < | |
| | || |+- / -|-- @ ------|| |+- ,.|
| | || | | |+- & -|+- > |
|- tree -|- @ -|| |+- > | | | |
| | || || |+- root | | |
| | || ||-----||- ; | | |
| | |+-----|| |+- ] | | |
| | | || | |+- tr | |
| | | || |+- @ ------|+- > | |
| | | |+- @ -|+- ar | | |
+--------+-----+------+------+-----------+------+-----+

"graft" is the main verb in the next group of defns. The argument
is a table whose rows are GTs for the nodes at the same depth.
The result is a GT.

"root" accepts a string left argument and a GT right argument.
The result is a literal matrix with the string centered relative
to the GT.

"leaf" computes a unitary (single-element) GT from its argument.

"tr" accepts an argument which is the opened atomic representation
of an object, and computes a GT therefrom. The verbs with the "tr"
prefix embody logic to effect "nice" displays for various special cases.
Thus, in "trcase", the items in the agenda are:
ID Agenda
---- ---------------------------------------------
0 leaf@oarg noun (leaf)
@. trgl the left subtree is a gerund
`: trgl the left subtree is a gerund
4 trg bonded (curried) conjunction
~ trtil possible instance of evoke

"rep" is a conjunction whose left argument is a proposition p and
whose right argument is a single literal c, deriving a verb such that
the phrase p rep c y replaces with c all the positions in y marked by
p y.

"tree" accepts a boxed name and computes the tree representation of
the named object. The appearance of the result is improved on systems
with better box drawing characters (such as the PC). "tree" is a model
of 5!:4, and is slower by a factor of about 30.

--------------------------------
Roger Hui, Iverson Software Inc., 33 Major Street, Toronto, Ontario M5S 2K9
(416) 925 6096; Fax: (416) 488 7559