Issue 19510: Invalid algorithm in definitions of sortedBy (ocl2-rtf) Source: (, ) Nature: Clarification Severity: Minor Summary: The following problems are common to all definitions of sortedBy in 11.9: Invalid algorithm: * When the current element is not the first one, but is the greatest one so far, for example 2 in Sequence{1,2}->sortedBy(x|x), then result->select (item | body (item) > body (iterator)) is empty and calling ->first on it would result in invalid. Inconsistent use of < and >: * The text descriptions mention using < operation on the elements, but the algorithm uses > operator. Typos: * The accumulator initialization incorrectly uses : instead of =. * The source for the iterate expression is missing. * The closing parenthesis for the iterate expression is missing. * The operations append and insertAt are called by . operator. SOLUTION: * Introduce a new local variable upperBounds, containing elements from the accumulator that are greater than the current element. * Swap body (iterator) and body (item). * Fix typos. Corrected algorithm for Set (11.9.2) and OrderedSet (11.9.5): **************************************** source->sortedBy(iterator | body) = source->iterate( iterator ; result : OrderedSet(T) = OrderedSet {} | let upperBounds : OrderedSet(T) = result->select (item | body (iterator) < body (item) ) in if upperBounds->isEmpty() then result->append(iterator) else let position : Integer = result->indexOf ( upperBounds->first() ) in result->insertAt(position, iterator) endif ) **************************************** Corrected algorithm for Sequence (11.9.4) and Bag (11.9.3): **************************************** source->sortedBy(iterator | body) = source->iterate( iterator ; result : Sequence(T) = Sequence {} | let upperBounds : Sequence(T) = result->select (item | body (iterator) < body (item) ) in if upperBounds->isEmpty() then result->append(iterator) else let position : Integer = result->indexOf ( upperBounds->first() ) in result->insertAt(position, iterator) endif ) **************************************** FURTHER SUGGESTIONS: * The presented algorithm works only under assumption that indexOf(obj:T) on Sequence(T) returns the first occurence. This is not mentioned in the definition of indexOf. If indexOf can return any index, for example: Sequence{2, 2}->indexOf(2) = 2, then the above algorithm could insert the element at the wrong place, for example: Sequence{2, 2, 1}->sortedBy(x|x) = Sequence{2, 1, 2} * The algorithm is stable for Sequence and OrderedSet, this fact could be mentioned in the description, to make it clear that successive sortedBy iterations can be used to sort by multiple criteria. Resolution: Revised Text: Actions taken: July 4, 2014: received issue Discussion: End of Annotations:===== m: webmaster@omg.org Date: 04 Jul 2014 13:29:13 -0400 To: Subject: Issue/Bug Report ******************************************************************************* Name: Vlastimil Dort Employer: mailFrom: panacekcz@seznam.cz Terms_Agreement: I agree Specification: Object Constraint Language Section: 11.9 FormalNumber: formal/2014-02-03 Version: 2.4 Doc_Year: 2014 Doc_Month: February Doc_Day: 03 Page: 180-183 Title: Invalid algorithm in definitions of sortedBy Nature: Clarification Severity: Minor CODE: 3TMw8 B1: Report Issue Remote Name: eduroam52.ms.mff.cuni.cz Remote User: HTTP User Agent: Mozilla/5.0 (Windows NT 6.1; rv:30.0) Gecko/20100101 Firefox/30.0 Time: 01:29 PM Description: The following problems are common to all definitions of sortedBy in 11.9: Invalid algorithm: * When the current element is not the first one, but is the greatest one so far, for example 2 in Sequence{1,2}->sortedBy(x|x), then result->select (item | body (item) > body (iterator)) is empty and calling ->first on it would result in invalid. Inconsistent use of < and >: * The text descriptions mention using < operation on the elements, but the algorithm uses > operator. Typos: * The accumulator initialization incorrectly uses : instead of =. * The source for the iterate expression is missing. * The closing parenthesis for the iterate expression is missing. * The operations append and insertAt are called by . operator. SOLUTION: * Introduce a new local variable upperBounds, containing elements from the accumulator that are greater than the current element. * Swap body (iterator) and body (item). * Fix typos. Corrected algorithm for Set (11.9.2) and OrderedSet (11.9.5): **************************************** source->sortedBy(iterator | body) = source->iterate( iterator ; result : OrderedSet(T) = OrderedSet {} | let upperBounds : OrderedSet(T) = result->select (item | body (iterator) < body (item) ) in if upperBounds->isEmpty() then result->append(iterator) else let position : Integer = result->indexOf ( upperBounds->first() ) in result->insertAt(position, iterator) endif ) **************************************** Corrected algorithm for Sequence (11.9.4) and Bag (11.9.3): **************************************** source->sortedBy(iterator | body) = source->iterate( iterator ; result : Sequence(T) = Sequence {} | let upperBounds : Sequence(T) = result->select (item | body (iterator) < body (item) ) in if upperBounds->isEmpty() then result->append(iterator) else let position : Integer = result->indexOf ( upperBounds->first() ) in result->insertAt(position, iterator) endif ) **************************************** FURTHER SUGGESTIONS: * The presented algorithm works only under assumption that indexOf(obj:T) on Sequence(T) returns the first occurence. This is not mentioned in the definition of indexOf. If indexOf can return any index, for example: Sequence{2, 2}->indexOf(2) = 2, then the above algorithm could insert the element at the wrong place, for example: Sequence{2, 2, 1}->sortedBy(x|x) = Sequence{2, 1, 2} * The algorithm is stable for Sequence and OrderedSet, this fact could be mentioned in the description, to make it clear that successive sortedBy iterations can be used to sort by multiple criteria.