Sure:
'data indices'=. 'abcdeq';__ 0 1 1 1 0
We see that b and q have a as their parent:
data {~ indices {~ data i.'bq'
aa
And, we see that c d and e have b as their parent:
data {~ indices {~ data i.'cde'
bbb
And when we look at the diagram, we see the same thing:
c
/
b - d
/ \
a e
\
q
So, for example:
insert_under=:dyad define
'old_data old_indices'=. y
'new_data new_parents'=. x
data=.old_data,~.new_data -. old_data
data;old_indices,old_data i. ($new_data)$new_parents
)
Example use:
('jkl';'d') insert_under 'abcdeq';__ 0 1 1 1 0
That said, beware that like most tree implementations, this is a
solution searching for a problem. (Which is itself a problem, since
usually we need solutions to real life problems - and this usually
takes us way outside our comfort level. Which tends to snowball until
either someone fixes it or ... not ...).
Thanks,
--
Raul
newparents=.
Thanks,
--
Raul
On Fri, Dec 22, 2017 at 9:18 AM, Dabrowski, Andrew John
<[email protected]> wrote:
>
>
> On Dec 22, 2017 12:50 AM, Raul Miller <[email protected]> wrote:
> I'm not sure about ordinal fractions, but one way of representing that
> tree in J is:
>
> 'abcdeq';__ 0 1 1 1 0
>
> Here, we have a pair of lists, the first is data, the second is structure.
>
> The structural values are the index of the parent
>
> Could you explain this? I might have thought it would be
>
> 'abqcde';_ 0 1 0 1 2
>
>
>
> node. This approach
> allows for relatively simple insertion. (Delete makes things more
> complex but you can get rid of indexes and perhaps even replace the
> corresponding data element with fill. This requires a later garbage
> collect operation.)
>
> Sometimes it might make things easier to have the root node be the
> parent of itself.
>
> Like any J implementation, scalar traversal will tend to be
> inefficient, but if you can operate on the structure as a whole you
> can get good performance. (This also suggests that inserts and deletes
> would ideally be done en-masse rather than bit by bit.)
>
> Now... whether a tree structure is worth implementing is another
> issue. For example, OS directory structures can serve as tree
> structures, and sometimes are a good choice.
>
> Then again ... trees are often used primarily to represent a flat
> list "efficiently" for a small-step-at-a-time algorithm, and that an
> approach based on flat lists might be more efficient if you can group
> up the inserts and deletes in a good way...
>
> Of course, often people use trees because it's fun to re-invent the wheel.
>
> But I guess what I'm saying is that trees can sometimes be a "code smell".
>
> Thanks,
>
> --
> Raul
>
> On Thu, Dec 21, 2017 at 10:21 PM, David Lambert <[email protected]> wrote:
>> I'd use an index vector to store the ordinal fraction as I understand them.
>> Check my comprehension please. Do the ordinal fractions and tree agree?
>>
>>
>> c
>> /
>> b - d
>> / \
>> a e
>> \
>> q
>>
>>
>> 0 0 0 a
>> 0 1 0 b
>> 0 2 0 q
>> 0 1 1 c
>> 0 1 1 d
>> 0 1 2 e
>>
>>
>> Boxes take a long time in j because, among other things, each open box must
>> be type and shape and rank checked.
>>
>> Under ordinal fraction addressing scheme, is there a way to know that data
>> is stored internally as a regular array? Knowing the stride between items
>> is key to fast execution.
>> ----------------------------------------------------------------------
>> 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
