nimコレクション操作

概要

nimのコレクション操作をコツコツと。

• algorithm
• tables
• sets
• lists
• queues
• critbits
• intsets

以下メモ

同じ値で埋める(fill)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary : array[0..3,int]
  # 範囲指定なし
  fill(ary,1)
  for x in ary:
    echo x
  # 範囲指定
  fill(ary,0,3,5)
  for x in ary:
    echo x

(stdout)
1
1
1
1
5
5
5
5

リバース

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[1,2,3,4]
  echo ary
  ary.reverse
  echo ary
  var ary2 = ary.reversed
  echo ary2

(stdout)
@[1, 2, 3, 4]
@[4, 3, 2, 1]
@[1, 2, 3, 4]

検索(バイナリサーチ)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[1,2,3,4,5,6,7,8,9]
  echo ary.binarySearch(8)
  echo ary.smartBinarySearch(3)

(stdout)
7
2

lowerBound

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[1,2,3,4,5,6]
  for x in 0..10 :
    echo x," ",ary.lowerBound(x)

(stdout)
0 0
1 0
2 1
3 2
4 3
5 4
6 5
7 6
8 6
9 6
10 6

ソート

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  # cmp関数でソート
  var ary = @[3,4,1,8,6,5,7,0,1]
  echo ary
  ary.sort(system.cmp[int])
  echo ary

(stdout)
@[3, 4, 1, 8, 6, 5, 7, 0, 1]
@[0, 1, 1, 3, 4, 5, 6, 7, 8]

ソート(procを渡す)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[3,4,1,8,6,5,7,0,1]
  ary.sort( proc (x,y:int) : int = cmp(x,y) )
  echo ary

(stdout)
@[0, 1, 1, 3, 4, 5, 6, 7, 8]

ソート(doを使ったソート)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[3,4,1,8,6,5,7,0,1]
  ary.sort do (x,y:int) -> int : result = cmp(x,y)
  echo ary

(stdout)
@[0, 1, 1, 3, 4, 5, 6, 7, 8]

ソート(sorted)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  # doを使ったソート
  var ary = @[3,4,1,8,6,5,7,0,1]
  var ary2 = ary.sorted do (x,y:int) -> int :
    result = cmp(x,y)
  echo "original=",ary
  echo "sorted  =",ary2
  echo ary.isSorted(system.cmp[int])
  echo ary2.isSorted(system.cmp[int])

(stdout)
original=@[3, 4, 1, 8, 6, 5, 7, 0, 1]
sorted  =@[0, 1, 1, 3, 4, 5, 6, 7, 8]
false
true

順列 (prevPermutation)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[1,2,4,3]
  ary.prevPermutation
  echo ary

(stdout)
@[1, 2, 3, 4]

templateを使ったソート

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[3,4,1,8,6,5,7,0,1]
  echo ary.sortedByIt(it)

(stdout)
@[0, 1, 1, 3, 4, 5, 6, 7, 8]

hashesによるハッシュを取得

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var name1 = "Mr.スポック"
  var name2 = "Mr.スポック"
  echo name1.hash == name2.hash

(stdout)
true

tables サンプル

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
#[
tableは、ハッシュキーを拡張したものっぽいです。
独自構造体？をキーにする場合は、hash関数を実装しないと動作しないようです。
]#
type
  Person = object
    firstName, lastName: string
proc hash(x: Person): Hash =
  ## Piggyback on the already available string hash proc.
  ##
  ## Without this proc nothing works!
  result = x.firstName.hash !& x.lastName.hash
  result = !$result
proc `$`(x: Person) : string =
  result = x.firstName
block:
  var
    salaries: Table[Person,int] = initTable[Person, int]()
    p1, p2, p3: Person
  p1.firstName = "Steven"
  p1.lastName = "Rogers"
  salaries[p1] = 30_000
  p2.firstName = "Tony"
  p2.lastName = "Stark"
  salaries[p2] = 40_000
  p3.firstName = "Bruce"
  p3.lastName = "Banner"
  echo "contains=",salaries.contains(p1)
  echo "get value=",salaries[p1]
  echo "length=",salaries.len
  echo "get or default=", salaries.getOrDefault(p3)
  ### toTableを使った初期化
  let salaries2: Table[Person,int] = {p1:30_000,p2:40_000}.toTable
  echo salaries == salaries2
  #salaries2[p3] = 10_000
  let salaries3: OrderedTable[Person,int] = {p1:30_000,p2:40_000}.toOrderedTable
  for k,v in salaries :
    echo k
  for k,v in salaries2 :
    echo k
  for k,v in salaries3 :
    echo k

(stdout)
contains=true
get value=30000
length=2
get or default=0
true
Steven
Tony
Steven
Tony
Steven
Tony

COuntTable　キーのみで、その数をカウントする

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var count = initCountTable[string]()
  count.inc("DEC")
  count.inc("DEC")
  count.inc("ABC")
  count.inc("ABC")
  count.inc("ABC")
  echo count
  count.sort
  echo count

(stdout)
{ABC: 3, DEC: 2}
{ABC: 3, DEC: 2}

HashSet

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  # initSetで初期化
  var hashSet1: HashSet[string] = initSet[string]()
  hashSet1.incl("key1")
  hashSet1.incl("key2")
  echo "hashSet1=>",hashSet1
  echo "contains=>",hashSet1.contains("key1")
  # 取り除く
  hashSet1.excl("key1")
  hashSet1.excl("key2")
  echo "hashSet1=>",hashSet1
  # 再び追加
  hashSet1.incl("key1")
  hashSet1.incl("key2")
  # toSetで初期化
  var hashSet2 = ["key1","key2"].toSet
  echo "hashSet2=>",hashSet2
  echo "equals  =>",hashSet1 == hashSet2
  for x in hashSet1.items :
    echo "item=>",x

(stdout)
hashSet1=>{key2, key1}
contains=>true
hashSet1=>{}
hashSet2=>{key2, key1}
equals  =>true
item=>key2
item=>key1

OrderedHashSet(値を追加した順番を保持)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  # initOrderedSetで初期化
  var hashSet1: OrderedSet[string] = initOrderedSet[string]()
  hashSet1.incl("key1")
  hashSet1.incl("key2")
  echo "hashSet1=>",hashSet1
  # toOrderedSetで初期化
  var hashSet2: OrderedSet[string] = ["key1","key2"].toOrderedSet
  echo "hashSet2=>",hashSet2
  #echo hashSet1 == hashSet2
  var hashSet3: OrderedSet[string] = initOrderedSet[string]()
  hashSet3.incl("key1")
  hashSet3.incl("key2")
  echo "equals=>",hashSet1 == hashSet3

(stdout)
hashSet1=>{key1, key2}
hashSet2=>{key1, key2}
equals=>true

双方向リンクリスト

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var list1 : DoublyLinkedList[int] = initDoublyLinkedList[int]()
  # 末尾に追加
  list1.append(1)
  list1.append(2)
  list1.append(3)
  list1.append(4)
  echo "list1=>",list1
  # 先頭に追加
  list1.prepend(4)
  list1.prepend(5)
  list1.prepend(6)
  list1.prepend(7)
  echo "list1=>",list1
  # 検索
  echo "find=>",list1.find(7).value
  # 削除
  list1.remove(list1.find(7))
  echo "list1=>",list1

(stdout)
list1=>[1, 2, 3, 4]
list1=>[7, 6, 5, 4, 1, 2, 3, 4]
find=>7
list1=>[6, 5, 4, 1, 2, 3, 4]

Queue

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var q : Queue[string] = initQueue[string]()
  q.enqueue("abc")
  q.add("def")
  q.add("ghi")
  echo "len=>",q.len
  echo "q  =>",q
  var v = q.dequeue()
  echo "v  =>",v
  echo "q  =>",q
  for v in q :
    echo "val=>",v
  echo "q  =>",q

(stdout)
len=>3
q  =>[abc, def, ghi]
v  =>abc
q  =>[def, ghi]
val=>def
val=>ghi
q  =>[def, ghi]

Crit-Bit ハッシュ ( http://blog.livedoor.jp/dankogai/archives/51853853.html )

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var r: CritBitTree[string]
  r["abc"] = "ABC"
  r["def"] = "DEF"
  echo "tree=>",r.contains("abc")
  for x in r.keys :
    echo "key=>",x
  for k,v in r :
    echo "key=>",k," val=>",v

(stdout)
tree=>true
key=>abc
key=>def
key=>abc val=>ABC
key=>def val=>DEF

intsets

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var intSet: IntSet = initIntSet()
  # キーを追加
  intSet.incl 1
  intSet.incl 2
  # ダンプ
  echo intSet
  for x in intSet.items :
    echo "key=>",x
  # 格納されているか？
  echo "contains(1)=>",intSet.contains(1)
  intSet.excl 1
  echo "contains(1)=>",intSet.contains(1)
  # containsOrInclを試す
  echo "contains(3)=>",intSet.contains(3)
  echo "           =>",intSet.containsOrIncl(3)
  echo "contains(3)=>",intSet.contains(3)

(stdout)
{1, 2}
key=>1
key=>2
contains(1)=>true
contains(1)=>false
contains(3)=>false
           =>false
contains(3)=>true

sequtils.concat

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  # サンプルのまんま
  let
    s1 = @[1, 2, 3]
    s2 = @[4, 5]
    s3 = @[6, 7]
    total = concat(s1, s2, s3)
  echo total

(stdout)
@[1, 2, 3, 4, 5, 6, 7]

sequtils.cycle

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    s = @[1, 2, 3]
    total = s.cycle(3)
  echo total

(stdout)
@[1, 2, 3, 1, 2, 3, 1, 2, 3]

sequtils.repeat

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    total1 = repeat(5, 3)
    total2 = repeat(@[1,2,3], 3)
  echo "total1=>",total1
  echo "total2=>",total2

(stdout)
total1=>@[5, 5, 5]
total2=>@[@[1, 2, 3], @[1, 2, 3], @[1, 2, 3]]

sequtils.deduplicate

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    dup1 = @[1, 1, 3, 4, 2, 2, 8, 1, 4]
    dup2 = @["a", "a", "c", "d", "d"]
    unique1 = deduplicate(dup1)
    unique2 = deduplicate(dup2)
  echo "unique1=>",unique1
  echo "unique2=>",unique2

(stdout)
unique1=>@[1, 3, 4, 2, 8]
unique2=>@[a, c, d]

sequtils.zip

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    short = @[1, 2, 3]
    long = @[6, 5, 4, 3, 2, 1]
    words = @["one", "two", "three"]
    zip1 = zip(short, long)
    zip2 = zip(short, words)
  echo "zip1=>", zip1
  echo "zip2=>", zip2
  echo "zip1[2].b=>", zip1[2].b
  echo "zip2[2].b=>", zip2[2].b

(stdout)
zip1=>@[(a: 1, b: 6), (a: 2, b: 5), (a: 3, b: 4)]
zip2=>@[(a: 1, b: one), (a: 2, b: two), (a: 3, b: three)]
zip1[2].b=>4
zip2[2].b=>three

sequtils.distribute

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let numbers = @[1, 2, 3, 4, 5, 6, 7]
  echo "(2      )=>",numbers.distribute(2)
  echo "(2,false)=>",numbers.distribute(2, false)
  echo "(3      )=>",numbers.distribute(3)
  echo "(3,false)=>",numbers.distribute(3, false)
  echo "(4      )=>",numbers.distribute(4)
  echo "(4,false)=>",numbers.distribute(4, false)
  echo "(5      )=>",numbers.distribute(5)
  echo "(5,false)=>",numbers.distribute(5, false)
  echo "(6      )=>",numbers.distribute(6)
  echo "(6,false)=>",numbers.distribute(6, false)

(stdout)
(2      )=>@[@[1, 2, 3, 4], @[5, 6, 7]]
(2,false)=>@[@[1, 2, 3, 4], @[5, 6, 7]]
(3      )=>@[@[1, 2, 3], @[4, 5], @[6, 7]]
(3,false)=>@[@[1, 2, 3], @[4, 5, 6], @[7]]
(4      )=>@[@[1, 2], @[3, 4], @[5, 6], @[7]]
(4,false)=>@[@[1, 2], @[3, 4], @[5, 6], @[7]]
(5      )=>@[@[1, 2], @[3, 4], @[5], @[6], @[7]]
(5,false)=>@[@[1, 2], @[3, 4], @[5, 6], @[7], @[]]
(6      )=>@[@[1, 2], @[3], @[4], @[5], @[6], @[7]]
(6,false)=>@[@[1, 2], @[3, 4], @[5, 6], @[7], @[], @[]]

sequtils.map

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    a = @[1, 2, 3, 4]
    b = map(a, proc(x: int): string = $x)
    c = a.map do (x:int) -> string : $(x+1)
  echo "b=>",b
  echo "c=>",c

(stdout)
b=>@[1, 2, 3, 4]
c=>@[2, 3, 4, 5]

sequtils.apply(var 引数が渡される) deprecatedらしいです。

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var a = @["1", "2", "3", "4"]
  echo a
  map(a, proc(x: var string) = x &= "42")
  echo a

(stdout)
@[1, 2, 3, 4]
@[142, 242, 342, 442]

sequtils.filter

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    colors = @["red", "yellow", "black"]
    f1 = filter(colors, proc(x: string) : bool = x.len < 6)
    f2 = filter(colors) do (x: string) -> bool : x.len > 5
  echo "f1=>",f1
  echo "f2=>",f2
  echo "abc".startsWith("a")
  let f3 = colors.map(
    proc(x:string)  : string = x & " is color"
  ).filter(
    proc (x:string) : bool = x.find("black") != -1
  )
  echo f3

(stdout)
f1=>@[red, black]
f2=>@[yellow]
true
@[black is color]

sequtils.keepIf

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var floats = @[13.0, 12.5, 5.8, 2.0, 6.1, 9.9, 10.1]
  keepIf(floats, proc(x: float): bool = x > 10)
  echo "floats=>",floats

(stdout)
floats=>@[13.0, 12.5, 10.1]

sequtils.delete

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let outcome = @[1,1,1,1,1,1,1,1]
  var dest = @[1,1,1,2,2,2,2,2,2,1,1,1,1,1]
  dest.delete(3, 8)
  echo "outcom=>",outcome

(stdout)
outcom=>@[1, 1, 1, 1, 1, 1, 1, 1]

sequtils.insert

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var dest = @[1,1,1,1,1,1,1,1]
  let
    src = @[2,2,2,2,2,2]
    outcome = @[1,1,1,2,2,2,2,2,2,1,1,1,1,1]
  dest.insert(src, 3)
  echo "dest=>",dest

(stdout)
dest=>@[1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1]

sequtils.all すべての要素にたいして条件を満たすかどうかをチェック

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let numbers = @[1, 4, 5, 8, 9, 7, 4]
  echo all(numbers, proc (x: int): bool = return x < 10)
  echo all(numbers, proc (x: int): bool = return x < 9)

(stdout)
true
false

sequtils.any どれか１つの要素にたいして条件を満たすかどうかをチェック

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let numbers = @[1, 4, 5, 8, 9, 7, 4]
  echo any(numbers, proc (x: int): bool = return x < 10)
  echo any(numbers, proc (x: int): bool = return x > 9)
## sequtils マクロ

(stdout)
true
false

filterIt

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    temperatures = @[-272.15, -2.0, 24.5, 44.31, 99.9, -113.44]
    acceptable = filterIt(temperatures, it < 50 and it > -10)
    notAcceptable = filterIt(temperatures, it > 50 or it < -10)
  echo "acceptable   =>",acceptable
  echo "notAcceptable=>",notAcceptable

(stdout)
acceptable   =>@[-2.0, 24.5, 44.31]
notAcceptable=>@[-272.15, 99.90000000000001, -113.44]

keepIfIf

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var candidates = @["foo", "bar", "baz", "foobar"]
  keepItIf(candidates, it.len == 3 and it[0] == 'b')
  echo "candidates=>",candidates

(stdout)
candidates=>@[bar, baz]

allIt

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let numbers = @[1, 4, 5, 8, 9, 7, 4]
  echo "numbers=>",allIt(numbers, it < 10)
  echo "numbers=>",allIt(numbers, it < 9)

(stdout)
numbers=>true
numbers=>false

anyIt

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let numbers = @[1, 4, 5, 8, 9, 7, 4]
  echo "numbers=>",anyIt(numbers, it > 8)
  echo "numbers=>",anyIt(numbers, it > 9)

(stdout)
numbers=>true
numbers=>false

toSeq

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    numeric = @[1, 2, 3, 4, 5, 6, 7, 8, 9]
    odd_numbers = toSeq(filter(numeric) do (x: int) -> bool:
      if x mod 2 == 1:
        result = true)
  echo "odd_numbers", odd_numbers

(stdout)
odd_numbers@[1, 3, 5, 7, 9]

foldl

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    numbers = @[5, 9, 11]
    addition = foldl(numbers, a + b)
    subtraction = foldl(numbers, a - b)
    multiplication = foldl(numbers, a * b)
    words = @["nim", "is", "cool"]
    concatenation = foldl(words, a & b)
  echo addition , " Addition is (((5)+9)+11)"
  echo subtraction  , " Subtraction is (((5)-9)-11)"
  echo multiplication , " Multiplication is (((5)*9)*11)"
  echo concatenation

(stdout)
25 Addition is (((5)+9)+11)
-15 Subtraction is (((5)-9)-11)
495 Multiplication is (((5)*9)*11)
nimiscool

foldl 初期値あり

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    numbers = @[0, 8, 1, 5]
    digits = foldl(numbers, a & (chr(b + ord('0'))), "")
  echo digits

(stdout)

foldr

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    numbers = @[5, 9, 11]
    addition = foldr(numbers, a + b)
    subtraction = foldr(numbers, a - b)
    multiplication = foldr(numbers, a * b)
    words = @["nim", "is", "cool"]
    concatenation = foldr(words, a & b)
  echo addition , " Addition is (5+(9+(11)))"
  echo subtraction , " Subtraction is (5-(9-(11)))"
  echo multiplication, " Multiplication is (5*(9*(11)))"
  echo concatenation

(stdout)
25 Addition is (5+(9+(11)))
7 Subtraction is (5-(9-(11)))
495 Multiplication is (5*(9*(11)))
nimiscool

mapIt

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    nums = @[1, 2, 3, 4]
    strings = nums.mapIt(4 * it)
  echo "strings=>",strings

(stdout)
strings=>@[4, 8, 12, 16]

mapIt

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    nums = @[1, 2, 3, 4]
    strings = nums.mapIt(4 * it)
  echo "strings=>",strings

(stdout)
strings=>@[4, 8, 12, 16]

applyIt(自分自身に適用)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var nums = @[1, 2, 3, 4]
  nums.applyIt(it * 3)
  echo nums[0] + nums[3]

(stdout)
15

newSeqWith

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
import random
block:
  var seq2D = newSeqWith(4, newSeq[bool](4))
  seq2D[0][0] = true
  seq2D[1][0] = true
  seq2D[0][1] = true
  echo seq2D
  var seqRand = newSeqWith(4, random(4))
  echo seqRand

(stdout)