VList
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) |
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.
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>
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 ]
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"]
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
Racket
See https://github.com/takikawa/tr-pfds/blob/master/pfds/vlist.rkt for an implementation of VLists.
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. <lang rexx>/*REXX pgm demonstrates VList operations: add/update/delete/insert/show.*/ /*╔════════════════════════════════════════════════════════════════════╗
║ ║ ║ ┌────────────┬───────────────────────────┐ ║ ║ │ 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 ║ ╚════════════════════════════════════════════════════════════════════╝*/ /*could use: q = 1 2 3 4 */
call q 0, 1 2 3 4 /*populate the list with 1──►4 */ say q(4) /*show indexed access to an item.*/
call q 2, 'Fred' /*update (or add) the 2nd item. */ say q(2) q(4) /*show 2nd and 4th items in list.*/
/*0th item is inserted in front. */
call q 0, 'Mike' /*insert item in front of list. */ say q(1) q(2) q(4) /*show 1st, 2nd, and 4th items. */
/*any negative number is deleted.*/
call q -1 /*delete the first item in list. */ say q(1) q(2) q(4) /*show 1st, 2nd, and 4th items. */
/*Fractional # inserts an item. */
call q 3.5, '3½' /*insert item after the 3rd item.*/ say q , /*show all VList items. */
/*Put on a dog and pony show. */
say 'number of items in Vlist:' q() /*show and tell time for Vlist. */ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────Q subroutine────────────────────────*/ q: parse arg n 1 na 1 ni,!; w=words(q); $= /*get args, 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*/ if n> w then do; q=q !; return q; end /*add it to end. */ na=abs(n) /*might need ABS.*/ if \datatype(ni,'W') & ni>0 then ni=trunc(na) /*an insert. */
else ni=0 /*plain Jane. */ do j=1 for w /*rebuild Vlist. */ if j==na then do; if na==n then $=$ !; end /*replace item. */ else $=$ word(q,j) /*easy-peasy bld.*/ if j==ni then $=$ ! /*handle insert. */ end /*j*/
q=space($); return q /*purify, return.*/</lang>
- Output:
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>