SCClassLibrary/Common/Collections/SortedList.sc

   1 SortedList : List {
   2         var <>function;
   3
   4         *new { arg size = 8, function;
   5                 function = function ? { arg a, b; a < b }
   6                 ^super.new(size).function_(function)
   7         }
   8         add { arg item;
   9                 var nextIndex;
  10
  11                 if ( this.isEmpty, {
  12                         ^super.add(item);
  13                 });
  14                 nextIndex = this.indexForInserting(item);
  15                 this.insert(nextIndex, item);
  16         }
  17         addAll { arg aCollection;
  18                 aCollection = aCollection.asCollection;
  19                 if ( aCollection.size > (this.size div: 3), {
  20                         // Faster to add the new elements and resort
  21                         aCollection.do({ arg each; super.add(each) });
  22                         this.sort
  23                 },{     // Faster to add the elements individually in their proper places
  24                         aCollection.do({ arg each; this.add(each) });
  25                 });
  26         }
  27
  28         copyRange { arg start, end; ^this.class.newUsing(array.copyRange(start, end)).function_(function) }
  29         copySeries { arg first, second, last;
  30                 ^this.class.newUsing(array.copySeries(first, second, last)).function_(function)
  31         }
  32
  33         // PRIVATE
  34         indexForInserting { arg newObject;
  35                 var index;
  36                 var low = 0;
  37                 var high = this.size-1;
  38                 while ({
  39                         index = high + low div: 2;
  40                         low <= high;
  41                 },{
  42                         if (function.value(array.at(index), newObject), {
  43                                 low = index + 1;
  44                         },{
  45                                 high = index - 1;
  46                         });
  47                 });
  48                 ^low
  49         }
  50
  51         sort { this.sortRange(0, array.size - 1) }
  52
  53         sortRange { arg i, j;
  54                 //Sort elements i through j of this to be nondescending according to
  55                 // function.
  56
  57                 var di, dij, dj, tt, ij, k, l, n;
  58                 // The prefix d means the data at that index.
  59                 if ((n = j + 1  - i) <= 1, { ^this });  // Nothing to sort.
  60
  61                 //Sort di,dj.
  62                 di = array.at(i);
  63                 dj = array.at(j);
  64                 if (function.value(di, dj).not, { // i.e., should di precede dj?
  65                         array.swap(i,j);
  66                                  tt = di;
  67                                  di = dj;
  68                                  dj = tt;
  69                 });
  70                 if ( n > 2, { // More than two elements.
  71                         ij = (i + j) div: 2;  // ij is the midpoint of i and j.
  72                         dij = array.at(ij);  // Sort di,dij,dj.  Make dij be their median.
  73                         if (function.value(di,  dij), {  // i.e. should di precede dij?
  74                                 if (function.value(dij, dj).not, {  // i.e., should dij precede dj?
  75                                         array.swap(j, ij);
  76                                         dij = dj;
  77                                 })
  78                         },{ // i.e. di should come after dij"
  79                                 array.swap(i, ij);
  80                                 dij = di;
  81                         });
  82                         if ( n > 3, { // More than three elements.
  83                                 // Find k>i and l<j such that dk,dij,dl are in reverse order.
  84                                 // Swap k and l.  Repeat this procedure until k and l pass each other.
  85                                 k = i;
  86                                 l = j;
  87                                 while ({
  88                                         while ({
  89                                                 l = l - 1;
  90                                                 k <= l and: { function.value(dij, array.at(l)) }
  91                                         }); // i.e. while dl succeeds dij
  92                                         while ({
  93                                                 k = k + 1;
  94                                                 k <= l and: { function.value(array.at(k), dij) };
  95                                         }); // i.e. while dij succeeds dk
  96                                         k <= l
  97                                 },{
  98                                         array.swap(k, l);
  99                                 });
 100                 // Now l<k (either 1 or 2 less), and di through dl are all less than or equal to dk
 101                 // through dj.  Sort those two segments.
 102                                 this.sortRange(i, l);
 103                                 this.sortRange(k, j);
 104                         });
 105                 });
 106         }
 107 }