Kuina-chan

くいなちゃん2018年12月11日


プログラミング言語Kuin」の逆引き辞典3、リスト型とスタック型とキュー型と辞書型の扱い方についてです。

目次

1リスト型を扱う

「リスト」とは、配列と同様、同じ型の複数の変数をまとめて扱える型ですが、配列に比べて要素の追加、削除、挿入が高速に行えるため、動的に要素数が変わる場合に効率的な型です。
一方、要素番号を指定してアクセスする処理はリストよりも配列のほうが速く、要素数が頻繁に変わらない多くのケースでは配列のほうが効率的です。

1.1リストを作成する



Kuinでのリストは「list<型名>」と書くことで、その型の値が複数集まったリストを表すことができます(図1-1)。
  1. func main()
  2.   var items: list<int>
  3.   do items :: #list<int>
  4.   do items.add(3)
  5.   do items.add(5)
  6. end func
図1-1: リスト
2行目のように「list<int>」とすると、int型のリストになります。
3行目のように「#list<型名>」と書くことで、リストのインスタンスが生成されます。
4~5行目のように「.add」メソッドを使うことで、リストの末尾に要素が追加できます。 このプログラムの場合、先頭から順に「3」「5」の値が格納されます。

1.2リストの要素数を得る



リストの要素数は要素数演算子「^」で得ることができます(図1-2)。
  1. func main()
  2.   var items: list<int> :: #list<int>
  3.   do items.add(3)
  4.   do items.add(5)
  5.   var num: int :: ^items {2}
  6. end func
図1-2: リストの要素数

1.3リストの要素を順番に辿る



リストの要素には、リストが持つポインタを使ってアクセスします。 リストの要素を順番に辿るには、まずポインタを先頭に設定してから、終端に辿り着くまで1つずつ進めます(図1-3)。
  1. func main()
  2.   var items: list<int> :: #list<int>
  3.   do items.add(3)
  4.   do items.add(5)
  5.   do items.head() {ポインタを先頭に設定}
  6.   while(!items.term()) {ポインタが終端を超えていなければ繰り返し}
  7.     var item: int :: items.get() {ポインタの位置の要素を取得}
  8.     do items.next() {ポインタを末尾へ進める}
  9.   end while
  10. end func
図1-3: リストの走査
このプログラムではwhileの中が計2回実行され、変数itemには1回目には「3」、2回目には「5」が入っています。
リストの末尾から先頭に向かって逆順に辿るには図1-4のように書きます。
  1. func main()
  2.   var items: list<int> :: #list<int>
  3.   do items.add(3)
  4.   do items.add(5)
  5.   do items.tail() {ポインタを末尾に設定}
  6.   while(!items.term()) {ポインタが終端を超えていなければ繰り返し}
  7.     var item: int :: items.get() {ポインタの位置の要素を取得}
  8.     do items.prev() {ポインタを先頭へ進める}
  9.   end while
  10. end func
図1-4: リストの逆順の走査

1.4リストの要素を削除する



リストの要素を削除するには「.del」メソッドを使います。 「.del」メソッドを呼び出すと、ポインタの位置の要素が削除され、ポインタは次の要素を指すようになります(図1-5)。
  1. func main()
  2.   var items: list<int> :: #list<int>
  3.   do items.add(3)
  4.   do items.add(4)
  5.   do items.add(5)
  6.   do items.head()
  7.   while(!items.term())
  8.     var item: int :: items.get()
  9.     if(item = 4)
  10.       do items.del() {ポインタの位置の要素を削除して末尾へ進める}
  11.     else
  12.       do items.next()
  13.     end if
  14.   end while
  15. end func
図1-5: リストの要素の削除
実行すると、リストの先頭から「3」「4」「5」の要素が入っていたのが、「4」が削除され「3」「5」だけになります。
ポインタをその位置の要素を指すようにしたまま、その次の要素を削除するには「.delNext」メソッドを使います(図1-6)。
  1. func main()
  2.   var items: list<int> :: #list<int>
  3.   do items.add(3)
  4.   do items.add(4)
  5.   do items.add(5)
  6.   do items.head()
  7.   do items.delNext()
  8. end func
図1-6: リストの次の要素を削除
実行すると「4」が削除され、リストの先頭から順に「3」「5」となります。

1.5リストのポインタの位置に要素を挿入する



リストのポインタの位置に要素を挿入するには「.ins」メソッドを使います。 「.ins」メソッドを使うと、ポインタをその位置の要素を指すようにしたまま、その前に要素を挿入します(図1-7)。
  1. func main()
  2.   var items: list<int> :: #list<int>
  3.   do items.add(3)
  4.   do items.add(5)
  5.   do items.head()
  6.   do items.next()
  7.   do items.ins(4)
  8. end func
図1-7: リストの要素の挿入
実行すると、最終的にリストの先頭から順に「3」「4」「5」となります。

1.6リストを配列に変換する



リストを配列に変換するには「.toArray」メソッドを使います(図1-8)。
  1. func main()
  2.   var items: list<int> :: #list<int>
  3.   do items.add(3)
  4.   do items.add(5)
  5.   var array: []int :: items.toArray() {[3, 5]}
  6. end func
図1-8: リストの配列化

2スタック型やキュー型を扱う

「スタック」は後に追加した要素から先に取り出されるデータ構造の型で、「キュー」は追加した順に要素が取り出されるデータ構造の型です。

2.1スタックやキューを作成する



Kuinでスタックを表すには「stack<型名>」と書き、キューを表すには「queue<型名>」と書きます(図2-1)。
  1. func main()
  2.   var stackItems: stack<int>
  3.   var queueItems: queue<int>
  4.   do stackItems :: #stack<int>
  5.   do queueItems :: #queue<int>
  6.   do stackItems.add(3)
  7.   do queueItems.add(3)
  8. end func
図2-1: スタックとキュー
2~3行目のように「stack<int>」「queue<int>」とすると、int型のスタックやキューになります。
4~5行目のように「#stack<型名>」「#queue<型名>」と書くことで、スタックやキューのインスタンスが生成されます。
6~7行目のように「.add」メソッドを使うことで、スタックやキューに要素が追加できます。

2.2スタックやキューの要素数を得る



スタックやキューの要素数は要素数演算子「^」で得ることができます(図2-2)。
  1. func main()
  2.   var stackItems: stack<int> :: #stack<int>
  3.   var queueItems: queue<int> :: #queue<int>
  4.   do stackItems.add(3)
  5.   do queueItems.add(3)
  6.   var stackNum: int :: ^stackItems {1}
  7.   var queueNum: int :: ^queueItems {1}
  8. end func
図2-2: スタックやキューの要素数
スタックやキューが空かどうかを判定する場合には、「^」演算子を使って結果が0かどうかを調べます。

2.3スタックやキューから要素を取得して削除する



スタックやキューから要素を取得するには「.get」メソッドを使います。 取得した要素はスタックやキューから削除されます(図2-3)。
  1. func main()
  2.   var stackItems: stack<int> :: #stack<int>
  3.   var queueItems: queue<int> :: #queue<int>
  4.   do stackItems.add(1)
  5.   do stackItems.add(2)
  6.   do queueItems.add(1)
  7.   do queueItems.add(2)
  8.   var item: int
  9.   do item :: stackItems.get() {2}
  10.   do item :: stackItems.get() {1}
  11.   do item :: queueItems.get() {1}
  12.   do item :: queueItems.get() {2}
  13. end func
図2-3: スタックやキューの要素の取得

2.4スタックやキューから要素を削除せずに取得する



スタックやキューから要素を削除せずに取得するには「.peek」メソッドを使います(図2-4)。
  1. func main()
  2.   var stackItems: stack<int> :: #stack<int>
  3.   var queueItems: queue<int> :: #queue<int>
  4.   do stackItems.add(1)
  5.   do stackItems.add(2)
  6.   do queueItems.add(1)
  7.   do queueItems.add(2)
  8.   var item: int
  9.   do item :: stackItems.peek() {2}
  10.   do item :: stackItems.peek() {2}
  11.   do item :: queueItems.peek() {1}
  12.   do item :: queueItems.peek() {1}
  13. end func
図2-4: スタックやキューの要素を削除せずに取得

3辞書型を扱う

「辞書」はキーと値のペアを複数持ち、キーから値が高速に検索できるデータ構造の型です。

3.1辞書を作成する



Kuinで辞書を表すには「dict<キーの型名, 値の型名>」と書きます(図3-1)。
  1. func main()
  2.   var items: dict<[]char, int>
  3.   do items :: #dict<[]char, int>
  4.   do items.add("one", 1)
  5.   do items.add("two", 2)
  6.   do items.add("three", 3)
  7. end func
図3-1: 辞書
2行目のように「dict<[]char, int>」とすると、キーが[]char型、値がint型の辞書になります。
3行目のように「#dict<キーの型名, 値の型名>」と書くことで、辞書のインスタンスが生成されます。
4行目のように「.add」メソッドを使うことで、辞書に要素が追加できます。

3.2辞書の要素数を得る



辞書の要素数は要素数演算子「^」で得ることができます(図3-2)。
  1. func main()
  2.   var items: dict<[]char, int> :: #dict<[]char, int>
  3.   do items.add("one", 1)
  4.   do items.add("two", 2)
  5.   do items.add("three", 3)
  6.   var num: int :: ^items {3}
  7. end func
図3-2: 辞書の要素数

3.3辞書から要素を取得する



辞書から要素を取得するには「.get」メソッドを使います(図3-3)。
  1. func main()
  2.   var items: dict<[]char, int> :: #dict<[]char, int>
  3.   do items.add("one", 1)
  4.   do items.add("two", 2)
  5.   do items.add("three", 3)
  6.   var existed: bool
  7.   var item: int :: items.get("two", &existed) {item = 2, existed = true}
  8. end func
図3-3: 辞書の要素の取得
辞書にキーが見つからなければ、existedはfalseになり、戻り値にはデフォルト値(int型の場合は0)が返ります。

3.4辞書に要素が存在するかを判定する



辞書に要素が存在するかを判定するには「.exist」メソッドを使います(図3-4)。
  1. func main()
  2.   var items: dict<[]char, int> :: #dict<[]char, int>
  3.   do items.add("one", 1)
  4.   do items.add("two", 2)
  5.   do items.add("three", 3)
  6.   var existence: bool
  7.   do existence :: items.exist("two") {true}
  8.   do existence :: items.exist("five") {false}
  9. end func
図3-4: 辞書の要素の存在の判定

3.5辞書の全要素を順番に処理する



辞書に存在する全要素を順に処理するには「.forEach」メソッドを使います。 コールバック関数を渡すと、各要素に対してその関数が呼ばれる流れです(図3-5)。
  1. func main()
  2.   var items: dict<[]char, int> :: #dict<[]char, int>
  3.   do items.add("one", 1)
  4.   do items.add("two", 2)
  5.   do items.add("three", 3)
  6.  
  7.   var str: lib@Str :: #lib@Str {文字列をラップしたクラス}
  8.   do str.value :: "" {空文字列を設定しておく}
  9.   var completed: bool :: items.forEach(callback, str) {true}
  10.  
  11.   func callback(key: []char, value: int, data: lib@Str): bool
  12.     do data.value :~ "\{key}=\{value}." {各要素に対して文字列を追加する}
  13.     ret true {継続する場合はtrue、中止する場合はfalseを返す}
  14.   end func
  15. end func
図3-5: 辞書の走査
9行目で「.forEach」メソッドを呼び出し、第1引数のコールバック関数にcallback関数を渡しています。 callback関数は11~14行目で定義しています。
「.forEach」の第2引数にはコールバック関数に渡すための任意のデータが指定できます。 ただしクラスでなければなりません。 今回は文字列型を渡したいのですが、文字列型はクラスではないため、文字列型をラップした「lib@Str」クラスを使っています。
コールバック関数が呼び出されるときの要素の順番は、キーを昇順に並べたときの順番です。 「"one"」「"two"」「"three"」を昇順(辞書順)に並べると「"one"」「"three"」「"two"」になるため、最終的に出来上がる「str.value」の値は「"one=1.three=3.two=2."」になります。
コールバック関数の戻り値をfalseにすると、「.forEach」の処理をそこで終わらせることができます。 終わらせた場合には「.forEach」メソッドの戻り値もfalseになり、最後まで処理した場合には戻り値はtrueになります。

3.6辞書を配列に変換する



辞書を配列に変換するには「.toArrayKey」や「.toArrayValue」メソッドを使います(図3-6)。
  1. func main()
  2.   var items: dict<[]char, int> :: #dict<[]char, int>
  3.   do items.add("one", 1)
  4.   do items.add("two", 2)
  5.   do items.add("three", 3)
  6.   var keys: [][]char :: items.toArrayKey() {["one", "three", "two"]}
  7.   var values: []int :: items.toArrayValue() {[1, 3, 2]}
  8. end func
図3-6: 辞書の配列化
配列化するときの要素の順番は、キーを昇順に並べたときの順番です。
1544539397jaf