OCL25 — Invalid algorithm in definitions of sortedBy

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.