6.27. kink/VEC

6.27.1. vec型

vecは、可変長で変更可能な値の列である。

vecの要素の添字は、0から始まって連続する整数である。

vecはplain_paramの部分型である。kink/param/PLAIN_PARAMを見よう。

6.27.1.1. Vec.get(Ind)

getは、添字Indに位置する要素を戻す。

事前条件

Indは、[0, Vec.size)の範囲内の整数のnumでなければならない。

例

6.27.1.2. Vec.size

sizeは、Vecの要素の数を整数のnum値として戻す。

例

6.27.1.3. Vec.front

frontは、Vecの最初の要素を戻す。

事前条件

Vecは空であってはならない。

例

6.27.1.4. Vec.back

backは、Vecの最後の要素を戻す。

事前条件

Vecは空であってはならない。

例

6.27.1.5. Vec.take_front(N)

take_frontは、Vecの最初のN個の要素を含む新しいvecを戻す。

事前条件

Nは、[0, Vec.size)の範囲内の整数のnumでなければならない。

例

6.27.1.6. Vec.take_back(N)

take_backは、Vecの最後のN個の要素を含む新しいvecを戻す。

事前条件

Nは、[0, Vec.size)の範囲内の整数のnumでなければならない。

例

6.27.1.7. Vec.drop_front(N)

drop_frontは、[N, Vec.size)の範囲のVecのスライスの要素を含む新しいvecを戻す。

事前条件

Nは、[0, Vec.size)の範囲内の整数のnumでなければならない。

例

6.27.1.8. Vec.drop_back(N)

drop_backは、[0, Vec.size - N)の範囲のVecのスライスの要素を含む新しいvecを戻す。

事前条件

Nは、[0, Vec.size)の範囲内の整数のnumでなければならない。

例

6.27.1.9. Vec.slice(From To)

sliceは、[From, To)の範囲のVecのスライスの要素を含む新しいvecを戻す。

事前条件

FromとToは整数のnum値でなければならない。

0 <= From <= To <= Vec.size

例

6.27.1.10. Vec.set(Ind Val)

setは、添字Indの位置にValを書き込む。

Vecのサイズは変わらない。

事前条件

Indは、[0, Vec.size)の範囲内の整数のnumでなければならない。

例

6.27.1.11. Vec.push_front(Val)

push_frontは、ValをVecの最初の要素として挿入する。

Vecのサイズは1だけ伸びる。既存の要素は後方に1だけコピーされる。

例

6.27.1.12. Vec.push_back(Val)

push_backはValをVecの最後の要素として挿入する。

Vecのサイズは1だけ伸びる。

例

6.27.1.13. Vec.push_at(Pos Val)

push_atはValを添字Posの位置に挿入する。

Vecのサイズは1だけ伸びる。Posの位置以降の既存の要素は、後方に1だけコピーされる。

事前条件

Posは整数のnum値でなければならない。

0 <= Pos <= Vec.size

例

6.27.1.14. Vec.append_front(Eacher)

append_frontは、Eacherのすべての要素をVecの先頭に挿入する。

Eacher.eachが、それぞれの$consumeの呼び出しでE(0), E(1) ,,, E(n-1)を渡すとき、またVecの現在の要素がV(0), V(1) ,,, V(m-1)であるとき、append_frontの呼び出し後に、Vecの要素はE(0), E(1) ,,, E(n-1), V(0), V(1) ,,, V(m-1)になる。

事前条件

Eacherは each($consume) メソッドを持っていなければならない。eachは$consumeをEacherのそれぞれの要素について呼び出すものでなければならない。

例

6.27.1.15. Vec.append_back(Eacher)

append_backは、Eacherのすべての要素をVecの末尾に挿入する。

Eacher.eachが、それぞれの$consumeの呼び出しでE(0), E(1) ,,, E(n-1)を渡すとき、またVecの現在の要素がV(0), V(1) ,,, V(m-1)であるとき、append_backの呼び出し後に、Vecの要素はV(0), V(1) ,,, V(m-1), E(0), E(1) ,,, E(n-1)になる。

事前条件

Eacherは each($consume) メソッドを持っていなければならない。eachは$consumeをEacherのそれぞれの要素について呼び出すものでなければならない。

例

6.27.1.16. Vec.append_at(Pos Eacher)

append_atは、Eacherのすべての要素を、Vecの添字Posの位置に挿入する。

Eacher.eachが、それぞれの$consumeの呼び出しでE(0), E(1) ,,, E(n-1)を渡すとき、またVecの現在の要素がV(0), V(1) ,,, V(m-1)であるときappend_atの呼び出し後に、Vecの要素はV(0), V(1) ,,, V(Pos-1), E(0), E(1) ,,, E(n-1), V(Pos) ,,, V(m-1)になる。

事前条件

Posは整数のnum値でなければならない。

0 <= Pos <= Vec.size

Eacherは each($consume) メソッドを持っていなければならない。eachは$consumeをEacherのそれぞれの要素について呼び出すものでなければならない。

例

6.27.1.17. Vec.pop_front

pop_frontは、Vecの最初の要素を削除して、その要素を戻す。

削除された要素の後ろの要素は、先頭の方へ1ずつコピーされる。Vecのサイズは1だけ切り詰められる。

事前条件

Vecは空であってはならない。

例

6.27.1.18. Vec.pop_back

pop_backは、Vecの最後の要素を削除して、その要素を戻す。

Vecのサイズは1だけ切り詰められる。

事前条件

Vecは空であってはならない。

例

6.27.1.19. Vec.pop_at(Ind)

pop_atは、添字Indの位置の要素を削除して、その要素を戻す。

削除された要素の後ろの要素は、先頭の方へ1ずつコピーされる。Vecのサイズは1だけ切り詰められる。

事前条件

Indは整数のnum値でなければならない。

0 <= Ind < Vec.size

例

6.27.1.20. Vec.clear(...[From=0 To=Vec.size])

clearは、Vecの要素から[From, To)の範囲のスライスを削除する。

削除されたスライスの後の要素は、(To - From)ずつ先頭の方にコピーされる。VecのサイズはVec.size - (To - From)に切り詰められる。

事前条件

FromとToは整数のnum値でなければならない。

0 <= From <= To <= Vec.size

例: 引数なし

例: Fromを指定

例: FromとToを指定

6.27.1.21. Dest_vec.move(D_from Src ...[S_from=0 S_to=Src.size])

moveは、ベクタSrcのスライス[S_from, S_to)から要素をコピーして、ベクタDest_vecのスライス[D_from, D_from + (S_to - S_from))に貼り付ける。

moveという名前は、memmove関数から来ている。Dest_vecとSrcが同じベクタで、スライスが重なっても良いためである。

事前条件

D_fromは[0, Dest_vec.size]の範囲の整数のnumでなければならない。

Srcはvec値でなければならない。

S_fromとS_toは整数のnum値でなければならない。

0 <= S_from <= S_to <= Src.size

D_from + (S_to - S_from) <= Dest_vec.size

例

6.27.1.22. Vec.dup

dupは、Vecと同じ要素の列を持つ新しいvecを戻す。

例

6.27.1.23. Vec.reverse

reverseは、Vecと同じ要素を逆順で持つ新しいvecを戻す。

例

6.27.1.24. Vec.concat

concatは、Vecの中のvecをつなぎ合わせる。

concatは、Vecの要素がすべてvecであると想定する。concatは、これらのvecの要素をすべて持つ新しいvecを戻す。要素は、これらのvecの順番で、またvecの中の要素の順番で現れる。

事前条件

Vecの要素はすべてvecでなければならない。

例

6.27.1.25. Vec.unconcat(N)

unconcatは、Vecの要素をN個ずつに分割して、それらN個の要素を含むvecのを要素とするvecをもどす。

Vecの要素がE(0), E(1) ,,, E(N-1), E(N), E(N+1) ,,, E(N+(N-1)) ,,, E(m*N), E(m*N+1) ,,, E(m*N+(N-1))のとき、結果のvecは、[E(0) E(1) ,,, E(N-1)], [E(N) E(N+1) ,,, E(N+(N-1))] ,,, [E(m*N) E(m*N+1) ,,, E(m*N+(N-1))]を含む。

事前条件

Nは、正の整数のnumでなければならない。

Vec.size % N == 0

例

6.27.1.26. Vec.just(...[$if_empty])

justはVecが1要素であるとき、その要素を戻す。

Vecが空で、$if_emptyが渡されているとき、justは$if_emptyを末尾呼び出しする。

それ以外の場合、justは例外を投げる。

事前条件

$if_emptyはサンクでなければならない。

例

6.27.1.27. Vec.with_elems(...[$with0 $with1 $with2 ,,,])

with_elemsは、Vecの要素を引数として関数を末尾呼び出しする。

with_elemsは任意個数の関数を取る。これらを順番に、$with0, $with1, $with2, ,,, と呼ぶ。VecのサイズがNのとき、with_elemsは、Vecの要素を引数として$withNを末尾呼び出しする。

事前条件

Vecのサイズは、引数の数よりも小さくなければならない。

$withK (k = 0, 1, 2, ,,,) はK個の引数を取らなければならない。

例

6.27.1.28. Vec.each($consume)

eachは、先頭から末尾に向けて、それぞれの要素について$consumeを呼び出す。

Vecが空でない場合、eachは最後の要素について$consumeを末尾呼び出しする。

事前条件

$consumeは、ひとつの値を取る関数でなければならない。

例

6.27.1.29. Vec.map($transform)

mapは、Vecの要素を$transformで変換した要素を含むvecを戻す。

Vecの要素がE(0), E(1) ,,, E(n-1)のとき、結果のvecの要素はtransform(E(0)) transform(E(1)) ,,, transform(E(n-1))になる。

事前条件

$transformは、ひとつの値を取る関数でなければならない。

例

6.27.1.30. Vec.concat_map($to_vec)

concat_mapは、to_vec(Vecの要素)の結果であるvecを結合したvecを戻す。

事前条件

$to_vecは、ひとつの値を取ってvecを戻す関数でなければならない。

例

6.27.1.31. Vec.filter($include?)

filterは、述語$include?を満たすすべての要素を含むvecを戻す。

事前条件

$include?は述語でなければならない。

例

6.27.1.32. Vec.count($counted?)

countは、述語$counted?を満たす要素の数を整数のnumとして戻す。

事前条件

$counted?は述語でなければならない。

例

6.27.1.33. Vec.fold(Init $combine)

foldは、Initを種として要素を畳み込む。

Vecの要素がE(0) E(1) ,,, E(n-1)のとき、結果はcombine(combine(,,, combine(combine(Init E(0)) E(1)) ,,,) E(n-1))になる。

事前条件

$combineは、ふたつの値を取る関数でなければならない。

例

6.27.1.34. Vec.reduce($combine ...[$empty_fallback])

reduceは、Vecの要素を相互に畳み込む。

Vecが1個以上の要素を持っているとき、reduceはVec.drop_front(1).fold(Vec.front $combine)を末尾呼び出しする。

Vecが空で、$empty_fallbackが与えられているとき、reduceは$empty_fallbackを引数なしで末尾呼び出しする。

Vecが空で、$empty_fallbackが与えられなかったとき、reduceは例外を投げる。

事前条件

$combineは、ふたつの値を取る関数でなければならない。

$empty_fallbackはサンクでなければならない。

例: フォールバックなし

例: フォールバックあり

6.27.1.35. Vec.take_while($include?)

take_whileは、要素が述語$include?を満たすような最長の先頭部分のvecを戻す。

事前条件

$include?は述語でなければならない。

例

6.27.1.36. Vec.drop_while($exclude?)

drop_whileは、要素が述語$exclude?を満たすような最長の先頭部分の後の要素のvecを戻す。

事前条件

$exclude?は述語でなければならない。

例

6.27.1.37. Vec.all?($match?)

all?は、Vecのすべての要素が述語$match?を満たすかどうかを戻す。

事前条件

$match?は述語でなければならない。

例

6.27.1.38. Vec.any?(...[$match?={ true }])

any?は、Vecの要素のひとつ以上が述語$match?を満たすかどうかを戻す。

$match?はオプショナル引数であり、そのデフォルト値は{ true }である。したがって、$match?が渡されなければ、any?はVecが空でないかどうかを戻す。

事前条件

$match?は述語でなければならない。

例

例

6.27.1.39. Vec.have?(Target)

have?は、 == 演算子、つまりop_eqメソッドにおいて、Targetと等しい要素をVecが持っているかどうかを戻す。

Vec.have?(Target)を呼ぶことは、Vec.any?{(:E) Target == E }を呼ぶことと等しい。

例

6.27.1.40. Vec.have_all?(Vals)

have_all?は、Valsのすべての要素をVecが持っているかどうかを戻す。

Vec.have_all?(Vals)を呼ぶことは、Vals.all?{(:T) Vec.have?(T) }を呼ぶことと等しい。

事前条件

Valsは、all?($match?)メソッドを持っていなければならない。

== 演算子、つまりop_eqメソッドで、Vecの要素とValsの要素が比較できなければならない。

例

6.27.1.41. Vec.have_any?(Vals)

have_any?は、Valsのひとつ以上の要素をVecが持っているかどうかを戻す。

Vec.have_any?(Vals)を呼ぶことは、Vals.any?{(:T) Vec.have?(T) }を呼ぶことと等しい。

事前条件

Valsは、any?($match?)メソッドを持っていなければならない。

== 演算子、つまりop_eqメソッドで、Vecの要素とValsの要素が比較できなければならない。

例

6.27.1.42. Vec.sort(...[$up_to?={(:X :Y) X <= Y }])

sortは、要素をVecからコピーして、$up_to?によって昇順に整列したvecを戻す。

比較

要素の比較は$up_to?によって行う。

$up_to?はVecの要素についての全順序関係でなければならない。Vecの要素中のすべてのX, Y, Zについて、$up_to?は次を満たさなければならない。

• 反射律: up_to?(X X)

• 推移律: if up_to?(X Y) && up_to?(Y Z) then up_to?(X Z)

• 反対称律: if up_to?(X Y) && up_to?(Y X) then X is equivalent to Y

• 狭義の連結律: up_to?(X Y) || up_to?(Y X)

安定ソート

sortは安定ソートを行う。Vecの要素E1, E2についてup_to?(E1 E2) && up_to(E2 E1)のとき、E1とE2はVecの中と同じ順番で結果のvecに現れる。

事前条件

$up_to?は、ふたつの値を取ってboolを戻す関数でなければならない。

例

6.27.1.43. Vec.iter(...[From=0 To=Vec.size])

iterメソッドは、[From, To)の範囲のスライスの要素を含むiterを戻す。

事前条件

FromとToは整数のnum値でなければならない。

0 <= From <= To <= Vec.size

例

6.27.1.44. Vec1 + Vec2

+ 演算子、つまりop_addメソッドは、Vec1のすべての要素を先頭に、Vec2のすべての要素を末尾に置いたvecを戻す。

事前条件

Vec2はvec値でなければならない。

例

6.27.1.45. Vec * N

* 演算子、つまりop_mulメソッドは、Vecの要素をN回繰り返したvecを戻す。

事前条件

Nは、非負の整数のnumでなければならない。

例

6.27.1.46. Vec1 == Vec2

== 演算子、つまりop_eqメソッドは、Vec1とVec2が等しいか、つまり、ふたつのvecが同じ順番で同値の要素を持っているかどうかを戻す。

ふたつのvecは次の場合に等しい:

1) Vec1.size == Vec2.size

2) [0, Vec1.size]の範囲のすべてのiについて、Vec1.get(i) == Vec2.get(i)

上記の条件は順番に評価される。また、小さい i から大きい i にかけて評価される。どこかで比較がfalseを戻したら、以降の比較は評価されず、ふたつのvecは等しくないと決まる。

事前条件

Vec1とVec2はvec値でなければならない。

例

6.27.1.47. Vec1 <= Vec2

<= 演算子、つまりop_leメソッドは、要素同士の <= 演算子で定義される順序で、Vec1がVec2以下であるかどうかを戻す。

Vec1は、次の場合にVec2以下である。

1) [0, k) 内のすべてのiについて、Vec1.get(i) <= Vec2.get(i) && Vec2.get(i) <= Vec1.get(i)かつ、! (Vec2.get(k) <= Vec1.get(k))となる非負の整数k (k < min(Vec1.size Vec2.size))が存在する場合、または

2) Vec1.size <= Vec2.sizeであり、[0, Vec1.size)内のすべてのiについて、Vec1.get(i) <= Vec2.get(i) && Vec2.get(i) <= Vec1.get(i)である場合。

比較は小さい添字から大きい添字に向けて行われる。結果が途中で判明した場合、後続する比較は行われない。

事前条件

Vec2はvec値でなければならない。

例

6.27.1.48. Lhs <- Rhs

<- 演算子、つまりop_storeメソッドは、左辺のvecであるLhsと、右辺のvecであるRhsの間で多重代入を行う。

ここで、Lhsの要素はパラメータと、Rhsの要素は引数と呼ぶ。

パラメータと引数

パラメータには三つの種類がある。

• plain_param: ex. varref, vec. 1個の引数が受け取れる。

• opt_param: ex. Varref.opt. 0個か1個の引数が受け取れる。

• rest_param: ex. Varref.rest. 任意の数の引数が受け取れる。

plain_paramとopt_paramは、Lhsの中で任意の回数現れられる。opt_paramが、plain_paramの前に現れてはならない。

Lhsは、末尾に0個か1個のrest_paramが持てる。

NPをplain_paramの数、NOをopt_paramの数とする。ここで、P(0), P(1) ,,, P(NP-1), O(0), O(1) ,,, O(NO-1)がパラメータである。(0 <= i < NP)のそれぞれのiについてP(i)はplain_param、(0 <= j < NO)のそれぞれのjについてO(j)はopt_paramである。

加えて、NAを引数の数、(0 <= k < NA)のそれぞれのkについて、A(k)を引数とする。

Lhsがrest_paramを持つかどうかによって、op_storeのふるまいは変わる。

Lhsがrest_paramを持たない場合

この場合、引数の数NAは、NP <= NA <= NP+NOのときに正しい。

引数の数が正しくないとき、op_storeは例外を投げる。

引数の数が正しいとき、op_storeは、それぞれのパラメータについて次のようにメソッドを呼ぶ。

• P(k).op_store(A(k)) for each k (0 <= k < NP)

• O(k - NP).pass_arg(A(k)) for each k (NP <= k < NA)

• O(k - NP).pass_nothing for each k (NA <= k < NP+NO)

Lhsがrest_param、Rを持つ場合

この場合、引数の数NAは、NP <= NAのときに正しい。

引数の数が正しくないとき、op_storeは例外を投げる。

引数の数が正しいとき、op_storeは、それぞれのパラメータについて次のようにメソッドを呼ぶ。

• P(k).op_store(A(k)) for each k (0 <= k < NP)

• O(k - NP).pass_arg(A(k)) for each k (NP <= k < NA)

• O(k - NP).pass_nothing for each k (NA <= k < NP+NO)

• R.pass_rest(vec of A(k) for each k (NP+NO <= k < NA))

事前条件

Rhsはvecでなければならない。

例

6.27.1.49. Vec.repr

reprは、Vecのstr表現を戻す。

例

6.27.2. VEC.is?(Val)

is?は、Valがvecであるかどうかを戻す。

6.27.3. VEC.from_each(Eacher)

from_eachは、Eacherの要素をすべて含むvecを新しく作って戻す。

Eacherは、.each($consume)メソッドを持っていなければならない。eachは、それぞれの要素について$consumeを呼び出すものでなければならない。

例