--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/SegmentedOrderedCollection.st Mon Mar 18 22:48:03 2013 +0100
@@ -0,0 +1,260 @@
+"{ Package: 'stx:libbasic2' }"
+
+SequenceableCollection subclass:#SegmentedOrderedCollection
+ instanceVariableNames:'segments maxSegmentSize tally'
+ classVariableNames:''
+ poolDictionaries:''
+ category:'Collections-Sequenceable'
+!
+
+!SegmentedOrderedCollection class methodsFor:'documentation'!
+
+documentation
+"
+ SegmentedOrderedCollections keep their elements in chunks (segments),
+ allowing for relatively fast adding/removing at either end, AND inside the collection.
+ For huge collections, performance is better for add/remove inside.
+ Hoeverer, notice: when only removing at either end only, an OrderedCollection is much faster.
+
+ Usable for a replacement for OrderedCollections with big size (say > 10000),
+ in which elements are going to be removed from the inside.
+
+ Possibly unfinished (needs 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.
+! !
+
+!SegmentedOrderedCollection methodsFor:'accessing'!
+
+at:index
+ |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
+ |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
+ tally == 0 ifTrue:[^ self emptyCollectionError].
+ ^ segments first first
+!
+
+last
+ tally == 0 ifTrue:[^ self emptyCollectionError].
+ ^ segments last last
+! !
+
+!SegmentedOrderedCollection methodsFor:'adding & removing'!
+
+add:anObject
+ "add anObject to the end."
+
+ |seg|
+
+ (seg := segments last) size >= maxSegmentSize ifTrue:[
+ self splitSegmentAt:(segments size).
+ seg := segments last.
+ ].
+ seg add:anObject.
+ tally := tally + 1.
+!
+
+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
+ |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
+ |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:[
+ (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
+ |seg el|
+
+ tally == 0 ifTrue:[
+ ^ self emptyCollectionError
+ ].
+ seg := segments last.
+ el := seg removeLast.
+ seg isEmpty ifTrue:[
+ segments removeLast
+ ].
+ tally := tally - 1.
+ ^ el
+!
+
+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:'enumerating'!
+
+do:aBlock
+ segments do:[:seg |
+ seg do:aBlock
+ ].
+!
+
+keysAndValuesDo:aBlock
+ |idx|
+
+ idx := 1.
+ segments do:[:seg |
+ seg do:[:each |
+ aBlock value:idx value:each.
+ idx := idx + 1.
+ ]
+ ].
+! !
+
+!SegmentedOrderedCollection methodsFor:'initialization'!
+
+initialize
+ "Invoked when a new instance is created."
+
+ segments := OrderedCollection with:(OrderedCollection new:10).
+ maxSegmentSize := 200.
+ tally := 0.
+! !
+
+!SegmentedOrderedCollection methodsFor:'queries'!
+
+size
+ ^ tally
+! !
+
+!SegmentedOrderedCollection class methodsFor:'documentation'!
+
+version
+ ^ '$Header: /cvs/stx/stx/libbasic2/SegmentedOrderedCollection.st,v 1.1 2013-03-18 21:48:03 cg Exp $'
+!
+
+version_CVS
+ ^ '$Header: /cvs/stx/stx/libbasic2/SegmentedOrderedCollection.st,v 1.1 2013-03-18 21:48:03 cg Exp $'
+! !
+