[erlang-questions] Tuples referencing each other problem

[Jesper Louis Andersen]

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.

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.

On Sun, Sep 24, 2017 at 6:02 PM Grzegorz Junka <list1@REDACTED> wrote:

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