NEPLg2 Standard Library

list: 単方向たんほうこう連結れんけつリストを扱うライブラリ

目的もくてき:

cons/head/tail/get/len/reverse など、リスト処理の基本 API を提供します。
空リスト・範囲外アクセスを Option で安全に扱える形で提供します。

実装じっそう:

ノードは [value:.T][next:i32] レイアウトでヒープ確保します。
空リストは 0 ポインタで表現します。

注意ちゅうい:

list_get は範囲外や負 index で Option::None を返します。
list_free は循環リストを想定していません。
list_reverse は新しいノード列を構築するため、元リストと逆順リストは別管理です。

計算量けいさんりょう:

list_nil/list_cons/list_head/list_tail/list_is_empty は O(1)。
list_len/list_get/list_free/list_reverse は O(n)。

追加の使い方:

TEST

#entry main
#target std
#import "alloc/collections/list" as *
#import "alloc/string" as *
#import "core/option" as *
fn main <()*>i32> ():
    let base0 <List<i32>>:
        list_nil<i32>
        |> list_push_front<i32> 3
        |> list_push_front<i32> 2
        |> list_push_front<i32> 1
    let ok0 if eq list_len<i32> base0 3 1 0;
    let base1 <List<i32>>:
        list_nil<i32>
        |> list_push_front<i32> 3
        |> list_push_front<i32> 2
        |> list_push_front<i32> 1
    let ok1 match list_head<i32> base1:
        Option::Some x:
            if eq x 1 1 0
        Option::None:
            0
    let base2 <List<i32>>:
        list_nil<i32>
        |> list_push_front<i32> 3
        |> list_push_front<i32> 2
        |> list_push_front<i32> 1
    let ok2 match list_get<i32> base2 1:
        Option::Some x:
            if eq x 2 1 0
        Option::None:
            0
    let base3 <List<i32>>:
        list_nil<i32>
        |> list_push_front<i32> 3
        |> list_push_front<i32> 2
        |> list_push_front<i32> 1
    let ok3 match list_tail<i32> base3:
        Option::Some t:
            if eq list_len<i32> t 2 1 0
        Option::None:
            0
    let s01 <i32> add ok0 ok1;
    let s23 <i32> add ok2 ok3;
    add s01 s23

使い方:

TEST

#entry main
#target std
#import "alloc/collections/list" as *
#import "alloc/string" as *
#import "core/option" as *
fn main <()*>i32> ():
    let src0 <List<str>>:
        list_nil<str>
        |> list_push_front<str> "c"
        |> list_push_front<str> "b"
        |> list_push_front<str> "a"
    let ra list_reverse<str> src0;
    let ok0 match list_head<str> ra:
        Option::Some x:
            if str_eq x "c" 1 0
        Option::None:
            0
    let src1 <List<str>>:
        list_nil<str>
        |> list_push_front<str> "c"
        |> list_push_front<str> "b"
        |> list_push_front<str> "a"
    let rb list_reverse<str> src1;
    let ok1 match list_get<str> rb 2:
        Option::Some x:
            if str_eq x "a" 1 0
        Option::None:
            0
    let src2 <List<str>>:
        list_nil<str>
        |> list_push_front<str> "c"
        |> list_push_front<str> "b"
        |> list_push_front<str> "a"
    let rc list_reverse<str> src2;
    let ok2 if is_none<str> list_get<str> rc 3 1 0;
    let s01 <i32> add ok0 ok1;
    add s01 ok2

List: 単方向連結リストの先頭ポインタを隠蔽する構造体

目的:

ノード先頭ポインタ (i32) を公開 API から隠蔽します。

実装(アルゴリズム):

ptr フィールドに先頭ノードアドレスを保持します。

注意(重要):

ptr == 0 は空リストを表します。

計算量:

O(1)

list_nil: 空リストを表す値を返す

目的:

空リスト（null ポインタ）を返します。

実装(アルゴリズム):

定数 0 を返すだけです。

注意(重要):

0 は「空」を表す特別な値です。

計算量:

O(1)

使い方:

TEST

#entry main
#target std
#import "alloc/collections/list" as *
fn main <()*>i32> ():
    if list_is_empty<i32> list_nil<i32> 0 1

list_cons: 先頭に要素を追加して新しいリストを作る

目的:

head を値として持つ新ノードを確保し、tail を next に接続します。

実装(アルゴリズム):

size_of<.T> + 4 の領域を確保し、[value][next] を格納します。

注意(重要):

返り値は新しい先頭ノードのポインタです。

計算量:

O(1)

使い方:

TEST

#entry main
#target std
#import "alloc/collections/list" as *
fn main <()*>i32> ():
    let l list_cons<i32> 5 list_nil<i32>;
    if list_is_empty<i32> l 1 0

list_push_front: 既存リストの先頭に要素を追加する（pipe向け）

目的:

xs |> list_push_front v の形で先頭追加を自然に書けるようにします。

実装(アルゴリズム):

引数順だけを pipe 向けに並べ替えて list_cons を呼びます。

注意(重要):

返り値は新しい先頭ノードのポインタです。

計算量:

O(1)

list_head: 先頭要素を取得する

目的:

空なら None、非空なら先頭の値を Some で返します。

実装(アルゴリズム):

lst が 0 かを判定し、非空なら value を load します。

注意(重要):

空リストでは None を返します。

計算量:

O(1)

使い方:

TEST

#entry main
#target std
#import "alloc/collections/list" as *
#import "core/option" as *
fn main <()*>i32> ():
    let l list_cons<i32> 8 list_nil<i32>;
    match list_head<i32> l:
        Option::Some x:
            if eq x 8 0 1
        Option::None:
            1

list_tail: 末尾以外の部分（次のノード）を取得する

目的:

空なら None、非空なら next ポインタを Some で返します。

実装(アルゴリズム):

lst が 0 かを判定し、非空なら next を load します。

注意(重要):

戻り値の Some は i32 のポインタです。

計算量:

O(1)

使い方:

TEST

#entry main
#target std
#import "alloc/collections/list" as *
#import "core/option" as *
fn main <()*>i32> ():
    let l2 <List<i32>>:
        list_nil<i32>
        |> list_push_front<i32> 2
        |> list_push_front<i32> 1
    match list_tail<i32> l2:
        Option::Some t:
            if eq list_len<i32> t 1 0 1
        Option::None:
            1

list_is_empty: 空リストか判定する

目的:

lst が空なら true を返します。

実装(アルゴリズム):

lst == 0 を判定します。

注意(重要):

空リストは 0 で表します。

計算量:

O(1)

使い方:

TEST

#entry main
#target std
#import "alloc/collections/list" as *
fn main <()*>i32> ():
    if list_is_empty<i32> list_nil<i32> 0 1

list_len: 長さを数える

目的:

リストの要素数を返します。

実装(アルゴリズム):

next をたどりながらカウントを増やします。

注意(重要):

循環リストに対しては無限ループします。

計算量:

O(n)

使い方:

TEST

#entry main
#target std
#import "alloc/collections/list" as *
fn main <()*>i32> ():
    let l3 <List<i32>>:
        list_nil<i32>
        |> list_push_front<i32> 3
        |> list_push_front<i32> 2
        |> list_push_front<i32> 1
    if eq list_len<i32> l3 3 0 1

list_get: 指定位置の要素を取得する

目的:

idx が範囲内なら Some(value)、範囲外なら None を返します。

実装(アルゴリズム):

先頭から idx 回 next をたどり、到達したノードの value を返します。
途中で null に到達したら None を返します。

注意(重要):

idx が負のときは None です。

計算量:

O(n)

使い方:

TEST

#entry main
#target std
#import "alloc/collections/list" as *
#import "core/option" as *
fn main <()*>i32> ():
    let l3 <List<i32>>:
        list_nil<i32>
        |> list_push_front<i32> 3
        |> list_push_front<i32> 2
        |> list_push_front<i32> 1
    match list_get<i32> l3 1:
        Option::Some x:
            if eq x 2 0 1
        Option::None:
            1

list_free: リスト全体を解放する

目的:

連結リストの全ノードを解放します。

実装(アルゴリズム):

next を保存しながら現在ノードを順に dealloc します。

注意(重要):

循環リストには対応していません。

計算量:

O(n)

使い方:

TEST

#entry main
#target std
#import "alloc/collections/list" as *
fn main <()*>i32> ():
    let l0 list_nil<i32>;
    let l1 list_cons<i32> 1 l0;
    list_free<i32> l1;
    0

list_reverse: リストを逆順にする

目的:

逆順の新しいリストを作って返します。

実装(アルゴリズム):

先頭から走査し、list_cons で新しい先頭へ積み直します。

注意(重要):

返り値は新しいリストで、元のノードは再利用しません。

計算量:

O(n)

使い方:

TEST

#entry main
#target std
#import "alloc/collections/list" as *
#import "core/option" as *
fn main <()*>i32> ():
    let l3 <List<i32>>:
        list_nil<i32>
        |> list_push_front<i32> 3
        |> list_push_front<i32> 2
        |> list_push_front<i32> 1
    let r list_reverse<i32> l3;
    match list_head<i32> r:
        Option::Some x:
            if eq x 3 0 1
        Option::None:
            1