liii_array_buffer.tmu

<TMU|<tuple|1.1.0|2025.0.5>>

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

<\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>
  </hide-preamble>

  <chapter|(liii array-buffer)>

  <section|许可证>

  <\goldfish-chunk|goldfish/liii/array-buffer.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.

    ;

    \;
  </goldfish-chunk>

  <\goldfish-chunk|tests/goldfish/liii/array-buffer-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.

    ;

    \;
  </goldfish-chunk>

  <section|接口>

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

    (import (liii lang))

    (export array-buffer)

    (begin

    \;
  </goldfish-chunk>

  <section|测试>

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

    \;

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

    \;
  </goldfish-chunk>

  <section|array-buffer>

  <scm|array-buffer> 是大小可变的数组，支持随机读写，均摊 <math|O<around*|(|1|)>> 时间在末尾插入和删除元素。成员 <scm|size> 表示数组的大小，<scm|capacity> 表示内存中预留的空间。

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (define-case-class array-buffer ((data vector?) (size integer?) (capacity integer?))

    \;
  </goldfish-chunk>

  <subsection|静态方法>

  <paragraph|array-buffer@from-vector>

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (chained-define (@from-vector vec)

    \ \ (let ((len (vector-length vec)))

    \ \ \ \ (array-buffer (copy vec) len len)))

    \;
  </goldfish-chunk>

  <\scm-chunk|tests/goldfish/liii/array-buffer-test.scm|true|true>
    (check (array-buffer :from-vector #(1 2 3) :collect) =\<gtr\> #(1 2 3))

    \;
  </scm-chunk>

  <paragraph|array-buffer@from-list>

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (chained-define (@from-list lst)

    \ \ (let ((len (length lst)))

    \ \ \ \ (array-buffer (copy lst (make-vector len)) len len)))

    \;
  </goldfish-chunk>

  <\scm-chunk|tests/goldfish/liii/array-buffer-test.scm|true|true>
    (check (array-buffer :from-list '(1 2 3) :collect) =\<gtr\> #(1 2 3))

    \;
  </scm-chunk>

  <subsection|内部方法>

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (define (check-bound n)

    \ \ (when (or (not (integer? n)) (\<less\> n 0) (\<gtr\>= n size))

    \ \ \ \ (key-error "array-buffer out of bound")))

    \;
  </goldfish-chunk>

  <subsection|选择器>

  <paragraph|array-buffer%collect>

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (define (%collect) (copy data (make-vector size)))

    \;
  </goldfish-chunk>

  <paragraph|array-buffer%length>

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (define (%length) size)

    \;
  </goldfish-chunk>

  <paragraph|array-buffer%apply>

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (define (%apply n)

    \ \ (check-bound n)

    \ \ (vector-ref data n))

    \;
  </goldfish-chunk>

  <\scm-chunk|tests/goldfish/liii/array-buffer-test.scm|true|true>
    (let ((arr (array-buffer :from-list '(1 2 3))))

    \ \ (check (arr :length) =\<gtr\> 3)

    \ \ (check (arr 0) =\<gtr\> 1)

    \ \ (check (arr 1) =\<gtr\> 2)

    \ \ (check (arr 2) =\<gtr\> 3)

    \ \ (check-catch 'key-error (arr 3)))

    \;
  </scm-chunk>

  <subsection|修改器>

  <paragraph|array-buffer%set!>

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (chained-define (%set! n v)

    \ \ (check-bound n)

    \ \ (vector-set! data n v)

    \ \ (%this))

    \;
  </goldfish-chunk>

  <paragraph|array-buffer%update!>

  同 <scm|%set!>，兼容 Scala。

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (define (%update! . args)

    \ \ (apply %set! args))

    \;
  </goldfish-chunk>

  <\scm-chunk|tests/goldfish/liii/array-buffer-test.scm|true|true>
    (let ((arr (array-buffer :from-list '(1 2 3))))

    \ \ (check (arr :set! 0 4 :collect) =\<gtr\> #(4 2 3))

    \ \ (check (arr :update! 1 5 :collect) =\<gtr\> #(4 5 3)))

    \;
  </scm-chunk>

  <paragraph|array-buffer%extend!>

  将内部存储预留至少大小为 <scm|n> 的空间。

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (chained-define (%extend! n)

    \ \ (when (\<less\> capacity n)

    \ \ \ \ (if (= capacity 0)

    \ \ \ \ \ \ (set! capacity n)

    \ \ \ \ \ \ (let loop ()

    \ \ \ \ \ \ \ \ (when (\<less\> capacity n)

    \ \ \ \ \ \ \ \ \ \ (set! capacity (* 2 capacity))

    \ \ \ \ \ \ \ \ \ \ (loop))))

    \ \ \ \ (set! data (copy data (make-vector capacity) 0 size)))

    \ \ (%this))

    \;
  </goldfish-chunk>

  <paragraph|array-buffer%size-hint!>

  同 <scm|%extend!>，兼容 Scala。

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (define (%size-hint! . args) (apply %extend! args))

    \;
  </goldfish-chunk>

  <\scm-chunk|tests/goldfish/liii/array-buffer-test.scm|true|true>
    (let ((arr (array-buffer :from-list '(1 2 3))))

    \ \ (check (arr :extend! 5 :length) =\<gtr\> 3)

    \ \ (check-true (== (arr :extend! 10)

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (array-buffer :from-list '(1 2 3))))

    \ \ (check (arr :size-hint! 15 :length) =\<gtr\> 3)

    \ \ (check-true (== (arr :size-hint! 20)

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (array-buffer :from-list '(1 2 3)))))

    \;
  </scm-chunk>

  <paragraph|array-buffer%resize!>

  修改数组大小为 <scm|n>，该操作不会影响内部预留的空间。

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (chained-define (%resize! n)

    \ \ (%extend! n)

    \ \ (set! size n)

    \ \ (%this))

    \;
  </goldfish-chunk>

  <paragraph|array-buffer%trim-to-size!>

  修改数组大小为 <scm|n>，该操作可以释放多余的预留空间。

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (chained-define (%trim-to-size! n)

    \ \ (%extend! n)

    \ \ (set! size n)

    \ \ (when (\<gtr\> capacity (* 2 size))

    \ \ \ \ (set! data (copy data (make-vector size)))

    \ \ \ \ (set! capacity size))

    \ \ (%this))

    \;
  </goldfish-chunk>

  <paragraph|array-buffer%add-one!>

  在数组末尾添加一个元素。

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (chained-define (%add-one! x)

    \ \ (%extend! (+ size 1))

    \ \ (vector-set! data size x)

    \ \ (set! size (+ size 1))

    \ \ (%this))

    \;
  </goldfish-chunk>

  <\scm-chunk|tests/goldfish/liii/array-buffer-test.scm|true|true>
    (let ((arr (array-buffer :from-list '(1 2 3))))

    \ \ (check (arr :add-one! 4 :collect) =\<gtr\> #(1 2 3 4))

    \ \ (check (arr :add-one! 5 :length) =\<gtr\> 5)

    \ \ (check-true (== (arr :add-one! 6)

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (array-buffer :from-list '(1 2 3 4 5 6)))))

    \;
  </scm-chunk>

  <paragraph|array-buffer%clear!>

  清除数组，即 <scm|(%resize! 0)>。注意该操作并不会修改内部存储的空间。

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (chained-define (%clear!)

    \ \ (set! size 0)

    \ \ (%this))

    \;
  </goldfish-chunk>

  <paragraph|array-buffer%clear/shrink!>

  清除数组并回收所用空间。

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (chained-define (%clear/shrink!)

    \ \ (set! size 0)

    \ \ (set! capacity 1)

    \ \ (set! data (make-vector 1))

    \ \ (%this))

    \;
  </goldfish-chunk>

  <\scm-chunk|tests/goldfish/liii/array-buffer-test.scm|true|true>
    (let ((arr (array-buffer :from-list '(1 2 3))))

    \ \ (check (arr :clear! :length) =\<gtr\> 0)

    \ \ (check (arr :add-one! 4 :collect) =\<gtr\> #(4))

    \ \ (check-true (== (arr :clear!)

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (array-buffer :from-list '()))))

    \;

    (let ((arr (array-buffer :from-list '(1 2 3))))

    \ \ (check (arr :clear/shrink! :length) =\<gtr\> 0)

    \ \ (check (arr :add-one! 4 :collect) =\<gtr\> #(4))

    \ \ (check-true (== (arr :clear/shrink!)

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (array-buffer :from-list '()))))

    \;
  </scm-chunk>

  <paragraph|array-buffer%insert!>

  在指定位置插入元素。

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (chained-define (%insert! index elem)

    \ \ (%extend! (+ size 1))

    \ \ (set! size (+ size 1))

    \ \ (check-bound index)

    \ \ (let loop ((p (- size 1)))

    \ \ \ \ (when (\<gtr\> p index)

    \ \ \ \ \ \ (vector-set! data p (vector-ref data (- p 1)))

    \ \ \ \ \ \ (loop (- p 1))))

    \ \ (vector-set! data index elem)

    \ \ (%this))

    \;
  </goldfish-chunk>

  <\scm-chunk|tests/goldfish/liii/array-buffer-test.scm|true|true>
    (let ((arr (array-buffer :from-list '(1 2 3))))

    \ \ (check (arr :insert! 0 0 :collect) ==\<gtr\> #(0 1 2 3))

    \ \ (check (arr :insert! 2 5 :collect) ==\<gtr\> #(0 1 5 2 3))

    \ \ (check (arr :insert! 5 6 :length) ==\<gtr\> 6)

    \ \ (check-true (== (arr :insert! 3 4)

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (array-buffer :from-list '(0 1 5 4 2 3 6))))

    \ \ (check-catch 'key-error (arr :insert! 8 9)))

    \;
  </scm-chunk>

  <subsection|谓词>

  <paragraph|array-buffer%equals>

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (typed-define (%equals (that case-class?))

    \ \ (and (that :is-instance-of 'array-buffer)

    \ \ \ \ \ \ \ ((%to-vector) :equals (that :to-vector))))

    \;
  </goldfish-chunk>

  <\goldfish-chunk|tests/goldfish/liii/array-buffer-test.scm|true|true>
    (check-true (== (array-buffer :from-list '(1 2 3))

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (array-buffer :from-list '(1 2) :add-one! 3)))

    (check-true (== (array-buffer :from-list '(1 2 3))

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (array-buffer :from-list '(1 2 3) :extend! 10)))

    \;
  </goldfish-chunk>

  <subsection|高阶函数>

  <subsection|转换器>

  <paragraph|array-buffer%to-vector>

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (define (%to-vector) (rich-vector (copy data (make-vector size))))

    \;
  </goldfish-chunk>

  <paragraph|array-buffer%to-list>

  <\goldfish-chunk|goldfish/liii/array-buffer.scm|true|true>
    (define (%to-list) (rich-list (vector-\<gtr\>list (copy data (make-vector size)))))

    \;
  </goldfish-chunk>

  <subsection|结尾>

  <\scm-chunk|goldfish/liii/array-buffer.scm|true|true>
    ) ; end of array-buffer

    \;
  </scm-chunk>

  综合测试。

  <\goldfish-chunk|tests/goldfish/liii/array-buffer-test.scm|true|true>
    (let ((arb (array-buffer :from-list '(3 1 2 5 4))))

    \ \ (check (arb :collect) =\<gtr\> #(3 1 2 5 4))

    \ \ (check (arb :to-vector) =\<gtr\> (rich-vector #(3 1 2 5 4)))

    \ \ (check (arb :to-list) =\<gtr\> (rich-list '(3 1 2 5 4)))

    \ \ (arb :add-one! 0)

    \ \ (check (arb :collect) =\<gtr\> #(3 1 2 5 4 0))

    \ \ (check (arb :to-vector) =\<gtr\> (rich-vector #(3 1 2 5 4 0)))

    \ \ (check (arb :to-list) =\<gtr\> (rich-list '(3 1 2 5 4 0)))

    \ \ (arb :insert! 0 0)

    \ \ (check (arb :collect) =\<gtr\> #(0 3 1 2 5 4 0))

    \ \ (check (arb :to-vector) =\<gtr\> (rich-vector #(0 3 1 2 5 4 0)))

    \ \ (check (arb :to-list) =\<gtr\> (rich-list '(0 3 1 2 5 4 0)))

    \ \ (check (arb :resize! 4 :to-list) =\<gtr\> (rich-list '(0 3 1 2)))

    \ \ (check (arb :resize! 3 :to-vector) =\<gtr\> (rich-vector #(0 3 1)))

    \ \ (check (arb :insert! 1 2 :to-list) =\<gtr\> (rich-list '(0 2 3 1)))

    \ \ (check (arb :collect) =\<gtr\> #(0 2 3 1))

    \ \ (check (arb 0) =\<gtr\> 0)

    \ \ (check (arb 1) =\<gtr\> 2)

    \ \ (check-catch 'key-error (arb 5)))

    \;
  </goldfish-chunk>

  <section|结尾>

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

    ) ; end of define-library

    \;
  </goldfish-chunk>

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

    \;
  </goldfish-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|preamble|false>
    <associate|save-aux|false>
  </collection>
</initial>