确保数组排序的有效 Eiffel 后置条件
Effective Eiffel Postcondition for Ensuring that Array is sorted
我已经实现了一个查询来判断数组是否已排序。我想做一个很好的后置条件,它将有效地检查数组是否使用 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
工作或者我应该做其他事情?
您可以遍历索引而不是数组。类似的东西:
across 1 |..| (a.count - 1) as la_index all a.at(la_index.item) <= a.at(la_index.item + 1) end
为了补充 Louis 的回答,这里还有一些变体。首先,考虑到数组索引不一定以 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
我已经实现了一个查询来判断数组是否已排序。我想做一个很好的后置条件,它将有效地检查数组是否使用 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
工作或者我应该做其他事情?
您可以遍历索引而不是数组。类似的东西:
across 1 |..| (a.count - 1) as la_index all a.at(la_index.item) <= a.at(la_index.item + 1) end
为了补充 Louis 的回答,这里还有一些变体。首先,考虑到数组索引不一定以 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