Essays/Tree Display

From J Wiki
Jump to: navigation, search

Tree Display

The verb tree produces a tree display from a 2-column table of the edges. The result is a list of boxed literal tables, one box for each tree in the forest specified by the edges.

BOXC=: 9!:6 ''    NB. box drawing characters
EW  =: {: BOXC    NB. east-west

tree=: 3 : 0
 assert. ($y) -: (#y),2
 y=. ":&.>^:(32 ~: 3!:0) y
 assert. ((2 = 3!:0&>) *. 1 >: #@$&>) y
 j=.  ~. , y
 t=. (<EW,' ') ,@<@,:@,&.> j           NB. GTs (generational trees)
 c=. |: j i. y
 while. +./ b=. ({.c)*.//.-.e.~/c do.
  i=. b#~.{.c                          NB. parents whose children are leaves
  j=. </./(({.c)e.i)#"1 c              NB. leaves grouped by parents
  assert. ~:;j                         NB. non-unique means not forest
  t=. a: (;j)}t i}~ (i{t) subtree&.> j{&.><t
  c=. (-.({.c)e.i)#"1 c                NB. prune edges to leaves
 end.
 assert. c -: i.2 0                    NB. non-empty means not a forest
 ([: ,.&.>/ extend&.>)&> t -. a:
)

subtree=: 4 : 0
 p=. EW={."1 s=. >{.t=. graft y
 (<(>{.x) root p),(<(connect p),.s),}.t
)

graft=: 3 : 0
 n=. (-~ >./) #&> y
 f=. i.@(,&0)@#&.>@{.&.> y
 ,&.>/ y ,&> n$&.>f
)

connect=: 3 : 0
 b=. (+./\ *. +./\.) y
 c=. (b+2*y){' ',9 3 3{BOXC  NB. │ NS ├ E
 c=. (0{BOXC) (b i. 1)}c     NB. ┌ NW
 c=. (6{BOXC) (b i: 1)}c     NB. └ SW
 j=. (b i. 1)+<.-:+/b
 EW&(j})^:(1=+/b) c j}~ ((0 3 6 9{BOXC)i.j{c){1 4 7 5{BOXC
)

root=: 4 : 0
 j=. k+<.-:1+(y i: 1)-k=. y i. 1
 (-j)|.(#y){.x,.,:' ',EW
)

extend=: 3 : '(+./\"1 (y=EW) *. *./\."1 y e.'' '',EW)}y,:EW'

Examples

   ] t1=: }. (p:^:_1 ,. ]) i.20
0  1
0  2
1  3
2  4
2  5
3  6
3  7
4  8
4  9
4 10
4 11
5 12
5 13
6 14
6 15
6 16
6 17
7 18
7 19
   tree t1
┌────────────────────────────┐
│                       ┌─ 14│
│                       ├─ 15│
│                 ┌─ 6 ─┼─ 16│
│                 │     └─ 17│
│     ┌─ 1 ─── 3 ─┤     ┌─ 18│
│     │           └─ 7 ─┴─ 19│
│     │           ┌─ 8       │
│─ 0 ─┤           ├─ 9       │
│     │     ┌─ 4 ─┼─ 10      │
│     │     │     └─ 11      │
│     └─ 2 ─┤     ┌─ 12      │
│           └─ 5 ─┴─ 13      │
└────────────────────────────┘
   tree t1,30+5{.t1
┌────────────────────────────┬──────────────────┐
│                       ┌─ 14│      ┌─ 31 ─── 33│
│                       ├─ 15│─ 30 ─┤      ┌─ 34│
│                 ┌─ 6 ─┼─ 16│      └─ 32 ─┴─ 35│
│                 │     └─ 17│                  │
│     ┌─ 1 ─── 3 ─┤     ┌─ 18│                  │
│     │           └─ 7 ─┴─ 19│                  │
│     │           ┌─ 8       │                  │
│─ 0 ─┤           ├─ 9       │                  │
│     │     ┌─ 4 ─┼─ 10      │                  │
│     │     │     └─ 11      │                  │
│     └─ 2 ─┤     ┌─ 12      │                  │
│           └─ 5 ─┴─ 13      │                  │
└────────────────────────────┴──────────────────┘

The nodes can have labels specified as strings. For example:

   a=: ;:'zero one two three four five six seven eight nine'
   a=: a ,;:'ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen'
   t2=: (?.~@# { ]) t1{a
   $ t2
19 2
   5{.t2
┌─────┬────────┐
│three│seven   │
├─────┼────────┤
│seven│nineteen│
├─────┼────────┤
│zero │two     │
├─────┼────────┤
│four │eight   │
├─────┼────────┤
│one  │three   │
└─────┴────────┘
   tree t2
┌─────────────────────────────────────────────────┐
│                          ┌─ eight               │
│                          ├─ eleven              │
│                ┌─ four ──┼─ nine                │
│                │         └─ ten                 │
│        ┌─ two ─┤         ┌─ twelve              │
│        │       └─ five ──┴─ thirteen            │
│        │                            ┌─ nineteen │
│─ zero ─┤                 ┌─ seven ──┴─ eighteen │
│        │                 │          ┌─ fifteen  │
│        └─ one ─── three ─┤          ├─ fourteen │
│                          └─ six ────┼─ sixteen  │
│                                     └─ seventeen│
└─────────────────────────────────────────────────┘

   ] t3=: _2 ]\ ;:'tree subtree tree extend subtree graft subtree root subtree connect'
┌───────┬───────┐
│tree   │subtree│
├───────┼───────┤
│tree   │extend │
├───────┼───────┤
│subtree│graft  │
├───────┼───────┤
│subtree│root   │
├───────┼───────┤
│subtree│connect│
└───────┴───────┘
   tree t3
┌──────────────────────────────┐
│                    ┌─ graft  │
│        ┌─ subtree ─┼─ root   │
│─ tree ─┤           └─ connect│
│        └─ extend             │
└──────────────────────────────┘

Program Logic

A generational tree is a list of boxed literal tables having the same number of rows, such that the nodes at the same depth are in the same box. For example, the GT for the tree t1 above is:

┌─────┬──────┬──────┬──────┬─────┐
│     │      │      │      │┌─ 14│
│     │      │      │      │├─ 15│
│     │      │      │┌─ 6 ─│┼─ 16│
│     │      │      ││     │└─ 17│
│     │┌─ 1 ─│── 3 ─│┤     │┌─ 18│
│     ││     │      │└─ 7 ─│┴─ 19│
│     ││     │      │┌─ 8  │     │
│─ 0 ─│┤     │      │├─ 9  │     │
│     ││     │┌─ 4 ─│┼─ 10 │     │
│     ││     ││     │└─ 11 │     │
│     │└─ 2 ─│┤     │┌─ 12 │     │
│     │      │└─ 5 ─│┴─ 13 │     │
└─────┴──────┴──────┴──────┴─────┘

The main verb tree maintains a GT for each node (in the local name t). Each iteration of main loop generates subtrees represented as GTs for those parents all of whose children are leaves, then all branches leading to leaves are pruned and the GTs for the leaves are purged. The iteration terminates when there are no such parents.

For the tree t1 above, the initial list of GTs is:

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬    ─┬──────┐
│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│     │┌────┐│
││─ 0│││─ 1│││─ 2│││─ 3│││─ 4│││─ 5│││─ 6│││─ 7││ ... ││─ 19││
│└───┘│└───┘│└───┘│└───┘│└───┘│└───┘│└───┘│└───┘│     │└────┘│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴    ─┴──────┘

After the next iteration, the resultant list of GTs is:

┌─────┬─────┬─────┬─────┬─────────────┬─────────────┬─────────────┬─────────────┬┬┬┬┬┬┬┬┬┬┬┬┐
│┌───┐│┌───┐│┌───┐│┌───┐│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│││││││││││││
││─ 0│││─ 1│││─ 2│││─ 3│││     │┌─ 8 │││     │┌─ 12│││     │┌─ 14│││     │┌─ 18││││││││││││││
│└───┘│└───┘│└───┘│└───┘││     │├─ 9 │││─ 5 ─│┴─ 13│││     │├─ 15│││─ 7 ─│┴─ 19││││││││││││││
│     │     │     │     ││─ 4 ─│┼─ 10││└─────┴─────┘││─ 6 ─│┼─ 16││└─────┴─────┘│││││││││││││
│     │     │     │     ││     │└─ 11││             ││     │└─ 17││             │││││││││││││
│     │     │     │     │└─────┴─────┘│             │└─────┴─────┘│             │││││││││││││
└─────┴─────┴─────┴─────┴─────────────┴─────────────┴─────────────┴─────────────┴┴┴┴┴┴┴┴┴┴┴┴┘

And after the next:

┌─────┬─────┬────────────────────┬────────────────────┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┐
│┌───┐│┌───┐│┌─────┬──────┬─────┐│┌─────┬──────┬─────┐│││││││││││││││││
││─ 0│││─ 1│││     │      │┌─ 8 │││     │      │┌─ 14││││││││││││││││││
│└───┘│└───┘││     │      │├─ 9 │││     │      │├─ 15││││││││││││││││││
│     │     ││     │┌─ 4 ─│┼─ 10│││     │┌─ 6 ─│┼─ 16││││││││││││││││││
│     │     ││     ││     │└─ 11│││     ││     │└─ 17││││││││││││││││││
│     │     ││─ 2 ─│┤     │┌─ 12│││─ 3 ─│┤     │┌─ 18││││││││││││││││││
│     │     ││     │└─ 5 ─│┴─ 13│││     │└─ 7 ─│┴─ 19││││││││││││││││││
│     │     │└─────┴──────┴─────┘│└─────┴──────┴─────┘│││││││││││││││││
└─────┴─────┴────────────────────┴────────────────────┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┘

subtree

subtree does the "heavy-lifting" of the main loop. The left argument is the label for a parent; the right argument is a list of boxed GTs for its children. The result is a single GT for that parent. For example:

   x
┌───┐
│─ 2│
└───┘
   y
┌─────────────┬─────────────┐
│┌─────┬─────┐│┌─────┬─────┐│
││     │┌─ 8 │││     │┌─ 12││
││     │├─ 9 │││─ 5 ─│┴─ 13││
││─ 4 ─│┼─ 10││└─────┴─────┘│
││     │└─ 11││             │
│└─────┴─────┘│             │
└─────────────┴─────────────┘
   x subtree y
┌─────┬──────┬─────┐
│     │      │┌─ 8 │
│     │      │├─ 9 │
│     │┌─ 4 ─│┼─ 10│
│     ││     │└─ 11│
│─ 2 ─│┤     │┌─ 12│
│     │└─ 5 ─│┴─ 13│
└─────┴──────┴─────┘

graft

graft takes a list of boxed GTs for the children of a node and combines them into a single GT. For example:

   y
┌───────────────────────────┬────────────────────┐
│┌─────┬──────┬──────┬─────┐│┌─────┬──────┬─────┐│
││     │      │      │┌─ 14│││     │      │┌─ 8 ││
││     │      │      │├─ 15│││     │      │├─ 9 ││
││     │      │┌─ 6 ─│┼─ 16│││     │┌─ 4 ─│┼─ 10││
││     │      ││     │└─ 17│││     ││     │└─ 11││
││─ 1 ─│── 3 ─│┤     │┌─ 18│││─ 2 ─│┤     │┌─ 12││
││     │      │└─ 7 ─│┴─ 19│││     │└─ 5 ─│┴─ 13││
│└─────┴──────┴──────┴─────┘│└─────┴──────┴─────┘│
└───────────────────────────┴────────────────────┘
   graft y
┌─────┬──────┬──────┬─────┐
│     │      │      │┌─ 14│
│     │      │      │├─ 15│
│     │      │┌─ 6 ─│┼─ 16│
│     │      ││     │└─ 17│
│─ 1 ─│── 3 ─│┤     │┌─ 18│
│     │      │└─ 7 ─│┴─ 19│
│     │      │┌─ 8  │     │
│     │      │├─ 9  │     │
│     │┌─ 4 ─│┼─ 10 │     │
│     ││     │└─ 11 │     │
│─ 2 ─│┤     │┌─ 12 │     │
│     │└─ 5 ─│┴─ 13 │     │
└─────┴──────┴──────┴─────┘

connect

connect applies to a boolean list with 1s indicating where subtree roots are located. The result is is a literal list with the following properties:

  • vertical lines spanning the first and the last 1s, with "corners" at those first and last 1s
  • tick marks on the right for subtree roots
  • a single tick mark on the left for the root located midway between the first and the last 1

This result is best viewed as a column.

Examples:

   connect 1 1 1
┌┼└
   ,. connect 1 1 1
┌
┼
└
   ,. connect 0 0 1 0 1 0 0 1 1


┌
│
├
┤
│
├
└
   ,. connect 1
─

root

The dyad root applies to a one-row literal matrix left argument and to a boolean list with 1s indicating where subtree roots are located (same as the argument for connect). It produces a literal matrix suitable for use as the root (the leftmost matrix) of a GT. For example:

   ] t=: (,:EW,' abc') root 0 0 1 0 1 0



─ abc ─


   $ t
6 7

extend

extend extends the trailing horizontal line (EW) characters in a literal table to the right edge of the table. For example:

   t
┌────────┬────────┬──────────┬───────────┬────────────┐
│        │        │          │┌─ eight   │            │
│        │        │          │├─ eleven  │            │
│        │        │┌─ four ─ │┼─ nine    │            │
│        │        ││         │└─ ten     │            │
│        │┌─ two ─│┤         │┌─ twelve  │            │
│        ││       │└─ five ─ │┴─ thirteen│            │
│        ││       │          │           │┌─ nineteen │
│─ zero ─│┤       │          │┌─ seven ─ │┴─ eighteen │
│        ││       │          ││          │┌─ fifteen  │
│        │└─ one ─│── three ─│┤          │├─ fourteen │
│        │        │          │└─ six ─   │┼─ sixteen  │
│        │        │          │           │└─ seventeen│
└────────┴────────┴──────────┴───────────┴────────────┘
   extend&.> t
┌────────┬────────┬──────────┬───────────┬────────────┐
│        │        │          │┌─ eight   │            │
│        │        │          │├─ eleven  │            │
│        │        │┌─ four ──│┼─ nine    │            │
│        │        ││         │└─ ten     │            │
│        │┌─ two ─│┤         │┌─ twelve  │            │
│        ││       │└─ five ──│┴─ thirteen│            │
│        ││       │          │           │┌─ nineteen │
│─ zero ─│┤       │          │┌─ seven ──│┴─ eighteen │
│        ││       │          ││          │┌─ fifteen  │
│        │└─ one ─│── three ─│┤          │├─ fourteen │
│        │        │          │└─ six ────│┼─ sixteen  │
│        │        │          │           │└─ seventeen│
└────────┴────────┴──────────┴───────────┴────────────┘



Contributed by Roger Hui. The program logic is similar to that in a post to the comp.lang.apl newsgroup on 1991-09-28.