SCClassLibrary/Common/Collections/SparseArray.sc

   1 Order : SequenceableCollection {
   2
   3         var <>array, <>indices;
   4
   5         *new { arg size = 8;
   6                 ^super.new.clear(size)
   7         }
   8
   9         *newFromIndices { arg array, indices;
  10                 ^super.newCopyArgs(array, indices)
  11         }
  12
  13         clear { arg size;
  14                 array = Array.new(size);
  15                 indices = Array.new(size);
  16         }
  17
  18         makeEmpty { this.clear }
  19
  20         copy {
  21                  ^this.class.newCopyArgs(array.copy, indices.copy)
  22         }
  23
  24         asArray { ^array.copy }
  25
  26         do { arg function;
  27                 indices.do { |index, i|
  28                         function.value(array.at(i), index, i)
  29                 };
  30         }
  31
  32         doRange { arg function, from = 0, to;
  33                 if(from <= indices.last) {
  34                         if(to.isNil) { to = indices.size - 1 } { to = min(to, this.lastIndex) };
  35                         for(this.slotFor(from), to) { |i|
  36                                 function.value(array.at(i), indices.at(i), i)
  37                         }
  38                 }
  39         }
  40
  41         keysValuesDo { arg function;
  42                 indices.do { |index, i|
  43                         function.value(index, array.at(i), i)
  44                 }
  45         }
  46
  47         size { ^indices.size }
  48
  49         lastIndex { ^indices.last }
  50
  51         // current write position
  52         pos {
  53                 var index = this.lastIndex;
  54                 ^if(index.isNil) { 0 } { index + 1 }
  55         }
  56
  57         add { arg obj;
  58                         array = array.add(obj);
  59                         indices = indices.add(this.pos);
  60         }
  61
  62         put { arg index, obj;
  63                 this.prPutSlot(this.nextSlotFor(index), index, obj)
  64         }
  65
  66         at { arg index;
  67                 var slot = this.slotFor(index);
  68                 ^if(slot.notNil) {
  69                         if(indices.at(slot) == index) {
  70                                 array.at(slot)
  71                         }
  72                 }
  73         }
  74
  75         removeAt { arg index, obj;
  76                 var nextSlot = this.nextSlotFor(index), slot;
  77                 ^if(nextSlot.notNil) {
  78                         slot = max(0, nextSlot - 1);
  79                         if(indices.at(slot) == index) { this.removeAtSlot(slot) }
  80                 }
  81         }
  82
  83         removeAtSlot { arg slot;
  84                 indices.removeAt(slot);
  85                 ^array.removeAt(slot)
  86         }
  87
  88         pop {
  89                 indices.pop;
  90                 ^array.pop
  91         }
  92
  93         collect { arg function;
  94                 ^this.copy.array_(array.collect(function));
  95         }
  96
  97         select { arg function;
  98                 var res = this.class.new;
  99                 this.indicesDo { |item, i|
 100                         if(function.value(item, i)) { res.put(i, item) }
 101                 }
 102                 ^res
 103         }
 104
 105         reject { arg function;
 106                 var res = this.class.new;
 107                 this.indicesDo { |item, i|
 108                         if(function.value(item, i).not) { res.put(i, item) }
 109                 }
 110                 ^res
 111         }
 112
 113         removeAllSuchThat { arg function;
 114                 var removedItems = this.class.new;
 115                 var copy = this.copy;
 116                 copy.indicesDo { | item, i |
 117                         if ( function.value(item, i) )
 118                         {
 119                                 this.remove(item);
 120                                 removedItems = removedItems.put(i, item);
 121                         }
 122                 };
 123                 ^removedItems
 124         }
 125
 126         selectInPlace { arg function;
 127                 indices.copy.do { |index, i|
 128                         if(function.value(array.at(i), index).not) {
 129                                 this.removeAtSlot(i)
 130                         }
 131                 }
 132         }
 133
 134         rejectInPlace { arg function;
 135                 indices.copy.do { |index, i|
 136                         if(function.value(array.at(i), index)) {
 137                                 this.removeAtSlot(i)
 138                         }
 139                 }
 140         }
 141
 142         indicesDo { arg function;
 143                 indices.do { |slot, i|
 144                         function.value(array.at(i), slot, i)
 145                 }
 146         }
 147
 148         // private implementation
 149
 150         resetIndices { arg step = 1, offset = 0;
 151                 indices = (offset, step .. indices.size - 1);
 152         }
 153
 154         nextSlotFor { arg index;
 155                 ^indices.indexOfGreaterThan(index) ?? { indices.size }
 156         }
 157
 158         slotFor { arg index;
 159                 ^max(0, this.nextSlotFor(index) - 1)
 160         }
 161
 162         prPutSlot { arg nextSlot, index, obj;
 163                 var slot = max(0, nextSlot - 1);
 164                 if(indices.at(slot) == index) {
 165                         array.put(slot, obj)
 166                 } {
 167                         array = array.insert(nextSlot, obj);
 168                         indices = indices.insert(nextSlot, index);
 169                 }
 170         }
 171
 172         choose {
 173                 ^array.choose
 174         }
 175 }
 176
 177
 178 SparseArray : Order {
 179
 180         var <>default, <>defaultSize;
 181
 182         *newClear { arg size, default;
 183                 ^super.new(size).defaultSize_(size).default_(default)
 184         }
 185
 186         *reduceArray { arg array, default;
 187                 var res = this.new.default_(default);
 188                 array.do { |item, i| res.putIfNotDefault(i, item) };
 189                 res.defaultSize = if(default.isNil) { res.size } { array.size };
 190                 ^res
 191         }
 192
 193         clear { arg size;
 194                 size = size.min(67108864 / 2); // For very large data we must assume sparse indices or we can't initialise the indices here
 195                 array = Array.new(size);
 196                 indices = Array.new(size);
 197         }
 198
 199         putIfNotDefault { arg i, item;
 200                 if(item != default) { this.put(i, item) }
 201         }
 202
 203         copy {
 204                  ^this.class.newCopyArgs(array.copy, indices.copy, default, defaultSize)
 205         }
 206
 207         asArray { ^this[_] ! this.size }
 208
 209         at { arg index;
 210                 ^super.at(index) ? default
 211         }
 212
 213         do { arg function;
 214                 if(this.isEmpty) { ^this };
 215                 this.size.do { |i|
 216                         function.value(this.at(i), i)
 217                 }
 218         }
 219
 220         size {
 221                 var last = super.lastIndex ? (-1);
 222                 ^if(defaultSize.isNil) {
 223                         last + 1
 224                 } {
 225                         max(last + 1, defaultSize)
 226                 }
 227         }
 228
 229         lastIndex {
 230                 var last = super.lastIndex ? 0;
 231                 ^if(defaultSize.isNil) {
 232                         last
 233                 } {
 234                         max(last, defaultSize)
 235                 }
 236         }
 237
 238         // current write position
 239         pos {
 240                 var index = super.lastIndex;
 241                 ^if(index.isNil) { 0 } { index + 1 }
 242         }
 243
 244         collect { arg function;
 245                 ^this.class.reduceArray(
 246                         this.asArray.collect(function),
 247                         default !? { function.value(default, 0) }               )
 248         }
 249
 250         select { arg function;
 251                 ^this.class.reduceArray(
 252                         this.asArray.select(function),
 253                         if(default.notNil and: { function.value(default, 0) }) { default }
 254                 )
 255         }
 256
 257         reject { arg function;
 258                 ^this.class.reduceArray(
 259                         this.asArray.reject(function),
 260                         if(default.notNil and: { function.value(default, 0).not }) { default }
 261                 )
 262         }
 263
 264         sum { | function |
 265                 var sum = 0;
 266                 ^if (function.isNil or: {function.numArgs < 2}) { // optimized version if no function, or if index is irrelevant
 267                         this.sparseSum
 268                 }{
 269                         this.do {|elem, i| sum = sum + function.value(elem, i); };
 270                         sum
 271                 }
 272         }
 273         // if index is irrelevant, assume that the result for all implicit elements is the same
 274         sparseSum { | function |
 275                 var sum = 0;
 276                 "sparseSum : inner array size is %".format(array.size).postln;
 277                 if (function.isNil) { // optimized version if no function
 278                         array.do { | elem | sum = sum + elem; };
 279                         sum = sum + (default * (this.size-array.size));
 280                 }{
 281                         array.do {|elem| sum = sum + function.value(elem); };
 282                         sum = sum + (function.value(default) * (this.size-array.size));
 283                 }
 284                 ^sum;
 285         }
 286
 287
 288
 289         // does not pass the index to each default item: faster than collect
 290         sparseCollect { arg function;
 291                 var res = super.collect(function);
 292                 default !? { res.default = function.value(default) };
 293                 ^res
 294         }
 295
 296         sparseSelect { arg function;
 297                 var res = super.select(function);
 298                 if(default.notNil and: { function.value(default, 0) }) { res.default = default }
 299                 ^res
 300         }
 301
 302         sparseReject { arg function;
 303                 var res = super.reject(function);
 304                 if(default.notNil and: { function.value(default, 0).not })
 305                         { res.default = default }
 306                 ^res
 307         }
 308
 309         sparseRemoveAt { arg index;
 310                 ^super.removeAt(index)
 311         }
 312
 313         sparseRemove { arg item;
 314                 var index = super.indexOf(item);
 315                 ^if(index.notNil) { super.removeAt(index) } { nil }
 316         }
 317
 318         removeAt { arg index;
 319                 //^this.notYetImplemented(thisMethod)
 320                 var res, slot = this.slotFor(index), size = indices.size;
 321                 if(index >= this.size) { ^nil };
 322
 323                 if(indices[slot] == index) {
 324                         res = this.removeAtSlot(slot);
 325                         slot =  slot - 1;
 326                 } {
 327                         if(size > 0) { res = default };
 328                         if(indices.first > index) { slot = -1 };
 329                 };
 330                 indices = indices[..slot] ++ (indices[slot+1..] - 1);
 331
 332                 if(defaultSize.notNil and: { defaultSize > 0 } and: { index < defaultSize }) {
 333                                 defaultSize = defaultSize - 1;
 334                 };
 335                 ^res
 336
 337         }
 338
 339         firstGap { arg from = 0, to;
 340                 if(indices.first == 0) { ^nil };
 341                 to = to ?? { indices.size };
 342                 (from..to).do { |i|
 343                         if(indices[i] != i) { ^i };
 344                 };
 345                 ^nil
 346         }
 347
 348         indexOf { arg item;
 349                 var slot = array.indexOf(item), res;
 350                 if(item == default) {
 351                                 res = this.firstGap(0, slot);
 352                                 if(res.notNil) { ^res };
 353                 };
 354                 ^if(slot.isNil) { nil } { indices[slot] }
 355         }
 356
 357         compress {
 358                 var ind, list, size = defaultSize ?? { this.size };
 359                 array.do { |item, i|
 360                         if(item != default) {
 361                                 list = list.add(item);
 362                                 ind = ind.add(indices.at(i))
 363                         };
 364                 };
 365                 ^this.class.newFromIndices(list, ind).default_(default).defaultSize_(size)
 366         }
 367
 368         pop {
 369                 ^if(defaultSize.notNil and: { defaultSize > indices.last }) {
 370                         defaultSize = defaultSize - 1;
 371                         default
 372                 } {
 373                         super.pop
 374                 }
 375         }
 376
 377
 378         ++ { arg coll;
 379                 var res = this.copy.sparseAddAll(coll);
 380                 if(defaultSize.notNil) { res.defaultSize_(this.size + coll.size) };
 381                 ^res
 382         }
 383
 384         sparseAddAll { arg coll;
 385                 var slot = this.size;
 386                 coll.do { |item, i|
 387                         if(item != default) { this.put(slot + i, item) }
 388                 };
 389         }
 390
 391         putSeries { arg first, second, last, value;
 392                 (first, second..last).do { |index|
 393                         this.put(index, value)
 394                 }
 395         }
 396         atSeries { arg first, second, last;
 397                 ^(first, second..last).collect { |index|
 398                         this.at(index)
 399                 }
 400         }
 401
 402         minItem { |function|
 403                 ^if(function.isNil or: {function.numArgs < 2}){
 404                         if(array.size == this.size){ // full up! default not used (weird)
 405                                 array.minItem(function)
 406                         }{
 407                                 array.minItem(function).min(if(function.isNil, default, function.value(default)))
 408                         }
 409                 }{
 410                         super.minItem(function);
 411                 }
 412         }
 413         maxItem { |function|
 414                 ^if(function.isNil or: {function.numArgs < 2}){
 415                         if(array.size == this.size){ // full up! default not used (weird)
 416                                 array.maxItem(function)
 417                         }{
 418                                 array.maxItem(function).max(if(function.isNil, default, function.value(default)))
 419                         }
 420                 }{
 421                         super.maxItem(function);
 422                 }
 423         }
 424
 425         // private implementation
 426
 427         prPutSlot { arg nextSlot, index, obj;
 428                 var slot = max(0, nextSlot - 1);
 429                 index = index.asInteger; // SparseArray supports only integer indices
 430                 if(indices.at(slot) == index) {
 431                         array.put(slot, obj)
 432                 } {
 433                         array = array.insert(nextSlot, obj);
 434                         indices = indices.insert(nextSlot, index);
 435                 }
 436         }
 437 }