DevonMcCormick's example
C: |__n0 | |_n00 | |_n01 | |__n1 |__n10 | |__n100 |__n11 | |__n110
| |__n111 | |__n112 |__n12
is expressed by ordinal fraction like this:
0 |__1 | |__11 | |__12 | |__2 |__21 | |__211 |__22
| |__221 | |__222 | |__223 |__23
This tree is represented by
'0 1 11 12 2 21 211 22 221 222 223 23'
or
'000 100 110 120 200 210 211 220 221 222 223 230'
Note
1. that ordinal fractions are one-origin-indexed unlike J-arrays that
are zero-origin-indexed
2. that ordinal fractions are left-justified unlike integers that are
right-justified
3. that ordinal fractions may be zeropadded to the right (23=230),
unlike integers that may be zeropadded to the left. (23=023)
4. that ordinal fractions also represents general arrays using zero as
a general wild-card character.
5. the ordering is alphabetic unlike Devon's which is breadth-first
for your information.
Bo.
Den 22:55 mandag den 8. september 2014 skrev 'Pascal Jasmin' via Programming
<programm...@jsoftware.com>:
>
>
>I think that is awesome, Thomas. For those who didn't load the code, its much
>easier to use than it looks as everything is a verb, and the whole thing is
>like a mini stack language, and each operation produces intuitive and visible
>results.
>
>
>
>
>----- Original Message -----
>From: Thomas Costigliola <tcost...@gmail.com>
>To: J Programming Forum <programm...@jsoftware.com>
>Cc:
>Sent: Monday, September 8, 2014 4:04 PM
>Subject: Re: [Jprogramming] Ragged Array Shapes are Trees
>
>Array representations and "pointer" representations of trees both have
>their uses. In the end it depends on what problem you are trying to solve.
>As Devon demonstrated, for his purpose, array representation was not a
>hindrance at all. But, as Dan mentions, trees are also used to implement
>abstract data structures with certain run-time properties where finding the
>children of a node or inserting / moving sub-trees in less than constant
>time is not acceptable. J already can do the "pointer" representation with
>boxed arrays but as stated by others previously, there are insufficient
>primitives for working with them conveniently without additional overhead.
>
>I have played around with code similar to Pascal's for working with trees.
>I felt, however, this type of stuff has limited usefulness in production
>code without help from the interpreter to optimize it. It's the same idea
>as a "zipper" data structure in other languages. Here is a bare bones
>implementation with lots of room for more bells and whistles if desired.
>
>x=. @ [
>
>y=. @ ]
>
>focus=. (3&{::) y
>
>addrs=. (2&{::) y
>
>crumbs=. (1&{::) y
>
>stack=. (0&{::) y
>
>
>zip=. '';'';'';<
>
>unzip=. focus @: (zout ^: (#@crumbs))
>
>
>zin=. (stack) ; (crumbs , <@focus) ; (addrs , <x) ; <@([ {:: focus)
>
>zout=. (stack) ; (}:@crumbs) ; (}:@addrs) ; <@(0 (([:*@L. _1{::crumbs)
><y^:[ focus)`(_1{::addrs)`(_1{::crumbs)} ])
>
>zam=. <x 3} ] NB. amend
>
>zap=. (@ focus)(<@:)(`((3})`]))(`:6) NB. apply
>
>zpush=. (stack , <@focus) ; (crumbs) ; (addrs) ; (<@focus) NB. push focus
>in temp stack
>
>zpop=. (}:@stack) ; (crumbs) ; (addrs) ; <@(_1{::stack) NB. pop from temp
>stack
>
>zswap=. (}:@stack,<@focus) ; (crumbs) ; (addrs) ; <@(_1{::stack) NB. swap
>focus and top of temp stack
>
>
>]T=. (i.3 3);(11;22;<(_1;i.5));(<'AAA';<'BBB';'CCC')
>
>┌─────┬──────────────────────┬───────────────┐
>
>│0 1 2│┌──┬──┬──────────────┐│┌───┬─────────┐│
>
>│3 4 5││11│22│┌──┬─────────┐│││AAA│┌───┬───┐││
>
>│6 7 8││ │ ││_1│0 1 2 3 4││││ ││BBB│CCC│││
>
>│ ││ │ │└──┴─────────┘│││ │└───┴───┘││
>
>│ │└──┴──┴──────────────┘│└───┴─────────┘│
>
>└─────┴──────────────────────┴───────────────┘
>
>NB. zip tree
>
>zip T
>
>┌┬┬┬──────────────────────────────────────────────┐
>
>││││┌─────┬──────────────────────┬───────────────┐│
>
>│││││0 1 2│┌──┬──┬──────────────┐│┌───┬─────────┐││
>
>│││││3 4 5││11│22│┌──┬─────────┐│││AAA│┌───┬───┐│││
>
>│││││6 7 8││ │ ││_1│0 1 2 3 4││││ ││BBB│CCC││││
>
>│││││ ││ │ │└──┴─────────┘│││ │└───┴───┘│││
>
>│││││ │└──┴──┴──────────────┘│└───┴─────────┘││
>
>││││└─────┴──────────────────────┴───────────────┘│
>
>└┴┴┴──────────────────────────────────────────────┘
>
>NB. Change 'CCC' to 'DDD'
>
>unzip 'DDD' zam _1 zin _1 zin _1 zin zip T
>
>┌─────┬──────────────────────┬───────────────┐
>
>│0 1 2│┌──┬──┬──────────────┐│┌───┬─────────┐│
>
>│3 4 5││11│22│┌──┬─────────┐│││AAA│┌───┬───┐││
>
>│6 7 8││ │ ││_1│0 1 2 3 4││││ ││BBB│DDD│││
>
>│ ││ │ │└──┴─────────┘│││ │└───┴───┘││
>
>│ │└──┴──┴──────────────┘│└───┴─────────┘│
>
>└─────┴──────────────────────┴───────────────┘
>
>NB. Copy the third sub-tree down into the second
>
>unzip zpop _1 zin (,&a:) zap 2 zin 1 zin zout zpush 2 zin zip T
>
>┌─────┬──────────────────────────────────────┬───────────────┐
>
>│0 1 2│┌──┬──┬──────────────────────────────┐│┌───┬─────────┐│
>
>│3 4 5││11│22│┌──┬─────────┬───────────────┐│││AAA│┌───┬───┐││
>
>│6 7 8││ │ ││_1│0 1 2 3 4│┌───┬─────────┐││││ ││BBB│CCC│││
>
>│ ││ │ ││ │ ││AAA│┌───┬───┐│││││ │└───┴───┘││
>
>│ ││ │ ││ │ ││ ││BBB│CCC│││││└───┴─────────┘│
>
>│ ││ │ ││ │ ││ │└───┴───┘││││ │
>
>│ ││ │ ││ │ │└───┴─────────┘│││ │
>
>│ ││ │ │└──┴─────────┴───────────────┘││ │
>
>│ │└──┴──┴──────────────────────────────┘│ │
>
>└─────┴──────────────────────────────────────┴───────────────┘
>
>NB. This time swap the sub-trees in the previous example
>
>unzip zpop 2 zin zout zout zswap 2 zin 1 zin zout zpush 2 zin zip T
>
>┌─────┬───────────────────────┬──────────────┐
>
>│0 1 2│┌──┬──┬───────────────┐│┌──┬─────────┐│
>
>│3 4 5││11│22│┌───┬─────────┐│││_1│0 1 2 3 4││
>
>│6 7 8││ │ ││AAA│┌───┬───┐│││└──┴─────────┘│
>
>│ ││ │ ││ ││BBB│CCC││││ │
>
>│ ││ │ ││ │└───┴───┘│││ │
>
>│ ││ │ │└───┴─────────┘││ │
>
>│ │└──┴──┴───────────────┘│ │
>
>└─────┴───────────────────────┴──────────────┘
>
>
>On Mon, Sep 8, 2014 at 3:45 PM, Devon McCormick <devon...@gmail.com> wrote:
>
>> A little research clarified what we see here: apparently it's part of the
>> definition of a binary tree that the left node be smaller than its parent
>> but the right one is greater. Right away, I see a problem for the
>> predecessor-index representation of a tree that I'm advocating as it does
>> not distinguish between right and left nodes as it is usually implemented.
>>
>>
>> On Mon, Sep 8, 2014 at 3:03 PM, Devon McCormick <devon...@gmail.com>
>> wrote:
>>
>> > Do you have a reference to a good example of this? Looking at the
>> > "before" and "after" pictures on the right here -
>> > http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree - the
>> > rebalancing seems arbitrary as it preserves some relations but changes
>> > others.
>> >
>> >
>> > On Mon, Sep 8, 2014 at 2:30 PM, Dan Bron <j...@bron.us> wrote:
>> >
>> >> Raul wrote:
>> >> > Note that J already supports trees.
>> >>
>> >> Devon wrote:
>> >> > I have J code that uses trees which I run daily and
>> >> > have been doing so for years.
>> >>
>> >> Pascal wrote:
>> >> > I think trees are done at least ok, if not "right" already.
>> >>
>> >> Challenge: express, in J, the logic of rebalancing a heap (say, a
>> >> Fibonacci
>> >> heap, but I'm not particularly picky).
>> >>
>> >> For the sake of this exercise, you may ignore considerations of
>> efficiency
>> >> (though that's a bit of a self-contradiction, because heaps are
>> frequently
>> >> introduced specifically for the sake of efficiency). I am only
>> interested
>> >> in the directness, simplicity, elegance (lyricality) of the notation, in
>> >> its current form, for expressing ideas about trees. We can make it
>> >> efficient "later" (Pepe's TCO utility is a start).
>> >>
>> >> -Dan
>> >>
>> >>
>> >>
>> >> ----------------------------------------------------------------------
>> >> For information about J forums see http://www.jsoftware.com/forums.htm
>> >>
>> >
>> >
>> >
>> > --
>> > Devon McCormick, CFA
>> >
>> >
>>
>>
>> --
>> Devon McCormick, CFA
>
>
>
>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
>----------------------------------------------------------------------
>For information about J forums see http://www.jsoftware.com/forums.htm
>----------------------------------------------------------------------
>For information about J forums see http://www.jsoftware.com/forums.htm
>
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
