From 8238718217f1457b681ceae518ffbe8804339a2a Mon Sep 17 00:00:00 2001 From: "Arthur A. Gleckler" Date: Thu, 11 Mar 2021 21:04:24 -0800 Subject: Remove . Users should be able to control whether to open each link in a new tab or window. --- srfi-214.html | 26 +++++++++++++------------- 1 file changed, 13 insertions(+), 13 deletions(-) (limited to 'srfi-214.html') diff --git a/srfi-214.html b/srfi-214.html index 40bdb0e..cf09c1c 100644 --- a/srfi-214.html +++ b/srfi-214.html @@ -19,13 +19,13 @@
  • Draft #2 published: 2021-01-13

    • Abstract

    -

    A flexvector, also known as a dynamic array or an arraylist, is a mutable vector-like data structure with an adjustable size. Flexvectors allow fast random access and fast insertion/removal at the end. This SRFI defines a suite of operations on flexvectors, modeled after SRFI 133's vector operations.

    +

    A flexvector, also known as a dynamic array or an arraylist, is a mutable vector-like data structure with an adjustable size. Flexvectors allow fast random access and fast insertion/removal at the end. This SRFI defines a suite of operations on flexvectors, modeled after SRFI 133's vector operations.

    Rationale

    -

    Unlike the default vector datatype of many other languages, Scheme vectors have a fixed length. This makes vectors unusable as mutable stacks or queues, and is the reason that SRFI 133 lacks common collection operations like filter.

    -

    In fact, no Scheme standard defines a mutable datatype that is suitable for this very common purpose, analogous to a Java ArrayList or to the default list data structure in JavaScript or Python. SRFI 117 defines the commonly-used "tconc" mutable queue, but it is a linked list. And SRFI 134 defines a deque datatype, but that datatype is immutable. Neither data structure has the (often useful) properties of being a mutable, contiguous, random-access sequence.

    +

    Unlike the default vector datatype of many other languages, Scheme vectors have a fixed length. This makes vectors unusable as mutable stacks or queues, and is the reason that SRFI 133 lacks common collection operations like filter.

    +

    In fact, no Scheme standard defines a mutable datatype that is suitable for this very common purpose, analogous to a Java ArrayList or to the default list data structure in JavaScript or Python. SRFI 117 defines the commonly-used "tconc" mutable queue, but it is a linked list. And SRFI 134 defines a deque datatype, but that datatype is immutable. Neither data structure has the (often useful) properties of being a mutable, contiguous, random-access sequence.

    This SRFI does not define a comparator or any sorting procedures, in order to ensure that it has no dependencies. These may be defined in future SRFIs.

    Terminology

    -

    What this SRFI calls a flexvector is better known as a dynamic array. This data structure has a wide variety of names in different languages:

    +

    What this SRFI calls a flexvector is better known as a dynamic array. This data structure has a wide variety of names in different languages:

    Scheme literature already uses the terms list (for cons lists), vector (for fixed-length vectors), and array (for fixed-length numeric arrays), so a new term is needed. Because array in Scheme refers to a numeric array, the term dynamic array is not ideal. Dynamic vector is a possibility, but dynamic-vector would be an unwieldy prefix due to its length. The newly-minted term flexvector communicates this data structure's flexible size and its relationship to Scheme vectors, while being only as long as an existing Scheme data type name (bytevector).

    Procedure inclusion and naming

    -

    This SRFI is primarily modeled on SRFI 133. It includes flexvector equivalents of all SRFI 133 procedures, most with the same names and argument order. There are three notable exceptions:

    +

    This SRFI is primarily modeled on SRFI 133. It includes flexvector equivalents of all SRFI 133 procedures, most with the same names and argument order. There are three notable exceptions:

      -
    1. flexvector-unfold mimics the API of SRFI 1's unfold, not SRFI 133's vector-unfold. vector-unfold is limited by the necessity of a fixed vector length, while flexvector-unfold may generate a flexvector of any length, and so the unfold API is more useful.
      2. +
    2. flexvector-unfold mimics the API of SRFI 1's unfold, not SRFI 133's vector-unfold. vector-unfold is limited by the necessity of a fixed vector length, while flexvector-unfold may generate a flexvector of any length, and so the unfold API is more useful.
    3. There is no flexvector equivalent of vector-unfold!, because flexvectors use the list version of unfold, which has no unfold! equivalent with a similar API.
      4. -
    4. The flexvector equivalent of vector= is flexvector=?. It is conventional for Scheme equality predicates to end in =? (e.g., symbol=?, string=?), and most data structure SRFIs follow this convention (see SRFI 113, 125, 146). This SRFI follows established convention, even when it does not match SRFI 133's procedure names.
      5. +
    5. The flexvector equivalent of vector= is flexvector=?. It is conventional for Scheme equality predicates to end in =? (e.g., symbol=?, string=?), and most data structure SRFIs follow this convention (see SRFI 113, 125, 146). This SRFI follows established convention, even when it does not match SRFI 133's procedure names.
    -

    Additionally, this SRFI includes deque-like operations that reference, add to, and remove from both ends of a flexvector. The naming convention for these operations is taken from SRFI 134, which uses the terms front and back. Front refers to the start of the flexvector (index 0), while back refers to the end (index (- (flexvector-length x) 1)).

    +

    Additionally, this SRFI includes deque-like operations that reference, add to, and remove from both ends of a flexvector. The naming convention for these operations is taken from SRFI 134, which uses the terms front and back. Front refers to the start of the flexvector (index 0), while back refers to the end (index (- (flexvector-length x) 1)).

    Specification

    Flexvectors have the same random-access performance guarantees as ordinary vectors. In particular, if a given Scheme implements vectors with contiguous memory locations and O(1) random access and mutation, flexvectors must also have these performance characteristics. Additionally, appending to the back of a flexvector has the same (amortized) performance as setting an existing location in the same flexvector.

    In this section, the following notation is used to specify parameters and examples:

    @@ -395,20 +395,20 @@ zot

    Both start and end are clamped to the range [0, (string-length string)). It is an error if end is less than start.

    flexvector->generator

    (flexvector->generator fv)

    -

    Returns a SRFI 158 generator that emits the elements of the flexvector fv, in order. If fv is mutated before the generator is exhausted, the generator's remaining return values are undefined.

    +

    Returns a SRFI 158 generator that emits the elements of the flexvector fv, in order. If fv is mutated before the generator is exhausted, the generator's remaining return values are undefined.

    generator->flexvector

    (generator->flexvector gen)

    -

    Creates a flexvector containing all elements produced by the SRFI 158 generator gen.

    +

    Creates a flexvector containing all elements produced by the SRFI 158 generator gen.

    Implementation

    -

    A sample implementation is available on GitHub. The sample implementation supports Gauche, Sagittarius, and Chibi, and includes a test suite.

    +

    A sample implementation is available on GitHub. The sample implementation supports Gauche, Sagittarius, and Chibi, and includes a test suite.

    Acknowledgements

    -

    Thanks to the authors of SRFI 133 (John Cowan, and, transitively, Taylor Campbell), on whose work this SRFI is based. Much of the language in this SRFI was copied directly from 133 with only minor changes.

    +

    Thanks to the authors of SRFI 133 (John Cowan, and, transitively, Taylor Campbell), on whose work this SRFI is based. Much of the language in this SRFI was copied directly from 133 with only minor changes.

    © Adam Nelson 2020-2021.

    Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

    -

    srfi-158]: https://srfi.schemers.org/srfi-158/srfi-158.html

    +

    srfi-158]: https://srfi.schemers.org/srfi-158/srfi-158.html

    Editor: Arthur A. Gleckler
    -- cgit 1.4.1