1 "

     2  COPYRIGHT (c) 1989-93 by Claus Gittinger

     3               All Rights Reserved

     4 

     5  This software is furnished under a license and may be used

     6  only in accordance with the terms of that license and with the

     7  inclusion of the above copyright notice.   This software may not

     8  be provided or otherwise made available to, or used by, any

     9  other person.  No title to or ownership of the software is

    10  hereby transferred.

    11 "

    12 

    13 Collection subclass:#SequenceableCollection

    14        instanceVariableNames:''

    15        classVariableNames:''

    16        poolDictionaries:''

    17        category:'Collections-Abstract'

    18 !

    19 

    20 SequenceableCollection comment:'

    21 

    22 COPYRIGHT (c) 1989-93 by Claus Gittinger

    23               All Rights Reserved

    24 

    25 SequenceableCollections have ordered elements which can be accessed via

    26 an index. SequenceableCollection is an abstract class - there are no

    27 instances of it in the system.

    28 

    29 %W% %E%

    30 

    31 written spring 89 by claus

    32 '!

    33 

    34 !SequenceableCollection class methodsFor:'instance creation'!

    35 

    36 new:size withAll:element

    37     "return a new Collection of size, where all elements are

    38      initialized to element"

    39 

    40     |newCollection|

    41 

    42     newCollection := self new:size.

    43     newCollection atAllPut:element.

    44     ^ newCollection

    45 ! !

    46 

    47 !SequenceableCollection methodsFor:'accessing'!

    48 

    49 first

    50     "return the first element"

    51 

    52     ^ self at:1

    53 !

    54 

    55 last

    56     "return the last element"

    57 

    58     ^ self at:(self size)

    59 ! !

    60 

    61 !SequenceableCollection methodsFor:'comparing'!

    62 

    63 = aCollection

    64     "return true if the receiver and aCollection represent collections

    65      with equal contents."

    66 

    67     |index "{ Class: SmallInteger }"

    68      stop  "{ Class: SmallInteger }" |

    69 

    70     (aCollection == self) ifTrue:[^true].

    71     (aCollection isKindOf:SequenceableCollection) ifFalse:[^false].

    72 

    73     stop := self size.

    74     stop == (aCollection size) ifFalse:[^false].

    75     index := 1.

    76     [index <= stop] whileTrue:[

    77         (self at:index) = (aCollection at:index) ifFalse:[^false].

    78         index := index + 1

    79     ].

    80     ^ true

    81 !

    82 

    83 startsWith:aCollection

    84     "return true, if the receivers first elements match those

    85      of aCollection"

    86 

    87     |index "{ Class: SmallInteger }"

    88      stop  "{ Class: SmallInteger }" |

    89 

    90     (aCollection == self) ifTrue:[^true].

    91     (aCollection isKindOf:SequenceableCollection) ifFalse:[^false].

    92 

    93     stop := aCollection size.

    94     stop > self size ifTrue:[^false].

    95 

    96     index := 1.

    97     [index <= stop] whileTrue:[

    98         (self at:index) = (aCollection at:index) ifFalse:[^false].

    99         index := index + 1

   100     ].

   101     ^ true

   102 

   103     "'abcde' startsWith:#($a $b $c)"

   104     "#[1 2 3 4] startsWith:#(1 2 3)"

   105     "#(1 2 3 4) asOrderedCollection startsWith:#(1 2 3)"

   106 !

   107 

   108 endsWith:aCollection

   109     "return true, if the receivers last elements match those

   110      of aCollection"

   111 

   112     |index1 "{ Class: SmallInteger }"

   113      index2 "{ Class: SmallInteger }" 

   114      stop   "{ Class: SmallInteger }" |

   115 

   116     (aCollection == self) ifTrue:[^true].

   117     (aCollection isKindOf:SequenceableCollection) ifFalse:[^false].

   118 

   119     stop := aCollection size.

   120     stop > self size ifTrue:[^false].

   121 

   122     index1 := self size.

   123     index2 := aCollection size.

   124     [index2 > 0] whileTrue:[

   125         (self at:index1) = (aCollection at:index2) ifFalse:[^false].

   126         index1 := index1 - 1.

   127         index2 := index2 - 1

   128     ].

   129     ^ true

   130 

   131     "'abcde' endsWith:#($d $e)"

   132     "#[1 2 3 4] endsWith:#(3 4)"

   133     "#(1 2 3 4) asOrderedCollection endsWith:#(3 4)"

   134 ! !

   135 

   136 !SequenceableCollection methodsFor:'testing'!

   137 

   138 size

   139     "return the number of elements in the collection.

   140      concrete implementations must define this"

   141 

   142     ^ self subclassResponsibility

   143 ! !

   144 

   145 !SequenceableCollection methodsFor:'copying'!

   146 

   147 , aCollection

   148     "return a new collection formed from concatenating the receiver with

   149      the argument"

   150 

   151     |newCollection 

   152      mySize    "{ Class: SmallInteger }"

   153      newSize   "{ Class: SmallInteger }"

   154      otherSize "{ Class: SmallInteger }"

   155      dstIndex  "{ Class: SmallInteger }"|

   156 

   157     mySize := self size.

   158     otherSize := aCollection size.

   159     newSize := mySize + otherSize.

   160     newCollection := self species new:newSize.

   161 

   162     newCollection replaceFrom:1 to:mySize with:self startingAt:1.

   163     dstIndex := mySize + 1.

   164     (aCollection isKindOf:SequenceableCollection) ifTrue:[

   165         "yes, aCollection has indexed elements"

   166         newCollection replaceFrom:dstIndex to:newSize

   167                              with:aCollection startingAt:1.

   168         ^ newCollection

   169     ] ifFalse:[

   170         "no, enumerate aCollection"

   171         aCollection do:[:element |

   172             newCollection at:dstIndex put:element.

   173             dstIndex := dstIndex + 1

   174         ]

   175     ].

   176     ^ newCollection

   177 !

   178 

   179 copyWith:newElement

   180     "return a new collection consisting of receivers elements

   181      plus the argument"

   182 

   183     |newCollection mySize newSize|

   184 

   185     mySize := self size.

   186     newSize := mySize + 1.

   187     newCollection := self species new:newSize.

   188     newCollection replaceFrom:1 to:mySize with:self startingAt:1.

   189     newCollection at:newSize put:newElement.

   190     ^newCollection

   191 !

   192 

   193 copyWithout:anElement

   194     "return a new collection consisting of receivers elements

   195      without anElement (if it was present)"

   196 

   197     |newCollection skipIndex 

   198      dstIndex "{ Class: SmallInteger }"

   199      index    "{ Class: SmallInteger }"

   200      stop     "{ Class: SmallInteger }" |

   201 

   202     skipIndex := self indexOf:anElement startingAt:1.

   203     (skipIndex == 0) ifTrue:[^ self copy].

   204     stop := self size.

   205     newCollection := self class new:(stop - 1).

   206     dstIndex := 1.

   207     index := 1.

   208     [index <= stop] whileTrue:[

   209         (index ~~ skipIndex) ifTrue:[

   210             newCollection at:dstIndex put:(self at:index).

   211             dstIndex := dstIndex + 1

   212         ].

   213         index := index + 1

   214     ].

   215     ^ newCollection

   216 !

   217 

   218 copyFrom:start to:stop

   219     "return a new collection consisting of receivers elements

   220      between start and stop"

   221 

   222     |newCollection newSize|

   223 

   224     newSize := stop - start + 1.

   225     newCollection := self class new:newSize.

   226     newCollection replaceFrom:1 to:newSize with:self startingAt:start.

   227     ^ newCollection

   228 !

   229 

   230 copyFrom:start

   231     "return a new collection consisting of receivers elements

   232      from start to the end of the collection"

   233 

   234     ^ self copyFrom:start to:(self size)

   235 !

   236 

   237 copyTo:stop

   238     "return a new collection consisting of receivers elements

   239      from 1 up to index stop"

   240 

   241     ^ self copyFrom:1 to:stop

   242 !

   243 

   244 copyWithoutIndex:omitIndex

   245     "return a new collection consisting of receivers elements

   246      without the argument stored at omitIndex"

   247 

   248     |copy|

   249 

   250     copy := self class new:(self size - 1).

   251     copy replaceFrom:1 to:(omitIndex - 1) with:self startingAt:1.

   252     copy replaceFrom:omitIndex to:(copy size) 

   253                 with:self startingAt:(omitIndex + 1).

   254     ^ copy

   255 ! !

   256 

   257 !SequenceableCollection methodsFor:'filling and replacing'!

   258 

   259 from:index1 to:index2 put:anObject

   260     "replace the elements from index1 to index2 of the collection

   261      by the argument, anObject"

   262 

   263     |index "{ Class: SmallInteger }"

   264      end   "{ Class: SmallInteger }"|

   265 

   266     index := index1.

   267     end := index2.

   268     [index <= end] whileTrue:[

   269         self at:index put:anObject.

   270         index := index + 1

   271     ]

   272 !

   273 

   274 atAllPut:anObject

   275     "replace all elements of the collection by the argument, anObject"

   276 

   277     self from:1 to:(self size) put:anObject

   278 !

   279 

   280 atAll:indexCollection put:anObject

   281     "put anObject into all indexes from indexCollection in the receiver"

   282 

   283     indexCollection do:[:index | self at:index put:anObject]

   284 

   285     "(Array new:10) atAll:(1 to:5) put:0"

   286     "(Array new:10) atAll:#(1 5 6 9) put:0"

   287 !

   288 

   289 replaceAll:oldObject by:newObject

   290     "replace all oldObjects by newObject in the receiver"

   291 

   292     1 to:self size do:[:index |

   293         (self at:index) = oldObject ifTrue:[

   294             self at:index put:newObject

   295         ]

   296     ]

   297 !

   298 

   299 replaceFrom:start with:replacementCollection

   300     "replace elements starting at start with elements

   301      taken from replacementCollection (starting at 1)"

   302 

   303     ^ self replaceFrom:start 

   304                     to:(start + replacementCollection size - 1)

   305                   with:replacementCollection

   306             startingAt:1

   307 !

   308 

   309 replaceFrom:start to:stop with:replacementCollection

   310     "replace elements between index start and stop with elements

   311      taken from replacementCollection (starting at 1)"

   312 

   313     ^ self replaceFrom:start

   314                     to:stop

   315                   with:replacementCollection

   316             startingAt:1

   317 !

   318 

   319 replaceFrom:start to:stop with:replacementCollection startingAt:repStart

   320     "replace elements between index start and stop with elements

   321      taken from replacementCollection (starting at repStart)"

   322 

   323     |srcIndex "{ Class: SmallInteger }"

   324      dstIndex "{ Class: SmallInteger }"

   325      end      "{ Class: SmallInteger }" |

   326 

   327     (replacementCollection == self) ifTrue:[

   328         (repStart < start) ifTrue:[

   329             " must do reverse copy "

   330             srcIndex := repStart + (stop - start).

   331             dstIndex := stop.

   332             end := start.

   333             [dstIndex >= end] whileTrue:[

   334                 self at:dstIndex put:(replacementCollection at:srcIndex).

   335                 srcIndex := srcIndex - 1.

   336                 dstIndex := dstIndex - 1

   337             ].

   338             ^ self

   339         ]

   340     ].

   341 

   342     srcIndex := repStart.

   343     dstIndex := start.

   344     end := stop.

   345     [dstIndex <= end] whileTrue:[

   346         self at:dstIndex put:(replacementCollection at:srcIndex).

   347         srcIndex := srcIndex + 1.

   348         dstIndex := dstIndex + 1

   349     ]

   350 !

   351 

   352 withCRs

   353     "return a new collection consisting of receivers elements

   354      with all \-characters replaced by cr-characters"

   355 

   356     |newCollection

   357      size "{ Class: SmallInteger }" |

   358 

   359     newCollection := self copy.

   360     size := self size.

   361     1 to:size do:[:index |

   362         ((self at:index) == $\) ifTrue:[

   363             newCollection at:index put:(Character cr)

   364         ]

   365     ].

   366     ^ newCollection

   367 !

   368 

   369 withoutCRs

   370     "return a new collection consisting of receivers elements

   371      with all cr-characters replaced by \-characters"

   372 

   373     |newCollection 

   374      size "{ Class: SmallInteger }" |

   375 

   376     newCollection := self copy.

   377     size := self size.

   378     1 to:size do:[:index|

   379         ((self at:index) == Character cr) ifTrue:[

   380             newCollection at:index put:$\

   381         ]

   382     ].

   383     ^ newCollection

   384 ! !

   385 

   386 !SequenceableCollection methodsFor:'adding & removing'!

   387 

   388 addFirst:anElement

   389     "prepend the argument, anElement to the collection"

   390 

   391     |newSize|

   392 

   393     newSize := self size + 1.

   394     self grow:newSize.

   395     self replaceFrom:2 to:newSize with:self startingAt:1.

   396     self at:1 put:anElement

   397 !

   398 

   399 add:anElement

   400     "append the argument, anElement to the collection"

   401 

   402     |newSize|

   403 

   404     newSize := self size + 1.

   405     self grow:newSize.

   406     self at:newSize put:anElement

   407 !

   408 

   409 add:anElement beforeIndex:index

   410     "insert the first argument, anObject into the collection before slot index"

   411 

   412     |newSize|

   413 

   414     newSize := self size + 1.

   415     self grow:newSize.

   416     self replaceFrom:index + 1 to:newSize with:self startingAt:index.

   417     self at:index put:anElement

   418 !

   419 

   420 remove:anElement ifAbsent:aBlock

   421     "search for anElement and, if present remove it; if not present

   422      return the value of evaluating aBlock"

   423 

   424     |any 

   425      dstIndex "{ Class: SmallInteger }"

   426      sz       "{ Class: SmallInteger }"|

   427 

   428     dstIndex := 1.

   429     any := false.

   430     sz := self size.

   431     1 to:sz do:[:srcIndex |

   432         (anElement = (self at:srcIndex)) ifTrue:[

   433             any := true

   434         ] ifFalse:[

   435             (dstIndex ~~ srcIndex) ifTrue:[

   436                 self at:dstIndex put:(self at:srcIndex)

   437             ].

   438             dstIndex := dstIndex + 1

   439         ]

   440     ].

   441     any ifTrue:[

   442         self grow:dstIndex - 1

   443     ] ifFalse:[

   444         aBlock value

   445     ]

   446 !

   447 

   448 removeFromIndex:startIndex toIndex:endIndex

   449     "remove the elements stored at indexes between startIndex and endIndex"

   450 

   451     |newSize|

   452 

   453     newSize := self size - endIndex + startIndex - 1.

   454     self replaceFrom:startIndex to:newSize with:self startingAt:(endIndex + 1).

   455     self grow:newSize

   456 !

   457 

   458 removeIndex:index

   459     "remove the argument stored at index"

   460 

   461     self removeFromIndex:index toIndex:index

   462 ! !

   463 

   464 !SequenceableCollection methodsFor:'searching'!

   465 

   466 detect:aBlock ifNone:exceptionBlock

   467     "find the first element, for which evaluation of the argument, aBlock

   468      return true; if none does so, return the evaluation of exceptionBlock

   469 

   470     reimplemented here for speed"

   471 

   472     |index "{ Class: SmallInteger }"

   473      stop  "{ Class: SmallInteger }"

   474      element|

   475 

   476     stop := self size.

   477     index := 1.

   478     [index <= stop] whileTrue:[

   479         element := self at:index.

   480         (aBlock value:element) ifTrue:[

   481             ^ element

   482         ].

   483         index := index + 1

   484     ].

   485     ^ exceptionBlock value

   486 !

   487 

   488 indexOf:anElement

   489     "search the collection for anElement;

   490      if found, return the index otherwise return 0.

   491      The comparison is done using = (i.e. equality test)."

   492 

   493     ^ self indexOf:anElement startingAt:1

   494 !

   495 

   496 indexOf:anElement ifAbsent:exceptionBlock

   497     "search the collection for anElement;

   498      if found, return the index otherwise return the value of the

   499      exceptionBlock.

   500      The comparison is done using = (i.e. equality test)."

   501 

   502     |index|

   503 

   504     index := self indexOf:anElement startingAt:1.

   505     (index == 0) ifTrue:[^ exceptionBlock value].

   506     ^ index

   507 !

   508 

   509 indexOf:anElement startingAt:start

   510     "search the collection for anElement staring search at index start;

   511      if found, return the index otherwise return 0.

   512      The comparison is done using = (i.e. equality test)."

   513 

   514     |index "{ Class: SmallInteger }"

   515      stop  "{ Class: SmallInteger }" |

   516 

   517     index := start.

   518     stop := self size.

   519     [index <= stop] whileTrue:[

   520         anElement = (self at:index) ifTrue:[^ index].

   521         index := index + 1

   522     ].

   523     ^ 0

   524 !

   525 

   526 indexOf:anElement startingAt:start ifAbsent:exceptionBlock

   527     "search the collection for anElement starting search at start;

   528      if found, return the index otherwise return the value of the

   529      exceptionBlock.

   530      The comparison is done using = (i.e. equality test)."

   531 

   532     |index|

   533 

   534     index := self indexOf:anElement startingAt:start.

   535     (index == 0) ifTrue:[^ exceptionBlock value].

   536     ^ index

   537 !

   538 

   539 identityIndexOf:anElement

   540     "search the collection for anElement using identity compare (i.e. ==);

   541      if found, return the index otherwise return 0."

   542 

   543     ^ self identityIndexOf:anElement startingAt:1

   544 !

   545 

   546 identityIndexOf:anElement ifAbsent:exceptionBlock

   547     "search the collection for anElement using identity compare (i.e. ==);

   548      if found, return the index otherwise return the value of the

   549      exceptionBlock."

   550 

   551     |index|

   552 

   553     index := self identityIndexOf:anElement startingAt:1.

   554     (index == 0) ifTrue:[^ exceptionBlock value].

   555     ^ index

   556 !

   557 

   558 identityIndexOf:anElement startingAt:start

   559     "search the collection for anElement staring search at index start

   560      using identity compare  (i.e. ==);

   561      if found, return the index otherwise return 0."

   562 

   563     |index "{ Class: SmallInteger }"

   564      stop  "{ Class: SmallInteger }" |

   565 

   566     index := start.

   567     stop := self size.

   568     [index <= stop] whileTrue:[

   569         anElement == (self at:index) ifTrue:[^ index].

   570         index := index + 1

   571     ].

   572     ^ 0

   573 !

   574 

   575 identityIndexOf:anElement startingAt:start ifAbsent:exceptionBlock

   576     "search the collection for anElement starting search at start;

   577      if found, return the index otherwise return the value of the

   578      exceptionBlock.

   579      This one searches for identical objects (i.e. ==)."

   580 

   581     |index|

   582 

   583     index := self identityIndexOf:anElement startingAt:start.

   584     (index == 0) ifTrue:[^ exceptionBlock value].

   585     ^ index

   586 !

   587 

   588 findFirst:aBlock

   589     "find the first element, for which evaluation of the argument, aBlock

   590      return true; return its index or 0 if none detected."

   591 

   592     |index "{ Class: SmallInteger }"

   593      stop  "{ Class: SmallInteger }" |

   594 

   595     stop := self size.

   596     index := 1.

   597     [index <= stop] whileTrue:[

   598         (aBlock value:(self at:index)) ifTrue:[^ index].

   599         index := index + 1

   600     ].

   601     ^ 0

   602 

   603     "#(1 2 3 4 5 6) findFirst:[:x | (x > 3) and:[x even]]"

   604 !

   605 

   606 includes:anElement

   607     "return true if the collection contains anElement; false otherwise.

   608      Comparison is done using equality compare (i.e. =)."

   609 

   610     ((self indexOf:anElement startingAt:1) == 0) ifTrue:[^ false].

   611     ^ true

   612 ! !

   613 

   614 !SequenceableCollection methodsFor:'sorting & reordering'!

   615 

   616 reverse

   617     "reverse the order of the arguments inplace"

   618 

   619     |lowIndex "{ Class: SmallInteger }"

   620      hiIndex  "{ Class: SmallInteger }"

   621      t|

   622 

   623     hiIndex := self size.

   624     lowIndex := 1.

   625     [lowIndex < hiIndex] whileTrue:[

   626         t := self at:lowIndex.

   627         self at:lowIndex put:(self at:hiIndex). 

   628         self at:hiIndex put:t.

   629         lowIndex := lowIndex + 1.

   630         hiIndex := hiIndex - 1

   631     ]

   632     "#(4 5 6 7 7) reverse"

   633 !

   634 

   635 quickSortFrom:begin to:end

   636     "actual quicksort worker for sort-message"

   637 

   638     |b "{ Class: SmallInteger }"

   639      e "{ Class: SmallInteger }"

   640      middleElement temp |

   641 

   642     b := begin.

   643     e := end.

   644     middleElement := self at:((b + e) // 2).

   645 

   646     [b < e] whileTrue:[

   647         [b < end and:[(self at:b) < middleElement]] whileTrue:[b := b + 1].

   648         [e > begin and:[middleElement < (self at:e)]] whileTrue:[e := e - 1].

   649 

   650         (b <= e) ifTrue:[

   651             (b == e) ifFalse:[

   652                 temp := self at:b.

   653                 self at:b put:(self at:e).

   654                 self at:e put:temp

   655             ].

   656             b := b + 1.

   657             e := e - 1

   658         ]

   659     ].

   660     (begin < e) ifTrue:[self quickSortFrom:begin to:e].

   661     (b < end) ifTrue:[self quickSortFrom:b to:end]

   662 !

   663 

   664 quickSortFrom:begin to:end with:aCollection

   665     "actual quicksort worker for sortWith-message"

   666 

   667     |b "{ Class: SmallInteger }"

   668      e "{ Class: SmallInteger }"

   669      middleElement temp |

   670 

   671     b := begin.

   672     e := end.

   673     middleElement := self at:((b + e) // 2).

   674 

   675     [b < e] whileTrue:[

   676         [b < end and:[(self at:b) < middleElement]] whileTrue:[b := b + 1].

   677         [e > begin and:[middleElement < (self at:e)]] whileTrue:[e := e - 1].

   678 

   679         (b <= e) ifTrue:[

   680             (b == e) ifFalse:[

   681                 temp := self at:b.

   682                 self at:b put:(self at:e).

   683                 self at:e put:temp.

   684                 temp := aCollection at:b.

   685                 aCollection at:b put:(aCollection at:e).

   686                 aCollection at:e put:temp

   687             ].

   688             b := b + 1.

   689             e := e - 1

   690         ]

   691     ].

   692     (begin < e) ifTrue:[self quickSortFrom:begin to:e with:aCollection].

   693     (b < end) ifTrue:[self quickSortFrom:b to:end with:aCollection]

   694 !

   695 

   696 quickSortFrom:begin to:end sortBlock:sortBlock

   697     "actual quicksort worker for sort:-message"

   698 

   699     |b "{ Class: SmallInteger }"

   700      e "{ Class: SmallInteger }"

   701      middleElement temp |

   702 

   703     b := begin.

   704     e := end.

   705     middleElement := self at:((b + e) // 2).

   706 

   707     [b < e] whileTrue:[

   708         [b < end and:[sortBlock value:(self at:b) value:middleElement]] whileTrue:[b := b + 1].

   709         [e > begin and:[sortBlock value:middleElement value:(self at:e)]] whileTrue:[e := e - 1].

   710 

   711         (b <= e) ifTrue:[

   712             (b == e) ifFalse:[

   713                 temp := self at:b.

   714                 self at:b put:(self at:e).

   715                 self at:e put:temp

   716             ].

   717             b := b + 1.

   718             e := e - 1

   719         ]

   720     ].

   721     (begin < e) ifTrue:[self quickSortFrom:begin to:e sortBlock:sortBlock].

   722     (b < end) ifTrue:[self quickSortFrom:b to:end sortBlock:sortBlock]

   723 !

   724 

   725 quickSortFrom:begin to:end sortBlock:sortBlock with:aCollection

   726     "actual quicksort worker for sort:with:-message"

   727 

   728     |b "{ Class: SmallInteger }"

   729      e "{ Class: SmallInteger }"

   730      middleElement temp |

   731 

   732     b := begin.

   733     e := end.

   734     middleElement := self at:((b + e) // 2).

   735 

   736     [b < e] whileTrue:[

   737         [b < end and:[sortBlock value:(self at:b) value:middleElement]] whileTrue:[b := b + 1].

   738         [e > begin and:[sortBlock value:middleElement value:(self at:e)]] whileTrue:[e := e - 1].

   739 

   740         (b <= e) ifTrue:[

   741             (b == e) ifFalse:[

   742                 temp := self at:b.

   743                 self at:b put:(self at:e).

   744                 self at:e put:temp.

   745                 temp := aCollection at:b.

   746                 aCollection at:b put:(aCollection at:e).

   747                 aCollection at:e put:temp

   748             ].

   749             b := b + 1.

   750             e := e - 1

   751         ]

   752     ].

   753     (begin < e) ifTrue:[self quickSortFrom:begin to:e sortBlock:sortBlock with:aCollection].

   754     (b < end) ifTrue:[self quickSortFrom:b to:end sortBlock:sortBlock with:aCollection]

   755 !

   756 

   757 bubbleSort

   758     "sort the collection inplace using bubbleSort (sloooow)

   759      - this one makes only sense to sort after inserting an element into

   760        an already sorted collection (if at all)"

   761 

   762     |index  "{ Class: SmallInteger }"

   763      index2 "{ Class: SmallInteger }"

   764      end    "{ Class: SmallInteger }"

   765      smallest smallestIndex thisOne|

   766 

   767     end := self size.

   768     index := 1.

   769     [index <= end] whileTrue:[

   770         smallest := self at:index.

   771         smallestIndex := index.

   772         index2 := index + 1.

   773         [index2 <= end] whileTrue:[

   774             (self at:index2) < smallest ifTrue:[

   775                 smallestIndex := index2.

   776                 smallest := self at:index2

   777             ].

   778             index2 := index2 + 1

   779         ].

   780         (smallestIndex ~~ index) ifTrue:[

   781             thisOne := self at:index.

   782             self at:index put:smallest.

   783             self at:smallestIndex put:thisOne

   784         ].

   785         index := index + 1

   786     ]

   787 

   788     "#(1 16 7 98 3 19 4 0) bubbleSort"

   789 !

   790 

   791 sort

   792     "sort the collection inplace. The elements are compared using

   793      > and < i.e. they should offer a magnitude-like protocol."

   794     |sz|

   795 

   796     sz := self size.

   797     (sz > 1) ifTrue:[

   798         self quickSortFrom:1 to:sz

   799     ]

   800 

   801     "#(1 16 7 98 3 19 4 0) sort"

   802 !

   803 

   804 sortWith:aCollection

   805     "sort the receiver collection inplace, also sort aCollection with it.

   806      Use, when you have a key collection to sort another collection with."

   807 

   808     |sz|

   809 

   810     sz := self size.

   811     (sz > 1) ifTrue:[

   812         self quickSortFrom:1 to:sz with:aCollection

   813     ]

   814 

   815     "|c1 c2|

   816      c1 := #(1 16 7 9).

   817      c2 := #('one' 'sixteen' 'seven' 'nine').

   818      c1 sortWith:c2.

   819      c1 printNewline.

   820      c2 printNewline"

   821 !

   822 

   823 sort:sortBlock

   824     "sort the collection inplace using the 2-arg block sortBlock

   825      for comparison. This allows any sort criteria to be implemented."

   826 

   827     |sz|

   828 

   829     sz := self size.

   830     (sz > 1) ifTrue:[

   831         self quickSortFrom:1 to:sz sortBlock:sortBlock

   832     ]

   833 

   834     "#(1 16 7 98 3 19 4 0) sort:[:a :b | a < b]"

   835     "#(1 16 7 98 3 19 4 0) sort:[:a :b | a > b]"

   836 !

   837 

   838 sort:sortBlock with:aCollection

   839     "sort the collection inplace using the 2-arg block sortBlock

   840      for comparison. Also reorder the elements in aCollection"

   841 

   842     |sz|

   843 

   844     sz := self size.

   845     (sz > 1) ifTrue:[

   846         self quickSortFrom:1 to:sz sortBlock:sortBlock with:aCollection

   847     ]

   848 

   849     "|c1 c2|

   850      c1 := #(1 16 7 9).

   851      c2 := #('one' 'sixteen' 'seven' 'nine').

   852      c1 sort:[:a :b | a > b] with:c2.

   853      c1 printNewline.

   854      c2 printNewline"

   855 ! !

   856 

   857 !SequenceableCollection methodsFor:'enumerating'!

   858 

   859 do:aBlock

   860     "evaluate the argument, aBlock for every element in the collection."

   861 

   862     |index  "{ Class:SmallInteger }"

   863      length "{ Class:SmallInteger }"|

   864 

   865     index := 1.

   866     length := self size.

   867     [index <= length] whileTrue:[

   868         aBlock value:(self at:index).

   869         index := index + 1

   870     ]

   871 !

   872 

   873 from:index1 to:index2 do:aBlock

   874     "evaluate the argument, aBlock for the elements with index index1 to

   875      index2 in the collection"

   876 

   877     |index "{ Class:SmallInteger }"

   878      stop  "{ Class:SmallInteger }" |

   879 

   880     index := index1.

   881     stop := index2.

   882     [index <= stop] whileTrue:[

   883         aBlock value:(self at:index).

   884         index := index + 1

   885     ]

   886 !

   887 

   888 with:aCollection do:aBlock

   889     "evaluate the argument, aBlock for successive elements from

   890      each of the two collections self and aCollection.

   891      aBlock must be a two-argument block"

   892 

   893     |index "{ Class: SmallInteger }"

   894      stop  "{ Class: SmallInteger }" |

   895 

   896     index := 1.

   897     stop := self size.

   898     [index <= stop] whileTrue:[

   899         aBlock value:(self at:index) value:(aCollection at:index).

   900         index := index + 1

   901     ]

   902 !

   903 

   904 reverseDo:aBlock

   905     "evaluate the argument, aBlock for every element in the collection

   906      in reverse order"

   907 

   908     |index "{ Class:SmallInteger }" |

   909 

   910     index := self size.

   911     [index > 0] whileTrue:[

   912         aBlock value:(self at:index).

   913         index := index - 1

   914     ]

   915 !

   916 

   917 collect:aBlock

   918     "evaluate the argument, aBlock for every element in the collection

   919      and return a collection of the results"

   920 

   921     |newCollection

   922      index  "{ Class:SmallInteger }"

   923      length "{ Class:SmallInteger }" |

   924 

   925     length := self size.

   926     newCollection := self species new:length.

   927     index := 1.

   928     [index <= length] whileTrue:[

   929         newCollection at:index put:(aBlock value:(self at:index)).

   930         index := index + 1

   931     ].

   932     ^ newCollection

   933 !

   934 

   935 select:aBlock

   936     "evaluate the argument, aBlock for every element in the collection

   937      and return a collection of all elements for which the block return

   938      true"

   939 

   940     |element newColl

   941      index  "{ Class:SmallInteger }"

   942      length "{ Class:SmallInteger }" |

   943 

   944     length := self size.

   945     newColl := OrderedCollection new:length.

   946     index := 1.

   947     [index <= length] whileTrue:[

   948         element := self at:index.

   949         (aBlock value:element) ifTrue:[

   950             newColl add:element

   951         ].

   952         index := index + 1

   953     ].

   954     ^ newColl

   955 ! !