SCClassLibrary/Common/Collections/Set.sc

   1 Set : Collection {
   2         var <>array, <size=0;
   3
   4         *new { arg n=2; ^super.new.initSet(max(n,2)*2) }
   5         species { ^this.class }
   6         copy { ^this.shallowCopy.array_( array.copy ) }
   7         do { arg function;
   8                 var i=0;
   9                 if ( size > 0, {
  10                         array.do({ arg item;
  11                                 if (item.notNil, {
  12                                         function.value(item, i);
  13                                         i = i + 1;
  14                                 })
  15                         })
  16                 })
  17         }
  18
  19         clear { array.fill; size=0 }
  20         makeEmpty { this.clear; }
  21
  22         includes { arg item;
  23                 ^array.at(this.scanFor(item)).notNil;
  24         }
  25         findMatch { arg item;
  26                 // return an item that matches a given item
  27                 ^array.at(this.scanFor(item));
  28         }
  29         add { arg item;
  30                 var index;
  31                 if (item.isNil, { Error("A Set cannot contain nil.\n").throw; });
  32                 index = this.scanFor(item);
  33                 if ( array.at(index).isNil, { this.putCheck(index, item) });
  34         }
  35         remove { arg item;
  36                 var index = this.scanFor(item);
  37                 if ( array.at(index).notNil, {
  38                         array.put(index, nil);
  39                         size = size - 1;
  40                         this.fixCollisionsFrom(index);
  41                 });
  42         }
  43         choose {
  44                 var index, val;
  45                 if (size <= 0, { ^nil });
  46                 while({
  47                         index = array.size.rand;
  48                         (val = array.at(index)).isNil;
  49                 });
  50                 ^val
  51         }
  52         pop {
  53                 var index = 0, val;
  54                 while({
  55                         (index < array.size) and: { (val = array.at(index)).isNil }
  56                 },{
  57                         index = index + 1
  58                 });
  59                 if (index < array.size, {
  60                         this.remove(val);
  61                         ^val
  62                 }, {
  63                         ^nil
  64                 });
  65         }
  66 //      powerset {
  67 //              ^this.asArray.sort.powerset
  68 //      }
  69         unify {
  70                 var result = this.species.new;
  71                 this.do {|x| result.addAll(x) }
  72                 ^result
  73         }
  74         sect { arg that;
  75                 var result = this.species.new;
  76                 this.do({ arg item;
  77                         if (that.includes(item), {
  78                                 result.add(item);
  79                         });
  80                 });
  81                 ^result
  82         }
  83         union { arg that;
  84                 var result = this.species.new;
  85                 result.addAll(this);
  86                 result.addAll(that);
  87                 ^result
  88         }
  89         difference { arg that;
  90                 ^this.copy.removeAll(that);
  91         }
  92         symmetricDifference { arg that;
  93                 var result = this.species.new;
  94                 this.do({ arg item;
  95                         if (that.includes(item).not, {
  96                                 result.add(item);
  97                         });
  98                 });
  99                 that.do({ arg item;
 100                         if (this.includes(item).not, {
 101                                 result.add(item);
 102                         });
 103                 });
 104                 ^result;
 105         }
 106         isSubsetOf { | that | ^that.includesAll(this) }
 107
 108         & { arg that; ^this.sect(that) }
 109         | { arg that; ^this.union(that) }
 110         - { arg that; ^this.difference(that) }
 111         -- { arg that; ^this.symmetricDifference(that) }
 112
 113
 114         // PRIVATE IMPLEMENTATION
 115         initSet { arg n; array = Array.newClear(n); size = 0; }
 116         putCheck { arg index, item;
 117                 array.put(index, item);
 118                 size = size + 1;
 119                 this.fullCheck;
 120         }
 121         fullCheck {
 122                 if (array.size < (size * 2), { this.grow });
 123         }
 124         grow {
 125                 var oldElements = array;
 126                 array = Array.newClear(array.size * 2);
 127                 size = 0;
 128                 oldElements.do({ arg item;
 129                         if ( item.notNil, { this.noCheckAdd(item) })
 130                 });
 131         }
 132         noCheckAdd { arg item;
 133                 array.put(this.scanFor(item), item);
 134                 size = size + 1;
 135         }
 136         scanFor { arg obj;
 137                 var elem;
 138                 var start = obj.hash % array.size;
 139                 var end = array.size;
 140                 var i = start;
 141
 142                 while ({ i < end }, {
 143                         elem = array.at(i);
 144
 145                         if ( elem.isNil or: { elem == obj }, { ^i });
 146                         i = i + 1;
 147                 });
 148                 end = start - 1;
 149                 i = 0;
 150                 while ({ i <= end }, {
 151                         elem = array.at(i);
 152                         if ( elem.isNil or: { elem == obj }, { ^i });
 153                         i = i + 1;
 154                 });
 155                 error("There is no free space in this set!\n");
 156                 array.postln;
 157                 ^-1
 158         }
 159
 160         fixCollisionsFrom { arg index;
 161                 var newIndex, element;
 162                 var oldIndex = index;
 163                 var lastKeyIndex = array.size - 1;
 164
 165                 while ({
 166                         if (oldIndex == lastKeyIndex, { oldIndex = 0 }, { oldIndex = oldIndex + 1 });
 167                         (element = this.keyAt(oldIndex)).notNil
 168                 },{
 169                         newIndex = this.scanFor(element);
 170                         if ( oldIndex != newIndex, { array.swap(oldIndex, newIndex) })
 171                 })
 172         }
 173         keyAt { arg index; ^array.at(index) }
 174
 175         asSet { ^this }
 176 }
 177
 178 IdentitySet : Set {
 179         scanFor { arg argKey;
 180                 ^array.atIdentityHash(argKey)
 181         /*
 182                 var i, start, end, elem;
 183
 184                 start = obj.identityHash % array.size;
 185                 end = array.size;
 186                 i = start;
 187                 while ({ i < end }, {
 188                         elem = array.at(i);
 189                         if ( elem.isNil or: { elem === obj }, { ^i });
 190                         i = i + 1;
 191                 });
 192                 end = start - 1;
 193                 i = 0;
 194                 while ({ i < end }, {
 195                         elem = array.at(i);
 196                         if ( elem.isNil or: { elem === obj }, { ^i });
 197                         i = i + 1;
 198                 });
 199                 ^-1
 200         */
 201         }
 202 }
 203
 204
 205 OrderedIdentitySet : IdentitySet {
 206         var >items;
 207
 208         copy {
 209                 ^this.shallowCopy
 210                 .array_( array.copy )
 211                 .items_( items.copy )
 212         }
 213
 214         do { arg function;
 215                 items.do(function)
 216         }
 217
 218         clear {
 219                 super.clear;
 220                 items = nil;
 221         }
 222
 223         remove { arg item;
 224                 super.remove(item);
 225                 items.remove(item);
 226         }
 227         sort { arg func;
 228                 items.sort(func)
 229         }
 230
 231         // private
 232
 233         putCheck { arg index, item;
 234                 super.putCheck(index, item);
 235                 items = items.add(item);
 236         }
 237 }