 1. OMG Issue

# OCL25 — Invalid algorithm in definitions of sortedBy

• Key: OCL25-113
• Legacy Issue Number: 19510
• Status: open
• Source: seznam.cz ( Vlastimil Dort)
• 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.
• Reported: OCL 2.4 — Fri, 4 Jul 2014 04:00 GMT
• Updated: Sat, 20 Jan 2018 09:25 GMT