<div dir="ltr">Consider an ETS table and insert<div><br></div><div>[{Key, Id}, {Id, Key}]</div><div><br></div><div>This ensures fast lookup in both directions. Alternatively, run this in a map. I often do this when mapping monitor references in code.</div></div><br><div class="gmail_quote"><div dir="ltr">On Sat, Sep 23, 2017 at 3:50 PM Grzegorz Junka <<a href="mailto:list1@gjunka.com">list1@gjunka.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Zipper looks interesting but I don't think it would suit here. Keeping<br>
paths to leafs could work but since the tree is dynamic those paths<br>
would often change and it would be very difficult to update paths that<br>
have already been stored.<br>
<br>
In short, I have keys, which may be any Erlang terms, and numerical Ids<br>
assigned to those terms. Keys must be sorted. Numerical Ids are<br>
increasing monotonically. Then the following lookups should be efficient:<br>
<br>
1. Having a key quickly search for its numeric Id<br>
2. Having a numeric Id quickly get back the key<br>
<br>
Also the following conditions should be met:<br>
<br>
3. The same key should be always assigned the same numeric Id<br>
4. One key has always one numeric Id (and vice versa), so they are<br>
always added or removed together<br>
<br>
Since keys can be of any length I don't want to store them more than<br>
once. And since they must be sorted I was thinking about using a B+Tree.<br>
Then another structure to map the numeric Id back to their keys.<br>
<br>
An obvious solution would be to make the B+Tree bidirectional - the key<br>
would be recreated by traversing the tree back from a leaf to the root.<br>
The other structure would then need to keep a mapping between the<br>
numeric Id and the reference to the leaf for the key corresponding to<br>
that numeric Id.<br>
<br>
But an equally valid solution would be to tag all nodes of the B+Tree<br>
with numbers and store tags to parents in their children. Then in<br>
another structure, e.g. an array, the mapping between the tag and its<br>
node. That would also allow to traverse the tree backward from leafs to<br>
the root.<br>
<br>
GrzegorzJ<br>
<br>
<br>
On 22/09/2017 00:37, Richard A. O'Keefe wrote:<br>
><br>
><br>
> On 22/09/17 2:23 AM, Grzegorz Junka wrote:<br>
>> To answer your question Richard, I don't actually need a cyclical<br>
>> structure. As I mentioned, this is a simplification of a more specific<br>
>> problem. I didn't want to describe all the specifics to ask a question.<br>
>> I need to design a tree, a variant of a HAMT tree, but which can be<br>
>> traversed in both directions, from the root to leafs and from leafs to<br>
>> the root (independently, i.e. starting from a reference to a leaf rather<br>
>> than recursively).<br>
><br>
> Of course this pushes back the question a further step.<br>
> Why do you want to traverse the tree in both directions?<br>
><br>
> Might the "zipper" approach be any use?<br>
><br>
> If you want references to leaves, such references could be paths.<br>
> I used that technique once in a programming language that used<br>
> reference counting, so that link cycles meant no collection.<br>
> (Yes, I know modern reference-based collectors have solved that<br>
> problem.)  I've also used that technique for processing XML in<br>
> a pure functional language.<br>
><br>
> In an imperative context, that doesn't work very well because the<br>
> tree structure might change.  The DOM suffers from trying to make<br>
> this "work" in some sense, but trying to iterate over a graph<br>
> while something else is changing it is never going to be easy.<br>
><br>
> It is possible that the Haskell "Functional Graph Library"<br>
> may be relevant to your needs.<br>
><br>
> _______________________________________________<br>
> erlang-questions mailing list<br>
> <a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
> <a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br>
_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
</blockquote></div>