VList: Difference between revisions

</pre>

=={{header|Phix}}==

<lang Phix>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()</lang>

{{out}}

<pre>

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