[PD] Associative list datastructure

Tue Nov 18 08:34:13 CET 2014

Hi,

that's very nice and useful. Maybe it's time someone writes a [text]-abs
collection? :)

The only "ugly" thing is the semi-global send/receive in $1/in and $1/out. I
wonder if this couldn't be made a bit more conflict-free. I guess, I would
prefer one really global receiver, that could possibly made local with a second
argument (i.e. $0) that is prepended to the receiver name, as it is done in sssad.

But maybe that always was ugly itself.

Ciao
-- 
Frank

On Thu, Nov 13, 2014 at 11:47:50AM +0800, Chris McCormick wrote:
> Hi *,
> 
> Attached is another vanilla implementation for a datastructure commonly
> found in programming languages, sometimes called map, hashmap or
> associative array where keys refer to values.
> <http://en.wikipedia.org/wiki/Associative_array>
> 
> In this case the key is the first item of a list and the value is the
> remainder of the list.
> 
> Internally it uses the new [text] datastructure to make it a big faster
> than previous similar implementations.
> 
> This isn't a true hashmap as it doesn't use hashing for storage and
> lookups, so lookup time will get slower as you add more elements = O(n).
> For many of our use-cases that is probably fine.
> 
> Cheers,
> 
> Chris.
> 
> -- 
> http://mccormick.cx/

> #N canvas 911 346 450 336 10;
> #X obj 12 11 inlet;
> #X obj 189 312 outlet;
> #N canvas 520 234 450 628 set 0;
> #X obj 11 12 inlet;
> #X obj 11 119 sel -1;
> #X obj 11 64 list split 1;
> #X obj 11 274 list;
> #X obj 11 249 t b a;
> #X obj 11 299 text set \$0-map;
> #X obj 11 94 text search \$0-map;
> #X obj 11 34 t a a;
> #X text 91 145 try to find a __NULL key to replace;
> #X obj 11 169 text search \$0-map;
> #X obj 11 191 sel -1;
> #X msg 11 145 list __NULL;
> #X text 137 82 try to find the key to replace;
> #X text 70 220 create a new key space;
> #X msg 11 224 1e+09;
> #X connect 0 0 7 0;
> #X connect 1 0 11 0;
> #X connect 1 1 4 0;
> #X connect 2 0 6 0;
> #X connect 3 0 5 0;
> #X connect 4 0 3 0;
> #X connect 4 1 5 1;
> #X connect 6 0 1 0;
> #X connect 7 0 2 0;
> #X connect 7 1 3 1;
> #X connect 9 0 10 0;
> #X connect 10 0 14 0;
> #X connect 10 1 4 0;
> #X connect 11 0 9 0;
> #X connect 14 0 4 0;
> #X restore 101 187 pd set;
> #N canvas 721 137 450 326 get 0;
> #X obj 11 11 inlet;
> #X obj 11 292 outlet;
> #X obj 11 57 text search \$0-map;
> #X obj 11 79 sel -1;
> #X obj 44 107 text get \$0-map;
> #X obj 11 33 list;
> #X obj 44 129 list split 1;
> #X connect 0 0 5 0;
> #X connect 2 0 3 0;
> #X connect 3 0 1 0;
> #X connect 3 1 4 0;
> #X connect 4 0 6 0;
> #X connect 5 0 2 0;
> #X connect 6 1 1 0;
> #X restore 189 187 pd get;
> #N canvas 523 249 450 628 del 0;
> #X obj 11 12 inlet;
> #X obj 11 89 sel -1;
> #X obj 11 34 list split 1;
> #X obj 44 114 t b a;
> #X obj 44 164 text set \$0-map;
> #X obj 11 64 text search \$0-map;
> #X msg 44 139 list __NULL;
> #X connect 0 0 2 0;
> #X connect 1 1 3 0;
> #X connect 2 0 5 0;
> #X connect 3 0 6 0;
> #X connect 3 1 4 1;
> #X connect 5 0 1 0;
> #X connect 6 0 4 0;
> #X restore 145 187 pd del;
> #N canvas 204 125 450 436 each 1;
> #X obj 13 14 inlet;
> #X obj 13 373 outlet;
> #X obj 13 186 until;
> #X obj 13 217 text sequence \$0-map;
> #X obj 13 146 t b b;
> #X msg 70 169 line 0;
> #X obj 13 239 t a a;
> #X obj 13 351 list;
> #X obj 13 264 list split 1;
> #X msg 70 309 bang;
> #X obj 13 286 sel __NULL;
> #X obj 13 36 text size \$0-map;
> #X obj 13 58 > 0;
> #X obj 13 80 sel 1;
> #X text 129 64 sanity check empty map.;
> #X connect 0 0 11 0;
> #X connect 2 0 3 0;
> #X connect 3 0 6 0;
> #X connect 3 1 2 1;
> #X connect 4 0 2 0;
> #X connect 4 1 5 0;
> #X connect 5 0 3 0;
> #X connect 6 0 8 0;
> #X connect 6 1 7 1;
> #X connect 7 0 1 0;
> #X connect 8 0 10 0;
> #X connect 9 0 7 0;
> #X connect 10 1 9 0;
> #X connect 11 0 12 0;
> #X connect 12 0 13 0;
> #X connect 13 0 4 0;
> #X restore 278 187 pd each;
> #X obj 53 11 r \$1/in;
> #X obj 216 288 s \$1/out;
> #X text 285 111 non-map messages (clear \, write \, read etc.) get
> passed straight through to text, f 25;
> #X obj 189 265 t a a;
> #X obj 328 187 text define \$0-map;
> #X obj 189 244 list prepend;
> #X obj 101 148 route set del get length each;
> #N canvas 2 50 450 300 len 0;
> #X obj 18 9 inlet;
> #X obj 18 84 outlet;
> #X obj 18 59 text size \$0-map;
> #X msg 18 34 bang;
> #X connect 0 0 3 0;
> #X connect 2 0 1 0;
> #X connect 3 0 2 0;
> #X restore 233 187 pd len;
> #X obj 12 45 list;
> #X obj 12 67 list trim;
> #X obj 12 89 route prefix;
> #X obj 12 111 s \$0/prefix;
> #X obj 258 223 r \$0/prefix;
> #X connect 0 0 14 0;
> #X connect 3 0 11 0;
> #X connect 5 0 11 0;
> #X connect 6 0 14 0;
> #X connect 9 0 1 0;
> #X connect 9 1 7 0;
> #X connect 10 0 11 0;
> #X connect 11 0 9 0;
> #X connect 12 0 2 0;
> #X connect 12 1 4 0;
> #X connect 12 2 3 0;
> #X connect 12 3 13 0;
> #X connect 12 4 5 0;
> #X connect 12 5 10 0;
> #X connect 13 0 11 0;
> #X connect 14 0 15 0;
> #X connect 15 0 16 0;
> #X connect 16 0 17 0;
> #X connect 16 1 12 0;
> #X connect 18 0 11 1;

> #N canvas 490 246 450 398 10;
> #X obj 16 14 inlet;
> #X obj 47 155 s \$1/in;
> #X obj 35 268 r \$1/out;
> #X obj 35 312 spigot 0;
> #X obj 35 334 outlet;
> #X msg 79 58 1;
> #X msg 16 228 0;
> #X obj 35 290 route \$0;
> #X obj 63 133 s \$1/in;
> #X obj 63 90 \$0;
> #X msg 63 112 prefix \$1;
> #X obj 16 36 t b b a b b;
> #X msg 31 177 prefix;
> #X obj 31 199 s \$1/in;
> #X connect 0 0 11 0;
> #X connect 2 0 7 0;
> #X connect 3 0 4 0;
> #X connect 5 0 3 1;
> #X connect 6 0 3 1;
> #X connect 7 0 3 0;
> #X connect 9 0 10 0;
> #X connect 10 0 8 0;
> #X connect 11 0 6 0;
> #X connect 11 1 12 0;
> #X connect 11 2 1 0;
> #X connect 11 3 9 0;
> #X connect 11 4 5 0;
> #X connect 12 0 13 0;

> #N canvas 735 405 450 300 10;
> #X msg 16 71 get /test/one;
> #X obj 16 263 print 2;
> #X msg 16 16 set /test/one hello i am an entry;
> #X msg 16 218 get /test/two;
> #X obj 363 16 map \$0/test;
> #X obj 16 95 map-api \$0/test;
> #X msg 16 158 set /test/two 120 zing boom;
> #X msg 187 72 del /test/one;
> #X obj 16 38 map-api \$0/test;
> #X obj 16 241 map-api \$0/test;
> #X obj 16 180 map-api \$0/test;
> #X obj 187 94 map-api \$0/test;
> #X obj 16 117 print /test/one;
> #X msg 240 173 each;
> #X obj 240 217 print each;
> #X obj 240 195 map-api \$0/test;
> #X connect 0 0 5 0;
> #X connect 2 0 8 0;
> #X connect 3 0 9 0;
> #X connect 5 0 12 0;
> #X connect 6 0 10 0;
> #X connect 7 0 11 0;
> #X connect 9 0 1 0;
> #X connect 13 0 15 0;
> #X connect 15 0 14 0;

> #N canvas 446 203 450 383 10;
> #X obj 150 310 print;
> #X msg 319 105 each;
> #X msg 20 240 prefix 123;
> #X msg 19 64 set /test this is my list of 8 different elements;
> #X text 17 9 hash map mimic. __NULL is a reserved key. Use the map-api
> object to interface with a particular instance.;
> #X msg 49 91 set /test some other list to replace it;
> #X msg 76 118 set /test/two more data to store;
> #X msg 128 148 get /test;
> #X msg 139 171 get /test/two;
> #X msg 193 245 get 543543;
> #X msg 158 195 del /test;
> #X msg 170 221 del /test/two;
> #X msg 293 163 clear;
> #X msg 293 186 read my-map.txt;
> #X msg 293 209 write my-map.txt;
> #X text 19 218 ID a request;
> #X msg 21 263 prefix;
> #X obj 319 291 s mymap/in;
> #X obj 150 288 map mymap;
> #X msg 319 269 each;
> #X obj 319 313 r mymap/out;
> #X text 316 248 native send/receive;
> #X connect 1 0 18 0;
> #X connect 2 0 18 0;
> #X connect 3 0 18 0;
> #X connect 5 0 18 0;
> #X connect 6 0 18 0;
> #X connect 7 0 18 0;
> #X connect 8 0 18 0;
> #X connect 9 0 18 0;
> #X connect 10 0 18 0;
> #X connect 11 0 18 0;
> #X connect 12 0 18 0;
> #X connect 13 0 18 0;
> #X connect 14 0 18 0;
> #X connect 16 0 18 0;
> #X connect 18 0 0 0;
> #X connect 19 0 17 0;

> _______________________________________________
> Pd-list at lists.iem.at mailing list
> UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list

-- 
 Frank Barknecht                                     _ ______footils.org__