For Gauche 0.9.5


Next: , Previous: , Up: ライブラリモジュール - SRFI   [Contents][Index]

11.23 srfi-117 - リストを元にしたキュー

Module: srfi-117

リストを元にしたキューのライブラリです。 Gaucheはdata.queueモジュールでキューをサポートしています (スレッドセーフなキューも含まれています。詳しくはキューを参照。) このモジュールは、主としてポータブルなコードのために、 data.queue<queue>の上に実装されています。

このモジュールでいうリストキューは<queue>のインスタンスそのものなので、 make-queueで作ったキューをsrfi-117のAPIに渡したり、 make-list-queueで作ったキューをGaucheのキューAPIに渡すこともできます。

註: このsrfiのAPIには、性能のために、キューが使う内部のペアをそのまま返すことを要求されている ものがあります。これらの内部ペアはキューの操作によって破壊的に変更される可能性があります。 ユーザ側でも変更した場合、その後のキューの動作は保証されません。

Function: make-list-queue lis :optional last

[SRFI-117] リストlisの内容を初期値として持つリストキューを作って返します。 Gaucheでは、リストキューは<queue>のインスタンスです(キュー参照)。

lisの実体は作成されたキューの所有物となります。 呼び出し側は、この関数を呼んだ後でlisを変更してはいけません。 また、作成されたキューの操作によってlisの内容は変更されるでしょう。

省略可能なlast引数は、もし与えられる場合は、lisの最後のペアで なければなりません。この引数が渡された場合、make-list-queueは自分で リストの末尾のペアを見つけるかわりに、呼び出し側を信頼してlastを最後の ペアとして保持します。

Function: list-queue elt …

[SRFI-117] elt …を初期内容とするリストキューを作成して返します。 Gaucheでは、リストキューは<queue>のインスタンスです(キュー参照)。

Function: list-queue-copy queue

[SRFI-117] リストキューqueueのコピーを返します。

Function: list-queue-unfold p f g seed :optional queue

[SRFI-117] リストキューqueueの前に、(unfold p f g seed)で生成される 要素を付け足して、queueを返します。queueが省略された場合は 新たに作成したキューを使います。

(list-queue-unfold (pa$ = 5) ; p
                   (pa$ * 2) ; f
                   (pa$ + 1) ; g
                   0         ; seed
                   (list-queue 'x 'y 'z))
 ⇒ a queue containing (0 2 4 6 8 x y z)
Function: list-queue-unfold-right p f g seed :optional queue

[SRFI-117] queueの後ろに、(unfold-right p f g seed)で生成される 要素を付け足して、queueを返します。queueが省略された場合は 新たに作成したキューを使います。

(list-queue-unfold-right (pa$ = 5) ; p
                         (pa$ * 2) ; f
                         (pa$ + 1) ; g
                         0         ; seed
                         (list-queue 'x 'y 'z))
 ⇒ a queue containing (x y z 8 6 4 2 0)
Function: list-queue? obj

[SRFI-117] queueがリストキューなら#tを、そうでなければ#fを返します。 Gaucheではdata.queueモジュールのqueue?と同じです。

Function: list-queue-empty? queue

[SRFI-117] queueが空なら#tを、そうでなければ#fを返します。 data.queuequeue-empty?と同じです。

Function: list-queue-front queue

[SRFI-117] queueの先頭の要素を返します。queueが空の場合はエラーを報告します。 data.queuequeue-frontと同じです。

Function: list-queue-back queue

[SRFI-117] queueの末尾の要素を返します。queueが空の場合はエラーを報告します。 data.queuequeue-rearと同じです。

Function: list-queue-list queue

[SRFI-117] queueが内部的に保持している要素のリストを返します。 返されたリストは、queueが操作されれば破壊的に変更される可能性があり、 また返されたリストを破壊的に変更した場合はqueueの一貫性が失われます。 この手続きの主な目的は、他のキュー操作を効率よく実装することです。

単にキューの中身にオーバーヘッド無くアクセスしたい場合は、 list-queue-remove-all!が使えないかどうか検討してください。 そちらはキューの中身のリストを直接返すと同時にキュー自体を空にするので、安全です。

Function: list-queue-fist-last queue

queueの内部で要素を保持しているリストの先頭と末尾のペアを返します。 キューが空の場合は、二つの空リストを返します。

この手続きも、list-queue-listと同じく、内部のリストを直接返すため、 返されたリストは、queueが操作されれば破壊的に変更される可能性があり、 また返されたリストを破壊的に変更した場合はqueueの一貫性が失われます。 この手続きの主な目的は、他のキュー操作を効率よく実装することであり、 一般的な用途に使うべきではありません。

Function: list-queue-add-front! queue elt

[SRFI-117] eltqueueの先頭に追加します。 data.queue(queue-push! queue elt)と同じです。

Function: list-queue-add-back! queue elt

[SRFI-117] eltqueueの末尾に追加します。 data.queue(enqueue! queue elt)と同じです。

Function: list-queue-remove-front! queue

[SRFI-117] queueの先頭から要素をひとつ取り除き、その取り除かれた要素を返します。 queueが空ならエラーを報告します。 data.queue(dequeue! queue elt)と同じです。

Function: list-queue-remove-back! queue

[SRFI-117] queueの末尾から要素をひとつ取り除き、その取り除かれた要素を返します。 queueが空ならエラーを報告します。 この手続きは、キューの持つ要素数nに対してO(n)の時間がかかります。 もしこの操作を頻繁に必要とするなら、デック(deque, 両端キュー)を使うことを 検討すべきでしょう。(変更不可な両端キューおよび リングバッファ参照。)

Function: list-queue-remove-all! queue

[SRFI-117] queueを空にして、入っていた全ての要素をリストで返します。 リストはコピーされません。つまりO(1)の操作です。 可能なら、list-queue-listよりはこちらを使う方が安全です。 Gaucheでは、これはdata.queuedeque-all!と同じです。

Function: list-queue-set-list! queue lis :optional last

[SRFI-117] queueを変更して、lisの内容がキューの内容になるようにします。 queueの元の内容は捨てられます。省略可能なlast引数が渡される場合、 それはlisの最後のペアでなければなりません。手続きは呼び出し元を信頼して、 lisをスキャンせずにlastを最後のペアと考えることで O(1)操作を実現しています。

この手続きを呼び出した後では、lisqueueに所有され、破壊的変更を 受けます。この後でlisの内容をあてにしたり変更したりしてはいけません。

Function: list-queue-append queue …

[SRFI-117] 与えられたqueueを全部つないだ要素を持つリストキューを 新たに作成して返します。引数のキューは変更されません。 これは要素の総数nについてO(n)の操作となります。

Function: list-queue-append! queue …

[SRFI-117] 与えられたqueueの要素を全てつないだものを要素とするリストキューを 返します。操作によって、queueの内容は破壊されることがあり、 以降それらのキューを使ってはなりません (Gaucheでは、事故を避けるために、全てのqueueを空にしています)。 結果として返されるキューが、引数のどれともeq?になる必要はない、 ということに注意してください。 これはキューの総数mに対してO(m)の操作です(要素の総数ではなく)。

Function: list-queue-concatenate queues

[SRFI-117] (apply list-queue-append queues).

Function: list-queue-map proc queue

[SRFI-117] procqueueの各要素に適用して得られた結果を要素とする 新たなリストキューを返します。

Function: list-queue-map! proc queue

[SRFI-117] queueの各要素を、それにprocを適用して得られた結果に 置き替えます。

Function: list-queue-for-each proc queue

[SRFI-117] procqueueの各要素に適用します。結果は捨てられます。


Next: , Previous: , Up: ライブラリモジュール - SRFI   [Contents][Index]