[erlang-questions] Tuples referencing each other problem

[Grzegorz Junka]

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 
> <mailto: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 <mailto:erlang-questions@REDACTED>
>     > http://erlang.org/mailman/listinfo/erlang-questions
>
>     _______________________________________________
>     erlang-questions mailing list
>     erlang-questions@REDACTED <mailto: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/29b9a761/attachment.htm>