#FEATURE by cg
class: OrderedCollection
refactored to allow subclasses to use a different
underlying container (see WeakOrderedCollection)
added: #containerClass
changed:
#grow:
#initContents:
#makeRoomAtFront
#makeRoomAtIndex:
#makeRoomAtIndex:for:
#makeRoomAtLast
--- a/OrderedCollection.st Mon Jul 30 11:45:35 2018 +0200
+++ b/OrderedCollection.st Mon Jul 30 12:13:09 2018 +0200
@@ -1724,54 +1724,67 @@
oldSize := lastIndex - firstIndex + 1.
newSize ~~ oldSize ifTrue:[
- newLast := firstIndex + newSize - 1.
- newSize < oldSize ifTrue:[
- newSize == 0 ifTrue:[
- self initContents:0.
- ^ self.
- ].
- oldLast := lastIndex.
- lastIndex := newLast.
- "
- nil out rest, to give GC a chance to reclaim things
- "
- contentsArray from:lastIndex + 1 to:oldLast put:nil.
- ] ifFalse:[
- newLast <= contentsArray size ifTrue:[
- lastIndex := newLast.
- ^ self
- ].
-
- newContents := Array basicNew:newSize.
- newContents replaceFrom:1 to:oldSize with:contentsArray startingAt:firstIndex.
- contentsArray := newContents.
- firstIndex := 1.
- lastIndex := newSize
- ]
+ newLast := firstIndex + newSize - 1.
+ newSize < oldSize ifTrue:[
+ newSize == 0 ifTrue:[
+ self initContents:0.
+ ^ self.
+ ].
+ oldLast := lastIndex.
+ lastIndex := newLast.
+ "
+ nil out rest, to give GC a chance to reclaim things
+ "
+ contentsArray from:lastIndex + 1 to:oldLast put:nil.
+ ] ifFalse:[
+ newLast <= contentsArray size ifTrue:[
+ lastIndex := newLast.
+ ^ self
+ ].
+
+ newContents := self containerClass basicNew:newSize.
+ newContents replaceFrom:1 to:oldSize with:contentsArray startingAt:firstIndex.
+ contentsArray := newContents.
+ firstIndex := 1.
+ lastIndex := newSize
+ ]
]
+
+ "Modified: / 30-07-2018 / 12:06:33 / Claus Gittinger"
! !
!OrderedCollection methodsFor:'private'!
+containerClass
+ "the class of the underlying container.
+ Here Array; redefined in WeakOrderedCollection to use a WeakArray"
+
+ ^ Array
+
+ "Created: / 30-07-2018 / 12:06:28 / Claus Gittinger"
+!
+
initContents:size
"setup the receiver-collection to hold size entries"
size == 0 ifTrue:[
- contentsArray := #(). "save memory by using a shared instance"
+ contentsArray := #(). "save memory by using a shared instance"
] ifFalse:[
- contentsArray := Array basicNew:size.
+ contentsArray := self containerClass basicNew:size.
].
firstIndex := 1.
lastIndex := 0
+
+ "Modified: / 30-07-2018 / 12:06:49 / Claus Gittinger"
!
makeRoomAtFront
"grow/shift the contents for more room at the beginning.
Does not change the logical size.
i.e. the contents array is changed from:
- #(1 2 3 4 5 6) -> #(nil 1 2 3 4 5 6)
+ #(1 2 3 4 5 6) -> #(nil 1 2 3 4 5 6)
and the start/stopIndices are adjusted as required"
|newContents
@@ -1784,9 +1797,9 @@
sz := lastIndex - firstIndex + 1.
((oldSize == 0) or:[sz == 0]) ifTrue:[
- contentsArray := Array basicNew:MinContentsArraySize.
- firstIndex := 2. lastIndex := 1.
- ^ self
+ contentsArray := self containerClass basicNew:MinContentsArraySize.
+ firstIndex := 2. lastIndex := 1.
+ ^ self
].
"
@@ -1795,28 +1808,29 @@
which get elements removed at the end and added at front.
"
oldSize > (sz * 2) ifTrue:[
- startIndex := oldSize // 4.
- startIndex > 1 ifTrue:[
- contentsArray
- replaceFrom:startIndex to:(startIndex + sz - 1)
- with:contentsArray startingAt:1.
- contentsArray from:1 to:(startIndex - 1) put:nil.
- firstIndex := startIndex.
- lastIndex := startIndex + sz - 1.
- ^ self
- ]
+ startIndex := oldSize // 4.
+ startIndex > 1 ifTrue:[
+ contentsArray
+ replaceFrom:startIndex to:(startIndex + sz - 1)
+ with:contentsArray startingAt:1.
+ contentsArray from:1 to:(startIndex - 1) put:nil.
+ firstIndex := startIndex.
+ lastIndex := startIndex + sz - 1.
+ ^ self
+ ]
].
newSize := oldSize * 2.
- newContents := Array basicNew:newSize.
+ newContents := self containerClass basicNew:newSize.
newContents
- replaceFrom:(oldSize + 1) to:newSize
- with:contentsArray startingAt:1.
+ replaceFrom:(oldSize + 1) to:newSize
+ with:contentsArray startingAt:1.
contentsArray := newContents.
firstIndex := firstIndex + oldSize.
lastIndex := lastIndex + oldSize
"Created: / 08-11-1995 / 12:47:49 / cg"
"Modified: / 22-10-2008 / 17:10:13 / cg"
+ "Modified: / 30-07-2018 / 12:08:34 / Claus Gittinger"
!
makeRoomAtIndex:whereToMakeEmptySlot
@@ -1844,105 +1858,106 @@
last := lastIndex.
(first > 1) ifTrue:[
- "there is room at the beginning"
-
- shiftLeft := true.
-
- index == first ifFalse:[
- "/ so, we'd have to copy all elements before that index
- "/ one slot towards the containers beginning ...
- "/ if there is also space at the end, AND the number of
- "/ elements after the index is smaller than the number before,
- "/ copy the remaining elements. To copy the least possible number.
-
- (last - index) < (index - first) ifTrue:[
- last < oldSize ifTrue:[
- shiftLeft := false.
- shiftRight := true.
- ]
- ]
- ]
+ "there is room at the beginning"
+
+ shiftLeft := true.
+
+ index == first ifFalse:[
+ "/ so, we'd have to copy all elements before that index
+ "/ one slot towards the containers beginning ...
+ "/ if there is also space at the end, AND the number of
+ "/ elements after the index is smaller than the number before,
+ "/ copy the remaining elements. To copy the least possible number.
+
+ (last - index) < (index - first) ifTrue:[
+ last < oldSize ifTrue:[
+ shiftLeft := false.
+ shiftRight := true.
+ ]
+ ]
+ ]
] ifFalse:[
- last < oldSize ifTrue:[
- shiftRight := true
- ]
+ last < oldSize ifTrue:[
+ shiftRight := true
+ ]
].
shiftLeft == true ifTrue:[
- "there is room at the beginning"
-
- index == first ifFalse:[
- contentsArray
- replaceFrom:(first - 1) to:(index - 2)
- with:contentsArray startingAt:first.
- contentsArray at:index-1 put:nil.
- ].
- firstIndex := first - 1.
- ^ index - 1
+ "there is room at the beginning"
+
+ index == first ifFalse:[
+ contentsArray
+ replaceFrom:(first - 1) to:(index - 2)
+ with:contentsArray startingAt:first.
+ contentsArray at:index-1 put:nil.
+ ].
+ firstIndex := first - 1.
+ ^ index - 1
].
shiftRight == true ifTrue:[
- "there is room at the end"
-
- last := last + 1.
- index == last ifFalse:[
- contentsArray
- replaceFrom:(index + 1) to:last
- with:contentsArray startingAt:index.
- contentsArray at:index put:nil
- ].
- lastIndex := last.
- ^ index
+ "there is room at the end"
+
+ last := last + 1.
+ index == last ifFalse:[
+ contentsArray
+ replaceFrom:(index + 1) to:last
+ with:contentsArray startingAt:index.
+ contentsArray at:index put:nil
+ ].
+ lastIndex := last.
+ ^ index
].
"/ no space at either end
oldSize < MinContentsArraySize ifTrue:[
- newSize := MinContentsArraySize
+ newSize := MinContentsArraySize
] ifFalse:[
- newSize := oldSize * 2.
+ newSize := oldSize * 2.
].
- newContents := Array basicNew:newSize.
+ newContents := self containerClass basicNew:newSize.
index == first ifTrue:[
- "/ if there is a lot at the end (> 50), make all new space at the beginning.
- "/ otherwise make 3/4 of the new space to the beginning, 1/4 to the end
- oldSize ~~ 0 ifTrue:[
- (last < (oldSize - 50)) ifTrue:[
- lastIndex := newSize - (oldSize-last).
- firstIndex := lastIndex - (last - first).
- ] ifFalse:[
- firstIndex := oldSize * 3 // 4.
- firstIndex < 2 ifTrue:[firstIndex := 2]. "/ pathological case (was explicitly allocated with size<MinSize
- lastIndex := firstIndex + (last - first).
- ].
- newContents
- replaceFrom:firstIndex to:lastIndex
- with:contentsArray startingAt:first.
- ].
- contentsArray := newContents.
- firstIndex := firstIndex - 1.
-
- ^ firstIndex.
+ "/ if there is a lot at the end (> 50), make all new space at the beginning.
+ "/ otherwise make 3/4 of the new space to the beginning, 1/4 to the end
+ oldSize ~~ 0 ifTrue:[
+ (last < (oldSize - 50)) ifTrue:[
+ lastIndex := newSize - (oldSize-last).
+ firstIndex := lastIndex - (last - first).
+ ] ifFalse:[
+ firstIndex := oldSize * 3 // 4.
+ firstIndex < 2 ifTrue:[firstIndex := 2]. "/ pathological case (was explicitly allocated with size<MinSize
+ lastIndex := firstIndex + (last - first).
+ ].
+ newContents
+ replaceFrom:firstIndex to:lastIndex
+ with:contentsArray startingAt:first.
+ ].
+ contentsArray := newContents.
+ firstIndex := firstIndex - 1.
+
+ ^ firstIndex.
] ifFalse:[
- oldSize ~~ 0 ifTrue:[
- newContents
- replaceFrom:1 to:(index - first)
- with:contentsArray startingAt:first.
-
- index <= last ifTrue:[
- newContents
- replaceFrom:(index - first + 2) to:(last - first + 2)
- with:contentsArray startingAt:index.
- ].
- ].
- contentsArray := newContents.
- firstIndex := 1.
- lastIndex := last - first + 2.
-
- "/ return the modified index
- ^ index - (first - firstIndex).
+ oldSize ~~ 0 ifTrue:[
+ newContents
+ replaceFrom:1 to:(index - first)
+ with:contentsArray startingAt:first.
+
+ index <= last ifTrue:[
+ newContents
+ replaceFrom:(index - first + 2) to:(last - first + 2)
+ with:contentsArray startingAt:index.
+ ].
+ ].
+ contentsArray := newContents.
+ firstIndex := 1.
+ lastIndex := last - first + 2.
+
+ "/ return the modified index
+ ^ index - (first - firstIndex).
].
"Modified: / 22-10-2008 / 17:11:06 / cg"
+ "Modified: / 30-07-2018 / 12:07:10 / Claus Gittinger"
!
makeRoomAtIndex:whereToMakeEmptySlots for:howMany
@@ -1974,44 +1989,44 @@
shiftLeft := shiftRight := false.
((first > howMany) and:[first > oneFourthOfSize]) ifTrue:[
- "there is room (>25%) at the beginning"
- shiftLeft := true.
+ "there is room (>25%) at the beginning"
+ shiftLeft := true.
] ifFalse:[
- ((last + howMany) <= oldSize
- and:[last < (oneFourthOfSize * 3)]) ifTrue:[
- shiftRight := true
- ]
+ ((last + howMany) <= oldSize
+ and:[last < (oneFourthOfSize * 3)]) ifTrue:[
+ shiftRight := true
+ ]
].
shiftLeft == true ifTrue:[
- "there is room at the beginning"
-
- index == first ifFalse:[
- contentsArray
- replaceFrom:(first - howMany)
- to:(index - howMany - 1)
- with:contentsArray
- startingAt:first.
- contentsArray from:index-howMany to:index-1 put:nil.
- ].
- firstIndex := first - howMany.
- ^ index - howMany
+ "there is room at the beginning"
+
+ index == first ifFalse:[
+ contentsArray
+ replaceFrom:(first - howMany)
+ to:(index - howMany - 1)
+ with:contentsArray
+ startingAt:first.
+ contentsArray from:index-howMany to:index-1 put:nil.
+ ].
+ firstIndex := first - howMany.
+ ^ index - howMany
].
shiftRight == true ifTrue:[
- "there is room at the end"
-
- last := last + howMany.
- index == last ifFalse:[
- contentsArray
- replaceFrom:(index + howMany)
- to:last
- with:contentsArray
- startingAt:index.
- contentsArray from:index to:index+howMany-1 put:nil
- ].
- lastIndex := last.
- ^ index
+ "there is room at the end"
+
+ last := last + howMany.
+ index == last ifFalse:[
+ contentsArray
+ replaceFrom:(index + howMany)
+ to:last
+ with:contentsArray
+ startingAt:index.
+ contentsArray from:index to:index+howMany-1 put:nil
+ ].
+ lastIndex := last.
+ ^ index
].
newSize := (oldSize+howMany) nextPowerOf2.
@@ -2020,22 +2035,22 @@
"/ newSize := (newSize * 2) max:howMany
"/ ].
- newContents := Array basicNew:newSize.
+ newContents := self containerClass basicNew:newSize.
oldSize ~~ 0 ifTrue:[
- index > first ifTrue:[
- newContents
- replaceFrom:1
- to:(index - first)
- with:contentsArray
- startingAt:first.
- ].
- index <= last ifTrue:[
- newContents
- replaceFrom:(index - first + howMany + 1)
- to:(last - first + howMany + 1)
- with:contentsArray
- startingAt:(index).
- ].
+ index > first ifTrue:[
+ newContents
+ replaceFrom:1
+ to:(index - first)
+ with:contentsArray
+ startingAt:first.
+ ].
+ index <= last ifTrue:[
+ newContents
+ replaceFrom:(index - first + howMany + 1)
+ to:(last - first + howMany + 1)
+ with:contentsArray
+ startingAt:(index).
+ ].
].
contentsArray := newContents.
firstIndex := 1.
@@ -2044,7 +2059,8 @@
"/ return the modified index
^ index - (first - firstIndex).
- "Modified: 15.4.1997 / 12:34:16 / cg"
+ "Modified: / 15-04-1997 / 12:34:16 / cg"
+ "Modified: / 30-07-2018 / 12:07:16 / Claus Gittinger"
!
makeRoomAtLast
@@ -2068,32 +2084,33 @@
elements removed at front and added at the end.
"
oldSize > (sz * 2) ifTrue:[
- startIndex := firstIndex // 4.
- startIndex == 0 ifTrue:[
- startIndex := 1
- ].
- contentsArray
- replaceFrom:startIndex to:startIndex + sz - 1
- with:contentsArray startingAt:firstIndex.
- contentsArray from:startIndex + sz to:lastIndex put:nil.
- firstIndex := startIndex.
- lastIndex := startIndex + sz - 1.
- ^ self
+ startIndex := firstIndex // 4.
+ startIndex == 0 ifTrue:[
+ startIndex := 1
+ ].
+ contentsArray
+ replaceFrom:startIndex to:startIndex + sz - 1
+ with:contentsArray startingAt:firstIndex.
+ contentsArray from:startIndex + sz to:lastIndex put:nil.
+ firstIndex := startIndex.
+ lastIndex := startIndex + sz - 1.
+ ^ self
].
oldSize == 0 ifTrue:[
- newSize := MinContentsArraySize
+ newSize := MinContentsArraySize
] ifFalse:[
- newSize := oldSize * 2.
+ newSize := oldSize * 2.
].
- newContents := Array basicNew:newSize.
+ newContents := self containerClass basicNew:newSize.
oldSize ~~ 0 ifTrue:[
- newContents
- replaceFrom:1 to:oldSize
- with:contentsArray startingAt:1.
+ newContents
+ replaceFrom:1 to:oldSize
+ with:contentsArray startingAt:1.
].
contentsArray := newContents
"Modified: / 22-10-2008 / 11:50:28 / cg"
+ "Modified: / 30-07-2018 / 12:07:22 / Claus Gittinger"
!
setFirstIndex:newFirstIndex lastIndex:newLastIndex