<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>Thanks but that won't work. As mentioned keys must be sorted so
that I can quickly query for range from min/max key. I could add
an index but in that case the key would be stored twice, once in
the index and once in the value, which I wanted to avoid.</p>
<p>GrzegorzJ<br>
</p>
<br>
<div class="moz-cite-prefix">On 24/09/2017 15:29, Jesper Louis
Andersen wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAGrdgiU=Z+1ObXwxdZrBU_DOPNOkT_vnr8OqNyjv_fgUdaWDzg@mail.gmail.com">
<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" moz-do-not-send="true">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" moz-do-not-send="true">erlang-questions@erlang.org</a><br>
> <a
href="http://erlang.org/mailman/listinfo/erlang-questions"
rel="noreferrer" target="_blank" moz-do-not-send="true">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"
moz-do-not-send="true">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions"
rel="noreferrer" target="_blank" moz-do-not-send="true">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
</blockquote>
</div>
</blockquote>
<br>
</body>
</html>