liii_queue.tmu

<TMU|<tuple|1.0.5|1.2.9.8>>

<style|<tuple|generic|chinese|goldfish|literate|reduced-margins|python>>

<\body>
  <\hide-preamble>
    <assign|r7rs|<flag|R7RS|dark cyan>>

    <assign|srfi|<flag|SRFI|dark red>>

    <assign|font|math=Latin Modern Math,cjk=Noto CJK SC,CMU>

    <assign|typehint|<macro|body|<goldfish-lang|<arg|body>>>>
  </hide-preamble>

  <chapter|(liii queue)>

  这个函数库是三鲤自定义的库，参考了C++和Java的队列相关的函数库的接口。目前基于Scheme的列表实现，从队列取出数据的复杂度是<math|O<around*|(|1|)>>，从队列存入数据的复杂度是<math|O<around*|(|n|)>>。

  <section|许可证>

  <\scm-chunk|goldfish/liii/queue.scm|false|true>
    ;

    ; Copyright (C) 2024 The Goldfish Scheme Authors

    ;

    ; Licensed under the Apache License, Version 2.0 (the "License");

    ; you may not use this file except in compliance with the License.

    ; You may obtain a copy of the License at

    ;

    ; http://www.apache.org/licenses/LICENSE-2.0

    ;

    ; Unless required by applicable law or agreed to in writing, software

    ; distributed under the License is distributed on an "AS IS" BASIS, WITHOUT

    ; WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the

    ; License for the specific language governing permissions and limitations

    ; under the License.

    ;

    \;
  </scm-chunk>

  <\scm-chunk|tests/goldfish/liii/queue-test.scm|false|true>
    ;

    ; Copyright (C) 2024 The Goldfish Scheme Authors

    ;

    ; Licensed under the Apache License, Version 2.0 (the "License");

    ; you may not use this file except in compliance with the License.

    ; You may obtain a copy of the License at

    ;

    ; http://www.apache.org/licenses/LICENSE-2.0

    ;

    ; Unless required by applicable law or agreed to in writing, software

    ; distributed under the License is distributed on an "AS IS" BASIS, WITHOUT

    ; WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the

    ; License for the specific language governing permissions and limitations

    ; under the License.

    ;

    \;
  </scm-chunk>

  <section|接口>

  <\scm-chunk|goldfish/liii/queue.scm|true|true>
    (define-library (liii queue)

    (import (liii list)

    \ \ \ \ \ \ \ \ (liii base)

    \ \ \ \ \ \ \ \ (srfi srfi-9)

    \ \ \ \ \ \ \ \ (liii error))

    (export

    \ \ queue

    \ \ queue? queue-empty?

    \ \ queue-size queue-front queue-back

    \ \ queue-pop! queue-push!

    \ \ queue-\<gtr\>list)

    (begin

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
  </scm-chunk>

  <section|测试>

  <\scm-chunk|tests/goldfish/liii/queue-test.scm|true|true>
    (import (liii queue)

    \ \ \ \ \ \ \ \ (liii base)

    \ \ \ \ \ \ \ \ (liii check))

    \;

    (check-set-mode! 'report-failed)

    \;

    (let1 q1 (queue)

    \ \ (check-true (queue-empty? q1))

    \ \ (check (queue-size q1) =\<gtr\> 0)

    \ \ (check-catch 'value-error (queue-pop! q1))

    \;

    \ \ (queue-push! q1 1)

    \ \ (check (queue-size q1) =\<gtr\> 1)

    \ \ (check (queue-front q1) =\<gtr\> 1)

    \ \ (check (queue-back q1) =\<gtr\> 1)

    \ \ (check (queue-pop! q1) =\<gtr\> 1)

    \ \ (check-true (queue-empty? q1))

    )

    \;

    (let1 q2 (queue 1 2 3)

    \ \ (check (queue-size q2) =\<gtr\> 3)

    \ \ (check (queue-front q2) =\<gtr\> 1)

    \ \ (check (queue-back q2) =\<gtr\> 3)

    \ \ (check (queue-pop! q2) =\<gtr\> 1)

    \ \ (check (queue-pop! q2) =\<gtr\> 2)

    \ \ (check (queue-pop! q2) =\<gtr\> 3)

    )

    \;
  </scm-chunk>

  <section|实现>

  <\scm-chunk|goldfish/liii/queue.scm|true|true>
    (define-record-type :queue

    \ \ (make-queue data)

    \ \ queue?

    \ \ (data get-data set-data!))

    \;

    (define (%queue-assert-type q)

    \ \ (when (not (queue? q))

    \ \ \ \ (type-error "Parameter q is not a queue")))

    \;

    (define (%queue-assert-value q)

    \ \ (when (queue-empty? q)

    \ \ \ \ (value-error "q must be non-empty")))

    \;
  </scm-chunk>

  <paragraph|queue><index|queue>

  第一个参数是队列的头部，最后一个参数是队列的尾部。

  <\scm-chunk|goldfish/liii/queue.scm|true|true>
    (define (queue . l)

    \ \ (if (null? l)

    \ \ \ \ \ \ (make-queue '())

    \ \ \ \ \ \ (make-queue l)))

    \;
  </scm-chunk>

  <paragraph|queue-empty?><index|queue-empty?><scm|(queue) =\<gtr\> bool>

  <\scm-chunk|goldfish/liii/queue.scm|true|true>
    (define (queue-empty? q)

    \ \ (%queue-assert-type q)

    \ \ (null? (get-data q)))

    \;
  </scm-chunk>

  <paragraph|queue-size><index|queue-size><scm|(queue) =\<gtr\> int>

  <\scm-chunk|goldfish/liii/queue.scm|true|true>
    (define (queue-size q)

    \ \ (%queue-assert-type q)

    \ \ (length (get-data q)))

    \;
  </scm-chunk>

  <paragraph|queue-front><index|queue-front><scm|(queue) =\<gtr\> x>

  <\scm-chunk|goldfish/liii/queue.scm|true|true>
    (define (queue-front q)

    \ \ (%queue-assert-type q)

    \ \ (%queue-assert-value q)

    \ \ (first (get-data q)))

    \;
  </scm-chunk>

  <paragraph|queue-back><index|queue-back><scm|(queue) =\<gtr\> x>

  <\scm-chunk|goldfish/liii/queue.scm|true|true>
    (define (queue-back q)

    \ \ (%queue-assert-type q)

    \ \ (%queue-assert-value q)

    \ \ (last (get-data q)))

    \;
  </scm-chunk>

  <paragraph|queue-push!><index|queue-push!><scm|(queue x) =\<gtr\> queue>

  <\scm-chunk|goldfish/liii/queue.scm|true|true>
    (define (queue-push! q x)

    \ \ (%queue-assert-type q)

    \ \ (let1 data (get-data q)

    \ \ \ \ (set-data! q (append data (list x)))))

    \;
  </scm-chunk>

  <paragraph|queue-pop!><index|queue-pop!><scm|(queue) =\<gtr\> x>

  <\scm-chunk|goldfish/liii/queue.scm|true|true>
    (define (queue-pop! q)

    \ \ (%queue-assert-type q)

    \ \ (%queue-assert-value q)

    \ \ (let1 data (get-data q)

    \ \ \ \ (set-data! q (cdr data))

    \ \ \ \ (car data)))

    \;
  </scm-chunk>

  <paragraph|queue-\<gtr\>list><index|queue-\<gtr\>list><scm|(queue) =\<gtr\> list>

  <\scm-chunk|goldfish/liii/queue.scm|true|true>
    (define (queue-\<gtr\>list q)

    \ \ (get-data q))

    \;
  </scm-chunk>

  <section|结尾>

  <\scm-chunk|goldfish/liii/queue.scm|true|false>
    ) ; end of begin

    ) ; end of library

    \;
  </scm-chunk>

  <\scm-chunk|tests/goldfish/liii/queue-test.scm|true|false>
    (check-report)

    \;
  </scm-chunk>

  \;
</body>

<\initial>
  <\collection>
    <associate|font-base-size|12>
    <associate|page-height|auto>
    <associate|page-orientation|landscape>
    <associate|page-screen-margin|false>
    <associate|page-type|a4>
    <associate|page-width|auto>
    <associate|save-aux|false>
  </collection>
</initial>