SCClassLibrary/Common/Collections/Dictionary.sc

   1 Dictionary : Set {
   2
   3         *new { arg n=8; ^super.new(n*2) }
   4         *newFrom { arg aCollection;
   5                 var newCollection = this.new(aCollection.size);
   6                 aCollection.keysValuesDo({ arg k,v, i; newCollection.put(k,v) });
   7                 ^newCollection
   8         }
   9
  10         // accessing
  11         at { arg key;
  12                 ^array.at(this.scanFor(key) + 1)
  13         }
  14         atFail { arg key, function;
  15                 var val;
  16                 val = this.at(key);
  17                 if ( val.isNil, { ^function.value }, { ^val });
  18         }
  19         matchAt { |key|
  20                 this.keysValuesDo({ |k, v|
  21                         if(k.matchItem(key)) { ^v }
  22                 });
  23                 ^nil
  24         }
  25         trueAt { arg key;
  26                 ^this.at(key) ? false
  27         }
  28         add { arg anAssociation;
  29                 this.put(anAssociation.key, anAssociation.value);
  30         }
  31         put { arg key, value;
  32                 var atKey;
  33                 var index;
  34                 value ?? { this.removeAt(key); ^this };
  35                 index = this.scanFor(key);
  36                 array.put(index+1, value);
  37                 if ( array.at(index).isNil, {
  38                         array.put(index, key);
  39                         size = size + 1;
  40                         if (array.size < (size * 4), { this.grow });
  41                 });
  42         }
  43         putAll { arg ... dictionaries;
  44                 dictionaries.do {|dict|
  45                         dict.keysValuesDo { arg key, value;
  46                                 this.put(key, value)
  47                         }
  48                 }
  49         }
  50         putPairs { arg args;
  51                 args.pairsDo { |key, val| this.put(key, val) }
  52         }
  53         getPairs { arg args;
  54                 var result;
  55                 args = args ?? { this.keys };
  56                 args.do { |key|
  57                         var val = this.at(key);
  58                         val !? { result = result.add(key).add(val) }
  59                 };
  60                 ^result
  61         }
  62
  63         associationAt { arg key;
  64                 var index = this.scanFor(key);
  65                 if (index >= 0, {
  66                         ^Association.new(array.at(index), array.at(index+1));
  67                 },{
  68                         ^nil
  69                 });
  70         }
  71         associationAtFail { arg argKey, function;
  72                 var index = this.scanFor(argKey);
  73                 var key = array.at(index);
  74                 if ( key.isNil, { ^function.value }, {
  75                         ^Association.new(key, array.at(index+1)) });
  76         }
  77         keys { arg species(Set);
  78                 var set = species.new(size);
  79                 this.keysDo({ arg key; set.add(key) });
  80                 ^set
  81         }
  82         values {
  83                 var list = List.new(size);
  84                 this.do({ arg value; list.add(value) });
  85                 ^list
  86         }
  87
  88         // testing
  89         includes { arg item1;
  90                 this.do({ arg item2; if (item1 == item2, {^true}) });
  91                 ^false
  92         }
  93         includesKey { arg key;
  94                 ^this.at( key ).notNil;
  95         }
  96
  97         // removing
  98         removeAt { arg key;
  99                 var val;
 100                 var index = this.scanFor(key);
 101                 var atKeyIndex = array.at(index);
 102                 if ( atKeyIndex.isNil, { ^nil });
 103                 val = array.at(index+1);
 104                 array.put(index, nil);
 105                 array.put(index+1, nil);
 106                 size = size - 1;
 107                 this.fixCollisionsFrom(index);
 108                 ^val
 109         }
 110         removeAtFail { arg key, function;
 111                 var val;
 112                 var index = this.scanFor(key);
 113                 var atKeyIndex = array.at(index);
 114                 if ( atKeyIndex.isNil, { ^function.value });
 115                 val = array.at(index+1);
 116                 array.put(index, nil);
 117                 array.put(index+1, nil);
 118                 size = size - 1;
 119                 this.fixCollisionsFrom(index);
 120                 ^val
 121         }
 122
 123         remove { ^this.shouldNotImplement(thisMethod) }
 124         removeFail { ^this.shouldNotImplement(thisMethod) }
 125
 126         // enumerating
 127         keysValuesDo { arg function;
 128                 this.keysValuesArrayDo(array, function);
 129         }
 130         keysValuesChange { arg function;
 131                 this.keysValuesDo({ arg key, value, i;
 132                         this.put(key, function.value(key, value, i));
 133                 })
 134         }
 135         do { arg function;
 136                 this.keysValuesDo({ arg key, value, i;
 137                         function.value(value, i);
 138                 })
 139         }
 140         keysDo { arg function;
 141                 this.keysValuesDo({ arg key, val, i;
 142                         function.value(key, i);
 143                 })
 144         }
 145         associationsDo { arg function;
 146                 this.keysValuesDo({ arg key, val, i;
 147                         function.value( Association.new(key, val), i);
 148                 })
 149         }
 150         pairsDo { arg function;
 151                 this.keysValuesArrayDo(array, function);
 152
 153         }
 154         collect { arg function;
 155                 var res = this.class.new(this.size);
 156                 this.keysValuesDo { arg key, elem; res.put(key, function.value(elem, key)) }
 157                 ^res;
 158         }
 159         select { arg function;
 160                 var res = this.class.new(this.size);
 161                 this.keysValuesDo { arg key, elem; if(function.value(elem, key)) { res.put(key, elem) } }
 162                 ^res;
 163         }
 164         reject { arg function;
 165                 var res = this.class.new(this.size);
 166                 this.keysValuesDo { arg key, elem; if(function.value(elem, key).not)
 167                         { res.put(key, elem) } }
 168                 ^res;
 169         }
 170
 171         invert {
 172                 var dict = this.class.new(this.size);
 173                 this.keysValuesDo {|key, val|
 174                         dict.put(val, key)
 175                 };
 176                 ^dict
 177         }
 178
 179         merge {|that, func, fill = true|
 180                 var commonKeys, myKeys = this.keys, otherKeys = that.keys;
 181                 var res = ();
 182
 183                 if (myKeys == otherKeys) {
 184                         commonKeys = myKeys
 185                 } {
 186                         commonKeys = myKeys.sect(otherKeys);
 187                 };
 188
 189                 commonKeys.do { |key|
 190                         res[key] = func.value(this[key], that[key], key)
 191                 };
 192
 193                 if (fill) {
 194                         myKeys.difference(otherKeys).do { |key| res[key] = this[key] };
 195                         otherKeys.difference(myKeys).do { |key| res[key] = that[key] };
 196                 };
 197                 ^res
 198         }
 199
 200         blend { |that, blend = 0.5, fill = true, specs|
 201
 202                 ^this.merge(that, { |a, b, key|
 203                         var spec = if (specs.notNil) { specs[key].asSpec };
 204                         if (spec.notNil) {
 205                                 spec.map(blend(spec.unmap(a), spec.unmap(b), blend))
 206                         } {
 207                                 blend(a, b, blend)
 208                         }
 209                 }, fill)
 210         }
 211
 212         findKeyForValue { arg argValue;
 213                 this.keysValuesArrayDo(array, { arg key, val, i;
 214                         if (argValue == val, { ^key })
 215                 });
 216                 ^nil
 217         }
 218
 219         sortedKeysValuesDo { arg function, sortFunc;
 220                 var keys = this.keys(Array);
 221                 keys.sort(sortFunc);
 222
 223                 keys.do { arg key, i;
 224                         function.value(key, this[key], i);
 225                 };
 226         }
 227
 228         choose {
 229                 var index, key, val;
 230                 if( this.isEmpty, { ^nil }); // empty dictionary
 231                 while({
 232                         index = (array.size >> 1).rand << 1; // generate an even index.
 233                         array.at(index).isNil;                    // key is at even index.
 234                 });
 235                 // return the value for the first non Nil key we find.
 236                 // the value is at the odd index.
 237                 ^array.at(index + 1);
 238         }
 239         order { arg func;
 240                 var assoc;
 241                 if( this.isEmpty, { ^nil });
 242                 this.keysValuesDo { arg key, val;
 243                         assoc = assoc.add(key -> val);
 244                 };
 245                 ^assoc.sort(func).collect(_.key)
 246         }
 247         powerset {
 248                 var keys = this.keys.asArray.powerset;
 249                 ^keys.collect { | list |
 250                         var dict = this.class.new;
 251                         list.do { |key| dict.put(key, this[key]) };
 252                         dict
 253                 }
 254         }
 255
 256         // Pattern support
 257         transformEvent { arg event;
 258                 ^event.putAll(this);
 259         }
 260         embedInStream { arg event;
 261                 ^yield(event !? { event.copy.putAll(this) })
 262         }
 263
 264         asSortedArray {
 265                 var array;
 266                 if ( this.notEmpty ){
 267                         this.keysValuesDo({ arg key, value; array = array.add([key,value]); });
 268                         array = array.sort({ arg a, b; a.at(0) < b.at(0) });
 269                 }{
 270                         array = [];
 271                 };
 272                 ^array;
 273         }
 274         asKeyValuePairs {
 275                 var array = Array.new(this.size * 2);
 276                 this.keysValuesDo { |key, val| array.add(key); array.add(val) };
 277                 ^array
 278         }
 279
 280         // PRIVATE IMPLEMENTATION
 281         keysValuesArrayDo { arg argArray, function;
 282                 // special byte codes inserted by compiler for this method
 283                 var i=0, j=0, key, val;
 284                 var arraySize = argArray.size;
 285                 while ({ i < arraySize },{
 286                         key = argArray.at(i);
 287                         if (key.notNil, {
 288                                 val = argArray.at(i+1);
 289                                 function.value(key, val, j);
 290                                 j = j + 1;
 291                         });
 292                         i = i + 2;
 293                 });
 294         }
 295         grow {
 296                 var index;
 297                 var oldElements = array;
 298                 array = Array.newClear(array.size * 2);
 299                 this.keysValuesArrayDo(oldElements,
 300                 { arg key, val;
 301                         index = this.scanFor(key);
 302                         array.put(index, key);
 303                         array.put(index+1, val);
 304                 });
 305         }
 306         fixCollisionsFrom { arg index;
 307                 var newIndex, key;
 308
 309                 var oldIndex = index;
 310                 var lastKeyIndex = array.size - 2;
 311                 while ({
 312                         if (oldIndex == lastKeyIndex, { oldIndex = 0 }, { oldIndex = oldIndex + 2 });
 313                         (key = array.at(oldIndex)).notNil
 314                 },{
 315                         newIndex = this.scanFor(key);
 316                         if ( oldIndex != newIndex, {
 317                                 array.swap(oldIndex, newIndex);
 318                                 array.swap(oldIndex+1, newIndex+1)
 319                         })
 320                 })
 321         }
 322         scanFor { arg argKey;
 323                 var maxHash = array.size div: 2;
 324                 var start = (argKey.hash % maxHash) * 2;
 325                 var end = array.size-1;
 326                 var i = start;
 327                 forBy( start, end, 2, { arg i;
 328                         var key = array.at(i);
 329                         if ( key.isNil or: { key == argKey }, { ^i });
 330                 });
 331                 end = start - 1;
 332                 forBy( 0, start-2, 2, { arg i;
 333                         var key = array.at(i);
 334                         if ( key.isNil or: { key == argKey }, { ^i });
 335                 });
 336                 ^-2
 337         }
 338
 339         storeItemsOn { arg stream, itemsPerLine = 5;
 340                 var itemsPerLinem1 = itemsPerLine - 1;
 341                 var last = this.size - 1;
 342                 this.associationsDo({ arg item, i;
 343                         item.storeOn(stream);
 344                         if (i < last, { stream.comma.space;
 345                                 if (i % itemsPerLine == itemsPerLinem1, { stream.nl.space.space });
 346                         });
 347                 });
 348         }
 349         printItemsOn { arg stream, itemsPerLine = 5;
 350                 var itemsPerLinem1 = itemsPerLine - 1;
 351                 var last = this.size - 1;
 352                 this.associationsDo({ arg item, i;
 353                         item.printOn(stream);
 354                         if (i < last, { stream.comma.space;
 355                                 if (i % itemsPerLine == itemsPerLinem1, { stream.nl.space.space });
 356                         });
 357                 });
 358         }
 359 }
 360
 361 IdentityDictionary : Dictionary {
 362         var <>proto; // inheritance of properties
 363         var <>parent; // inheritance of properties
 364
 365         var <>know = false;
 366         // if know is set to true then not understood messages will look in the dictionary
 367         // for that selector and send the value message to them.
 368
 369         *new { arg n=8, proto, parent, know=false;
 370                 ^super.new(n).proto_(proto).parent_(parent).know_(know)
 371         }
 372
 373         at { arg key;
 374                 _IdentDict_At
 375                 ^this.primitiveFailed
 376                 /*^array.at(this.scanFor(key) + 1)*/
 377         }
 378         put { arg key, value;
 379                 _IdentDict_Put
 380                 value ?? { this.removeAt(key); ^this };
 381                 ^this.primitiveFailed
 382                 /*
 383                 var index, atKey;
 384                 index = this.scanFor(key);
 385                 array.put(index+1, value);
 386                 if ( array.at(index).isNil, {
 387                         array.put(index, key);
 388                         size = size + 1;
 389                         if (array.size < (size * 4), { this.grow });
 390                 });
 391                 */
 392         }
 393         putGet { arg key, value;
 394                 _IdentDict_PutGet
 395                 ^this.primitiveFailed
 396                 /*
 397                 var index, atKey, prev;
 398                 index = this.scanFor(key);
 399                 prev = array.at(index + 1);
 400                 array.put(index+1, value);
 401                 if ( array.at(index).isNil, {
 402                         array.put(index, key);
 403                         size = size + 1;
 404                         if (array.size < (size * 4), { this.grow });
 405                 });
 406                 ^prev
 407                 */
 408         }
 409
 410         includesKey { arg key;
 411                 ^this.at( key ).notNil;
 412         }
 413
 414         findKeyForValue { arg argValue;
 415                 this.keysValuesArrayDo(array, { arg key, val, i;
 416                         if (argValue === val, { ^key })
 417                 });
 418                 ^nil
 419         }
 420         scanFor { arg argKey;
 421                 ^array.atIdentityHashInPairs(argKey)
 422         }
 423
 424         doesNotUnderstand { arg selector ... args;
 425                 var func;
 426                 if (know) {
 427
 428                         func = this[selector];
 429                         if (func.notNil) {
 430                                 ^func.functionPerformList(\value, this, args);
 431                         };
 432
 433                         if (selector.isSetter) {
 434                                 selector = selector.asGetter;
 435                                 if(this.respondsTo(selector)) {
 436                                         warn(selector.asCompileString
 437                                                 + "exists a method name, so you can't use it as pseudo-method.")
 438                                 };
 439                                 ^this[selector] = args[0];
 440                         };
 441                         func = this[\forward];
 442                         if (func.notNil) {
 443                                 ^func.functionPerformList(\value, this, selector, args);
 444                         };
 445                         ^nil
 446                 };
 447                 ^this.superPerformList(\doesNotUnderstand, selector, args);
 448         }
 449
 450                 // Quant support.
 451                 // The Quant class assumes the quant/phase/offset scheduling model.
 452                 // If you want a different model, you can write a dictionary like so:
 453                 // (nextTimeOnGrid: { |self, clock| ... calculate absolute beat number here ... },
 454                 //      parameter: value, parameter: value, etc.)
 455                 // If you leave out the nextTimeOnGrid function, fallback to quant/phase/offset.
 456
 457         nextTimeOnGrid { |clock|
 458                 if(this[\nextTimeOnGrid].notNil) {
 459                         ^this[\nextTimeOnGrid].value(this, clock)
 460                 } {
 461                         ^clock.nextTimeOnGrid(this[\quant] ? 1, (this[\phase] ? 0) - (this[\offset] ? 0))
 462                 }
 463         }
 464         asQuant { ^this.copy }
 465         timingOffset { ^this[\timingOffset] }           // for synchWithQuant()
 466 }