[erlang-questions] Tuples referencing each other problem

[Jesper Louis Andersen]

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/af383fc9/attachment.htm>