VList
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.
Data Structure
This illustrates a data structure, a means of storing data within a program.
| 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) |
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
<lang gwbasic> 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</lang>
- 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
<lang 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; }</lang>
C++
<lang c>
- 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;
} </lang>
- 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 <lang oberon2> 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. </lang> Interface extracted from implementation: <lang oberon2> 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.</lang> Module that uses previous module: <lang oberon2> 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. </lang> 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
<lang d>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;
}</lang>
- 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
Go
<lang 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()
}</lang>
- 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):
<lang J>coclass 'vlist'
off=: 0 lastsz=: 1 (current=: 'b1')=: 0
size=: Template: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
}}</lang>
Example use:
<lang J> 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</lang>
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
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.
<lang ruby>""" 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 = pop!(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()
</lang>
- 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
<lang scala>// 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()
}</lang>
- 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
<lang Nim>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()</lang>
- 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
<lang objeck>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();
}
}</lang>
- 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: <lang ooRexx> -- 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]
</lang>
- 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)
<lang perl6>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 $i ≥ 0 {
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 6 … 1; 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;</lang>
- 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 ║ ╚════════════════════════════════════════════════════════════════════╝
<lang rexx>/*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. */</lang>
- 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
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. <lang Scala>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.")
}</lang>
Wren
<lang ecmascript>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()</lang>
- 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]