Nim-ACL

Slice utilities

概要

sliceutilsはNimのSliceへ、逆順・step付き列挙、 配列の部分取得・step付き代入を追加します。

rangeをデータ構造の半開区間へ変換する用途には atcoder/rangeutilsを使用します。

import

import atcoder/extra/other/sliceutils

index

let values = @[10, 20, 30]
let indices = values.index

doAssert indices.a == 0
doAssert indices.b == 2

空の配列では0 .. -1を返します。

逆順列挙

for i in rev(1 .. 4):
  echo i

4, 3, 2, 1の順に列挙します。

UFCSでは括弧を付けます。

for i in (1 .. 4).rev():
  echo i

(1 .. 4).revのように括弧を省略したproperty形式は 利用できません。

step付き列挙

>>は小さいindexから、<<は大きいindexから列挙します。

for i in ((1 .. 7) >> 2):
  echo i
# 1, 3, 5, 7

for i in ((1 .. 7) << 2):
  echo i
# 7, 5, 3, 1

stepは0以外である必要があります。

整数の列挙

for i in 5:
  echo i

0, 1, 2, 3, 4を列挙します。

部分取得

let values = @[10, 20, 30, 40, 50]

doAssert values[1 .. 3] == @[20, 30, 40]

step付き代入

var values = @[0, 0, 0, 0, 0]

values[(0 .. 4) >> 2] =
  @[10, 20, 30]

doAssert values == @[10, 0, 20, 0, 30]

右辺の長さは列挙される位置数と一致させてください。

公開API

proc index(openArray): Slice[int]
proc rev(Slice): ReversedSlice
iterator items(int): int
proc `>>`(Slice, step): StepSlice
proc `<<`(Slice, step): StepSlice
proc low(StepSlice)
proc high(StepSlice)
iterator items(ReversedSlice)
iterator items(StepSlice)
proc `[]`(openArray, Slice): seq
proc `[]=`(var openArray, StepSlice, openArray)

ReversedSliceとStepSliceは実装用の戻り値型です。 利用側で型名を直接指定する必要はありません。

境界条件

計算量

列挙または操作する要素数をkとします。

操作 計算量
index O(1)
revの構築 O(1)
step Sliceの構築 O(1)
列挙 O(k)
部分取得 O(k)
step付き代入 O(k)

関連

検証

専用testで以下を確認しています。