src/core/array-extensible-sorted.slate

   1 collections define: #InternallyOrderedSequence &parents: {ExtensibleSequence}.
   2 "An extensible Sequence whose elements order is determined by a constraint
   3 rather than manipulable by a public protocol."
   4 "TODO: Factor out an immutable Sequence type."
   5
   6 sc@(InternallyOrderedSequence traits) at: index put: obj
   7 "TODO? Just call add:."
   8 [sc shouldNotImplement].
   9
  10 collections define: #SortedArray &parents: {ExtensibleArray. InternallyOrderedSequence}
  11   &slots: {#sortBlock -> #<= `er }.
  12 "A SortedArray is a Sequence which is Extensible, but which however maintains
  13 an order determined by a sorting block, therefore making indexed modification
  14 inappropriate."
  15
  16 c@(Collection traits) sort
  17 "TODO: this scales up poorly."
  18 [(SortedArray newSizeOf: c) `>> [addAll: c. ]].
  19
  20 c@(Collection traits) sortBy: block
  21 "TODO: this scales up poorly."
  22 [(SortedArray newSizeOf: c) `>> [sortBlock: block. addAll: c. ]].
  23
  24 sc@(SortedArray traits) sort [sc].
  25
  26 sc@(SortedArray traits) newSortedBy: block
  27 [sc new `>> [sortBlock: block. ]].
  28
  29 sc@(SortedArray traits) shouldArrange: x before: y
  30 [sc sortBlock apply*, x, y].
  31
  32 sc@(SortedArray traits) min
  33 [sc isEmpty ifFalse: [sc first]].
  34
  35 sc@(SortedArray traits) max
  36 [sc isEmpty ifFalse: [sc last]].
  37
  38 sc@(SortedArray traits) median
  39 [sc at: sc size + 1 // 2].
  40
  41 sc@(SortedArray traits) sortViolation
  42 [error: 'Sort order violation.'].
  43
  44 sc@(SortedArray traits) at: index insert: obj
  45 [
  46   (sc indexForInserting: obj) = index
  47     ifTrue: [resend]
  48     ifFalse: [sc sortViolation]
  49 ].
  50
  51 sc@(SortedArray traits) add: obj
  52 "Use the unsafe #at:insert: call to avoid a double #indexForInserting:
  53 calculation which would be expensive."
  54 [#at:insert: sendTo: {sc. sc indexForInserting: obj. obj}
  55              through: {ExtensibleArray. Nil. Nil}
  56 ].
  57
  58 sc@(SortedArray traits) addLast: obj
  59 [
  60   sc isEmpty
  61     ifTrue: [resend]
  62     ifFalse: [(sc shouldArrange: sc last before: obj)
  63                 ifTrue: [resend]
  64                 ifFalse: [sc sortViolation]]
  65 ].
  66
  67 sc@(SortedArray traits) addFirst: obj
  68 [
  69   sc isEmpty
  70     ifTrue: [resend]
  71     ifFalse: [(sc shouldArrange: obj before: sc first)
  72                 ifTrue: [resend]
  73                 ifFalse: [sc sortViolation]]
  74 ].
  75
  76 sc@(SortedArray traits) addAll: c
  77 "If the number of elements to add is great enough, add the elements unsafely,
  78 and then sort. Otherwise, add each in turn."
  79 [
  80   c size > (sc size // 3)
  81     ifTrue: [c do: [| :each | #addLast: sendTo: {sc. each}
  82                                         through: {ExtensibleArray. Nil}].
  83              sc reSort]
  84     ifFalse: [c do: #(sc add: _) `er].
  85   c
  86 ].
  87
  88 sc@(SortedArray traits) = sc2@(SortedArray traits)
  89 [
  90   sc sortBlock = sc2 sortBlock /\ [resend]
  91 ].
  92
  93 sc@(SortedArray traits) copy
  94 "Make a new SortedArray with the same sortBlock. Since we know the order
  95 will not change, use the minimally-checking addLast: method vice addAll:."
  96 [
  97   result ::= sc newSameSize.
  98   sc do: #(result addLast: _) `er.
  99   result
 100 ].
 101
 102 sc@(SortedArray traits) copyWith: obj
 103 "Non-destructively append, but don't use addLast: as ExtensibleArray does."
 104 [
 105   sc copy `>> [add: obj. ]
 106 ].
 107
 108 sc@(SortedArray traits) copyFrom: start to: end
 109 "Copy the range into a new SortedArray which keeps the same sortBlock."
 110 [| result |
 111   end < start \/ [sc isEmpty]
 112     ifTrue: [result := sc new]
 113     ifFalse:
 114       [result := sc new &capacity: end - start + 1.
 115        start to: end do: [| :index | result addLast: (sc at: index)]].
 116   result
 117 ].
 118
 119 sc@(SortedArray traits) reversed
 120 [resend `>> [sortBlock := sc sortBlock converse. ]].
 121
 122 sc@(SortedArray traits) collect: block
 123 "Override in order to return an ExtensibleArray instead of a SortedArray."
 124 [
 125   result ::= ExtensibleArray newSizeOf: sc.
 126   sc do: [| :each | result addLast: (block applyWith: each)].
 127   result
 128 ].
 129
 130 sc@(SortedArray traits) indexOf: obj startingAt: start ifAbsent: block
 131 "Subdivides the SortedArray into segments by comparing mid-elements with
 132 the object, narrowing until the object is found, or running the block if it
 133 isn't."
 134 [| index low high |
 135   low := sc firstIndex + start.
 136   high := sc lastIndex.
 137   [index := high + low // 2. low > high]
 138     whileFalse:
 139       [(sc contents at: index) = obj
 140          ifTrue: [^ index].
 141        (sc shouldArrange: (sc contents at: index) before: obj)
 142          ifTrue: [low := index + 1]
 143          ifFalse: [high := index - 1]].
 144   block do
 145 ].
 146
 147 sc@(SortedArray traits) includes: obj
 148 "Overridden because the sort order makes a faster implementation possible."
 149 [
 150   (sc indexOf: obj ifAbsent: [^ False]) isPositive
 151 ].
 152
 153 sc@(SortedArray traits) indexForInserting: obj
 154 "This returns the index where the object should be inserted to preserve sort
 155 order."
 156 [| index low high |
 157   low := sc firstIndex.
 158   high := sc lastIndex.
 159   [index := high + low // 2. low > high]
 160     whileFalse: [(sc shouldArrange: (sc contents at: index) before: obj)
 161       ifTrue: [low := index + 1] ifFalse: [high := index - 1]].
 162   low - sc firstIndex
 163 ].
 164
 165 sc@(SortedArray traits) replaceNextLargerWith: obj
 166 "Find the place at which obj would normally be inserted into the Sequence.
 167 If that place is already occupied by obj, just return Nil. If the place
 168 does not exist (i.e., it is off the end of the collection), add it to the
 169 end, otherwise replace the element at that point with obj. This returns the
 170 destination index in any normal case. This operation does preserve the
 171 sort order."
 172 [
 173   (index ::= sc indexForInserting: obj) > sc indexLast
 174     ifTrue: [sc addLast: obj. sc indexLast]
 175     ifFalse: [(sc at: index) = obj ifFalse:
 176       [sc contents at: index + sc firstIndex put: obj. index]]
 177 ].
 178
 179 sc@(SortedArray traits) reSort
 180 [
 181   sc contents sortFrom: sc firstIndex to: sc lastIndex by: sc sortBlock.
 182   sc
 183 ].