VList

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.

C

<lang c>#include <stdio.h>

1. 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++

Translation of: Go

<lang c>

1. include <iostream>
2. include <vector>
3. include <forward_list>
4. 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

Translation of: C

<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

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. <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>