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

This example is incomplete. Please show how to use a VList in C++. Please ensure that it meets all task requirements and remove this message.

OOTL implements a VList, see An Implemenation of the vlist data structure, http://www.ootl.org/doc/vlist.html, retrieved 19 January 2011 .

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"]