src/core/sequence-extensible.slate

   1 collections define: #ExtensibleSequence
   2             &parents: {ExtensibleCollection. Sequence}.
   3 "A Sequence which is Extensible. This is abstract, with several possible
   4 implementations. A particular feature of this type is that add: maps to
   5 addLast:, adding at the end."
   6
   7 es@(ExtensibleSequence traits) copyFrom: start to: end
   8 [| result |
   9   end < start \/ [es isEmpty]
  10     ifTrue: [result := es new]
  11     ifFalse:
  12       [result := es new &capacity: end + 1 - start.
  13        start to: end do: [| :index | result addLast: (es at: index)]].
  14   result
  15 ].
  16
  17 es@(ExtensibleSequence traits) copyWith: obj
  18 "Non-destructively append."
  19 [es copy `>> [addLast: obj. ]].
  20
  21 es@(ExtensibleSequence traits) reversed
  22 [
  23   result ::= es newSameSize.
  24   es reverseDo: [| :obj |
  25     result addLast: obj].
  26   result
  27 ].
  28
  29 es@(ExtensibleSequence traits) growSize
  30 "The new capacity for a call to a grow- method."
  31 [es capacity * 2 max: 8].
  32
  33 es@(ExtensibleSequence traits) grow
  34 [es growTo: es growSize].
  35
  36 es@(ExtensibleSequence traits) growTo: n
  37 [overrideThis].
  38
  39 es@(ExtensibleSequence traits) growBy: n
  40 [es growTo: es capacity + n].
  41
  42 es@(ExtensibleSequence traits) capacity
  43 [overrideThis].
  44
  45 es@(ExtensibleSequence traits) addFirst: obj
  46 "Add the given object to the beginning of the Sequence."
  47 [overrideThis].
  48
  49 es@(ExtensibleSequence traits) addLast: obj
  50 "Add the given object to the end of the Sequence."
  51 [overrideThis].
  52
  53 es@(ExtensibleSequence traits) add: obj
  54 "A particular feature of this type is that add: maps to addLast:, adding at
  55 the end."
  56 [es addLast: obj].
  57
  58 es@(ExtensibleSequence traits) append: obj
  59 "Append the object to the Sequence; aliases addLast:."
  60 [es addLast: obj].
  61
  62 es@(ExtensibleSequence traits) prepend: obj
  63 "Prepend the object to the Sequence; aliases addFirst:."
  64 [es addFirst: obj].
  65
  66 es@(ExtensibleSequence traits) addAll: c
  67 [es addAllLast: c].
  68
  69 es@(ExtensibleSequence traits) addAllFirst: seq
  70 [
  71   seq reverseDo: #(es addFirst: _) `er.
  72   seq
  73 ].
  74
  75 es@(ExtensibleSequence traits) addAllLast: seq
  76 [
  77   seq do: #(es addLast: _) `er.
  78   seq
  79 ].
  80
  81 es@(ExtensibleSequence traits) prependAll: seq
  82 "Prepend all of the objects to the Sequence; aliases addAllFirst:."
  83 [es addAllFirst: seq].
  84
  85 es@(ExtensibleSequence traits) appendAll: seq
  86 "Append all of the objects to the Sequence; aliases addAllLast:."
  87 [es addAllLast: seq].
  88
  89 es@(ExtensibleSequence traits) collect: block
  90 "Override to use addLast: vice at:put:."
  91 [
  92   result ::= es newSameSize.
  93   es do: [| :each | result addLast: (block applyWith: each)].
  94   result
  95 ].
  96
  97 es@(ExtensibleSequence traits) collect: block from: start to: end
  98 "Override to use addLast: vice at:put:."
  99 [| result |
 100   start < 0 \/ [end >= es size]
 101     ifTrue: [result := es new]
 102     ifFalse:
 103       [result := es new &capacity: end - start + 1.
 104        start to: end do:
 105          [| :index | result addLast: (block applyWith: (es at: index))]].
 106   result
 107 ].
 108
 109 es@(ExtensibleSequence traits) with: seq collect: binBlock
 110 [
 111   result ::= es new &capacity: (es size min: seq size).
 112   0 below: result capacity do: [| :index |
 113     result addLast: (binBlock applyWith: (es at: index) with: (seq at: index))].
 114   result
 115 ].
 116
 117 es@(ExtensibleSequence traits) removeFirst
 118 "Removes and answers the first element."
 119 [overrideThis].
 120
 121 es@(ExtensibleSequence traits) removeLast
 122 "Removes and answers the last element."
 123 [overrideThis].
 124
 125 es@(ExtensibleSequence traits) remove
 126 "Removes from the front by default, providing LIFO semantics in combination
 127 with add:->addLast:."
 128 [es removeFirst].
 129
 130 es@(ExtensibleSequence traits) removeFirst: n
 131 [
 132   n > es size ifTrue: [n := es size].
 133   result ::= es new &capacity: n.
 134   n timesRepeat: [result addLast: n removeFirst].
 135   result
 136 ].
 137
 138 es@(ExtensibleSequence traits) removeLast: n
 139 [
 140   n > es size ifTrue: [n := es size].
 141   result ::= es new &capacity: n.
 142   n timesRepeat: [result addFirst: es removeLast].
 143   result
 144 ].
 145
 146 collections define: #ArrayBacked &parents: {ExtensibleSequence} &slots: {#contents -> {}}.
 147 "This merely provides an area for common methods for various implementation
 148 extensions of ExtensibleSequence which use a contents Array to store their
 149 elements."
 150
 151 es@(ArrayBacked traits) clear
 152 [es contents clear. ].
 153
 154 es@(ArrayBacked traits) copy
 155 [es cloneSettingSlots: #{#contents} to: {es contents copy}].
 156
 157 es@(ArrayBacked traits) new &capacity: n
 158 [es cloneSettingSlots: #{#contents}
 159     to: {es contents new &capacity: (n ifNil: [es contents size max: 4])}].
 160
 161 es@(ArrayBacked traits) arrayType
 162 "The underlying implementation prototype."
 163 [es contents arrayType].
 164
 165 es@(ArrayBacked traits) elementType
 166 "The underlying implementation element type accepted."
 167 [es contents elementType].
 168
 169 es@(ArrayBacked traits) capacity
 170 [es contents size].
 171
 172 es@(ArrayBacked traits) growTo: n
 173 [
 174   result ::= es contents new &capacity: n.
 175   result replaceFrom: 0 to: es size - 1 with: es contents.
 176   es contents := result.
 177   es
 178 ].
 179
 180 s@(Sequence traits) as: es@(ArrayBacked traits)
 181 "Allows dynamically carrying forward the arrayType into the new Sequence."
 182 [
 183   es new `>> [contents := s arrayType newSizeOf: s.
 184               addAll: s. ]
 185 ].
 186
 187 es@(ArrayBacked traits) convertContentsTo: s
 188 [
 189   es contents := es contents as: s. es
 190 ].
 191
 192 collections define: #ExtensibleArray &parents: {ArrayBacked} &slots: {#firstIndex -> 0. #lastIndex -> -1}.
 193 "An ExtensibleArray implemented by an Array with padding on both ends for
 194 the contents."
 195
 196 es@(ExtensibleArray traits) new &capacity: n
 197 [resend `>> [firstIndex := 0. lastIndex := -1. ]].
 198
 199 es@(ExtensibleArray traits) size
 200 [
 201   es lastIndex - es firstIndex + 1
 202 ].
 203
 204 es@(ExtensibleArray traits) at: index
 205 [
 206   (es includesKey: index)
 207     ifTrue: [es contents at: es firstIndex + index]
 208     ifFalse: [index keyNotFoundOn: es]
 209 ].
 210
 211 es@(ExtensibleArray traits) at: index put: value
 212 [
 213   (es includesKey: index)
 214     ifTrue: [es contents at: es firstIndex + index put: value]
 215     ifFalse: [index keyNotFoundOn: es]
 216 ].
 217
 218 es@(ExtensibleArray traits) clear
 219 "Resets to the values for being empty. lastIndex is -1 to coordinate with the
 220 size method and addLast:."
 221 [
 222   resend.
 223   es firstIndex := 0.
 224   es lastIndex := -1.
 225   es
 226 ].
 227
 228 es@(ExtensibleArray traits) copyReplaceFrom: start to: end with: c
 229 "Performs an insert or append as necessary if the replacing collection doesn't
 230 fit in the bounds. eg start < 0 prepends, start > size appends."
 231 [| delta startIndex endIndex |
 232   delta := 0.
 233   ess ::= es size.
 234   cs ::= c size.
 235   start < 0
 236     ifTrue: [startIndex := endIndex := 0]
 237     ifFalse:
 238       [endIndex := end.
 239        (startIndex := start) > ess
 240          ifTrue: [startIndex := endIndex := size + 1]
 241          ifFalse: [endIndex < (startIndex - 1) \/ [endIndex > (ess - 1)]
 242                      ifTrue: [^ Nil].
 243                    delta := endIndex - startIndex + 1]].
 244   result ::= es new &capacity: ess + cs - delta.
 245   0 below: startIndex do: [| :index | result add: (es at: index)].
 246   0 below: cs do: [| :index | result add: (c at: index)].
 247   endIndex + 1 below: ess do: [| :index | result add: (es at: index)].
 248   result
 249 ].
 250
 251 es@(ExtensibleArray traits) growFirst &by: growBy
 252 "Provide a larger array and map the contents in to yield more growth area at
 253 the beginning. The growth factor is 2."
 254 [
 255   defaultGrowBy ::= es growSize - es capacity.
 256   growBy := (growBy
 257     ifNil: [defaultGrowBy]
 258     ifNotNil: [growBy max: defaultGrowBy]).
 259   newContents ::= es lastIndex + growBy >= (es capacity - 1)
 260     ifTrue: [es contents new &capacity: es capacity + growBy]
 261     ifFalse: [es contents].
 262   offset ::= newContents size - es lastIndex - 1.
 263   es lastIndex downTo: es firstIndex do:
 264     [| :index | newContents at: index + offset put: (es contents at: index)].
 265   es firstIndex := es firstIndex + offset.
 266   es lastIndex := es lastIndex + offset.
 267   es contents := newContents
 268 ].
 269
 270 es@(ExtensibleArray traits) grow
 271 "This is the default for growing since add: addLast:s."
 272 [es growLast].
 273
 274 es@(ExtensibleArray traits) growLast &by: growBy
 275 "Provide a larger array and map the contents in to yield more growth area at
 276 the end. The growth factor is 2."
 277 [
 278   defaultGrowBy ::= es growSize - es capacity.
 279   growBy := (growBy
 280     ifNil: [defaultGrowBy]
 281     ifNotNil: [growBy max: defaultGrowBy]).
 282   newContents ::= es firstIndex - growBy <= 0
 283     ifTrue: [es contents new &capacity: es capacity + growBy]
 284     ifFalse: [es contents].
 285   es firstIndex upTo: es lastIndex do:
 286     [| :index |
 287      newContents
 288        at: index - es firstIndex
 289        put: (es contents at: index)].
 290   es lastIndex -= es firstIndex.
 291   es firstIndex := 0.
 292   es contents := newContents
 293 ].
 294
 295 es@(ExtensibleArray traits) addFirst: obj
 296 [
 297   (firstIndex ::= es firstIndex) = 0 ifTrue: [es growFirst].
 298   es firstIndex -= 1.
 299   es contents at: es firstIndex put: obj.
 300   obj
 301 ].
 302
 303 es@(ExtensibleArray traits) addLast: obj
 304 [
 305   es lastIndex + 1 < es capacity ifFalse: [es growLast].
 306   es lastIndex += 1.
 307   es contents at: es lastIndex put: obj.
 308   obj
 309 ].
 310
 311 es@(ExtensibleArray traits) insert: obj after: member
 312 [
 313   es add: obj after: member
 314 ].
 315
 316 es@(ExtensibleArray traits) add: obj after: member
 317 [
 318   (es find: member) ifNotNilDo:
 319     [| :index | es at: index + 1 insert: obj. obj]
 320 ].
 321
 322 es@(ExtensibleArray traits) insert: obj before: member
 323 [
 324   es add: obj before: member
 325 ].
 326
 327 es@(ExtensibleArray traits) add: obj before: member
 328 [
 329   (es find: member) ifNotNilDo:
 330     [| :index | es at: index insert: obj. obj]
 331 ].
 332
 333 es@(ExtensibleArray traits) remove: obj ifAbsent: block
 334 [| index |
 335   index := es firstIndex.
 336   [index <= es lastIndex] whileTrue:
 337     [obj = (es contents at: index)
 338       ifTrue: [es contents replaceFrom: index to: es lastIndex - 1
 339           with: es contents startingAt: index + 1.
 340           es contents at: es lastIndex put: es contents defaultElement.
 341           es lastIndex -= 1.
 342           ^ obj]
 343       ifFalse: [index += 1]].
 344   block do
 345 ].
 346
 347 es@(ExtensibleArray traits) removeAllSuchThat: test
 348 "Remove each element of the receiver for which aBlock evaluates to true.
 349 The method in ExtensibleCollection is O(N^2); this is O(N)."
 350 [| n |
 351   n := es firstIndex.
 352   es firstIndex to: es lastIndex do:
 353    [| :index |
 354     (test applyWith: (es contents at: index)) ifFalse:
 355       [es contents at: n put: (es contents at: index).
 356        n += 1]].
 357   n to: es lastIndex do: [| :index | es contents at: index put: Nil].
 358   es lastIndex := n - 1.
 359   es
 360 ].
 361
 362 es@(ExtensibleArray traits) at: index remove: n
 363 "Remove the next N objects currently starting from the given index, sliding
 364 items from the right over to fill in the places."
 365 [
 366   localStart ::= index + es firstIndex.
 367   es contents replaceFrom: localStart to: es lastIndex - n
 368       with: es contents startingAt: localStart + n.
 369   es lastIndex -= n.
 370   es
 371 ].
 372
 373 es@(ExtensibleArray traits) removeAt: index
 374 "Remove the object currently at the given index, sliding items from the right
 375 over to fill in the place."
 376 [
 377   removed ::= es at: index.
 378   localIndex ::= index + es firstIndex.
 379   es contents replaceFrom: localIndex to: es lastIndex - 1
 380       with: es contents startingAt: localIndex + 1.
 381   es contents at: es lastIndex put: es contents defaultElement.
 382   es lastIndex -= 1.
 383   removed
 384 ].
 385
 386 es@(ExtensibleArray traits) removeFirst
 387 [
 388   es emptyCheck.
 389   firstObj ::= es contents at: es firstIndex.
 390   es contents at: es firstIndex put: es contents defaultElement.
 391   es firstIndex += 1.
 392   firstObj
 393 ].
 394
 395 es@(ExtensibleArray traits) removeLast
 396 [
 397   es emptyCheck.
 398   lastObj ::= es contents at: es lastIndex.
 399   es contents at: es lastIndex put: es contents defaultElement.
 400   es lastIndex -= 1.
 401   lastObj
 402 ].
 403
 404 es@(ExtensibleArray traits) removeFirst: n
 405 [
 406   n > es size ifTrue: [n := es size].
 407   result ::= es contents new &capacity: n.
 408   es firstIndex below: es firstIndex + n do:
 409     [| :i | result at: i put: (es contents at: i).
 410      es contents at: i put: es contents defaultElement].
 411   es firstIndex += n.
 412   result
 413 ].
 414
 415 es@(ExtensibleArray traits) removeLast: n
 416 [
 417   n > es size ifTrue: [n := es size].
 418   result ::= es contents new &capacity: n.
 419   es lastIndex above: (es lastIndex -= n)
 420     do: [| :i | result at: (n -= 1) put: (es contents at: i).
 421          es contents at: i put: es contents defaultElement].
 422   result
 423 ].
 424
 425 c@(Collection traits) collect: block into: es@(ExtensibleArray traits)
 426 "Override to use the specific implementation."
 427 [
 428   c do: [| :each | es addLast: (block applyWith: each)].
 429   es
 430 ].
 431
 432 es@(ExtensibleArray traits) collect: block from: start to: end
 433 "Override to use the specific implementation."
 434 [| result |
 435   start < 0 \/ [end >= es size]
 436     ifTrue: [result := es new]
 437     ifFalse:
 438       [result := es new &capacity: end - start + 1.
 439        es firstIndex + start to: es firstIndex + end do:
 440          [| :index | result addLast: (block applyWith: (es contents at: index))]].
 441   result
 442 ].
 443
 444 es@(ExtensibleArray traits) do: block
 445 [| index |
 446   index := es firstIndex.
 447   limit ::= es lastIndex.
 448   [index <= limit] whileTrue:
 449     [block applyWith: (es contents at: index).
 450      index += 1].
 451   es
 452 ].
 453
 454 es@(ExtensibleArray traits) reverseDo: block
 455 [| index |
 456   index := es lastIndex.
 457   limit ::= es firstIndex.
 458   [index >= limit] whileTrue:
 459     [block applyWith: (es contents at: index).
 460      index -= 1].
 461   es
 462 ].
 463
 464 c@(Collection traits) select: block into: es@(ExtensibleArray traits)
 465 [
 466   c do: [| :each | (block applyWith: each) ifTrue: [es addLast: each]].
 467   es
 468 ].
 469
 470 c@(Sequence traits) collectWithIndex: binBlock into: es@(ExtensibleArray traits)
 471 "Override to use addLast: vice at:put:."
 472 [
 473   c doWithIndex:
 474     [| :each :index | es addLast: (block applyWith: each with: index)].
 475   es
 476 ].
 477
 478 es@(ExtensibleArray traits) find: obj
 479 [| index |
 480   index := es firstIndex.
 481   limit ::= es lastIndex.
 482   [index <= limit] whileTrue:
 483     [(es contents at: index) = obj ifTrue: [^ index].
 484      index += 1].
 485   Nil
 486 ].
 487
 488 es@(ExtensibleArray traits) makeGapAt: index &size: size
 489 "Make a gap at the requested index, and return the start offset of
 490 the created gap in the contents array."
 491 [
 492   size `defaultsTo: 1.
 493   `conditions: (
 494     [size isNegative]
 495       -> [error: 'Gap size must be bigger then 0'].
 496     [index isNegative \/ [index > es size]]
 497       -> [index keyNotFoundOn: es].
 498     [index isZero]
 499       -> [es firstIndex - size < 0 ifTrue: [es growFirst &by: size].
 500           es firstIndex := es firstIndex - size]
 501   ) otherwise:
 502     [es lastIndex + size >= es capacity ifTrue: [es growLast &by: size].
 503      contentsIndex ::= es firstIndex + index.
 504      index = es size ifFalse:
 505        [es contents
 506           replaceFrom: contentsIndex + size
 507           to: es lastIndex + size
 508           with: es contents
 509           startingAt: contentsIndex].
 510      es lastIndex += size.
 511      contentsIndex]
 512 ].
 513
 514 es@(ExtensibleArray traits) at: index insert: obj
 515 [
 516   es contents at: (es makeGapAt: index) put: obj
 517 ].
 518
 519 es@(ExtensibleArray traits) at: index insertAll: col
 520 [
 521   startOffset ::= es makeGapAt: index &size: col size.
 522   col doWithIndex: [| :each :index | es contents at: startOffset + index put: each].
 523   es
 524 ].
 525
 526 es@(ExtensibleArray traits) move: obj to: index
 527 "Re-position the object so that it has the given index, and slide up/down other
 528 objects as needed."
 529 [
 530   (src ::= es find: obj)
 531     ifNil: [obj elementNotFoundOn: es].
 532   (tgt ::= index + es startIndex) = src ifFalse:
 533     [src > tgt
 534        ifTrue:
 535          [es contents
 536             replaceFrom: tgt + 1
 537             to: src
 538             with: es contents
 539             startingAt: tgt]
 540        ifFalse:
 541          [es contents
 542             replaceFrom: src
 543             to: es contents lastIndex
 544             with: es contents
 545             startingAt: src + 1].
 546      es contents at: tgt put: obj].
 547   es
 548 ].
 549
 550 "this will call the correct #as function when converting to strings"
 551 collections define: #ExtensibleByteArray &parents: {ExtensibleArray}.
 552 ExtensibleByteArray contents := ByteArray new.
 553
 554 es@(ExtensibleByteArray traits) elementType [SmallInteger].
 555
 556 es@(ExtensibleByteArray traits) as: s@(String traits)
 557 [
 558   result ::= s newSizeOf: es.
 559   es doWithIndex:
 560     [| :each :index | result at: index put: (each as: s elementType)].
 561   result
 562 ].
 563
 564 s@(ASCIIString traits) as: a@(ExtensibleByteArray traits)
 565 [
 566   result ::= a new &capacity: s size.
 567   s do: [| :each | result add: (each as: a elementType)].
 568   result
 569 ].