--- a/OrdColl.st Sat Jan 08 17:24:16 1994 +0100
+++ b/OrdColl.st Sat Jan 08 17:29:16 1994 +0100
@@ -22,6 +22,14 @@
COPYRIGHT (c) 1989 by Claus Gittinger
All Rights Reserved
+$Header: /cvs/stx/stx/libbasic/Attic/OrdColl.st,v 1.7 1994-01-08 16:28:35 claus Exp $
+written spring 89 by claus
+'!
+
+!OrderedCollection class methodsFor:'documentation'!
+
+documentation
+"
OrderedCollection have ordered elements. Insertion and removal at both ends
is possible - therefore they can be used for queues and stacks.
@@ -30,10 +38,8 @@
contentsArray <Array> the actual contents
firstIndex <SmallInteger> index of first valid element
lastIndex <SmallInteger> index of last valid element
-
-$Header: /cvs/stx/stx/libbasic/Attic/OrdColl.st,v 1.6 1993-12-11 00:53:00 claus Exp $
-written spring 89 by claus
-'!
+"
+! !
!OrderedCollection class methodsFor:'instance creation'!
@@ -234,8 +240,8 @@
"
|c|
c := #(4 3 2 1) asOrderedCollection.
- c add:'here' after:3
- c add:'here' after:1
+ c add:'here' after:3.
+ c add:'here' after:5
"
!
@@ -256,8 +262,8 @@
"
|c|
c := #(4 3 2 1) asOrderedCollection.
- c add:'here' after:3
- c add:'here' after:1
+ c add:'here' before:3.
+ c add:'here' before:5
"
! !
@@ -266,10 +272,12 @@
grow:newSize
"grow the receiver to newSize"
- |newContents|
+ |newContents oldLast|
newSize <= (lastIndex - firstIndex + 1) ifTrue:[
- lastIndex := firstIndex + newSize - 1
+ oldLast := lastIndex.
+ lastIndex := firstIndex + newSize - 1.
+ contentsArray from:lastIndex + 1 to:oldLast put:nil.
] ifFalse:[
newContents := Array new:newSize.
newContents replaceFrom:1 to:(lastIndex - firstIndex + 1) with:contentsArray.
@@ -334,13 +342,26 @@
!
makeRoomAtLast
- "grow the contents for more room at the end"
+ "grow/shift the contents for more room at the end"
|newContents
- oldSize "{ Class:SmallInteger }"
- newSize "{ Class:SmallInteger }" |
+ oldSize "{ Class:SmallInteger }"
+ newSize "{ Class:SmallInteger }"
+ startIndex "{ Class:SmallInteger }"
+ sz "{ Class:SmallInteger }"|
oldSize := contentsArray size.
+ sz := self size.
+
+ "if there is lots of room at the beginning (> 50%), shift instead of growing"
+ oldSize > (sz * 2) ifTrue:[
+ startIndex := firstIndex // 4.
+ 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
+ ].
newSize := oldSize * 2.
newSize == 0 ifTrue:[ newSize := 1].
newContents := Array new:newSize.
@@ -349,13 +370,26 @@
!
makeRoomAtFront
- "grow the contents for more room at the beginning"
+ "grow/shift the contents for more room at the beginning"
|newContents
- oldSize "{ Class:SmallInteger }"
- newSize "{ Class:SmallInteger }" |
+ oldSize "{ Class:SmallInteger }"
+ newSize "{ Class:SmallInteger }"
+ startIndex "{ Class:SmallInteger }"
+ sz "{ Class:SmallInteger }"|
oldSize := contentsArray size.
+ sz := self size.
+
+ "if there is lots of room at the end (> 50%), shift instead of growing"
+ oldSize > (sz * 2) ifTrue:[
+ startIndex := oldSize // 4.
+ 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.
newSize == 0 ifTrue:[ newSize := 1].
newContents := Array new:newSize.
@@ -377,13 +411,38 @@
oldSize "{ Class:SmallInteger }" |
oldSize := contentsArray size.
- newSize := oldSize + 1.
+ firstIndex > (oldSize // 4) ifTrue:[
+ "there is room at the beginning"
+
+ index == 1 ifFalse:[
+ contentsArray replaceFrom:(firstIndex - 1) to:(index - 1)
+ with:contentsArray startingAt:firstIndex.
+ contentsArray at:index put:nil.
+ ].
+ firstIndex := firstIndex - 1.
+ ^ self
+ ].
+ lastIndex < (oldSize * 3 // 4) ifTrue:[
+ "there is room at the end"
+
+ index == (lastIndex + 1) ifFalse:[
+ contentsArray replaceFrom:(index + 1) to:(lastIndex + 1)
+ with:contentsArray startingAt:index.
+ contentsArray at:index put:nil
+ ].
+ lastIndex := lastIndex + 1.
+ ^ self
+ ].
+
+ newSize := oldSize * 2.
newContents := Array new:newSize.
index == 1 ifFalse:[
- newContents replaceFrom:1 to:index-1 with:contentsArray startingAt:1.
+ newContents replaceFrom:1 to:index-1
+ with:contentsArray startingAt:1.
].
index == newSize ifFalse:[
- newContents replaceFrom:index + 1 to:newSize with:contentsArray startingAt:index.
+ newContents replaceFrom:index + 1 to:oldSize + 1
+ with:contentsArray startingAt:index.
].
contentsArray := newContents.
lastIndex := lastIndex + 1
@@ -398,55 +457,55 @@
!OrderedCollection methodsFor:'testing'!
includes:anObject
- "return true if the object is in the collection"
+ "return true if anObject is in the collection. Compare using ="
- |index|
+ |index "{ Class:SmallInteger }"|
index := contentsArray indexOf:anObject startingAt:firstIndex.
- ^ index between:firstIndex and:lastIndex
+ ((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ false].
+ ^ true
!
identityIndexOf:anObject
- "return the index of the object, 0 if not in the collection"
+ "return the index of anObject or 0 if not found. Compare using =="
- |index|
+ |index "{ Class:SmallInteger }"|
index := contentsArray identityIndexOf:anObject startingAt:firstIndex.
- index < firstIndex ifTrue:[^ 0].
- index > lastIndex ifTrue:[^ 0].
+ ((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ 0].
^ index - firstIndex + 1
!
identityIndexOf:anObject startingAt:startIndex
- "return the index of the object, 0 if not in the collection"
+ "return the index of anObject, starting search at startIndex.
+ Compare using ==; return 0 if not found in the collection"
- |index|
+ |index "{ Class:SmallInteger }"|
index := contentsArray identityIndexOf:anObject startingAt:(startIndex + firstIndex - 1).
- index < firstIndex ifTrue:[^ 0].
- index > lastIndex ifTrue:[^ 0].
+ ((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ 0].
^ index - firstIndex + 1
!
indexOf:anObject
- "return the index of the object, 0 if not in the collection"
+ "return the index of anObject or 0 if not found in the collection.
+ Compare using ="
- |index|
+ |index "{ Class:SmallInteger }"|
index := contentsArray indexOf:anObject startingAt:firstIndex.
- index < firstIndex ifTrue:[^ 0].
- index > lastIndex ifTrue:[^ 0].
+ ((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ 0].
^ index - firstIndex + 1
!
indexOf:anObject startingAt:startIndex
- "return the index of the object, 0 if not in the collection"
+ "return the index of anObject, starting search at startIndex.
+ Compare using =; return 0 if not found in the collection"
- |index|
+ |index "{ Class:SmallInteger }"|
index := contentsArray indexOf:anObject startingAt:(startIndex + firstIndex - 1).
- index < firstIndex ifTrue:[^ 0].
- index > lastIndex ifTrue:[^ 0].
+ ((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ 0].
^ index - firstIndex + 1
! !
@@ -474,7 +533,12 @@
"evaluate the argument, aBlock for every element in the collection,
passing both index and element as arguments."
- firstIndex to:lastIndex do:[:index |
+ |start "{ Class:SmallInteger }"
+ stop "{ Class:SmallInteger }" |
+
+ stop := lastIndex.
+ start := firstIndex.
+ start to:stop do:[:index |
aTwoArgBlock value:index value:(contentsArray at:index)
]
!
@@ -484,15 +548,31 @@
and return a collection of the results"
|newCollection
- index "{ Class:SmallInteger }"
- end "{ Class:SmallInteger }" |
+ start "{ Class:SmallInteger }"
+ stop "{ Class:SmallInteger }" |
- end := lastIndex.
newCollection := (self species new).
- index := firstIndex.
- [index <= end] whileTrue:[
+ stop := lastIndex.
+ start := firstIndex.
+ start to:stop do:[:index |
newCollection add:(aBlock value:(contentsArray at:index)).
- index := index + 1
].
^ newCollection
! !
+
+!OrderedCollection methodsFor:'misc'!
+
+inspect
+ "redefined to launch a SequenceableCollectionInspector on the receiver
+ (instead of the default InspectorView)."
+
+ OrderedCollectionInspectorView isNil ifTrue:[
+ super inspect
+ ] ifFalse:[
+ OrderedCollectionInspectorView openOn:self
+ ]
+
+ "(OrderedCollection withAll:#(3 2 1)) inspect"
+ "(OrderedCollection withAll:#(3 2 1)) removeFirst; yourself; inspect"
+ "#(0 8 15 3 99 2) asSortedCollection inspect"
+! !