# HG changeset patch # User Claus Gittinger # Date 853903740 -3600 # Node ID e6fa084818ec0aad1df8ba1743276eda1a606f3d # Parent 38a064616dfd4adeb461675074632788701594c9 added #addAll:beforeIndex: and #makeRoomAtIndex:for: diff -r 38a064616dfd -r e6fa084818ec OrdColl.st --- a/OrdColl.st Wed Jan 22 03:18:33 1997 +0100 +++ b/OrdColl.st Wed Jan 22 04:29:00 1997 +0100 @@ -430,6 +430,55 @@ "Modified: 12.4.1996 / 16:47:31 / cg" ! +addAll:aCollection beforeIndex:index + "insert all elements of the argument, anObject to become located at index. + The collection may be unordered, but then order of the sliced-in elements + is undefined. + Return the receiver." + + |idx count| + + aCollection isSequenceable ifTrue:[ + "/ we are lucky - that thing can count & do bulk copies + + count := aCollection size. + idx := self makeRoomAtIndex:(index + firstIndex) for:count. + "/ notice: the above may change firstIndex + contentsArray replaceFrom:idx to:(idx + count - 1) with:aCollection startingAt:1. + ^ self + ]. + + idx := index. + aCollection do:[:element | + self add:element beforeIndex:idx. + idx := idx + 1. + ]. + + " + |c| + c := #(1 2 3 4) asOrderedCollection. + c addAll:'here' beforeIndex:3 + " + " + |c| + c := #(1 2 3 4) asOrderedCollection. + c addAll:'here' beforeIndex:1 + " + " + |c| + c := #(1 2 3 4) asOrderedCollection. + c addAll:'here' beforeIndex:5 + " + + " + |c| + c := #(1 2 3 4) asOrderedCollection. + c addAll:('hello' asSet) beforeIndex:3 + " + + "Modified: 22.1.1997 / 04:00:27 / cg" +! + addFirst:anObject "add the argument, anObject to the beginning of the collection. Return the argument, anObject." @@ -1207,6 +1256,103 @@ "Modified: 12.4.1996 / 17:18:58 / cg" ! +makeRoomAtIndex:whereToMakeEmptySlots for:howMany + "grow the contents for inserting at whereToMakeEmptySlot. + The whereToMakeEmptySlot argument must be a physical index within the contentsArray. + If there is (plenty of) room at either end, elements are shifted inplace to create + an empty slot; otherwise, a new contentsArray is allocated. + Since this changes the logical size, the modified index is returned. + i.e. + #(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:3 for:2 -> #(1 2 nil nil 3 4 5 6) + #(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:1 for:2 -> #(nil nil 1 2 3 4 5 6) + #(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:7 for:2 -> #(1 2 3 4 5 6 nil nil)" + + |newContents + newSize "{ Class:SmallInteger }" + oldSize "{ Class:SmallInteger }" + oneFourthOfSize "{ Class:SmallInteger }" + first "{ Class:SmallInteger }" + last "{ Class:SmallInteger }" + index "{ Class:SmallInteger }" + shiftLeft shiftRight| + + oldSize := contentsArray size. + oneFourthOfSize := oldSize // 4. + index := whereToMakeEmptySlots. + first := firstIndex. + last := lastIndex. + + ((first > howMany) and:[first > oneFourthOfSize]) ifTrue:[ + "there is room (>25%) at the beginning" + + shiftLeft := true. + ] ifFalse:[ + last < (oneFourthOfSize * 3) ifTrue:[ + shiftRight := true + ] + ]. + + shiftLeft == true ifTrue:[ + "there is room (>25%) 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 (>25%) 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 * 2. + [newSize < (oldSize+howMany)] whileTrue:[ + newSize := newSize * 2 + ]. + + newContents := Array basicNew:newSize. + 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. + lastIndex := last - first + howMany + 1. + + "/ return the modified index + ^ index - (first - firstIndex). + + "Modified: 22.1.1997 / 03:51:33 / cg" +! + makeRoomAtLast "grow/shift the contents for more room at the end. Does not change the logical size. @@ -1411,5 +1557,5 @@ !OrderedCollection class methodsFor:'documentation'! version - ^ '$Header: /cvs/stx/stx/libbasic/Attic/OrdColl.st,v 1.54 1997-01-14 15:20:58 cg Exp $' + ^ '$Header: /cvs/stx/stx/libbasic/Attic/OrdColl.st,v 1.55 1997-01-22 03:29:00 cg Exp $' ! ! diff -r 38a064616dfd -r e6fa084818ec OrderedCollection.st --- a/OrderedCollection.st Wed Jan 22 03:18:33 1997 +0100 +++ b/OrderedCollection.st Wed Jan 22 04:29:00 1997 +0100 @@ -430,6 +430,55 @@ "Modified: 12.4.1996 / 16:47:31 / cg" ! +addAll:aCollection beforeIndex:index + "insert all elements of the argument, anObject to become located at index. + The collection may be unordered, but then order of the sliced-in elements + is undefined. + Return the receiver." + + |idx count| + + aCollection isSequenceable ifTrue:[ + "/ we are lucky - that thing can count & do bulk copies + + count := aCollection size. + idx := self makeRoomAtIndex:(index + firstIndex) for:count. + "/ notice: the above may change firstIndex + contentsArray replaceFrom:idx to:(idx + count - 1) with:aCollection startingAt:1. + ^ self + ]. + + idx := index. + aCollection do:[:element | + self add:element beforeIndex:idx. + idx := idx + 1. + ]. + + " + |c| + c := #(1 2 3 4) asOrderedCollection. + c addAll:'here' beforeIndex:3 + " + " + |c| + c := #(1 2 3 4) asOrderedCollection. + c addAll:'here' beforeIndex:1 + " + " + |c| + c := #(1 2 3 4) asOrderedCollection. + c addAll:'here' beforeIndex:5 + " + + " + |c| + c := #(1 2 3 4) asOrderedCollection. + c addAll:('hello' asSet) beforeIndex:3 + " + + "Modified: 22.1.1997 / 04:00:27 / cg" +! + addFirst:anObject "add the argument, anObject to the beginning of the collection. Return the argument, anObject." @@ -1207,6 +1256,103 @@ "Modified: 12.4.1996 / 17:18:58 / cg" ! +makeRoomAtIndex:whereToMakeEmptySlots for:howMany + "grow the contents for inserting at whereToMakeEmptySlot. + The whereToMakeEmptySlot argument must be a physical index within the contentsArray. + If there is (plenty of) room at either end, elements are shifted inplace to create + an empty slot; otherwise, a new contentsArray is allocated. + Since this changes the logical size, the modified index is returned. + i.e. + #(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:3 for:2 -> #(1 2 nil nil 3 4 5 6) + #(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:1 for:2 -> #(nil nil 1 2 3 4 5 6) + #(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:7 for:2 -> #(1 2 3 4 5 6 nil nil)" + + |newContents + newSize "{ Class:SmallInteger }" + oldSize "{ Class:SmallInteger }" + oneFourthOfSize "{ Class:SmallInteger }" + first "{ Class:SmallInteger }" + last "{ Class:SmallInteger }" + index "{ Class:SmallInteger }" + shiftLeft shiftRight| + + oldSize := contentsArray size. + oneFourthOfSize := oldSize // 4. + index := whereToMakeEmptySlots. + first := firstIndex. + last := lastIndex. + + ((first > howMany) and:[first > oneFourthOfSize]) ifTrue:[ + "there is room (>25%) at the beginning" + + shiftLeft := true. + ] ifFalse:[ + last < (oneFourthOfSize * 3) ifTrue:[ + shiftRight := true + ] + ]. + + shiftLeft == true ifTrue:[ + "there is room (>25%) 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 (>25%) 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 * 2. + [newSize < (oldSize+howMany)] whileTrue:[ + newSize := newSize * 2 + ]. + + newContents := Array basicNew:newSize. + 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. + lastIndex := last - first + howMany + 1. + + "/ return the modified index + ^ index - (first - firstIndex). + + "Modified: 22.1.1997 / 03:51:33 / cg" +! + makeRoomAtLast "grow/shift the contents for more room at the end. Does not change the logical size. @@ -1411,5 +1557,5 @@ !OrderedCollection class methodsFor:'documentation'! version - ^ '$Header: /cvs/stx/stx/libbasic/OrderedCollection.st,v 1.54 1997-01-14 15:20:58 cg Exp $' + ^ '$Header: /cvs/stx/stx/libbasic/OrderedCollection.st,v 1.55 1997-01-22 03:29:00 cg Exp $' ! !