--- a/SortedCollection.st Sun Aug 05 18:38:41 2012 +0200
+++ b/SortedCollection.st Mon Aug 06 12:44:52 2012 +0200
@@ -62,6 +62,9 @@
... be aware, that the sortBlock has an effect on a few algorithms
found here; especially #indexForInserting is critical.)
+ [caveat:]
+ a balanced tree may be a better choice, as inserting may be slow when
+ elements have to be shifted.
[author:]
Claus Gittinger
@@ -324,95 +327,6 @@
^ self withAll:aCollection sortBlock:aBlock
! !
-!SortedCollection class methodsFor:'helpers'!
-
-binarySearch:aSortedArray for:anObject
- "search for an existing element; return true if found.
- by checking if the element at the returned index is the one we look for.
- Uses a binarySearch since we can depend on the elements being on sorted order.
- The returned index is a physical one, for accessing contentsArray.
- This is only to be used for arrays which are known to be sorted."
-
- |idx|
-
- idx := self
- binarySearch:aSortedArray
- forIndexOf:anObject.
- ^ idx <= aSortedArray size
- and:[ (aSortedArray at:idx) = anObject ].
-
- "
- SortedCollection
- binarySearch:#(1 2 3 4 7 99 1313 981989 898989898)
- for:898989898
- "
-!
-
-binarySearch:aSortedArray forIndexOf:anObject
- "search the index at which to insert anObject.
- Can also be used to search for an existing element
- by checking if the element at the returned index is the one we look for.
- Uses a binarySearch since we can depend on the elements being on sorted order.
- The returned index is a physical one, for accessing contentsArray.
- This is only to be used for arrays which are known to be sorted."
-
- ^ self
- binarySearch:aSortedArray
- from:1 to:(aSortedArray size)
- forIndexOf:anObject
- usingSortBlock:[:a :b | a < b ]
-
- "
- SortedCollection
- binarySearch:#(1 2 3 4 7 99 1313 981989 898989898)
- from:1 to:9
- forIndexOf:99
- usingSortBlock:[:a :b | a < b ]
- "
-
- "Modified: 12.4.1996 / 13:22:03 / cg"
-!
-
-binarySearch:aSortedArray from:firstIndex to:lastIndex forIndexOf:anObject usingSortBlock:sortBlock
- "search the index at which to insert anObject.
- Can also be used to search for an existing element
- by checking if the element at the returned index is the one we look for.
- Uses a binarySearch since we can depend on the elements being on sorted order.
- The returned index is a physical one, for accessing contentsArray.
- This is only to be used for arrays which are known to be sorted."
-
- |low "{ Class: SmallInteger}"
- high "{ Class: SmallInteger}"
- middle "{ Class: SmallInteger}"
- element|
-
- "
- we can of course use a binary search - since the elements are sorted
- "
- low := firstIndex.
- high := lastIndex.
- [low > high] whileFalse:[
- middle := (low + high) // 2.
- element := aSortedArray at:middle.
- (sortBlock value:element value:anObject) ifTrue:[
- "middleelement is smaller than object"
- low := middle + 1
- ] ifFalse:[
- high := middle - 1
- ]
- ].
- ^ low
-
- "
- SortedCollection
- binarySearch:#(1 2 3 4 7 99 1313 981989 898989898)
- from:1 to:9
- forIndexOf:99
- usingSortBlock:[:a :b | a < b ]
- "
-
- "Modified: 12.4.1996 / 13:22:03 / cg"
-! !
!SortedCollection methodsFor:'accessing'!
@@ -840,28 +754,6 @@
!SortedCollection methodsFor:'private'!
-indexForInserting:anObject
- "search the index at which to insert anObject.
- Can also be used to search for an existing element
- by checking if the element at the returned index is the one we look for.
- Uses a binarySearch since we can depend on the elements being on sorted order.
- The returned index is a physical one, for accessing contentsArray."
-
- ^ self class
- binarySearch:contentsArray
- from:firstIndex to:lastIndex
- forIndexOf:anObject usingSortBlock:sortBlock
-
- "
- #(1 2 3 4 7 99 1313 981989 898989898) asSortedCollection indexForInserting:50
-
- #(1.0 2.0 3 4 7 49.0 51.0 99 1313 981989 898989898) asSortedCollection indexForInserting:50
-
- "
-
- "Modified: 12.4.1996 / 13:22:03 / cg"
-!
-
setSortBlock: aSortBlock
"set the sortblock without resorting - private only"
@@ -1060,7 +952,7 @@
!SortedCollection class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic/SortedCollection.st,v 1.72 2012-04-21 17:38:20 stefan Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic/SortedCollection.st,v 1.73 2012-08-06 10:44:52 cg Exp $'
! !
SortedCollection initialize!