60 This may be changed in a future release of ST/X |
60 This may be changed in a future release of ST/X |
61 (it is not yet, to not confuse existing applications ... |
61 (it is not yet, to not confuse existing applications ... |
62 ... be aware, that the sortBlock has an effect on a few algorithms |
62 ... be aware, that the sortBlock has an effect on a few algorithms |
63 found here; especially #indexForInserting is critical.) |
63 found here; especially #indexForInserting is critical.) |
64 |
64 |
|
65 [caveat:] |
|
66 a balanced tree may be a better choice, as inserting may be slow when |
|
67 elements have to be shifted. |
65 |
68 |
66 [author:] |
69 [author:] |
67 Claus Gittinger |
70 Claus Gittinger |
68 " |
71 " |
69 ! |
72 ! |
320 |
323 |
321 !SortedCollection class methodsFor:'Compatibility-Dolphin'! |
324 !SortedCollection class methodsFor:'Compatibility-Dolphin'! |
322 |
325 |
323 sortBlock:aBlock withAll:aCollection |
326 sortBlock:aBlock withAll:aCollection |
324 ^ self withAll:aCollection sortBlock:aBlock |
327 ^ self withAll:aCollection sortBlock:aBlock |
325 ! ! |
|
326 |
|
327 !SortedCollection class methodsFor:'helpers'! |
|
328 |
|
329 binarySearch:aSortedArray for:anObject |
|
330 "search for an existing element; return true if found. |
|
331 by checking if the element at the returned index is the one we look for. |
|
332 Uses a binarySearch since we can depend on the elements being on sorted order. |
|
333 The returned index is a physical one, for accessing contentsArray. |
|
334 This is only to be used for arrays which are known to be sorted." |
|
335 |
|
336 |idx| |
|
337 |
|
338 idx := self |
|
339 binarySearch:aSortedArray |
|
340 forIndexOf:anObject. |
|
341 ^ idx <= aSortedArray size |
|
342 and:[ (aSortedArray at:idx) = anObject ]. |
|
343 |
|
344 " |
|
345 SortedCollection |
|
346 binarySearch:#(1 2 3 4 7 99 1313 981989 898989898) |
|
347 for:898989898 |
|
348 " |
|
349 ! |
|
350 |
|
351 binarySearch:aSortedArray forIndexOf:anObject |
|
352 "search the index at which to insert anObject. |
|
353 Can also be used to search for an existing element |
|
354 by checking if the element at the returned index is the one we look for. |
|
355 Uses a binarySearch since we can depend on the elements being on sorted order. |
|
356 The returned index is a physical one, for accessing contentsArray. |
|
357 This is only to be used for arrays which are known to be sorted." |
|
358 |
|
359 ^ self |
|
360 binarySearch:aSortedArray |
|
361 from:1 to:(aSortedArray size) |
|
362 forIndexOf:anObject |
|
363 usingSortBlock:[:a :b | a < b ] |
|
364 |
|
365 " |
|
366 SortedCollection |
|
367 binarySearch:#(1 2 3 4 7 99 1313 981989 898989898) |
|
368 from:1 to:9 |
|
369 forIndexOf:99 |
|
370 usingSortBlock:[:a :b | a < b ] |
|
371 " |
|
372 |
|
373 "Modified: 12.4.1996 / 13:22:03 / cg" |
|
374 ! |
|
375 |
|
376 binarySearch:aSortedArray from:firstIndex to:lastIndex forIndexOf:anObject usingSortBlock:sortBlock |
|
377 "search the index at which to insert anObject. |
|
378 Can also be used to search for an existing element |
|
379 by checking if the element at the returned index is the one we look for. |
|
380 Uses a binarySearch since we can depend on the elements being on sorted order. |
|
381 The returned index is a physical one, for accessing contentsArray. |
|
382 This is only to be used for arrays which are known to be sorted." |
|
383 |
|
384 |low "{ Class: SmallInteger}" |
|
385 high "{ Class: SmallInteger}" |
|
386 middle "{ Class: SmallInteger}" |
|
387 element| |
|
388 |
|
389 " |
|
390 we can of course use a binary search - since the elements are sorted |
|
391 " |
|
392 low := firstIndex. |
|
393 high := lastIndex. |
|
394 [low > high] whileFalse:[ |
|
395 middle := (low + high) // 2. |
|
396 element := aSortedArray at:middle. |
|
397 (sortBlock value:element value:anObject) ifTrue:[ |
|
398 "middleelement is smaller than object" |
|
399 low := middle + 1 |
|
400 ] ifFalse:[ |
|
401 high := middle - 1 |
|
402 ] |
|
403 ]. |
|
404 ^ low |
|
405 |
|
406 " |
|
407 SortedCollection |
|
408 binarySearch:#(1 2 3 4 7 99 1313 981989 898989898) |
|
409 from:1 to:9 |
|
410 forIndexOf:99 |
|
411 usingSortBlock:[:a :b | a < b ] |
|
412 " |
|
413 |
|
414 "Modified: 12.4.1996 / 13:22:03 / cg" |
|
415 ! ! |
328 ! ! |
416 |
329 |
417 !SortedCollection methodsFor:'accessing'! |
330 !SortedCollection methodsFor:'accessing'! |
418 |
331 |
419 largest:n |
332 largest:n |
587 |
500 |
588 This should be used when a number of elements is to be added. |
501 This should be used when a number of elements is to be added. |
589 Notice, that quicksort degenerates to a veeery slow bubble-like |
502 Notice, that quicksort degenerates to a veeery slow bubble-like |
590 sort when a collection of already sorted elements is given to it. |
503 sort when a collection of already sorted elements is given to it. |
591 Therefore, adding chunks is better done by sorting the chunk and merging |
504 Therefore, adding chunks is better done by sorting the chunk and merging |
592 it in, instead of resorting the receiver." |
505 it in, instead of resorting the receiver. |
|
506 |
|
507 aSortedCollection must be sorted by the same sortBlock as myself!!" |
593 |
508 |
594 |newContentsArray |
509 |newContentsArray |
595 contentsArray2 |
510 contentsArray2 |
596 destIndex "{ Class: SmallInteger }" |
511 destIndex "{ Class: SmallInteger }" |
597 n1 "{ Class: SmallInteger }" |
512 n1 "{ Class: SmallInteger }" |
601 last1 "{ Class: SmallInteger }" |
516 last1 "{ Class: SmallInteger }" |
602 last2 "{ Class: SmallInteger }" |
517 last2 "{ Class: SmallInteger }" |
603 end1Reached end2Reached |
518 end1Reached end2Reached |
604 el1 el2 | |
519 el1 el2 | |
605 |
520 |
606 n1 := self size. |
|
607 n2 := aSortedCollection size. |
521 n2 := aSortedCollection size. |
608 |
|
609 n1 == 0 ifTrue:[ |
|
610 ^ aSortedCollection. |
|
611 ]. |
|
612 n2 == 0 ifTrue:[ |
522 n2 == 0 ifTrue:[ |
613 ^ self. |
523 ^ self. |
614 ]. |
524 ]. |
615 |
525 |
616 newContentsArray := Array new:(n1 + n2). |
526 aSortedCollection isSortedCollection ifTrue:[ |
617 destIndex := 1. |
527 contentsArray2 := aSortedCollection contentsArray. |
618 |
528 srcIndex2 := aSortedCollection firstIndex. |
619 (aSortedCollection isSortedBy:sortBlock) ifTrue:[ |
|
620 aSortedCollection isSortedCollection ifTrue:[ |
|
621 contentsArray2 := aSortedCollection contentsArray. |
|
622 srcIndex2 := aSortedCollection firstIndex. |
|
623 ] ifFalse:[ |
|
624 contentsArray2 := aSortedCollection. |
|
625 srcIndex2 := 1. |
|
626 ] |
|
627 ] ifFalse:[ |
529 ] ifFalse:[ |
628 contentsArray2 := aSortedCollection. |
530 contentsArray2 := aSortedCollection. |
629 srcIndex2 := 1. |
531 srcIndex2 := 1. |
630 ]. |
532 ]. |
|
533 |
|
534 n1 := self size. |
|
535 n1 == 0 ifTrue:[ |
|
536 firstIndex := srcIndex2. |
|
537 lastIndex := firstIndex + n2 - 1. |
|
538 contentsArray := contentsArray2 copy. |
|
539 ^ self. |
|
540 ]. |
|
541 |
|
542 newContentsArray := Array new:(n1 + n2). |
|
543 destIndex := 1. |
631 |
544 |
632 last2 := srcIndex2 + n2 -1. |
545 last2 := srcIndex2 + n2 -1. |
633 |
546 |
634 srcIndex1 := firstIndex. |
547 srcIndex1 := firstIndex. |
635 last1 := srcIndex1 + n1 -1. |
548 last1 := srcIndex1 + n1 -1. |
842 |
755 |
843 indexForInserting:anObject |
756 indexForInserting:anObject |
844 "search the index at which to insert anObject. |
757 "search the index at which to insert anObject. |
845 Can also be used to search for an existing element |
758 Can also be used to search for an existing element |
846 by checking if the element at the returned index is the one we look for. |
759 by checking if the element at the returned index is the one we look for. |
847 Uses a binarySearch since we can depend on the elements being on sorted order. |
760 Uses a binarySearch since we can depend on the elements being in sorted order. |
848 The returned index is a physical one, for accessing contentsArray." |
761 The returned index is a physical one, for accessing contentsArray." |
849 |
762 |
850 ^ self class |
763 |low "{ Class: SmallInteger}" |
851 binarySearch:contentsArray |
764 high "{ Class: SmallInteger}" |
852 from:firstIndex to:lastIndex |
765 middle "{ Class: SmallInteger}" |
853 forIndexOf:anObject usingSortBlock:sortBlock |
766 element| |
|
767 |
|
768 " |
|
769 we can of course use a binary search - since the elements are sorted |
|
770 " |
|
771 low := firstIndex. |
|
772 high := lastIndex. |
|
773 [low > high] whileFalse:[ |
|
774 middle := (low + high) // 2. |
|
775 element := contentsArray at:middle. |
|
776 (sortBlock value:element value:anObject) ifTrue:[ |
|
777 "middleelement is smaller than object" |
|
778 low := middle + 1 |
|
779 ] ifFalse:[ |
|
780 high := middle - 1 |
|
781 ] |
|
782 ]. |
|
783 ^ low |
854 |
784 |
855 " |
785 " |
856 #(1 2 3 4 7 99 1313 981989 898989898) asSortedCollection indexForInserting:50 |
786 #(1 2 3 4 7 99 1313 981989 898989898) asSortedCollection indexForInserting:50 |
857 |
787 |
858 #(1.0 2.0 3 4 7 49.0 51.0 99 1313 981989 898989898) asSortedCollection indexForInserting:50 |
788 #(1.0 2.0 3 4 7 49.0 51.0 99 1313 981989 898989898) asSortedCollection indexForInserting:50 |