March 05, 2021, 07:25:42 AM

Author Topic: [bb] Container: vector by octothorpe [ 1+ years ago ]  (Read 455 times)

Offline BlitzBot

[bb] Container: vector by octothorpe [ 1+ years ago ]
« on: June 29, 2017, 12:28:42 AM »
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[/url].

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

Code: [Select]
; 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
  1. ;vector_test()
  2.  
  3. ; ------------------------------------------------------------------------------
  4. ;= TO DO
  5. ; ------------------------------------------------------------------------------
  6. ; iterator sanity checking (try to catch problems which might be caused by deleting elements while iterating)
  7.  
  8. ; ------------------------------------------------------------------------------
  9. ;= CHANGE LOG
  10. ; ------------------------------------------------------------------------------
  11. ; 12/11/2005 - iterator sample usage for quick copying and pasting
  12. ; 12/11/2005 - negative index values now represent elements in reverse order,
  13. ;              added remove_element(), insert_element_*(), shift(), unshift(),
  14. ;              and iterators
  15. ; 12/11/2005 - calling new() is now required
  16. ; 06/11/2005 - new() for forwards compatibility
  17. ; 03/11/2005 - renamed class from vectorType
  18.  
  19. ; ------------------------------------------------------------------------------
  20. ;= CONSTANTS
  21. ; ------------------------------------------------------------------------------
  22. const VECTORS_EXPAND_BY = 20
  23.         ; instead of resizing our bank every push() operation, grab some extra space
  24.  
  25. ; ------------------------------------------------------------------------------
  26. ;= TYPES
  27. ; ------------------------------------------------------------------------------
  28. type vectorC
  29.         field last_element%                   ; size of the container - 1
  30.         field elements_allocated%             ; size of the bank (not in bytes)
  31.         field bank
  32. end type
  33.  
  34. type vectorC_iter
  35.         field vector.vectorC
  36.         field forwards                        ; bool to keep track of which direction we're going
  37.         field current_index%
  38. end type
  39.  
  40. ; ------------------------------------------------------------------------------
  41. ;= FUNDAMENTAL
  42. ; ------------------------------------------------------------------------------
  43.  
  44. ; ------------------------------------------------------------------------------
  45. function vector_new.vectorC(elements% = 0)
  46. ; create a new vector
  47.  
  48.         our_vector.vectorC = new vectorC
  49.         our_vectorank = createbank(0)
  50.         vector_resize(our_vector, elements)   ; also sets last_element to elements-1
  51.         return our_vector
  52. end function
  53.  
  54. ; ------------------------------------------------------------------------------
  55. function vector_destroy(our_vector.vectorC)
  56. ; delete a vector and all of its elements
  57.  
  58.         freebank(our_vectorank)
  59.         delete our_vector
  60. end function
  61.  
  62. ; ------------------------------------------------------------------------------
  63. function vector_set(our_vector.vectorC, index%, value)
  64. ; set value at specified index
  65.  
  66.         if our_vector = null then runtimeerror("not a valid vectorC: null")
  67.         if (index < 0) then index = our_vectorlast_element+1 + index                   ; negative indexes reference elements in reverse order
  68.         if (index < 0 or index > our_vectorlast_element) then runtimeerror("element out of range: "+index)
  69.         pokeint(our_vectorank, 4 * index, value)
  70. end function
  71.  
  72. ; ------------------------------------------------------------------------------
  73. function vector_get(our_vector.vectorC, index%)
  74. ; get value at specified index
  75.  
  76.         if our_vector = null then runtimeerror("not a valid vectorC: null")
  77.         if (index < 0) then index = our_vectorlast_element+1 + index                   ; negative indexes reference elements in reverse order
  78.         if (index < 0 or index > our_vectorlast_element) then runtimeerror("element out of range: "+index)
  79.         return peekint(our_vectorank, 4 * index)
  80. end function
  81.  
  82. ; ------------------------------------------------------------------------------
  83. function vector_resize(our_vector.vectorC, elements%)
  84. ; set the size of the vector
  85.  
  86.         if our_vector = null then runtimeerror("not a valid vectorC: null")
  87.         resizebank(our_vectorank, 4 * elements)
  88.         our_vectorelements_allocated = elements
  89.         our_vectorlast_element = elements - 1
  90. end function
  91.  
  92. ; ------------------------------------------------------------------------------
  93. function vector_count(our_vector.vectorC)
  94. ; return the number of elements in the vector
  95.  
  96.         if our_vector = null then runtimeerror("not a valid vectorC: null")
  97.         return our_vectorlast_element + 1
  98. end function
  99.  
  100. ; ------------------------------------------------------------------------------
  101. ;= STACK OPERATIONS
  102. ; ------------------------------------------------------------------------------
  103. function vector_push(our_vector.vectorC, value)
  104. ; add a new element to the end of the vector
  105.  
  106.         if our_vector = null then runtimeerror("not a valid vectorC: null")
  107.         ; allocate more space if required
  108.         if our_vectorelements_allocated-1 = our_vectorlast_element then
  109.                 our_vectorelements_allocated = our_vectorelements_allocated + VECTORS_EXPAND_BY
  110.                 resizebank(our_vectorank, 4 * our_vectorelements_allocated)
  111.         endif
  112.         ; store the new value
  113.         our_vectorlast_element = our_vectorlast_element + 1
  114.         pokeint(our_vectorank, 4 * our_vectorlast_element, value)
  115. end function
  116.  
  117. ; ------------------------------------------------------------------------------
  118. function vector_pop(our_vector.vectorC)
  119. ; remove an element from the end of the vector
  120.  
  121.         if our_vector = null then runtimeerror("not a valid vectorC: null")
  122.         if our_vectorlast_element = -1 then return 0
  123.         our_vectorlast_element = our_vectorlast_element - 1
  124.         return peekint(our_vectorank, 4 * (our_vectorlast_element + 1))
  125. end function
  126.  
  127. ; ------------------------------------------------------------------------------
  128. function vector_alloc(our_vector.vectorC, elements%)
  129. ; preallocate a bunch of space for push() operations
  130.  
  131.         if our_vector = null then runtimeerror("not a valid vectorC: null")
  132.         if elements < our_vectorlast_element + 1 then runtimeerror("cannot alloc less space than is currently being used")
  133.         our_vectorelements_allocated = elements
  134.         resizebank(our_vectorank, 4 * our_vectorelements_allocated)
  135. end function
  136.  
  137. ; ------------------------------------------------------------------------------
  138. ;= SLOW OPERATIONS
  139. ; ------------------------------------------------------------------------------
  140. function vector_remove_element(our_vector.vectorC, index%)
  141. ; remove an element from anywhere in a vector
  142.  
  143.         if our_vector = null then runtimeerror("not a valid vectorC: null")
  144.         if (index < 0) then index = our_vectorlast_element+1 + index                   ; negative indexes reference elements in reverse order
  145.         if (index < 0 or index > our_vectorlast_element) then runtimeerror("element out of range: "+index)
  146.         value = peekint(our_vectorank, 4 * index)
  147.         our_vectorlast_element = our_vectorlast_element - 1
  148.         ; move elements backward to cover our hole
  149.         copybank(our_vectorank, 4*(index+1), our_vectorank, 4*index, 4*(our_vectorlast_element+1 - index))
  150.         return value
  151. end function
  152.  
  153. ; ------------------------------------------------------------------------------
  154. function vector_insert_before(our_vector.vectorC, index%, value)
  155. ; add a new element before an existing one
  156. ; note that we allow a reference index of our_vectorlast_element+1 (which is dispatched to vector_push() anyways)
  157.  
  158.  
  159.         if our_vector = null then runtimeerror("not a valid vectorC: null")
  160.         if (index < 0) then index = our_vectorlast_element+1 + index                   ; negative indexes reference elements in reverse order
  161.         if index = our_vectorlast_element+1 then return vector_push(our_vector, value) ; much faster alternative!
  162.         if (index < 0 or index > our_vectorlast_element) then runtimeerror("element out of range: "+index)
  163.         ; allocate more space if required
  164.         if our_vectorelements_allocated-1 = our_vectorlast_element then
  165.                 our_vectorelements_allocated = our_vectorelements_allocated + VECTORS_EXPAND_BY
  166.                 resizebank(our_vectorank, 4 * our_vectorelements_allocated)
  167.         endif
  168.         ; move elements forward
  169.         copybank(our_vectorank, 4*(index), our_vectorank, 4*(index+1), 4*(our_vectorlast_element+1 - index))
  170.         our_vectorlast_element = our_vectorlast_element + 1
  171.         ; set our new value
  172.         pokeint(our_vectorank, 4 * index, value)
  173. end function
  174.  
  175. ; ------------------------------------------------------------------------------
  176. function vector_insert_after(our_vector.vectorC, index%, value)
  177. ; add a new element after an existing one
  178.         if (index < 0) then index = our_vectorlast_element+1 + index                   ; negative indexes reference elements in reverse order
  179.         return vector_insert_before(our_vector, index+1, value)
  180. end function
  181.  
  182. ; ------------------------------------------------------------------------------
  183. function vector_shift(our_vector.vectorC)
  184. ; add a new element after an existing one
  185.         return vector_remove_element(our_vector, 0)
  186. end function
  187.  
  188. ; ------------------------------------------------------------------------------
  189. function vector_unshift(our_vector.vectorC, value)
  190. ; add a new element to the front of the vector
  191.         vector_insert_before(our_vector, 0, value)
  192. end function
  193.  
  194. ; ------------------------------------------------------------------------------
  195. ;= ITERATORS
  196. ; ------------------------------------------------------------------------------
  197.  
  198. ; sample usage
  199.  
  200. ; ; for item.type = each vector
  201. ;       it.vectorC_iter = vector_iterator_begin(vector)
  202. ;       while vector_iterator_next(it)
  203. ;               item.type = object.type(vector_iterator_get(it))
  204. ;       wend
  205.  
  206.  
  207. ; ------------------------------------------------------------------------------
  208. function vector_iterator_begin.vectorC_iter(our_vector.vectorC)
  209. ; create a new iterator for traversing the vector forwards
  210.  
  211.         it.vectorC_iter = new vectorC_iter
  212.         if our_vector <> null then
  213.                 itvector = our_vector
  214.                 itforwards = true
  215.                 itcurrent_index = 0-1
  216.         endif
  217.         return it
  218. end function
  219.  
  220. ; ------------------------------------------------------------------------------
  221. function vector_iterator_begin_reverse.vectorC_iter(our_vector.vectorC)
  222. ; create a new iterator for traversing the vector backwards
  223.  
  224.         it.vectorC_iter = new vectorC_iter
  225.         if our_vector <> null then
  226.                 itvector = our_vector
  227.                 itforwards = false
  228.                 itcurrent_index = our_vectorlast_element+1
  229.         endif
  230.         return it
  231. end function
  232.  
  233. ; ------------------------------------------------------------------------------
  234. function vector_iterator_next(it.vectorC_iter)
  235. ; advance the iterator to the next element in the vector
  236.  
  237.         ; drop out immediately if this iterator is void
  238.         if itvector = null then return false
  239.        
  240.         if itforwards = true then
  241.                 itcurrent_index = itcurrent_index + 1
  242.                 if itcurrent_index > itvectorlast_element then delete it : return false
  243.         else
  244.                 itcurrent_index = itcurrent_index - 1
  245.                 if itcurrent_index < 0 then delete it : return false
  246.         endif
  247.         return true
  248. end function
  249.  
  250. ; ------------------------------------------------------------------------------
  251. function vector_iterator_get(it.vectorC_iter)
  252. ; return the value of the element the iterator is currently on
  253.  
  254.         return peekint(itvectorank, 4 * itcurrent_index)
  255. end function
  256.  
  257. ; ------------------------------------------------------------------------------
  258. ;= TESTING
  259. ; ------------------------------------------------------------------------------
  260. function vector_test()
  261.         print "vector_test()"
  262.  
  263.         sample_vector.vectorC = vector_new(2)
  264.  
  265.         vector_set(sample_vector, 0, 123)
  266.         vector_set(sample_vector, 1, 456)
  267.         vector_push(sample_vector, 789)
  268.         vector_unshift(sample_vector, 321)
  269.         vector_insert_after(sample_vector, -1, -100)
  270.  
  271.         it.vectorC_iter = vector_iterator_begin(sample_vector)
  272.         while vector_iterator_next(it)
  273.                 value = vector_iterator_get(it)
  274.                 print value
  275.         wend
  276.        
  277.  
  278.         print "press any key to exit..."
  279.         waitkey
  280.         end
  281.  
  282. end function


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal