VList

From Rosetta Code
VList is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Data Structure
This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.
This page uses content from Wikipedia. The original article was at VList. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

In computer science, the VList is a persistent data structure that combines the fast indexing of arrays with the easy extension of cons-based (or singly-linked) linked lists.

Like arrays, VLists have constant-time lookup on average and are highly compact, requiring only O(log n) storage for pointers, allowing them to take advantage of locality of reference. Like singly-linked or cons-based lists, they are persistent, and elements can be added to or removed from the front in constant time. Length can also be found in O(log n) time.

The primary operations of a VList are:

  • Locate the kth element (O(1) average, O(log n) worst-case)
  • Add an element to the front of the VList (O(1) average, with an occasional allocation)
  • Obtain a new array beginning at the second element of an old array (O(1))
  • Compute the length of the list (O(log n))
Task

The task is to demonstrate creation of a VList and how to perform the primary operations.

Applesoft BASIC

 0  DEF  FN CDR(X) = V(X):Q$ =  CHR$ (34)
 1  FOR A = 6 TO 1 STEP  - 1:A$ =  STR$ (A): PRINT "CONS "A$": ";: GOSUB 10: GOSUB 50: NEXT A
 2  GOSUB 30: PRINT "LENGTH: "L
 3  PRINT "CDR: ";:V =  FN CDR(V): GOSUB 50
 4  GOSUB 30: PRINT "LENGTH: "L
 5 I = 3: PRINT "ITEM "I": ";: GOSUB 20: GOSUB 90:I = 8: PRINT "ITEM "I": ";: GOSUB 20: GOSUB 90
 6  END 

REM CONS given A$ return V
 10 N = N + 1:V(N) = V:V$(N) = A$:V = N: RETURN 

REM GET ITEM given I return A
 20  FOR N = 1 TO I:A = V:V = V(V): NEXT N: PRINT  MID$ ("",1,0 ^ V((A = 0) * 32767));: RETURN

REM GET LENGTH OF LIST given V return L
 30 A = V: FOR L = 1 TO 1E9: IF V(A) THEN A = V(A): NEXT L
 40  RETURN

REM PRINT STRUCTURE given V
 50 C$ = "": FOR P = V TO 0 STEP 0: IF V THEN  PRINT C$;: GOSUB 70:C$ = ", ":P = V(P): NEXT P
 60  PRINT : RETURN 

REM PRINT ELEMENT given P
 70  IF P THEN  PRINT Q$V$(P)Q$;: RETURN 
 80  PRINT "NULL";: RETURN 

REM PRINT ELEMENT WITH NEWLINE given A
 90 P = A: GOSUB 70: PRINT : RETURN
Output:
CONS 6: "6"
CONS 5: "5", "6"
CONS 4: "4", "5", "6"
CONS 3: "3", "4", "5", "6"
CONS 2: "2", "3", "4", "5", "6"
CONS 1: "1", "2", "3", "4", "5", "6"
LENGTH: 6
CDR: "2", "3", "4", "5", "6"
LENGTH: 5
ITEM 3: "4"
ITEM 8: 
?BAD SUBSCRIPT ERROR IN 20

C

#include <stdio.h>
#include <stdlib.h>

typedef struct sublist{
	struct sublist* next;
	int *buf;
} sublist_t;

sublist_t* sublist_new(size_t s)
{
	sublist_t* sub = malloc(sizeof(sublist_t) + sizeof(int) * s);
	sub->buf = (int*)(sub + 1);
	sub->next = 0;
	return sub;
}

typedef struct vlist_t {
	sublist_t* head;
	size_t last_size, ofs;
} vlist_t, *vlist;

vlist v_new()
{
	vlist v = malloc(sizeof(vlist_t));
	v->head = sublist_new(1);
	v->last_size = 1;
	v->ofs = 0;
	return v;
}

void v_del(vlist v)
{
	sublist_t *s;
	while (v->head) {
		s = v->head->next;
		free(v->head);
		v->head = s;
	}
	free(v);
}

inline size_t v_size(vlist v)
{
	return v->last_size * 2 - v->ofs - 2;
}

int* v_addr(vlist v, size_t idx)
{
	sublist_t *s = v->head;
	size_t top = v->last_size, i = idx + v->ofs;

	if (i + 2 >= (top << 1)) {
		fprintf(stderr, "!: idx %d out of range\n", (int)idx);
		abort();
	}
	while (s && i >= top) {
		s = s->next, i ^= top;
		top >>= 1;
	}
	return s->buf + i;
}

inline int v_elem(vlist v, size_t idx)
{
	return *v_addr(v, idx);
}

int* v_unshift(vlist v, int x)
{
	sublist_t* s;
	int *p;

	if (!v->ofs) {
		if (!(s = sublist_new(v->last_size << 1))) {
			fprintf(stderr, "?: alloc failure\n");
			return 0;
		}
		v->ofs = (v->last_size <<= 1);
		s->next = v->head;
		v->head = s;
	}
	*(p = v->head->buf + --v->ofs) = x;
	return p;
}

int v_shift(vlist v)
{
	sublist_t* s;
	int x;

	if (v->last_size == 1 && v->ofs == 1) {
		fprintf(stderr, "!: empty list\n");
		abort();
	}
	x = v->head->buf[v->ofs++];

	if (v->ofs == v->last_size) {
		v->ofs = 0;
		if (v->last_size > 1) {
			s = v->head, v->head = s->next;
			v->last_size >>= 1;
			free(s);
		}
	}
	return x;
}

int main()
{
	int i;

	vlist v = v_new();
	for (i = 0; i < 10; i++) v_unshift(v, i);

	printf("size: %d\n", v_size(v));
	for (i = 0; i < 10; i++) printf("v[%d] = %d\n", i, v_elem(v, i));
	for (i = 0; i < 10; i++) printf("shift: %d\n", v_shift(v));

	/* v_shift(v); */ /* <- boom */

	v_del(v);
	return 0;
}

C++

Translation of: Go
#include <iostream>
#include <vector>
#include <forward_list>
#include <cassert>
#include <memory>

template<typename T>
class VList {
public:
    VList() : datas(), offset(0) {}
private:
    std::forward_list<std::shared_ptr<std::vector<T>>> datas;
    int offset;
public:

    // modify structure instead of returning a new one like the pure functional way does
    void cons(const T& a) {
        if(datas.empty()){
            std::shared_ptr<std::vector<T>> base = std::shared_ptr<std::vector<T>>(new std::vector<T>(1)) ;
            (*base)[0] = a;
            datas.emplace_front(base);
            offset = 0;
            return;
        }
        if(offset == 0){
            datas.front()->shrink_to_fit();
            const int new_capacity = (int) datas.front()->capacity() * 2;
            const int new_offset = new_capacity - 1;
            std::shared_ptr<std::vector<T>> base = std::shared_ptr<std::vector<T>>(new std::vector<T>(new_capacity)) ;
            (*base)[new_offset] = a;
            datas.emplace_front(base);
            offset = new_offset;
            return ;
        }
        --offset;
        (* datas.front())[offset] = a;
    }
    
    // lisp like cdr to keep previous version
    VList* cdr() {
        if (datas.empty()) {
            // cdr of empty list is an empty list
            return this;
        }
        VList* new_vlist = new VList();
        new_vlist->datas = this->datas;
        new_vlist->offset = offset;
        new_vlist->offset++;
        if(new_vlist->offset < new_vlist->datas.front()->capacity()){
            return new_vlist;
        }
        new_vlist->offset = 0;
        new_vlist->datas.front().reset();
        new_vlist->datas.pop_front();
        return new_vlist;
    }

    // compute the length of the list.  (It's O(1).)
    int length() {
        if (datas.empty()) {
            return 0;
        }
        return (int)datas.front()->capacity()*2 - this->offset - 1;
    }

    bool index(int i, T& out) {
        bool isValid = false;
        if (i >= 0) {
            i += this->offset;
            for(auto data : datas) {
                if (i < data->size()) {
                    out = (* data)[i];
                    isValid = true;
                    break;
                }
                i -= data->size();
            }
        }
        return isValid;
    }
    
    void printList() {
        if (datas.empty()) {
            std::cout << "[]" << std::endl;
            return;
        }
        std::vector<T>* first = datas.front().get();
        assert(NULL != first);
        std::cout << "[";
        for (int i=offset; i<first->size(); i++) {
            std::cout << " " << (* first)[i];
        }
        for(auto data : datas) {
            if(data.get() == datas.front().get())
                continue;
            for (int i=0; i<data->size(); i++) {
                std::cout << " " << (* data)[i];
            }
        }
        std::cout << " ]" << std::endl;
    }
    
    // One more method for demonstration purposes
    void printStructure() {
        std::cout << "offset:" << this->offset << std::endl;
        if (datas.empty()) {
            std::cout << "[]" << std::endl;
            return ;
        }
        std::vector<T>* first = datas.front().get();
        assert(NULL != first);
        std::cout << "[";
        for (int i=offset; i<first->size(); i++) {
            std::cout << " " << (* first)[i];
        }
        std::cout << " ]" << std::endl;
        for(auto data : datas) {
            if(data.get() == datas.front().get())
                continue;
            std::cout << "[";
            for (int i=0; i<data->size(); i++) {
                std::cout << " " << (* data)[i];
            }
            std::cout << " ]" << std::endl;
        }
        std::cout << std::endl;
    }
};

int main(int argc, const char * argv[]) {

    std::unique_ptr<VList<char>> vlist = std::unique_ptr<VList<char>>(new VList<char>());
    
    std::cout << "zero value for type.  empty vList:";
    vlist->printList();
    vlist->printStructure();

    std::cout << "demonstrate cons. 6 elements added:";
    for (char a = '6'; a >= '1'; a--) {
        vlist->cons(a);
    }
    vlist->printList();
    vlist->printStructure();

    std::cout << "demonstrate cdr. 1 element removed:";
    vlist = std::unique_ptr<VList<char>>(vlist->cdr());
    vlist->printList();
    vlist->printStructure();    
    
    std::cout << "demonstrate length. length =" << vlist->length() << std::endl;
    
    char out;
    bool isValid = vlist->index(3, out);
    if(isValid)
        std::cout << "demonstrate element access. v[3] =" << out << std::endl;
    
    std::cout << "show cdr releasing segment. 2 elements removed:";    
    vlist = std::unique_ptr<VList<char>>(vlist->cdr()->cdr());
    vlist->printList();
    vlist->printStructure();
    
    return 0;
}
Output:
zero value for type.  empty vList:[]
offset:0
[]
demonstrate cons. 6 elements added:[ 1 2 3 4 5 6 ]
offset:1
[ 1 2 3 ]
[ 4 5 ]
[ 6 ]

demonstrate cdr. 1 element removed:[ 2 3 4 5 6 ]
offset:2
[ 2 3 ]
[ 4 5 ]
[ 6 ]

demonstrate length. length =5
demonstrate element access. v[3] =5
show cdr releasing segment. 2 elements removed:[ 4 5 6 ]
offset:0
[ 4 5 ]
[ 6 ]

Component Pascal

BlackBox Component Builder

Two modules are provided - one for implementing and one for using VLists

MODULE RosettaVLists;
(** In 2002, Phil Bagwell published "Fast Functional Lists" which introduced VLists as alternatives to Functional Programming's
ubiquitous linked lists and described Visp (a dialect of  Common Lisp) using VLists, but including a "foldr" function,
optimized to use VLists.  VLists have the same properties as immutable functional linked lists (including full persistence); but,
unlike a linked list, with O(1) random access time. The VLists implemented here is based on section 2.1 of that article but has been
modified to retain the safety features of Component Pascal.

VLists are referenced through 2 fields: "base" and "offset".  A third field "length" reduces the  time to determine its length to O(1).

Methods provided for manipulating VLists are named after their corresponding Visp functions, but follow Component Pascal's case conventions. **)

    TYPE
        Element* = CHAR; (** "Element" could be defined as a generic type.
        To demonstrate strings, it is defined as a character. **)

        Accum* = ABSTRACT RECORD END; (** For use in "FoldR" **)

        Out* = ABSTRACT RECORD END; (** For use in "Exp" **)

        Link = RECORD base: Base; offset: INTEGER END;

        Base = POINTER TO RECORD
            link: Link;
            lastUsed: INTEGER;
            block: POINTER TO ARRAY OF Element
        END;

        List* = RECORD
            link: Link;
            length-: INTEGER (** the length of the list **)
        END;
        (* The field "length" (read-only outside this module) has been added to "List".
        This reduces the  time to determine the VList's length to O(1). *)
        (* primary operation #4: the length of the VList. *)

    VAR
        nilBase: Base;

    (** Used for processing an element in "FoldR" **)
    PROCEDURE (VAR a: Accum) Do- (e: Element), NEW, ABSTRACT;

    (** Process the elements of "l" in reverse **)
    PROCEDURE (IN l: List) FoldR* (VAR a: Accum), NEW;
    (* Uses only O(log n) storage for pointers *)

        PROCEDURE Aux (IN k: Link; len: INTEGER);
            VAR i: INTEGER;
        BEGIN
            IF len = 0 THEN RETURN END;
            Aux(k.base.link, len - k.offset - 1);
            FOR i := 0 TO k.offset DO
                a.Do(k.base.block[i])
            END
        END Aux;

    BEGIN
        Aux(l.link, l.length)
    END FoldR;

    (** Returns the first element of "l".  It is an error for "l" be empty. **)
    PROCEDURE (IN l: List) Car* (): Element, NEW;
    (* An indirect load via the list "link". *)
    BEGIN
        ASSERT(l.length > 0);
        RETURN l.link.base.block[l.link.offset]
    END Car;

    (** Returns the "n"th element of "l". It is an error for "n" to be negative or at least
    "l.length". **)
    PROCEDURE (IN l: List) Nth* (n: INTEGER): Element, NEW;
    (* primary operation #1 *)
        VAR k: Link;
    BEGIN
        ASSERT(0 <= n); ASSERT(n < l.length);
        k := l.link;
        WHILE n > k.offset DO
            DEC(n, k.offset + 1);
            k := k.base.link
        END;
        RETURN k.base.block[k.offset - n]
    END Nth;

    PROCEDURE (b: Base) NewBlock (size: INTEGER; e: Element), NEW;
    BEGIN
        b.lastUsed := 0; NEW(b.block, size); b.block[0] := e
    END NewBlock;

    (** Prefix "e" to "l". **)
    PROCEDURE (VAR l: List) Cons* (e: Element), NEW;
    (* primary operation #2 *)

        PROCEDURE NewBase (size: INTEGER);
            VAR b: Base;
        BEGIN
            NEW(b); b.link := l.link; b.NewBlock(size, e);
            l.link.base := b; l.link.offset := 0
        END NewBase;

    BEGIN
        INC(l.length);
        IF l.link.base = NIL THEN
            ASSERT(l.length = 1); NewBase(1)
        ELSIF l.link.offset + 1 = LEN(l.link.base.block) THEN
            (* If there is no room in "block" then a new "Base", with its length doubled in
            size, is added and the new entry made. *)
            NewBase(2 * LEN(l.link.base.block))
        ELSIF l.link.offset = l.link.base.lastUsed THEN
        (* "offset" is compared with "lastUsed". If they are the same and there is still
        room in "block", they are simply both incremented and the new entry made. *)
            INC(l.link.offset); (* Increment "offset". *)
            INC(l.link.base.lastUsed); (* Increment "lastUsed". *)
            l.link.base.block[l.link.offset] := e (* New entry. *)
        ELSIF l.link.base.block[l.link.offset + 1] = e THEN
        (* If the next location happens to contain an element identical to the new element.
        only "offset" is incremented *)
            INC(l.link.offset) (* Increment "offset". *)
        ELSE
        (* If "offset" is less than "lastUsed", "Cons" is being applied to the tail of a
        longer vlist. In this case a new "Base" must be allocated and its "link" set to the
        tail contained in the original list with "offset" being set to the point in this tail
        and the new entry made.  The two lists now share a common tail, as would have
        been the case with a linked list implementation. *)
            NewBase(1)
        END
    END Cons;

    (** Remove the first element of "l". Unlike Common Lisp it is an error for "l" be empty. **)
    PROCEDURE (VAR l: List) Cdr* (), NEW;
    (* primary operation #3 *)
    (* Follow "link" to the next "Base" if "offset" of "link" is 0 else decrement
    "offset" of "link" *)
    BEGIN
        ASSERT(l.length > 0); DEC(l.length);
        IF l.link.offset = 0 THEN
            l.link := l.link.base.link (* Follow "link" to the next "Base". *)
        ELSE
            DEC(l.link.offset) (* Decrement "offset" of "link". *)
        END
    END Cdr;

    (** Remove the first "n" elements of "l".  It is an error for "n" to be negative or at
    least "l.length".  Except for performance, equivalent to performing "n" "Cdr"s **)
    PROCEDURE (VAR l: List) NthCdr* (n: INTEGER), NEW;
        VAR k: Link;
    BEGIN
        ASSERT(0 <= n); ASSERT(n < l.length); DEC(l.length, n);
        k := l.link;
        WHILE n > k.offset DO
            DEC(n, k.offset + 1);
            k := k.base.link
        END;
        l.link.base := k.base; l.link.offset := k.offset - n;
    END NthCdr;
    
    (** initialise "l" to the empty list **)
    PROCEDURE (VAR l: List) Init*, NEW;
    BEGIN
        l.link.base := nilBase; l.link.offset := -1;
        l.length := 0
    END Init;

    (** Used for outputting in "Exp" **)
    PROCEDURE (IN o: Out) Char- (e: Element), NEW, ABSTRACT;

    (** "Expose" exposes the structure of "l" by outputting it, separating the blocks
    with '┃' characters **)
    PROCEDURE (IN l: List) Expose* (IN o: Out), NEW;
        VAR k: Link; len, i: INTEGER;
    BEGIN
        k := l.link; len := l.length;
        IF len = 0 THEN RETURN END;
        LOOP
            FOR i := k.offset TO 0 BY -1 DO
                o.Char(k.base.block[i])
            END;
            DEC(len, k.offset+1);
            IF len = 0 THEN RETURN END;
            o.Char('┃');
            k := k.base.link            
        END
    END Expose;

BEGIN
    NEW(nilBase); nilBase.NewBlock(1, '*')
END RosettaVLists.

Interface extracted from implementation:

DEFINITION RosettaVLists;

	TYPE
		Accum = ABSTRACT RECORD 
			(VAR a: Accum) Do- (e: Element), NEW, ABSTRACT
		END;

		Element = CHAR;

		List = RECORD 
			length-: INTEGER;
			(IN l: List) Car (): Element, NEW;
			(VAR l: List) Cdr, NEW;
			(VAR l: List) Cons (e: Element), NEW;
			(IN l: List) Expose (IN o: Out), NEW;
			(IN l: List) FoldR (VAR a: Accum), NEW;
			(VAR l: List) Init, NEW;
			(IN l: List) Nth (n: INTEGER): Element, NEW;
			(VAR l: List) NthCdr (n: INTEGER), NEW
		END;

		Out = ABSTRACT RECORD 
			(IN o: Out) Char- (e: Element), NEW, ABSTRACT
		END;

END RosettaVLists.

Module that uses previous module:

MODULE RosettaVListsUse;

    IMPORT Out, VLists := RosettaVLists;

    TYPE
        Char = VLists.Element;
        String = VLists.List;
        Log = RECORD (VLists.Out) END; (* Used for outputting in "Exp" *)
        App = RECORD (VLists.Accum) s: String END;

    (* Used for appending in "FoldR" *)
    PROCEDURE (VAR a: App) Do (c: Char);
    BEGIN
        a.s.Cons(c)
    END Do;

    (* Uses "FoldR" to concatenate "f" onto "r". *)
    PROCEDURE Append (IN f: String; VAR r: String);
        VAR a: App;
    BEGIN
        a.s := r; f.FoldR(a); r := a.s
    END Append;

    (* Concatenate "f" onto "r". *)
    PROCEDURE Prefix (f: ARRAY OF CHAR; VAR r: String);
        VAR i: INTEGER;
    BEGIN
        FOR i := LEN(f$) - 1 TO 0 BY -1 DO r.Cons(f[i]) END
    END Prefix;

    PROCEDURE Output (s: String);
        VAR i: INTEGER;
    BEGIN
        FOR i := 0 TO s.length - 1 DO Out.Char(s.Nth(i)) END;
    END Output;

    (* Used for outputting in "Expose" *)
    PROCEDURE (IN o: Log) Char- (c: Char);
    BEGIN
        Out.Char(c)
    END Char;

    PROCEDURE Display (IN name: ARRAY OF CHAR; s: String);
        VAR o: Log;
    BEGIN
        Out.String(name + ' = "'); Output(s);
        Out.String('"; length = '); Out.Int(s.length, 0);
        Out.String('; stored as "'); s.Expose(o); Out.Char('"');
        Out.Ln
    END Display;

    PROCEDURE Use*; (* Examples to demonstrate persistence *)
        VAR nu, no, e, d, b: String;
    BEGIN
        nu.Init; Prefix("numerator", nu); Display("nu", nu);
        no := nu; Display("no", no);
        no.NthCdr(5); Display("no", no);
        Prefix("nomin", no); Display("no", no);
        e := nu; e.Cons('e'); Display("e", e);
        Display("no", no); Display("nu", nu);
        d.Init; Prefix("data", d); Display("d", d);
        b.Init; Prefix("base", b); Display("b", b);
        Append(d, b); Display("d", d); Display("b", b);
    END Use;

END RosettaVListsUse.

Execute: ^Q RosettaVListsUse.Use

Output:
nu = "numerator"; length = 9; stored as "nu┃mera┃to┃r"
no = "numerator"; length = 9; stored as "nu┃mera┃to┃r"
no = "ator"; length = 4; stored as "a┃to┃r"
no = "nominator"; length = 9; stored as "no┃mi┃n┃a┃to┃r"
e = "enumerator"; length = 10; stored as "enu┃mera┃to┃r"
no = "nominator"; length = 9; stored as "no┃mi┃n┃a┃to┃r"
nu = "numerator"; length = 9; stored as "nu┃mera┃to┃r"
d = "data"; length = 4; stored as "d┃at┃a"
b = "base"; length = 4; stored as "b┃as┃e"
d = "data"; length = 4; stored as "d┃at┃a"
b = "database"; length = 8; stored as "d┃atab┃as┃e"

D

Translation of: C
import core.stdc.stdio: fprintf, stderr;
import core.stdc.stdlib: malloc, free, abort;

/// Uses C malloc and free to manage its memory.
/// Use only VList.alloc and VList.free.
struct VList(T) {
    static struct Sublist {
        Sublist* next;
        T[0] dataArr0;

        @property data() inout pure nothrow {
            return dataArr0.ptr;
        }

        static typeof(this)* alloc(in size_t len) nothrow {
            auto ptr = cast(typeof(this)*)malloc(typeof(this).sizeof +
                                                 T.sizeof * len);
            ptr.next = null;
            return ptr;
        }
    }

    // A dynamic array of pointers to growing buffers seems
    // better than a linked list of them.
    Sublist* head;
    size_t lastSize, ofs;

    static typeof(this)* alloc() nothrow {
        auto v = cast(typeof(this)*)malloc(VList.sizeof);
        enum startLength = 1;
        v.head = Sublist.alloc(startLength);
        v.lastSize = startLength;
        v.ofs = 0;
        return v;
    }

    void free() nothrow {
        while (this.head) {
            auto s = this.head.next;
            .free(this.head);
            this.head = s;
        }
        .free(&this);
    }

    @property size_t length() const nothrow {
        return this.lastSize * 2 - this.ofs - 2;
    }

    T* addr(in size_t idx) const nothrow {
        const(Sublist)* s = this.head;
        size_t top = this.lastSize;
        size_t i = idx + this.ofs;

        if (i + 2 >= (top << 1)) {
            fprintf(stderr, "!: idx %zd out of range\n", idx);
            abort();
        }
        while (s && i >= top) {
            s = s.next;
            i ^= top;
            top >>= 1;
        }
        return s.data + i;
    }

    T elem(in size_t idx) const nothrow {
        return *this.addr(idx);
    }

    // Currently dangerous.
    //T opIndex(in size_t idx) const nothrow {
    //    return elem(idx);
    //}

    T* prepend(in T x) nothrow {
        if (!this.ofs) {
            auto s = Sublist.alloc(this.lastSize << 1);
            if (s == null) {
                fprintf(stderr, "?: alloc failure\n");
                return null;
            }
            this.lastSize <<= 1;
            this.ofs = this.lastSize;
            s.next = this.head;
            this.head = s;
        }

        this.ofs--;
        auto p = this.head.data + this.ofs;
        *p = x;
        return p;
    }

    T popHead() nothrow {
        if (this.lastSize == 1 && this.ofs == 1) {
            fprintf(stderr, "!: empty list\n");
            abort();
        }

        auto x = this.head.data[this.ofs];
        this.ofs++;

        if (this.ofs == this.lastSize) {
            this.ofs = 0;
            if (this.lastSize > 1) {
                auto s = this.head;
                this.head = s.next;
                this.lastSize >>= 1;
                .free(s);
            }
        }

        return x;
    }

    // Range protocol is missing.
}


void main() {
    import std.stdio, std.bigint;
    enum N = 10;

    auto v = VList!BigInt.alloc;
    foreach (immutable i; 0 .. N)
        v.prepend(i.BigInt);

    writefln("v.length = %d", v.length);
    foreach (immutable i; 0 .. N)
        writefln("v[%d] = %s", i, v.elem(i));
    foreach (immutable i; 0 .. N)
        writefln("popHead: %s", v.popHead);

    v.free;
}
Output:
v.length = 10
v[0] = 9
v[1] = 8
v[2] = 7
v[3] = 6
v[4] = 5
v[5] = 4
v[6] = 3
v[7] = 2
v[8] = 1
v[9] = 0
popHead: 9
popHead: 8
popHead: 7
popHead: 6
popHead: 5
popHead: 4
popHead: 3
popHead: 2
popHead: 1
popHead: 0


FreeBASIC

VList.inc

'********************************************************************
' FBVLIST, Virtual ListBox custom control for FreeBasic
'********************************************************************
' Public Domain by Borje Hagsten, December 2000
'
' Modified for Freebasic by James Klutho
'--------------------------------------------------------------------
'  VL_REFRESH      - to refresh control with new array data
' wParam = Not used, should be 0.
' lParam = Not used, should be 0.
' Returns: Nothing, 0
' Example: SendMessage hWndCtrl,  VLB_REFRESH, 0, 0
'--------------------------------------------------------------------
'  VL_SIZEHANDLER  - internal, for handling resizing and memory DC's etc.
' wParam = Not used, should be 0.
' lParam = Not used, should be 0.
' Returns: Nothing, 0
' Example: SendMessage hWndCtrl,  VLB_SIZEHANDLER, 0, 0
'--------------------------------------------------------------------
'  VL_GETSELECTED  - returns selected line number ((array item)
' wParam = not used, should be 0.
' lParam = not used, should be 0.
' Returns: Index of selected line.
' Example: index = SendMessage(hWndCtrl,  VLB_GETSELECTED, 0, 0)
'--------------------------------------------------------------------
'  VL_SETSELECTED  - sets selected line number ((array item)
' wParam = Line to select.
' lParam = Redraw flag.  TRUE to redraw,  FALSE to ignore
' Returns: Index of selected line, or -1 if no selection could be made.
' Example: index = SendMessage(hWndCtrl,  VLB_SETSELECTED, SelectLine,  TRUE)
'--------------------------------------------------------------------
'  VL_GETTOPLINE   - returns first visible line in control
' wParam = not used, should be 0.
' lParam = not used, should be 0.
' Returns: Index of control's top (first visible) line.
' Example: index = SendMessage(hWndCtrl,  VLB_GETTOPLINE, 0, 0)
'--------------------------------------------------------------------
'  VL_SETTOPLINE   - sets first visible line in control
' wParam = Line to show as top (first visible) line.
' lParam = Redraw flag.  TRUE to redraw,  FALSE to ignore
' Returns: Index of top line, or -1 if no items are available.
' Example: index = SendMessage(hWndCtrl,  VLB_SETTOPLINE, TopLine,  TRUE)
'--------------------------------------------------------------------
'  VLN_RETURN
' Notification sent to parent's  WM_COMMAND when Enter key has been pressed
'--------------------------------------------------------------------
'  VLN_SPACE
' Notification sent to parent's  WM_COMMAND when Space bar has been pressed
'--------------------------------------------------------------------
'  VLN_DELETE
' Notification sent to parent's  WM_COMMAND when Delete key has been pressed

'********************************************************************
' Declares
'********************************************************************

Declare Sub SetSBar(Myhwnd As HWND, Byval vhPage As Long, Byval vhMax As Long, Byval vhPos As Long, Byval vhBar As Long)

'VList messages and Notifications
#define VL_SETARRAY     WM_USER + 1
#define VL_REFRESH      WM_USER + 2
#define VL_GETSELECTED  WM_USER + 3
#define VL_SETSELECTED  WM_USER + 4
#define VL_GETTOPLINE   WM_USER + 5
#define VL_SETTOPLINE   WM_USER + 6
#define VL_SIZEHANDLER  WM_USER + 7
#define VL_GETCURSEL    WM_USER + 8
#define VL_SETCURSEL    WM_USER + 9

#define VLN_RETURN      WM_USER + 200
#define VLN_SPACE       WM_USER + 201
#define VLN_DELETE      WM_USER + 202

#define FBVLISTSTYLES   WS_VISIBLE OR WS_CHILD OR WS_VSCROLL OR WS_TABSTOP OR WS_DLGFRAME OR WS_HSCROLL

#define VL_WSTRINGLEN  50  'Change to any desired fixed length Wstring you desire
#define USEWSTR         1  'Change to zero to use ANSI strings - non zero for Wstrings

Type MyNotify
    NMHeader As NMHDR
    Param1   As Long
    Param2   As Long
    Param3   As Long
    Param4   As Long
End Type

Type vListData                 'Type variable to hold private ListBox data
    hParent      As HWND       'Can be freely customized to meet extended needs
    hInst        As HINSTANCE
    id           As Long
    cyChar       As Long
    wMaxHeight   As Long
    wFirstLine   As Long
    wLastLine    As Long
    tLineCount   As Long
    charWidth    As Long
    wMaxWidth    As Long
    iHscrollMax  As Long
    iHscrollPos  As Long
    xPos         As Long
    hBit         As hGDIOBJ
    memDC        As hDC
    SelLine      As Long
    hFont        As hFont
    st           As String Ptr
    ws           As WSTRING Ptr
End Type


Function VLSendNotifyMessage(Byval hWnd As hWnd, Byval hCtrl As hWnd, Byval CtrlID As Long, Byval NCode As Long,Byval MyParam1 As Long, Byval MyParam2 As Long, Byval MyParam3 As Long, Byval MyParam4 As Long) As Long
    Dim NMG As MyNotify
    
    NMG.NMHeader.hwndFrom=hCtrl
    NMG.NMHeader.idFrom=CtrlID
    NMG.NMHeader.code=NCode
    NMG.Param1=MyParam1
    NMG.Param2=MyParam2
    NMG.Param3=MyParam3
    NMG.Param4=MyParam4
    
    Return SendMessage(hWnd, WM_NOTIFY,Cast(wParam,CtrlID), Cast(lParam,Varptr(NMG)))
End Function         

'********************************************************************
' Set Scroll bars
'********************************************************************
Sub SetSBar( myhwnd As HWND, Byval vhPage As Long, Byval vhMax As Long,Byval vhPos As Long, Byval vhBar As Long)
    Dim si As SCROLLINFO
    
    si.cbSize = Sizeof(si)
    si.fMask  = SIF_ALL Or SIF_DISABLENOSCROLL
    si.nMin   = 0
    si.nMax   = MAX(0, vhMax)
    si.nPage  = vhPage
    si.nPos   = vhPos
    SetScrollInfo myhwnd, vhBar, @si, -1
End Sub

'********************************************************************
' Main control procedure
'********************************************************************
Function VL_Proc (hWnd As Hwnd, wMsg As UINT, _
    wParam As WPARAM, lParam As LPARAM) As LRESULT
    Dim tm As TEXTMETRIC, rc As RECT, wRect As RECT
    Dim ps As PAINTSTRUCT,_
    si   As SCROLLINFO, lp As Point, _
    hdc  As hDC, hPen As hGDIOBJ, hBrush As hGDIOBJ, _
    tSel As Long, bkBrush As hGDIOBJ, hBrushSel As hGDIOBJ, _
    y    As Long, i As Long, iVscrollInc As Long, hScrlInc As Long
    
    Dim MyWStr As wstring * 50
    
    'Note: v is declared as DIM, but stored globally via DIMAlloc and
    '      a pointer to the returned handle is stored in the extra bytes
    '      of the control's private window class (in cbWndExtra), so each
    '      control still can hold its own private data.
    
    Dim v As VlistData Ptr
    
    If wMsg <> WM_CREATE Then v = GetProp(hWnd,"VlistData")
    
    Select Case wMsg
    Case WM_CREATE  'Allocate storage for the vListData structure.        
        v = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, Sizeof(VlistData))
        'print v
        If v Then
            SetProp hWnd, "VlistData", Cast(HANDLE,v)
        Else
            MessageBox hWnd, "Could not allocate memory for Virtual Listbox" & Chr$(0), _
            "FBLIST32 message" & Chr$(0), MB_OK
            Function = -1 : Exit Function  'Return -1 to break the action
        End If
        
        v->hParent = GetParent(hWnd)
        v->id      = GetWindowLong(hWnd, GWL_ID)
        v->hInst   = Cast(hInstance, GetWindowLongPtr(hWnd, GWLP_HINSTANCE))
        v->SelLine = -1 : v->tLineCount = -1
        SendMessage hWnd, VL_SIZEHANDLER, 0, 0
        
    Case WM_DESTROY
        If v Then
            If v->hbit  Then DeleteObject SelectObject(v->memDC, v->hbit)
            If v->memDC Then DeleteDC Cast(hDC, v->memDC)
            HeapFree(GetProcessHeap(), 0, Byval v)
            RemoveProp hWnd,"VlistData"
        End If
        
    Case WM_SETFONT
        If wParam <> v->hFont Then
            v->hFont = Cast(hFont, wParam)
            SelectObject v->memDC, v->hFont
            GetTextMetrics (v->memDC, @tm)                  'Get font parameters
            v->cyChar = tm.tmHeight + tm.tmExternalLeading  'Line spacing
            v->charWidth  = tm.tmAveCharWidth               'Average character width
            GetWindowRect(hWnd, @wRect)                     'Adjust height to avoid partial lines
            v->wMaxHeight = (wRect.Bottom - wRect.Top) \ v->cyChar
            v->wMaxWidth = MAX(1, ((wRect.Right - wRect.Left) / 2) / (v->charWidth - 1)) 'Get window size in characters
            SetWindowPos hWnd, 0, 0, 0, wRect.Right - wRect.Left,v->wMaxHeight * v->cyChar + 4,SWP_NOMOVE Or SWP_NOZORDER
            
            SendMessage hWnd, VL_SIZEHANDLER, 0, 0
        End If
        
    Case WM_SIZE
        If Hiword(lParam) Then
            v->wMaxHeight = Hiword(lParam) / v->cyChar
            SendMessage hWnd, VL_SIZEHANDLER, 0, 0
        End If
        
    Case VL_SIZEHANDLER  'create a virtual window that fits current window size
        If v->hbit  Then DeleteObject SelectObject(v->memDC,v->hbit)
        If v->memDC Then DeleteDC v->memDC
        
        hDC = GetDC(hWnd)
        GetClientRect(hWnd, @wRect)
        v->memDC = CreateCompatibleDC(hDC)
        v->hbit  = CreateCompatibleBitmap(hDC, wRect.Right, wRect.Bottom)
        v->hbit  = SelectObject(v->memDC, v->hbit)
        
        hbrush   = GetStockObject( WHITE_BRUSH)
        
        If hbrush Then SelectObject v->memDC, hbrush
        If v->hFont = 0 Then v->hFont = GetStockObject(ANSI_VAR_FONT)
        If v->hFont Then SelectObject v->memDC, v->hFont
        PatBlt v->memDC, 0, 0, wRect.Right, wRect.Bottom, PATCOPY
        
        GetTextMetrics (v->memDC, @tm)                  'Get font parameters
        v->cyChar = tm.tmHeight + tm.tmExternalLeading  'Line spacing
        v->charWidth = tm.tmAveCharWidth                'Average character width
        ReleaseDC (hWnd, hdc)
        
        v->wMaxHeight = wRect.Bottom / v->cyChar
        v->wMaxWidth = MAX(1, (wRect.Right / 2) / (v->charWidth - 1) ) 'Get window size in characters
        
        v->iHscrollMax = MAX (0, 1024 - v->wMaxWidth) '1024, max number of characters..
        v->iHscrollPos = MIN (v->iHscrollPos, v->iHscrollMax)
        v->xPos = v->charWidth * (- v->iHscrollPos)
        SetSBar hwnd, v->wMaxWidth, v->iHscrollMax, v->iHscrollPos, SB_HORZ
        
        v->wMaxHeight = wRect.Bottom / v->cyChar
        SetSBar hwnd, v->wMaxHeight, MAX(0, v->tLineCount), v->wFirstLine, SB_VERT
        InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
        
    Case WM_VSCROLL
        If v->tLineCount < 0 Then Exit Select
        
        Select Case Loword(wParam)
        Case SB_TOP        : iVscrollInc = -v->wFirstLine
        Case SB_BOTTOM     : iVscrollInc =  v->tLineCount - v->wMaxHeight
        Case SB_LINEUP     : iVscrollInc = -1
        Case SB_LINEDOWN   : If v->wFirstLine < v->tLineCount - v->wMaxHeight + 1 Then iVscrollInc =  1
        Case SB_PAGEUP     : iVscrollInc = MIN(-1, v->wMaxHeight)
        Case SB_PAGEDOWN   : iVscrollInc = MAX(1, v->wMaxHeight)
        Case SB_THUMBTRACK ' getScrollInfo enables 32-bit scroll positions
            si.cbSize = Sizeof(si)
            si.fMask  = SIF_TRACKPOS
            GetScrollInfo hWnd, SB_VERT, @si
            iVscrollInc = si.nTrackPos - v->wFirstLine
        Case Else          : iVscrollInc = 0
        End Select
        
        iVscrollInc = MAX(-v->wFirstLine, MIN(iVscrollInc, v->tLineCount - v->wMaxHeight + 1))
        
        If iVscrollInc <> 0 And v->wFirstLine <= v->tLineCount - v->wMaxHeight + 1 Then
            v->wFirstLine = MIN(v->wFirstLine + iVscrollInc, v->tLineCount - v->wMaxHeight + 1)
            SetSBar hwnd, v->wMaxHeight, MAX(0, v->tLineCount), v->wFirstLine, SB_VERT
            InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
        End If
        
    Case WM_HSCROLL
        Select Case Loword(wParam)
        Case SB_LINELEFT      : hScrlInc = -1
        Case SB_LINERIGHT     : hScrlInc =  1
        Case SB_PAGELEFT      : hScrlInc = -v->wMaxWidth
        Case SB_PAGERIGHT     : hScrlInc =  v->wMaxWidth
        Case SB_THUMBTRACK    : hScrlInc = Hiword(wParam) - v->iHscrollPos
        Case Else             : hScrlInc = 0
        End Select
        
        hScrlInc = MAX(-v->iHscrollPos, MIN(hScrlInc, v->iHscrollMax - v->iHscrollPos))
        If hScrlInc <> 0 Then
            v->iHscrollPos = v->iHscrollPos + hScrlInc
            v->xPos = v->charWidth * (- v->iHscrollPos)
            SetSBar hwnd, v->wMaxWidth, v->iHscrollMax, v->iHscrollPos, SB_HORZ
            InvalidateRect hwnd, Byval  NULL, 0 : UpdateWindow hwnd
        End If
        
    Case WM_GETDLGCODE ' Ensure that the control processes all keys (except tab and escape) by itself
        Dim iMsg As UINT, pMsg As TAGMSG Ptr
        pMsg = Cast(TAGMSG Ptr, lParam)
        If pMsg > 0 Then iMsg = pMsg->Message
        If iMsg = WM_KEYDOWN Or iMsg =  WM_CHAR Then
            Select Case pMsg->wParam
            Case VK_TAB, VK_ESCAPE   'let system handle these
                Function = DefWindowProc(hWnd, wMsg, wParam, lParam)
            Case Else
                Function = DLGC_WANTALLKEYS
            End Select
        End If
        
    Case WM_CHAR 
        #If(USEWSTR = 0) 
        
        ' mimic standard listbox's search on keypress
        For i = v->SelLine + 1 To v->tLineCount ' look for next item that starts like pressed key
            If Ucase(Chr(wParam)) = Ucase(Chr(Asc(v->st[i]))) Then  ' on success, set sel and exit
                SendMessage hWnd, VL_SETCURSEL, i, 1
                Exit Function
            End If
        Next
        
        'if no success and SelLine is > first item, scan from array start to SelLine - 1
        If v->SelLine > 0 Then 
            For i = 0 To v->SelLine - 1
                If Ucase(Chr(wParam)) = Ucase(Chr(Asc(v->st[i]))) Then
                    SendMessage hWnd, VL_SETCURSEL, i, 1
                    Exit Function
                End If
            Next
        End If
        #Else
        
        For i = v->SelLine + 1 To v->tLineCount ' look for next item that starts like pressed key
            If Ucase(Chr(wParam)) = Ucase(Chr(Asc(v->ws[i * VL_WSTRINGLEN]))) Then  ' on success, set sel and exit
                SendMessage hWnd, VL_SETCURSEL, i, 1
                Exit Function
            End If
        Next
        
        'if no success and SelLine is > first item, scan from array start to SelLine - 1
        If v->SelLine > 0 Then 
            For i = 0 To v->SelLine - 1
                If Ucase(Chr(wParam)) = Ucase(Chr(Asc(v->ws[i * VL_WSTRINGLEN]))) Then
                    SendMessage hWnd, VL_SETCURSEL, i, 1
                    Exit Function
                End If
            Next
        End If
        #endif
        
    Case WM_KEYDOWN
        If v->tLineCount < 0 And wParam <>  VK_TAB Then Exit Select
        
        Select Case (wParam)
        Case VK_UP, VK_LEFT
            If v->SelLine = -1 Then v->SelLine = v->wFirstLine + 1
            v->SelLine = MAX&(v->SelLine - 1, 0)
            If v->SelLine < v->wFirstLine Or v->SelLine > v->wLastLine Then
                v->wFirstLine = MIN&(v->SelLine, v->tLineCount - v->wMaxHeight + 1)
                SetSBar hwnd, v->wMaxHeight, MAX&(0, v->tLineCount), v->wFirstLine, SB_VERT
            End If
            InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
            
        Case VK_DOWN, VK_RIGHT
            If v->SelLine = -1 Then v->SelLine = v->wFirstLine - 1
            v->SelLine = MIN(v->SelLine + 1, v->tLineCount)
            'print v->wMaxHeight
            If v->SelLine > v->wLastLine Or v->SelLine < v->wFirstLine Then
                v->wFirstLine = MIN(v->SelLine, v->tLineCount) - v->wMaxHeight + 1
                'print v->wFirstLine
                SetSBar hwnd, v->wMaxHeight, MAX(0, v->tLineCount), v->wFirstLine, SB_VERT
            End If
            InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
            
        Case VK_PRIOR 'PgUp
            If v->SelLine = v->wFirstLine Then
                v->SelLine = MAX(v->SelLine - v->wMaxHeight + 1, 0)
            Else
                v->SelLine = v->wFirstLine
            End If
            
            If v->SelLine < v->wFirstLine + 1 Then
                v->wFirstLine = v->SelLine
                SetScrollPos (hWnd, SB_VERT, v->wFirstLine, TRUE)
            End If
            InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
            
        Case VK_NEXT  'PgDn
            If v->SelLine = v->wLastLine Then
                v->SelLine = MIN(v->SelLine + v->wMaxHeight - 1, v->tLineCount)
            Else
                v->SelLine = v->wLastLine
            End If
            
            If v->SelLine > v->wLastLine Then
                v->wFirstLine = MIN&(v->SelLine, v->tLineCount) - v->wMaxHeight + 1
                SetScrollPos (hWnd, SB_VERT, v->wFirstLine, TRUE)
            End If
            InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
            
        Case VK_SPACE  'Space bar pressed
            VLSendNotifyMessage v->hParent,hWnd,v->id,VLN_SPACE,0,0,0,0
            
        Case VK_RETURN 'Enter key pressed
            VLSendNotifyMessage v->hParent,hWnd,v->id,VLN_RETURN,0,0,0,0
            
        Case VK_DELETE 'Delete key pressed
            VLSendNotifyMessage v->hParent,hWnd,v->id,VLN_DELETE,0,0,0,0
            
        Case VK_HOME
            v->SelLine = 0 : v->wFirstLine = 0
            SetScrollPos (hWnd, SB_VERT, v->wFirstLine, TRUE)
            InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
            
        Case VK_END
            v->SelLine = v->tLineCount
            v->wFirstLine = v->tLineCount - v->wMaxHeight + 1
            SetScrollPos (hWnd, SB_VERT, v->wFirstLine, TRUE)
            InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
            
        Case Else
            
    End Select
        
    Case WM_MOUSEMOVE
        If v->tLineCount < 0 Then Exit Select
        If wParam =  MK_LBUTTON Then
            GetCursorPos @lp : GetWindowRect hWnd, @wRect
            If lp.y < wRect.Top + 3 Then
                tSel = v->wFirstLine - ((wRect.Top - lp.y) \ v->cyChar + 1)
            Else
                tSel = v->wFirstLine + Hiword(lParam) \ v->cyChar
            End If
            
            If tSel < 0 Then tSel = 0
            If tSel > v->tLineCount Then tSel = v->tLineCount
            If v->SelLine = tSel Then Exit Select 'no need to repeat ourselves..
            
            If tSel > v->wLastLine Then v->wFirstLine = tSel - v->wMaxHeight + 1
            If tSel < v->wFirstLine Then v->wFirstLine = tSel
            v->SelLine = tSel
            
            If v->tLineCount > v->wMaxHeight - 1 Then
                SetSBar hwnd, v->wMaxHeight, MAX(0, v->tLineCount), v->wFirstLine, SB_VERT
            End If
            
            InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
        End If
        
    Case WM_LBUTTONDBLCLK
        If v->tLineCount < 0 Then Exit Select
        v->SelLine = MAX(0, v->wFirstLine + Hiword(lParam) \ v->cyChar)
        If v->SelLine <= v->tLineCount Then
            SendMessage v->hParent, WM_COMMAND, MAKELONG(v->id, LBN_DBLCLK), Cast(lparam,hwnd)
        End If
        
    Case WM_LBUTTONDOWN
        If v->tLineCount < 0 Then Exit Select
        SetCapture hWnd
        v->SelLine = v->wFirstLine + Hiword(lParam) \ v->cyChar
        If v->SelLine < 0 Then v->SelLine = 0
        If v->SelLine > v->tLineCount Then v->SelLine = v->tLineCount
        SetFocus hWnd
        InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
        
    Case WM_LBUTTONUP
        If v->tLineCount < 0 Then Exit Select
        ReleaseCapture
        
    Case WM_KILLFOCUS, WM_SETFOCUS ' Must process these if line is selected
        If v->SelLine > - 1 Then
            InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
        Else
            GetClientRect hWnd, @wRect
            rc.Left = 0 : rc.Top = 0 : rc.Right = wRect.Right : rc.Bottom = v->cyChar
            hdc = GetDc(hWnd)
            DrawFocusRect hDC, @rc
            ReleaseDc hWnd, hdc
        End If
        If wMsg =  WM_KILLFOCUS Then 'Send notifications to parent
            SendMessage v->hParent, WM_COMMAND, MAKELONG(v->id, LBN_KILLFOCUS), Cast(lparam,hwnd)
        Else
            SendMessage v->hParent, WM_COMMAND, MAKELONG(v->id, LBN_SETFOCUS), Cast(lparam,hwnd)
        End If
        
    Case WM_PAINT 'Draw only the list items that needs to be shown
        'Send  WM_CTLCOLORLISTBOX to parent, to get eventual brush for bg color
        bkBrush = Cast(hGDIOBJ,SendMessage(v->hParent, WM_CTLCOLORLISTBOX, Cast(wParam,v->memDC), Cast(lparam,hwnd)) )
        If bkBrush Then SelectObject v->memDC, bkBrush
        
        hdc = BeginPaint(hWnd, @ps)
        GetClientRect(hWnd, @wRect)
        
        v->wFirstLine = MAX(0, v->wFirstLine)
        v->wLastLine  = MIN(v->tLineCount, v->wFirstLine + v->wMaxHeight - 1)
        
        PatBlt v->memDC, 0, 0, wRect.Right, wRect.Bottom, PATCOPY
        
        If v->tLineCount > -1 Then ' DRAW TEXT (ARRAY)
            For i = v->wFirstLine To v->wLastLine
                y = v->cyChar * (-v->wFirstLine + i)
                
                #If(USEWSTR = 0)
                    TabbedTextOut v->memDC, v->xPos, y,Byval Strptr(v->st[i]), Len(v->st[i]),0, Byval  NULL, 0
                #Else
                    MyWStr = v->ws[i * VL_WSTRINGLEN]   '"Jimmy " + WSTR(i)
                    TabbedTextOutW v->memDC, v->xPos, y,Byval Varptr(MyWstr), Len(MyWStr),0, Byval  NULL, 0
                #endif
            Next
        End If
        
        'DRAW SELECTION
        If v->SelLine >= v->wFirstLine Then
            If v->SelLine > v->tLineCount Then v->SelLine = v->tLineCount
            rc.Left = 0 : rc.Top = v->cyChar * (v->SelLine - v->wFirstLine)
            rc.Right = wRect.right : rc.Bottom = rc.Top + v->cyChar
            
            '=== Draw Selection rectangle, plus focus rectangle ===
            If GetFocus = hWnd Then
                hBrushSel = GetSysColorBrush( COLOR_HIGHLIGHT)
            Else
                hBrushSel = GetSysColorBrush( COLOR_INACTIVECAPTION)
            End If
            hBrushSel = SelectObject(v->memDC, hBrushSel)
            hPen = CreatePen( PS_DOT, 1, GetSysColor( COLOR_HIGHLIGHTTEXT))
            hPen = SelectObject(v->memDC, hPen)
            
            SetROP2(v->memDC, R2_MERGEPENNOT)
            Rectangle(v->memDC, rc.Left - 1, rc.Top - 1, rc.Right + 1, rc.Bottom + 1)
            If GetFocus() = hWnd Then DrawFocusRect(v->memDC, @rc)
            
            SelectObject v->memDC, hBrushSel
            DeleteObject SelectObject(v->memDC, hPen)
            SendMessage v->hParent, WM_COMMAND, MAKELONG(v->id, LBN_SELCHANGE), Cast(lparam,hwnd)
            
        Elseif v->SelLine = -1 And GetFocus = hWnd Then
            rc.Left = 0 : rc.Top = 0 : rc.Right = wRect.right : rc.Bottom = v->cyChar
            DrawFocusRect v->memDC, @rc
        End If
        
        BitBlt hDC, wRect.top, wRect.left, wRect.right, wRect.bottom, v->memDC, 0, 0, SRCCOPY
        EndPaint(hWnd, @ps)
        
    Case WM_ERASEBKGND 'Prevent erasing background
        Function = 1
        
    Case LB_SETHORIZONTALEXTENT
        GetClientRect(hWnd, @wRect)
        v->iHscrollMax = MAX (0, wParam - wRect.Right)
        SetSBar hwnd, v->wMaxWidth, v->iHscrollMax, v->iHscrollPos, SB_HORZ
        
    Case VL_SETARRAY
        #If(USEWSTR = 0)
            v->st = Cast(Any Ptr,wParam)
        #Else
            v->ws = Cast(Any Ptr,wParam)
        #endif 
        v->SelLine = -1 
        v->tLineCount = lParam
        v->wFirstLine = 0
        
    Case VL_REFRESH
        SetSBar hwnd, v->wMaxHeight, MAX(0, v->tLineCount), v->wFirstLine, SB_VERT
        InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
        
    Case VL_GETSELECTED
        Function = v->SelLine
        
    Case VL_GETCURSEL
        Function = v->SelLine
        
    Case VL_SETSELECTED
        If wParam < 0 Then
            v->SelLine = -1
        Else
            v->SelLine = MIN(wParam, v->tLineCount)
        End If
        SetSBar hwnd, v->wMaxHeight, MAX(0, v->tLineCount), v->wFirstLine, SB_VERT
        If lParam Then 'Refresh control
            InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
        End If
        Function = v->SelLine
        
    Case VL_SETCURSEL
        If wParam < 0 Then
            v->SelLine = -1
        Else
            v->SelLine = MIN(wParam, v->tLineCount)
            If v->SelLine < v->wFirstLine Then
                v->wFirstLine = v->SelLine
            Elseif v->SelLine > v->wFirstLine + v->wMaxHeight - 1 Then
                v->wFirstLine = MIN(v->SelLine - v->wMaxHeight + 1, v->tLineCount - v->wMaxHeight + 1)
            End If
        End If
        
        SetSBar hwnd, v->wMaxHeight, MAX(0, v->tLineCount), v->wFirstLine, SB_VERT
        InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
        Function = v->SelLine
        
    Case VL_GETTOPLINE
        Function = v->wFirstLine
        
    Case VL_SETTOPLINE
        If wParam < 0 Then
            v->wFirstLine = 0
        Else
            v->wFirstLine = MIN(wParam, v->tLineCount - v->wMaxHeight + 1)
        End If
        SetSBar hwnd, v->wMaxHeight, MAX(0, v->tLineCount), v->wFirstLine, SB_VERT
        If lParam Then 'Refresh control
            InvalidateRect hWnd, Byval  NULL, 0 : UpdateWindow hwnd
        End If
        Function = v->wFirstLine
        
    Case Else  ' Process all other messages
        Function = DefWindowProc(hWnd, wMsg, wParam, lParam)

    End Select
End Function

Sub VL_INT()
    Dim wc As WNDCLASSEX
    Dim As String szClassName = "FBVLIST"
    
    If GetClassInfoEx(GetModuleHandle(Byval NULL), Strptr(szClassName), @wc) <> 0 Then
        '    'It is already registered
        Exit Sub
    End If
    
    wc.cbSize        = Sizeof(wc)
    wc.style         = CS_DBLCLKS
    wc.lpfnWndProc   = @VL_Proc
    wc.cbWndExtra    = 4  '4 extra bytes for pointer to UDT
    wc.hInstance     = GetModuleHandle(Byval NULL)
    wc.hCursor       = LoadCursor(NULL, Byval IDC_ARROW)
    wc.lpszClassName = Strptr(szClassName)
    
    RegisterClassEx @wc
End Sub

Code test

'Programmed for Freebasic by James Klutho
'--------------------------------------------------------------------

#include once "windows.bi"
#INCLUDE ONCE "VList.inc"

Dim Shared hVList1 As hwnd
Dim Shared hLBox As hwnd
Dim Shared hButExit As hwnd
Dim Shared hButChange As hwnd


Const IDC_VLIST = 101
Const IDC_LBOX  = 102
Const IDC_MYEXIT  = 103
Const IDC_MYCHANGE  = 104

'To switch between ANSI and Wstrings, make these changes in the VList.inc file

'define VL_WSTRINGLEN     50    'Change to any desired fixed length Wstring you desire
'define USEWSTR            1    'Change to zero to use dynamic ANSI strings

Dim Shared ss(50) As String                  'ANSI dynamic string
Dim Shared ww(50) As Wstring * VL_WSTRINGLEN 'Fixed length Wstring


Sub AddNote(hMyLBox As hwnd, s As String)
    Dim MyMsg As ZString * 256
    Static COUNT As Long
    Dim s5 As zSTRING * 5
    
    COUNT = COUNT +1
    s5 = Str(COUNT)
    MyMsg="Notification # "& s5 & ":" & s
    SendMessage(hMyLBox,LB_INSERTSTRING,0,Cast(lparam,Varptr(MyMsg)))
End Sub     

Declare Function WinMain (Byval hInstance As HINSTANCE, _
                          Byval hPrevInstance As HINSTANCE, _
                          Byval szCmdLine As zstring Ptr, _
                          Byval iCmdShow As Integer) As Integer
End WinMain(GetModuleHandle(null), null, Command(), SW_NORMAL)

'':::::
Function WndProc (Byval hWnd As HWND, Byval wMsg As UINT, _
    Byval wParam As WPARAM, Byval lParam As LPARAM) As LRESULT
    
    Dim MyNptr As MyNotify Ptr
    
    Function = 0
    
    Select Case(wMsg)
    Case WM_CREATE            
        Exit Function
        
    Case WM_COMMAND
        If GETFOCUS = hVList1 Then Exit Function
        
        Select Case Loword(wParam)
        Case IDC_MYEXIT
            ' // close the application sending an WM_CLOSE message
            If Hiword(wParam) = BN_CLICKED Then
                SendMessageW hwnd, WM_CLOSE, 0, 0
                Exit Function
            End If
        Case IDC_MYCHANGE
            ' // Display the message
            If Hiword(wParam) = BN_CLICKED Then
                #If(USEWSTR = 0)
                ss(10) = "Changed"
                #Else
                ww(10) = "Changed"
                #endif
                SendMessageW hVList1, VL_REFRESH, 0, 0
            End If
        End Select
        
    Case WM_NOTIFY 
        MyNptr = Cast(MyNotify Ptr,lParam)
        If MyNptr->NMHeader.idFrom = IDC_VLIST Then 
            Select Case MyNptr->NMHeader.code
            Case VLN_RETURN
                AddNote hLBox, "RETURN "
            Case VLN_SPACE
                AddNote hLBox, "SPACE  "
            Case VLN_DELETE
                AddNote hLBox, "DELETE "
            End Select                          
        End If 
        
    Case WM_PAINT
        Dim rct As RECT
        Dim pnt As PAINTSTRUCT
        Dim hDC As HDC
        
        hDC = BeginPaint(hWnd, @pnt)
        
        EndPaint(hWnd, @pnt)
        Exit Function            
        
    Case WM_KEYDOWN
        
        
    Case WM_DESTROY
        PostQuitMessage(0)
        Exit Function
    End Select
    
    Function = DefWindowProc(hWnd, wMsg, wParam, lParam)    
End Function

'':::::
Function WinMain (Byval hInstance As HINSTANCE, _
                  Byval hPrevInstance As HINSTANCE, _
                  Byval szCmdLine As zstring Ptr, _
                  Byval iCmdShow As Integer) As Integer    
    
    Dim wMsg As MSG
    Dim wcls As WNDCLASS     
    Dim hWnd As HWND
    Dim x As Long
    
    Function = 0
    
    With wcls
    	.style         = CS_HREDRAW Or CS_VREDRAW
    	.lpfnWndProc   = @WndProc
    	.cbClsExtra    = 0
    	.cbWndExtra    = 0
    	.hInstance     = hInstance
    	.hIcon         = LoadIcon(NULL, IDI_APPLICATION)
    	.hCursor       = LoadCursor(NULL, IDC_ARROW)
    	.hbrBackground = GetStockObject(WHITE_BRUSH)
    	.lpszMenuName  = NULL
    	.lpszClassName = @"FBListTest"
    End With
    
    If(RegisterClass(@wcls) = FALSE) Then
        MessageBox(null, "Failed to register wcls", "Error", MB_ICONERROR)
        Exit Function
    End If
    
    hWnd = CreateWindowEx(0, _
           @"FBListTest", _
           "The Hello Program", _
           WS_OVERLAPPEDWINDOW, _
           4, 4, 500, 500, _
           NULL, _
           NULL, _
           hInstance, _
           NULL)
    
    
    VL_Int
    
    hVList1 = CreateWindow ("FBVLIST",_   'window class name
              Byval NULL,_                'window caption
              FBVLISTSTYLES,_             'window style
              4,4,300,300,_               'initial Position
              hWnd,_                      'parent window handle
              Cast(hMENU,IDC_VLIST),_     'window menu handle
              hInstance,_                 'program instance handle
              Byval NULL) 
    
    hLBox = CreateWindow ("listbox",_  'window class name
            Byval NULL,_   'window caption
            LBS_NOTIFY Or WS_CHILDWINDOW Or WS_BORDER Or WS_VSCROLL Or WS_VISIBLE, _
            4,_    'initial x position
            325,_  'initial y position
            480,_  'initial x size
            100,_  'initial y
            HWND,_ 'parent window handle
            Cast(hMENU,IDC_LBOX),_
            hInstance,_  'program instance handle
            Byval NULL)
    
    hButExit = CreateWindow ("button",_  'window class name
               "Exit",_   'window caption
               WS_CHILDWINDOW Or WS_BORDER Or WS_VISIBLE, _
               325,_  'initial x position
               50,_   'initial y position
               50,_   'initial x size
               30,_   'initial y
               HWND,_ 'parent window handle
               Cast(hMENU,IDC_MYEXIT),_
               hInstance,_  'program instance handle
               Byval NULL)
    
    hButChange = CreateWindow ("button",_  'window class name
                 "Change",_   'window caption
                 WS_CHILDWINDOW Or WS_BORDER Or WS_VISIBLE, _
                 325,_  'initial x position
                 125,_  'initial y position
                 75,_   'initial x size
                 30,_   'initial y
                 HWND,_ 'parent window handle
                 Cast(hMENU,IDC_MYCHANGE),_
                 hInstance,_  'program instance handle
                 Byval NULL)                                                         
    
    SendMessage hVList1,WM_SETFONT,Cast(wParam,GetStockObject(SYSTEM_FIXED_FONT)),MAKELONG(TRUE,0)
    AddNote hLBox,"Ready"                        
    
    For x = Lbound(ww) To Ubound(ww)
        ww(x) = "FreeBasic Wide String " & Wstr(x)
    Next x 
    
    For x = Lbound(ss) To Ubound(ss)
        ss(x) = "FreeBasic " & Str(x)
    Next x                       
    
    
    #If(USEWSTR = 0)
        SendMessage hVList1,VL_SETARRAY,Cast(wparam,Varptr(ss(0))),Cast(lparam,Ubound(ss))
    #Else
        SendMessage hVList1,VL_SETARRAY,Cast(wparam,Varptr(ww(0))),Cast(lparam,Ubound(ww)) 
    #endif
    SendMessage hVList1,VL_REFRESH,0,0     
    
    
    ShowWindow(hWnd, iCmdShow)
    UpdateWindow(hWnd)
    
    While(GetMessage(@wMsg, NULL, 0, 0) <> FALSE)    
        TranslateMessage(@wMsg)
        DispatchMessage(@wMsg)
    Wend
    
    Function = wMsg.wParam
End Function


Go

package main

import "fmt" 

type vList struct {
    base   *vSeg
    offset int
}

type vSeg struct {
    next *vSeg
    ele  []vEle
}

// element type could be anything. i pick string to demonstrate the task.
type vEle string
    
// primary operation 1: locate the kth element.
func (v vList) index(i int) (r vEle) {
    if i >= 0 { 
        i += v.offset
        for sg := v.base; sg != nil; sg = sg.next {
            if i < len(sg.ele) {
                return sg.ele[i]
            }
            i -= len(sg.ele)
        }
    }
    // consistent with the way Go panics on slice index out of range
    panic("index out of range")
}

// primary operation 2: add an element to the front of the VList.
func (v vList) cons(a vEle) vList {
    if v.base == nil {
        return vList{base: &vSeg{ele: []vEle{a}}}
    }
    if v.offset == 0 {
        l2 := len(v.base.ele) * 2 
        ele := make([]vEle, l2)
        ele[l2-1] = a
        return vList{&vSeg{v.base, ele}, l2 - 1}
    }
    v.offset--
    v.base.ele[v.offset] = a
    return v
}   

// primary operation 3: obtain a new array beginning at the second element
// of an old array
func (v vList) cdr() vList {
    if v.base == nil {
        // consistent with panic above.  (not consistent with lisp)
        panic("cdr on empty vList")
    }
    v.offset++
    if v.offset < len(v.base.ele) {
        return v
    }
    return vList{v.base.next, 0}
}

// primary operation 4:  compute the length of the list.  (It's O(1).)
func (v vList) length() int {
    if v.base == nil {
        return 0
    }
    return len(v.base.ele)*2 - v.offset - 1
}

// A handy method:  satisfy stringer interface for easy output.
func (v vList) String() string {
    if v.base == nil {
        return "[]"
    }
    r := fmt.Sprintf("[%v", v.base.ele[v.offset])
    for sg, sl := v.base, v.base.ele[v.offset+1:]; ; {
        for _, e := range sl {
            r = fmt.Sprintf("%s %v", r, e)
        }
        sg = sg.next
        if sg == nil {
            break
        }
        sl = sg.ele
    }
    return r + "]"
}

// One more method for demonstration purposes
func (v vList) printStructure() {
    fmt.Println("offset:", v.offset)
    for sg := v.base; sg != nil; sg = sg.next {
        fmt.Printf("  %q\n", sg.ele) // %q illustrates the string type
    }
    fmt.Println()
}

// demonstration program using the WP example data
func main() {
    var v vList
    fmt.Println("zero value for type.  empty vList:", v)
    v.printStructure()

    for a := '6'; a >= '1'; a-- {
        v = v.cons(vEle(a))
    }
    fmt.Println("demonstrate cons. 6 elements added:", v)
    v.printStructure()
    
    v = v.cdr()
    fmt.Println("demonstrate cdr. 1 element removed:", v)
    v.printStructure()

    fmt.Println("demonstrate length. length =", v.length())
    fmt.Println()

    fmt.Println("demonstrate element access. v[3] =", v.index(3))
    fmt.Println()

    v = v.cdr().cdr()
    fmt.Println("show cdr releasing segment. 2 elements removed:", v)
    v.printStructure()
}
Output:
zero value for type.  empty vList: []
offset: 0

demonstrate cons. 6 elements added: [1 2 3 4 5 6]
offset: 1
  ["" "1" "2" "3"]
  ["4" "5"]
  ["6"]

demonstrate cdr. 1 element removed: [2 3 4 5 6]
offset: 2
  ["" "1" "2" "3"]
  ["4" "5"]
  ["6"]

demonstrate length. length = 5

demonstrate element access. v[3] = 5

show cdr releasing segment. 2 elements removed: [4 5 6]
offset: 0
  ["4" "5"]
  ["6"]

J

A vlist preallocates storage in increasing powers of 2. The "head" of the vlist is in the last (largest) storage block. Here we define a class with methods unshift (which adds to the "head" of the vlist), shift (which removes from the "head" of the vlist), size (which tells us how many elements the vlist currently contains), and get (which retrieves the nth element from the vlist):

coclass 'vlist'

off=: 0
lastsz=: 1
(current=: 'b1')=: 0

size=: {{ lastsz+off-1 }}

get=: {{
  assert. y>:0 ['negative index not supported'
  assert. y<size 'index too large'
  bi=. #:y+1     NB. work with binary representation of origin 1 index
  b=. #.(#bi){.1 NB. most significant bit (the reason for origin 1)
  i=. #.}.bi     NB. rest of index
  i{do 'b',":b
}}"0

unshift=: {{
  (current)=: y off} do current
  off=: 1+off
  if. off=lastsz do.
    off=: 0
    lastsz=: 2*lastsz
    current=: 'b',":lastsz
    (current)=: lastsz#0
  end.
  y
}}"0

shift=: {{
  assert. 0<size 'vlist empty'
  off=: off-1
  if. 0>off do.
    erase current
    lastsz=: <.-:lastsz
    off=: lastsz-1
    current=: 'b',":lastsz
  end.
  r=. off{do current
}}

Example use:

   L=: conew'vlist'
   size__L''
0
   unshift__L 100
100
   unshift__L 200 303 404 555
200 303 404 555
   size__L''
5
   get__L 0 1 2
100 200 303
   shift__L''
555
   size__L''
4

Caution: this is an accurate model of the vlist data structure but should not be used if performance is critical.

If performance is critical use J's native operations and make sure that there's only the named reference to the list when adding or removing the last item from the list. For example, given L=:100 200 303 404, use L=: L,555 to append to the list, and and after using {:L to extract the final element from L, use L=: }:L to discard the final element from the list. (And, of course, #L will report the size of the list.) J's implementation uses techniques which are in some ways similar in character to vlists for these operations (but uses copy on write if there's other references to the list).

Julia

Translation of: Go

Benchmarking suggests that the `cons routine` as given is not truly O(1), perhaps because of allocations. Other VList methods may well be O(1). In addition, benchmarking the native Vector or Array{Char, 1} type shows this to be superior in every timing benchmark over the VList implementation, except for the copy from second element, and that copy is only slower because of the time for making such a copy. Importantly, Julia has a `view` macro which is a similar copy-saving trick to that used by VList, only much faster, and also O(1). So, from the linked list form available to me, it seems use of VList may primarily be for languages with slower arrays.

""" Rosetta Code task rosettacode.org/wiki/VList """

import Base.length, Base.string

using BenchmarkTools

abstract type VNode end

struct VNil <: VNode end
const nil = VNil()

mutable struct VSeg{T} <: VNode
    next::VNode
    ele::Vector{T}
end

mutable struct VList
    base::VNode
    offset::Int
    VList(b = nil, o = 0) = new(b, o)
end

""" primary operation 1: locate the kth element. """
function index(v, i)
    i < 0 && error("index out of range")
    i += v.offset
    sg = v.base
    while sg !== nil
        i < length(sg.ele) && return sg.ele[i + 1]
        i -= length(sg.ele)
        sg = sg.next
    end
end

""" primary operation 2: add an element to the front of the VList. """
function cons(v::VList, a)
    v.base === nil && return VList(VSeg(nil, [a]), 0)
    if v.offset == 0
        newlen = length(v.base.ele) * 2
        ele = Vector{typeof(a)}(undef, newlen)
        ele[newlen] = a
        return VList(VSeg(v.base, ele), newlen - 1)
    end
    v.base.ele[v.offset] = a
    v.offset -= 1
    return v
end

""" primary operation 3: obtain new array beginning at second element of old array """
function cdr(v)
    v.base === nil && error("cdr on empty VList")
    v.offset += 1
    return v.offset < length(v.base.ele) ? v : VList(v.base.next, 0)
end

""" primary operation 4:  compute the length of the list.  (It's O(1).) """
Base.length(v::VList) = (v.base === nil) ? 0 : length(v.base.ele) * 2 - v.offset - 1

""" A handy method:  satisfy string interface for easy output. """
function Base.string(v::VList)
    v.base === nil && return "[]"
    r = "[" * string(v.base.ele[v.offset+1])
    sg, sl = v.base, v.base.ele[v.offset+2:end]
    while true
        r *= " " * join(sl, " ")
        sg = sg.next
        sg === nil && break
        sl = sg.ele
    end
    return r * "]"
end

""" Basic print for VList """
Base.print(io::IO, v::VList) = print(io, string(v))

""" One more method for demonstration purposes """
function print_structure(v::VList)
    println("offset: ", v.offset)
    sg = v.base
    while sg !== nil
        println("  $(sg.ele)") # illustrates the string type
        sg = sg.next
    end
    println()
end

""" demonstration program using the WP example data """
function testVList()
    v = VList()
    println("zero value for type.  empty VList: $v")
    print_structure(v)

    for a in '6':-1:'1'
        v = cons(v, a)
    end
    println("demonstrate cons. 6 elements added: $v")
    print_structure(v)

    v = cdr(v)
    println("demonstrate cdr. 1 element removed: $v")
    print_structure(v)

    println("demonstrate length. length = ", length(v), "\n")

    println("demonstrate element access. v[3] = ", index(v, 3), "\n")

    v = v |> cdr |> cdr
    println("show cdr releasing segment. 2 elements removed: $v")
    print_structure(v)

    # Timings for n = 10, 100, 1000, 1000 sized structures

    for i in 1:4
        v = VList()
        c = Char[]
        for a in 10^i:-1:1
            v = cons(v, a)
            push!(c, a)
        end
        println("Testing index for VList of size ", 10^i)
        arr = rand(1:10^i-1, 100)
        @btime let
            n = 0
            for k in $arr
                n = index($v, k)
            end
        end
        println("Testing index for vector of size ", 10^i)
        @btime let n = 0
            for k in $arr
                n = $c[k]
            end
        end
        println("Testing adding an element for VList of size ", 10^i)
        @btime let n = cons($v, 0) end
        println("Testing adding an element for vector of size ", 10^i)
        @btime let n = push!($c, '\0') end

        println("Testing new array beginning at second element for VList of size ", 10^i)
        @btime let m = cdr($v) end
        println("Testing new vector with copy beginning at second element for vector of size ", 10^i)
        @btime let m = popfirst!(copy($c)) end
        println("Testing new vector using a view beginning at second element for vector of size ", 10^i)
        @btime let m = @view $c[2:end] end

        println("Testing length for VList of size ", 10^i)
        @btime let n = length($v) end
        println("Testing length for vector of size ", 10^i)
        @btime let n = length($c) end
    end
end

testVList()
Output:
zero value for type.  empty VList: []
offset: 0

demonstrate cons. 6 elements added: [1 2 3 4 5 6]
offset: 1
  ['\x0b\x54\x2e\xa0', '1', '2', '3']
  ['4', '5']
  ['6']

demonstrate cdr. 1 element removed: [2 3 4 5 6]
offset: 2
  ['\x0b\x54\x2e\xa0', '1', '2', '3']
  ['4', '5']
  ['6']

demonstrate length. length = 5

demonstrate element access. v[3] = 5

show cdr releasing segment. 2 elements removed: [4 5 6]
offset: 0
  ['4', '5']
  ['6']

Testing index for VList of size 10
  28.100 μs (0 allocations: 0 bytes)
Testing index for vector of size 10
  49.141 ns (0 allocations: 0 bytes)
Testing adding an element for VList of size 10
  457.839 ns (3 allocations: 256 bytes)
Testing adding an element for vector of size 10
  6.600 ns (0 allocations: 0 bytes)
Testing new array beginning at second element for VList of size 10
  199.470 ns (2 allocations: 48 bytes)
Testing new vector with copy beginning at second element for vector of size 10
  6.738 ms (2 allocations: 40.06 MiB)
Testing new vector using a view beginning at second element for vector of size 10
  2.700 ns (0 allocations: 0 bytes)
Testing length for VList of size 10
  99.576 ns (3 allocations: 48 bytes)
Testing length for vector of size 10
  2.200 ns (0 allocations: 0 bytes)
Testing index for VList of size 100
  26.200 μs (0 allocations: 0 bytes)
Testing index for vector of size 100
  49.091 ns (0 allocations: 0 bytes)
Testing adding an element for VList of size 100
  476.596 ns (3 allocations: 1.12 KiB)
Testing adding an element for vector of size 100
  6.700 ns (0 allocations: 0 bytes)
Testing new array beginning at second element for VList of size 100
  200.000 ns (2 allocations: 48 bytes)
Testing new vector with copy beginning at second element for vector of size 100
  6.851 ms (2 allocations: 40.06 MiB)
Testing new vector using a view beginning at second element for vector of size 100
  2.700 ns (0 allocations: 0 bytes)
Testing length for VList of size 100
  100.530 ns (3 allocations: 48 bytes)
Testing length for vector of size 100
  2.200 ns (0 allocations: 0 bytes)
Testing index for VList of size 1000
  27.800 μs (245 allocations: 3.83 KiB)
Testing index for vector of size 1000
  49.144 ns (0 allocations: 0 bytes)
Testing adding an element for VList of size 1000
  648.436 ns (6 allocations: 8.23 KiB)
Testing adding an element for vector of size 1000
  8.600 ns (0 allocations: 0 bytes)
Testing new array beginning at second element for VList of size 1000
  205.900 ns (3 allocations: 64 bytes)
Testing new vector with copy beginning at second element for vector of size 1000
  6.769 ms (2 allocations: 40.06 MiB)
Testing new vector using a view beginning at second element for vector of size 1000
  2.700 ns (0 allocations: 0 bytes)
Testing length for VList of size 1000
  109.892 ns (5 allocations: 80 bytes)
Testing length for vector of size 1000
  2.300 ns (0 allocations: 0 bytes)
Testing index for VList of size 10000
  33.600 μs (716 allocations: 11.19 KiB)
Testing index for vector of size 10000
  49.190 ns (0 allocations: 0 bytes)
Testing adding an element for VList of size 10000
  1.954 μs (7 allocations: 128.16 KiB)
Testing adding an element for vector of size 10000
  6.700 ns (0 allocations: 0 bytes)
Testing new array beginning at second element for VList of size 10000
  205.612 ns (3 allocations: 64 bytes)
Testing new vector with copy beginning at second element for vector of size 10000
  6.876 ms (2 allocations: 40.09 MiB)
Testing new vector using a view beginning at second element for vector of size 10000
  2.700 ns (0 allocations: 0 bytes)
Testing length for VList of size 10000
  109.903 ns (5 allocations: 80 bytes)
Testing length for vector of size 10000
  2.200 ns (0 allocations: 0 bytes)

Kotlin

Translation of: Go
// version 1.1.3

class VList<T : Any?> {

    private class VSeg {
        var next: VSeg? = null
        lateinit var ele: Array<Any?>
    }

    private var base: VSeg? = null
    private var offset = 0

    /* locate kth element */
    operator fun get(k: Int): T {
        var i = k
        if (i >= 0) {
            i += offset
            var sg = base
            while (sg != null) {
                @Suppress("UNCHECKED_CAST")
                if (i < sg.ele.size) return sg.ele[i] as T
                i -= sg.ele.size
                sg = sg.next
            }
        }
        throw IllegalArgumentException("Index out of range")
    }  
     
    /* add an element to the front of VList */
    fun cons(a: T): VList<T> {        
        if (this.base == null) {
            val v = VList<T>()
            val s = VSeg()
            s.ele = arrayOf<Any?>(a)
            v.base = s
            return v
        }
        if (this.offset == 0) {
            val l2 = this.base!!.ele.size * 2
            val ele = arrayOfNulls<Any>(l2)
            ele[l2 - 1] = a
            val v = VList<T>()
            val s = VSeg()
            s.next = this.base
            s.ele = ele
            v.base = s
            v.offset = l2 - 1 
            return v
        }
        this.offset--
        this.base!!.ele[this.offset] = a
        return this
    }

    /* obtain a new VList beginning at the second element of an old VList */
    fun cdr(): VList<T> {
        if (base == null) throw RuntimeException("cdr invoked on empty VList")
        offset++
        if (offset < base!!.ele.size) return this
        val v = VList<T>()
        v.base = this.base!!.next
        return v
    }

    /* compute the size of the VList */
    val size: Int
        get() {
            if (base == null) return 0
            return base!!.ele.size * 2 - offset - 1
        }

    override fun toString(): String {
        if (base == null) return "[]"
        var r = "[${base!!.ele[offset]}"
        var sg = base
        var sl = base!!.ele.sliceArray(offset + 1..base!!.ele.lastIndex)
        while (true) {
            for (e in sl) r += " $e"
            sg = sg!!.next
            if (sg == null) break
            sl = sg.ele
        }
        return r + "]"
    }

    fun printStructure() {
        println("Offset: $offset")
        var sg = base
        while (sg != null) {
            println(sg.ele.contentToString())
            sg = sg.next
        }
        println()
    }
}

fun main(args: Array<String>) {
    var v = VList<Int>()
    println("Before adding any elements, empty VList: $v")
    v.printStructure()

    for (a in 6 downTo 1) v = v.cons(a)
    println("Demonstrating cons method, 6 elements added: $v")
    v.printStructure()

    v = v.cdr()
    println("Demonstrating cdr method, 1 element removed: $v")
    v.printStructure() 

    println("Demonstrating size property, size = ${v.size}\n")
    println("Demonstrating element access, v[3] = ${v[3]}\n")
 
    v = v.cdr().cdr()
    println("Demonstrating cdr method again, 2 more elements removed: $v")
    v.printStructure()
}
Output:
Before adding any elements, empty VList: []
Offset: 0

Demonstrating cons method, 6 elements added: [1 2 3 4 5 6]
Offset: 1
[null, 1, 2, 3]
[4, 5]
[6]

Demonstrating cdr method, 1 element removed: [2 3 4 5 6]
Offset: 2
[null, 1, 2, 3]
[4, 5]
[6]

Demonstrating size property, size = 5

Demonstrating element access, v[3] = 5

Demonstrating cdr method again, 2 more elements removed: [4 5 6]
Offset: 0
[4, 5]
[6]

Nim

Translation of: Go
type

  VSeg[T] = ref object
    next: VSeg[T]
    elems: seq[T]

  VList[T] = ref object
    base: VSeg[T]
    offset: int


func newVList[T](): VList[T] = new(VList[T])


func `[]`[T](v: VList[T]; k: int): T =
  ## Primary operation 1: locate the kth element.
  if k >= 0:
    var i = k + v.offset
    var sg = v.base
    while not sg.isNil:
      if i < sg.elems.len:
        return sg.elems[i]
      dec i, sg.elems.len
      sg = sg.next
  raise newException(IndexDefect, "index out of range; got " & $k)


func cons[T](v: VList[T]; a: T): VList[T] =
  ## Primary operation 2: add an element to the front of the VList.
  if v.base.isNil:
    return VList[T](base: VSeg[T](elems: @[a]))

  if v.offset == 0:
    let l2 = v.base.elems.len * 2
    var elems = newSeq[T](l2)
    elems[l2 - 1] = a
    return VList[T](base: VSeg[T](next: v.base, elems: move(elems)), offset: l2 - 1)

  dec v.offset
  v.base.elems[v.offset] = a
  result = v


func cdr[T](v: VList[T]): VList[T] =
  ## Primary operation 3: obtain a new array beginning at the second element of an old array.
  if v.base.isNil:
    raise newException(NilAccessDefect, "cdr on empty list")

  if v.offset + 1 < v.base.elems.len:
    inc v.offset
    return v
  result = VList[T](base: v.base.next, offset: 0)


func len[T](v: VList[T]): Natural =
  ## Primary operation 4:  compute the length of the list.
  if v.base.isNil: return 0
  result = v.base.elems.len * 2 - v.offset - 1


func `$`[T](v: VList[T]): string =
  if v.base.isNil: return "[]"
  result = '[' & $v.base.elems[v.offset]
  var sg = v.base
  var sl = v.base.elems[v.offset+1..^1]
  while true:
    for e in sl: result.add ' ' & $e
    sg = sg.next
    if sg.isNil: break
    sl = sg.elems
  result.add ']'


proc printStructure[T](v: VList[T]) =
  echo "offset: ", v.offset
  var sg = v.base
  while not sg.isNil:
    echo "  ", sg.elems
    sg = sg.next
  echo()


when isMainModule:

  var v = newVList[string]()

  echo "Zero value for type.  Empty vList:", v
  v.printStructure()

  for a in countdown('6', '1'): v = v.cons($a)
  echo "Demonstrate cons. Six elements added:", v
  v.printStructure()

  v = v.cdr()
  echo "Demonstrate cdr. One element removed:", v
  v.printStructure()

  echo "Demonstrate length. Length = ", v.len()
  echo()

  echo "Demonstrate element access. v[3] = ", v[3]
  echo()

  v = v.cdr().cdr()
  echo "Show cdr releasing segment. Two elements removed: ", v
  v.printStructure()
Output:
Zero value for type.  Empty vList:[]
offset: 0

Demonstrate cons. Six elements added:[1 2 3 4 5 6]
offset: 1
  @["", "1", "2", "3"]
  @["4", "5"]
  @["6"]

Demonstrate cdr. One element removed:[2 3 4 5 6]
offset: 2
  @["", "1", "2", "3"]
  @["4", "5"]
  @["6"]

Demonstrate length. Length = 5

Demonstrate element access. v[3] = 5

Show cdr releasing segment. Two elements removed: [4 5 6]
offset: 0
  @["4", "5"]
  @["6"]

Objeck

Translation of: Kotlin
class vList<T:Stringify> {
  @base : vSeg<T>;
  @offset : Int;

  New() {}

  New(base : vSeg<T>, offset : Int) {
    @base := base;
    @offset := offset;
  }

  New(base : vSeg<T>) {
    @base := base;
  }

  method : public : GetBase() ~ vSeg<T> {
    return @base;
  }

  method : public : GetOffset() ~ Int {
    return @offset;
  }

  method : public : Cons(a : T) ~ vList<T> {
    if(@base = Nil) {
      return vList->New(vSeg->New(a)<T>)<T>;
    }
    else if(@offset = 0) {
      l2 := @base->GetEle()->Size() * 2;
      ele := T->New[l2];
      ele[l2 - 1] := a;
      return vList->New(vSeg->New(@base, ele)<T>, l2 - 1)<T>;
    }
    else {
      @offset -= 1;
      ele := @base->GetEle();
      ele[@offset] := a;
      return @self;
    };
  }

  method : public : Cdr() ~ vList<T> {
    if(@base = Nil) {
      return Nil;
    };

    @offset += 1;
    if(@offset < @base->GetEle()->Size()) {
      return @self;
    }
    else {
      return vList->New(@base->GetNext(), 0)<T>;
    };
  }

  method : public : Index(i : Int) ~ T {
    if(i >= 0) {
      i += @offset;
      for(sg := @base; sg <> Nil; sg := sg->GetNext();) {
        ele := sg->GetEle();
        if(i < ele->Size()) {
          return ele[i];
        };
        
        i -= ele->Size();
      };
    };

    return Nil;
  }

  method : public : Size() ~ Int {
    if(@base = Nil) {
      return 0;
    };

    return @base->GetEle()->Size() * 2 - @offset - 1;
  }

  method : public : ToString() ~ String {
    if(@base = Nil) {
      return "[]";
    };

    r := "[";
    ele := @base->GetEle();
    r += ele[@offset]->ToString();
    r += ' ';

    sg := @base;
    offset := @offset + 1;
    
    done := false;
    while(<>done) {
      for(i := offset; i < ele->Size(); i += 1;) {
        r += ele[i]->ToString();
        r += ' ';
      };

      sg := sg->GetNext();
      if(sg <> Nil) {
        ele := sg->GetEle();
        offset := 0;
      }
      else {
        done := true;
      };
    };
    r += ']';

    return r;
  }

  method : public : PrintStructure() ~ Nil {
    offset := @offset;
    "  offset: {$offset}"->PrintLine();
    
    for(sg := @base; sg <> Nil; sg := sg->GetNext();) {
      values := sg->GetEle();
      "  ["->Print();
      each(i : values) {
        value := values[i];
        if(value <> Nil) {
          "{$value}"->Print();
        }
        else {
          "{Nil}"->Print();
        };

        if(i + 1 < values->Size()) {
          ", "->Print();
        };
      };
      "]"->PrintLine();
    };
    ""->PrintLine();
  }
}
 
class vSeg<T:Stringify> {
  @next : vSeg<T>;
  @ele : T[];

  New(next : vSeg<T>, ele : T[]) {
    @next := next;
    @ele := ele;
  }

  New(s : T) {
    @ele := T->New[1];
    @ele[0] := s;
  }

  method : public : GetNext() ~ vSeg<T> {
    return @next;
  }

  method : public : GetEle() ~ T[] {
    return @ele;
  }
}

class Test {
  function : Main(args : String[]) ~ Nil {
    v := vList->New()<String>;
    "Zero value for type. empty vList: {$v}"->PrintLine();
    v->PrintStructure();

    for(a := '6'; a >= '1'; a -=1;) {
      v := v->Cons("{$a}")<String>;
    };
    
    "Demonstrate cons. 6 elements added: {$v}"->PrintLine();
    v->PrintStructure();

    v := v->Cdr()<String>;
    Runtime->Assert(v <> Nil);
    "Demonstrate cdr. 1 element removed: {$v}"->PrintLine();
    v->PrintStructure();

    size := v->Size();
    "Demonstrating size property, size = {$size}"->PrintLine();

    e := v->Index(3);
    Runtime->Assert(e <> Nil);
    "Demonstrate element access. v[3] = {$e}"->PrintLine();

    v := v->Cdr()->Cdr()<String>;
    Runtime->Assert(v <> Nil);
    "Demonstrate cdr. 2 elements removed: {$v}"->PrintLine();
    v->PrintStructure();
  }
}
Output:
Zero value for type. empty vList: []
  offset: 0

Demonstrate cons. 6 elements added: [1 2 3 4 5 6 ]
  offset: 1
  [{Nil}, 1, 2, 3]
  [4, 5]
  [6]

Demonstrate cdr. 1 element removed: [2 3 4 5 6 ]
  offset: 2
  [{Nil}, 1, 2, 3]
  [4, 5]
  [6]

Demonstrating size property, size = 5
Demonstrate element access. v[3] = 5
Demonstrate cdr. 2 elements removed: [4 5 6 ]
  offset: 0
  [4, 5]
  [6]

ooRexx

The ooRexx queue class is a vlist implementation. Here are some examples of usage:

-- show how to use the queue class
q = .queue~of(1, 2, 3, 4)

-- show indexed access to item
say q[4]

-- update an item
q[2] = "Fred"

-- show update and that other indexes are unchanged
say q[2] q[4]

-- push an item on the front and show the change in positions
q~push("Mike")
say q[1] q[2] q[4]

-- pop an item and show the change again
q~pull
say q[1] q[2] q[4]
Output:
4
Fred 4
Mike 1 3
1 Fred 4

Phix

with javascript_semantics
enum OFFSET,     -- (first spare slot [0=none])
     SEGMENTS
 
function new_vlist()
    return {0,{}} -- offset of 0, no segments
end function 
 
function get_vlist(sequence v, integer k)
-- locate kth element
    if k>0 then
        k += v[OFFSET]
        integer sg = 1
        while sg<=length(v[SEGMENTS]) do
            sequence vsg = v[SEGMENTS][sg]
            if k<= length(vsg) then return vsg[k] end if
            k -= length(vsg)
            sg += 1
        end while
    end if
    throw("index out of range")
end function
 
function cons(sequence v, object a)
-- add an element to the front of v
    if length(v[SEGMENTS])=0 then
        return {0,{{a}}}
    end if
    integer offset = v[OFFSET]
    if offset=0 then
        offset = length(v[SEGMENTS][1])*2
        v[SEGMENTS] = prepend(v[SEGMENTS],repeat(0,offset))
    end if
    v[SEGMENTS][1][offset] = a
    v[OFFSET] = offset-1
    return v
end function
 
function cdr(sequence v)
-- remove first element of v
    if length(v[SEGMENTS])=0 then
        throw("cdr invoked on empty VList")
    end if
    integer offset = v[OFFSET]+1
    if offset>length(v[SEGMENTS][1]) then
        v[SEGMENTS] = v[SEGMENTS][2..$]
        v[OFFSET] = 1
    else
        v[OFFSET] = offset
    end if
    return v
end function
 
function vlist_size(sequence v)
-- compute the size of v
    if length(v[SEGMENTS])=0 then return 0 end if
    return length(v[SEGMENTS][1])*2 -v[OFFSET] -1 
end function
 
function sprint_vlist(sequence v) 
    return sprint(flatten(v[SEGMENTS])[v[OFFSET]+1..$])
end function
 
procedure print_vlist_structure(sequence v)
    printf(1,"Offset: %d\n",v[OFFSET])
    pp(v[SEGMENTS],{pp_Nest,1})
end procedure
 
procedure main()
    sequence v = new_vlist()
    printf(1,"Before adding any elements, empty VList: %s\n",{sprint_vlist(v)})
    print_vlist_structure(v)
 
    for a=6 to 1 by -1 do v = cons(v,a) end for
    printf(1,"Demonstrating cons method, 6 elements added: %s\n",{sprint_vlist(v)})
    print_vlist_structure(v)
 
    v = cdr(v)
    printf(1,"Demonstrating cdr method, 1 element removed: %s\n",{sprint_vlist(v)})
    print_vlist_structure(v)
 
    printf(1,"Demonstrating size property, size = %d\n",vlist_size(v))
    -- (note this is 1-based indexing)
    printf(1,"Demonstrating element access, v[3] = %d\n",get_vlist(v,3))
 
    v = cdr(cdr(cdr(v)))
    printf(1,"Demonstrating cdr method again, 3 more elements removed: %s, size = %d\n",
            {sprint_vlist(v),vlist_size(v)})
    print_vlist_structure(v)
 
    for a=7 to 9 do v = cons(v,a) end for -- (this time not by -1; {9 8 7 5 6} is expected)
    printf(1,"Demonstrating cons method, 3 more elements added: %s, size = %d\n",
            {sprint_vlist(v),vlist_size(v)})
    print_vlist_structure(v)
 
end procedure
main()
Output:
Before adding any elements, empty VList: ""
Offset: 0
{}
Demonstrating cons method, 6 elements added: {1,2,3,4,5,6}
Offset: 1
{{0,1,2,3},
 {4,5},
 {6}}
Demonstrating cdr method, 1 element removed: {2,3,4,5,6}
Offset: 2
{{0,1,2,3},
 {4,5},
 {6}}
Demonstrating size property, size = 5
Demonstrating element access, v[3] = 4
Demonstrating cdr method again, 3 more elements removed: {5,6}, size = 2
Offset: 1
{{4,5},
 {6}}
Demonstrating cons method, 3 more elements added: {9,8,7,5,6}, size = 5
Offset: 2
{{0,0,9,8},
 {7,5},
 {6}}

Racket

See https://github.com/takikawa/tr-pfds/blob/master/pfds/vlist.rkt for an implementation of VLists.

Raku

(formerly Perl 6)

Translation of: Go
Translation of: Kotlin
class vList {

   subset vEle of Any; # or Str

   class vSeg {
      has      $.next is rw is default(Nil) ;
      has vEle @.ele  is rw ;
   }

   has vSeg $.base   is rw is default(vSeg.new(ele=>()));
   has Int  $.offset is rw is default(0) ;

   method Index(Int $i is copy --> vEle) { # method to locate the kth element
      if $i0 {
         loop ( $i += self.offset, $_ = self.base; $_.defined; $_ := $_.next) {
            ($i < my $len = .ele.elems) ?? return .ele[$i] !! $i -= $len
         }
      }
      die "index out of range"
   }

   method cons(vEle \a --> vList) { # method to add an element to the front
      if not self.base.ele.Bool {   # probably faster than .elems ?
         self.base.ele.push: a ;
         return self;
      } elsif self.offset == 0 {
         my \L2offset = (self.base.ele.elems * 2) - 1 ;
         my \s = vSeg.new(next => self.base, ele => flat Nil xx L2offset, a);
         return vList.new(base => s, offset => L2offset )
      }
      self.base.ele[--self.offset] = a;
      return self
   }

   # obtain a new array beginning at the second element of an old array
   method cdr(--> vList) {
      die "cdr on empty vList" unless self.base.defined;
      return self if ++self.offset < self.base.ele.elems;
      return vList.new(base => self.base.next)
   }

   method Length(--> Int) { # method to  compute the length of the list
      return 0 unless self.base.defined;
      return self.base.ele.elems*2 - self.offset - 1
   }

   method gist { # (mis)used to create output similar to Go/Kotlin
      return '[]' unless self.base.ele.Bool;
      my @sl = self.base.ele[self.offset .. *];
      loop ($_=self.base.next; $_.defined; $_:=$_.next) { @sl.append: .ele }
      return  "[" ~ @sl.Str ~ "]"
   }

   method printStructure {  # One more method for demonstration purposes
      say "offset: ", self.offset;
      loop ( $_ = self.base; $_.defined ; $_ := $_.next ) { .ele.say }
   }
}

my $v := vList.new;
say "zero value for type.  empty vList: ", $v;
$v.printStructure;
say " ";
$v := $v.cons($_.Str) for 61;
say "demonstrate cons. 6 elements added: ", $v;
$v.printStructure;
say " ";
$v := $v.cdr;
say "demonstrate cdr. 1 element removed: ", $v;
$v.printStructure;
say " ";
say "demonstrate length. length = ", $v.Length;
say " ";
say "demonstrate element access. v[3] = ", $v.Index(3) ;
say " ";
$v := $v.cdr.cdr;
say "show cdr releasing segment. 2 elements removed: ", $v;
$v.printStructure;
Output:
zero value for type.  empty vList: []
offset: 0
[]

demonstrate cons. 6 elements added: [1 2 3 4 5 6]
offset: 1
[(vEle) 1 2 3]
[4 5]
[6]

demonstrate cdr. 1 element removed: [2 3 4 5 6]
offset: 2
[(vEle) 1 2 3]
[4 5]
[6]

demonstrate length. length = 5

demonstrate element access. v[3] = 5

show cdr releasing segment. 2 elements removed: [4 5 6]
offset: 0
[4 5]
[6]

REXX

This classic REXX version uses (mostly) the same "input" and operations as the ooRexx version, except that the (stack) queue isn't changed or used.

 ╔════════════════════════════════════════════════════════════════════╗
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │                           │  (no args)  ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ returns the number of items in the VList.                          ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  0,  a b c d  ∙∙∙         │             ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ inserts the specified items(s) to the  front  of the VList.        ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  999999999,  a b c d ∙∙∙  │             ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ appends the specified items(s) to the  end  of the VList.          ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  10,  a b c d  ∙∙∙        │             ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ sets the tenth item to the items(s) specified.   If there're less  ║
 ║ than  10  items in the VList,  the specified item(s) are appended  ║
 ║ to the  end  of the VList.                                         ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  17                       │             ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ returns the  seventeenth  item in the VList.                       ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  ,                        │  (a comma)  ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ returns  all  the items in the VList.                              ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  -11                      │             ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ deletes the  eleventh  item in the VList.                          ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  63.1,  a b c d  ∙∙∙      │             ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ inserts the specified items after the  63rd  item.  If there's less║
 ║ then  63  items in the VList,  the specified items() are appended  ║
 ║ to the  end  of the VList.  Any non-zero decimal fraction may be   ║
 ║ used.       I.E.:     63.01     63.5     63.63     63.9            ║
 ╚════════════════════════════════════════════════════════════════════╝
/*REXX program demonstrates  VList  operations:   add,  update,  delete, insert,  show. */
                                                 /*could use instead:     q  =  1 2 3 4 */
call  q  0, 1 2 3 4                              /*populate the list with values 1 ── ►4*/
say q(4)                                         /*show the indexed access to an item.  */

call q  2, 'Fred'                                /*update  (or add)  the second item.   */
say q(2) q(4)                                    /*show second and fourth items in list.*/
                                                 /*zeroth item is inserted in the front.*/
call q  0, 'Mike'                                /*insert item in front of the list.    */
say q(1) q(2) q(4)                               /*show first, second, and fourth items.*/
                                                 /*any  negative number  is deleted.    */
call q  -1                                       /*delete the first item in the list.   */
say q(1) q(2) q(4)                               /*show the  1st,  2nd,  and  4th items.*/
                                                 /*Fractional number inserts an item.   */
call q  3.5, '3½'                                /*insert the item after the third item.*/
say q ,                                          /*show all the  VList  items.          */
                                                 /*Put on a dog and pony show.          */
say 'number of items in Vlist:' q()              /*show and tell time for the  Vlist.   */
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
q: parse arg n 1 na 1 ni,!;   w=words(q);   $=             /*obtain arguments;  # items.*/
   if symbol('Q')=='LIT' then q=                           /*var Q may not be defined.  */
   if arg()==0        then return words(q)                 /*return the VList item count*/
   if arg(1, 'O')     then return q                        /*return the whole shebang.  */
   if arg()==1 & n>0  then return word(q,n)                /*1 positive arg?  Return it.*/
   if n==0            then do;  q=! q;  return q;  end     /*insert in front of the list*/
   if n> w            then do;  q=q !;  return q;  end     /*add it to  end.  "  "    " */
   na=abs(n)                                               /*we might need use of  ABS. */
   if \datatype(ni, 'W') & ni>0  then ni=trunc(na)         /*Is this an insert>?  TRUNC.*/
                                 else ni=0                 /*... No?  Then a plain Jane.*/
          do j=1 for w                                     /* [↓]  rebuild the  Vlist.  */
          if j==na  then do; if na==n then $=$ !;  end     /*replace the item in list.  */
                    else $=$ word(q, j)                    /*an easy-peasy (re-)build.  */
          if j==ni  then $=$ !                             /*handle the  "insert".      */
          end   /*j*/
   q=space($);           return q                          /*elide superfluous blanks.  */
output   when using the default input:
4
Fred 4
Mike 1 3
1 Fred 4
1 Fred 3 3½ 4
number of items in Vlist: 5

Scala

Library: Scala
Two of Scala's 2.8 immutable data structures are vectors and hash tries, represented as 32-ary trees.

These were originally designed by Phil Bagwell, who was working with my team at EPFL, then adopted for Clojure, and now finally adopted for Scala 2.8.

The Scala implementation shares a common root with the Clojure implementation, but is certainly not a port of it.

A quote of Martin Odersky, his co-worker Phil Bagwell† invented the VList.

object VList extends App {

  val emptyVlist1 = Vector.empty[Int]
  val emptyVlist2 = Vector[Int]()
  val emptyVlist3 = Vector()

  val addedVlist1 = Vector(1, 2) :+ 6 :+ 10 :+ 12 :+ 42

  assert((addedVlist1, addedVlist1.head) == (Vector(1, 2, 6, 10, 12, 42), 1), "Header or VList not OK")

  val addedVlist2 = addedVlist1.head +: addedVlist1.tail.drop(1)
  assert((addedVlist2, addedVlist2.head) == (Vector(1, 6, 10, 12, 42), 1), "First CDR not deleted.")

  assert(addedVlist1.size == 6)

  assert(addedVlist1(3) == 10, "Wrong element accesed.")
  println("Successfully completed without errors.")
}

Wren

Translation of: Kotlin
class VSeg_ {
    construct new() {
        _next = null
        _ele  = []
    }

    next       { _next }
    next=(n)   { _next = n}
    ele        { _ele }
    ele=(e)    { _ele = e }
}

class VList {
    construct new() {
        _base = null
        _offset = 0
    }

    base       { _base }
    base=(b)   { _base = b}
    offset     { _offset }
    offset=(o) { _offset = o }

    /* locate kth element */
    [k] {
        var i = k
        if (i >= 0) {
            i = i + _offset
            var sg = _base
            while (sg) {
                if (i < sg.ele.count) return sg.ele[i]
                i = i - sg.ele.count
                sg = sg.next
            }
        }
        Fiber.abort("Index out of range.")
    }

    /* add an element to the front of VList */
    cons(a) {
        if (!_base) {
            var v = VList.new()
            var s = VSeg_.new()
            s.ele = [a]
            v.base = s
            return v
        }
        if (_offset == 0) {
            var l2 = _base.ele.count * 2
            var ele = List.filled(l2, null)
            ele[l2 - 1] = a
            var v = VList.new()
            var s = VSeg_.new()
            s.next = _base
            s.ele = ele
            v.base = s
            v.offset = l2 - 1
            return v
        }
        _offset = _offset - 1
        _base.ele[_offset] = a
        return this
    }

    /* obtain a new VList beginning at the second element of an old VList */
    cdr() {
        if (!_base) Fiber.abort("cdr invoked on empty VList")
        _offset = _offset + 1
        if (offset < _base.ele.count) return this
        var v = VList.new()
        v.base = _base.next
        return v
    }

     /* compute the size of the VList */
    size {
        if (!_base) return 0
        return _base.ele.count * 2 - _offset - 1
    }

    toString {
        if (!_base) return "[]"
        var r = "[%(_base.ele[_offset])"
        var sg = _base
        var sl = _base.ele[_offset + 1..-1]
        while (true) {
            for (e in sl) r = r + " %(e)"
            sg = sg.next
            if (!sg) break
            sl = sg.ele
        }
        return r + "]"
    }

    printStructure() {
        System.print("Offset: %(_offset)")
        var sg = _base
        while (sg) {
            System.print(sg.ele)
            sg = sg.next
        }
        System.print()
    }
}

var v = VList.new()
System.print("Before adding any elements, empty VList: %(v)")
v.printStructure()

for (a in 6..1) v = v.cons(a)
System.print("Demonstrating cons method, 6 elements added: %(v)")
v.printStructure()

v = v.cdr()
System.print("Demonstrating cdr method, 1 element removed: %(v)")
v.printStructure()

System.print("Demonstrating size property, size = %(v.size)\n")
System.print("Demonstrating element access, v[3] = %(v[3])\n")

v = v.cdr().cdr()
System.print("Demonstrating cdr method again, 2 more elements removed: %(v)")
v.printStructure()
Output:
Before adding any elements, empty VList: []
Offset: 0

Demonstrating cons method, 6 elements added: [1 2 3 4 5 6]
Offset: 1
[null, 1, 2, 3]
[4, 5]
[6]

Demonstrating cdr method, 1 element removed: [2 3 4 5 6]
Offset: 2
[null, 1, 2, 3]
[4, 5]
[6]

Demonstrating size property, size = 5

Demonstrating element access, v[3] = 5

Demonstrating cdr method again, 2 more elements removed: [4 5 6]
Offset: 0
[4, 5]
[6]