"{ Package: 'stx:libbasic2' }"
SequenceableCollection subclass:#SegmentedOrderedCollection
instanceVariableNames:'segments maxSegmentSize tally'
classVariableNames:''
poolDictionaries:''
category:'Collections-Sequenceable'
!
!SegmentedOrderedCollection class methodsFor:'documentation'!
documentation
"
SegmentedOrderedCollections are intended as a replacement for huge OrderedCollections.
They keep their elements in chunks (segments), allowing for fast
adding/removing at either end AND relatively fast add/remove inside the collection.
For huge collections, the performance is much better when adding/removing inner elements.
However, notice: when only removing at either end only, an OrderedCollection is much faster.
The break-even in performance depends on the number of elements and the usage pattern.
Consider it with (say) > 10000 elements and many adds/removes from the inside.
Possibly unfinished (may need optimized search and replace).
[author:]
Claus Gittinger
[see also:]
Array OrderedCollection BTree
"
! !
!SegmentedOrderedCollection class methodsFor:'instance creation'!
new
"return an initialized instance"
^ self basicNew initialize.
!
new:size
"return an initialized instance with space for size elements.
However, be aware that the logical size is 0"
^ self basicNew initialize.
! !
!SegmentedOrderedCollection methodsFor:'accessing'!
at:index
"return the element at index, anInteger"
|segStart segEnd|
(index between:1 and:tally) ifFalse:[
^ self indexNotIntegerOrOutOfBounds:index
].
segStart := 1.
segments do:[:seg |
segEnd := segStart + (seg size - 1).
(index between:segStart and:segEnd) ifTrue:[
^ seg at:(index - segStart + 1).
].
segStart := segEnd + 1.
].
self error:'oops - should not be here'
!
at:index put:newElement
"set the element at index, to be anInteger.
Return anObject (sigh)."
|segStart segEnd|
(index between:1 and:tally) ifFalse:[
^ self indexNotIntegerOrOutOfBounds:index
].
segStart := 1.
segments do:[:seg |
segEnd := segStart + (seg size - 1).
(index between:segStart and:segEnd) ifTrue:[
^ seg at:(index - segStart + 1) put:newElement.
].
segStart := segEnd + 1.
].
self error:'oops - should not be here'
!
first
"return the first element"
tally == 0 ifTrue:[^ self emptyCollectionError].
^ segments first first
!
last
"return the last element"
tally == 0 ifTrue:[^ self emptyCollectionError].
^ segments last last
! !
!SegmentedOrderedCollection methodsFor:'adding & removing'!
add:anObject
"add anObject to the end.
Returns the object (sigh)"
|seg|
(seg := segments last) size >= maxSegmentSize ifTrue:[
self splitSegmentAt:(segments size).
seg := segments last.
].
seg add:anObject.
tally := tally + 1.
^ anObject.
!
add:anObject beforeIndex:index
"insert the first argument, anObject into the collection before slot index.
Return the receiver (sigh - ST-80 compatibility).
Notice, that this is modifies the receiver NOT a copy."
|prevSeg segStart|
index == (tally+1) ifTrue:[
^ self add:anObject
].
segStart := 1.
segments do:[:seg |
|segEnd|
segEnd := segStart + (seg size - 1).
(index between:segStart and:segEnd) ifTrue:[
index == segStart ifTrue:[
prevSeg notNil ifTrue:[
prevSeg size < seg size ifTrue:[
prevSeg add:anObject.
tally := tally + 1.
^ anObject
].
].
].
seg add:anObject beforeIndex:(index - segStart + 1).
tally := tally + 1.
^ anObject
].
segStart := segEnd + 1.
prevSeg := seg.
].
self error:'oops - should not be here'
!
addFirst:anObject
"add anObject to the beginning (insert as new first element)."
|seg|
(seg := segments first) size >= maxSegmentSize ifTrue:[
self splitSegmentAt:1.
seg := segments first.
].
seg addFirst:anObject.
tally := tally + 1.
!
removeFirst
"remove the first element from the collection; return the element.
If there is no element in the receiver collection, raise an error."
|seg el|
tally == 0 ifTrue:[
^ self emptyCollectionError
].
seg := segments first.
el := seg removeFirst.
seg isEmpty ifTrue:[
segments removeFirst
].
tally := tally - 1.
^ el
!
removeFromIndex:startIndex toIndex:endIndex
"remove the elements stored under startIndex up to and including
the elements under stopIndex.
Return the receiver.
Returning the receiver here is a historic leftover - it may change.
Please use yourself in a cascade, if you need the receiver's value
when using this method."
|segStart segEnd removing segIndex nextSegIndex seg|
(startIndex between:1 and:tally) ifFalse:[
^ self indexNotIntegerOrOutOfBounds:startIndex
].
(endIndex between:1 and:tally) ifFalse:[
^ self indexNotIntegerOrOutOfBounds:endIndex
].
segStart := 1.
segIndex := 1.
removing := false.
[true] whileTrue:[
seg := segments at:segIndex.
nextSegIndex := segIndex + 1.
segEnd := segStart + (seg size - 1).
removing ifFalse:[
"still searching for the segment"
(startIndex between:segStart and:segEnd) ifTrue:[
(endIndex between:segStart and:segEnd) ifTrue:[
seg removeFromIndex:(startIndex - segStart + 1) toIndex:(endIndex - segStart + 1).
seg isEmpty ifTrue:[
segments removeAtIndex:segIndex.
].
tally := tally - (endIndex - startIndex + 1).
^ self.
].
seg removeFromIndex:(startIndex - segStart + 1).
seg isEmpty ifTrue:[
segments removeAtIndex:segIndex.
nextSegIndex := segIndex.
].
removing := true.
].
] ifTrue:[
(endIndex between:segStart and:segEnd) ifTrue:[
seg removeFromIndex:1 toIndex:(endIndex - segStart + 1).
seg isEmpty ifTrue:[
segments removeAtIndex:segIndex.
].
tally := tally - (endIndex - startIndex + 1).
^ self.
] ifFalse:[
"/ remove the whole segment
segments removeAtIndex:segIndex.
nextSegIndex := segIndex.
]
].
segStart := segEnd + 1.
segIndex := nextSegIndex.
].
self halt:'should not be here'
!
removeLast
"remove the last element from the collection; return the element"
|seg el|
tally == 0 ifTrue:[
^ self emptyCollectionError
].
seg := segments last.
el := seg removeLast.
seg isEmpty ifTrue:[
segments removeLast
].
tally := tally - 1.
^ el
! !
!SegmentedOrderedCollection methodsFor:'enumerating'!
do:aBlock
"evaluate the argument, aBlock for every element in the collection."
segments do:[:seg |
seg do:aBlock
].
!
keysAndValuesDo:aBlock
"evaluate the argument, aBlock for every element in the collection,
passing both index and element as arguments."
|idx|
idx := 1.
segments do:[:seg |
seg do:[:each |
aBlock value:idx value:each.
idx := idx + 1.
]
].
! !
!SegmentedOrderedCollection methodsFor:'grow & shrink'!
grow:newSize
"adjust the logical size to newSize"
|numExtraSegments segStart segEnd segIndex seg|
newSize == 0 ifTrue:[
segments := OrderedCollection new:2.
tally := 0.
^ self
].
newSize < tally ifTrue:[
"/ shrinking
segStart := 1.
segIndex := 1.
[true] whileTrue:[
seg := segments at:segIndex.
segEnd := segStart + (seg size - 1).
(newSize between:segStart and:segEnd) ifTrue:[
(segments at:segIndex) removeFromIndex:(newSize - segStart + 1 + 1).
segments removeFromIndex:segIndex+1.
tally := newSize.
^ self
].
segStart := segEnd + 1.
segIndex := segIndex + 1.
].
"/ not reached
].
"/ growing
numExtraSegments := (newSize - tally) // maxSegmentSize + 1.
numExtraSegments timesRepeat:[
segments add:((OrderedCollection new:maxSegmentSize) grow:maxSegmentSize)
].
tally := newSize
! !
!SegmentedOrderedCollection methodsFor:'initialization'!
initialize
"Invoked when a new instance is created."
segments := OrderedCollection with:(OrderedCollection new:10).
maxSegmentSize := 200.
tally := 0.
! !
!SegmentedOrderedCollection methodsFor:'private'!
splitSegmentAt:segmentIndex
|seg rightPart|
seg := segments at:segmentIndex.
rightPart := OrderedCollection new:20.
rightPart grow:10.
rightPart replaceFrom:1 to:10 with:seg startingAt:(seg size - 9).
seg removeFromIndex:(seg size - 9) toIndex:seg size.
segments add:rightPart afterIndex:segmentIndex.
! !
!SegmentedOrderedCollection methodsFor:'queries'!
isFixedSize
"return true if the receiver cannot grow"
^ false
!
size
"return the number of elements in the collection"
^ tally
! !
!SegmentedOrderedCollection class methodsFor:'documentation'!
version
^ '$Header: /cvs/stx/stx/libbasic2/SegmentedOrderedCollection.st,v 1.5 2013-06-25 11:23:35 cg Exp $'
!
version_CVS
^ '$Header: /cvs/stx/stx/libbasic2/SegmentedOrderedCollection.st,v 1.5 2013-06-25 11:23:35 cg Exp $'
! !