Best way to implement a "Linked MultiMap" data structure?

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Best way to implement a "Linked MultiMap" data structure?

cambiata
I often have a need "list of linked lists"/"linked multimap" solutions with the following properties:

Basic functionality:
* One parent list/dictionary/array, acting as parent for
* N number of sublists/dictionarys/arrays (each item an object)
* The sublists should be linked, with the possibility to push an item from one sublist to the next etc.

On top of that:
* There should be a possibility to implement some rules for controlling things like the maximum number of items in a sublist
* Automatic creation/deletion of sublists to take care of addition/deletion of sublitst items

A typical use would be in a TextArea control, where
- the text area is the parent list
- each line is a sublist
- each word is an item in the sublist

When starting typing, we have one sublist with an increasing number of words...
When exceeding the maximum linewidth, the line breaks and the overflowing word is pushed onto an automatically created sublist...
When removing a word somewhere in a line, there should be a "backflow" of words if possible...

So, does this kind of "data structure pattern" exist in an established form?
What would be the most elegant/fastest way to handle this kind of structure?

Just to clearify: I'm *not* aiming to rewrite any ui textarea stuff, I'm collecting solutions that would be possible to use in a musical notation context, where there's the same problem with flowing bars from one system to the next, flowing systems from one page to the next etc...

Just to make things more interesting, it would be great to implement something like Kunth/Pliss algorithm for object flow, implemeted in TeX for word-wrap etc... :-) http://en.wikipedia.org/wiki/Word_wrap
That one exists in a js canvas implementation, by the way:

Ideas?
Reply | Threaded
Open this post in threaded view
|

Re: Best way to implement a "Linked MultiMap" data structure?

Tarwin Stroh-Spijer
If there isn't one here (http://code.google.com/p/polygonal/source/browse/#svn%2Ftrunk%2Fsrc%2Flib%2Fde%2Fpolygonal%2Fds) then you / they might want to add to it?


Tarwin Stroh-Spijer
_______________________

Touch My Pixel
http://www.touchmypixel.com/
phone: +61 3 8060 5321
_______________________


On Sat, Nov 5, 2011 at 9:22 AM, cambiata <[hidden email]> wrote:
I often have a need "list of linked lists"/"linked multimap" solutions with
the following properties:

Basic functionality:
* One parent list/dictionary/array, acting as parent for
* N number of sublists/dictionarys/arrays (each item an object)
* The sublists should be linked, with the possibility to push an item from
one sublist to the next etc.

On top of that:
* There should be a possibility to implement some rules for controlling
things like the maximum number of items in a sublist
* Automatic creation/deletion of sublists to take care of addition/deletion
of sublitst items

A typical use would be in a TextArea control, where
- the text area is the parent list
- each line is a sublist
- each word is an item in the sublist

When starting typing, we have one sublist with an increasing number of
words...
When exceeding the maximum linewidth, the line breaks and the overflowing
word is pushed onto an automatically created sublist...
When removing a word somewhere in a line, there should be a "backflow" of
words if possible...

So, does this kind of "data structure pattern" exist in an established form?
What would be the most elegant/fastest way to handle this kind of structure?

Just to clearify: I'm *not* aiming to rewrite any ui textarea stuff, I'm
collecting solutions that would be possible to use in a musical notation
context, where there's the same problem with flowing bars from one system to
the next, flowing systems from one page to the next etc...

Just to make things more interesting, it would be great to implement
something like Kunth/Pliss algorithm for object flow, implemeted in TeX for
word-wrap etc... :-) http://en.wikipedia.org/wiki/Word_wrap
That one exists in a js canvas implementation, by the way:

Ideas?

--
View this message in context: http://haxe.1354130.n2.nabble.com/Best-way-to-implement-a-Linked-MultiMap-data-structure-tp6966166p6966166.html
Sent from the Haxe mailing list archive at Nabble.com.

--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Best way to implement a "Linked MultiMap" data structure?

cambiata
Hi Tarwin!

I'd love to, If I only knew how..!
I was hoping to draw Michaels attraction to this thread. Let's see what happens! :-)
Reply | Threaded
Open this post in threaded view
|

Re: Best way to implement a "Linked MultiMap" data structure?

cambiata
...draw Michaels *attention*..? :-)
Reply | Threaded
Open this post in threaded view
|

Re: Best way to implement a "Linked MultiMap" data structure?

Michael Baczynski-2
actually, after reading this thread I did some research this morning about multi maps. :) It's
definitely on my TODO list. about your "Linked MultiMap" proposal, I don't quite understand: can you
explain it in terms of Key->Value mappings? A MultiMap can map several values to the same key:
Key1=>Value1,Value2,ValueN..

best,
michael

On 07.11.2011 09:30, cambiata wrote:
> ...draw Michaels *attention*..? :-)
>
> --
> View this message in context: http://haxe.1354130.n2.nabble.com/Best-way-to-implement-a-Linked-MultiMap-data-structure-tp6966166p6969556.html
> Sent from the Haxe mailing list archive at Nabble.com.
>


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Best way to implement a "Linked MultiMap" data structure?

Dion Whitehead Amago
Hydrax has Multimaps and Multisets.

Dion

On Monday, November 7, 2011, Michael Baczynski <[hidden email]> wrote:
> actually, after reading this thread I did some research this morning about multi maps. :) It's definitely on my TODO list. about your "Linked MultiMap" proposal, I don't quite understand: can you explain it in terms of Key->Value mappings? A MultiMap can map several values to the same key:
> Key1=>Value1,Value2,ValueN..

>
> best,
> michael
>
> On 07.11.2011 09:30, cambiata wrote:
>>
>> ...draw Michaels *attention*..? :-)
>>
>> --
>> View this message in context: http://haxe.1354130.n2.nabble.com/Best-way-to-implement-a-Linked-MultiMap-data-structure-tp6966166p6969556.html
>> Sent from the Haxe mailing list archive at Nabble.com.
>>
>
>
> --
> haXe - an open source web programming language
> http://haxe.org
>
--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Best way to implement a "Linked MultiMap" data structure?

cambiata
In reply to this post by Michael Baczynski-2
@Michael: There are two levels in this "linking" stuff...

1. The sub lists (represented by each key) are "chained" together so that the last value of key1 is "linked" to the first value of key 2 etc. The "linked multimap" keys (representing value lists) should offer helper methods like pushLastValueToNextKeylist() or pullFirstValueFromNextKeylist() etc...

2. The "linked multimap" should simplify the creation of "control logic" callbacks for the sublists. Here the TextArea analogy is the best way to explain it, I think: The "control logic" here is a callback that checks if the maximum line width is exceeded, and if so pushes the last word to the next line (= pushLastValueToNextKeylist())
Reply | Threaded
Open this post in threaded view
|

Re: Best way to implement a "Linked MultiMap" data structure?

cambiata
In reply to this post by Dion Whitehead Amago
@Dion: Great!
Well, to really stand out, Hydrax should have "Linked multimaps"! :-)

I'll check it out. Thanks!
Reply | Threaded
Open this post in threaded view
|

Re: Best way to implement a "Linked MultiMap" data structure?

Michael Baczynski-2
In reply to this post by cambiata
If the last value of key1 is linked to the first value of key2 keys have to be stored in a sorted
order, right? I would take a linked-list (=keys), each storing another linked lists (=values), so
you have a sequential structure. now shifting elements between sublists is straightforward.
Finding the key and a value in the sublist would be O(n) worst case or O(n/2) avg I guess.

best,
michael

On 07.11.2011 22:20, cambiata wrote:

> @Michael: There are two levels in this "linking" stuff...
>
> 1. The sub lists (represented by each key) are "chained" together so that
> the last value of key1 is "linked" to the first value of key 2 etc. The
> "linked multimap" keys (representing value lists) should offer helper
> methods like pushLastValueToNextKeylist() or pullFirstValueFromNextKeylist()
> etc...
>
> 2. The "linked multimap" should simplify the creation of "control logic"
> callbacks for the sublists. Here the TextArea analogy is the best way to
> explain it, I think: The "control logic" here is a callback that checks if
> the maximum line width is exceeded, and if so pushes the last word to the
> next line (= pushLastValueToNextKeylist())
>
>
> --
> View this message in context: http://haxe.1354130.n2.nabble.com/Best-way-to-implement-a-Linked-MultiMap-data-structure-tp6966166p6972121.html
> Sent from the Haxe mailing list archive at Nabble.com.
>


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Best way to implement a "Linked MultiMap" data structure?

cambiata
Thank you, Michael! I'll give it a try!