SyntaxBomb - Indie Coders

Languages & Coding => Blitz Code Archives => Algorithms => Topic started by: BlitzBot on June 29, 2017, 00:28:42

Title: [bb] Container: vector by octothorpe [ 1+ years ago ]
Post by: BlitzBot on June 29, 2017, 00:28:42
Title : Container: vector
Author : octothorpe
Posted : 1+ years ago

Description : Vector containers have nothing to do with spatial vectors!

This library makes it painless to add many independant vector containers for many different types of objects. This is done by storing Handle()s to your objects. Each container should hold objects of only one type.  For more information on containers, an example of how to use them, and a tutorial, <a href="../Community/posts8333.html?topic=53352" target="_blank">click here</a>.

A vector is essentially the same as an array, but it can also work like a FIFO stack.

But Blitz already has arrays!  Sure, it has two kinds of arrays: basic arrays (Dim a(10)) and type arrays (Field x[10]).  The first kind is global and cannot be passed to functions, the second is limited to a static number of elements.  Vectors implemented with this library suffer neither of these limitations.

Additionally, you can use your vector as a stack if you use the optional push() and pop() functions.

For an example of how to use this library, scroll down to the test() function at the very bottom.  This code will run standalone if you uncomment the line at the top which runs the test code.
Please post bugs or feature requests in comments.
Fundamentals

   vector_new.vectorC(elements% = 0)
      - create a new vector
   vector_destroy(our_vector.vectorC)
      - delete a vector and all of its elements

Standard Operations

   vector_set(our_vector.vectorC, index%, value)
      - set value at specified index
   vector_get(our_vector.vectorC, index%)
      - get value at specified index
   vector_resize(our_vector.vectorC, elements%)
      - set the size of the vector
   vector_count(our_vector.vectorC)
      - return the number of elements in the vector

Stack Operations

   vector_push(our_vector.vectorC, value)
      - add a new element to the end of the vector
   vector_pop(our_vector.vectorC)
      - remove an element from the end of the vector, returning its value
   vector_alloc(our_vector.vectorC, elements%)
      - preallocate a bunch of space for push() operations

Slow Operations

   vector_remove_element(our_vector.vectorC, index%)
      - remove an element from anywhere in a vector, returning its value
   vector_insert_before(our_vector.vectorC, index%, value)
      - add a new element before an existing one
   vector_insert_after(our_vector.vectorC, index%, value)
      - add a new element after an existing one
   vector_shift(our_vector.vectorC)
      - remove an element from the front of the vector, returning its value
   vector_unshift(our_vector.vectorC, value)
      - add a new element to the front of the vector

Iterators

; for item.type = each our_vector
it.vectorC_iter = vector_iterator_begin(our_vector)
while vector_iterator_next(it)
item.type = object.type(vector_iterator_get(it))
; do stuff with item
wend


   vector_iterator_begin_reverse.vectorC_iter(our_vector.vectorC)
      - create a new iterator for traversing the list backwards

---

The Code [/i]

Code :
Code (blitzbasic) Select
;vector_test()

; ------------------------------------------------------------------------------
;= TO DO
; ------------------------------------------------------------------------------
; iterator sanity checking (try to catch problems which might be caused by deleting elements while iterating)

; ------------------------------------------------------------------------------
;= CHANGE LOG
; ------------------------------------------------------------------------------
; 12/11/2005 - iterator sample usage for quick copying and pasting
; 12/11/2005 - negative index values now represent elements in reverse order,
;              added remove_element(), insert_element_*(), shift(), unshift(),
;              and iterators
; 12/11/2005 - calling new() is now required
; 06/11/2005 - new() for forwards compatibility
; 03/11/2005 - renamed class from vectorType

; ------------------------------------------------------------------------------
;= CONSTANTS
; ------------------------------------------------------------------------------
const VECTORS_EXPAND_BY = 20
; instead of resizing our bank every push() operation, grab some extra space

; ------------------------------------------------------------------------------
;= TYPES
; ------------------------------------------------------------------------------
type vectorC
field last_element%                   ; size of the container - 1
field elements_allocated%             ; size of the bank (not in bytes)
field bank
end type

type vectorC_iter
field vector.vectorC
field forwards                        ; bool to keep track of which direction we're going
field current_index%
end type

; ------------------------------------------------------------------------------
;= FUNDAMENTAL
; ------------------------------------------------------------------------------

; ------------------------------------------------------------------------------
function vector_new.vectorC(elements% = 0)
; create a new vector

our_vector.vectorC = new vectorC
our_vectorank = createbank(0)
vector_resize(our_vector, elements)   ; also sets last_element to elements-1
return our_vector
end function

; ------------------------------------------------------------------------------
function vector_destroy(our_vector.vectorC)
; delete a vector and all of its elements

freebank(our_vectorank)
delete our_vector
end function

; ------------------------------------------------------------------------------
function vector_set(our_vector.vectorC, index%, value)
; set value at specified index

if our_vector = null then runtimeerror("not a valid vectorC: null")
if (index < 0) then index = our_vectorlast_element+1 + index                   ; negative indexes reference elements in reverse order
if (index < 0 or index > our_vectorlast_element) then runtimeerror("element out of range: "+index)
pokeint(our_vectorank, 4 * index, value)
end function

; ------------------------------------------------------------------------------
function vector_get(our_vector.vectorC, index%)
; get value at specified index

if our_vector = null then runtimeerror("not a valid vectorC: null")
if (index < 0) then index = our_vectorlast_element+1 + index                   ; negative indexes reference elements in reverse order
if (index < 0 or index > our_vectorlast_element) then runtimeerror("element out of range: "+index)
return peekint(our_vectorank, 4 * index)
end function

; ------------------------------------------------------------------------------
function vector_resize(our_vector.vectorC, elements%)
; set the size of the vector

if our_vector = null then runtimeerror("not a valid vectorC: null")
resizebank(our_vectorank, 4 * elements)
our_vectorelements_allocated = elements
our_vectorlast_element = elements - 1
end function

; ------------------------------------------------------------------------------
function vector_count(our_vector.vectorC)
; return the number of elements in the vector

if our_vector = null then runtimeerror("not a valid vectorC: null")
return our_vectorlast_element + 1
end function

; ------------------------------------------------------------------------------
;= STACK OPERATIONS
; ------------------------------------------------------------------------------
function vector_push(our_vector.vectorC, value)
; add a new element to the end of the vector

if our_vector = null then runtimeerror("not a valid vectorC: null")
; allocate more space if required
if our_vectorelements_allocated-1 = our_vectorlast_element then
our_vectorelements_allocated = our_vectorelements_allocated + VECTORS_EXPAND_BY
resizebank(our_vectorank, 4 * our_vectorelements_allocated)
endif
; store the new value
our_vectorlast_element = our_vectorlast_element + 1
pokeint(our_vectorank, 4 * our_vectorlast_element, value)
end function

; ------------------------------------------------------------------------------
function vector_pop(our_vector.vectorC)
; remove an element from the end of the vector

if our_vector = null then runtimeerror("not a valid vectorC: null")
if our_vectorlast_element = -1 then return 0
our_vectorlast_element = our_vectorlast_element - 1
return peekint(our_vectorank, 4 * (our_vectorlast_element + 1))
end function

; ------------------------------------------------------------------------------
function vector_alloc(our_vector.vectorC, elements%)
; preallocate a bunch of space for push() operations

if our_vector = null then runtimeerror("not a valid vectorC: null")
if elements < our_vectorlast_element + 1 then runtimeerror("cannot alloc less space than is currently being used")
our_vectorelements_allocated = elements
resizebank(our_vectorank, 4 * our_vectorelements_allocated)
end function

; ------------------------------------------------------------------------------
;= SLOW OPERATIONS
; ------------------------------------------------------------------------------
function vector_remove_element(our_vector.vectorC, index%)
; remove an element from anywhere in a vector

if our_vector = null then runtimeerror("not a valid vectorC: null")
if (index < 0) then index = our_vectorlast_element+1 + index                   ; negative indexes reference elements in reverse order
if (index < 0 or index > our_vectorlast_element) then runtimeerror("element out of range: "+index)
value = peekint(our_vectorank, 4 * index)
our_vectorlast_element = our_vectorlast_element - 1
; move elements backward to cover our hole
copybank(our_vectorank, 4*(index+1), our_vectorank, 4*index, 4*(our_vectorlast_element+1 - index))
return value
end function

; ------------------------------------------------------------------------------
function vector_insert_before(our_vector.vectorC, index%, value)
; add a new element before an existing one
; note that we allow a reference index of our_vectorlast_element+1 (which is dispatched to vector_push() anyways)


if our_vector = null then runtimeerror("not a valid vectorC: null")
if (index < 0) then index = our_vectorlast_element+1 + index                   ; negative indexes reference elements in reverse order
if index = our_vectorlast_element+1 then return vector_push(our_vector, value) ; much faster alternative!
if (index < 0 or index > our_vectorlast_element) then runtimeerror("element out of range: "+index)
; allocate more space if required
if our_vectorelements_allocated-1 = our_vectorlast_element then
our_vectorelements_allocated = our_vectorelements_allocated + VECTORS_EXPAND_BY
resizebank(our_vectorank, 4 * our_vectorelements_allocated)
endif
; move elements forward
copybank(our_vectorank, 4*(index), our_vectorank, 4*(index+1), 4*(our_vectorlast_element+1 - index))
our_vectorlast_element = our_vectorlast_element + 1
; set our new value
pokeint(our_vectorank, 4 * index, value)
end function

; ------------------------------------------------------------------------------
function vector_insert_after(our_vector.vectorC, index%, value)
; add a new element after an existing one
if (index < 0) then index = our_vectorlast_element+1 + index                   ; negative indexes reference elements in reverse order
return vector_insert_before(our_vector, index+1, value)
end function

; ------------------------------------------------------------------------------
function vector_shift(our_vector.vectorC)
; add a new element after an existing one
return vector_remove_element(our_vector, 0)
end function

; ------------------------------------------------------------------------------
function vector_unshift(our_vector.vectorC, value)
; add a new element to the front of the vector
vector_insert_before(our_vector, 0, value)
end function

; ------------------------------------------------------------------------------
;= ITERATORS
; ------------------------------------------------------------------------------

; sample usage

; ; for item.type = each vector
; it.vectorC_iter = vector_iterator_begin(vector)
; while vector_iterator_next(it)
; item.type = object.type(vector_iterator_get(it))
; wend


; ------------------------------------------------------------------------------
function vector_iterator_begin.vectorC_iter(our_vector.vectorC)
; create a new iterator for traversing the vector forwards

it.vectorC_iter = new vectorC_iter
if our_vector <> null then
itvector = our_vector
itforwards = true
itcurrent_index = 0-1
endif
return it
end function

; ------------------------------------------------------------------------------
function vector_iterator_begin_reverse.vectorC_iter(our_vector.vectorC)
; create a new iterator for traversing the vector backwards

it.vectorC_iter = new vectorC_iter
if our_vector <> null then
itvector = our_vector
itforwards = false
itcurrent_index = our_vectorlast_element+1
endif
return it
end function

; ------------------------------------------------------------------------------
function vector_iterator_next(it.vectorC_iter)
; advance the iterator to the next element in the vector

; drop out immediately if this iterator is void
if itvector = null then return false

if itforwards = true then
itcurrent_index = itcurrent_index + 1
if itcurrent_index > itvectorlast_element then delete it : return false
else
itcurrent_index = itcurrent_index - 1
if itcurrent_index < 0 then delete it : return false
endif
return true
end function

; ------------------------------------------------------------------------------
function vector_iterator_get(it.vectorC_iter)
; return the value of the element the iterator is currently on

return peekint(itvectorank, 4 * itcurrent_index)
end function

; ------------------------------------------------------------------------------
;= TESTING
; ------------------------------------------------------------------------------
function vector_test()
print "vector_test()"

sample_vector.vectorC = vector_new(2)

vector_set(sample_vector, 0, 123)
vector_set(sample_vector, 1, 456)
vector_push(sample_vector, 789)
vector_unshift(sample_vector, 321)
vector_insert_after(sample_vector, -1, -100)

it.vectorC_iter = vector_iterator_begin(sample_vector)
while vector_iterator_next(it)
value = vector_iterator_get(it)
print value
wend


print "press any key to exit..."
waitkey
end

end function


Comments : none...