<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>Fair enough, I missed that you can set ordered_set in ETS, but
nevertheless it won't work with maps. However, even if I use ETS
the Key is still stored twice, isn't? (once as the key for
ordered_set, once as the value when the Id is the key).<br>
</p>
<br>
<div class="moz-cite-prefix">On 24/09/2017 16:43, Jesper Louis
Andersen wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAGrdgiW3QWL2Nv-rcJTctbMU6zZdw4JSH6-93dJRFUJ6DMRBaQ@mail.gmail.com">
<div dir="ltr">Of course it will work: the ETS table is an
ordered_set. This ensures that you have Term order. Now, in
Erlang, numbers and thus integers have order less than
everything else. In short, min/1 is given by a call to
ets:first/1. To get max, we observe that the atom 'x' is not
part of your keys, nor part of the integers. So it is larger
than any integer. If we ask ets:prev/2 on that 'x', we get
max/1.
<div><br>
</div>
<div>This covers the range operations on IDs. For the range
operations on keys, it is even easier because they already
have sorted order. You can also get rather fast traversal by
using ets:select/1,2 and using the continuations to walk the
data set in larger chunks.</div>
<div><br>
<div class="gmail_quote">
<div dir="ltr">On Sun, Sep 24, 2017 at 6:02 PM Grzegorz
Junka <<a href="mailto:list1@gjunka.com"
target="_blank" 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">
<div 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>
</div>
<div text="#000000" bgcolor="#FFFFFF"> <br>
<div
class="m_-5731480297345621750m_-9105246346882466089moz-cite-prefix">On
24/09/2017 15:29, Jesper Louis Andersen wrote:<br>
</div>
<blockquote type="cite">
<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" target="_blank"
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>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
<br>
</body>
</html>