src/core/array-extensible.slate

   1
   2 collections define: #ExtensibleArray &parents: {ArrayBacked} &slots: {#firstIndex -> 0. #lastIndex -> -1}.
   3 "An ExtensibleArray implemented by an Array with padding on both ends for
   4 the contents."
   5
   6 es@(ExtensibleArray traits) new &capacity: n
   7 [resend `>> [firstIndex := 0. lastIndex := -1. ]].
   8
   9 es@(ExtensibleArray traits) size
  10 [
  11   es lastIndex - es firstIndex + 1
  12 ].
  13
  14 es@(ExtensibleArray traits) at: index
  15 [
  16   (es includesKey: index)
  17     ifTrue: [es contents at: es firstIndex + index]
  18     ifFalse: [index keyNotFoundOn: es]
  19 ].
  20
  21 es@(ExtensibleArray traits) at: index put: value
  22 [
  23   (es includesKey: index)
  24     ifTrue: [es contents at: es firstIndex + index put: value]
  25     ifFalse: [index keyNotFoundOn: es]
  26 ].
  27
  28 es@(ExtensibleArray traits) clear
  29 "Resets to the values for being empty. lastIndex is -1 to coordinate with the
  30 size method and addLast:."
  31 [
  32   resend.
  33   es firstIndex := 0.
  34   es lastIndex := -1.
  35   es
  36 ].
  37
  38 es@(ExtensibleArray traits) copyReplaceFrom: start to: end with: c
  39 "Performs an insert or append as necessary if the replacing collection doesn't
  40 fit in the bounds. eg start < 0 prepends, start > size appends."
  41 [| delta startIndex endIndex |
  42   delta := 0.
  43   ess ::= es size.
  44   cs ::= c size.
  45   start < 0
  46     ifTrue: [startIndex := endIndex := 0]
  47     ifFalse:
  48       [endIndex := end.
  49        (startIndex := start) > ess
  50          ifTrue: [startIndex := endIndex := size + 1]
  51          ifFalse: [endIndex < (startIndex - 1) \/ [endIndex > (ess - 1)]
  52                      ifTrue: [^ Nil].
  53                    delta := endIndex - startIndex + 1]].
  54   result ::= es new &capacity: ess + cs - delta.
  55   0 below: startIndex do: [| :index | result add: (es at: index)].
  56   0 below: cs do: [| :index | result add: (c at: index)].
  57   endIndex + 1 below: ess do: [| :index | result add: (es at: index)].
  58   result
  59 ].
  60
  61 es@(ExtensibleArray traits) growFirst &by: growBy
  62 "Provide a larger array and map the contents in to yield more growth area at
  63 the beginning. The growth factor is 2."
  64 [
  65   defaultGrowBy ::= es growSize - es capacity.
  66   growBy := (growBy
  67     ifNil: [defaultGrowBy]
  68     ifNotNil: [growBy max: defaultGrowBy]).
  69   newContents ::= es lastIndex + growBy >= (es capacity - 1)
  70     ifTrue: [es contents new &capacity: es capacity + growBy]
  71     ifFalse: [es contents].
  72   offset ::= newContents size - es lastIndex - 1.
  73   es lastIndex downTo: es firstIndex do:
  74     [| :index | newContents at: index + offset put: (es contents at: index)].
  75   es firstIndex := es firstIndex + offset.
  76   es lastIndex := es lastIndex + offset.
  77   es contents := newContents
  78 ].
  79
  80 es@(ExtensibleArray traits) grow
  81 "This is the default for growing since add: addLast:s."
  82 [es growLast].
  83
  84 es@(ExtensibleArray traits) growLast &by: growBy
  85 "Provide a larger array and map the contents in to yield more growth area at
  86 the end. The growth factor is 2."
  87 [
  88   defaultGrowBy ::= es growSize - es capacity.
  89   growBy := (growBy
  90     ifNil: [defaultGrowBy]
  91     ifNotNil: [growBy max: defaultGrowBy]).
  92   newContents ::= es firstIndex - growBy <= 0
  93     ifTrue: [es contents new &capacity: es capacity + growBy]
  94     ifFalse: [es contents].
  95   es firstIndex upTo: es lastIndex do:
  96     [| :index |
  97      newContents
  98        at: index - es firstIndex
  99        put: (es contents at: index)].
 100   es lastIndex -= es firstIndex.
 101   es firstIndex := 0.
 102   es contents := newContents
 103 ].
 104
 105 es@(ExtensibleArray traits) addFirst: obj
 106 [
 107   (firstIndex ::= es firstIndex) = 0 ifTrue: [es growFirst].
 108   es firstIndex -= 1.
 109   es contents at: es firstIndex put: obj.
 110   obj
 111 ].
 112
 113 es@(ExtensibleArray traits) addLast: obj
 114 [
 115   es lastIndex + 1 < es capacity ifFalse: [es growLast].
 116   es lastIndex += 1.
 117   es contents at: es lastIndex put: obj.
 118   obj
 119 ].
 120
 121 es@(ExtensibleArray traits) insert: obj after: member
 122 [
 123   es add: obj after: member
 124 ].
 125
 126 es@(ExtensibleArray traits) add: obj after: member
 127 [
 128   (es find: member) ifNotNilDo:
 129     [| :index | es at: index + 1 insert: obj. obj]
 130 ].
 131
 132 es@(ExtensibleArray traits) insert: obj before: member
 133 [
 134   es add: obj before: member
 135 ].
 136
 137 es@(ExtensibleArray traits) add: obj before: member
 138 [
 139   (es find: member) ifNotNilDo:
 140     [| :index | es at: index insert: obj. obj]
 141 ].
 142
 143 es@(ExtensibleArray traits) remove: obj ifAbsent: block
 144 [| index |
 145   index := es firstIndex.
 146   [index <= es lastIndex] whileTrue:
 147     [obj = (es contents at: index)
 148       ifTrue: [es contents replaceFrom: index to: es lastIndex - 1
 149           with: es contents startingAt: index + 1.
 150           es contents at: es lastIndex put: es contents defaultElement.
 151           es lastIndex -= 1.
 152           ^ obj]
 153       ifFalse: [index += 1]].
 154   block do
 155 ].
 156
 157 es@(ExtensibleArray traits) removeAllSuchThat: test
 158 "Remove each element of the receiver for which aBlock evaluates to true.
 159 The method in ExtensibleCollection is O(N^2); this is O(N)."
 160 [| n |
 161   n := es firstIndex.
 162   es firstIndex to: es lastIndex do:
 163    [| :index |
 164     (test applyWith: (es contents at: index)) ifFalse:
 165       [es contents at: n put: (es contents at: index).
 166        n += 1]].
 167   n to: es lastIndex do: [| :index | es contents at: index put: Nil].
 168   es lastIndex := n - 1.
 169   es
 170 ].
 171
 172 es@(ExtensibleArray traits) at: index remove: n
 173 "Remove the next N objects currently starting from the given index, sliding
 174 items from the right over to fill in the places."
 175 [
 176   localStart ::= index + es firstIndex.
 177   es contents replaceFrom: localStart to: es lastIndex - n
 178       with: es contents startingAt: localStart + n.
 179   es lastIndex -= n.
 180   es
 181 ].
 182
 183 es@(ExtensibleArray traits) removeAt: index
 184 "Remove the object currently at the given index, sliding items from the right
 185 over to fill in the place."
 186 [
 187   removed ::= es at: index.
 188   localIndex ::= index + es firstIndex.
 189   es contents replaceFrom: localIndex to: es lastIndex - 1
 190       with: es contents startingAt: localIndex + 1.
 191   es contents at: es lastIndex put: es contents defaultElement.
 192   es lastIndex -= 1.
 193   removed
 194 ].
 195
 196 es@(ExtensibleArray traits) removeFirst
 197 [
 198   es emptyCheck.
 199   firstObj ::= es contents at: es firstIndex.
 200   es contents at: es firstIndex put: es contents defaultElement.
 201   es firstIndex += 1.
 202   firstObj
 203 ].
 204
 205 es@(ExtensibleArray traits) removeLast
 206 [
 207   es emptyCheck.
 208   lastObj ::= es contents at: es lastIndex.
 209   es contents at: es lastIndex put: es contents defaultElement.
 210   es lastIndex -= 1.
 211   lastObj
 212 ].
 213
 214 es@(ExtensibleArray traits) removeFirst: n
 215 [
 216   n > es size ifTrue: [n := es size].
 217   result ::= es contents new &capacity: n.
 218   es firstIndex below: es firstIndex + n do:
 219     [| :i | result at: i put: (es contents at: i).
 220      es contents at: i put: es contents defaultElement].
 221   es firstIndex += n.
 222   result
 223 ].
 224
 225 es@(ExtensibleArray traits) removeLast: n
 226 [
 227   n > es size ifTrue: [n := es size].
 228   result ::= es contents new &capacity: n.
 229   es lastIndex above: (es lastIndex -= n)
 230     do: [| :i | result at: (n -= 1) put: (es contents at: i).
 231          es contents at: i put: es contents defaultElement].
 232   result
 233 ].
 234
 235 c@(Collection traits) collect: block into: es@(ExtensibleArray traits)
 236 "Override to use the specific implementation."
 237 [
 238   c do: [| :each | es addLast: (block applyWith: each)].
 239   es
 240 ].
 241
 242 es@(ExtensibleArray traits) collect: block from: start to: end
 243 "Override to use the specific implementation."
 244 [| result |
 245   start < 0 \/ [end >= es size]
 246     ifTrue: [result := es new]
 247     ifFalse:
 248       [result := es new &capacity: end - start + 1.
 249        es firstIndex + start to: es firstIndex + end do:
 250          [| :index | result addLast: (block applyWith: (es contents at: index))]].
 251   result
 252 ].
 253
 254 es@(ExtensibleArray traits) do: block
 255 [| index |
 256   index := es firstIndex.
 257   limit ::= es lastIndex.
 258   [index <= limit] whileTrue:
 259     [block applyWith: (es contents at: index).
 260      index += 1].
 261   es
 262 ].
 263
 264 es@(ExtensibleArray traits) reverseDo: block
 265 [| index |
 266   index := es lastIndex.
 267   limit ::= es firstIndex.
 268   [index >= limit] whileTrue:
 269     [block applyWith: (es contents at: index).
 270      index -= 1].
 271   es
 272 ].
 273
 274 c@(Collection traits) select: block into: es@(ExtensibleArray traits)
 275 [
 276   c do: [| :each | (block applyWith: each) ifTrue: [es addLast: each]].
 277   es
 278 ].
 279
 280 c@(Sequence traits) collectWithIndex: binBlock into: es@(ExtensibleArray traits)
 281 "Override to use addLast: vice at:put:."
 282 [
 283   c doWithIndex:
 284     [| :each :index | es addLast: (block applyWith: each with: index)].
 285   es
 286 ].
 287
 288 es@(ExtensibleArray traits) find: obj
 289 [| index |
 290   index := es firstIndex.
 291   limit ::= es lastIndex.
 292   [index <= limit] whileTrue:
 293     [(es contents at: index) = obj ifTrue: [^ index].
 294      index += 1].
 295   Nil
 296 ].
 297
 298 es@(ExtensibleArray traits) makeGapAt: index &size: size
 299 "Make a gap at the requested index, and return the start offset of
 300 the created gap in the contents array."
 301 [
 302   size `defaultsTo: 1.
 303   `conditions: (
 304     [size isNegative]
 305       -> [error: 'Gap size must be bigger then 0'].
 306     [index isNegative \/ [index > es size]]
 307       -> [index keyNotFoundOn: es].
 308     [index isZero]
 309       -> [es firstIndex - size < 0 ifTrue: [es growFirst &by: size].
 310           es firstIndex := es firstIndex - size]
 311   ) otherwise:
 312     [es lastIndex + size >= es capacity ifTrue: [es growLast &by: size].
 313      contentsIndex ::= es firstIndex + index.
 314      index = es size ifFalse:
 315        [es contents
 316           replaceFrom: contentsIndex + size
 317           to: es lastIndex + size
 318           with: es contents
 319           startingAt: contentsIndex].
 320      es lastIndex += size.
 321      contentsIndex]
 322 ].
 323
 324 es@(ExtensibleArray traits) at: index insert: obj
 325 [
 326   es contents at: (es makeGapAt: index) put: obj
 327 ].
 328
 329 es@(ExtensibleArray traits) at: index insertAll: col
 330 [
 331   startOffset ::= es makeGapAt: index &size: col size.
 332   col doWithIndex: [| :each :index | es contents at: startOffset + index put: each].
 333   es
 334 ].
 335
 336 es@(ExtensibleArray traits) move: obj to: index
 337 "Re-position the object so that it has the given index, and slide up/down other
 338 objects as needed."
 339 [
 340   (src ::= es find: obj)
 341     ifNil: [obj elementNotFoundOn: es].
 342   (tgt ::= index + es startIndex) = src ifFalse:
 343     [src > tgt
 344        ifTrue:
 345          [es contents
 346             replaceFrom: tgt + 1
 347             to: src
 348             with: es contents
 349             startingAt: tgt]
 350        ifFalse:
 351          [es contents
 352             replaceFrom: src
 353             to: es contents lastIndex
 354             with: es contents
 355             startingAt: src + 1].
 356      es contents at: tgt put: obj].
 357   es
 358 ].