NEPLg2 Standard Library

stack: 後入先出あといれさきだし（LIFO）スタックを扱うライブラリ

目的もくてき:

push / pop / peek / len など、スタック操作の基本 API を提供します。
parser や探索処理で使いやすい軽量なスタック実装を提供します。

実装じっそう:

スタック本体は Vec<.T> で表し、内部でヘッダ [len, cap, data_ptr] を保持します。
容量不足時は 2 倍拡張して realloc します。

注意ちゅうい:

stack_push / stack_clear は更新後の Stack<.T> を返します。
stack_pop は Option<.T> を返します。
stack_peek は値のみを返します。
stack_free 後のスタック値は再利用できません。

計算量けいさんりょう:

stack_len/stack_is_empty/stack_peek/stack_pop は O(1)。
stack_push はならし O(1)、拡張発生時のみ O(n)。

追加の使い方:

TEST

#entry main
#target std
#import "alloc/collections/stack" as *
#import "alloc/diag/error" as *
#import "core/option" as *
#import "core/field" as *
#import "core/result" as *
fn main <()*>i32> ():
    let st0 <Stack<i32>>:
        <Stack<i32>> new
        |> uwok
        |> push 10
        |> uwok
        |> push 20
        |> uwok
    let ok0 if eq len st0 2 1 0;
    let st1 <Stack<i32>>:
        <Stack<i32>> new
        |> uwok
        |> push 10
        |> uwok
        |> push 20
        |> uwok
    let ok1 match peek st1:
        Option::Some x:
            if eq x 20 1 0
        Option::None:
            0
    let st2 <Stack<i32>>:
        <Stack<i32>> new
        |> uwok
        |> push 10
        |> uwok
        |> push 20
        |> uwok
    let p pop st2;
    let ok2 match p:
        Option::Some x:
            if eq x 20 1 0
        Option::None:
            0
    let s01 <i32> add ok0 ok1;
    add s01 ok2

使い方:

TEST

#entry main
#target std
#import "alloc/collections/stack" as *
#import "alloc/string" as s
#import "alloc/diag/error" as *
#import "core/option" as *
#import "core/field" as *
#import "core/result" as *
fn main <()*>i32> ():
    let st <Stack<str>>:
        <Stack<str>> new
        |> uwok
        |> push "a"
        |> uwok
        |> push "b"
        |> uwok
    let p pop st;
    let ok0 match p:
        Option::Some x:
            if s::str_eq x "b" 1 0
        Option::None:
            0
    ok0

stack_header_len_ptr: ヘッダの length 欄らんを指さす

目的もくてき

[len, cap, data_ptr] 形式けいしきのヘッダ領域りょういきから length 欄らんを MemPtr<i32> として得えます。

実装じっそう

ヘッダ先頭せんとうの 4 byte を i32 欄らんとして解釈かいしゃくします。

注意ちゅうい

公開こうかい API ではなく、Stack 内部ないぶの補助ほじょです。

計算量けいさんりょう

O(1)

stack_header_cap_ptr: ヘッダの capacity 欄らんを指さす

目的もくてき

ヘッダ中ちゅうの capacity 欄らんを MemPtr<i32> として得えます。

実装じっそう

ヘッダ先頭せんとうから 4 byte 進すすめた位置いちを i32 欄らんとして扱あつかいます。

注意ちゅうい

公開こうかい API ではなく、Stack 内部ないぶの補助ほじょです。

計算量けいさんりょう

O(1)

stack_header_data_ptr_ptr: ヘッダの data pointer 欄らんを指さす

目的もくてき

データ領域りょういきの raw address を保持ほじする欄らんを MemPtr<i32> として得えます。

実装じっそう

ヘッダ先頭せんとうから 8 byte 進すすめた位置いちを i32 欄らんとして扱あつかいます。

注意ちゅうい

公開こうかい API ではなく、Stack 内部ないぶの補助ほじょです。

計算量けいさんりょう

O(1)

stack_len_raw: 内部ないぶで length を読よむ

目的もくてき

Stack の length 欄らんを i32 として読よみます。

実装じっそう

ヘッダの length 欄らんを raw load_i32 で参照さんしょうします。

注意ちゅうい

公開こうかい API ではなく、Stack 内部ないぶの補助ほじょです。

計算量けいさんりょう

O(1)

stack_cap_raw: 内部ないぶで capacity を読よむ

目的もくてき

Stack の capacity 欄らんを i32 として読よみます。

実装じっそう

ヘッダの capacity 欄らんを raw load_i32 で参照さんしょうします。

注意ちゅうい

公開こうかい API ではなく、Stack 内部ないぶの補助ほじょです。

計算量けいさんりょう

O(1)

stack_data_ptr: 内部ないぶでデータ先頭せんとうを得える

目的もくてき

Stack の要素ようそ領域りょういき先頭せんとうを MemPtr<.T> として返かえします。

実装じっそう

ヘッダに保持ほじした raw address を読よみ、MemPtr<.T> で包つつみます。

注意ちゅうい

公開こうかい API ではなく、Stack 内部ないぶの補助ほじょです。

計算量けいさんりょう

O(1)

stack_new: 空のスタックを作る

目的もくてき

既定きてい容量ようりょうの空からスタックを作成さくせいし、Stack<.T> として返かえします。

実装じっそう

12 byte のヘッダ領域りょういきと、既定きてい容量ようりょうぶんの要素ようそ領域りょういきを別々べつべつに確保かくほします。
ヘッダには [len, cap, data_ptr] を保存ほぞんし、Stack<.T> はそのヘッダ先頭せんとうを保持ほじします。

注意ちゅうい

失敗しっぱいすると Result::Err Diag を返かえします。
返かえる Stack<.T> は内部ないぶヘッダの所有権しょゆうけんを持もつので、不要ふようになったら stack_free で解放かいほうします。

計算量けいさんりょう

時間じかん計算量けいさんりょうは O(1)、追加ついかの空間くうかん計算量けいさんりょうも O(1) です。

使い方:

TEST

#entry main
#target std
#import "alloc/collections/stack" as *
#import "alloc/diag/error" as *
#import "core/result" as *
fn main <()*>i32> ():
    let st <Stack<i32>>:
        stack_new<i32>
        |> uwok
    if stack_is_empty<i32> st 0 1

stack_push: 末尾に要素を積む

目的もくてき

item を末尾まつびに積つみ、更新後こうしんごのスタックを返かえします。

実装じっそう

容量ようりょうが足たりる場合ばあいは末尾まつびに直接ちょくせつ書かき込こみます。
容量ようりょう不足ぶそくなら 2 倍ばいに拡張かくちょうし、realloc_ptr でデータ領域りょういきを移動いどうしてから追加ついかします。

注意ちゅうい

更新後こうしんごの Stack<.T> を返かえすので、呼よび出だし側がわで束縛そくばくし直なおす必要ひつようがあります。
拡張かくちょうが発生はっせいした場合ばあい、内部ないぶデータ領域りょういきの番地ばんちは変かわりえます。

計算量けいさんりょう

償却しょうきゃく時間じかん計算量けいさんりょうは O(1)、拡張かくちょう発生時はっせいじの最悪さいあく時間じかん計算量けいさんりょうは O(n) です。

使い方:

TEST

#entry main
#target std
#import "alloc/collections/stack" as *
#import "alloc/diag/error" as *
#import "core/result" as *
fn main <()*>i32> ():
    let mut st <Stack<i32>>:
        stack_new<i32>
        |> uwok
    set st:
        stack_push<i32> st 10
        |> uwok
    if eq stack_len<i32> st 1 0 1

stack_pop: 末尾要素を取り出す

目的もくてき

末尾まつび要素ようそを取とり出だし、存在そんざいすれば Option::Some として返かえします。

実装じっそう

len == 0 なら Option::None を返かえします。
要素ようそがある場合ばあいは最後さいごの添字そえじを計算けいさんし、load 後に length を 1 減へらします。

注意ちゅうい

返かえり値あたいは Option<.T> です。
空からスタックを異常いじょうにせず、None で表あらわします。

計算量けいさんりょう

時間じかん計算量けいさんりょうは O(1) です。

使い方:

TEST

#entry main
#target std
#import "alloc/collections/stack" as *
#import "alloc/diag/error" as *
#import "core/option" as *
#import "core/result" as *
fn main <()*>i32> ():
    let st <Stack<i32>>:
        stack_new<i32>
        |> uwok
        |> stack_push<i32> 10
        |> uwok
    let p stack_pop<i32> st;
    match p:
        Option::Some x:
            if eq x 10 0 1
        Option::None:
            1

stack_peek: 末尾要素を覗く

目的もくてき

末尾まつび要素ようそを削除さくじょせずに参照さんしょうしたいときに使つかいます。

実装じっそう

stack_pop と同様どうように最後さいごの添字そえじを求もとめますが、length は更新こうしんしません。

注意ちゅうい

返かえり値あたいは Option<.T> です。
空からスタックでは None を返かえします。

計算量けいさんりょう

時間じかん計算量けいさんりょうは O(1) です。

使い方:

TEST

#entry main
#target std
#import "alloc/collections/stack" as *
#import "alloc/diag/error" as *
#import "core/option" as *
#import "core/result" as *
fn main <()*>i32> ():
    let st <Stack<i32>>:
        stack_new<i32>
        |> uwok
        |> stack_push<i32> 20
        |> uwok
    match stack_peek<i32> st:
        Option::Some x:
            if eq x 20 0 1
        Option::None:
            1

stack_len: 長さを返す

目的もくてき

現在げんざいの要素数ようそすうを返かえします。

実装じっそう

ヘッダ先頭せんとうの length 欄らんを読よむだけです。

注意ちゅうい

変更へんこうを伴ともなわない読よみ取とり API です。

計算量けいさんりょう

時間じかん計算量けいさんりょうは O(1) です。

使い方:

TEST

#entry main
#target std
#import "alloc/collections/stack" as *
#import "alloc/diag/error" as *
#import "core/result" as *
fn main <()*>i32> ():
    let mut st <Stack<i32>> uwok stack_new<i32>;
    set st uwok stack_push<i32> st 1;
    set st uwok stack_push<i32> st 2;
    if eq stack_len<i32> st 2 0 1

stack_is_empty: 空か判定する

目的もくてき

スタックが空からかどうかを bool で返かえします。

実装じっそう

stack_len で要素数ようそすうを得えて 0 と比較ひかくします。

注意ちゅうい

変更へんこうを伴ともなわない読よみ取とり API です。

計算量けいさんりょう

時間じかん計算量けいさんりょうは O(1) です。

使い方:

TEST

#entry main
#target std
#import "alloc/collections/stack" as *
#import "alloc/diag/error" as *
#import "core/result" as *
fn main <()*>i32> ():
    let st <Stack<i32>> uwok stack_new<i32>;
    if stack_is_empty<i32> st 0 1

stack_clear: すべての要素を削除する

目的もくてき

要素数ようそすうを 0 に戻もどし、スタックを空からにします。

実装じっそう

ヘッダの length 欄らんだけを書き換かえます。

注意ちゅうい

確保かくほずみの容量ようりょうは維持いじされ、メモリは解放かいほうされません。
更新後こうしんごの Stack<.T> を返かえすので、呼よび出だし側がわで束縛そくばくし直なおします。

計算量けいさんりょう

時間じかん計算量けいさんりょうは O(1) です。

使い方:

TEST

#entry main
#target std
#import "alloc/collections/stack" as *
#import "alloc/diag/error" as *
#import "core/result" as *
fn main <()*>i32> ():
    let mut st <Stack<i32>> uwok stack_new<i32>;
    set st uwok stack_push<i32> st 9;
    set st stack_clear<i32> st;
    if stack_is_empty<i32> st 0 1

stack_free: メモリを解放する

目的もくてき

Stack<.T> が所有しょゆうするデータ領域りょういきとヘッダ領域りょういきを解放かいほうします。

実装じっそう

capacity からデータ領域りょういきの byte 数すうを計算けいさんして dealloc_ptr<.T> を呼よび、続つづけてヘッダ 12 byte も解放かいほうします。

注意ちゅうい

解放後かいほうごに stk を再利用さいりようしてはいけません。
Stack<.T> の所有権しょゆうけんを消費しょうひする終端しゅうたん操作として扱あつかいます。

計算量けいさんりょう

時間じかん計算量けいさんりょうは O(1) です。

使い方:

TEST

#entry main
#target std
#import "alloc/collections/stack" as *
#import "alloc/diag/error" as *
#import "core/result" as *
fn main <()*>i32> ():
    let st <Stack<i32>> uwok stack_new<i32>;
    stack_free<i32> st;
    0

new: stack_new の短縮名
push: stack_push の短縮名
pop: stack_pop の短縮名
peek: stack_peek の短縮名
len: stack_len の短縮名
is_empty: stack_is_empty の短縮名
clear: stack_clear の短縮名
free: stack_free の短縮名