[Pkg] The Trunk: Collections-ul.436.mcz

commits at source.squeak.org commits at source.squeak.org
Fri Apr 1 19:31:14 UTC 2011


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

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

Name: Collections-ul.436
Author: ul
Time: 1 April 2011, 9:25:17.967 pm
UUID: f684fc31-c114-bf41-aecb-98f347ccb43e
Ancestors: Collections-nice.435

Improved #beginsWith: and #endsWith: implementations.

=============== Diff against Collections-nice.435 ===============

Item was changed:
+ ----- Method: ByteString>>beginsWith: (in category 'testing') -----
+ beginsWith: sequence
+ 	"Answer whether the receiver begins with the given sequence. The comparison is case-sensitive. Overridden for better performance."
- ----- Method: ByteString>>beginsWith: (in category 'comparing') -----
- beginsWith: prefix
- 	"Answer whether the receiver begins with the given prefix string.
- 	The comparison is case-sensitive."
  
+ 	| sequenceSize |
+ 	sequence class isBytes ifFalse: [ ^super beginsWith: sequence ].
+ 	((sequenceSize := sequence size) = 0 or: [ self size < sequenceSize ]) ifTrue: [ ^false ].
+ 	"The following method uses a suboptimal algorithm (brute force pattern matching with O(n^2) worst case runtime), but the primitive in C is so fast (assuming large alphabets), that it's still worth using it instead of linear time pure smalltalk implementation. There are some obvious cases when the brute force algorithm is suboptimal, e.g. when the first elements don't match, so let's compare them here before using the primitive."
+ 	(self basicAt: 1) = (sequence basicAt: 1) ifFalse: [ ^false ].
+ 	^(self findSubstring: sequence in: self startingAt: 1 matchTable: CaseSensitiveOrder) = 1!
- 
- 	"IMPLEMENTATION NOTE:
- 	following algorithm is optimized in primitive only in case self and prefix are bytes like.
- 	Otherwise, if self is wide, then super outperforms,
- 	Otherwise, if prefix is wide, primitive is not correct"
- 	
- 	prefix class isBytes ifFalse: [^super beginsWith: prefix].
- 	
- 	self size < prefix size ifTrue: [^ false].
- 	^ (self findSubstring: prefix in: self startingAt: 1
- 			matchTable: CaseSensitiveOrder) = 1
- !

Item was changed:
+ ----- Method: ByteSymbol>>beginsWith: (in category 'testing') -----
+ beginsWith: sequence
+ 	"Answer whether the receiver begins with the given sequence. The comparison is case-sensitive. Overridden for better performance."
- ----- Method: ByteSymbol>>beginsWith: (in category 'comparing') -----
- beginsWith: prefix
- 	"Answer whether the receiver begins with the given prefix string.
- 	The comparison is case-sensitive."
  
+ 	| sequenceSize |
+ 	sequence class isBytes ifFalse: [ ^super beginsWith: sequence ].
+ 	((sequenceSize := sequence size) = 0 or: [ self size < sequenceSize ]) ifTrue: [ ^false ].
+ 	"The following method uses a suboptimal algorithm (brute force pattern matching with O(n^2) worst case runtime), but the primitive in C is so fast (assuming large alphabets), that it's still worth using it instead of linear time pure smalltalk implementation. There are some obvious cases when the brute force algorithm is suboptimal, e.g. when the first elements don't match, so let's compare them here before using the primitive."
+ 	(self basicAt: 1) = (sequence basicAt: 1) ifFalse: [ ^false ].
+ 	^(self findSubstring: sequence in: self startingAt: 1 matchTable: CaseSensitiveOrder) = 1!
- 
- 	"IMPLEMENTATION NOTE:
- 	following algorithm is optimized in primitive only in case self and prefix are bytes like.
- 	Otherwise, if self is wide, then super outperforms,
- 	Otherwise, if prefix is wide, primitive is not correct"
- 	
- 	prefix class isBytes ifFalse: [^super beginsWith: prefix].
- 	
- 	self size < prefix size ifTrue: [^ false].
- 	^ (self findSubstring: prefix in: self startingAt: 1
- 			matchTable: CaseSensitiveOrder) = 1
- !

Item was changed:
  ----- Method: SequenceableCollection>>beginsWith: (in category 'testing') -----
+ beginsWith: sequence
+ 	"Answer true if the receiver starts with the argument collection."
+ 	
+ 	| sequenceSize |
+ 	((sequenceSize := sequence size) = 0 or: [ self size < sequence size ]) ifTrue: [ ^false ].
+ 	1 to: sequenceSize do: [ :index |
+ 		(sequence at: index) = (self at: index) ifFalse: [ ^false ] ].
- beginsWith: aSequenceableCollection
- 	"Answer true if the receiver starts with the argument collection"
- 	(aSequenceableCollection isEmpty or: [self size < aSequenceableCollection size]) ifTrue: [^false].
- 	aSequenceableCollection withIndexDo: [:each :index | (self at: index) ~= each ifTrue: [^false]].
  	^true!

Item was changed:
  ----- Method: SequenceableCollection>>endsWith: (in category 'testing') -----
+ endsWith: sequence
+ 	"Answer true if the receiver ends with the argument collection."
+ 	
+ 	| sequenceSize offset |
+ 	((sequenceSize := sequence size) = 0 or: [ (offset := self size - sequence size) < 0 ]) ifTrue: [ ^false ].
+ 	1 to: sequenceSize do: [ :index |
+ 		(sequence at: index) = (self at: index + offset) ifFalse: [ ^false ] ].
- endsWith: aSequenceableCollection
- 	"Answer true if the receiver ends with the argument collection"
- 	| start |
- 	(aSequenceableCollection isEmpty or: [self size < aSequenceableCollection size]) ifTrue: [^false].
- 	start := self size - aSequenceableCollection size.
- 	aSequenceableCollection withIndexDo: [:each :index | (self at: start + index) ~= each ifTrue: [^false]].
  	^true!

Item was added:
+ ----- Method: String>>beginsWith: (in category 'testing') -----
+ beginsWith: sequence
+ 	"Answer true if the receiver starts with the argument collection. The comparison is case-sensitive. Overridden for better performance."
+ 
+ 	| sequenceSize |
+ 	sequence isString ifFalse: [ ^super beginsWith: sequence ].
+ 	((sequenceSize := sequence size) = 0 or: [ self size < sequence size ]) ifTrue: [ ^false ].
+ 	1 to: sequenceSize do: [ :index |
+ 		(sequence basicAt: index) = (self basicAt: index) ifFalse: [ ^false ] ].
+ 	^true!

Item was changed:
  ----- Method: String>>endsWith: (in category 'testing') -----
  endsWith: suffix
+ 	"Answer true if the receiver ends with the argument collection. The comparison is case-sensitive. Overridden for better performance."
- 	"Answer whether the tail end of the receiver is the same as suffix.
- 	The comparison is case-sensitive."
  	
+ 	| offset |
+ 	(offset := self size - suffix size) < 0 ifTrue: [ ^false ].
+ 	^(self findString: suffix startingAt: offset + 1) ~= 0!
- 	| extra |
- 	(extra := self size - suffix size) < 0 ifTrue: [^ false].
- 	^ (self findString: suffix startingAt: extra + 1) > 0
- "
-   'Elvis' endsWith: 'vis'
- "!



More information about the Packages mailing list