Lists Template

Home
Kits
BasicInformKit
Lists Template

Code to support the list of... kind of value constructor.

§1. Block Format. A list is a variable-length array of values all of which have the same kind. (Compare a combination, a fixed-length array of values with possibly different kinds.) The short block for a list is a pointer to the long block. The long block consists of the strong kind ID of the items (not of the list itself!), followed by the number of items, followed by one word for each item.

Constant LIST_ITEM_KOV_F = 0; The kind of the items
Constant LIST_LENGTH_F = 1;   The number of items
Constant LIST_ITEM_BASE = 2;  List items begin at this entry

§2. Creation. Lists are by default created empty but in a block-value with enough capacity to hold 25 items, this being what's left in a 32-word block once all overheads are taken care of: 4 words are consumed by the header, then 2 more by the list metadata entries below.

[ LIST_OF_TY_Create kind_id sb_address
    short_block long_block;
    long_block = CreatePVLongBlockFlexible(kind_id, 27);
    InitialisePVLongBlockField(long_block, LIST_ITEM_KOV_F,
        KindConstructorTerm(kind_id, 0));
    InitialisePVLongBlockField(long_block, LIST_LENGTH_F, 0);

    short_block = CreatePVShortBlock(sb_address, kind_id);
    short_block-->0 = long_block;

    return short_block;
];

§3. Destruction. If the list items are themselves block-values, they must all be freed before the list itself can be freed.

[ LIST_OF_TY_Destroy list no_items i k;
    k = PVField(list, LIST_ITEM_KOV_F);
    if (KindConformsTo_POINTER_VALUE_TY(k)) {
        no_items = PVField(list, LIST_LENGTH_F);
        for (i=0: i<no_items: i++)
            DestroyPV(PVField(list, i+LIST_ITEM_BASE));
    }
];

§4. Copying. Again, if the list contains block-values then they must be duplicated rather than bitwise copied as pointers.

Note that we use the pre-copy stage to remember the kind of value stored in the list. Type-checking will make sure this isn't abused: cases where it's important include copying the empty list into a list of rooms (it should not as a result acquire the kind "list of values"), or copying a list of people into a list of things (which should remain a list of things.)

[ LIST_OF_TY_CopyKind to from;
    WritePVField(to, LIST_ITEM_KOV_F, PVField(from, LIST_ITEM_KOV_F));
];

[ LIST_OF_TY_QuickCopy to from;
    if (PVField(to, LIST_ITEM_KOV_F) ~= PVField(from, LIST_ITEM_KOV_F))
        rfalse;
    rtrue;
];

[ LIST_OF_TY_LongBlockSize list;
    return PVField(list, LIST_LENGTH_F) + LIST_ITEM_BASE;
];

[ LIST_OF_TY_Copy lto lfrom kind recycling  precopied_list_kov no_items i nv bk val splk;
    precopied_list_kov = PVField(lto, LIST_ITEM_KOV_F);
    CopyPVRawData(lto, lfrom, kind, recycling);
    no_items = PVField(lfrom, LIST_LENGTH_F);
    bk = PVField(lfrom, LIST_ITEM_KOV_F);
    if (precopied_list_kov ~= 0 or UNKNOWN_TY)
        WritePVField(lto, LIST_ITEM_KOV_F, precopied_list_kov);
    else WritePVField(lto, LIST_ITEM_KOV_F, bk);
    if (KindConformsTo_POINTER_VALUE_TY(bk)) {
        for (i=0: i<no_items: i++) {
            val = PVField(lfrom, i+LIST_ITEM_BASE);
            if (precopied_list_kov ~= 0 or UNKNOWN_TY)
                nv = CreatePV(precopied_list_kov);
            else
                nv = CreatePV(bk);
            CopyPV(nv, val);
            WritePVField(lto, i+LIST_ITEM_BASE, nv);
        }
    }
];

§5. Comparison. Lists of a given kind of value are always grouped together, in this comparison: but the effect of that is unlikely to be noticed since Inform's type-checker will probably prevent comparisons of lists of differing items in any case. The next criterion is length: a short list precedes a long one. Beyond that, we use the list's own preferred comparison function to judge the items in turn, stopping as soon as a pair of corresponding items differs: thus we sort lists of equal size in lexicographic order.

[ LIST_OF_TY_Compare listleft listright delta no_items i cf;
    delta = PVField(listleft, LIST_LENGTH_F) - PVField(listright, LIST_LENGTH_F);
    if (delta) return delta;
    no_items = PVField(listleft, LIST_LENGTH_F);
    if (no_items == 0) return 0;
    delta = PVField(listleft, LIST_ITEM_KOV_F) - PVField(listright, LIST_ITEM_KOV_F);
    if (delta) return delta;
    cf = LIST_OF_TY_ComparisonFn(listleft);
    if (cf == 0 or UnsignedCompare) {
        for (i=0: i<no_items: i++) {
            delta = PVField(listleft, i+LIST_ITEM_BASE) -
                PVField(listright, i+LIST_ITEM_BASE);
            if (delta) return delta;
        }
    } else {
        for (i=0: i<no_items: i++) {
            delta = cf(PVField(listleft, i+LIST_ITEM_BASE),
                PVField(listright, i+LIST_ITEM_BASE));
            if (delta) return delta;
        }
    }
    return 0;
];

[ LIST_OF_TY_ComparisonFn list;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) return 0;
    return KindComparisonFunction(PVField(list, LIST_ITEM_KOV_F));
];

[ LIST_OF_TY_Distinguish txb1 txb2;
    if (LIST_OF_TY_Compare(txb1, txb2) == 0) rfalse;
    rtrue;
];

§6. Hashing.

[ LIST_OF_TY_Hash list  len kov rv i;
    rv = 0;
    len = PVField(list, LIST_LENGTH_F);
    kov = PVField(list, LIST_ITEM_KOV_F);
    for (i=0: i<len: i++)
        rv = rv * 33 + HashKindValuePair(kov, PVField(list, i+LIST_ITEM_BASE));
    return rv;
];

§7. Printing. Unusually, this function can print the value in one of several formats: 0 for a comma-separated list; 1 for a braced, set-notation list; 2 for a comma-separated list with definite articles, which only makes sense if the list contains objects; 3 for a comma-separated list with indefinite articles. Note that a list in this sense is {\it not} printed using the "ListWriter.i6t" code for elaborate lists of objects, and it doesn't use the "listing contents of..." activity in any circumstances.

[ LIST_OF_TY_Say list format no_items v i bk;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) return;
    no_items = PVField(list, LIST_LENGTH_F);
    bk = KindWeakID(PVField(list, LIST_ITEM_KOV_F));
    if (format == 1) print "{";
    for (i=0:i<no_items:i++) {
        v = PVField(list, i+LIST_ITEM_BASE);
        switch (format) {
            2: print (the) v;
            3: print (a) v;
            default:
                if (bk == LIST_OF_TY) LIST_OF_TY_Say(v, 1);
                else if ((bk == TEXT_TY) && (format == 1)) {
                    print "~"; SayKindValuePair(bk, v); print "~";
                }
                else SayKindValuePair(bk, v);
        }
        if (i<no_items-2) print ", ";
        if (i==no_items-2) {
            if (format == 1) print ", "; else {
                if (BasicInformKit`SERIAL_COMMA_CFGF) {
                    if (no_items ~= 2) print ",";
                }
                LW_Response('C');
            }
        }
    }
    if (format == 1) print "}";
    prior_named_list = no_items; prior_named_list_gender = -1;
];

§8. List From Description. That completes the compulsory services required for this KOV to function: from here on, the remaining routines provide definitions of stored action-related phrases in the Standard Rules.

Given a description D which applies to some objects and not others — say, "lighted rooms adjacent to the Transport Hub" — we can cast this into a list of all objects satisfying D with the following routine. Slightly wastefully of time, we have to iterate through the objects twice in order first to work out the length of list we will need, and then to transcribe them.

[ LIST_OF_TY_Desc list desc kov obj no_items ex len i;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) return false;
    ex = PVFieldCapacity(list);
    len = desc(-3);
    if (len+LIST_ITEM_BASE > ex) {
        if (SetPVFieldCapacity(list, len+LIST_ITEM_BASE) == false)
            return 0;
    }
    if (kov) WritePVField(list, LIST_ITEM_KOV_F, kov);
    else WritePVField(list, LIST_ITEM_KOV_F, OBJECT_TY);
    WritePVField(list, LIST_LENGTH_F, len);
    obj = 0;
    for (i=0: i<len: i++) {
        obj = desc(-2, obj, i);
        print "i = ", i, " and obj = ", obj, "^";
        WritePVField(list, i+LIST_ITEM_BASE, obj);
    }
    return list;
];

§9. Find Item. We test whether a list list includes a value equal to v or not. Equality here is in the sense of the list's comparison function: thus for texts or other lists, say, deep comparisons rather than simple pointer comparisons are performed. In other words, one copy of "Alert" is equal to another.

[ LIST_OF_TY_FindItem list v i no_items cf;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) rfalse;
    cf = LIST_OF_TY_ComparisonFn(list);
    no_items = PVField(list, LIST_LENGTH_F);
    if (cf == 0 or UnsignedCompare) {
        for (i=0: i<no_items: i++)
            if (v == PVField(list, i+LIST_ITEM_BASE)) rtrue;
    } else {
        for (i=0: i<no_items: i++)
            if (cf(v, PVField(list, i+LIST_ITEM_BASE)) == 0) rtrue;
    }
    rfalse;
];

§10. Insert Item. The following routine inserts an item into the list. If this would break the size of the current block-value, then we extend by at least enough room to hold at least another 16 entries.

In the call LIST_OF_TY_InsertItem(list, v, posnflag, posn, nodups), only the first two arguments are compulsory.

(a) If nodups is set, and an item equal to v is already present in the list, we return and do nothing. (nodups means "no duplicates".)
(b) Otherwise, if posnflag is false, we append a new entry v at the back of the given list.
(c) Otherwise, when posnflag is true, posn indicates the insertion position, from 1 (before the current first item) to \(N+1\) (after the last), where \(N\) is the number of items in the list at present.

[ LIST_OF_TY_InsertItem list v posnflag posn nodups i no_items ex nv contents_kind;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) return false;
    if (nodups && (LIST_OF_TY_FindItem(list, v))) return list;
    no_items = PVField(list, LIST_LENGTH_F);
    WritePVField(list, LIST_LENGTH_F, no_items); Forces the list to be mutable
    contents_kind = PVField(list, LIST_ITEM_KOV_F);
    if ((posnflag) && ((posn<1) || (posn > no_items+1))) {
        IssueRTP("AccessedNonExistentListItem",
            "Attempt to use list item which does not exist.", BasicInformKitRTPs);
        print "*** Couldn't add at entry ", posn, " in the list ";
        LIST_OF_TY_Say(list, true);
        print ", which has entries in the range 1 to ", no_items, " ***^";
        rfalse;
    }
    ex = PVFieldCapacity(list);
    if (no_items+LIST_ITEM_BASE+1 > ex) {
        if (SetPVFieldCapacity(list, ex+16) == false) return 0;
    }
    if (KindConformsTo_POINTER_VALUE_TY(contents_kind)) {
        nv = CreatePV(contents_kind);
        CopyPV(nv, v);
        v = nv;
    }
    if (posnflag) {
        posn--;
        for (i=no_items:i>posn:i--) {
            WritePVField(list, i+LIST_ITEM_BASE,
                PVField(list, i-1+LIST_ITEM_BASE));
        }
        WritePVField(list, posn+LIST_ITEM_BASE, v);
    } else {
        WritePVField(list, no_items+LIST_ITEM_BASE, v);
    }
    WritePVField(list, LIST_LENGTH_F, no_items+1);
    return list;
];

§11. Append List. Instead of adjoining a single value, we adjoin an entire second list, which must be of a compatible kind of value (something which Inform's type-checking machinery polices for us). Except that we have a list more rather than a value v to insert, the specification is the same as for LIST_OF_TY_InsertItem.

[ LIST_OF_TY_AppendList list more posnflag posn nodups v i j no_items msize ex nv;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) return false;
    if (WeakKindOfPV(more) ~= LIST_OF_TY) return list;
    no_items = PVField(list, LIST_LENGTH_F);
    WritePVField(list, LIST_LENGTH_F, no_items); Forces the list to be mutable
    if ((posnflag) && ((posn<1) || (posn > no_items+1))) {
        IssueRTP("AccessedNonExistentListItem",
            "Attempt to use list item which does not exist.", BasicInformKitRTPs);
        print "*** Couldn't add at entry ", posn, " in the list ";
        LIST_OF_TY_Say(list, true);
        print ", which has entries in the range 1 to ", no_items, " ***^";
        rfalse;
    }
    msize = PVField(more, LIST_LENGTH_F);
    ex = PVFieldCapacity(list);
    if (no_items+msize+LIST_ITEM_BASE > ex) {
        if (SetPVFieldCapacity(list, no_items+msize+LIST_ITEM_BASE+8) == false)
            return 0;
    }
    if (posnflag) {
        posn--;
        for (i=no_items+msize:i>=posn+msize:i--) {
            WritePVField(list, i+LIST_ITEM_BASE,
                PVField(list, i-msize+LIST_ITEM_BASE));
        }
        WritePVField(list, posn, v);
        for (j=0: j<msize: j++) {
            v = PVField(more, j+LIST_ITEM_BASE);
            if (KindConformsTo_POINTER_VALUE_TY(PVField(list, LIST_ITEM_KOV_F))) {
                nv = CreatePV(PVField(list, LIST_ITEM_KOV_F));
                CopyPV(nv, v);
                v = nv;
            }
            WritePVField(list, posn+j+LIST_ITEM_BASE, v);
        }
    } else {
        for (i=0, j=0: i<msize: i++) {
            v = PVField(more, i+LIST_ITEM_BASE);
            if (KindConformsTo_POINTER_VALUE_TY(PVField(list, LIST_ITEM_KOV_F))) {
                nv = CreatePV(PVField(list, LIST_ITEM_KOV_F));
                CopyPV(nv, v);
                v = nv;
            }
            if ((nodups == 0) || (LIST_OF_TY_FindItem(list, v) == false)) {
                WritePVField(list, no_items+j+LIST_ITEM_BASE, v);
                j++;
            }
        }
    }
    WritePVField(list, LIST_LENGTH_F, no_items+j);
    return list;
];

§12. Remove Value. We remove every instance of the value v from the given list. If the optional flag forgive is set, then we make no complaint if no value of v was present in the first place: otherwise, we issue a run-time problem.

Note that if the list contains block-values then the value must be properly destroyed with DestroyPV before being overwritten as the items shuffle down.

[ LIST_OF_TY_RemoveValue list v forgive i j no_items odsize f cf delendum;
    if ((list==0) || (WeakKindOfPV(list) ~= LIST_OF_TY)) rfalse;
    BlkMakeMutable(list);
    cf = LIST_OF_TY_ComparisonFn(list);
    no_items = PVField(list, LIST_LENGTH_F); odsize = no_items;
    WritePVField(list, LIST_LENGTH_F, no_items);
    for (i=0: i<no_items: i++) {
        delendum = PVField(list, i+LIST_ITEM_BASE);
        if (cf == 0 or UnsignedCompare)
            f = (v == delendum);
        else
            f = (cf(v, delendum) == 0);
        if (f) {
            if (KindConformsTo_POINTER_VALUE_TY(PVField(list, LIST_ITEM_KOV_F)))
                DestroyPV(delendum);
            for (j=i+1: j<no_items: j++)
                WritePVField(list, j-1+LIST_ITEM_BASE,
                    PVField(list, j+LIST_ITEM_BASE));
            no_items--; i--;
            WritePVField(list, LIST_LENGTH_F, no_items);
        }
    }
    if (odsize ~= no_items) rfalse;
    if (forgive) rfalse;
    IssueRTP("AccessedNonExistentListItem",
        "Attempt to use list item which does not exist.", BasicInformKitRTPs);
    print "*** Couldn't remove: the value ";
    SayKindValuePair(PVField(list, LIST_ITEM_KOV_F), v);
    print " was not present in the list ";
    LIST_OF_TY_Say(list, true);
    print " ***^";
];

§13. Remove Item Range. We excise items from to to from the given list, which numbers its items upwards from 1. If the optional flag forgive is set, then we truncate a range overspilling the actual list, and we make no complaint if it turns out that there is then nothing to be done: otherwise, in either event, we issue a run-time problem.

Once again, we destroy any block-values whose pointers will be overwritten as the list shuffles down to fill the void.

[ LIST_OF_TY_RemoveItemRange list from to forgive i d no_items;
    if ((list == 0) || (WeakKindOfPV(list) ~= LIST_OF_TY)) rfalse;
    BlkMakeMutable(list);
    no_items = PVField(list, LIST_LENGTH_F);
    if ((from > to) || (from <= 0) || (to > no_items)) {
        if (forgive) {
            if (from <= 0) from = 1;
            if (to >= no_items) to = no_items;
            if (from > to) return list;
        } else {
            IssueRTP("AccessedNonExistentListItem",
                "Attempt to use list item which does not exist.", BasicInformKitRTPs);
            print "*** Couldn't remove entries ", from, " to ", to, " from the list ";
            LIST_OF_TY_Say(list, true);
            print ", which has entries in the range 1 to ", no_items, " ***^";
            rfalse;
        }
    }
    to--; from--;
    d = to-from+1;
    if (KindConformsTo_POINTER_VALUE_TY(PVField(list, LIST_ITEM_KOV_F)))
        for (i=0: i<d: i++)
            DestroyPV(PVField(list, from+i+LIST_ITEM_BASE));
    for (i=from: i<no_items-d: i++)
        WritePVField(list, i+LIST_ITEM_BASE,
            PVField(list, i+d+LIST_ITEM_BASE));
    WritePVField(list, LIST_LENGTH_F, no_items-d);
    return list;
];

§14. Remove List. We excise all values from the removal list rlist, wherever they occur in list. Inevitably, given that we haven't sorted these lists and can spare neither time nor storage to do so, this is an expensive process with a running time proportional to the product of the two list sizes: we accept that as an overhead because in practice the rlist is almost always small in real-world use.

If the initial lists were disjoint, so that no removals occur, we always forgive the user: the request was not necessarily a foolish one, it only happened in this situation to be unhelpful.

[ LIST_OF_TY_Remove_List list rlist i j k v w no_items odsize rsize cf f;
    if ((list == 0) || (WeakKindOfPV(list) ~= LIST_OF_TY)) rfalse;
    BlkMakeMutable(list);
    no_items = PVField(list, LIST_LENGTH_F); odsize = no_items;
    rsize = PVField(rlist, LIST_LENGTH_F);
    cf = LIST_OF_TY_ComparisonFn(list);
    for (i=0: i<no_items: i++) {
        v = PVField(list, i+LIST_ITEM_BASE);
        for (k=0: k<rsize: k++) {
            w = PVField(rlist, k+LIST_ITEM_BASE);
            if (cf == 0 or UnsignedCompare)
                f = (v == w);
            else
                f = (cf(v, w) == 0);
            if (f) {
                if (KindConformsTo_POINTER_VALUE_TY(PVField(list, LIST_ITEM_KOV_F)))
                    DestroyPV(v);
                for (j=i+1: j<no_items: j++)
                    WritePVField(list, j+LIST_ITEM_BASE-1,
                        PVField(list, j+LIST_ITEM_BASE));
                no_items--; i--;
                WritePVField(list, LIST_LENGTH_F, no_items);
                break;
            }
        }
    }
    rfalse;
];

§15. Get Length.

[ LIST_OF_TY_GetLength list;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) return 0;
    return PVField(list, LIST_LENGTH_F);
];

[ LIST_OF_TY_Empty list;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) rfalse;
    if (PVField(list, LIST_LENGTH_F) == 0) rtrue;
    rfalse;
];

§16. Set Length. This is rather harder: it might lengthen the list, in which case we have to pad out with the default value for the kind of value stored — padding a list of numbers with 0s, a list of texts with copies of the empty text, and so on — creating such block-values as might be needed; or else it might shorten the list, in which case we must cut items, destroying them properly if they were block-values.

LIST_OF_TY_SetLength(list, newsize, this_way_only, truncation_end) alters the length of the given list to newsize. If this_way_only is 1, the list is only allowed to grow, and nothing happens if we have asked to shrink it; if it is \(-1\), the list is only allowed to shrink; if it is 0, the list is allowed either to grow or shrink. In the event that the list does have to shrink, entries must be removed, and we remove from the end if truncation_end is 1, or from the start if it is \(-1\).

[ LIST_OF_TY_SetLength list newsize this_way_only truncation_end no_items ex i dv;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) return 0;
    if (newsize < 0) return IssueRTP("ResizedListToNegativeSize",
            "Attempt to resize list to negative size.", BasicInformKitRTPs);
    BlkMakeMutable(list);
    no_items = PVField(list, LIST_LENGTH_F);
    if (no_items < newsize) {
        if (this_way_only == -1) return list;
        ex = PVFieldCapacity(list);
        if (newsize+LIST_ITEM_BASE > ex) {
            if (SetPVFieldCapacity(list, newsize+LIST_ITEM_BASE) == false)
                return 0;
        }
        dv = KindDefaultValue(PVField(list, LIST_ITEM_KOV_F));
        for (i=no_items: i<newsize: i++)
            WritePVField(list, LIST_ITEM_BASE+i, dv);
        WritePVField(list, LIST_LENGTH_F, newsize);
    }
    if (no_items > newsize) {
        if (this_way_only == 1) return list;
        if (truncation_end == -1) {
            if (KindConformsTo_POINTER_VALUE_TY(PVField(list, LIST_ITEM_KOV_F)))
                for (i=0: i<no_items-newsize: i++)
                    DestroyPV(PVField(list, LIST_ITEM_BASE+i));
            for (i=0: i<newsize: i++)
                WritePVField(list, LIST_ITEM_BASE+i,
                    PVField(list, LIST_ITEM_BASE+no_items-newsize+i));
        } else {
            if (KindConformsTo_POINTER_VALUE_TY(PVField(list, LIST_ITEM_KOV_F)))
                for (i=newsize: i<no_items: i++)
                    DestroyPV(PVField(list, LIST_ITEM_BASE+i));
        }
        WritePVField(list, LIST_LENGTH_F, newsize);
    }
    return list;
];

§17. Get Item.

[ LIST_OF_TY_GetItem list i forgive no_items;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) return false;
    no_items = PVField(list, LIST_LENGTH_F);
    if ((i<=0) || (i>no_items)) {
        if (forgive) return false;
        IssueRTP("AccessedNonExistentListItem",
            "Attempt to use list item which does not exist.", BasicInformKitRTPs);
        print "*** Couldn't read from entry ", i, " of a list which";
        switch (no_items) {
            0: print " is empty ***^";
            1: print " has only one entry, numbered 1 ***^";
            default: print " has entries numbered from 1 to ", no_items, " ***^";
        }
        if (no_items >= 1) i = 1;
        else return false;
    }
    return PVField(list, LIST_ITEM_BASE+i-1);
];

§18. Write Item. The slightly odd name for this function comes about because our usual way to convert an rvalue such as LIST_OF_TY_GetItem(L, 4) is to prefix Write, so that it becomes WriteLIST_OF_TY_GetItem(L, 4).

[ WriteLIST_OF_TY_GetItem list i val no_items;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) return false;
    no_items = PVField(list, LIST_LENGTH_F);
    if ((i<=0) || (i>no_items)) {
        IssueRTP("AccessedNonExistentListItem",
            "Attempt to use list item which does not exist.", BasicInformKitRTPs);
        print "*** Couldn't write to list entry ", i, " of a list which";
        switch (no_items) {
            0: print " is empty ***^";
            1: print " has only one entry, numbered 1 ***^";
            default: print " has entries numbered from 1 to ", no_items, " ***^";
        }
    } else {
        WritePVField(list, LIST_ITEM_BASE+i-1, val);
    }
];

§19. Put Item. Higher-level code should not use Write_LIST_OF_TY_GetItem, because it does not properly keep track of block-value copying: the following should be used instead.

[ LIST_OF_TY_PutItem list i v  no_items nv;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) return false;
    no_items = PVField(list, LIST_LENGTH_F);
    if (KindConformsTo_POINTER_VALUE_TY(PVField(list, LIST_ITEM_KOV_F))) {
        nv = CreatePV(PVField(list, LIST_ITEM_KOV_F));
        CopyPV(nv, v);
        v = nv;
    }
    if ((i<=0) || (i>no_items)) return false;
    WritePVField(list, LIST_ITEM_BASE+i-1, v);
];

§20. Reversing. Reversing a list is, happily, a very efficient operation when the list contains block-values: because the pointers are rearranged but none is duplicated or destroyed, we can for once ignore the fact that they are pointers to block-values and simply move them around like any other data.

[ LIST_OF_TY_Reverse list no_items i v;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) return 0;
    no_items = PVField(list, LIST_LENGTH_F);
    if (no_items < 2) return list;
    for (i=0:i*2<no_items:i++) {
        v = PVField(list, LIST_ITEM_BASE+i);
        WritePVField(list, LIST_ITEM_BASE+i,
            PVField(list, LIST_ITEM_BASE+no_items-1-i));
        WritePVField(list, LIST_ITEM_BASE+no_items-1-i, v);
    }
    return list;
];

§21. Rotation. The same is true of rotation. Here, "forwards" rotation means towards the end of the list, "backwards" means towards the start.

[ LIST_OF_TY_Rotate list backwards  no_items i v;
    if (WeakKindOfPV(list) ~= LIST_OF_TY) return 0;
    no_items = PVField(list, LIST_LENGTH_F);
    if (no_items < 2) return list;
    if (backwards) {
        v = PVField(list, LIST_ITEM_BASE);
        for (i=0:i<no_items-1:i++)
            WritePVField(list, LIST_ITEM_BASE+i,
                PVField(list, LIST_ITEM_BASE+i+1));
        WritePVField(list, no_items-1+LIST_ITEM_BASE, v);
    } else {
        v = PVField(list, no_items-1+LIST_ITEM_BASE);
        for (i=no_items-1:i>0:i--)
            WritePVField(list, LIST_ITEM_BASE+i,
                PVField(list, LIST_ITEM_BASE+i-1));
        WritePVField(list, LIST_ITEM_BASE, v);
    }
    return list;
];

§22. Sorting. And the same, again, is true of sorting: but we do have to take note of block values when it comes to performing comparisons, because we can only compare items in the list by looking at their contents, not the pointers to their contents.

LIST_OF_TY_Sort(list, dir, prop) sorts the given list in ascending order if dir is 1, in descending order if dir is \(-1\), or in random order if dir is 2. The comparison used is the one for the kind of value stored in the list, unless the optional argument prop is supplied, in which case we sort based not on the item values but on their values for the property prop. (This only makes sense if the list contains objects.)

LIST_OF_TY_Sort(list, dir, 0, 0, cf) sorts the given list with the custom comparison function cf, which must behave as any standard comparison function would.

Constant SORT_LIST_RANDOM = 2;

Global LIST_OF_TY_Sort_cf;

[ LIST_OF_TY_Sort list dir prop prop_is_bv cf  i j no_items v;
    BlkMakeMutable(list);
    no_items = PVField(list, LIST_LENGTH_F);
    if (dir == SORT_LIST_RANDOM) {
        if (no_items < 2) return;
        for (i=1:i<no_items:i++) {
            j = random(i+1) - 1;
            v = PVField(list, LIST_ITEM_BASE+i);
            WritePVField(list, LIST_ITEM_BASE+i, PVField(list, LIST_ITEM_BASE+j));
            WritePVField(list, LIST_ITEM_BASE+j, v);
        }
        return;
    }
    SetSortDomain(ListSwapEntries, ListCompareEntries);
    if (cf) {
        LIST_OF_TY_Sort_cf = cf;
    }
    else if (prop) {
        if (prop_is_bv) {
            LIST_OF_TY_Sort_cf = ComparePV;
        }
        else {
            LIST_OF_TY_Sort_cf = 0;
        }
    }
    else {
        LIST_OF_TY_Sort_cf = LIST_OF_TY_ComparisonFn(list);
    }
    SortArray(list, prop, dir, no_items, 0);
];

[ ListSwapEntries list i j v;
    if (i==j) return;
    v = PVField(list, LIST_ITEM_BASE+i-1);
    WritePVField(list, LIST_ITEM_BASE+i-1, PVField(list, LIST_ITEM_BASE+j-1));
    WritePVField(list, LIST_ITEM_BASE+j-1, v);
];

[ ListCompareEntries list col i j d;
    if (i==j) return 0;
    i = PVField(list, LIST_ITEM_BASE+i-1);
    j = PVField(list, LIST_ITEM_BASE+j-1);
    if (I7S_Col) {
        if (i provides I7S_Col) i=i.I7S_Col; else i=0;
        if (j provides I7S_Col) j=j.I7S_Col; else j=0;
    }
    if (LIST_OF_TY_Sort_cf == 0) {
        if (i > j) return 1;
        if (i < j) return -1;
        return 0;
    } else {
        return LIST_OF_TY_Sort_cf(i, j);
    }
];