The Trunk: Collections-ul.358.mcz

Levente Uzonyi uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.358.mcz

==================== Summary ====================

Name: Collections-ul.358
Author: ul
Time: 10 May 2010, 1:46:34.235 pm
UUID: c0381bb4-d024-8644-bfc2-513bbcdda3c3
Ancestors: Collections-ar.357

- OrderedCollection growth fixes

=============== Diff against Collections-ar.357 ===============

Item was added:
+ ----- Method: OrderedCollection>>growAtLast (in category 'private') -----
+ growAtLast
+
+ | newArray |
+ newArray := Array new: (array size * 2 max: 1).
+ newArray
+ replaceFrom: firstIndex
+ to: lastIndex
+ with: array
+ startingAt: firstIndex.
+ array := newArray!

Item was changed:
  ----- Method: OrderedCollection>>makeRoomAtFirst (in category 'private') -----
  makeRoomAtFirst
+ "Make some empty slots at the front of the array. If we have more than 50% free space, then just move the elements, so that the first 50% of the slots are free, otherwise add new free slots to the front by growing. Precondition: firstIndex = 1"
+
+ | tally newFirstIndex newLastIndex |
+ tally := self size.
+ tally * 2 >= array size ifTrue: [ ^self growAtFirst ].
+ tally = 0 ifTrue: [ ^self resetTo: array size + 1 ].
+ newFirstIndex := array size // 2 + 1.
+ newLastIndex := newFirstIndex - firstIndex + lastIndex.
+ 0 to: tally - 1 do: [ :offset |
+ array at: newLastIndex - offset put: (array at: lastIndex - offset) ].
+ array from: firstIndex to: newFirstIndex - 1 put: nil.
+ firstIndex := newFirstIndex.
+ lastIndex := newLastIndex!
- | delta index |
- delta := array size - self size.
- delta = 0 ifTrue:
- [self grow.
- delta := array size - self size].
- lastIndex = array size ifTrue: [^ self]. "just in case we got lucky"
- index := array size.
- [index > delta]
- whileTrue:
- [array at: index put: (array at: index - delta + firstIndex - 1).
- array at: index - delta + firstIndex - 1 put: nil.
- index := index - 1].
- firstIndex := delta + 1.
- lastIndex := array size!

Item was added:
+ ----- Method: OrderedCollection>>growAtFirst (in category 'private') -----
+ growAtFirst
+
+ | newArray newFirstIndex newLastIndex |
+ newArray := Array new: (array size * 2 max: 1).
+ newFirstIndex := newArray size - array size + firstIndex.
+ newLastIndex := newFirstIndex + lastIndex - firstIndex.
+ newArray
+ replaceFrom: newFirstIndex
+ to: newLastIndex
+ with: array
+ startingAt: firstIndex.
+ array := newArray.
+ firstIndex := newFirstIndex.
+ lastIndex := newLastIndex!

Item was changed:
  ----- Method: OrderedCollection>>reset (in category 'private') -----
  reset
+
+ self resetTo: 1!
- firstIndex := array size // 3 max: 1.
- lastIndex := firstIndex - 1!

Item was changed:
  ----- Method: OrderedCollection>>makeRoomAtLast (in category 'private') -----
  makeRoomAtLast
+ "Make some empty slots at the end of the array. If we have more than 50% free space, then just move the elements, so that the last 50% of the slots are free, otherwise add new free slots to the end by growing. Precondition: lastIndex = array size"
+
+ | tally newFirstIndex newLastIndex |
+ tally := self size.
+ tally * 2 >= lastIndex ifTrue: [ ^self growAtLast ].
+ tally = 0 ifTrue: [ ^self resetTo: 1 ].
+ newLastIndex := lastIndex // 2.
+ newFirstIndex := newLastIndex - lastIndex + firstIndex.
+ array
+ replaceFrom: newFirstIndex
+ to: newLastIndex
+ with: array
+ startingAt: firstIndex.
+ array from: newLastIndex + 1 to: lastIndex put: nil.
+ firstIndex := newFirstIndex.
+ lastIndex := newLastIndex!
- | newLast delta |
- newLast := self size.
- array size - self size = 0 ifTrue: [self grow].
- (delta := firstIndex - 1) = 0 ifTrue: [^ self].
- "we might be here under false premises or grow did the job for us"
- 1 to: newLast do:
- [:index |
- array at: index put: (array at: index + delta).
- array at: index + delta put: nil].
- firstIndex := 1.
- lastIndex := newLast!