<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">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">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>
</blockquote>
<br>
</div></blockquote></div></div></div>