Эффективное постусловие Эйфеля для обеспечения сортировки массива

Я реализовал запрос, который сообщает, отсортирован ли массив или нет. Я хочу сделать хорошее постусловие, которое будет эффективно проверять, отсортирован ли массив с помощью across или чего-то еще.

Я пытался сделать это так:

is_sorted (a: ARRAY [INTEGER]): BOOLEAN
        -- Given an array, tell if it's sorted in ascending order
    require
        array_set: a /= Void
    local
        i, j, temp: INTEGER
    do
        Result := True

        from
            i := a.lower
            j := i + 1
        invariant
            (i >= a.lower) and (i <= a.upper)
        until
            i = (a.upper) or (Result = False)
        loop
            if a[i] > a[j] then
                Result := False
            end

            i := i + 1
            j := j + 1
        variant
            a.count - i + 1
        end -- End of loop

    ensure
          -- Check if ARRAY is sorted here
    end

Я пытался написать что-то вроде этого:

ensure
    across a as el all (el.item <= el.forth.item) end

Но это явно не работает, потому что el.forth — это не запрос, а команда.

Как я могу заставить это across работать или я должен сделать что-то еще?


person Dragos Strugar    schedule 15.09.2017    source источник
comment
Можете ли вы использовать что-то вроде across 1 |..| (a.count - 1) as la_index all a.at(la_index.item) <= a.at(la_index.item + 1) end ?   -  person Louis M    schedule 15.09.2017
comment
@LouisM да, конечно. Это то, что я искал. Поместите это в ответы.   -  person Dragos Strugar    schedule 15.09.2017


Ответы (2)


Вы можете перебирать индексы вместо массива. Что-то такое:

across 1 |..| (a.count - 1) as la_index all a.at(la_index.item) <= a.at(la_index.item + 1) end

person Louis M    schedule 15.09.2017

Чтобы дополнить ответ Луи, вот еще несколько вариантов. Во-первых, тот же вариант, в котором учтено, что индексы массива не обязательно должны начинаться с 1:

across a.lower |..| (a.upper - 1) as i all a [i.item] <= a [i.item + 1] end

К сожалению, эта версия не работает, когда upper является минимальным целочисленным значением. В этом случае a.upper - 1 переполняется, и итерация получает неправильный целочисленный интервал. Решение состоит в том, чтобы придерживаться исходного диапазона индексов, но с условием, что последний элемент не сравнивается:

across a.lower |..| a.upper as i until i.item >= a.upper all a [i.item] <= a [i.item + 1] end

Вместо того, чтобы перебирать интервал, исходный массив можно перебирать напрямую, если последний элемент исключен из сравнения:

across a as i until i.target_index >= a.upper all i.item <= a [i.target_index + 1] end

или, используя специальный запрос is_last:

across a as i until i.is_last all i.item <= a [i.target_index + 1] end
person Alexander Kogtenkov    schedule 16.09.2017